- Generated by
1.18.0
|
Leka
A low-latency C++20 price-time-priority limit order book and matching engine
|
Open-addressed OrderId -> Order* index with average O(1) lookup. More...
#include <order_index.hpp>
Public Member Functions | |
| void | addOrder (Order *order) |
| Adds an order and rejects duplicate IDs. | |
| void | removeOrder (Order *order) |
| Removes an order after verifying pointer identity. | |
| Order * | findOrder (const OrderId &orderId) const |
| Finds an order by ID, or returns nullptr when absent. | |
| std::size_t | size () const |
| Returns the number of indexed orders. | |
| void | reserve (std::size_t orderCount) |
Grows the table, if needed, so orderCount entries fit under MaxLoadFactor without a later doubling. | |
Open-addressed OrderId -> Order* index with average O(1) lookup.
OrderId::isValid() reserves zero, which lets an empty Slot's default OrderId double as the "unoccupied" sentinel: no separate occupancy bitmap or tombstone state is needed. Slots live in one contiguous std::vector, so every element of the whole probe sequence for a lookup is one flat array, not the one-heap-allocation-per-entry, pointer-chasing structure a chained hash table (such as std::unordered_map) builds.
This is called on every add, cancel, reduce, and fill, so it is the hottest lookup in the engine. Unlike PriceLevel's PriceLadder, there is no natural fixed bound on how many orders can be live at once, so this grows by amortized doubling like std::vector rather than being pre-sized once.
Removal uses backward-shift deletion rather than tombstones: on removal, every following entry in the same probe run is shifted back into the vacated slot if doing so keeps it reachable, and the search for the next vacated slot continues until a genuinely empty one is found. This keeps lookups a single clean scan for empty forever, with no growing tombstone debt from a long session with many cancels, at the cost of removal being more than a single slot write.
Definition at line 35 of file order_index.hpp.
| void lob::OrderIndex::addOrder | ( | Order * | order | ) |
Adds an order and rejects duplicate IDs.
Only checks this index's own invariants: that order is non-null and that its ID is not already present. It does not re-check order's overall field validity (side, type, price, quantity, timestamp) — that is OrderBook::addOrderWithQuantities's job, and it always runs before an order reaches any book structure, this index included. PriceLevel::addOrder follows the same division: each class enforces only the invariant it alone owns, rather than every class re-verifying the whole Order on every insert.
Does not call order->isValid(): OrderBook::addOrderWithQuantities already does, before the order is linked into any book structure, so repeating it here would re-check the same fields on every accepted insert for an order this index cannot yet have any reason to distrust. See the header for the full reasoning.
Definition at line 115 of file order_index.cpp.
References lob::Order::getOrderId().
| void lob::OrderIndex::removeOrder | ( | Order * | order | ) |
Removes an order after verifying pointer identity.
Removes a mapping only when its pointer identity also matches.
Definition at line 137 of file order_index.cpp.
References lob::Order::getOrderId().
Finds an order by ID, or returns nullptr when absent.
Performs average constant-time lookup by OrderId.
Definition at line 170 of file order_index.cpp.
|
inline |
Returns the number of indexed orders.
Definition at line 59 of file order_index.hpp.
| void lob::OrderIndex::reserve | ( | std::size_t | orderCount | ) |
Grows the table, if needed, so orderCount entries fit under MaxLoadFactor without a later doubling.
Unlike PriceLadder, this table has no fixed bound to pre-size to exactly, so it still grows on demand for anyone who does not call this first (see the class comment). But a table that doubles while holding many live entries pays for an O(n) rehash of everything still indexed at the moment it happens, not the O(1) amortized cost the growth policy implies on average — a single one of those, late in a run with a large book, is a real tail-latency event (see ARCH_DECISIONS.md ADR-008). Calling this once, for a known or comfortably over-estimated order count, moves that rehash out of the hot path the same way OrderPool::reserve() moves page creation out of it.
Shares the doubling-and-rehash body with growIfNeeded() by simply picking the target capacity up front and looping the same "not big enough yet, double again" test growIfNeeded() uses one step at a time. Never shrinks: reserving a smaller count than the table already holds is a no-op.
Definition at line 63 of file order_index.cpp.
1.18.0