Skip to main content

MaxPriorityQueue

Git Source

This library implements a max priority queue using a linked list. We can achieve ~O(1) insertion by providing optimal hints for the insert position. The linked list design automatically gives us O(1) removal of the max bid.

State Variables​

QUEUE_START​

bytes32 internal constant QUEUE_START =
    0x0000000000000000ffffffffffffffffffffffff000000000000000000000001;

QUEUE_END​

bytes32 internal constant QUEUE_END =
    0xffffffffffffffff000000000000000000000000000000000000000000000001;

Functions​

initialize​

function initialize(Queue storage self) internal;

contains​

function contains(Queue storage self, bytes32 value) internal view returns (bool);

insert​

function insert(
    Queue storage self,
    bytes32 prev_,
    uint64 bidId_,
    uint96 amountIn_,
    uint96 minAmountOut_,
    uint256 baseScale_
) internal;

delMax​

Remove the max bid from the queue and return it.

function delMax(Queue storage self) internal returns (uint64, uint96, uint96);

getMax​

Return the max bid from the queue without removing it.

function getMax(Queue storage self) internal view returns (uint64, uint96, uint96);

getNext​

Return the key following the provided key

function getNext(Queue storage self, bytes32 key) internal view returns (bytes32);

getNumBids​

Return the number of bids in the queue.

function getNumBids(Queue storage self) internal view returns (uint256);

isEmpty​

Return true if the queue is empty.

function isEmpty(Queue storage self) internal view returns (bool);