/__w/smoldot/smoldot/repo/lib/src/trie/trie_structure/tests.rs
Line | Count | Source (jump to first uncovered line) |
1 | | // Smoldot |
2 | | // Copyright (C) 2019-2022 Parity Technologies (UK) Ltd. |
3 | | // SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0 |
4 | | |
5 | | // This program is free software: you can redistribute it and/or modify |
6 | | // it under the terms of the GNU General Public License as published by |
7 | | // the Free Software Foundation, either version 3 of the License, or |
8 | | // (at your option) any later version. |
9 | | |
10 | | // This program is distributed in the hope that it will be useful, |
11 | | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | // GNU General Public License for more details. |
14 | | |
15 | | // You should have received a copy of the GNU General Public License |
16 | | // along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | | |
18 | | #![cfg(test)] |
19 | | |
20 | | use super::{Nibble, TrieStructure}; |
21 | | |
22 | | use alloc::collections::{BTreeMap, BTreeSet}; |
23 | | use core::ops; |
24 | | use rand::{ |
25 | | distributions::{Distribution as _, Uniform}, |
26 | | seq::SliceRandom as _, |
27 | | }; |
28 | | use std::collections::HashSet; |
29 | | |
30 | | #[test] |
31 | 1 | fn remove_turns_storage_into_branch() { |
32 | 1 | let with_removal = { |
33 | 1 | let mut trie = TrieStructure::new(); |
34 | 1 | |
35 | 1 | trie.node( |
36 | 1 | [ |
37 | 1 | Nibble::try_from(1).unwrap(), |
38 | 1 | Nibble::try_from(2).unwrap(), |
39 | 1 | Nibble::try_from(3).unwrap(), |
40 | 1 | ] |
41 | 1 | .iter() |
42 | 1 | .cloned(), |
43 | 1 | ) |
44 | 1 | .into_vacant() |
45 | 1 | .unwrap() |
46 | 1 | .insert_storage_value() |
47 | 1 | .insert((), ()); |
48 | 1 | |
49 | 1 | trie.node( |
50 | 1 | [ |
51 | 1 | Nibble::try_from(1).unwrap(), |
52 | 1 | Nibble::try_from(2).unwrap(), |
53 | 1 | Nibble::try_from(3).unwrap(), |
54 | 1 | Nibble::try_from(10).unwrap(), |
55 | 1 | Nibble::try_from(11).unwrap(), |
56 | 1 | ] |
57 | 1 | .iter() |
58 | 1 | .cloned(), |
59 | 1 | ) |
60 | 1 | .into_vacant() |
61 | 1 | .unwrap() |
62 | 1 | .insert_storage_value() |
63 | 1 | .insert((), ()); |
64 | 1 | |
65 | 1 | trie.node( |
66 | 1 | [ |
67 | 1 | Nibble::try_from(1).unwrap(), |
68 | 1 | Nibble::try_from(2).unwrap(), |
69 | 1 | Nibble::try_from(3).unwrap(), |
70 | 1 | Nibble::try_from(12).unwrap(), |
71 | 1 | Nibble::try_from(13).unwrap(), |
72 | 1 | ] |
73 | 1 | .iter() |
74 | 1 | .cloned(), |
75 | 1 | ) |
76 | 1 | .into_vacant() |
77 | 1 | .unwrap() |
78 | 1 | .insert_storage_value() |
79 | 1 | .insert((), ()); |
80 | 1 | |
81 | 1 | trie.node( |
82 | 1 | [ |
83 | 1 | Nibble::try_from(1).unwrap(), |
84 | 1 | Nibble::try_from(2).unwrap(), |
85 | 1 | Nibble::try_from(3).unwrap(), |
86 | 1 | ] |
87 | 1 | .iter() |
88 | 1 | .cloned(), |
89 | 1 | ) |
90 | 1 | .into_occupied() |
91 | 1 | .unwrap() |
92 | 1 | .into_storage() |
93 | 1 | .unwrap() |
94 | 1 | .remove(); |
95 | 1 | |
96 | 1 | trie |
97 | 1 | }; |
98 | 1 | |
99 | 1 | let expected = { |
100 | 1 | let mut trie = TrieStructure::new(); |
101 | 1 | |
102 | 1 | trie.node( |
103 | 1 | [ |
104 | 1 | Nibble::try_from(1).unwrap(), |
105 | 1 | Nibble::try_from(2).unwrap(), |
106 | 1 | Nibble::try_from(3).unwrap(), |
107 | 1 | Nibble::try_from(10).unwrap(), |
108 | 1 | Nibble::try_from(11).unwrap(), |
109 | 1 | ] |
110 | 1 | .iter() |
111 | 1 | .cloned(), |
112 | 1 | ) |
113 | 1 | .into_vacant() |
114 | 1 | .unwrap() |
115 | 1 | .insert_storage_value() |
116 | 1 | .insert((), ()); |
117 | 1 | |
118 | 1 | trie.node( |
119 | 1 | [ |
120 | 1 | Nibble::try_from(1).unwrap(), |
121 | 1 | Nibble::try_from(2).unwrap(), |
122 | 1 | Nibble::try_from(3).unwrap(), |
123 | 1 | Nibble::try_from(12).unwrap(), |
124 | 1 | Nibble::try_from(13).unwrap(), |
125 | 1 | ] |
126 | 1 | .iter() |
127 | 1 | .cloned(), |
128 | 1 | ) |
129 | 1 | .into_vacant() |
130 | 1 | .unwrap() |
131 | 1 | .insert_storage_value() |
132 | 1 | .insert((), ()); |
133 | 1 | |
134 | 1 | trie |
135 | 1 | }; |
136 | 1 | |
137 | 1 | assert!(with_removal.structure_equal(&expected)); |
138 | 1 | } |
139 | | |
140 | | #[test] |
141 | 1 | fn insert_in_between() { |
142 | 1 | let order1 = { |
143 | 1 | let mut trie = TrieStructure::new(); |
144 | 1 | |
145 | 1 | trie.node([Nibble::try_from(1).unwrap()].iter().cloned()) |
146 | 1 | .into_vacant() |
147 | 1 | .unwrap() |
148 | 1 | .insert_storage_value() |
149 | 1 | .insert((), ()); |
150 | 1 | |
151 | 1 | trie.node( |
152 | 1 | [ |
153 | 1 | Nibble::try_from(1).unwrap(), |
154 | 1 | Nibble::try_from(2).unwrap(), |
155 | 1 | Nibble::try_from(3).unwrap(), |
156 | 1 | Nibble::try_from(4).unwrap(), |
157 | 1 | Nibble::try_from(5).unwrap(), |
158 | 1 | ] |
159 | 1 | .iter() |
160 | 1 | .cloned(), |
161 | 1 | ) |
162 | 1 | .into_vacant() |
163 | 1 | .unwrap() |
164 | 1 | .insert_storage_value() |
165 | 1 | .insert((), ()); |
166 | 1 | |
167 | 1 | trie.node( |
168 | 1 | [ |
169 | 1 | Nibble::try_from(1).unwrap(), |
170 | 1 | Nibble::try_from(2).unwrap(), |
171 | 1 | Nibble::try_from(3).unwrap(), |
172 | 1 | ] |
173 | 1 | .iter() |
174 | 1 | .cloned(), |
175 | 1 | ) |
176 | 1 | .into_vacant() |
177 | 1 | .unwrap() |
178 | 1 | .insert_storage_value() |
179 | 1 | .insert((), ()); |
180 | 1 | |
181 | 1 | trie |
182 | 1 | }; |
183 | 1 | |
184 | 1 | let order2 = { |
185 | 1 | let mut trie = TrieStructure::new(); |
186 | 1 | |
187 | 1 | trie.node( |
188 | 1 | [ |
189 | 1 | Nibble::try_from(1).unwrap(), |
190 | 1 | Nibble::try_from(2).unwrap(), |
191 | 1 | Nibble::try_from(3).unwrap(), |
192 | 1 | ] |
193 | 1 | .iter() |
194 | 1 | .cloned(), |
195 | 1 | ) |
196 | 1 | .into_vacant() |
197 | 1 | .unwrap() |
198 | 1 | .insert_storage_value() |
199 | 1 | .insert((), ()); |
200 | 1 | |
201 | 1 | trie.node( |
202 | 1 | [ |
203 | 1 | Nibble::try_from(1).unwrap(), |
204 | 1 | Nibble::try_from(2).unwrap(), |
205 | 1 | Nibble::try_from(3).unwrap(), |
206 | 1 | Nibble::try_from(4).unwrap(), |
207 | 1 | Nibble::try_from(5).unwrap(), |
208 | 1 | ] |
209 | 1 | .iter() |
210 | 1 | .cloned(), |
211 | 1 | ) |
212 | 1 | .into_vacant() |
213 | 1 | .unwrap() |
214 | 1 | .insert_storage_value() |
215 | 1 | .insert((), ()); |
216 | 1 | |
217 | 1 | trie.node([Nibble::try_from(1).unwrap()].iter().cloned()) |
218 | 1 | .into_vacant() |
219 | 1 | .unwrap() |
220 | 1 | .insert_storage_value() |
221 | 1 | .insert((), ()); |
222 | 1 | |
223 | 1 | trie |
224 | 1 | }; |
225 | 1 | |
226 | 1 | let order3 = { |
227 | 1 | let mut trie = TrieStructure::new(); |
228 | 1 | |
229 | 1 | trie.node( |
230 | 1 | [ |
231 | 1 | Nibble::try_from(1).unwrap(), |
232 | 1 | Nibble::try_from(2).unwrap(), |
233 | 1 | Nibble::try_from(3).unwrap(), |
234 | 1 | Nibble::try_from(4).unwrap(), |
235 | 1 | Nibble::try_from(5).unwrap(), |
236 | 1 | ] |
237 | 1 | .iter() |
238 | 1 | .cloned(), |
239 | 1 | ) |
240 | 1 | .into_vacant() |
241 | 1 | .unwrap() |
242 | 1 | .insert_storage_value() |
243 | 1 | .insert((), ()); |
244 | 1 | |
245 | 1 | trie.node( |
246 | 1 | [ |
247 | 1 | Nibble::try_from(1).unwrap(), |
248 | 1 | Nibble::try_from(2).unwrap(), |
249 | 1 | Nibble::try_from(3).unwrap(), |
250 | 1 | ] |
251 | 1 | .iter() |
252 | 1 | .cloned(), |
253 | 1 | ) |
254 | 1 | .into_vacant() |
255 | 1 | .unwrap() |
256 | 1 | .insert_storage_value() |
257 | 1 | .insert((), ()); |
258 | 1 | |
259 | 1 | trie.node([Nibble::try_from(1).unwrap()].iter().cloned()) |
260 | 1 | .into_vacant() |
261 | 1 | .unwrap() |
262 | 1 | .insert_storage_value() |
263 | 1 | .insert((), ()); |
264 | 1 | |
265 | 1 | trie |
266 | 1 | }; |
267 | 1 | |
268 | 1 | assert!(order1.structure_equal(&order2)); |
269 | 1 | assert!(order2.structure_equal(&order3)); |
270 | 1 | assert!(order1.structure_equal(&order3)); |
271 | 1 | } |
272 | | |
273 | | #[test] |
274 | 1 | fn insert_branch() { |
275 | 1 | let mut trie = TrieStructure::new(); |
276 | 1 | |
277 | 1 | trie.node([Nibble::try_from(1).unwrap()].iter().cloned()) |
278 | 1 | .into_vacant() |
279 | 1 | .unwrap() |
280 | 1 | .insert_storage_value() |
281 | 1 | .insert((), ()); |
282 | 1 | |
283 | 1 | trie.node( |
284 | 1 | [ |
285 | 1 | Nibble::try_from(1).unwrap(), |
286 | 1 | Nibble::try_from(2).unwrap(), |
287 | 1 | Nibble::try_from(3).unwrap(), |
288 | 1 | Nibble::try_from(4).unwrap(), |
289 | 1 | Nibble::try_from(5).unwrap(), |
290 | 1 | ] |
291 | 1 | .iter() |
292 | 1 | .cloned(), |
293 | 1 | ) |
294 | 1 | .into_vacant() |
295 | 1 | .unwrap() |
296 | 1 | .insert_storage_value() |
297 | 1 | .insert((), ()); |
298 | 1 | |
299 | 1 | trie.node( |
300 | 1 | [ |
301 | 1 | Nibble::try_from(1).unwrap(), |
302 | 1 | Nibble::try_from(2).unwrap(), |
303 | 1 | Nibble::try_from(3).unwrap(), |
304 | 1 | Nibble::try_from(5).unwrap(), |
305 | 1 | Nibble::try_from(6).unwrap(), |
306 | 1 | ] |
307 | 1 | .iter() |
308 | 1 | .cloned(), |
309 | 1 | ) |
310 | 1 | .into_vacant() |
311 | 1 | .unwrap() |
312 | 1 | .insert_storage_value() |
313 | 1 | .insert((), ()); |
314 | 1 | |
315 | 1 | assert!(!trie |
316 | 1 | .node( |
317 | 1 | [ |
318 | 1 | Nibble::try_from(1).unwrap(), |
319 | 1 | Nibble::try_from(2).unwrap(), |
320 | 1 | Nibble::try_from(3).unwrap(), |
321 | 1 | ] |
322 | 1 | .iter() |
323 | 1 | .cloned(), |
324 | 1 | ) |
325 | 1 | .into_occupied() |
326 | 1 | .unwrap() |
327 | 1 | .has_storage_value()); |
328 | 1 | } |
329 | | |
330 | | #[test] |
331 | 1 | fn remove_prefix_basic() { |
332 | 1 | let mut trie = TrieStructure::new(); |
333 | 1 | |
334 | 1 | trie.node([Nibble::try_from(1).unwrap()].iter().cloned()) |
335 | 1 | .into_vacant() |
336 | 1 | .unwrap() |
337 | 1 | .insert_storage_value() |
338 | 1 | .insert((), ()); |
339 | 1 | trie.node( |
340 | 1 | [ |
341 | 1 | Nibble::try_from(1).unwrap(), |
342 | 1 | Nibble::try_from(2).unwrap(), |
343 | 1 | Nibble::try_from(3).unwrap(), |
344 | 1 | ] |
345 | 1 | .iter() |
346 | 1 | .cloned(), |
347 | 1 | ) |
348 | 1 | .into_vacant() |
349 | 1 | .unwrap() |
350 | 1 | .insert_storage_value() |
351 | 1 | .insert((), ()); |
352 | 1 | trie.node( |
353 | 1 | [ |
354 | 1 | Nibble::try_from(1).unwrap(), |
355 | 1 | Nibble::try_from(2).unwrap(), |
356 | 1 | Nibble::try_from(4).unwrap(), |
357 | 1 | ] |
358 | 1 | .iter() |
359 | 1 | .cloned(), |
360 | 1 | ) |
361 | 1 | .into_vacant() |
362 | 1 | .unwrap() |
363 | 1 | .insert_storage_value() |
364 | 1 | .insert((), ()); |
365 | 1 | trie.node( |
366 | 1 | [ |
367 | 1 | Nibble::try_from(1).unwrap(), |
368 | 1 | Nibble::try_from(2).unwrap(), |
369 | 1 | Nibble::try_from(4).unwrap(), |
370 | 1 | Nibble::try_from(5).unwrap(), |
371 | 1 | Nibble::try_from(6).unwrap(), |
372 | 1 | ] |
373 | 1 | .iter() |
374 | 1 | .cloned(), |
375 | 1 | ) |
376 | 1 | .into_vacant() |
377 | 1 | .unwrap() |
378 | 1 | .insert_storage_value() |
379 | 1 | .insert((), ()); |
380 | 1 | |
381 | 1 | trie.remove_prefix( |
382 | 1 | [Nibble::try_from(1).unwrap(), Nibble::try_from(2).unwrap()] |
383 | 1 | .iter() |
384 | 1 | .cloned(), |
385 | 1 | ); |
386 | 1 | |
387 | 1 | assert_eq!(trie.len(), 1); |
388 | 1 | assert!(trie |
389 | 1 | .node([Nibble::try_from(1).unwrap(),].iter().cloned(),) |
390 | 1 | .into_occupied() |
391 | 1 | .unwrap() |
392 | 1 | .has_storage_value()); |
393 | 1 | } |
394 | | |
395 | | #[test] |
396 | 1 | fn remove_prefix_clear_all() { |
397 | 1 | let mut trie = TrieStructure::new(); |
398 | 1 | |
399 | 1 | trie.node( |
400 | 1 | [ |
401 | 1 | Nibble::try_from(1).unwrap(), |
402 | 1 | Nibble::try_from(2).unwrap(), |
403 | 1 | Nibble::try_from(3).unwrap(), |
404 | 1 | ] |
405 | 1 | .iter() |
406 | 1 | .cloned(), |
407 | 1 | ) |
408 | 1 | .into_vacant() |
409 | 1 | .unwrap() |
410 | 1 | .insert_storage_value() |
411 | 1 | .insert((), ()); |
412 | 1 | trie.node( |
413 | 1 | [ |
414 | 1 | Nibble::try_from(1).unwrap(), |
415 | 1 | Nibble::try_from(2).unwrap(), |
416 | 1 | Nibble::try_from(4).unwrap(), |
417 | 1 | ] |
418 | 1 | .iter() |
419 | 1 | .cloned(), |
420 | 1 | ) |
421 | 1 | .into_vacant() |
422 | 1 | .unwrap() |
423 | 1 | .insert_storage_value() |
424 | 1 | .insert((), ()); |
425 | 1 | trie.node( |
426 | 1 | [ |
427 | 1 | Nibble::try_from(1).unwrap(), |
428 | 1 | Nibble::try_from(2).unwrap(), |
429 | 1 | Nibble::try_from(4).unwrap(), |
430 | 1 | Nibble::try_from(5).unwrap(), |
431 | 1 | Nibble::try_from(6).unwrap(), |
432 | 1 | ] |
433 | 1 | .iter() |
434 | 1 | .cloned(), |
435 | 1 | ) |
436 | 1 | .into_vacant() |
437 | 1 | .unwrap() |
438 | 1 | .insert_storage_value() |
439 | 1 | .insert((), ()); |
440 | 1 | |
441 | 1 | trie.remove_prefix( |
442 | 1 | [Nibble::try_from(1).unwrap(), Nibble::try_from(2).unwrap()] |
443 | 1 | .iter() |
444 | 1 | .cloned(), |
445 | 1 | ); |
446 | 1 | |
447 | 1 | assert!(trie.is_empty()); |
448 | 1 | } |
449 | | |
450 | | #[test] |
451 | 1 | fn remove_prefix_exact() { |
452 | 1 | let mut trie = TrieStructure::new(); |
453 | 1 | |
454 | 1 | trie.node([Nibble::try_from(1).unwrap()].iter().cloned()) |
455 | 1 | .into_vacant() |
456 | 1 | .unwrap() |
457 | 1 | .insert_storage_value() |
458 | 1 | .insert((), ()); |
459 | 1 | |
460 | 1 | trie.node( |
461 | 1 | [ |
462 | 1 | Nibble::try_from(1).unwrap(), |
463 | 1 | Nibble::try_from(2).unwrap(), |
464 | 1 | Nibble::try_from(3).unwrap(), |
465 | 1 | ] |
466 | 1 | .iter() |
467 | 1 | .cloned(), |
468 | 1 | ) |
469 | 1 | .into_vacant() |
470 | 1 | .unwrap() |
471 | 1 | .insert_storage_value() |
472 | 1 | .insert((), ()); |
473 | 1 | trie.node( |
474 | 1 | [ |
475 | 1 | Nibble::try_from(1).unwrap(), |
476 | 1 | Nibble::try_from(2).unwrap(), |
477 | 1 | Nibble::try_from(3).unwrap(), |
478 | 1 | Nibble::try_from(4).unwrap(), |
479 | 1 | Nibble::try_from(5).unwrap(), |
480 | 1 | ] |
481 | 1 | .iter() |
482 | 1 | .cloned(), |
483 | 1 | ) |
484 | 1 | .into_vacant() |
485 | 1 | .unwrap() |
486 | 1 | .insert_storage_value() |
487 | 1 | .insert((), ()); |
488 | 1 | trie.node( |
489 | 1 | [ |
490 | 1 | Nibble::try_from(1).unwrap(), |
491 | 1 | Nibble::try_from(2).unwrap(), |
492 | 1 | Nibble::try_from(3).unwrap(), |
493 | 1 | Nibble::try_from(4).unwrap(), |
494 | 1 | Nibble::try_from(6).unwrap(), |
495 | 1 | ] |
496 | 1 | .iter() |
497 | 1 | .cloned(), |
498 | 1 | ) |
499 | 1 | .into_vacant() |
500 | 1 | .unwrap() |
501 | 1 | .insert_storage_value() |
502 | 1 | .insert((), ()); |
503 | 1 | |
504 | 1 | trie.remove_prefix( |
505 | 1 | [ |
506 | 1 | Nibble::try_from(1).unwrap(), |
507 | 1 | Nibble::try_from(2).unwrap(), |
508 | 1 | Nibble::try_from(3).unwrap(), |
509 | 1 | ] |
510 | 1 | .iter() |
511 | 1 | .cloned(), |
512 | 1 | ); |
513 | 1 | |
514 | 1 | assert_eq!(trie.len(), 1); |
515 | 1 | assert!(trie |
516 | 1 | .node([Nibble::try_from(1).unwrap(),].iter().cloned(),) |
517 | 1 | .into_occupied() |
518 | 1 | .unwrap() |
519 | 1 | .has_storage_value()); |
520 | 1 | } |
521 | | |
522 | | #[test] |
523 | 1 | fn remove_prefix_doesnt_match_anything() { |
524 | 1 | let mut trie = TrieStructure::new(); |
525 | 1 | |
526 | 1 | trie.node( |
527 | 1 | [ |
528 | 1 | Nibble::try_from(1).unwrap(), |
529 | 1 | Nibble::try_from(2).unwrap(), |
530 | 1 | Nibble::try_from(3).unwrap(), |
531 | 1 | ] |
532 | 1 | .iter() |
533 | 1 | .cloned(), |
534 | 1 | ) |
535 | 1 | .into_vacant() |
536 | 1 | .unwrap() |
537 | 1 | .insert_storage_value() |
538 | 1 | .insert((), ()); |
539 | 1 | |
540 | 1 | trie.remove_prefix( |
541 | 1 | [ |
542 | 1 | Nibble::try_from(1).unwrap(), |
543 | 1 | Nibble::try_from(2).unwrap(), |
544 | 1 | Nibble::try_from(5).unwrap(), |
545 | 1 | ] |
546 | 1 | .iter() |
547 | 1 | .cloned(), |
548 | 1 | ); |
549 | 1 | |
550 | 1 | assert_eq!(trie.len(), 1); |
551 | 1 | assert!(trie |
552 | 1 | .node( |
553 | 1 | [ |
554 | 1 | Nibble::try_from(1).unwrap(), |
555 | 1 | Nibble::try_from(2).unwrap(), |
556 | 1 | Nibble::try_from(3).unwrap(), |
557 | 1 | ] |
558 | 1 | .iter() |
559 | 1 | .cloned(), |
560 | 1 | ) |
561 | 1 | .into_occupied() |
562 | 1 | .unwrap() |
563 | 1 | .has_storage_value()); |
564 | 1 | } |
565 | | |
566 | | #[test] |
567 | 1 | fn remove_prefix_nothing_to_remove() { |
568 | 1 | let mut trie = TrieStructure::new(); |
569 | 1 | |
570 | 1 | trie.node( |
571 | 1 | [ |
572 | 1 | Nibble::try_from(1).unwrap(), |
573 | 1 | Nibble::try_from(2).unwrap(), |
574 | 1 | Nibble::try_from(3).unwrap(), |
575 | 1 | ] |
576 | 1 | .iter() |
577 | 1 | .cloned(), |
578 | 1 | ) |
579 | 1 | .into_vacant() |
580 | 1 | .unwrap() |
581 | 1 | .insert_storage_value() |
582 | 1 | .insert((), ()); |
583 | 1 | |
584 | 1 | trie.remove_prefix( |
585 | 1 | [ |
586 | 1 | Nibble::try_from(1).unwrap(), |
587 | 1 | Nibble::try_from(2).unwrap(), |
588 | 1 | Nibble::try_from(3).unwrap(), |
589 | 1 | Nibble::try_from(4).unwrap(), |
590 | 1 | ] |
591 | 1 | .iter() |
592 | 1 | .cloned(), |
593 | 1 | ); |
594 | 1 | |
595 | 1 | assert_eq!(trie.len(), 1); |
596 | 1 | assert!(trie |
597 | 1 | .node( |
598 | 1 | [ |
599 | 1 | Nibble::try_from(1).unwrap(), |
600 | 1 | Nibble::try_from(2).unwrap(), |
601 | 1 | Nibble::try_from(3).unwrap(), |
602 | 1 | ] |
603 | 1 | .iter() |
604 | 1 | .cloned(), |
605 | 1 | ) |
606 | 1 | .into_occupied() |
607 | 1 | .unwrap() |
608 | 1 | .has_storage_value()); |
609 | 1 | } |
610 | | |
611 | | #[test] |
612 | 1 | fn fuzzing() { |
613 | 559k | fn uniform_sample(min: u8, max: u8) -> u8 { |
614 | 559k | Uniform::new_inclusive(min, max).sample(&mut rand::thread_rng()) |
615 | 559k | } |
616 | | |
617 | | // We run the test multiple times because of randomness. |
618 | 257 | for _ in 0..256 { |
619 | | // Generate a set of keys that will find themselves in the tries in the end. |
620 | 256 | let final_storage: HashSet<Vec<Nibble>> = { |
621 | 256 | let mut list = vec![Vec::new()]; |
622 | 1.53k | for _ in 0..5 { |
623 | 30.9k | for elem in list.clone().into_iter()1.28k { |
624 | 30.9k | for _ in 0..uniform_sample(0, 4) { |
625 | 61.9k | let mut elem = elem.clone(); |
626 | 93.0k | for _ in 0..uniform_sample(0, 3) { |
627 | 93.0k | elem.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
628 | 93.0k | } |
629 | 61.9k | list.push(elem); |
630 | | } |
631 | | } |
632 | | } |
633 | 256 | list.into_iter().skip(1).collect() |
634 | 256 | }; |
635 | 256 | |
636 | 256 | // Create multiple tries, each with a different order of insertion for the nodes. |
637 | 256 | let mut tries = Vec::new(); |
638 | 4.35k | for _ in 0..16 { |
639 | | #[derive(Debug, Copy, Clone)] |
640 | | enum Op { |
641 | | Insert, |
642 | | Remove, |
643 | | ClearPrefix, |
644 | | } |
645 | | |
646 | 4.09k | let mut operations = final_storage |
647 | 4.09k | .iter() |
648 | 727k | .map(|k| (k.clone(), Op::Insert)) |
649 | 4.09k | .collect::<Vec<_>>(); |
650 | 4.09k | operations.shuffle(&mut rand::thread_rng()); |
651 | 4.09k | |
652 | 4.09k | // Insert in `operations` a tuple of an insertion and removal. |
653 | 4.09k | for _ in 0..uniform_sample(0, 24) { |
654 | 49.1k | let mut base_key = match operations.choose(&mut rand::thread_rng()) { |
655 | 49.1k | Some(op) => op.0.clone(), |
656 | 0 | None => continue, |
657 | | }; |
658 | | |
659 | 49.1k | for _ in 0..uniform_sample(0, 2) { |
660 | 49.1k | base_key.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
661 | 49.1k | } |
662 | | |
663 | 49.1k | let max_remove_index = operations |
664 | 49.1k | .iter() |
665 | 7.77M | .position(|(k, _)| *k == base_key) |
666 | 49.1k | .unwrap_or(operations.len()); |
667 | 49.1k | |
668 | 49.1k | let remove_index = |
669 | 49.1k | Uniform::new_inclusive(0, max_remove_index).sample(&mut rand::thread_rng()); |
670 | 49.1k | let insert_index = |
671 | 49.1k | Uniform::new_inclusive(0, remove_index).sample(&mut rand::thread_rng()); |
672 | 49.1k | operations.insert(remove_index, (base_key.clone(), Op::Remove)); |
673 | 49.1k | operations.insert(insert_index, (base_key, Op::Insert)); |
674 | | } |
675 | | |
676 | | // Insert in `operations` a tuple of multiple insertions of the same prefix, and |
677 | | // removal of said prefix. |
678 | 4.09k | for _ in 0..uniform_sample(0, 4) { |
679 | 8.10k | let mut base_key = match operations.choose(&mut rand::thread_rng()) { |
680 | 8.10k | Some(op) => op.0.clone(), |
681 | 0 | None => continue, |
682 | | }; |
683 | | |
684 | 8.10k | for _ in 0..uniform_sample(0, 2) { |
685 | 8.08k | base_key.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
686 | 8.08k | } |
687 | | |
688 | 8.10k | let max_remove_index = operations |
689 | 8.10k | .iter() |
690 | 1.32M | .position(|(k, _)| k.starts_with(&base_key)) |
691 | 8.10k | .unwrap_or(operations.len()); |
692 | 8.10k | |
693 | 8.10k | let mut remove_index = |
694 | 8.10k | Uniform::new_inclusive(0, max_remove_index).sample(&mut rand::thread_rng()); |
695 | 8.10k | operations.insert(remove_index, (base_key.clone(), Op::ClearPrefix)); |
696 | 8.10k | |
697 | 8.10k | for _ in 0..uniform_sample(0, 12) { |
698 | 48.4k | let mut base_key = base_key.clone(); |
699 | 194k | for _ in 0..uniform_sample(0, 8) { |
700 | 194k | base_key.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
701 | 194k | } |
702 | | |
703 | 48.4k | if operations |
704 | 48.4k | .iter() |
705 | 48.4k | .take(remove_index) |
706 | 4.02M | .any(|(k, _)| *k == base_key)48.4k |
707 | | { |
708 | 1.80k | continue; |
709 | 46.5k | } |
710 | 46.5k | |
711 | 46.5k | let insert_index = |
712 | 46.5k | Uniform::new_inclusive(0, remove_index).sample(&mut rand::thread_rng()); |
713 | 46.5k | operations.insert(insert_index, (base_key, Op::Insert)); |
714 | 46.5k | remove_index += 1; |
715 | | } |
716 | | } |
717 | | |
718 | | // Create a trie and applies `operations` on it. |
719 | 4.09k | let mut trie = TrieStructure::new(); |
720 | 880k | for (op_index, (key, op)) in operations.clone().into_iter().enumerate()4.09k { |
721 | 880k | match op { |
722 | 823k | Op::Insert => match trie.node(key.into_iter()) { |
723 | 724k | super::Entry::Vacant(e) => { |
724 | 724k | e.insert_storage_value().insert((), ()); |
725 | 724k | } |
726 | 99.0k | super::Entry::Occupied(super::NodeAccess::Branch(e)) => { |
727 | 99.0k | e.insert_storage_value(); |
728 | 99.0k | } |
729 | | super::Entry::Occupied(super::NodeAccess::Storage(_)) => { |
730 | 0 | unreachable!("index: {}\nops:{:?}", op_index, operations) |
731 | | } |
732 | | }, |
733 | 49.1k | Op::Remove => match trie.node(key.into_iter()) { |
734 | 49.1k | super::Entry::Occupied(super::NodeAccess::Storage(e)) => { |
735 | 49.1k | e.remove(); |
736 | 49.1k | } |
737 | | super::Entry::Vacant(_) => { |
738 | 0 | unreachable!("index: {}\nops:{:?}", op_index, operations) |
739 | | } |
740 | | super::Entry::Occupied(super::NodeAccess::Branch(_)) => { |
741 | 0 | unreachable!("index: {}\nops:{:?}", op_index, operations) |
742 | | } |
743 | | }, |
744 | 8.10k | Op::ClearPrefix => { |
745 | 8.10k | trie.remove_prefix(key.into_iter()); |
746 | 8.10k | } |
747 | | } |
748 | | } |
749 | | |
750 | 4.09k | tries.push(trie); |
751 | | } |
752 | | |
753 | | // Compare them to make sure they're equal. |
754 | 3.84k | for trie in 1..tries.len()256 { |
755 | 3.84k | tries[0].structure_equal(&tries[trie]); |
756 | 3.84k | } |
757 | | } |
758 | 1 | } |
759 | | |
760 | | #[test] |
761 | 1 | fn iter_properly_traverses() { |
762 | 1 | let mut trie = TrieStructure::new(); |
763 | 1 | |
764 | 1 | // Fill the trie with entries with randomly generated keys. |
765 | 1 | for _ in 0..Uniform::new_inclusive(0, 32).sample(&mut rand::thread_rng()) { |
766 | 6 | let mut key = Vec::new(); |
767 | 46 | for _ in 0..Uniform::new_inclusive(0, 12).sample(&mut rand::thread_rng()) { |
768 | 46 | key.push( |
769 | 46 | Nibble::try_from(Uniform::new_inclusive(0, 15).sample(&mut rand::thread_rng())) |
770 | 46 | .unwrap(), |
771 | 46 | ); |
772 | 46 | } |
773 | | |
774 | 6 | match trie.node(key.into_iter()) { |
775 | 6 | super::Entry::Vacant(e) => { |
776 | 6 | e.insert_storage_value().insert((), ()); |
777 | 6 | } |
778 | 0 | super::Entry::Occupied(super::NodeAccess::Branch(e)) => { |
779 | 0 | e.insert_storage_value(); |
780 | 0 | } |
781 | 0 | super::Entry::Occupied(super::NodeAccess::Storage(_)) => {} |
782 | | } |
783 | | } |
784 | | |
785 | 1 | assert_eq!(trie.iter_ordered().count(), trie.nodes.len()); |
786 | 1 | } |
787 | | |
788 | | #[test] |
789 | 1 | fn range() { |
790 | | // This test makes sure that the `range` function works as expected. |
791 | | // It first builds a random tree structure, then puts all the nodes of the structure into |
792 | | // a `BTreeMap` (from the standard library), then compares whether `TreeStructure::range` |
793 | | // returns the same results as `BTreeMap::range`. |
794 | | |
795 | 3.35M | fn uniform_sample(min: u8, max: u8) -> u8 { |
796 | 3.35M | Uniform::new_inclusive(min, max).sample(&mut rand::thread_rng()) |
797 | 3.35M | } |
798 | | |
799 | | // We run the test multiple times because of randomness. |
800 | 4.09k | for _ in 0..4096 { |
801 | | // Generate a set of random keys that will find themselves in the trie in the end. |
802 | 4.09k | let final_storage: BTreeSet<Vec<Nibble>> = { |
803 | 4.09k | let mut list = vec![Vec::new()]; |
804 | 20.4k | for _ in 0..4 { |
805 | 165k | for elem in list.clone().into_iter()16.3k { |
806 | 165k | for _ in 0..uniform_sample(0, 4) { |
807 | 330k | let mut elem = elem.clone(); |
808 | 495k | for _ in 0..uniform_sample(0, 3) { |
809 | 495k | elem.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
810 | 495k | } |
811 | 330k | list.push(elem); |
812 | | } |
813 | | } |
814 | | } |
815 | 4.09k | list.into_iter().skip(1).collect() |
816 | 4.09k | }; |
817 | 4.09k | |
818 | 4.09k | // Create a trie and puts `final_storage` in it. |
819 | 4.09k | let mut trie = TrieStructure::new(); |
820 | 249k | for key245k in &final_storage { |
821 | 245k | match trie.node(key.iter().copied()) { |
822 | 245k | super::Entry::Vacant(e) => { |
823 | 245k | e.insert_storage_value().insert((), ()); |
824 | 245k | } |
825 | 0 | super::Entry::Occupied(super::NodeAccess::Branch(e)) => { |
826 | 0 | e.insert_storage_value(); |
827 | 0 | } |
828 | | super::Entry::Occupied(super::NodeAccess::Storage(_)) => { |
829 | 0 | unreachable!() |
830 | | } |
831 | | } |
832 | | } |
833 | | |
834 | | // Create a `BTreeMap` containins all the nodes of the trie. |
835 | 4.09k | let btree_map = trie |
836 | 4.09k | .iter_unordered() |
837 | 259k | .map(|node_index| { |
838 | 259k | let full_key = trie |
839 | 259k | .node_full_key_by_index(node_index) |
840 | 259k | .unwrap() |
841 | 259k | .collect::<Vec<_>>(); |
842 | 259k | (full_key, node_index) |
843 | 259k | }) |
844 | 4.09k | .collect::<BTreeMap<_, _>>(); |
845 | | |
846 | | // Randomly query ranges of the btree map and the trie. |
847 | 266k | for _ in 0..64 { |
848 | 262k | let mut start_key = Vec::new(); |
849 | 655k | for _ in 0..uniform_sample(0, 5) { |
850 | 655k | start_key.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
851 | 655k | } |
852 | | |
853 | 262k | let mut end_key = Vec::new(); |
854 | 656k | for _ in 0..uniform_sample(0, 5) { |
855 | 656k | end_key.push(Nibble::try_from(uniform_sample(0, 15)).unwrap()); |
856 | 656k | } |
857 | | |
858 | 262k | let (start_range_btree, start_range_trie) = match uniform_sample(0, 2) { |
859 | 87.2k | 0 => ( |
860 | 87.2k | ops::Bound::Included(start_key.clone()), |
861 | 87.2k | ops::Bound::Included(start_key.iter().copied()), |
862 | 87.2k | ), |
863 | 87.8k | 1 => ( |
864 | 87.8k | ops::Bound::Excluded(start_key.clone()), |
865 | 87.8k | ops::Bound::Excluded(start_key.iter().copied()), |
866 | 87.8k | ), |
867 | 87.0k | 2 => (ops::Bound::Unbounded, ops::Bound::Unbounded), |
868 | 0 | _ => unreachable!(), |
869 | | }; |
870 | | |
871 | 262k | let (end_range_btree, end_range_trie) = match uniform_sample(0, 2) { |
872 | 87.0k | 0 => ( |
873 | 87.0k | ops::Bound::Included(end_key.clone()), |
874 | 87.0k | ops::Bound::Included(end_key.iter().copied()), |
875 | 87.0k | ), |
876 | 87.3k | 1 => ( |
877 | 87.3k | ops::Bound::Excluded(end_key.clone()), |
878 | 87.3k | ops::Bound::Excluded(end_key.iter().copied()), |
879 | 87.3k | ), |
880 | 87.7k | 2 => (ops::Bound::Unbounded, ops::Bound::Unbounded), |
881 | 0 | _ => unreachable!(), |
882 | | }; |
883 | | |
884 | 262k | match (&start_range_btree, &end_range_btree) { |
885 | | ( |
886 | 58.3k | ops::Bound::Included(start58.0k ) | ops::Bound::Excluded(start), |
887 | 58.2k | ops::Bound::Included(end58.1k ) | ops::Bound::Excluded(end), |
888 | 116k | ) if start > end56.5k => { |
889 | 56.5k | let trie_result = trie |
890 | 56.5k | .range_iter(start_range_trie, end_range_trie) |
891 | 56.5k | .collect::<Vec<_>>(); |
892 | 56.5k | assert!( |
893 | 56.5k | trie_result.is_empty(), |
894 | 0 | "\nbtree: {:?}\ntrie_result: {:?}\nstart: {:?}\nend: {:?}", |
895 | | btree_map, |
896 | | trie_result, |
897 | | start_range_btree, |
898 | | end_range_btree |
899 | | ); |
900 | 56.5k | continue; |
901 | | } |
902 | 15.0k | (ops::Bound::Excluded(start), ops::Bound::Excluded(end)) if start == end => { |
903 | 877 | let trie_result = trie |
904 | 877 | .range_iter(start_range_trie, end_range_trie) |
905 | 877 | .collect::<Vec<_>>(); |
906 | 877 | assert!( |
907 | 877 | trie_result.is_empty(), |
908 | 0 | "\nbtree: {:?}\ntrie_result: {:?}\nstart: {:?}\nend: {:?}", |
909 | | btree_map, |
910 | | trie_result, |
911 | | start_range_btree, |
912 | | end_range_btree |
913 | | ); |
914 | 877 | continue; |
915 | | } |
916 | 204k | _ => {} |
917 | 204k | } |
918 | 204k | |
919 | 204k | let btree_result = btree_map |
920 | 204k | .range((start_range_btree.clone(), end_range_btree.clone())) |
921 | 6.85M | .map(|(_, idx)| *idx) |
922 | 204k | .collect::<Vec<_>>(); |
923 | 204k | let trie_result = trie |
924 | 204k | .range_iter(start_range_trie, end_range_trie) |
925 | 204k | .collect::<Vec<_>>(); |
926 | 204k | assert_eq!( |
927 | | btree_result, trie_result, |
928 | 0 | "\nbtree: {:?}\nbtree_result: {:?}\ntrie_result: {:?}\nstart: {:?}\nend: {:?}", |
929 | | btree_map, btree_result, trie_result, start_range_btree, end_range_btree |
930 | | ); |
931 | | } |
932 | | } |
933 | 1 | } |