Line data Source code
1 : use std::collections::BTreeMap;
2 : use std::collections::HashSet;
3 : use std::fmt::Debug;
4 : use std::mem::MaybeUninit;
5 :
6 : use crate::hash::Entry;
7 : use crate::hash::HashMapAccess;
8 : use crate::hash::HashMapInit;
9 : use crate::hash::core::FullError;
10 :
11 : use rand::seq::SliceRandom;
12 : use rand::{Rng, RngCore};
13 : use rand_distr::Zipf;
14 :
15 : const TEST_KEY_LEN: usize = 16;
16 :
17 : #[derive(Clone, Copy, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
18 : struct TestKey([u8; TEST_KEY_LEN]);
19 :
20 : impl From<&TestKey> for u128 {
21 0 : fn from(val: &TestKey) -> u128 {
22 0 : u128::from_be_bytes(val.0)
23 0 : }
24 : }
25 :
26 : impl From<u128> for TestKey {
27 390023 : fn from(val: u128) -> TestKey {
28 390023 : TestKey(val.to_be_bytes())
29 390023 : }
30 : }
31 :
32 : impl<'a> From<&'a [u8]> for TestKey {
33 0 : fn from(bytes: &'a [u8]) -> TestKey {
34 0 : TestKey(bytes.try_into().unwrap())
35 0 : }
36 : }
37 :
38 12 : fn test_inserts<K: Into<TestKey> + Copy>(keys: &[K]) {
39 12 : let w = HashMapInit::<TestKey, usize>::new_resizeable_named(100000, 120000, "test_inserts")
40 12 : .attach_writer();
41 :
42 110005 : for (idx, k) in keys.iter().enumerate() {
43 110005 : let res = w.entry((*k).into());
44 110005 : match res {
45 0 : Entry::Occupied(mut e) => {
46 0 : e.insert(idx);
47 0 : }
48 110005 : Entry::Vacant(e) => {
49 110005 : let res = e.insert(idx);
50 110005 : assert!(res.is_ok());
51 : }
52 : };
53 : }
54 :
55 110005 : for (idx, k) in keys.iter().enumerate() {
56 110005 : let x = w.get(&(*k).into());
57 110005 : let value = x.as_deref().copied();
58 110005 : assert_eq!(value, Some(idx));
59 : }
60 12 : }
61 :
62 : #[test]
63 1 : fn dense() {
64 : // This exercises splitting a node with prefix
65 1 : let keys: &[u128] = &[0, 1, 2, 3, 256];
66 1 : test_inserts(keys);
67 :
68 : // Dense keys
69 1 : let mut keys: Vec<u128> = (0..10000).collect();
70 1 : test_inserts(&keys);
71 :
72 : // Do the same in random orders
73 10 : for _ in 1..10 {
74 9 : keys.shuffle(&mut rand::rng());
75 9 : test_inserts(&keys);
76 9 : }
77 1 : }
78 :
79 : #[test]
80 1 : fn sparse() {
81 : // sparse keys
82 1 : let mut keys: Vec<TestKey> = Vec::new();
83 1 : let mut used_keys = HashSet::new();
84 10001 : for _ in 0..10000 {
85 : loop {
86 10000 : let key = rand::random::<u128>();
87 10000 : if used_keys.contains(&key) {
88 0 : continue;
89 10000 : }
90 10000 : used_keys.insert(key);
91 10000 : keys.push(key.into());
92 10000 : break;
93 : }
94 : }
95 1 : test_inserts(&keys);
96 1 : }
97 :
98 : #[derive(Clone, Debug)]
99 : struct TestOp(TestKey, Option<usize>);
100 :
101 179350 : fn apply_op(
102 179350 : op: &TestOp,
103 179350 : map: &mut HashMapAccess<TestKey, usize>,
104 179350 : shadow: &mut BTreeMap<TestKey, usize>,
105 179350 : ) {
106 : // apply the change to the shadow tree first
107 179350 : let shadow_existing = if let Some(v) = op.1 {
108 126384 : shadow.insert(op.0, v)
109 : } else {
110 52966 : shadow.remove(&op.0)
111 : };
112 :
113 179350 : let entry = map.entry(op.0);
114 179350 : let hash_existing = match op.1 {
115 126384 : Some(new) => match entry {
116 64716 : Entry::Occupied(mut e) => Some(e.insert(new)),
117 61668 : Entry::Vacant(e) => {
118 61668 : _ = e.insert(new).unwrap();
119 61668 : None
120 : }
121 : },
122 52966 : None => match entry {
123 22708 : Entry::Occupied(e) => Some(e.remove()),
124 30258 : Entry::Vacant(_) => None,
125 : },
126 : };
127 :
128 179350 : assert_eq!(shadow_existing, hash_existing);
129 179350 : }
130 :
131 15 : fn do_random_ops(
132 15 : num_ops: usize,
133 15 : size: u32,
134 15 : del_prob: f64,
135 15 : writer: &mut HashMapAccess<TestKey, usize>,
136 15 : shadow: &mut BTreeMap<TestKey, usize>,
137 15 : rng: &mut rand::rngs::ThreadRng,
138 15 : ) {
139 79350 : for i in 0..num_ops {
140 79350 : let key: TestKey = ((rng.next_u32() % size) as u128).into();
141 79350 : let op = TestOp(
142 79350 : key,
143 79350 : if rng.random_bool(del_prob) {
144 51627 : Some(i)
145 : } else {
146 27723 : None
147 : },
148 : );
149 79350 : apply_op(&op, writer, shadow);
150 : }
151 15 : }
152 :
153 46 : fn do_deletes(
154 46 : num_ops: usize,
155 46 : writer: &mut HashMapAccess<TestKey, usize>,
156 46 : shadow: &mut BTreeMap<TestKey, usize>,
157 46 : ) {
158 545 : for _ in 0..num_ops {
159 545 : let (k, _) = shadow.pop_first().unwrap();
160 545 : writer.remove(&k);
161 545 : }
162 46 : }
163 :
164 3 : fn do_shrink(
165 3 : writer: &mut HashMapAccess<TestKey, usize>,
166 3 : shadow: &mut BTreeMap<TestKey, usize>,
167 3 : from: u32,
168 3 : to: u32,
169 3 : ) {
170 3 : assert!(writer.shrink_goal().is_none());
171 3 : writer.begin_shrink(to);
172 3 : assert_eq!(writer.shrink_goal(), Some(to as usize));
173 2050 : for i in to..from {
174 2050 : if let Some(entry) = writer.entry_at_bucket(i as usize) {
175 225 : shadow.remove(&entry._key);
176 225 : entry.remove();
177 1825 : }
178 : }
179 3 : let old_usage = writer.get_num_buckets_in_use();
180 3 : writer.finish_shrink().unwrap();
181 3 : assert!(writer.shrink_goal().is_none());
182 3 : assert_eq!(writer.get_num_buckets_in_use(), old_usage);
183 3 : }
184 :
185 : #[test]
186 1 : fn random_ops() {
187 1 : let mut writer =
188 1 : HashMapInit::<TestKey, usize>::new_resizeable_named(100000, 120000, "test_random")
189 1 : .attach_writer();
190 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
191 :
192 1 : let distribution = Zipf::new(u128::MAX as f64, 1.1).unwrap();
193 1 : let mut rng = rand::rng();
194 100001 : for i in 0..100000 {
195 100000 : let key: TestKey = (rng.sample(distribution) as u128).into();
196 :
197 100000 : let op = TestOp(key, if rng.random_bool(0.75) { Some(i) } else { None });
198 :
199 100000 : apply_op(&op, &mut writer, &mut shadow);
200 : }
201 1 : }
202 :
203 : #[test]
204 1 : fn test_shuffle() {
205 1 : let mut writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1000, 1200, "test_shuf")
206 1 : .attach_writer();
207 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
208 1 : let mut rng = rand::rng();
209 :
210 1 : do_random_ops(10000, 1000, 0.75, &mut writer, &mut shadow, &mut rng);
211 1 : writer.shuffle();
212 1 : do_random_ops(10000, 1000, 0.75, &mut writer, &mut shadow, &mut rng);
213 1 : }
214 :
215 : #[test]
216 1 : fn test_grow() {
217 1 : let mut writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1000, 2000, "test_grow")
218 1 : .attach_writer();
219 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
220 1 : let mut rng = rand::rng();
221 :
222 1 : do_random_ops(10000, 1000, 0.75, &mut writer, &mut shadow, &mut rng);
223 1 : let old_usage = writer.get_num_buckets_in_use();
224 1 : writer.grow(1500).unwrap();
225 1 : assert_eq!(writer.get_num_buckets_in_use(), old_usage);
226 1 : assert_eq!(writer.get_num_buckets(), 1500);
227 1 : do_random_ops(10000, 1500, 0.75, &mut writer, &mut shadow, &mut rng);
228 1 : }
229 :
230 : #[test]
231 1 : fn test_clear() {
232 1 : let mut writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2000, "test_clear")
233 1 : .attach_writer();
234 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
235 1 : let mut rng = rand::rng();
236 1 : do_random_ops(2000, 1500, 0.75, &mut writer, &mut shadow, &mut rng);
237 1 : writer.clear();
238 1 : assert_eq!(writer.get_num_buckets_in_use(), 0);
239 1 : assert_eq!(writer.get_num_buckets(), 1500);
240 809 : while let Some((key, _)) = shadow.pop_first() {
241 808 : assert!(writer.get(&key).is_none());
242 : }
243 1 : do_random_ops(2000, 1500, 0.75, &mut writer, &mut shadow, &mut rng);
244 650 : for i in 0..(1500 - writer.get_num_buckets_in_use()) {
245 650 : writer.insert((1500 + i as u128).into(), 0).unwrap();
246 650 : }
247 1 : assert_eq!(writer.insert(5000.into(), 0), Err(FullError {}));
248 1 : writer.clear();
249 1 : assert!(writer.insert(5000.into(), 0).is_ok());
250 1 : }
251 :
252 : #[test]
253 1 : fn test_idx_remove() {
254 1 : let mut writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2000, "test_clear")
255 1 : .attach_writer();
256 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
257 1 : let mut rng = rand::rng();
258 1 : do_random_ops(2000, 1500, 0.25, &mut writer, &mut shadow, &mut rng);
259 101 : for _ in 0..100 {
260 100 : let idx = (rng.next_u32() % 1500) as usize;
261 100 : if let Some(e) = writer.entry_at_bucket(idx) {
262 22 : shadow.remove(&e._key);
263 22 : e.remove();
264 78 : }
265 : }
266 273 : while let Some((key, val)) = shadow.pop_first() {
267 272 : assert_eq!(*writer.get(&key).unwrap(), val);
268 : }
269 1 : }
270 :
271 : #[test]
272 1 : fn test_idx_get() {
273 1 : let mut writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2000, "test_clear")
274 1 : .attach_writer();
275 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
276 1 : let mut rng = rand::rng();
277 1 : do_random_ops(2000, 1500, 0.25, &mut writer, &mut shadow, &mut rng);
278 101 : for _ in 0..100 {
279 100 : let idx = (rng.next_u32() % 1500) as usize;
280 100 : if let Some(pair) = writer.get_at_bucket(idx) {
281 : {
282 21 : let v: *const usize = &pair.1;
283 21 : assert_eq!(writer.get_bucket_for_value(v), idx);
284 : }
285 : {
286 21 : let v: *const usize = &pair.1;
287 21 : assert_eq!(writer.get_bucket_for_value(v), idx);
288 : }
289 79 : }
290 : }
291 1 : }
292 :
293 : #[test]
294 1 : fn test_shrink() {
295 1 : let mut writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2000, "test_shrink")
296 1 : .attach_writer();
297 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
298 1 : let mut rng = rand::rng();
299 :
300 1 : do_random_ops(10000, 1500, 0.75, &mut writer, &mut shadow, &mut rng);
301 1 : do_shrink(&mut writer, &mut shadow, 1500, 1000);
302 1 : assert_eq!(writer.get_num_buckets(), 1000);
303 1 : do_deletes(500, &mut writer, &mut shadow);
304 1 : do_random_ops(10000, 500, 0.75, &mut writer, &mut shadow, &mut rng);
305 1 : assert!(writer.get_num_buckets_in_use() <= 1000);
306 1 : }
307 :
308 : #[test]
309 1 : fn test_shrink_grow_seq() {
310 1 : let mut writer =
311 1 : HashMapInit::<TestKey, usize>::new_resizeable_named(1000, 20000, "test_grow_seq")
312 1 : .attach_writer();
313 1 : let mut shadow: std::collections::BTreeMap<TestKey, usize> = BTreeMap::new();
314 1 : let mut rng = rand::rng();
315 :
316 1 : do_random_ops(500, 1000, 0.1, &mut writer, &mut shadow, &mut rng);
317 1 : eprintln!("Shrinking to 750");
318 1 : do_shrink(&mut writer, &mut shadow, 1000, 750);
319 1 : do_random_ops(200, 1000, 0.5, &mut writer, &mut shadow, &mut rng);
320 1 : eprintln!("Growing to 1500");
321 1 : writer.grow(1500).unwrap();
322 1 : do_random_ops(600, 1500, 0.1, &mut writer, &mut shadow, &mut rng);
323 1 : eprintln!("Shrinking to 200");
324 46 : while shadow.len() > 100 {
325 45 : do_deletes(1, &mut writer, &mut shadow);
326 45 : }
327 1 : do_shrink(&mut writer, &mut shadow, 1500, 200);
328 1 : do_random_ops(50, 1500, 0.25, &mut writer, &mut shadow, &mut rng);
329 1 : eprintln!("Growing to 10k");
330 1 : writer.grow(10000).unwrap();
331 1 : do_random_ops(10000, 5000, 0.25, &mut writer, &mut shadow, &mut rng);
332 1 : }
333 :
334 : #[test]
335 1 : fn test_bucket_ops() {
336 1 : let writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1000, 1200, "test_bucket_ops")
337 1 : .attach_writer();
338 1 : match writer.entry(1.into()) {
339 0 : Entry::Occupied(mut e) => {
340 0 : e.insert(2);
341 0 : }
342 1 : Entry::Vacant(e) => {
343 1 : _ = e.insert(2).unwrap();
344 1 : }
345 : }
346 1 : assert_eq!(writer.get_num_buckets_in_use(), 1);
347 1 : assert_eq!(writer.get_num_buckets(), 1000);
348 1 : assert_eq!(*writer.get(&1.into()).unwrap(), 2);
349 1 : let pos = match writer.entry(1.into()) {
350 1 : Entry::Occupied(e) => {
351 1 : assert_eq!(e._key, 1.into());
352 1 : e.bucket_pos as usize
353 : }
354 : Entry::Vacant(_) => {
355 0 : panic!("Insert didn't affect entry");
356 : }
357 : };
358 1 : assert_eq!(writer.entry_at_bucket(pos).unwrap()._key, 1.into());
359 1 : assert_eq!(*writer.get_at_bucket(pos).unwrap(), (1.into(), 2));
360 : {
361 1 : let ptr: *const usize = &*writer.get(&1.into()).unwrap();
362 1 : assert_eq!(writer.get_bucket_for_value(ptr), pos);
363 : }
364 1 : writer.remove(&1.into());
365 1 : assert!(writer.get(&1.into()).is_none());
366 1 : }
367 :
368 : #[test]
369 1 : fn test_shrink_zero() {
370 1 : let mut writer =
371 1 : HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2000, "test_shrink_zero")
372 1 : .attach_writer();
373 1 : writer.begin_shrink(0);
374 1501 : for i in 0..1500 {
375 1500 : writer.entry_at_bucket(i).map(|x| x.remove());
376 : }
377 1 : writer.finish_shrink().unwrap();
378 1 : assert_eq!(writer.get_num_buckets_in_use(), 0);
379 1 : let entry = writer.entry(1.into());
380 1 : if let Entry::Vacant(v) = entry {
381 1 : assert!(v.insert(2).is_err());
382 : } else {
383 0 : panic!("Somehow got non-vacant entry in empty map.")
384 : }
385 1 : writer.grow(50).unwrap();
386 1 : let entry = writer.entry(1.into());
387 1 : if let Entry::Vacant(v) = entry {
388 1 : assert!(v.insert(2).is_ok());
389 : } else {
390 0 : panic!("Somehow got non-vacant entry in empty map.")
391 : }
392 1 : assert_eq!(writer.get_num_buckets_in_use(), 1);
393 1 : }
394 :
395 : #[test]
396 : #[should_panic]
397 1 : fn test_grow_oom() {
398 1 : let writer = HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2000, "test_grow_oom")
399 1 : .attach_writer();
400 1 : writer.grow(20000).unwrap();
401 1 : }
402 :
403 : #[test]
404 : #[should_panic]
405 1 : fn test_shrink_bigger() {
406 1 : let mut writer =
407 1 : HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2500, "test_shrink_bigger")
408 1 : .attach_writer();
409 1 : writer.begin_shrink(2000);
410 1 : }
411 :
412 : #[test]
413 : #[should_panic]
414 1 : fn test_shrink_early_finish() {
415 1 : let writer =
416 1 : HashMapInit::<TestKey, usize>::new_resizeable_named(1500, 2500, "test_shrink_early_finish")
417 1 : .attach_writer();
418 1 : writer.finish_shrink().unwrap();
419 1 : }
420 :
421 : #[test]
422 : #[should_panic]
423 1 : fn test_shrink_fixed_size() {
424 1 : let mut area = [MaybeUninit::uninit(); 10000];
425 1 : let init_struct = HashMapInit::<TestKey, usize>::with_fixed(3, &mut area);
426 1 : let mut writer = init_struct.attach_writer();
427 1 : writer.begin_shrink(1);
428 1 : }
|
