qualia_core_db/net/qdnf/resolve/qsr/
hot.rs1use crate::net::qdnf::errors::QdnfError;
9use crate::net::qdnf::types::StrongDigest;
10
11pub const MAX_HOT_REPLICAS: u8 = 3;
13pub const PARENT_CAP: u8 = 8;
15const NO_PARENT: u8 = 0xff;
16
17#[repr(C)]
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub struct Partition {
21 pub part: u8,
22 pub of: u8,
23}
24
25#[repr(C)]
27#[derive(Clone, Copy, Debug)]
28pub struct ParentTable {
29 parent: [u8; 8],
30}
31
32impl ParentTable {
33 pub const fn new() -> Self {
35 Self {
36 parent: [NO_PARENT; 8],
37 }
38 }
39
40 #[inline]
41 pub const fn parent_of(&self, node: u8) -> Option<u8> {
43 if node >= PARENT_CAP {
44 return None;
45 }
46 let p = self.parent[node as usize];
47 if p == NO_PARENT {
48 None
49 } else {
50 Some(p)
51 }
52 }
53}
54
55pub fn coalesce_hot(key: &StrongDigest, replicas: u8) -> Result<u8, QdnfError> {
59 if replicas < 1 || replicas > MAX_HOT_REPLICAS {
60 return Err(QdnfError::Range);
61 }
62 let slot = mix_key(key) % (replicas as u32);
63 Ok(slot as u8 + 1)
64}
65
66pub fn partition_record(key: &StrongDigest, parts: u8) -> Result<Partition, QdnfError> {
68 if parts == 0 {
69 return Err(QdnfError::Range);
70 }
71 let part = (mix_key(key) % (parts as u32)) as u8;
72 Ok(Partition { part, of: parts })
73}
74
75fn mix_key(key: &StrongDigest) -> u32 {
76 let mut acc = 2166136261u32;
77 let mut i = 0usize;
78 while i < 48 {
79 acc = acc.wrapping_mul(16777619).wrapping_add(key.0[i] as u32);
80 i += 1;
81 }
82 acc
83}
84
85pub fn insert_parent(table: &mut ParentTable, child: u8, parent: u8) -> Result<(), QdnfError> {
87 if child >= PARENT_CAP || parent >= PARENT_CAP {
88 return Err(QdnfError::Range);
89 }
90 if child == parent {
91 return Err(QdnfError::Conflict);
92 }
93 let mut cur = parent;
94 let mut steps = 0u8;
95 while steps < PARENT_CAP {
96 if cur == child {
97 return Err(QdnfError::Conflict);
98 }
99 let next = table.parent[cur as usize];
100 if next == NO_PARENT {
101 break;
102 }
103 cur = next;
104 steps = steps + 1;
105 }
106 table.parent[child as usize] = parent;
107 Ok(())
108}
109
110#[cfg(test)]
111mod tests {
112 use super::*;
113
114 fn key_tail(b47: u8) -> StrongDigest {
115 let mut k = StrongDigest::ZERO;
116 k.0[0] = 0xab;
117 k.0[47] = b47;
118 k
119 }
120
121 #[test]
122 fn coalesce_rejects_zero_and_more_than_three() {
123 let k = StrongDigest::ZERO;
124 assert_eq!(coalesce_hot(&k, 0), Err(QdnfError::Range));
125 assert_eq!(coalesce_hot(&k, 4), Err(QdnfError::Range));
126 let r = coalesce_hot(&k, 3).unwrap();
127 assert!(r >= 1 && r <= 3);
128 }
129
130 #[test]
131 fn coalesce_is_stable_for_same_key() {
132 let k = key_tail(0x11);
133 assert_eq!(coalesce_hot(&k, 2).unwrap(), coalesce_hot(&k, 2).unwrap());
134 }
135
136 #[test]
137 fn partition_is_stable_for_same_key() {
138 let k = key_tail(0x22);
139 let a = partition_record(&k, 7).unwrap();
140 let b = partition_record(&k, 7).unwrap();
141 assert_eq!(a, b);
142 assert_eq!(a.of, 7);
143 assert!(a.part < 7);
144 }
145
146 #[test]
147 fn partition_uses_later_bytes() {
148 let a = key_tail(0x01);
149 let b = key_tail(0x02);
150 assert_eq!(a.0[0], b.0[0]);
151 let pa = partition_record(&a, 16).unwrap();
152 let pb = partition_record(&b, 16).unwrap();
153 assert_eq!(pa.of, pb.of);
154 assert_ne!(pa.part, pb.part);
155 }
156
157 #[test]
158 fn partition_zero_parts_is_range() {
159 assert_eq!(
160 partition_record(&StrongDigest::ZERO, 0),
161 Err(QdnfError::Range)
162 );
163 }
164
165 #[test]
166 fn parent_cycle_is_conflict() {
167 let mut t = ParentTable::new();
168 insert_parent(&mut t, 1, 0).unwrap();
169 insert_parent(&mut t, 2, 1).unwrap();
170 assert_eq!(insert_parent(&mut t, 0, 2), Err(QdnfError::Conflict));
171 assert_eq!(insert_parent(&mut t, 3, 3), Err(QdnfError::Conflict));
172 assert_eq!(t.parent_of(1), Some(0));
173 assert_eq!(t.parent_of(0), None);
174 }
175
176 #[test]
177 fn parent_out_of_table_is_range() {
178 let mut t = ParentTable::new();
179 assert_eq!(insert_parent(&mut t, 8, 0), Err(QdnfError::Range));
180 assert_eq!(insert_parent(&mut t, 0, 8), Err(QdnfError::Range));
181 }
182
183 #[test]
184 fn acyclic_chain_is_ok() {
185 let mut t = ParentTable::new();
186 insert_parent(&mut t, 2, 1).unwrap();
187 insert_parent(&mut t, 1, 0).unwrap();
188 assert_eq!(t.parent_of(2), Some(1));
189 assert_eq!(t.parent_of(1), Some(0));
190 }
191}