Skip to main content

qualia_core_db/inference/runtime/kv/prefix/
radix.rs

1pub use etalon_inference::runtime::kv::prefix::radix::*;
2
3#[cfg(test)]
4use super::super::paged::{BlockPool, SequenceBlockTable};
5
6#[cfg(test)]
7mod tests {
8    use super::*;
9
10    #[test]
11    fn test_radix_match_and_osrp_logit_withhold() {
12        let mut index = RadixPrefixIndex::<16>::new();
13
14        // Page 1: tokens 1..=16
15        let p1_tokens: [u32; 16] = core::array::from_fn(|i| (i + 1) as u32);
16        let n1 = index.insert_child_page(None, &p1_tokens, 100, 1).unwrap();
17
18        // Page 2: tokens 17..=32
19        let p2_tokens: [u32; 16] = core::array::from_fn(|i| (i + 17) as u32);
20        index
21            .insert_child_page(Some(n1), &p2_tokens, 200, 1)
22            .unwrap();
23
24        let mut out_pages = [0u32; 4];
25
26        // 1. Partial query matching only Page 1 + 5 tokens of Page 2
27        let mut query = Vec::new();
28        query.extend_from_slice(&p1_tokens);
29        query.extend_from_slice(&p2_tokens[..5]);
30
31        let (matched, reusable, pages) = index
32            .match_longest_prefix(&query, 2, &mut out_pages)
33            .unwrap();
34        // Page 1 matched completely; Page 2 was partial, so only Page 1 is matched
35        assert_eq!(matched, 16);
36        assert_eq!(reusable, 16);
37        assert_eq!(pages, 1);
38        assert_eq!(out_pages[0], 100);
39
40        // 2. Exact match of all 32 tokens -> OSRP rule withholds 1 token (reusable = 31)
41        let mut full_query = Vec::new();
42        full_query.extend_from_slice(&p1_tokens);
43        full_query.extend_from_slice(&p2_tokens);
44
45        let (matched_full, reusable_full, pages_full) = index
46            .match_longest_prefix(&full_query, 3, &mut out_pages)
47            .unwrap();
48        assert_eq!(matched_full, 32);
49        assert_eq!(reusable_full, 31); // Withheld for decode logits!
50        assert_eq!(pages_full, 2);
51        assert_eq!(out_pages[0], 100);
52        assert_eq!(out_pages[1], 200);
53    }
54
55    #[test]
56    fn test_radix_lru_leaf_eviction() {
57        let mut pool = BlockPool::new(8);
58        let p0 = pool.allocate().unwrap();
59        let p1 = pool.allocate().unwrap();
60
61        let mut index = RadixPrefixIndex::<8>::new();
62        let t1 = [1u32, 2, 3, 4];
63        let t2 = [5u32, 6, 7, 8];
64
65        let n1 = index.insert_child_page(None, &t1, p0, 10).unwrap();
66        index.insert_child_page(Some(n1), &t2, p1, 5).unwrap();
67
68        assert_eq!(index.node_count(), 2);
69        // Leaf (p1, epoch 5) is evicted first
70        let evicted = index.evict_lru_leaf(&mut pool).unwrap();
71        assert_eq!(evicted, Some(p1));
72        assert_eq!(index.node_count(), 1);
73
74        // Now n1 (p0, epoch 10) is a leaf and can be evicted
75        let evicted2 = index.evict_lru_leaf(&mut pool).unwrap();
76        assert_eq!(evicted2, Some(p0));
77        assert_eq!(index.node_count(), 0);
78    }
79
80    #[test]
81    fn test_repoint_page_references() {
82        let mut pool = BlockPool::new(8);
83        let p_dup = pool.allocate().unwrap();
84        let p_canon = pool.allocate().unwrap();
85
86        let mut t1 = SequenceBlockTable::new(4);
87        let mut t2 = SequenceBlockTable::new(4);
88        t1.install_shared_prefix(&[p_dup], &mut pool).unwrap();
89        t2.install_shared_prefix(&[p_dup], &mut pool).unwrap();
90
91        let mut slice = [&mut t1, &mut t2];
92        let repointed =
93            RadixPrefixIndex::<8>::repoint_page_references(&mut slice, p_dup, p_canon, &mut pool)
94                .unwrap();
95
96        assert_eq!(repointed, 2);
97        assert_eq!(t1.get(0), Some(p_canon));
98        assert_eq!(t2.get(0), Some(p_canon));
99    }
100}