/
PriorityQueue.sol
82 lines (67 loc) · 3.47 KB
/
PriorityQueue.sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// SPDX-License-Identifier: MIT
pragma solidity 0.8.20;
/// @notice The structure that contains meta information of the L2 transaction that was requested from L1
/// @dev The weird size of fields was selected specifically to minimize the structure storage size
/// @param canonicalTxHash Hashed L2 transaction data that is needed to process it
/// @param expirationTimestamp Expiration timestamp for this request (must be satisfied before)
/// @param layer2Tip Additional payment to the validator as an incentive to perform the operation
struct PriorityOperation {
bytes32 canonicalTxHash;
uint64 expirationTimestamp;
uint192 layer2Tip;
}
/// @author Matter Labs
/// @custom:security-contact security@matterlabs.dev
/// @dev The library provides the API to interact with the priority queue container
/// @dev Order of processing operations from queue - FIFO (Fist in - first out)
library PriorityQueue {
using PriorityQueue for Queue;
/// @notice Container that stores priority operations
/// @param data The inner mapping that saves priority operation by its index
/// @param head The pointer to the first unprocessed priority operation, equal to the tail if the queue is empty
/// @param tail The pointer to the free slot
struct Queue {
mapping(uint256 => PriorityOperation) data;
uint256 tail;
uint256 head;
}
/// @notice Returns zero if and only if no operations were processed from the queue
/// @return Index of the oldest priority operation that wasn't processed yet
function getFirstUnprocessedPriorityTx(Queue storage _queue) internal view returns (uint256) {
return _queue.head;
}
/// @return The total number of priority operations that were added to the priority queue, including all processed ones
function getTotalPriorityTxs(Queue storage _queue) internal view returns (uint256) {
return _queue.tail;
}
/// @return The total number of unprocessed priority operations in a priority queue
function getSize(Queue storage _queue) internal view returns (uint256) {
return uint256(_queue.tail - _queue.head);
}
/// @return Whether the priority queue contains no operations
function isEmpty(Queue storage _queue) internal view returns (bool) {
return _queue.tail == _queue.head;
}
/// @notice Add the priority operation to the end of the priority queue
function pushBack(Queue storage _queue, PriorityOperation memory _operation) internal {
// Save value into the stack to avoid double reading from the storage
uint256 tail = _queue.tail;
_queue.data[tail] = _operation;
_queue.tail = tail + 1;
}
/// @return The first unprocessed priority operation from the queue
function front(Queue storage _queue) internal view returns (PriorityOperation memory) {
require(!_queue.isEmpty(), "D"); // priority queue is empty
return _queue.data[_queue.head];
}
/// @notice Remove the first unprocessed priority operation from the queue
/// @return priorityOperation that was popped from the priority queue
function popFront(Queue storage _queue) internal returns (PriorityOperation memory priorityOperation) {
require(!_queue.isEmpty(), "s"); // priority queue is empty
// Save value into the stack to avoid double reading from the storage
uint256 head = _queue.head;
priorityOperation = _queue.data[head];
delete _queue.data[head];
_queue.head = head + 1;
}
}