art/
lib.rs

1use std::fmt;
2use std::marker::PhantomData;
3use std::mem::size_of;
4use std::ops::{Bound, RangeBounds};
5
6// This is important due to the use of tagged pointers
7// in the low 3 bits of the node addresses.
8#[repr(align(8))]
9struct MinAlign<T>(T);
10
11/// An Adaptive Radix Trie (ART) for fixed-length
12/// keys.
13#[derive(Clone)]
14pub struct Art<ValueType, const KEY_LENGTH: usize> {
15    len: usize,
16    root: Node<ValueType>,
17}
18
19impl<V, const K: usize> FromIterator<([u8; K], V)> for Art<V, K> {
20    fn from_iter<T>(iter: T) -> Self
21    where
22        T: IntoIterator<Item = ([u8; K], V)>,
23    {
24        let mut art = Art::new();
25        for (k, v) in iter {
26            art.insert(k, v);
27        }
28        art
29    }
30}
31
32impl<V: fmt::Debug, const K: usize> fmt::Debug for Art<V, K> {
33    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
34        f.write_str("Art ")?;
35        f.debug_map().entries(self.iter()).finish()?;
36        Ok(())
37    }
38}
39
40impl<V, const K: usize> Default for Art<V, K> {
41    fn default() -> Art<V, K> {
42        Art {
43            len: 0,
44            root: Node::none(),
45        }
46    }
47}
48
49impl<V: PartialEq, const K: usize> PartialEq for Art<V, K> {
50    fn eq(&self, other: &Self) -> bool {
51        if self.len() != other.len() {
52            return false;
53        }
54
55        let mut other_iter = other.iter();
56
57        for self_item in self.iter() {
58            if let Some(other_item) = other_iter.next() {
59                if self_item != other_item {
60                    return false;
61                }
62            } else {
63                return false;
64            }
65        }
66
67        if other_iter.next().is_none() {
68            true
69        } else {
70            false
71        }
72    }
73}
74
75impl<V: Eq, const K: usize> Eq for Art<V, K> {}
76
77impl<V, const K: usize> Art<V, K> {
78    pub const fn new() -> Art<V, K> {
79        // TODO compiler error if K is above a range that
80        // will cause stack overflow when the recursive prune
81        // function is called
82        Art {
83            len: 0,
84            root: Node::none(),
85        }
86    }
87
88    pub const fn len(&self) -> usize {
89        self.len
90    }
91
92    pub const fn is_empty(&self) -> bool {
93        self.len() == 0
94    }
95
96    pub fn insert(&mut self, key: [u8; K], mut value: V) -> Option<V> {
97        let (parent_opt, cursor) = self.slot_for_key(&key, true).unwrap();
98        match cursor.deref_mut() {
99            NodeMut::Value(ref mut old) => {
100                std::mem::swap(&mut **old, &mut value);
101                Some(value)
102            }
103            NodeMut::None => {
104                *cursor = Node::value(value);
105                if let Some(children) = parent_opt {
106                    *children = children.checked_add(1).unwrap();
107                }
108                self.len += 1;
109                None
110            }
111            _ => unreachable!(),
112        }
113    }
114
115    pub fn remove(&mut self, key: &[u8; K]) -> Option<V> {
116        let (parent_opt, cursor) = self.slot_for_key(key, false)?;
117
118        match std::mem::take(cursor).take() {
119            Some(old) => {
120                if let Some(children) = parent_opt {
121                    *children = children.checked_sub(1).unwrap();
122
123                    if *children == 48
124                        || *children == 16
125                        || *children == 4
126                        || *children == 1
127                        || *children == 0
128                    {
129                        self.prune(key);
130                    }
131                }
132                self.len -= 1;
133                Some(old)
134            }
135            None => None,
136        }
137    }
138
139    // []
140    //  don't do anything
141    // [1]
142    //  shrink without while loop
143    // [1][2]
144    //
145    // [1:2]
146    // [1:2][3]
147    // [1][2:3]
148    // [12:3][4]
149    // [1:2][3:4]
150    fn prune(&mut self, key: &[u8; K]) {
151        self.root.prune(key);
152    }
153
154    // returns the optional parent node for child maintenance, and the value node
155    fn slot_for_key(
156        &mut self,
157        key: &[u8; K],
158        is_add: bool,
159    ) -> Option<(Option<&mut u16>, &mut Node<V>)> {
160        let mut parent: Option<&mut u16> = None;
161        let mut path: &[u8] = &key[..];
162        let mut cursor: &mut Node<V> = &mut self.root;
163        // println!("root is {:?}", cursor);
164
165        while !path.is_empty() {
166            //println!("path: {:?} cursor {:?}", path, cursor);
167            cursor.assert_size();
168            if cursor.is_none() {
169                if !is_add {
170                    return None;
171                }
172                // we need to create intermediate nodes before
173                // populating the value for this insert
174                *cursor = Node::node1(Box::default());
175                if let Some(children) = parent {
176                    *children = children.checked_add(1).unwrap();
177                }
178                let prefix_len = (path.len() - 1).min(MAX_PATH_COMPRESSION_BYTES);
179                let prefix = &path[..prefix_len];
180                cursor.header_mut().path[..prefix_len].copy_from_slice(prefix);
181                cursor.header_mut().path_len = u8::try_from(prefix_len).unwrap();
182                let (p, child) = cursor.child_mut(path[prefix_len], is_add, false).unwrap();
183                parent = Some(p);
184                cursor = child;
185                path = &path[prefix_len + 1..];
186                continue;
187            }
188
189            let prefix = cursor.prefix();
190            let partial_path = &path[..path.len() - 1];
191            if !partial_path.starts_with(prefix) {
192                if !is_add {
193                    return None;
194                }
195                // path compression needs to be reduced
196                // to allow for this key, which does not
197                // share the compressed path.
198                // println!("truncating cursor at {:?}", cursor);
199                cursor.truncate_prefix(partial_path);
200                // println!("cursor is now after truncation {:?}", cursor);
201                continue;
202            }
203
204            let next_byte = path[prefix.len()];
205            path = &path[prefix.len() + 1..];
206
207            //println!("cursor is now {:?}", cursor);
208            let clear_child_index = !is_add && path.is_empty();
209            let (p, next_cursor) =
210                if let Some(opt) = cursor.child_mut(next_byte, is_add, clear_child_index) {
211                    opt
212                } else {
213                    assert!(!is_add);
214                    return None;
215                };
216            cursor = next_cursor;
217            parent = Some(p);
218        }
219
220        Some((parent, cursor))
221    }
222
223    pub fn get(&self, key: &[u8; K]) -> Option<&V> {
224        let mut k: &[u8] = &*key;
225        let mut cursor: &Node<V> = &self.root;
226
227        while !k.is_empty() {
228            let prefix = cursor.prefix();
229
230            if !k.starts_with(prefix) {
231                return None;
232            }
233
234            cursor = cursor.child(k[prefix.len()])?;
235            k = &k[prefix.len() + 1..];
236        }
237
238        match cursor.deref() {
239            NodeRef::Value(ref v) => return Some(v),
240            NodeRef::None => return None,
241            _ => unreachable!(),
242        }
243    }
244
245    pub fn iter(&self) -> Iter<'_, V, K> {
246        self.range(..)
247    }
248
249    pub fn range<'a, R>(&'a self, range: R) -> Iter<'a, V, K>
250    where
251        R: RangeBounds<[u8; K]>,
252    {
253        Iter {
254            root: self.root.node_iter(),
255            path: vec![],
256            rev_path: vec![],
257            lower_bound: map_bound(range.start_bound(), |b| *b),
258            upper_bound: map_bound(range.end_bound(), |b| *b),
259            finished_0: false,
260        }
261    }
262}
263
264fn map_bound<T, U, F: FnOnce(T) -> U>(bound: Bound<T>, f: F) -> Bound<U> {
265    match bound {
266        Bound::Unbounded => Bound::Unbounded,
267        Bound::Included(x) => Bound::Included(f(x)),
268        Bound::Excluded(x) => Bound::Excluded(f(x)),
269    }
270}
271
272#[cfg(target_pointer_width = "64")]
273const fn _size_and_alignment_tests() {
274    let _: [u8; 2_u32.pow(PTR_MASK.trailing_zeros()) as usize] =
275        [0; std::mem::align_of::<MinAlign<()>>()];
276    let _: [u8; 8] = [0; size_of::<Node<()>>()];
277    let _: [u8; 12] = [0; size_of::<Header>()];
278    let _: [u8; 24] = [0; size_of::<Node1<()>>()];
279    let _: [u8; 48] = [0; size_of::<Node4<()>>()];
280    let _: [u8; 160] = [0; size_of::<Node16<()>>()];
281    let _: [u8; 656] = [0; size_of::<Node48<()>>()];
282    let _: [u8; 2064] = [0; size_of::<Node256<()>>()];
283}
284
285const MAX_PATH_COMPRESSION_BYTES: usize = 9;
286
287const NONE_HEADER: Header = Header {
288    children: 0,
289    path_len: 0,
290    path: [0; MAX_PATH_COMPRESSION_BYTES],
291};
292
293const VALUE_HEADER: Header = Header {
294    children: 1,
295    path_len: 0,
296    path: [0; MAX_PATH_COMPRESSION_BYTES],
297};
298
299#[must_use]
300pub struct Iter<'a, V, const K: usize> {
301    root: NodeIter<'a, V>,
302    path: Vec<(u8, NodeIter<'a, V>)>,
303    rev_path: Vec<(u8, NodeIter<'a, V>)>,
304    lower_bound: Bound<[u8; K]>,
305    upper_bound: Bound<[u8; K]>,
306    finished_0: bool,
307}
308
309impl<'a, V, const K: usize> IntoIterator for &'a Art<V, K> {
310    type IntoIter = Iter<'a, V, K>;
311    type Item = ([u8; K], &'a V);
312
313    fn into_iter(self) -> Self::IntoIter {
314        self.iter()
315    }
316}
317
318impl<'a, V, const K: usize> Iter<'a, V, K> {
319    fn char_bound(&self, is_forward: bool) -> (Bound<u8>, Bound<u8>) {
320        let mut raw_path = [0_u8; K];
321        let mut raw_len = 0_usize;
322
323        let node_path = if is_forward {
324            &self.path
325        } else {
326            &self.rev_path
327        };
328
329        let root_prefix = self.root.node.prefix();
330        raw_path[0..root_prefix.len()].copy_from_slice(root_prefix);
331        raw_len += root_prefix.len();
332
333        for (byte, ancestor) in node_path {
334            raw_path[raw_len] = *byte;
335            raw_len += 1;
336            let prefix = ancestor.node.prefix();
337            raw_path[raw_len..raw_len + prefix.len()].copy_from_slice(prefix);
338            raw_len += prefix.len();
339        }
340
341        let path = &raw_path[..raw_len];
342
343        // included(12345)
344        //   path
345        //      122 => excluded(0)
346        //      123 => included(4)
347        //      124 => excluded(255)
348        // excluded(12345)
349        //   path
350        //      122 => excluded(0)
351        //      123 => excluded(4)
352        //      124 => excluded(255)
353        let lower = match self.lower_bound {
354            Bound::Unbounded => Bound::Unbounded,
355            Bound::Included(lower) => {
356                if lower.starts_with(path) {
357                    Bound::Included(lower[path.len()])
358                } else if &lower[..path.len()] < path {
359                    Bound::Unbounded
360                } else {
361                    Bound::Excluded(255)
362                }
363            }
364            Bound::Excluded(lower) => {
365                if lower.starts_with(path) {
366                    if path.len() + 1 == K {
367                        Bound::Excluded(lower[path.len()])
368                    } else {
369                        Bound::Included(lower[path.len()])
370                    }
371                } else if &lower[..path.len()] < path {
372                    Bound::Unbounded
373                } else {
374                    Bound::Excluded(255)
375                }
376            }
377        };
378
379        let upper = match self.upper_bound {
380            Bound::Unbounded => Bound::Unbounded,
381            Bound::Included(upper) => {
382                if upper.starts_with(path) {
383                    Bound::Included(upper[path.len()])
384                } else if &upper[..path.len()] > path {
385                    Bound::Unbounded
386                } else {
387                    Bound::Excluded(0)
388                }
389            }
390            Bound::Excluded(upper) => {
391                if upper.starts_with(path) {
392                    if path.len() + 1 == K {
393                        Bound::Excluded(upper[path.len()])
394                    } else {
395                        Bound::Included(upper[path.len()])
396                    }
397                } else if &upper[..path.len()] > path {
398                    Bound::Unbounded
399                } else {
400                    Bound::Excluded(0)
401                }
402            }
403        };
404
405        (lower, upper)
406    }
407}
408
409impl<'a, V, const K: usize> Iterator for Iter<'a, V, K> {
410    type Item = ([u8; K], &'a V);
411
412    fn next(&mut self) -> Option<Self::Item> {
413        if K == 0 {
414            let k: [u8; K] = [0; K];
415            let in_bounds = (self.lower_bound, self.upper_bound).contains(&k);
416            let finished = self.finished_0;
417            let can_return = in_bounds && !finished;
418            self.finished_0 = true;
419            match self.root.node.deref() {
420                NodeRef::Value(ref v) if can_return => return Some(([0; K], v)),
421                NodeRef::Value(_) | NodeRef::None => return None,
422                _ => unreachable!(),
423            }
424        }
425
426        // find next value, populating intermediate
427        // iterators until we reach a leaf.
428        let (vc, v) = loop {
429            if let Some((_c, last)) = self.path.last_mut() {
430                let child_opt = last.children.next();
431                if child_opt.is_none() {
432                    self.path.pop();
433                    continue;
434                }
435                let (c, node) = child_opt.unwrap();
436                let next_c_bound = self.char_bound(true);
437                if !next_c_bound.contains(&c) {
438                    continue;
439                }
440                match node.deref() {
441                    NodeRef::Value(v) => break (c, v),
442                    NodeRef::None => unreachable!(),
443                    _other => {
444                        let iter = node.node_iter();
445                        self.path.push((c, iter))
446                    }
447                }
448            } else {
449                let (c, node) = self.root.children.next()?;
450                let next_c_bound = self.char_bound(true);
451                if !next_c_bound.contains(&c) {
452                    continue;
453                }
454
455                match node.deref() {
456                    NodeRef::Value(v) => break (c, v),
457                    NodeRef::None => unreachable!(),
458                    _other => {
459                        let iter = node.node_iter();
460                        self.path.push((c, iter))
461                    }
462                }
463            }
464        };
465
466        let mut k = [0; K];
467        let mut written = 0;
468        let root_prefix = self.root.node.prefix();
469        k[..root_prefix.len()].copy_from_slice(root_prefix);
470        written += root_prefix.len();
471
472        for (c, node_iter) in &self.path {
473            k[written] = *c;
474            written += 1;
475
476            let node_prefix = node_iter.node.prefix();
477
478            k[written..written + node_prefix.len()].copy_from_slice(node_prefix);
479            written += node_prefix.len();
480        }
481
482        k[written] = vc;
483        written += 1;
484
485        assert_eq!(written, K);
486
487        Some((k, v))
488    }
489}
490
491impl<'a, V, const K: usize> DoubleEndedIterator for Iter<'a, V, K> {
492    fn next_back(&mut self) -> Option<Self::Item> {
493        if K == 0 {
494            let k: [u8; K] = [0; K];
495            let in_bounds = (self.lower_bound, self.upper_bound).contains(&k);
496            let finished = self.finished_0;
497            let can_return = in_bounds && !finished;
498            self.finished_0 = true;
499            match self.root.node.deref() {
500                NodeRef::Value(ref v) if can_return => return Some(([0; K], v)),
501                NodeRef::Value(_) | NodeRef::None => return None,
502                _ => unreachable!(),
503            }
504        }
505
506        // find next value, populating intermediate
507        // iterators until we reach a leaf.
508        let (vc, v) = loop {
509            if let Some((_c, last)) = self.rev_path.last_mut() {
510                let child_opt = last.children.next_back();
511                if child_opt.is_none() {
512                    self.rev_path.pop();
513                    continue;
514                }
515                let (c, node) = child_opt.unwrap();
516                let next_c_bound = self.char_bound(false);
517                if !next_c_bound.contains(&c) {
518                    continue;
519                }
520
521                match node.deref() {
522                    NodeRef::Value(v) => break (c, v),
523                    NodeRef::None => unreachable!(),
524                    _other => {
525                        let iter = node.node_iter();
526                        self.rev_path.push((c, iter))
527                    }
528                }
529            } else {
530                let (c, node) = self.root.children.next_back()?;
531                let next_c_bound = self.char_bound(false);
532                if !next_c_bound.contains(&c) {
533                    continue;
534                }
535
536                match node.deref() {
537                    NodeRef::Value(v) => break (c, v),
538                    NodeRef::None => unreachable!(),
539                    _other => {
540                        let iter = node.node_iter();
541                        self.rev_path.push((c, iter))
542                    }
543                }
544            }
545        };
546
547        let mut k = [0; K];
548        let mut written = 0;
549        let root_prefix = self.root.node.prefix();
550        k[..root_prefix.len()].copy_from_slice(root_prefix);
551        written += root_prefix.len();
552
553        for (c, node_iter) in &self.rev_path {
554            k[written] = *c;
555            written += 1;
556
557            let node_prefix = node_iter.node.prefix();
558
559            k[written..written + node_prefix.len()].copy_from_slice(node_prefix);
560            written += node_prefix.len();
561        }
562
563        k[written] = vc;
564        written += 1;
565
566        assert_eq!(written, K);
567
568        Some((k, v))
569    }
570}
571
572struct NodeIter<'a, V> {
573    node: &'a Node<V>,
574    children: Box<dyn 'a + DoubleEndedIterator<Item = (u8, &'a Node<V>)>>,
575}
576
577#[derive(Debug, Default, Clone, Copy)]
578struct Header {
579    children: u16,
580    path: [u8; MAX_PATH_COMPRESSION_BYTES],
581    path_len: u8,
582}
583
584struct Node<V>(usize, PhantomData<V>);
585
586impl<V: Clone> Clone for Node<V> {
587    fn clone(&self) -> Node<V> {
588        match self.deref() {
589            NodeRef::Node1(n1) => Node::node1(Box::new(n1.clone())),
590            NodeRef::Node4(n4) => Node::node4(Box::new(n4.clone())),
591            NodeRef::Node16(n16) => Node::node16(Box::new(n16.clone())),
592            NodeRef::Node48(n48) => Node::node48(Box::new(n48.clone())),
593            NodeRef::Node256(n256) => Node::node256(Box::new(n256.clone())),
594            NodeRef::None => Node::default(),
595            NodeRef::Value(v) => Node::value(v.clone()),
596        }
597    }
598}
599
600impl<V: fmt::Debug> fmt::Debug for Node<V> {
601    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
602        f.debug_struct("Node")
603            .field("header", self.header())
604            .field("inner", &self.deref())
605            .finish()?;
606        Ok(())
607    }
608}
609
610impl<V> Drop for Node<V> {
611    fn drop(&mut self) {
612        match self.0 & TAG_MASK {
613            TAG_NONE => {}
614            TAG_VALUE => {
615                if size_of::<V>() > 0 {
616                    let ptr: *mut MinAlign<V> = if size_of::<V>() > 0 {
617                        (self.0 & PTR_MASK) as *mut MinAlign<V>
618                    } else {
619                        std::ptr::NonNull::dangling().as_ptr()
620                    };
621                    drop(unsafe { Box::from_raw(ptr) });
622                }
623            }
624            TAG_1 => {
625                let ptr: *mut Node1<V> = (self.0 & PTR_MASK) as *mut Node1<V>;
626                drop(unsafe { Box::from_raw(ptr) });
627            }
628            TAG_4 => {
629                let ptr: *mut Node4<V> = (self.0 & PTR_MASK) as *mut Node4<V>;
630                drop(unsafe { Box::from_raw(ptr) });
631            }
632            TAG_16 => {
633                let ptr: *mut Node16<V> = (self.0 & PTR_MASK) as *mut Node16<V>;
634                drop(unsafe { Box::from_raw(ptr) });
635            }
636            TAG_48 => {
637                let ptr: *mut Node48<V> = (self.0 & PTR_MASK) as *mut Node48<V>;
638                drop(unsafe { Box::from_raw(ptr) });
639            }
640            TAG_256 => {
641                let ptr: *mut Node256<V> = (self.0 & PTR_MASK) as *mut Node256<V>;
642                drop(unsafe { Box::from_raw(ptr) });
643            }
644            _ => unreachable!(),
645        }
646    }
647}
648
649const TAG_NONE: usize = 0b000;
650const TAG_VALUE: usize = 0b001;
651const TAG_1: usize = 0b010;
652const TAG_4: usize = 0b011;
653const TAG_16: usize = 0b100;
654const TAG_48: usize = 0b101;
655const TAG_256: usize = 0b110;
656const TAG_MASK: usize = 0b111;
657const PTR_MASK: usize = usize::MAX - TAG_MASK;
658
659#[derive(Debug)]
660enum NodeRef<'a, V> {
661    None,
662    Value(&'a V),
663    Node1(&'a Node1<V>),
664    Node4(&'a Node4<V>),
665    Node16(&'a Node16<V>),
666    Node48(&'a Node48<V>),
667    Node256(&'a Node256<V>),
668}
669
670enum NodeMut<'a, V> {
671    None,
672    Value(&'a mut V),
673    Node1(&'a mut Node1<V>),
674    Node4(&'a mut Node4<V>),
675    Node16(&'a mut Node16<V>),
676    Node48(&'a mut Node48<V>),
677    Node256(&'a mut Node256<V>),
678}
679
680impl<V> Default for Node<V> {
681    fn default() -> Node<V> {
682        Node::none()
683    }
684}
685
686impl<V> Node<V> {
687    const fn none() -> Node<V> {
688        Node(TAG_NONE, PhantomData)
689    }
690
691    fn node1(n1: Box<Node1<V>>) -> Node<V> {
692        let ptr: *mut Node1<V> = Box::into_raw(n1);
693        let us = ptr as usize;
694        assert_eq!(us & TAG_1, 0);
695        Node(us | TAG_1, PhantomData)
696    }
697
698    fn node4(n4: Box<Node4<V>>) -> Node<V> {
699        let ptr: *mut Node4<V> = Box::into_raw(n4);
700        let us = ptr as usize;
701        assert_eq!(us & TAG_4, 0);
702        Node(us | TAG_4, PhantomData)
703    }
704
705    fn node16(n16: Box<Node16<V>>) -> Node<V> {
706        let ptr: *mut Node16<V> = Box::into_raw(n16);
707        let us = ptr as usize;
708        assert_eq!(us & TAG_16, 0);
709        Node(us | TAG_16, PhantomData)
710    }
711
712    fn node48(n48: Box<Node48<V>>) -> Node<V> {
713        let ptr: *mut Node48<V> = Box::into_raw(n48);
714        let us = ptr as usize;
715        assert_eq!(us & TAG_48, 0);
716        Node(us | TAG_48, PhantomData)
717    }
718
719    fn node256(n256: Box<Node256<V>>) -> Node<V> {
720        let ptr: *mut Node256<V> = Box::into_raw(n256);
721        let us = ptr as usize;
722        assert_eq!(us & TAG_256, 0);
723        Node(us | TAG_256, PhantomData)
724    }
725
726    fn value(value: V) -> Node<V> {
727        let bx = Box::new(MinAlign(value));
728        let ptr: *mut MinAlign<V> = Box::into_raw(bx);
729        let us = ptr as usize;
730        if size_of::<V>() > 0 {
731            assert_eq!(us & TAG_VALUE, 0);
732        } else {
733            assert_eq!(ptr, std::ptr::NonNull::dangling().as_ptr());
734        }
735        Node(us | TAG_VALUE, PhantomData)
736    }
737
738    fn take(&mut self) -> Option<V> {
739        let us = self.0;
740        self.0 = 0;
741
742        match us & TAG_MASK {
743            TAG_NONE => None,
744            TAG_VALUE => {
745                let ptr: *mut MinAlign<V> = if size_of::<V>() > 0 {
746                    (us & PTR_MASK) as *mut MinAlign<V>
747                } else {
748                    std::ptr::NonNull::dangling().as_ptr()
749                };
750                let boxed: Box<MinAlign<V>> = unsafe { Box::from_raw(ptr) };
751                Some(boxed.0)
752            }
753            _ => unreachable!(),
754        }
755    }
756
757    const fn deref(&self) -> NodeRef<'_, V> {
758        match self.0 & TAG_MASK {
759            TAG_NONE => NodeRef::None,
760            TAG_VALUE => {
761                let ptr: *const MinAlign<V> = if size_of::<V>() > 0 {
762                    (self.0 & PTR_MASK) as *const MinAlign<V>
763                } else {
764                    std::ptr::NonNull::dangling().as_ptr()
765                };
766                let reference: &V = unsafe { &(*ptr).0 };
767                NodeRef::Value(reference)
768            }
769            TAG_1 => {
770                let ptr: *const Node1<V> = (self.0 & PTR_MASK) as *const Node1<V>;
771                let reference: &Node1<V> = unsafe { &*ptr };
772                NodeRef::Node1(reference)
773            }
774            TAG_4 => {
775                let ptr: *const Node4<V> = (self.0 & PTR_MASK) as *const Node4<V>;
776                let reference: &Node4<V> = unsafe { &*ptr };
777                NodeRef::Node4(reference)
778            }
779            TAG_16 => {
780                let ptr: *const Node16<V> = (self.0 & PTR_MASK) as *const Node16<V>;
781                let reference: &Node16<V> = unsafe { &*ptr };
782                NodeRef::Node16(reference)
783            }
784            TAG_48 => {
785                let ptr: *const Node48<V> = (self.0 & PTR_MASK) as *const Node48<V>;
786                let reference: &Node48<V> = unsafe { &*ptr };
787                NodeRef::Node48(reference)
788            }
789            TAG_256 => {
790                let ptr: *const Node256<V> = (self.0 & PTR_MASK) as *const Node256<V>;
791                let reference: &Node256<V> = unsafe { &*ptr };
792                NodeRef::Node256(reference)
793            }
794            _ => unreachable!(),
795        }
796    }
797
798    fn deref_mut(&mut self) -> NodeMut<'_, V> {
799        match self.0 & TAG_MASK {
800            TAG_NONE => NodeMut::None,
801            TAG_VALUE => {
802                let ptr: *mut MinAlign<V> = if size_of::<V>() > 0 {
803                    (self.0 & PTR_MASK) as *mut MinAlign<V>
804                } else {
805                    std::ptr::NonNull::dangling().as_ptr()
806                };
807                let reference: &mut V = unsafe { &mut (*ptr).0 };
808                NodeMut::Value(reference)
809            }
810            TAG_1 => {
811                let ptr: *mut Node1<V> = (self.0 & PTR_MASK) as *mut Node1<V>;
812                let reference: &mut Node1<V> = unsafe { &mut *ptr };
813                NodeMut::Node1(reference)
814            }
815            TAG_4 => {
816                let ptr: *mut Node4<V> = (self.0 & PTR_MASK) as *mut Node4<V>;
817                let reference: &mut Node4<V> = unsafe { &mut *ptr };
818                NodeMut::Node4(reference)
819            }
820            TAG_16 => {
821                let ptr: *mut Node16<V> = (self.0 & PTR_MASK) as *mut Node16<V>;
822                let reference: &mut Node16<V> = unsafe { &mut *ptr };
823                NodeMut::Node16(reference)
824            }
825            TAG_48 => {
826                let ptr: *mut Node48<V> = (self.0 & PTR_MASK) as *mut Node48<V>;
827                let reference: &mut Node48<V> = unsafe { &mut *ptr };
828                NodeMut::Node48(reference)
829            }
830            TAG_256 => {
831                let ptr: *mut Node256<V> = (self.0 & PTR_MASK) as *mut Node256<V>;
832                let reference: &mut Node256<V> = unsafe { &mut *ptr };
833                NodeMut::Node256(reference)
834            }
835            _ => unreachable!(),
836        }
837    }
838
839    // returns true if this node went from Node4 to None
840    fn prune(&mut self, partial_path: &[u8]) -> bool {
841        let prefix = self.prefix();
842
843        assert!(partial_path.starts_with(prefix));
844
845        if partial_path.len() > prefix.len() + 1 {
846            let byte = partial_path[prefix.len()];
847            let subpath = &partial_path[prefix.len() + 1..];
848
849            let (_, child) = self.child_mut(byte, false, false).expect(
850                "prune may only be called with \
851                freshly removed keys with a full \
852                ancestor chain still in-place.",
853            );
854
855            let child_shrunk = child.prune(subpath);
856            if child_shrunk {
857                let children: &mut u16 = &mut self.header_mut().children;
858                *children = children.checked_sub(1).unwrap();
859
860                if let NodeMut::Node48(n48) = self.deref_mut() {
861                    n48.child_index[byte as usize] = 255;
862                }
863            }
864        }
865
866        self.shrink_to_fit()
867    }
868
869    fn truncate_prefix(&mut self, partial_path: &[u8]) {
870        // println!("truncating prefix");
871        // expand path at shared prefix
872        //println!("chopping off a prefix at node {:?} since our partial path is {:?}", cursor.header(), partial_path);
873        let prefix = self.prefix();
874
875        let shared_bytes = partial_path
876            .iter()
877            .zip(prefix.iter())
878            .take_while(|(a, b)| a == b)
879            .count();
880
881        // println!("truncated node has path of len {} with a reduction of {}", shared_bytes, prefix.len() - shared_bytes);
882        let mut new_node4: Box<Node4<V>> = Box::default();
883        new_node4.header.path[..shared_bytes].copy_from_slice(&prefix[..shared_bytes]);
884        new_node4.header.path_len = u8::try_from(shared_bytes).unwrap();
885
886        let new_node = Node::node4(new_node4);
887
888        assert!(prefix.starts_with(new_node.prefix()));
889
890        let mut old_cursor = std::mem::replace(self, new_node);
891
892        let old_cursor_header = old_cursor.header_mut();
893        let old_cursor_new_child_byte = old_cursor_header.path[shared_bytes];
894
895        // we add +1 because we must account for the extra byte
896        // reduced from the node's fan-out itself.
897        old_cursor_header.path.rotate_left(shared_bytes + 1);
898        old_cursor_header.path_len = old_cursor_header
899            .path_len
900            .checked_sub(u8::try_from(shared_bytes + 1).unwrap())
901            .unwrap();
902
903        let (_, child) = self
904            .child_mut(old_cursor_new_child_byte, true, false)
905            .unwrap();
906        *child = old_cursor;
907        child.assert_size();
908
909        self.header_mut().children = 1;
910    }
911
912    const fn is_none(&self) -> bool {
913        self.0 == TAG_NONE
914    }
915
916    fn assert_size(&self) {
917        debug_assert_eq!(
918            {
919                let slots: &[Node<V>] = match self.deref() {
920                    NodeRef::Node1(_) => {
921                        debug_assert_eq!(self.len(), 1);
922                        return;
923                    }
924                    NodeRef::Node4(n4) => &n4.slots,
925                    NodeRef::Node16(n16) => &n16.slots,
926                    NodeRef::Node48(n48) => &n48.slots,
927                    NodeRef::Node256(n256) => &n256.slots,
928                    _ => &[],
929                };
930                slots.iter().filter(|s| !s.is_none()).count()
931            },
932            self.len(),
933        )
934    }
935
936    const fn is_full(&self) -> bool {
937        match self.deref() {
938            NodeRef::Node1(_) => 1 == self.len(),
939            NodeRef::Node4(_) => 4 == self.len(),
940            NodeRef::Node16(_) => 16 == self.len(),
941            NodeRef::Node48(_) => 48 == self.len(),
942            NodeRef::Node256(_) => 256 == self.len(),
943            _ => unreachable!(),
944        }
945    }
946
947    const fn len(&self) -> usize {
948        self.header().children as usize
949    }
950
951    const fn header(&self) -> &Header {
952        match self.deref() {
953            NodeRef::Node1(n1) => &n1.header,
954            NodeRef::Node4(n4) => &n4.header,
955            NodeRef::Node16(n16) => &n16.header,
956            NodeRef::Node48(n48) => &n48.header,
957            NodeRef::Node256(n256) => &n256.header,
958            NodeRef::None => &NONE_HEADER,
959            NodeRef::Value(_) => &VALUE_HEADER,
960        }
961    }
962
963    fn header_mut(&mut self) -> &mut Header {
964        match self.deref_mut() {
965            NodeMut::Node1(n1) => &mut n1.header,
966            NodeMut::Node4(n4) => &mut n4.header,
967            NodeMut::Node16(n16) => &mut n16.header,
968            NodeMut::Node48(n48) => &mut n48.header,
969            NodeMut::Node256(n256) => &mut n256.header,
970            _ => unreachable!(),
971        }
972    }
973
974    fn prefix(&self) -> &[u8] {
975        let header = self.header();
976        &header.path[..header.path_len as usize]
977    }
978
979    fn child(&self, byte: u8) -> Option<&Node<V>> {
980        match self.deref() {
981            NodeRef::Node1(n1) => n1.child(byte),
982            NodeRef::Node4(n4) => n4.child(byte),
983            NodeRef::Node16(n16) => n16.child(byte),
984            NodeRef::Node48(n48) => n48.child(byte),
985            NodeRef::Node256(n256) => n256.child(byte),
986            NodeRef::None => None,
987            NodeRef::Value(_) => unreachable!(),
988        }
989    }
990
991    fn child_mut(
992        &mut self,
993        byte: u8,
994        is_add: bool,
995        clear_child_index: bool,
996    ) -> Option<(&mut u16, &mut Node<V>)> {
997        // TODO this is gross
998        if self.child(byte).is_none() {
999            if !is_add {
1000                return None;
1001            }
1002            if self.is_full() {
1003                self.upgrade()
1004            }
1005        }
1006
1007        Some(match self.deref_mut() {
1008            NodeMut::Node1(n1) => n1.child_mut(byte),
1009            NodeMut::Node4(n4) => n4.child_mut(byte),
1010            NodeMut::Node16(n16) => n16.child_mut(byte),
1011            NodeMut::Node48(n48) => n48.child_mut(byte, clear_child_index),
1012            NodeMut::Node256(n256) => n256.child_mut(byte),
1013            NodeMut::None => unreachable!(),
1014            NodeMut::Value(_) => unreachable!(),
1015        })
1016    }
1017
1018    fn should_shrink(&self) -> bool {
1019        match (self.deref(), self.len()) {
1020            (NodeRef::Node1(_), 0)
1021            | (NodeRef::Node4(_), 1)
1022            | (NodeRef::Node16(_), 4)
1023            | (NodeRef::Node48(_), 16)
1024            | (NodeRef::Node256(_), 48) => true,
1025            (_, _) => false,
1026        }
1027    }
1028
1029    fn shrink_to_fit(&mut self) -> bool {
1030        if !self.should_shrink() {
1031            return false;
1032        }
1033
1034        let old_header = *self.header();
1035        let children = old_header.children;
1036
1037        let mut dropped = false;
1038        let mut swapped = std::mem::take(self);
1039
1040        *self = match (swapped.deref_mut(), children) {
1041            (NodeMut::Node1(_), 0) => {
1042                dropped = true;
1043                Node::none()
1044            }
1045            (NodeMut::Node4(n4), 1) => Node::node1(n4.downgrade()),
1046            (NodeMut::Node16(n16), 4) => Node::node4(n16.downgrade()),
1047            (NodeMut::Node48(n48), 16) => Node::node16(n48.downgrade()),
1048            (NodeMut::Node256(n256), 48) => Node::node48(n256.downgrade()),
1049            (_, _) => unreachable!(),
1050        };
1051
1052        if !dropped {
1053            *self.header_mut() = old_header;
1054        }
1055
1056        dropped
1057    }
1058
1059    fn upgrade(&mut self) {
1060        let old_header = *self.header();
1061        let mut swapped = std::mem::take(self);
1062        *self = match swapped.deref_mut() {
1063            NodeMut::Node1(n1) => Node::node4(n1.upgrade()),
1064            NodeMut::Node4(n4) => Node::node16(n4.upgrade()),
1065            NodeMut::Node16(n16) => Node::node48(n16.upgrade()),
1066            NodeMut::Node48(n48) => Node::node256(n48.upgrade()),
1067            NodeMut::Node256(_) => unreachable!(),
1068            NodeMut::None => unreachable!(),
1069            NodeMut::Value(_) => unreachable!(),
1070        };
1071        *self.header_mut() = old_header;
1072    }
1073
1074    fn node_iter<'a>(&'a self) -> NodeIter<'a, V> {
1075        let children: Box<dyn 'a + DoubleEndedIterator<Item = (u8, &'a Node<V>)>> =
1076            match self.deref() {
1077                NodeRef::Node1(n1) => Box::new(n1.iter()),
1078                NodeRef::Node4(n4) => Box::new(n4.iter()),
1079                NodeRef::Node16(n16) => Box::new(n16.iter()),
1080                NodeRef::Node48(n48) => Box::new(n48.iter()),
1081                NodeRef::Node256(n256) => Box::new(n256.iter()),
1082
1083                // this is only an iterator over nodes, not leaf values
1084                NodeRef::None => Box::new([].into_iter()),
1085                NodeRef::Value(_) => Box::new([].into_iter()),
1086            };
1087
1088        NodeIter {
1089            node: self,
1090            children,
1091        }
1092    }
1093}
1094
1095#[derive(Debug, Clone)]
1096struct Node1<V> {
1097    slot: Node<V>,
1098    header: Header,
1099    key: u8,
1100}
1101
1102impl<V> Default for Node1<V> {
1103    fn default() -> Node1<V> {
1104        Node1 {
1105            header: Default::default(),
1106            key: 0,
1107            slot: Node::default(),
1108        }
1109    }
1110}
1111
1112impl<V> Node1<V> {
1113    fn iter(&self) -> impl DoubleEndedIterator<Item = (u8, &Node<V>)> {
1114        std::iter::once((self.key, &self.slot))
1115    }
1116
1117    const fn child(&self, byte: u8) -> Option<&Node<V>> {
1118        if self.key == byte && !self.slot.is_none() {
1119            Some(&self.slot)
1120        } else {
1121            None
1122        }
1123    }
1124
1125    fn child_mut(&mut self, byte: u8) -> (&mut u16, &mut Node<V>) {
1126        assert!(byte == self.key || self.slot.is_none());
1127        self.key = byte;
1128        (&mut self.header.children, &mut self.slot)
1129    }
1130
1131    fn upgrade(&mut self) -> Box<Node4<V>> {
1132        let mut n4: Box<Node4<V>> = Box::default();
1133        n4.keys[0] = self.key;
1134        std::mem::swap(&mut self.slot, &mut n4.slots[0]);
1135        n4
1136    }
1137}
1138
1139#[derive(Debug, Clone)]
1140struct Node4<V> {
1141    header: Header,
1142    keys: [u8; 4],
1143    slots: [Node<V>; 4],
1144}
1145
1146impl<V> Default for Node4<V> {
1147    fn default() -> Node4<V> {
1148        Node4 {
1149            header: Default::default(),
1150            keys: [255; 4],
1151            slots: [Node::none(), Node::none(), Node::none(), Node::none()],
1152        }
1153    }
1154}
1155
1156impl<V> Node4<V> {
1157    fn iter(&self) -> impl DoubleEndedIterator<Item = (u8, &Node<V>)> {
1158        let mut pairs: [(u8, &Node<V>); 4] = [
1159            (self.keys[0], &self.slots[0]),
1160            (self.keys[1], &self.slots[1]),
1161            (self.keys[2], &self.slots[2]),
1162            (self.keys[3], &self.slots[3]),
1163        ];
1164
1165        pairs.sort_unstable_by_key(|(k, _)| *k);
1166
1167        pairs.into_iter().filter(|(_, n)| !n.is_none())
1168    }
1169
1170    fn free_slot(&self) -> Option<usize> {
1171        self.slots.iter().position(Node::is_none)
1172    }
1173
1174    fn child(&self, byte: u8) -> Option<&Node<V>> {
1175        for idx in 0..4 {
1176            if self.keys[idx] == byte && !self.slots[idx].is_none() {
1177                return Some(&self.slots[idx]);
1178            }
1179        }
1180        None
1181    }
1182
1183    fn child_mut(&mut self, byte: u8) -> (&mut u16, &mut Node<V>) {
1184        let idx_opt = self.keys.iter().position(|i| *i == byte).and_then(|idx| {
1185            if !self.slots[idx].is_none() {
1186                Some(idx)
1187            } else {
1188                None
1189            }
1190        });
1191        if let Some(idx) = idx_opt {
1192            (&mut self.header.children, &mut self.slots[idx])
1193        } else {
1194            let free_slot = self.free_slot().unwrap();
1195            self.keys[free_slot] = byte;
1196            (&mut self.header.children, &mut self.slots[free_slot])
1197        }
1198    }
1199
1200    fn upgrade(&mut self) -> Box<Node16<V>> {
1201        let mut n16: Box<Node16<V>> = Box::default();
1202        for (slot, byte) in self.keys.iter().enumerate() {
1203            std::mem::swap(&mut self.slots[slot], &mut n16.slots[slot]);
1204            n16.keys[slot] = *byte;
1205        }
1206        n16
1207    }
1208
1209    fn downgrade(&mut self) -> Box<Node1<V>> {
1210        let mut n1: Box<Node1<V>> = Box::default();
1211        let mut dst_idx = 0;
1212
1213        for (slot, byte) in self.keys.iter().enumerate() {
1214            if !self.slots[slot].is_none() {
1215                std::mem::swap(&mut self.slots[slot], &mut n1.slot);
1216                n1.key = *byte;
1217                dst_idx += 1;
1218            }
1219        }
1220
1221        assert_eq!(dst_idx, 1);
1222
1223        n1
1224    }
1225}
1226
1227#[derive(Debug, Clone)]
1228struct Node16<V> {
1229    header: Header,
1230    keys: [u8; 16],
1231    slots: [Node<V>; 16],
1232}
1233
1234impl<V> Default for Node16<V> {
1235    fn default() -> Node16<V> {
1236        Node16 {
1237            header: Default::default(),
1238            keys: [255; 16],
1239            slots: [
1240                Node::none(),
1241                Node::none(),
1242                Node::none(),
1243                Node::none(),
1244                Node::none(),
1245                Node::none(),
1246                Node::none(),
1247                Node::none(),
1248                Node::none(),
1249                Node::none(),
1250                Node::none(),
1251                Node::none(),
1252                Node::none(),
1253                Node::none(),
1254                Node::none(),
1255                Node::none(),
1256            ],
1257        }
1258    }
1259}
1260
1261impl<V> Node16<V> {
1262    fn iter(&self) -> impl DoubleEndedIterator<Item = (u8, &Node<V>)> {
1263        let mut pairs: [(u8, &Node<V>); 16] = [
1264            (self.keys[0], &self.slots[0]),
1265            (self.keys[1], &self.slots[1]),
1266            (self.keys[2], &self.slots[2]),
1267            (self.keys[3], &self.slots[3]),
1268            (self.keys[4], &self.slots[4]),
1269            (self.keys[5], &self.slots[5]),
1270            (self.keys[6], &self.slots[6]),
1271            (self.keys[7], &self.slots[7]),
1272            (self.keys[8], &self.slots[8]),
1273            (self.keys[9], &self.slots[9]),
1274            (self.keys[10], &self.slots[10]),
1275            (self.keys[11], &self.slots[11]),
1276            (self.keys[12], &self.slots[12]),
1277            (self.keys[13], &self.slots[13]),
1278            (self.keys[14], &self.slots[14]),
1279            (self.keys[15], &self.slots[15]),
1280        ];
1281
1282        pairs.sort_unstable_by_key(|(k, _)| *k);
1283
1284        pairs.into_iter().filter(|(_, n)| !n.is_none())
1285    }
1286
1287    fn free_slot(&self) -> Option<usize> {
1288        self.slots.iter().position(Node::is_none)
1289    }
1290
1291    fn child(&self, byte: u8) -> Option<&Node<V>> {
1292        for idx in 0..16 {
1293            if self.keys[idx] == byte && !self.slots[idx].is_none() {
1294                return Some(&self.slots[idx]);
1295            }
1296        }
1297        None
1298    }
1299
1300    fn child_mut(&mut self, byte: u8) -> (&mut u16, &mut Node<V>) {
1301        let idx_opt = self.keys.iter().position(|i| *i == byte).and_then(|idx| {
1302            if !self.slots[idx].is_none() {
1303                Some(idx)
1304            } else {
1305                None
1306            }
1307        });
1308        if let Some(idx) = idx_opt {
1309            (&mut self.header.children, &mut self.slots[idx])
1310        } else {
1311            let free_slot = self.free_slot().unwrap();
1312            self.keys[free_slot] = byte;
1313            (&mut self.header.children, &mut self.slots[free_slot])
1314        }
1315    }
1316
1317    fn upgrade(&mut self) -> Box<Node48<V>> {
1318        let mut n48: Box<Node48<V>> = Box::default();
1319        for (slot, byte) in self.keys.iter().enumerate() {
1320            if !self.slots[slot].is_none() {
1321                std::mem::swap(&mut self.slots[slot], &mut n48.slots[slot]);
1322                assert_eq!(n48.child_index[*byte as usize], 255);
1323                n48.child_index[*byte as usize] = u8::try_from(slot).unwrap();
1324            }
1325        }
1326        n48
1327    }
1328
1329    fn downgrade(&mut self) -> Box<Node4<V>> {
1330        let mut n4: Box<Node4<V>> = Box::default();
1331        let mut dst_idx = 0;
1332
1333        for (slot, byte) in self.keys.iter().enumerate() {
1334            if !self.slots[slot].is_none() {
1335                std::mem::swap(&mut self.slots[slot], &mut n4.slots[dst_idx]);
1336                n4.keys[dst_idx] = *byte;
1337                dst_idx += 1;
1338            }
1339        }
1340
1341        assert_eq!(dst_idx, 4);
1342
1343        n4
1344    }
1345}
1346
1347#[derive(Debug, Clone)]
1348struct Node48<V> {
1349    header: Header,
1350    child_index: [u8; 256],
1351    slots: [Node<V>; 48],
1352}
1353
1354impl<V> Default for Node48<V> {
1355    fn default() -> Node48<V> {
1356        Node48 {
1357            header: Default::default(),
1358            child_index: [255; 256],
1359            slots: [
1360                Node::none(),
1361                Node::none(),
1362                Node::none(),
1363                Node::none(),
1364                Node::none(),
1365                Node::none(),
1366                Node::none(),
1367                Node::none(),
1368                Node::none(),
1369                Node::none(),
1370                Node::none(),
1371                Node::none(),
1372                Node::none(),
1373                Node::none(),
1374                Node::none(),
1375                Node::none(),
1376                Node::none(),
1377                Node::none(),
1378                Node::none(),
1379                Node::none(),
1380                Node::none(),
1381                Node::none(),
1382                Node::none(),
1383                Node::none(),
1384                Node::none(),
1385                Node::none(),
1386                Node::none(),
1387                Node::none(),
1388                Node::none(),
1389                Node::none(),
1390                Node::none(),
1391                Node::none(),
1392                Node::none(),
1393                Node::none(),
1394                Node::none(),
1395                Node::none(),
1396                Node::none(),
1397                Node::none(),
1398                Node::none(),
1399                Node::none(),
1400                Node::none(),
1401                Node::none(),
1402                Node::none(),
1403                Node::none(),
1404                Node::none(),
1405                Node::none(),
1406                Node::none(),
1407                Node::none(),
1408            ],
1409        }
1410    }
1411}
1412
1413impl<V> Node48<V> {
1414    fn iter(&self) -> impl DoubleEndedIterator<Item = (u8, &Node<V>)> {
1415        self.child_index
1416            .iter()
1417            .enumerate()
1418            .filter(|(_, i)| **i != 255 && !self.slots[**i as usize].is_none())
1419            .map(|(c, i)| (u8::try_from(c).unwrap(), &self.slots[*i as usize]))
1420    }
1421
1422    fn free_slot(&self) -> Option<usize> {
1423        self.slots.iter().position(Node::is_none)
1424    }
1425
1426    const fn child(&self, byte: u8) -> Option<&Node<V>> {
1427        let idx = self.child_index[byte as usize];
1428        if idx == 255 || self.slots[idx as usize].is_none() {
1429            None
1430        } else {
1431            Some(&self.slots[idx as usize])
1432        }
1433    }
1434
1435    fn child_mut(&mut self, byte: u8, clear_child_index: bool) -> (&mut u16, &mut Node<V>) {
1436        let idx = self.child_index[byte as usize];
1437
1438        if idx == 255 {
1439            let free_slot = self.free_slot().unwrap();
1440            if !clear_child_index {
1441                self.child_index[byte as usize] = u8::try_from(free_slot).unwrap();
1442            }
1443            (&mut self.header.children, &mut self.slots[free_slot])
1444        } else {
1445            if clear_child_index {
1446                self.child_index[byte as usize] = 255;
1447            }
1448            (&mut self.header.children, &mut self.slots[idx as usize])
1449        }
1450    }
1451
1452    fn upgrade(&mut self) -> Box<Node256<V>> {
1453        let mut n256: Box<Node256<V>> = Box::default();
1454
1455        for (byte, idx) in self.child_index.iter().enumerate() {
1456            if *idx != 255 {
1457                assert!(!self.slots[*idx as usize].is_none());
1458                std::mem::swap(&mut n256.slots[byte], &mut self.slots[*idx as usize]);
1459            }
1460        }
1461
1462        n256
1463    }
1464
1465    fn downgrade(&mut self) -> Box<Node16<V>> {
1466        let mut n16: Box<Node16<V>> = Box::default();
1467        let mut dst_idx = 0;
1468
1469        for (byte, idx) in self.child_index.iter().enumerate() {
1470            if *idx != 255 {
1471                assert!(!self.slots[*idx as usize].is_none());
1472                std::mem::swap(&mut self.slots[*idx as usize], &mut n16.slots[dst_idx]);
1473                n16.keys[dst_idx] = u8::try_from(byte).unwrap();
1474                dst_idx += 1;
1475            }
1476        }
1477
1478        assert_eq!(dst_idx, 16);
1479
1480        n16
1481    }
1482}
1483
1484#[derive(Debug, Clone)]
1485struct Node256<V> {
1486    header: Header,
1487    slots: [Node<V>; 256],
1488}
1489
1490impl<V> Node256<V> {
1491    fn iter(&self) -> impl DoubleEndedIterator<Item = (u8, &Node<V>)> {
1492        self.slots
1493            .iter()
1494            .enumerate()
1495            .filter(move |(_, slot)| !slot.is_none())
1496            .map(|(c, slot)| (u8::try_from(c).unwrap(), slot))
1497    }
1498
1499    const fn child(&self, byte: u8) -> Option<&Node<V>> {
1500        if self.slots[byte as usize].is_none() {
1501            None
1502        } else {
1503            Some(&self.slots[byte as usize])
1504        }
1505    }
1506
1507    fn child_mut(&mut self, byte: u8) -> (&mut u16, &mut Node<V>) {
1508        let slot = &mut self.slots[byte as usize];
1509        (&mut self.header.children, slot)
1510    }
1511
1512    fn downgrade(&mut self) -> Box<Node48<V>> {
1513        let mut n48: Box<Node48<V>> = Box::default();
1514        let mut dst_idx = 0;
1515
1516        for (byte, slot) in self.slots.iter_mut().enumerate() {
1517            if !slot.is_none() {
1518                std::mem::swap(slot, &mut n48.slots[dst_idx]);
1519                n48.child_index[byte] = u8::try_from(dst_idx).unwrap();
1520                dst_idx += 1;
1521            }
1522        }
1523
1524        assert_eq!(dst_idx, 48);
1525
1526        n48
1527    }
1528}
1529
1530impl<V> Default for Node256<V> {
1531    fn default() -> Node256<V> {
1532        Node256 {
1533            header: Default::default(),
1534            slots: [
1535                Node::none(),
1536                Node::none(),
1537                Node::none(),
1538                Node::none(),
1539                Node::none(),
1540                Node::none(),
1541                Node::none(),
1542                Node::none(),
1543                Node::none(),
1544                Node::none(),
1545                Node::none(),
1546                Node::none(),
1547                Node::none(),
1548                Node::none(),
1549                Node::none(),
1550                Node::none(),
1551                Node::none(),
1552                Node::none(),
1553                Node::none(),
1554                Node::none(),
1555                Node::none(),
1556                Node::none(),
1557                Node::none(),
1558                Node::none(),
1559                Node::none(),
1560                Node::none(),
1561                Node::none(),
1562                Node::none(),
1563                Node::none(),
1564                Node::none(),
1565                Node::none(),
1566                Node::none(),
1567                Node::none(),
1568                Node::none(),
1569                Node::none(),
1570                Node::none(),
1571                Node::none(),
1572                Node::none(),
1573                Node::none(),
1574                Node::none(),
1575                Node::none(),
1576                Node::none(),
1577                Node::none(),
1578                Node::none(),
1579                Node::none(),
1580                Node::none(),
1581                Node::none(),
1582                Node::none(),
1583                Node::none(),
1584                Node::none(),
1585                Node::none(),
1586                Node::none(),
1587                Node::none(),
1588                Node::none(),
1589                Node::none(),
1590                Node::none(),
1591                Node::none(),
1592                Node::none(),
1593                Node::none(),
1594                Node::none(),
1595                Node::none(),
1596                Node::none(),
1597                Node::none(),
1598                Node::none(),
1599                Node::none(),
1600                Node::none(),
1601                Node::none(),
1602                Node::none(),
1603                Node::none(),
1604                Node::none(),
1605                Node::none(),
1606                Node::none(),
1607                Node::none(),
1608                Node::none(),
1609                Node::none(),
1610                Node::none(),
1611                Node::none(),
1612                Node::none(),
1613                Node::none(),
1614                Node::none(),
1615                Node::none(),
1616                Node::none(),
1617                Node::none(),
1618                Node::none(),
1619                Node::none(),
1620                Node::none(),
1621                Node::none(),
1622                Node::none(),
1623                Node::none(),
1624                Node::none(),
1625                Node::none(),
1626                Node::none(),
1627                Node::none(),
1628                Node::none(),
1629                Node::none(),
1630                Node::none(),
1631                Node::none(),
1632                Node::none(),
1633                Node::none(),
1634                Node::none(),
1635                Node::none(),
1636                Node::none(),
1637                Node::none(),
1638                Node::none(),
1639                Node::none(),
1640                Node::none(),
1641                Node::none(),
1642                Node::none(),
1643                Node::none(),
1644                Node::none(),
1645                Node::none(),
1646                Node::none(),
1647                Node::none(),
1648                Node::none(),
1649                Node::none(),
1650                Node::none(),
1651                Node::none(),
1652                Node::none(),
1653                Node::none(),
1654                Node::none(),
1655                Node::none(),
1656                Node::none(),
1657                Node::none(),
1658                Node::none(),
1659                Node::none(),
1660                Node::none(),
1661                Node::none(),
1662                Node::none(),
1663                Node::none(),
1664                Node::none(),
1665                Node::none(),
1666                Node::none(),
1667                Node::none(),
1668                Node::none(),
1669                Node::none(),
1670                Node::none(),
1671                Node::none(),
1672                Node::none(),
1673                Node::none(),
1674                Node::none(),
1675                Node::none(),
1676                Node::none(),
1677                Node::none(),
1678                Node::none(),
1679                Node::none(),
1680                Node::none(),
1681                Node::none(),
1682                Node::none(),
1683                Node::none(),
1684                Node::none(),
1685                Node::none(),
1686                Node::none(),
1687                Node::none(),
1688                Node::none(),
1689                Node::none(),
1690                Node::none(),
1691                Node::none(),
1692                Node::none(),
1693                Node::none(),
1694                Node::none(),
1695                Node::none(),
1696                Node::none(),
1697                Node::none(),
1698                Node::none(),
1699                Node::none(),
1700                Node::none(),
1701                Node::none(),
1702                Node::none(),
1703                Node::none(),
1704                Node::none(),
1705                Node::none(),
1706                Node::none(),
1707                Node::none(),
1708                Node::none(),
1709                Node::none(),
1710                Node::none(),
1711                Node::none(),
1712                Node::none(),
1713                Node::none(),
1714                Node::none(),
1715                Node::none(),
1716                Node::none(),
1717                Node::none(),
1718                Node::none(),
1719                Node::none(),
1720                Node::none(),
1721                Node::none(),
1722                Node::none(),
1723                Node::none(),
1724                Node::none(),
1725                Node::none(),
1726                Node::none(),
1727                Node::none(),
1728                Node::none(),
1729                Node::none(),
1730                Node::none(),
1731                Node::none(),
1732                Node::none(),
1733                Node::none(),
1734                Node::none(),
1735                Node::none(),
1736                Node::none(),
1737                Node::none(),
1738                Node::none(),
1739                Node::none(),
1740                Node::none(),
1741                Node::none(),
1742                Node::none(),
1743                Node::none(),
1744                Node::none(),
1745                Node::none(),
1746                Node::none(),
1747                Node::none(),
1748                Node::none(),
1749                Node::none(),
1750                Node::none(),
1751                Node::none(),
1752                Node::none(),
1753                Node::none(),
1754                Node::none(),
1755                Node::none(),
1756                Node::none(),
1757                Node::none(),
1758                Node::none(),
1759                Node::none(),
1760                Node::none(),
1761                Node::none(),
1762                Node::none(),
1763                Node::none(),
1764                Node::none(),
1765                Node::none(),
1766                Node::none(),
1767                Node::none(),
1768                Node::none(),
1769                Node::none(),
1770                Node::none(),
1771                Node::none(),
1772                Node::none(),
1773                Node::none(),
1774                Node::none(),
1775                Node::none(),
1776                Node::none(),
1777                Node::none(),
1778                Node::none(),
1779                Node::none(),
1780                Node::none(),
1781                Node::none(),
1782                Node::none(),
1783                Node::none(),
1784                Node::none(),
1785                Node::none(),
1786                Node::none(),
1787                Node::none(),
1788                Node::none(),
1789                Node::none(),
1790                Node::none(),
1791            ],
1792        }
1793    }
1794}
1795
1796#[test]
1797fn test_inserts() {
1798    let mut art = Art::new();
1799    assert_eq!(art.insert([], "v1"), None);
1800    assert_eq!(art.insert([], "v2"), Some("v1"));
1801
1802    let mut art = Art::new();
1803    assert_eq!(art.insert([0], "k 0 v 1"), None);
1804    assert_eq!(art.insert([10], "k 1 v 1"), None);
1805    assert_eq!(art.insert([0], "k 0 v 2"), Some("k 0 v 1"));
1806    assert_eq!(art.insert([10], "k 1 v 2"), Some("k 1 v 1"));
1807    assert_eq!(art.insert([0], "k 0 v 3"), Some("k 0 v 2"));
1808    assert_eq!(art.insert([10], "k 1 v 3"), Some("k 1 v 2"));
1809
1810    let mut art: Art<&str, 2> = Art::new();
1811    assert_eq!(art.get(&[255, 255]), None);
1812    assert_eq!(art.insert([20, 20], "k 0 v 1"), None);
1813    assert_eq!(art.insert([20, 192], "k 1 v 1"), None);
1814    assert_eq!(art.insert([20, 20], "k 0 v 2"), Some("k 0 v 1"));
1815    assert_eq!(art.insert([20, 192], "k 1 v 2"), Some("k 1 v 1"));
1816    assert_eq!(art.insert([20, 20], "k 0 v 3"), Some("k 0 v 2"));
1817    assert_eq!(art.insert([20, 192], "k 1 v 3"), Some("k 1 v 2"));
1818}
1819
1820#[test]
1821fn regression_00() {
1822    let mut art: Art<u8, 1> = Art::new();
1823
1824    art.insert([37], 38);
1825    art.insert([0], 1);
1826    assert_eq!(art.len(), 2);
1827
1828    art.insert([5], 5);
1829    art.insert([1], 9);
1830    art.insert([0], 0);
1831    art.insert([255], 255);
1832    art.insert([0], 0);
1833    art.insert([47], 0);
1834    art.insert([253], 37);
1835    assert_eq!(art.len(), 7);
1836
1837    art.insert([10], 0);
1838    art.insert([38], 28);
1839    art.insert([24], 28);
1840    assert_eq!(art.len(), 10);
1841
1842    art.insert([28], 30);
1843    art.insert([30], 30);
1844    art.insert([28], 15);
1845    art.insert([51], 48);
1846    art.insert([53], 255);
1847    art.insert([59], 58);
1848    art.insert([58], 58);
1849    assert_eq!(art.len(), 16);
1850    assert_eq!(art.remove(&[85]), None);
1851    assert_eq!(art.len(), 16);
1852    art.insert([30], 30);
1853    art.insert([30], 0);
1854    art.insert([30], 0);
1855    assert_eq!(art.len(), 16);
1856    art.insert([143], 254);
1857    assert_eq!(art.len(), 17);
1858    art.insert([30], 30);
1859    assert_eq!(art.len(), 17);
1860    assert_eq!(art.len(), 17);
1861    assert_eq!(art.remove(&[85]), None);
1862    assert_eq!(art.len(), 17);
1863}
1864
1865#[test]
1866fn regression_01() {
1867    let mut art: Art<u8, 3> = Art::new();
1868
1869    assert_eq!(art.insert([0, 0, 0], 0), None);
1870    assert_eq!(art.insert([0, 11, 0], 1), None);
1871    assert_eq!(art.insert([0, 0, 0], 2), Some(0));
1872
1873    assert_eq!(
1874        art.iter().collect::<Vec<_>>(),
1875        vec![([0, 0, 0], &2), ([0, 11, 0], &1),]
1876    );
1877}
1878
1879#[test]
1880fn regression_02() {
1881    let mut art = Art::new();
1882    art.insert([1, 1, 1], 1);
1883    art.remove(&[2, 2, 2]);
1884    art.insert([0, 0, 0], 5);
1885    assert_eq!(
1886        art.iter().collect::<Vec<_>>(),
1887        vec![([0, 0, 0], &5), ([1, 1, 1], &1),]
1888    );
1889}
1890
1891#[test]
1892fn regression_03() {
1893    fn expand(k: [u8; 4]) -> [u8; 11] {
1894        let mut ret = [0; 11];
1895
1896        ret[0] = k[0];
1897        ret[5] = k[2];
1898        ret[10] = k[3];
1899
1900        let mut b = k[1];
1901        // byte at index 0 is k[0]
1902        for i in 1..5 {
1903            if b.leading_zeros() == 0 {
1904                ret[i] = 255;
1905            }
1906            b = b.rotate_left(1);
1907        }
1908        // byte at index 5 is k[2]
1909        for i in 6..10 {
1910            if b.leading_zeros() == 0 {
1911                ret[i] = 255;
1912            }
1913            b = b.rotate_left(1);
1914        }
1915        // byte at index 10 is k[3]
1916
1917        ret
1918    }
1919
1920    let mut art = Art::new();
1921    art.insert(expand([1, 173, 33, 255]), 255);
1922    art.insert(expand([255, 20, 255, 223]), 223);
1923
1924    let start = expand([223, 223, 223, 223]);
1925    let end = expand([255, 255, 255, 255]);
1926    let v = art.range(start..end).count();
1927    assert_eq!(v, 1);
1928}
1929
1930#[test]
1931fn regression_04() {
1932    let mut art = Art::new();
1933
1934    art.insert([], 0);
1935
1936    assert_eq!(art.get(&[]), Some(&0));
1937    assert_eq!(art.remove(&[]), Some(0));
1938    assert_eq!(art.get(&[]), None);
1939
1940    art.insert([], 3);
1941
1942    assert_eq!(art.iter().count(), 1);
1943}
1944
1945#[test]
1946fn regression_05() {
1947    let mut art = Art::new();
1948
1949    let k = [0; 2];
1950    art.insert(k, 0);
1951    assert_eq!(art.remove(&k), Some(0));
1952
1953    assert!(art.root.is_none());
1954}
1955
1956#[test]
1957fn regression_06() {
1958    let mut art = Art::new();
1959
1960    let max = u16::MAX as u32 + 1;
1961
1962    for i in 0..max {
1963        let k = i.to_be_bytes();
1964        art.insert(k, 0);
1965    }
1966
1967    for i in 0..max {
1968        let k = i.to_be_bytes();
1969        art.remove(&k);
1970    }
1971
1972    assert!(art.root.is_none());
1973}
1974
1975#[test]
1976fn regression_07() {
1977    fn run<T: Default>() {
1978        let _ = [([], Default::default())]
1979            .into_iter()
1980            .collect::<Art<(), 0>>();
1981    }
1982    run::<()>();
1983    run::<u8>();
1984    run::<u16>();
1985    run::<u32>();
1986    run::<u64>();
1987    run::<usize>();
1988    run::<String>();
1989    run::<Vec<usize>>();
1990}
art/lib.rs

art/
lib.rs
