use crate::book::common::types::{BookOrder, PriceSize, RunnerPrices};
use crate::book::protocol::command::Side;
use crate::book::protocol::reject::RejectReason;
use crate::types::{Money, OddsX10000, OrderId, RunnerId};
use serde::{Deserialize, Deserializer, Serialize, Serializer, de::Error as _};
use slab::Slab;
use std::collections::BTreeMap;
use std::num::NonZeroU32;
use std::ops::Bound;
use tracing::error;
const TICK_COUNT: usize = crate::types::odds::TICK_LADDER.len();
const LEVEL_PAGE_LEN: usize = 64;
const PAGE_COUNT: usize = TICK_COUNT.div_ceil(LEVEL_PAGE_LEN);
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[repr(transparent)]
pub(crate) struct OrderKey(NonZeroU32);
impl OrderKey {
fn from_slab_index(idx: usize) -> Self {
let raw = u32::try_from(idx)
.expect("order store exceeded u32::MAX slab slots")
.checked_add(1)
.expect("order store key overflow");
Self(unsafe { NonZeroU32::new_unchecked(raw) })
}
fn slab_index(self) -> usize {
(self.0.get() - 1) as usize
}
}
#[derive(Debug, Clone, Copy, Default)]
struct Links {
prev: Option<OrderKey>,
next: Option<OrderKey>,
}
#[derive(Debug, Clone)]
struct OrderSlot {
order: BookOrder,
links: Links,
in_level: bool,
level_side: Side,
level_tick: u16,
}
impl OrderSlot {
fn try_new(order: BookOrder) -> Result<Self, RejectReason> {
let Some(tick) = order.price.tick_index() else {
return Err(RejectReason::InvalidOdds);
};
Ok(Self {
level_side: order.info.side,
level_tick: tick as u16,
order,
links: Links::default(),
in_level: false,
})
}
}
#[derive(Debug, Clone, Default)]
pub(crate) struct OrderStore {
slab: Slab<OrderSlot>,
by_id: hashbrown::HashMap<OrderId, OrderKey>,
by_id_sorted: BTreeMap<OrderId, OrderKey>,
}
impl OrderStore {
pub(crate) fn with_capacity(capacity: usize) -> Self {
Self {
slab: Slab::with_capacity(capacity),
by_id: hashbrown::HashMap::with_capacity(capacity),
by_id_sorted: BTreeMap::new(),
}
}
pub(crate) fn get_key(&self, order_id: &OrderId) -> Option<OrderKey> {
self.by_id.get(order_id).copied()
}
pub(crate) fn contains(&self, order_id: &OrderId) -> bool {
self.by_id.contains_key(order_id)
}
pub(crate) fn get(&self, order_id: &OrderId) -> Option<&BookOrder> {
let key = self.get_key(order_id)?;
Some(&self.slab.get(key.slab_index())?.order)
}
pub(crate) fn get_mut(&mut self, order_id: &OrderId) -> Option<&mut BookOrder> {
let key = self.get_key(order_id)?;
Some(&mut self.slab.get_mut(key.slab_index())?.order)
}
fn slot(&self, key: OrderKey) -> &OrderSlot {
&self.slab[key.slab_index()]
}
fn slot_mut(&mut self, key: OrderKey) -> &mut OrderSlot {
&mut self.slab[key.slab_index()]
}
pub(crate) fn order_by_key(&self, key: OrderKey) -> &BookOrder {
&self.slot(key).order
}
pub(crate) fn stored_tick(&self, key: OrderKey) -> usize {
self.slot(key).level_tick as usize
}
pub(crate) fn in_level_by_key(&self, key: OrderKey) -> bool {
self.slot(key).in_level
}
pub(crate) fn insert(
&mut self,
order_id: OrderId,
order: BookOrder,
) -> Result<OrderKey, RejectReason> {
debug_assert_eq!(order_id, order.info.order_id);
let key = OrderKey::from_slab_index(self.slab.insert(OrderSlot::try_new(order)?));
self.by_id.insert(order_id, key);
self.by_id_sorted.insert(order_id, key);
Ok(key)
}
pub(crate) fn iter_sorted(&self) -> impl Iterator<Item = (OrderId, &BookOrder)> {
self.by_id_sorted
.iter()
.map(|(&oid, &key)| (oid, &self.slot(key).order))
}
pub(crate) fn iter_sorted_from(
&self,
cursor_after: Option<OrderId>,
) -> impl Iterator<Item = (OrderId, &BookOrder)> {
let range = match cursor_after {
Some(c) => (Bound::Excluded(c), Bound::Unbounded),
None => (Bound::Unbounded, Bound::Unbounded),
};
self.by_id_sorted
.range(range)
.map(|(&oid, &key)| (oid, &self.slot(key).order))
}
pub(crate) fn iter_keys_sorted(&self) -> impl Iterator<Item = (OrderId, OrderKey, &BookOrder)> {
self.by_id_sorted
.iter()
.map(|(&oid, &key)| (oid, key, &self.slot(key).order))
}
pub(crate) fn is_in_level(&self, order_id: &OrderId) -> bool {
let Some(&key) = self.by_id.get(order_id) else {
return false;
};
self.slot(key).in_level
}
pub(crate) fn remove(&mut self, order_id: &OrderId) -> Option<BookOrder> {
let key = self.by_id.remove(order_id)?;
self.by_id_sorted.remove(order_id);
Some(self.slab.remove(key.slab_index()).order)
}
}
impl Serialize for OrderStore {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
use serde::ser::SerializeMap;
let mut map = serializer.serialize_map(Some(self.by_id_sorted.len()))?;
for (&oid, &key) in &self.by_id_sorted {
map.serialize_entry(&oid, &self.slot(key).order)?;
}
map.end()
}
}
impl<'de> Deserialize<'de> for OrderStore {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
let orders = BTreeMap::<OrderId, BookOrder>::deserialize(deserializer)?;
let mut store = Self {
slab: Slab::with_capacity(orders.len()),
by_id: hashbrown::HashMap::with_capacity(orders.len()),
by_id_sorted: BTreeMap::new(),
};
for (oid, order) in orders {
let slot = OrderSlot::try_new(order)
.map_err(|err| D::Error::custom(format!("invalid order: {err:?}")))?;
let key = OrderKey::from_slab_index(store.slab.insert(slot));
store.by_id.insert(oid, key);
store.by_id_sorted.insert(oid, key);
}
Ok(store)
}
}
#[derive(Debug, Clone, Copy, Default)]
struct Bitset350 {
words: [u64; 6],
}
impl Bitset350 {
fn set(&mut self, idx: usize) {
if idx >= TICK_COUNT {
return;
}
let w = idx / 64;
let b = idx % 64;
self.words[w] |= 1u64 << b;
}
fn clear(&mut self, idx: usize) {
if idx >= TICK_COUNT {
return;
}
let w = idx / 64;
let b = idx % 64;
self.words[w] &= !(1u64 << b);
}
fn next_set_from(&self, start: usize) -> Option<usize> {
if start >= TICK_COUNT {
return None;
}
let mut w = start / 64;
let mut bits = self.words[w] & (!0u64 << (start % 64));
loop {
if bits != 0 {
return Some(w * 64 + bits.trailing_zeros() as usize);
}
w += 1;
if w >= self.words.len() {
return None;
}
bits = self.words[w];
}
}
fn prev_set_from(&self, start: usize) -> Option<usize> {
let start = start.min(TICK_COUNT.saturating_sub(1));
let mut w = start / 64;
let mut bits = self.words[w] & (!0u64 >> (63 - (start % 64)));
loop {
if bits != 0 {
return Some(w * 64 + (63 - bits.leading_zeros() as usize));
}
if w == 0 {
return None;
}
w -= 1;
bits = self.words[w];
}
}
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Level {
pub head: Option<OrderKey>,
pub tail: Option<OrderKey>,
pub total_remaining: Money,
}
impl Default for Level {
fn default() -> Self {
Self {
head: None,
tail: None,
total_remaining: Money::zero(),
}
}
}
#[derive(Debug, Clone)]
struct LevelPage {
levels: [Level; LEVEL_PAGE_LEN],
}
impl Default for LevelPage {
fn default() -> Self {
Self {
levels: [Level::default(); LEVEL_PAGE_LEN],
}
}
}
#[derive(Debug, Clone)]
pub(crate) struct SideBook {
page_refs: [u16; PAGE_COUNT],
pages: Vec<LevelPage>,
mask: Bitset350,
}
impl Default for SideBook {
fn default() -> Self {
Self {
page_refs: [0; PAGE_COUNT],
pages: Vec::new(),
mask: Bitset350::default(),
}
}
}
impl SideBook {
#[inline]
fn split_tick(tick: usize) -> (usize, usize) {
(tick / LEVEL_PAGE_LEN, tick % LEVEL_PAGE_LEN)
}
#[inline]
fn page_index(&self, page_idx: usize) -> Option<usize> {
match self.page_refs[page_idx] {
0 => None,
n => Some((n - 1) as usize),
}
}
#[inline]
fn level_ref(&self, tick: usize) -> Option<&Level> {
debug_assert!(tick < TICK_COUNT, "tick out of range: {tick}");
let (page_idx, slot_idx) = Self::split_tick(tick);
let page_idx = self.page_index(page_idx)?;
Some(&self.pages[page_idx].levels[slot_idx])
}
#[inline]
fn level_mut(&mut self, tick: usize) -> Option<&mut Level> {
debug_assert!(tick < TICK_COUNT, "tick out of range: {tick}");
let (page_idx, slot_idx) = Self::split_tick(tick);
let page_idx = self.page_index(page_idx)?;
Some(&mut self.pages[page_idx].levels[slot_idx])
}
#[inline]
fn level_mut_or_alloc(&mut self, tick: usize) -> &mut Level {
debug_assert!(tick < TICK_COUNT, "tick out of range: {tick}");
let (page_slot, slot_idx) = Self::split_tick(tick);
let page_idx = match self.page_index(page_slot) {
Some(page_idx) => page_idx,
None => {
debug_assert!(self.pages.len() < u16::MAX as usize);
self.pages.push(LevelPage::default());
let page_idx = self.pages.len() - 1;
self.page_refs[page_slot] = (page_idx as u16) + 1;
page_idx
}
};
&mut self.pages[page_idx].levels[slot_idx]
}
#[inline]
fn level_total_remaining(&self, tick: usize) -> Money {
self.level_ref(tick)
.map(|level| level.total_remaining)
.unwrap_or_else(Money::zero)
}
#[inline]
fn level_head(&self, tick: usize) -> Option<OrderKey> {
self.level_ref(tick).and_then(|level| level.head)
}
pub(crate) fn best_asc(&self) -> Option<usize> {
self.mask.next_set_from(0).filter(|&i| i < TICK_COUNT)
}
pub(crate) fn best_desc(&self) -> Option<usize> {
self.mask
.prev_set_from(TICK_COUNT - 1)
.filter(|&i| i < TICK_COUNT)
}
pub(crate) fn next_asc_from(&self, start: usize) -> Option<usize> {
self.mask.next_set_from(start).filter(|&i| i < TICK_COUNT)
}
pub(crate) fn next_desc_from(&self, start: usize) -> Option<usize> {
self.mask.prev_set_from(start).filter(|&i| i < TICK_COUNT)
}
}
#[derive(Debug, Clone, Default)]
pub(crate) struct RunnerBook {
pub back: SideBook,
pub lay: SideBook,
}
impl RunnerBook {
pub(crate) fn new() -> Self {
Self::default()
}
pub(crate) fn runner_prices(&self, runner_id: RunnerId, depth: usize) -> RunnerPrices {
let mut result = RunnerPrices {
runner_id,
available_to_back: Vec::with_capacity(depth),
available_to_lay: Vec::with_capacity(depth),
};
let mut tick = self.lay.best_desc();
while let Some(t) = tick {
if result.available_to_back.len() >= depth {
break;
}
let total_remaining = self.lay.level_total_remaining(t);
if total_remaining.0 > 0 {
result.available_to_back.push(PriceSize {
price: OddsX10000(crate::types::odds::TICK_LADDER[t]),
size: total_remaining,
});
}
if t == 0 {
break;
}
tick = self.lay.next_desc_from(t - 1);
}
let mut tick = self.back.best_asc();
while let Some(t) = tick {
if result.available_to_lay.len() >= depth {
break;
}
let total_remaining = self.back.level_total_remaining(t);
if total_remaining.0 > 0 {
result.available_to_lay.push(PriceSize {
price: OddsX10000(crate::types::odds::TICK_LADDER[t]),
size: total_remaining,
});
}
tick = self.back.next_asc_from(t + 1);
}
result
}
pub(crate) fn insert_tail(&mut self, orders: &mut OrderStore, key: OrderKey, remaining: Money) {
let (tick, side) = {
let s = orders.slot(key);
(s.level_tick as usize, s.level_side)
};
let book = match side {
Side::Yes => &mut self.back,
Side::No => &mut self.lay,
};
let mut set_mask = false;
{
let level = book.level_mut_or_alloc(tick);
if level.head.is_none() {
set_mask = true;
level.head = Some(key);
level.tail = Some(key);
} else {
let Some(tail) = level.tail else {
error!(tick, "tail missing for non-empty level");
return;
};
orders.slot_mut(tail).links.next = Some(key);
orders.slot_mut(key).links.prev = Some(tail);
level.tail = Some(key);
}
level.total_remaining = Money(level.total_remaining.0 + remaining.0);
}
if set_mask {
book.mask.set(tick);
}
let slot = orders.slot_mut(key);
slot.in_level = true;
slot.links.next = None;
}
pub(crate) fn unlink(&mut self, orders: &mut OrderStore, key: OrderKey, remaining: Money) {
let (tick, side, prev, next) = {
let slot = orders.slot(key);
(
slot.level_tick as usize,
slot.level_side,
slot.links.prev,
slot.links.next,
)
};
let book = match side {
Side::Yes => &mut self.back,
Side::No => &mut self.lay,
};
let became_empty = {
let Some(level) = book.level_mut(tick) else {
error!(tick, "level page missing during unlink");
return;
};
if level.head == Some(key) {
level.head = next;
}
if level.tail == Some(key) {
level.tail = prev;
}
if let Some(p) = prev {
orders.slot_mut(p).links.next = next;
}
if let Some(n) = next {
orders.slot_mut(n).links.prev = prev;
}
level.total_remaining = Money(level.total_remaining.0.saturating_sub(remaining.0));
level.head.is_none()
};
if became_empty {
book.mask.clear(tick);
}
let slot = orders.slot_mut(key);
slot.links = Links::default();
slot.in_level = false;
}
pub(crate) fn level_total_remaining(&self, side: Side, tick: usize) -> Money {
let book = match side {
Side::Yes => &self.back,
Side::No => &self.lay,
};
book.level_total_remaining(tick)
}
pub(crate) fn level_head(&self, side: Side, tick: usize) -> Option<OrderKey> {
let book = match side {
Side::Yes => &self.back,
Side::No => &self.lay,
};
book.level_head(tick)
}
pub(crate) fn best_tick_asc(&self, side: Side) -> Option<usize> {
let book = match side {
Side::Yes => &self.back,
Side::No => &self.lay,
};
book.best_asc()
}
pub(crate) fn best_tick_desc(&self, side: Side) -> Option<usize> {
let book = match side {
Side::Yes => &self.back,
Side::No => &self.lay,
};
book.best_desc()
}
pub(crate) fn next_tick_asc_from(&self, side: Side, start: usize) -> Option<usize> {
let book = match side {
Side::Yes => &self.back,
Side::No => &self.lay,
};
book.next_asc_from(start)
}
pub(crate) fn next_tick_desc_from(&self, side: Side, start: usize) -> Option<usize> {
let book = match side {
Side::Yes => &self.back,
Side::No => &self.lay,
};
book.next_desc_from(start)
}
pub(crate) fn iter_level_keys<'a>(
&'a self,
side: Side,
tick: usize,
orders: &'a OrderStore,
) -> LevelKeyIter<'a> {
LevelKeyIter {
orders,
cur: self.level_head(side, tick),
}
}
pub(crate) fn decrement_level_total(&mut self, side: Side, tick: usize, delta: Money) {
let book = match side {
Side::Yes => &mut self.back,
Side::No => &mut self.lay,
};
let Some(level) = book.level_mut(tick) else {
error!(tick, "level page missing during decrement");
return;
};
level.total_remaining = Money(level.total_remaining.0.saturating_sub(delta.0));
}
}
pub(crate) struct LevelKeyIter<'a> {
orders: &'a OrderStore,
cur: Option<OrderKey>,
}
impl<'a> Iterator for LevelKeyIter<'a> {
type Item = OrderKey;
fn next(&mut self) -> Option<Self::Item> {
let cur = self.cur?;
self.cur = self.orders.slot(cur).links.next;
Some(cur)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn bitset350_set_out_of_range_does_not_panic() {
let mut b = Bitset350::default();
let res = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| b.set(400)));
assert!(res.is_ok(), "set should ignore out-of-range indices");
assert_eq!(b.next_set_from(0), None);
}
#[test]
fn bitset350_clear_out_of_range_does_not_panic() {
let mut b = Bitset350::default();
b.set(10);
let res = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| b.clear(400)));
assert!(res.is_ok(), "clear should ignore out-of-range indices");
assert_eq!(b.next_set_from(0), Some(10));
}
fn sample_order(order_id: OrderId, side: Side, price: OddsX10000) -> BookOrder {
BookOrder {
info: crate::book::common::types::BookOrderInfo {
order_id,
account_id: crate::types::AccountId::from(1_u64),
correlation_id: None,
side,
state: crate::book::common::types::BookOrderState::ExecutableUnmatched,
created_at: chrono::Utc::now(),
last_updated_at: chrono::Utc::now(),
},
runner_id: RunnerId(1),
price,
stake: Money(100),
matched: Money::zero(),
persistence: crate::book::protocol::command::Persistence::Persist,
}
}
#[test]
fn sidebook_allocates_one_page_on_first_touch() {
let mut store = OrderStore::with_capacity(1);
let mut book = RunnerBook::new();
let key = store
.insert(
OrderId(1),
sample_order(
OrderId(1),
Side::Yes,
OddsX10000(crate::types::odds::TICK_LADDER[10]),
),
)
.expect("valid order");
book.insert_tail(&mut store, key, Money(100));
assert_eq!(book.back.pages.len(), 1);
assert_eq!(book.back.page_refs[0], 1);
assert_eq!(book.back.best_asc(), Some(10));
}
#[test]
fn sidebook_unlink_clears_tick_bit_but_retains_page() {
let mut store = OrderStore::with_capacity(1);
let mut book = RunnerBook::new();
let key = store
.insert(
OrderId(1),
sample_order(
OrderId(1),
Side::Yes,
OddsX10000(crate::types::odds::TICK_LADDER[10]),
),
)
.expect("valid order");
book.insert_tail(&mut store, key, Money(100));
book.unlink(&mut store, key, Money(100));
assert_eq!(book.back.pages.len(), 1);
assert_eq!(book.back.best_asc(), None);
assert_eq!(book.level_total_remaining(Side::Yes, 10), Money::zero());
assert_eq!(book.level_head(Side::Yes, 10), None);
}
#[test]
fn sidebook_reuses_page_after_tick_reactivates() {
let mut store = OrderStore::with_capacity(2);
let mut book = RunnerBook::new();
let key1 = store
.insert(
OrderId(1),
sample_order(
OrderId(1),
Side::Yes,
OddsX10000(crate::types::odds::TICK_LADDER[10]),
),
)
.expect("valid order");
book.insert_tail(&mut store, key1, Money(100));
book.unlink(&mut store, key1, Money(100));
let key2 = store
.insert(
OrderId(2),
sample_order(
OrderId(2),
Side::Yes,
OddsX10000(crate::types::odds::TICK_LADDER[10]),
),
)
.expect("valid order");
book.insert_tail(&mut store, key2, Money(100));
assert_eq!(book.back.pages.len(), 1);
assert_eq!(book.level_head(Side::Yes, 10), Some(key2));
assert_eq!(book.level_total_remaining(Side::Yes, 10), Money(100));
}
#[test]
fn sidebook_allocates_multiple_pages_for_distant_ticks() {
let mut store = OrderStore::with_capacity(2);
let mut book = RunnerBook::new();
let key_a = store
.insert(
OrderId(1),
sample_order(
OrderId(1),
Side::Yes,
OddsX10000(crate::types::odds::TICK_LADDER[10]),
),
)
.expect("valid order");
let key_b = store
.insert(
OrderId(2),
sample_order(
OrderId(2),
Side::Yes,
OddsX10000(crate::types::odds::TICK_LADDER[130]),
),
)
.expect("valid order");
book.insert_tail(&mut store, key_a, Money(100));
book.insert_tail(&mut store, key_b, Money(200));
assert_eq!(book.back.pages.len(), 2);
assert_eq!(book.back.page_refs[0], 1);
assert_eq!(book.back.page_refs[2], 2);
assert_eq!(book.back.best_asc(), Some(10));
assert_eq!(book.back.next_asc_from(11), Some(130));
assert_eq!(book.level_total_remaining(Side::Yes, 10), Money(100));
assert_eq!(book.level_total_remaining(Side::Yes, 130), Money(200));
}
#[test]
fn decrement_level_total_missing_page_is_noop() {
let mut book = RunnerBook::new();
book.decrement_level_total(Side::Yes, 130, Money(50));
assert_eq!(book.back.pages.len(), 0);
assert_eq!(book.level_total_remaining(Side::Yes, 130), Money::zero());
assert_eq!(book.level_head(Side::Yes, 130), None);
}
#[test]
fn absent_page_behaves_as_empty_level() {
let book = RunnerBook::new();
assert_eq!(book.level_total_remaining(Side::Yes, 25), Money::zero());
assert_eq!(book.level_head(Side::Yes, 25), None);
assert_eq!(
book.iter_level_keys(Side::Yes, 25, &OrderStore::with_capacity(0))
.count(),
0
);
}
}