qualia_core_db/inference/runtime/kv/prefix/
radix.rs1pub 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 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 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 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 assert_eq!(matched, 16);
36 assert_eq!(reusable, 16);
37 assert_eq!(pages, 1);
38 assert_eq!(out_pages[0], 100);
39
40 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); 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 let evicted = index.evict_lru_leaf(&mut pool).unwrap();
71 assert_eq!(evicted, Some(p1));
72 assert_eq!(index.node_count(), 1);
73
74 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}