Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/tests/iblt.rs

6.7 KiB, 3 runs

created by r1870400018:11218, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Integration tests for the IBLT primitive.
2
3use oxedyne_fe2o3_core::prelude::*;
4
5use oxedyne_fe2o3_data::iblt::{
6 DecodeOutcome,
7 Iblt,
8 IbltConfig,
9};
10
11use std::collections::BTreeSet;
12
13
14fn key_only_cfg(num_cells: usize, num_hashes: usize) -> IbltConfig {
15 IbltConfig {
16 num_cells,
17 num_hashes,
18 key_len: 8,
19 value_len: 0,
20 seed: 0x0123_4567_89ab_cdef,
21 }
22}
23
24fn key_bytes(x: u64) -> Vec<u8> {
25 x.to_le_bytes().to_vec()
26}
27
28
29#[test]
30fn rejects_zero_cells() -> Outcome<()> {
31 let cfg = IbltConfig {
32 num_cells: 0, num_hashes: 3, key_len: 8, value_len: 0, seed: 0,
33 };
34 assert!(Iblt::new(cfg).is_err());
35 Ok(())
36}
37
38#[test]
39fn rejects_zero_hashes() -> Outcome<()> {
40 let cfg = IbltConfig {
41 num_cells: 10, num_hashes: 0, key_len: 8, value_len: 0, seed: 0,
42 };
43 assert!(Iblt::new(cfg).is_err());
44 Ok(())
45}
46
47#[test]
48fn rejects_zero_key_len() -> Outcome<()> {
49 let cfg = IbltConfig {
50 num_cells: 10, num_hashes: 3, key_len: 0, value_len: 0, seed: 0,
51 };
52 assert!(Iblt::new(cfg).is_err());
53 Ok(())
54}
55
56#[test]
57fn rejects_num_hashes_above_num_cells() -> Outcome<()> {
58 let cfg = IbltConfig {
59 num_cells: 3, num_hashes: 4, key_len: 8, value_len: 0, seed: 0,
60 };
61 assert!(Iblt::new(cfg).is_err());
62 Ok(())
63}
64
65#[test]
66fn insert_length_mismatch_errors() -> Outcome<()> {
67 let cfg = key_only_cfg(32, 3);
68 let mut iblt = res!(Iblt::new(cfg));
69 assert!(iblt.insert(&[0u8; 4], &[]).is_err());
70 assert!(iblt.insert(&[0u8; 8], &[0u8; 1]).is_err());
71 Ok(())
72}
73
74#[test]
75fn empty_iblt_decodes_empty() -> Outcome<()> {
76 let cfg = key_only_cfg(32, 3);
77 let mut iblt = res!(Iblt::new(cfg));
78 match res!(iblt.decode()) {
79 DecodeOutcome::Complete { inserted, deleted } => {
80 assert!(inserted.is_empty());
81 assert!(deleted.is_empty());
82 },
83 other => panic!("expected Complete, got {:?}", other),
84 }
85 Ok(())
86}
87
88#[test]
89fn insert_then_delete_restores_empty() -> Outcome<()> {
90 let cfg = key_only_cfg(32, 3);
91 let mut iblt = res!(Iblt::new(cfg));
92 let k = key_bytes(42);
93 res!(iblt.insert(&k, &[]));
94 res!(iblt.delete(&k, &[]));
95 assert!(iblt.is_empty());
96 Ok(())
97}
98
99#[test]
100fn self_subtract_zeroes_out() -> Outcome<()> {
101 let cfg = key_only_cfg(64, 3);
102 let mut a = res!(Iblt::new(cfg));
103 for i in 1u64..=10 {
104 res!(a.insert(&key_bytes(i), &[]));
105 }
106 let b = a.clone();
107 res!(a.subtract(&b));
108 assert!(a.is_empty());
109 Ok(())
110}
111
112#[test]
113fn symmetric_difference_recovers_cleanly() -> Outcome<()> {
114 // Sizing: 19-key symmetric difference, k=3, so ~1.5 × 19 ≈ 29 cells
115 // suffice. 80 gives ample headroom to avoid flaky tests.
116 let cfg = key_only_cfg(80, 3);
117 let mut a = res!(Iblt::new(cfg));
118 let mut b = res!(Iblt::new(cfg));
119
120 let a_set: BTreeSet<u64> = (1u64..20).collect();
121 let b_set: BTreeSet<u64> = (10u64..30).collect();
122 for &x in &a_set {
123 res!(a.insert(&key_bytes(x), &[]));
124 }
125 for &x in &b_set {
126 res!(b.insert(&key_bytes(x), &[]));
127 }
128
129 res!(a.subtract(&b));
130 let outcome = res!(a.decode());
131 let (inserted, deleted) = match outcome {
132 DecodeOutcome::Complete { inserted, deleted } => (inserted, deleted),
133 other => panic!("expected Complete, got {:?}", other),
134 };
135
136 let recovered_inserted: BTreeSet<u64> = inserted.iter()
137 .map(|(k, _)| {
138 let mut buf = [0u8; 8];
139 buf.copy_from_slice(k);
140 u64::from_le_bytes(buf)
141 })
142 .collect();
143 let recovered_deleted: BTreeSet<u64> = deleted.iter()
144 .map(|(k, _)| {
145 let mut buf = [0u8; 8];
146 buf.copy_from_slice(k);
147 u64::from_le_bytes(buf)
148 })
149 .collect();
150
151 let expected_a_only: BTreeSet<u64> = a_set.difference(&b_set).copied().collect();
152 let expected_b_only: BTreeSet<u64> = b_set.difference(&a_set).copied().collect();
153 assert_eq!(recovered_inserted, expected_a_only);
154 assert_eq!(recovered_deleted, expected_b_only);
155 Ok(())
156}
157
158#[test]
159fn overload_returns_incomplete() -> Outcome<()> {
160 // Difference of 50 keys against 20 cells is far above the peeling
161 // threshold, so decoding must report Incomplete.
162 let cfg = key_only_cfg(20, 3);
163 let mut a = res!(Iblt::new(cfg));
164 for i in 0u64..50 {
165 res!(a.insert(&key_bytes(i), &[]));
166 }
167 let outcome = res!(a.decode());
168 match outcome {
169 DecodeOutcome::Incomplete { remaining_cells, .. } => {
170 assert!(remaining_cells > 0);
171 },
172 DecodeOutcome::Complete { .. } => {
173 panic!("expected Incomplete outcome on overloaded IBLT");
174 },
175 }
176 Ok(())
177}
178
179#[test]
180fn value_carrying_iblt_recovers_values() -> Outcome<()> {
181 let cfg = IbltConfig {
182 num_cells: 60,
183 num_hashes: 3,
184 key_len: 4,
185 value_len: 4,
186 seed: 0xdeadbeef,
187 };
188 let mut a = res!(Iblt::new(cfg));
189 let pairs: Vec<(u32, u32)> = (1u32..=12).map(|i| (i, i * 100)).collect();
190 for (k, v) in &pairs {
191 res!(a.insert(&k.to_le_bytes(), &v.to_le_bytes()));
192 }
193 let b = res!(Iblt::new(cfg));
194 res!(a.subtract(&b));
195 let (inserted, deleted) = match res!(a.decode()) {
196 DecodeOutcome::Complete { inserted, deleted } => (inserted, deleted),
197 other => panic!("expected Complete, got {:?}", other),
198 };
199 assert!(deleted.is_empty());
200 assert_eq!(inserted.len(), pairs.len());
201 let recovered: BTreeSet<(u32, u32)> = inserted.iter()
202 .map(|(k, v)| {
203 let mut kb = [0u8; 4];
204 kb.copy_from_slice(k);
205 let mut vb = [0u8; 4];
206 vb.copy_from_slice(v);
207 (u32::from_le_bytes(kb), u32::from_le_bytes(vb))
208 })
209 .collect();
210 let expected: BTreeSet<(u32, u32)> = pairs.iter().copied().collect();
211 assert_eq!(recovered, expected);
212 Ok(())
213}
214
215#[test]
216fn serialisation_roundtrips() -> Outcome<()> {
217 let cfg = key_only_cfg(32, 3);
218 let mut a = res!(Iblt::new(cfg));
219 for i in 1u64..10 {
220 res!(a.insert(&key_bytes(i), &[]));
221 }
222 let bytes = a.to_bytes();
223 let mut parsed = res!(Iblt::from_bytes(&bytes));
224 assert_eq!(parsed.config(), cfg);
225 // Decoding the roundtripped IBLT should recover the same set.
226 let outcome = res!(parsed.decode());
227 match outcome {
228 DecodeOutcome::Complete { inserted, deleted } => {
229 assert!(deleted.is_empty());
230 assert_eq!(inserted.len(), 9);
231 let recovered: BTreeSet<u64> = inserted.iter()
232 .map(|(k, _)| {
233 let mut buf = [0u8; 8];
234 buf.copy_from_slice(k);
235 u64::from_le_bytes(buf)
236 })
237 .collect();
238 let expected: BTreeSet<u64> = (1u64..10).collect();
239 assert_eq!(recovered, expected);
240 },
241 other => panic!("expected Complete, got {:?}", other),
242 }
243 Ok(())
244}
245
246#[test]
247fn subtract_config_mismatch_errors() -> Outcome<()> {
248 let a = res!(Iblt::new(key_only_cfg(32, 3)));
249 let b = res!(Iblt::new(key_only_cfg(32, 4)));
250 let mut a = a;
251 assert!(a.subtract(&b).is_err());
252 Ok(())
253}
254
255#[test]
256fn decode_preserves_completeness_under_reorder() -> Outcome<()> {
257 // Inserting the same set in two different orders must produce bitwise
258 // identical IBLTs -- the structure is order-agnostic.
259 let cfg = key_only_cfg(48, 3);
260 let mut a = res!(Iblt::new(cfg));
261 let mut b = res!(Iblt::new(cfg));
262 for i in 1u64..=15 {
263 res!(a.insert(&key_bytes(i), &[]));
264 }
265 for i in (1u64..=15).rev() {
266 res!(b.insert(&key_bytes(i), &[]));
267 }
268 assert_eq!(a.to_bytes(), b.to_bytes());
269 Ok(())
270}