qualia_core_db/net/qdnf/resolve/qsr/
traversal.rs1use super::cover::{covers_digit, validate_cover, CoverInterval};
7use super::key::{digit, keys_equal};
8use super::outcome::QsrOutcome;
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::{Generation, StrongDigest};
11
12pub const SNAPSHOT_CAP: usize = 32;
14
15#[repr(C)]
17#[derive(Clone, Copy, Debug)]
18pub struct QsrSnapshot {
19 keys: [StrongDigest; SNAPSHOT_CAP],
20 values: [StrongDigest; SNAPSHOT_CAP],
21 len: u8,
22 generation: Generation,
23}
24
25impl QsrSnapshot {
26 pub const fn empty(generation: Generation) -> Self {
28 Self {
29 keys: [StrongDigest::ZERO; SNAPSHOT_CAP],
30 values: [StrongDigest::ZERO; SNAPSHOT_CAP],
31 len: 0,
32 generation,
33 }
34 }
35
36 #[inline]
37 pub const fn len(&self) -> usize {
39 self.len as usize
40 }
41
42 #[inline]
43 pub const fn generation(&self) -> Generation {
45 self.generation
46 }
47
48 pub fn insert(&mut self, key: StrongDigest, value: StrongDigest) -> Result<(), QdnfError> {
50 if self.len as usize >= SNAPSHOT_CAP {
51 return Err(QdnfError::Capacity);
52 }
53 let i = self.len as usize;
54 self.keys[i] = key;
55 self.values[i] = value;
56 self.len = self.len + 1;
57 Ok(())
58 }
59
60 #[inline]
62 pub fn pair_at(&self, i: usize) -> Option<(StrongDigest, StrongDigest)> {
63 if i >= self.len as usize {
64 return None;
65 }
66 Some((self.keys[i], self.values[i]))
67 }
68}
69
70pub fn lookup_into(
72 snapshot: &QsrSnapshot,
73 key: &StrongDigest,
74 covers: &[CoverInterval],
75 required_generation: Generation,
76 out: &mut [StrongDigest],
77) -> Result<QsrOutcome, QdnfError> {
78 validate_cover(covers)?;
79 if required_generation != snapshot.generation && required_generation != Generation(0) {
80 return Ok(QsrOutcome::Stale);
81 }
82 let d0 = digit(key, 0)?;
83 if !covers_digit(covers, d0) {
84 return Ok(QsrOutcome::Incomplete);
85 }
86
87 let occupied = snapshot.len as usize;
88 let mut match_i = usize::MAX;
89 let mut match_n: u8 = 0;
90 let mut conflict = false;
91 let mut i = 0usize;
92 while i < occupied {
93 if keys_equal(&snapshot.keys[i], key) {
94 if match_n == 0 {
95 match_i = i;
96 match_n = 1;
97 } else if !keys_equal(&snapshot.values[i], &snapshot.values[match_i]) {
98 conflict = true;
99 } else if match_n < 64 {
100 match_n = match_n + 1;
101 }
102 }
103 i += 1;
104 }
105
106 if conflict {
107 return Ok(QsrOutcome::Conflict);
108 }
109 if match_n == 0 {
110 return Ok(QsrOutcome::EmptyInSnapshot);
111 }
112 if out.is_empty() {
113 return Ok(QsrOutcome::NeedContinuation);
114 }
115 out[0] = snapshot.values[match_i];
116 Ok(QsrOutcome::Found { count: 1 })
117}
118
119pub fn lookup(
121 snapshot: &QsrSnapshot,
122 key: &StrongDigest,
123 covers: &[CoverInterval],
124 required_generation: Generation,
125) -> Result<QsrOutcome, QdnfError> {
126 let mut slot = [StrongDigest::ZERO; 1];
127 lookup_into(snapshot, key, covers, required_generation, &mut slot)
128}
129
130#[cfg(test)]
131mod tests {
132 use super::*;
133 use crate::net::qdnf::resolve::qsr::key::KEY_DEPTH;
134
135 fn key_same_first_byte(rest: u8) -> StrongDigest {
136 let mut k = StrongDigest::ZERO;
137 k.0[0] = 0x10;
138 let mut i = 1usize;
139 while i < 48 {
140 k.0[i] = rest;
141 i += 1;
142 }
143 k
144 }
145
146 fn full_cover() -> [CoverInterval; 1] {
147 [CoverInterval { start: 0, end: 15 }]
148 }
149
150 #[test]
151 fn shared_first_byte_is_distinguished_by_full_key() {
152 let a = key_same_first_byte(0x01);
153 let b = key_same_first_byte(0x02);
154 assert_eq!(a.0[0], b.0[0]);
155 assert_eq!(a.0[0] % KEY_DEPTH as u8, b.0[0] % KEY_DEPTH as u8);
156
157 let mut snap = QsrSnapshot::empty(Generation(1));
158 snap.insert(a, StrongDigest::ZERO).unwrap();
159 let covers = full_cover();
160
161 assert_eq!(
162 lookup(&snap, &a, &covers, Generation(1)),
163 Ok(QsrOutcome::Found { count: 1 })
164 );
165 assert_eq!(
166 lookup(&snap, &b, &covers, Generation(1)),
167 Ok(QsrOutcome::EmptyInSnapshot)
168 );
169 }
170
171 #[test]
172 fn first_byte_modulo_must_not_succeed() {
173 let a = key_same_first_byte(0xaa);
174 let b = key_same_first_byte(0xbb);
175 assert_eq!(a.0[0] % 96, b.0[0] % 96);
176
177 let mut snap = QsrSnapshot::empty(Generation(1));
178 snap.insert(a, StrongDigest::ZERO).unwrap();
179 let covers = full_cover();
180
181 assert_eq!(
182 lookup(&snap, &b, &covers, Generation(0)),
183 Ok(QsrOutcome::EmptyInSnapshot)
184 );
185 assert_ne!(
186 lookup(&snap, &b, &covers, Generation(0)),
187 Ok(QsrOutcome::Found { count: 1 })
188 );
189 }
190
191 #[test]
192 fn stale_generation_is_stale() {
193 let mut snap = QsrSnapshot::empty(Generation(2));
194 snap.insert(StrongDigest::ZERO, StrongDigest::ZERO).unwrap();
195 let covers = full_cover();
196 assert_eq!(
197 lookup(&snap, &StrongDigest::ZERO, &covers, Generation(1)),
198 Ok(QsrOutcome::Stale)
199 );
200 assert_eq!(
201 lookup(&snap, &StrongDigest::ZERO, &covers, Generation(0)),
202 Ok(QsrOutcome::Found { count: 1 })
203 );
204 }
205
206 #[test]
207 fn empty_snapshot_full_cover_is_empty_in_snapshot() {
208 let snap = QsrSnapshot::empty(Generation(1));
209 let covers = full_cover();
210 assert_eq!(
211 lookup(&snap, &StrongDigest::ZERO, &covers, Generation(1)),
212 Ok(QsrOutcome::EmptyInSnapshot)
213 );
214 assert_ne!(
215 lookup(&snap, &StrongDigest::ZERO, &covers, Generation(1)),
216 Ok(QsrOutcome::Found { count: 1 })
217 );
218 }
219
220 #[test]
221 fn overlapping_cover_is_rejected_before_lookup() {
222 let snap = QsrSnapshot::empty(Generation(0));
223 let covers = [
224 CoverInterval { start: 0, end: 10 },
225 CoverInterval { start: 8, end: 12 },
226 ];
227 assert_eq!(
228 lookup(&snap, &StrongDigest::ZERO, &covers, Generation(0)),
229 Err(QdnfError::Overlap)
230 );
231 }
232
233 #[test]
234 fn lookup_copies_target_into_caller_buffer() {
235 let mut key = StrongDigest::ZERO;
236 key.0[0] = 0x20;
237 let mut target = StrongDigest::ZERO;
238 target.0[47] = 0x77;
239 let mut snap = QsrSnapshot::empty(Generation(3));
240 snap.insert(key, target).unwrap();
241 let covers = full_cover();
242 let mut out = [StrongDigest::ZERO; 1];
243 assert_eq!(
244 lookup_into(&snap, &key, &covers, Generation(3), &mut out),
245 Ok(QsrOutcome::Found { count: 1 })
246 );
247 assert!(keys_equal(&out[0], &target));
248 }
249
250 #[test]
251 fn duplicate_key_conflicting_values_are_conflict() {
252 let key = StrongDigest::ZERO;
253 let mut v1 = StrongDigest::ZERO;
254 let mut v2 = StrongDigest::ZERO;
255 v1.0[0] = 1;
256 v2.0[0] = 2;
257 let mut snap = QsrSnapshot::empty(Generation(1));
258 snap.insert(key, v1).unwrap();
259 snap.insert(key, v2).unwrap();
260 assert_eq!(
261 lookup(&snap, &key, &full_cover(), Generation(1)),
262 Ok(QsrOutcome::Conflict)
263 );
264 }
265}