- Generated by
1.18.0
|
Leka
A low-latency C++20 price-time-priority limit order book and matching engine
|
Fixed-range, tick-indexed array of PriceLevel slots for one side of a book. More...
#include <price_ladder.hpp>
Public Member Functions | |
| PriceLadder (Price minPrice, Price tickSize, std::size_t levelCount, bool descending) | |
| Pre-allocates every level the ladder will ever hold. | |
| PriceLadder (const PriceLadder &)=delete | |
| PriceLadder & | operator= (const PriceLadder &)=delete |
| PriceLadder (PriceLadder &&)=delete | |
| PriceLadder & | operator= (PriceLadder &&)=delete |
| PriceLevel & | levelAt (Price price) |
| Returns the level slot for a price; the slot always exists. | |
| void | markOccupied (Price price) |
| Marks a level occupied; call exactly once when its order count transitions from zero to nonzero. | |
| void | markEmpty (Price price) |
| Marks a level empty; call exactly once when its order count transitions from nonzero to zero. | |
| PriceLevel * | best () |
| Returns the best occupied level, or nullptr when the side is empty. | |
| const PriceLevel * | best () const |
| Returns the best occupied level for read-only inspection. | |
| std::size_t | occupiedCount () const |
| Returns the number of currently occupied levels. | |
| template<typename Fn> requires std::invocable<Fn&, const PriceLevel&> | |
| void | forEachOccupied (std::size_t maxLevels, Fn &&fn) const |
Walks up to maxLevels occupied levels, best first. | |
Static Public Attributes | |
| static constexpr std::size_t | npos = static_cast<std::size_t>(-1) |
| Sentinel returned when no level is occupied. | |
Fixed-range, tick-indexed array of PriceLevel slots for one side of a book.
A price is not treated as an ordered-map key; it is treated as an index. Every level in [minPrice, minPrice + (levelCount-1)*tickSize] is constructed once, at PriceLadder construction, and never destroyed or moved for the ladder's lifetime. Adding an order at a price that already has resting orders, or that has never had one, is the same O(1) array access with no allocation and no tree rebalancing; the old std::map<Price, PriceLevel> design paid a node allocation for the former and a pointer-chasing tree descent for the latter on every best-of-book query.
Because PriceLevel addresses are stable for the ladder's lifetime, Order's cached PriceLevel* pointer stays valid across every insert and remove at any other price: nothing is ever reallocated out from under it.
"Best" is always the lowest occupied index. Index 0 is the worst price a resting order can have on that side, so the two sides differ only in which direction price increases with index: ascending for asks (index 0 is the lowest, hence best, ask) and descending for bids (index 0 is the highest, hence best, bid). This lets both sides share one implementation and one "lowest set bit" query instead of a min-heap on one side and a max-heap on the other.
Occupancy is tracked in a bitset rather than by asking each PriceLevel whether it is empty, so finding the best level after it empties is a hardware find-first-set over a handful of 64-bit words rather than a linear scan of PriceLevel objects. The best index is additionally cached, so the common case, a level away from the current best changing occupancy, costs one array access and one bit flip with no search at all.
Definition at line 46 of file price_ladder.hpp.
| lob::PriceLadder::PriceLadder | ( | Price | minPrice, |
| Price | tickSize, | ||
| std::size_t | levelCount, | ||
| bool | descending ) |
Pre-allocates every level the ladder will ever hold.
| minPrice | Lowest representable price on this side. |
| tickSize | Price increment between adjacent indices. |
| levelCount | Number of representable price levels. |
| descending | True for the bid side, where index 0 is the highest price rather than the lowest. |
| std::invalid_argument | if minPrice is zero, tickSize is zero, levelCount is zero, or the configured range overflows. |
Definition at line 8 of file price_ladder.cpp.
| PriceLevel & lob::PriceLadder::levelAt | ( | Price | price | ) |
Returns the level slot for a price; the slot always exists.
| std::out_of_range | if the price falls outside the configured range. |
| std::invalid_argument | if the price does not fall on a configured tick boundary. |
Definition at line 60 of file price_ladder.cpp.
| void lob::PriceLadder::markOccupied | ( | Price | price | ) |
Marks a level occupied; call exactly once when its order count transitions from zero to nonzero.
Setting bits and lowering a cached minimum are both O(1); nothing here ever searches.
Definition at line 68 of file price_ladder.cpp.
| void lob::PriceLadder::markEmpty | ( | Price | price | ) |
Marks a level empty; call exactly once when its order count transitions from nonzero to zero.
Clearing a bit is O(1). Re-deriving the best index is only needed when the level that just emptied WAS the best index; every other call is O(1) as well. That one case scans forward from the vacated index for the next set bit, which is a handful of instructions per 64-bit word rather than a per-level check, and in practice terminates almost immediately because resting liquidity clusters near the touch.
Definition at line 85 of file price_ladder.cpp.
References npos.
Referenced by lob::OrderBook::removeOrder().
| PriceLevel * lob::PriceLadder::best | ( | ) |
Returns the best occupied level, or nullptr when the side is empty.
Definition at line 115 of file price_ladder.cpp.
References npos.
| const PriceLevel * lob::PriceLadder::best | ( | ) | const |
Returns the best occupied level for read-only inspection.
Definition at line 119 of file price_ladder.cpp.
References npos.
|
inline |
Returns the number of currently occupied levels.
Definition at line 98 of file price_ladder.hpp.
|
inline |
Walks up to maxLevels occupied levels, best first.
Read-only traversal for market-data snapshots. Because "best" is always the lowest occupied index on either side (see the class comment), walking outward from the touch is the same forward bit-scan on both bids and asks, and it visits levels in true price priority order without sorting anything.
This deliberately stops after maxLevels rather than walking the whole ladder: a snapshot consumer wants the top of book, and the ladder may span hundreds of thousands of mostly-empty levels.
Definition at line 115 of file price_ladder.hpp.
References npos.
|
staticconstexpr |
Sentinel returned when no level is occupied.
Definition at line 49 of file price_ladder.hpp.
Referenced by best(), best(), forEachOccupied(), and markEmpty().
1.18.0