# Skip List Implementation

The canonical OrderBook keeps both sides of the book in deterministic, nine-level skip lists. This note breaks down how the data structures map to the on-chain implementation.

## Deterministic Level Assignment

Unlike classic probabilistic skip lists that rely on random promotion, dBook derives the level for a price deterministically:

```solidity
function _getDistributedLevel(uint256 price) internal pure returns (uint8 nodeLevel) {
    uint256 hash = uint256(keccak256(abi.encode(price)));
    nodeLevel = 1;
    if ((hash & 0x3) == 0) {
        nodeLevel = 2;
        if ((hash >> 8 & 0x3) == 0) {
            nodeLevel = 3;
            // ... continues up to level 9 (SKIPLIST_MAX_LEVEL)
        }
    }
}
```

* Every price feeds the same hash, so level assignment is reproducible across chains and block replays.
* The bit tests create a geometric distribution (1/4 chance to climb each level) without touching block randomness.

To avoid adversarial sequences that only ever promote to level 1, the book also increments a counter per side and forces periodic promotion:

```solidity
function _nextForcedLevel(bool isBuy) internal returns (uint8 level) {
    uint64 count = isBuy ? ++buyPriceLevelInsertionCount : ++sellPriceLevelInsertionCount;
    level = 1;
    uint64 mask = count;
    while ((mask & 1) == 0 && level < SKIPLIST_MAX_LEVEL) {
        level++;
        mask >>= 1;
    }
}
```

`_addPriceLevel` picks the max of `_getDistributedLevel` and `_nextForcedLevel`, then rewires the `nextBuyPriceNode` or `nextSellPriceNode` arrays across all relevant levels.

## Sentinel Layout

* `BUY_SENTINEL_PRICE` is set to `type(uint256).max`. It anchors both the skip list and the active linked list on the bid side.
* `SELL_SENTINEL_PRICE` is zero. It anchors the ask side.
* The sentinels are marked as “active” so traversals have O(1) termination checks (`bestBidPrice == 0` iff the sentinel points to the opposite sentinel).

## Active Lists vs Skip Lists

The contract maintains two parallel structures per side:

1. **Skip list** – stored in `nextBuyPriceNode[price][level]` / `nextSellPriceNode`. These arrays let the engine jump multiple levels when scanning for match candidates.
2. **Active linked list** – stored in `nextActiveBuyPrice`, `prevActiveBuyPrice`, `nextActiveSellPrice`, `prevActiveSellPrice`. These are level-0 lists that make “next best price” lookups constant-time.

When volume at a price level drops to zero, `_removeEmptyPriceLevel` removes the node from both structures.

## Queue Positions & Fenwick Trees

Claim accounting relies on two supporting structures:

* `buyQueuePos` / `sellQueuePos` store the cumulative queue position (`position`) and a `reserved` baseline captured whenever the queue resets. This keeps `claimRangeStart` / `claimRangeEnd` meaningful across cancellations.
* Fenwick trees (`buyFwEnd`, `buyFwCancel`, and their sell-side counterparts) provide O(log n) updates when orders are cancelled in the middle of a queue. `_recordCancelledRemainder` bumps the relevant Fenwick entry immediately so later makers do not double-count claimable volume.

Each order stores a `(pointer, generation)` index retrieved via `_getOrderCancelIndex`. If the queue resets, the generation increments and stale indices are ignored.

## Matching Algorithm Recap

1. The taker picks the appropriate active list (`bestAskPrice` for buys, `bestBidPrice` for sells).
2. `_matchAtPriceLevel` reads the packed `PriceLevelData` for that price, decides how much to consume (`min(volume, takerRemaining)`), and updates cumulative claim trackers.
3. If the level is exhausted, `_removeEmptyPriceLevel` tears it out of both the skip list and the active list. Otherwise the level stays in place with reduced volume.
4. The taker moves to the next price using the active list pointers. No search over the skip list is required unless hints are provided (not used in the canonical contract).

## Practical Integration Notes

* Price traversal is deterministic. Off-chain simulators can reproduce the exact path by mirroring `bestBidPrice`, `bestAskPrice`, and the active list pointers.
* The deterministic level assignment means that replaying the same sequence of placements always produces the same skip list shape, simplifying debugging.
* When scraping on-chain data, prefer the active linked list (`nextActive*Price`) for real-time book reconstruction; the skip list arrays are primarily useful for audits.

Together, these structures keep insertion, removal, and matching costs predictable while avoiding dynamic memory allocations or expensive tree rotations.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dbookio.gitbook.io/dbook/technical-documentation/orderbook-contract/skip-list-implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.