Struct RadixCache 

pub struct RadixCache {
    pub page_pool: PagePool,
    pub evictable_leaves: FxHashSet<NodeId>,
    pub evictable_size: usize,
    pub protected_size: usize,
    /* private fields */
}

Radix tree for SGLang KV cache simulation.

Fields

page_pool: PagePool

evictable_leaves: FxHashSet<NodeId>

Total token count in evictable nodes.

evictable_size: usize

protected_size: usize

Total token count in protected (locked) nodes.

Implementations

impl RadixCache

pub fn new(total_tokens: usize, page_size: usize) -> Self

pub fn root(&self) -> NodeId

pub fn node(&self, id: NodeId) -> &TreeNode

pub fn page_size(&self) -> usize

pub fn num_nodes(&self) -> usize

pub fn match_prefix(&mut self, key: &[u32]) -> (usize, NodeId)

pub fn prefix_match_len(&self, key: &[u32]) -> usize

Read-only prefix match length (does not mutate timestamps or split nodes). Used for LPM scheduling scoring.

pub fn insert(&mut self, key: &[u32], value: &[usize]) -> NodeId

Insert a token sequence into the tree. Key is page-aligned before insertion.

pub fn insert_from_node( &mut self, prefix_node: NodeId, prefix_len: usize, key: &[u32], value: &[usize], ) -> NodeId

Insert only the suffix after a retained, page-aligned prefix.

prefix_node must be the locked terminal node for prefix_len. Keeping that handle lets decode growth avoid walking the full sequence from the root on every completed page.

pub fn is_leaf(&self, id: NodeId) -> bool

pub fn inc_lock_ref(&mut self, node_id: NodeId)

pub fn dec_lock_ref(&mut self, node_id: NodeId)

pub fn evict(&mut self, num_tokens: usize) -> (usize, Vec<KvPageId>)

Evict tokens from the cache by LRU order, rounding partial leaves to full pages. Returns (num_tokens_evicted, evicted_page_ids).

pub fn available_tokens(&self) -> usize

pub fn total_tokens(&self) -> usize