DoubleLinkedList
Library used to implement the data structure managing the priority queue used in Morpho's matching engine.
The Morpho protocol uses a semi-sorted Double Linked List to manage its priority queues. For each market, there are 2 priority queues: one for each supply & borrow side. In each priority queue, users are ordered from largest to lowest amount, up until a specific rank maxSortedUsers (to limit the gas consumption at insertion), set by governance. After this rank, users are not guaranteed to get ordered according to a specific criterion.
Insertion thus happens in O(maxSortedUsers) time complexity and removal is in O(1).
The implementation works as follows:
  • Each entity in the DLL stores information about the amount, the previous element in the DLL (null in case it's the head) and the next element in the DLL (null in case it's the tail).
  • At insertion, a new entity is added either at the first slot maintaining order within the maxSortedUsers first slots; or right after the tail.
  • At removal, the storage of the corresponding entity is purged and the previous entity is linked to the next entity (relative to the removed entity).
Research is actively led to implement, test and compare alternative data structures.
https://github.com/morpho-labs/morpho-contracts/blob/main/contracts/common/libraries/DoubleLinkedList.sol
github.com
DoubleLinkedList source code
Copy link