This repository contains the data structures that are used in Morpho Optimizer's matching engine. The data structures are built to be secure and gas efficient.
The current implementation of the double-linked list is based on this article written by Alberto Cuesta Cañada. You can find the repository here. Note that the code has been modified to meet our own needs and to allow us to sort the first accounts of the double-linked list. Our implementation is not a generalized one. What you can do with it:
- Insert an address sorted by a value passed along this address.
- Insert (and its value) before an account.
A Red Black Binary Tree is a kind of binary tree that allows insertion/deletion/search in O(log(n)).
Our implementation is a modified version of the OrderStatisticsTree repository written by Rob Hitechn which is also based on BokkyPooBahsRedBlackTreeLibrary repository written by bokkypoobah.
Our modified version makes keys unique items instead of just (key, value) unique pairs.
In order to manipulate a binary tree and visualize how it manages to stay balanced, this tool is very useful. You can also find here the pseudo-code logic of the tree's function.
This implementation is based on a heap data structure and refines it by adding an unsorted portion after it. This gives us an approximation of a heap, and thus operations are performed in constant time.
At least the first maxSortedUsers / 2 addresses are sorted in the Heap. To keep constant time operation, we divide by two the size of the Heap once the size overtakes the maxSortedUsers number. It means that we remove all leaves of the heap.
The choice of this implementation is explained by the desire to store a maximum of high-value nodes in the heap to use them for peer-to-peer matching.
Indeed, a naive implementation that would remove the tail and insert new values at maxSortedUsers (once the heap is full), would end up concentrating all new values on the same single path from the leaf to the root node because the shiftUp function will be always called from the same node. The risk is that low-value nodes stay in the Heap and that all the liquidity will be concentrated on the path from the leaf of index 'maxSortedUsers' to the root.
Removing all the leaves enables the protocol to remove low-value nodes and to call the shiftUp function at different locations in the Heap. This process is meant to keep a maximum of liquidity available in the heap for peer-to-peer lending.
The main entry point is the update function, calling internally either insert, increase, decrease or remove.
Other data structures may be explored in the future and we are open to any suggestions or optimization of current implementations ⚡️
The code concerning the heap based ordering data-structure has been audited by Omniscia and the report can be found online or in the file Morpho_Omniscia.
The data structures are licensed under AGPL-3.0-only, see LICENSE.