rbtree_arena/
lib.rs

1use core::fmt::Debug;
2use std::{alloc::Layout, cmp::Ordering, marker, ops::Index};
3use thiserror::Error;
4
5#[derive(Error, Debug)]
6#[cfg_attr(test, derive(PartialEq))]
7pub enum Error {
8    #[error("cannot insert, reached capacity limit of: {0}")]
9    ReachedCapacity(usize),
10}
11
12#[derive(Debug, PartialEq)]
13enum Color {
14    Red,
15    Black,
16}
17
18#[derive(Debug)]
19struct Node<K: Ord, V> {
20    color: Color,
21    left: NodePtr<K, V>,
22    right: NodePtr<K, V>,
23    parent: NodePtr<K, V>,
24    key: K,
25    value: V,
26}
27
28impl<K: Ord, V> Node<K, V> {
29    fn new(key: K, value: V, color: Color) -> Self {
30        Self::new_with_parent(key, value, color, NodePtr::null())
31    }
32
33    fn new_with_parent(
34        key: K,
35        value: V,
36        color: Color,
37        parent: NodePtr<K, V>,
38    ) -> Self {
39        Self {
40            color,
41            left: NodePtr::null(),
42            right: NodePtr::null(),
43            parent,
44            key,
45            value,
46        }
47    }
48}
49
50#[derive(Debug)]
51struct NodePtr<K: Ord, V>(*mut Node<K, V>);
52
53impl<K: Ord, V> Clone for NodePtr<K, V> {
54    fn clone(&self) -> NodePtr<K, V> {
55        *self
56    }
57}
58
59impl<K: Ord, V> Copy for NodePtr<K, V> {}
60
61impl<K: Ord, V> Ord for NodePtr<K, V> {
62    fn cmp(&self, other: &NodePtr<K, V>) -> Ordering {
63        unsafe { (*self.0).key.cmp(&(*other.0).key) }
64    }
65}
66
67impl<K: Ord, V> PartialOrd for NodePtr<K, V> {
68    fn partial_cmp(&self, other: &NodePtr<K, V>) -> Option<Ordering> {
69        Some(self.cmp(other))
70    }
71}
72
73impl<K: Ord, V> PartialEq for NodePtr<K, V> {
74    fn eq(&self, other: &NodePtr<K, V>) -> bool {
75        self.0 == other.0
76    }
77}
78
79impl<K: Ord, V> Eq for NodePtr<K, V> {}
80
81impl<K: Ord, V> NodePtr<K, V> {
82    #[inline]
83    fn null() -> NodePtr<K, V> {
84        NodePtr(std::ptr::null_mut())
85    }
86
87    #[inline]
88    fn is_null(&self) -> bool {
89        self.0.is_null()
90    }
91
92    fn as_option(&self) -> Option<&Node<K, V>> {
93        if self.0.is_null() {
94            None
95        } else {
96            unsafe { Some(&(*self.0)) }
97        }
98    }
99
100    fn as_option_mut(&self) -> Option<&mut Node<K, V>> {
101        if self.0.is_null() {
102            None
103        } else {
104            unsafe { Some(&mut (*self.0)) }
105        }
106    }
107
108    #[inline]
109    fn unsafe_deref(&self) -> &Node<K, V> {
110        unsafe { &(*self.0) }
111    }
112
113    fn find_min(&self) -> NodePtr<K, V> {
114        let mut node_ptr = self;
115        let mut result = node_ptr;
116        while let Some(node) = node_ptr.as_option_mut() {
117            result = node_ptr;
118            node_ptr = &node.left;
119        }
120        *result
121    }
122
123    fn find_max(&self) -> NodePtr<K, V> {
124        let mut node_ptr = self;
125        let mut result = node_ptr;
126        while let Some(node) = node_ptr.as_option_mut() {
127            result = node_ptr;
128            node_ptr = &node.right;
129        }
130        *result
131    }
132
133    fn next(&self) -> NodePtr<K, V> {
134        if self.is_null() {
135            return *self;
136        }
137
138        let right = self.unsafe_deref().right;
139        if !right.is_null() {
140            right.find_min()
141        } else {
142            let mut node_ptr = self;
143            let mut node = self.unsafe_deref();
144            loop {
145                if let Some(parent) = node.parent.as_option() {
146                    if parent.left == *node_ptr {
147                        return node.parent;
148                    }
149                    node_ptr = &node.parent;
150                    node = parent;
151                } else {
152                    return NodePtr::null();
153                }
154            }
155        }
156    }
157
158    fn prev(&self) -> NodePtr<K, V> {
159        if self.is_null() {
160            return *self;
161        }
162
163        let left = self.unsafe_deref().left;
164        if !left.is_null() {
165            left
166        } else {
167            let mut node_ptr = self;
168            let mut node = self.unsafe_deref();
169            loop {
170                if let Some(parent) = node.parent.as_option() {
171                    if parent.right == *node_ptr {
172                        return node.parent;
173                    }
174                    node_ptr = &node.parent;
175                    node = parent;
176                } else {
177                    return NodePtr::null();
178                }
179            }
180        }
181    }
182}
183
184pub struct Iter<'a, K: Ord + 'a, V: 'a> {
185    head: NodePtr<K, V>,
186    tail: NodePtr<K, V>,
187    length: usize,
188    _marker: marker::PhantomData<&'a ()>,
189}
190
191impl<'a, K: Ord + 'a, V: 'a> Clone for Iter<'a, K, V> {
192    fn clone(&self) -> Iter<'a, K, V> {
193        Iter {
194            head: self.head,
195            tail: self.tail,
196            length: self.length,
197            _marker: self._marker,
198        }
199    }
200}
201
202impl<'a, K: Ord + 'a, V: 'a> Iterator for Iter<'a, K, V> {
203    type Item = (&'a K, &'a V);
204
205    fn next(&mut self) -> Option<(&'a K, &'a V)> {
206        if self.length == 0 || self.head.is_null() {
207            return None;
208        }
209
210        let next = self.head.next();
211        let (key, value) =
212            unsafe { (&(*self.head.0).key, &(*self.head.0).value) };
213        self.head = next;
214        self.length -= 1;
215        Some((key, value))
216    }
217
218    fn size_hint(&self) -> (usize, Option<usize>) {
219        (self.length, Some(self.length))
220    }
221}
222
223impl<'a, K: Ord + 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
224    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
225        if self.length == 0 || self.tail.is_null() {
226            return None;
227        }
228
229        let prev = self.tail.prev();
230        let (key, value) =
231            unsafe { (&(*self.tail.0).key, &(*self.tail.0).value) };
232        self.tail = prev;
233        self.length -= 1;
234        Some((key, value))
235    }
236}
237
238pub struct IntoIter<K: Ord, V> {
239    head: NodePtr<K, V>,
240    tail: NodePtr<K, V>,
241    length: usize,
242
243    // Info to free the arena without dropping the key and values inside it, as
244    // they should already be freed by iterating them by value.
245    arena_ptr: *mut Node<K, V>,
246    arena_layout: Layout,
247}
248
249impl<K: Ord, V> Drop for IntoIter<K, V> {
250    fn drop(&mut self) {
251        let arena_ptr = self.arena_ptr;
252        let arena_layout = self.arena_layout;
253
254        // Drop keys and values we didn't get to iterate.
255        for (_, _) in self {}
256
257        // Free the arena's memory.
258        unsafe {
259            std::alloc::dealloc(arena_ptr as *mut u8, arena_layout);
260        }
261    }
262}
263
264impl<K: Ord, V> Iterator for IntoIter<K, V> {
265    type Item = (K, V);
266
267    fn next(&mut self) -> Option<(K, V)> {
268        if self.length == 0 || self.head.is_null() {
269            return None;
270        }
271
272        let next = self.head.next();
273        let (key, value) = unsafe {
274            (
275                core::ptr::read(&(*self.head.0).key),
276                core::ptr::read(&(*self.head.0).value),
277            )
278        };
279        self.head = next;
280        self.length -= 1;
281        Some((key, value))
282    }
283
284    fn size_hint(&self) -> (usize, Option<usize>) {
285        (self.length, Some(self.length))
286    }
287}
288
289impl<K: Ord, V> DoubleEndedIterator for IntoIter<K, V> {
290    fn next_back(&mut self) -> Option<(K, V)> {
291        if self.length == 0 || self.tail.is_null() {
292            return None;
293        }
294
295        let prev = self.tail.prev();
296        let (key, value) = unsafe {
297            (
298                core::ptr::read(&(*self.tail.0).key),
299                core::ptr::read(&(*self.tail.0).value),
300            )
301        };
302        self.tail = prev;
303        self.length -= 1;
304        Some((key, value))
305    }
306}
307
308pub struct RedBlackTree<K: Ord, V> {
309    arena: Vec<Node<K, V>>,
310    root: NodePtr<K, V>,
311}
312
313impl<K, V> Debug for RedBlackTree<K, V>
314where
315    K: Ord + Debug,
316    V: Debug,
317{
318    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
319        f.debug_map().entries(self.iter()).finish()
320    }
321}
322
323impl<K: Ord + Debug, V: Debug> RedBlackTree<K, V> {
324    fn print_tree(node_ptr: NodePtr<K, V>, level: usize, left: bool) {
325        if node_ptr.is_null() {
326            return;
327        }
328        let node = node_ptr.unsafe_deref();
329        let before = if level > 0 {
330            format!(
331                "{}|-{}-",
332                "    ".repeat(level - 1),
333                if left { "L" } else { "R" }
334            )
335        } else {
336            "".to_string()
337        };
338        let color = match node.color {
339            Color::Red => "\x1b[31m",
340            Color::Black => "\x1b[90m",
341        };
342        println!("{}{}{:?}\x1b[0m: {:?}", before, color, node.key, node.value);
343        Self::print_tree(node.left, level + 1, true);
344        Self::print_tree(node.right, level + 1, false);
345    }
346
347    pub fn pretty_print(&self) {
348        Self::print_tree(self.root, 0, true);
349    }
350}
351
352impl<K, V> PartialEq for RedBlackTree<K, V>
353where
354    K: Eq + Ord,
355    V: PartialEq,
356{
357    fn eq(&self, other: &RedBlackTree<K, V>) -> bool {
358        if self.len() != other.len() {
359            return false;
360        }
361
362        self.iter()
363            .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
364    }
365}
366
367impl<K, V> Eq for RedBlackTree<K, V>
368where
369    K: Eq + Ord,
370    V: Eq,
371{
372}
373
374impl<'a, K, V> Index<&'a K> for RedBlackTree<K, V>
375where
376    K: Ord,
377{
378    type Output = V;
379
380    fn index(&self, index: &K) -> &V {
381        self.get(index).expect("key not found")
382    }
383}
384
385impl<K: Ord, V> IntoIterator for RedBlackTree<K, V> {
386    type Item = (K, V);
387    type IntoIter = IntoIter<K, V>;
388
389    fn into_iter(mut self) -> IntoIter<K, V> {
390        let length = self.len();
391        let head = self.root.find_min();
392        let tail = self.root.find_max();
393
394        self.clear_no_dealloc();
395
396        let arena_ptr = self.arena.as_mut_ptr();
397        let arena_layout =
398            Layout::array::<Node<K, V>>(self.arena.len()).unwrap();
399
400        std::mem::forget(self.arena);
401
402        IntoIter {
403            head,
404            tail,
405            length,
406            arena_ptr,
407            arena_layout,
408        }
409    }
410}
411
412impl<K: Ord, V> RedBlackTree<K, V> {
413    fn with_arena(arena: Vec<Node<K, V>>) -> Self {
414        Self {
415            arena,
416            root: NodePtr::null(),
417        }
418    }
419
420    pub fn with_capacity(capacity: usize) -> Self {
421        Self::with_arena(Vec::with_capacity(capacity))
422    }
423
424    fn clear_no_dealloc(&mut self) {
425        self.root = NodePtr::null();
426    }
427
428    pub fn clear(&mut self) {
429        self.clear_no_dealloc();
430        self.arena.clear();
431    }
432
433    // Iterate using depth first search (minimum to maximum).
434    pub fn iter(&self) -> Iter<K, V> {
435        Iter {
436            head: self.root.find_min(),
437            tail: self.root.find_max(),
438            length: self.len(),
439            _marker: marker::PhantomData,
440        }
441    }
442
443    #[inline]
444    pub fn len(&self) -> usize {
445        self.arena.len()
446    }
447
448    #[inline]
449    pub fn is_empty(&self) -> bool {
450        self.len() == 0
451    }
452
453    #[inline]
454    pub fn capacity(&self) -> usize {
455        self.arena.capacity()
456    }
457
458    fn alloc_node(&mut self, node: Node<K, V>) -> Result<NodePtr<K, V>, Error> {
459        if self.capacity() == self.len() {
460            return Err(Error::ReachedCapacity(self.capacity()));
461        }
462        self.arena.push(node);
463        unsafe {
464            Ok(NodePtr(self.arena.as_mut_ptr().add(self.arena.len() - 1)))
465        }
466    }
467
468    fn find_node(&self, key: &K) -> NodePtr<K, V> {
469        let mut node_ptr = self.root;
470
471        while let Some(node) = node_ptr.as_option_mut() {
472            let next = match key.cmp(&node.key) {
473                Ordering::Less => &mut node.left,
474                Ordering::Greater => &mut node.right,
475                Ordering::Equal => return node_ptr,
476            };
477            node_ptr = *next;
478        }
479
480        NodePtr::null()
481    }
482
483    pub fn get(&self, key: &K) -> Option<&V> {
484        let node_ptr = self.find_node(key);
485        if node_ptr.is_null() {
486            None
487        } else {
488            unsafe { Some(&(*node_ptr.0).value) }
489        }
490    }
491
492    pub fn contains_key(&self, k: &K) -> bool {
493        let node_ptr = self.find_node(k);
494        !node_ptr.is_null()
495    }
496
497    pub fn set(&mut self, key: K, value: V) -> Result<Option<V>, Error> {
498        let mut node_ptr = self.root;
499        if node_ptr.is_null() {
500            self.root = self.alloc_node(Node::new(key, value, Color::Black))?;
501            return Ok(None);
502        }
503
504        loop {
505            let node = unsafe { &mut *node_ptr.0 };
506            let (left, next_ptr) = match key.cmp(&node.key) {
507                Ordering::Less => (true, node.left),
508                Ordering::Greater => (false, node.right),
509                Ordering::Equal => {
510                    return Ok(Some(std::mem::replace(&mut node.value, value)));
511                }
512            };
513
514            if next_ptr.is_null() {
515                let new_node_ptr = self.alloc_node(Node::new_with_parent(
516                    key,
517                    value,
518                    Color::Red,
519                    node_ptr,
520                ))?;
521
522                if left {
523                    node.left = new_node_ptr;
524                } else {
525                    node.right = new_node_ptr;
526                }
527
528                unsafe { self.insert_fixup(new_node_ptr) };
529                return Ok(None);
530            }
531
532            node_ptr = next_ptr;
533        }
534    }
535
536    unsafe fn insert_fixup(&mut self, inserted_node_ptr: NodePtr<K, V>) {
537        let mut node_ptr = inserted_node_ptr;
538        while node_ptr != self.root {
539            let node = &*node_ptr.0;
540            let parent_ptr = node.parent;
541            let parent = &mut *parent_ptr.0;
542            if parent.color == Color::Black {
543                break;
544            }
545
546            let grand_parent_ptr = parent.parent;
547            let grand_parent = &mut *grand_parent_ptr.0;
548
549            if parent_ptr == grand_parent.left {
550                let uncle_ptr = grand_parent.right;
551                let rotate = uncle_ptr.is_null()
552                    || uncle_ptr.unsafe_deref().color == Color::Black;
553                if rotate {
554                    if node_ptr == parent.right {
555                        node_ptr = parent_ptr;
556                        self.rotate_left(node_ptr);
557                    }
558
559                    (*(*node_ptr.0).parent.0).color = Color::Black;
560                    (*grand_parent_ptr.0).color = Color::Red;
561                    node_ptr = parent_ptr;
562                    self.rotate_right(grand_parent_ptr);
563                } else {
564                    let uncle = &mut *uncle_ptr.0;
565                    parent.color = Color::Black;
566                    uncle.color = Color::Black;
567                    grand_parent.color = Color::Red;
568                    node_ptr = grand_parent_ptr;
569                }
570            } else {
571                let uncle_ptr = grand_parent.left;
572                let rotate = uncle_ptr.is_null()
573                    || uncle_ptr.unsafe_deref().color == Color::Black;
574                if rotate {
575                    if node_ptr == parent.left {
576                        node_ptr = parent_ptr;
577                        self.rotate_right(node_ptr);
578                    }
579
580                    (*(*node_ptr.0).parent.0).color = Color::Black;
581                    (*grand_parent_ptr.0).color = Color::Red;
582                    node_ptr = parent_ptr;
583                    self.rotate_left(grand_parent_ptr);
584                } else {
585                    let uncle = &mut *uncle_ptr.0;
586                    parent.color = Color::Black;
587                    uncle.color = Color::Black;
588                    grand_parent.color = Color::Red;
589                    node_ptr = grand_parent_ptr;
590                }
591            }
592        }
593        (*self.root.0).color = Color::Black;
594    }
595
596    unsafe fn rotate_left(&mut self, node_ptr: NodePtr<K, V>) {
597        let node = &mut *node_ptr.0;
598        let right_ptr = node.right;
599        let right = &mut *right_ptr.0;
600
601        node.right = right.left;
602        if let Some(left) = right.left.as_option_mut() {
603            left.parent = node_ptr;
604        }
605
606        right.parent = node.parent;
607
608        match node.parent.as_option_mut() {
609            Some(parent) => {
610                if node_ptr == parent.left {
611                    parent.left = right_ptr;
612                } else {
613                    parent.right = right_ptr;
614                }
615            }
616            None => self.root = right_ptr,
617        }
618
619        right.left = node_ptr;
620        node.parent = right_ptr;
621    }
622
623    unsafe fn rotate_right(&mut self, node_ptr: NodePtr<K, V>) {
624        let node = &mut *node_ptr.0;
625        let left_ptr = node.left;
626        let left = &mut *left_ptr.0;
627
628        node.left = left.right;
629        if let Some(right) = left.right.as_option_mut() {
630            right.parent = node_ptr;
631        }
632
633        left.parent = node.parent;
634
635        match node.parent.as_option_mut() {
636            Some(parent) => {
637                if node_ptr == parent.right {
638                    parent.right = left_ptr;
639                } else {
640                    parent.left = left_ptr;
641                }
642            }
643            None => self.root = left_ptr,
644        }
645
646        left.right = node_ptr;
647        node.parent = left_ptr;
648    }
649}
650
651#[cfg(test)]
652mod tests {
653    use super::*;
654
655    #[test]
656    fn insert_int() {
657        let mut tree = RedBlackTree::with_capacity(2);
658        assert_eq!(tree.len(), 0);
659        assert_eq!(tree.set(1, 2), Ok(None));
660        assert_eq!(tree.len(), 1);
661        assert_eq!(tree.set(2, 4), Ok(None));
662        assert_eq!(tree.len(), 2);
663        assert_eq!(tree.set(2, 6), Ok(Some(4)));
664        assert_eq!(tree.len(), 2);
665        assert!(tree.contains_key(&1));
666        assert!(!tree.contains_key(&100));
667        assert_eq!(tree.get(&1), Some(&2));
668        assert_eq!(tree.get(&2), Some(&6));
669        assert_eq!(tree.get(&3), None);
670        assert!(tree.set(500, 600).is_err());
671    }
672
673    #[test]
674    fn insert_str() {
675        let mut tree = RedBlackTree::with_capacity(3);
676        assert_eq!(tree.set("B", "are"), Ok(None));
677        assert_eq!(tree.set("A", "B"), Ok(None));
678        assert_eq!(tree.set("A", "Trees"), Ok(Some("B")));
679        assert_eq!(tree.set("C", "cool"), Ok(None));
680        assert_eq!(tree.len(), 3);
681        assert!(tree.contains_key(&"C"));
682        assert!(!tree.contains_key(&"nope"));
683        assert_eq!(tree.get(&"A"), Some(&"Trees"));
684        assert_eq!(tree[&"B"], "are");
685        assert_eq!(tree.get(&"C"), Some(&"cool"));
686        assert_eq!(tree.get(&"D"), None);
687        assert!(tree.set("does not exist", "?").is_err());
688    }
689
690    #[test]
691    fn tree_that_runs_all_rotations_and_coloring() {
692        let mut tree = RedBlackTree::with_capacity(8);
693        for i in [8, 18, 5, 15, 17, 25, 40, 80] {
694            assert_eq!(tree.set(i, 0_u8), Ok(None));
695        }
696        let seventeen = tree.root.unsafe_deref();
697        assert_eq!(seventeen.color, Color::Black);
698
699        let eight = seventeen.left.unsafe_deref();
700        assert_eq!(eight.color, Color::Red);
701
702        let five = eight.left.unsafe_deref();
703        assert_eq!(five.color, Color::Black);
704
705        let fifteen = eight.right.unsafe_deref();
706        assert_eq!(fifteen.color, Color::Black);
707
708        let twentyfive = seventeen.right.unsafe_deref();
709        assert_eq!(twentyfive.color, Color::Red);
710
711        let eighteen = twentyfive.left.unsafe_deref();
712        assert_eq!(eighteen.color, Color::Black);
713
714        let forty = twentyfive.right.unsafe_deref();
715        assert_eq!(forty.color, Color::Black);
716
717        let eighty = forty.right.unsafe_deref();
718        assert_eq!(eighty.color, Color::Red);
719    }
720
721    #[test]
722    fn iter() {
723        let mut tree = RedBlackTree::with_capacity(4);
724        tree.set(100, "c").unwrap();
725        tree.set(50, "a").unwrap();
726        tree.set(75, "b").unwrap();
727        tree.set(150, "d").unwrap();
728        let mut iter = tree.iter();
729        assert_eq!(iter.next(), Some((&50, &"a")));
730        assert_eq!(iter.next(), Some((&75, &"b")));
731        assert_eq!(iter.next(), Some((&100, &"c")));
732        assert_eq!(iter.next(), Some((&150, &"d")));
733        assert_eq!(iter.next(), None);
734    }
735
736    #[test]
737    fn iter_clone() {
738        let mut tree = RedBlackTree::with_capacity(4);
739        tree.set(100, "c").unwrap();
740        tree.set(50, "a").unwrap();
741        tree.set(75, "b").unwrap();
742        tree.set(150, "d").unwrap();
743        let mut iter = tree.iter();
744        assert_eq!(iter.next(), Some((&50, &"a")));
745        assert_eq!(iter.next(), Some((&75, &"b")));
746
747        let mut cloned_iter = iter.clone();
748
749        assert_eq!(iter.next(), Some((&100, &"c")));
750        assert_eq!(iter.next(), Some((&150, &"d")));
751        assert_eq!(cloned_iter.next(), Some((&100, &"c")));
752        assert_eq!(cloned_iter.next(), Some((&150, &"d")));
753        assert_eq!(iter.next(), None);
754        assert_eq!(cloned_iter.next(), None);
755    }
756
757    #[test]
758    fn iter_reverse() {
759        let mut tree = RedBlackTree::with_capacity(4);
760        tree.set(100, "c").unwrap();
761        tree.set(50, "a").unwrap();
762        tree.set(75, "b").unwrap();
763        tree.set(150, "d").unwrap();
764        let mut iter = tree.iter().rev();
765        assert_eq!(iter.next(), Some((&150, &"d")));
766        assert_eq!(iter.next(), Some((&100, &"c")));
767        assert_eq!(iter.next(), Some((&75, &"b")));
768        assert_eq!(iter.next(), Some((&50, &"a")));
769        assert_eq!(iter.next(), None);
770    }
771
772    #[test]
773    fn into_iter() {
774        let mut tree = RedBlackTree::with_capacity(4);
775        tree.set(100, "c").unwrap();
776        tree.set(50, "a").unwrap();
777        tree.set(75, "b").unwrap();
778        tree.set(150, "d").unwrap();
779        let mut iter = tree.into_iter();
780        assert_eq!(iter.next(), Some((50, "a")));
781        assert_eq!(iter.next(), Some((75, "b")));
782        assert_eq!(iter.next(), Some((100, "c")));
783        assert_eq!(iter.next(), Some((150, "d")));
784        assert_eq!(iter.next(), None);
785    }
786
787    #[test]
788    fn into_iter_reverse() {
789        let mut tree = RedBlackTree::with_capacity(4);
790        tree.set(100, "c").unwrap();
791        tree.set(50, "a").unwrap();
792        tree.set(75, "b").unwrap();
793        tree.set(150, "d").unwrap();
794        let mut iter = tree.into_iter().rev();
795        assert_eq!(iter.next(), Some((150, "d")));
796        assert_eq!(iter.next(), Some((100, "c")));
797        assert_eq!(iter.next(), Some((75, "b")));
798        assert_eq!(iter.next(), Some((50, "a")));
799        assert_eq!(iter.next(), None);
800    }
801
802    #[test]
803    fn into_iter_for_loop_no_crash() {
804        struct User {
805            // Test there is no double free on a dynamically allocated struct.
806            _name: String,
807            _age: u8,
808        }
809
810        let mut tree = RedBlackTree::with_capacity(2);
811        tree.set(
812            "id1",
813            User {
814                _name: "John Doe".to_string(),
815                _age: 123,
816            },
817        )
818        .unwrap();
819        tree.set(
820            "id2",
821            User {
822                _name: "Tony Solomonik".to_string(),
823                _age: 24,
824            },
825        )
826        .unwrap();
827
828        for (_, _) in tree {}
829    }
830
831    #[test]
832    fn clear() {
833        let mut tree = RedBlackTree::with_capacity(4);
834        assert_eq!(tree.capacity(), 4);
835        assert_eq!(tree.set(100, "c"), Ok(None));
836        assert_eq!(tree.set(50, "a"), Ok(None));
837        assert_eq!(tree.set(75, "b"), Ok(None));
838        assert_eq!(tree.set(150, "d"), Ok(None));
839        tree.clear();
840        assert_eq!(tree.capacity(), 4);
841        assert_eq!(tree.len(), 0);
842    }
843
844    #[test]
845    fn equality() {
846        let mut tree1 = RedBlackTree::with_capacity(4);
847        assert_eq!(tree1.set(100, "c"), Ok(None));
848        assert_eq!(tree1.set(50, "a"), Ok(None));
849        assert_eq!(tree1.set(75, "b"), Ok(None));
850        assert_eq!(tree1.set(150, "d"), Ok(None));
851
852        let mut tree2 = RedBlackTree::with_capacity(4);
853        assert_eq!(tree2.set(150, "d"), Ok(None));
854        assert_eq!(tree2.set(50, "a"), Ok(None));
855        assert_eq!(tree2.set(100, "c"), Ok(None));
856        assert_eq!(tree2.set(75, "b"), Ok(None));
857
858        assert_eq!(tree1, tree2);
859    }
860}
rbtree_arena/lib.rs

rbtree_arena/
lib.rs
