sokoban/
critbit.rs

1use bytemuck::{Pod, Zeroable};
2use std::ops::{Index, IndexMut};
3
4use crate::node_allocator::{
5    FromSlice, NodeAllocator, NodeAllocatorMap, OrderedNodeAllocatorMap, TreeField as Field,
6    ZeroCopy, SENTINEL,
7};
8
9#[repr(C)]
10#[derive(Default, Copy, Clone)]
11pub struct CritbitNode {
12    pub key: u128,
13    pub prefix_len: u64,
14    pub _padding: u64,
15}
16
17unsafe impl Zeroable for CritbitNode {}
18unsafe impl Pod for CritbitNode {}
19
20impl CritbitNode {
21    pub fn new(prefix_len: u64, key: u128) -> Self {
22        Self {
23            prefix_len,
24            key,
25            _padding: 0,
26        }
27    }
28}
29
30#[repr(C)]
31#[derive(Copy, Clone)]
32pub struct Critbit<
33    V: Default + Copy + Clone + Pod + Zeroable,
34    const NUM_NODES: usize,
35    const MAX_SIZE: usize,
36> {
37    _padding0: u64,
38    /// Root node of the critbit tree
39    pub root: u32,
40    _padding1: u32,
41    /// Allocator corresponding to inner nodes and leaf pointers of the critbit
42    node_allocator: NodeAllocator<CritbitNode, NUM_NODES, 4>,
43    /// Allocator corresponding to the leaves of the critbit. Note that this
44    /// requires 4 registers per leaf to support proper alignment (for aarch64)
45    leaves: NodeAllocator<V, MAX_SIZE, 4>,
46}
47
48unsafe impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
49    Zeroable for Critbit<V, NUM_NODES, MAX_SIZE>
50{
51}
52
53unsafe impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
54    Pod for Critbit<V, NUM_NODES, MAX_SIZE>
55{
56}
57
58impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
59    ZeroCopy for Critbit<V, NUM_NODES, MAX_SIZE>
60{
61}
62
63impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
64    Default for Critbit<V, NUM_NODES, MAX_SIZE>
65{
66    fn default() -> Self {
67        assert!(NUM_NODES >= 2 * MAX_SIZE);
68        Self {
69            _padding0: 0,
70            root: SENTINEL,
71            _padding1: 0,
72            node_allocator: NodeAllocator::<CritbitNode, NUM_NODES, 4>::default(),
73            leaves: NodeAllocator::<V, MAX_SIZE, 4>::default(),
74        }
75    }
76}
77
78impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
79    FromSlice for Critbit<V, NUM_NODES, MAX_SIZE>
80{
81    fn new_from_slice(slice: &mut [u8]) -> &mut Self {
82        assert!(NUM_NODES >= 2 * MAX_SIZE);
83        let tree = Self::load_mut_bytes(slice).unwrap();
84        tree.initialize();
85        tree
86    }
87}
88
89impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
90    NodeAllocatorMap<u128, V> for Critbit<V, NUM_NODES, MAX_SIZE>
91{
92    fn insert(&mut self, key: u128, value: V) -> Option<u32> {
93        self._insert(key, value)
94    }
95
96    fn remove(&mut self, key: &u128) -> Option<V> {
97        self._remove(key)
98    }
99
100    fn contains(&self, key: &u128) -> bool {
101        self.get(key).is_some()
102    }
103
104    fn get(&self, key: &u128) -> Option<&V> {
105        if self.is_empty() {
106            return None;
107        }
108        let mut node_index = self.root;
109        loop {
110            let node = self.get_node(node_index);
111            if !self.is_inner_node(node_index) {
112                if node.key == *key {
113                    let leaf_index = self.get_leaf_index(node_index);
114                    return Some(self.get_leaf(leaf_index));
115                } else {
116                    return None;
117                }
118            }
119            let shared_prefix_len = (node.key ^ key).leading_zeros() as u64;
120            if shared_prefix_len >= node.prefix_len {
121                node_index = self.get_child(node.prefix_len, node_index, *key).0;
122                continue;
123            } else {
124                return None;
125            }
126        }
127    }
128
129    fn get_mut(&mut self, key: &u128) -> Option<&mut V> {
130        if self.is_empty() {
131            return None;
132        }
133        let mut node_index = self.root as u32;
134        loop {
135            let node = self.get_node(node_index);
136            if !self.is_inner_node(node_index) {
137                if node.key == *key {
138                    let leaf_index = self.get_leaf_index(node_index);
139                    return Some(self.get_leaf_mut(leaf_index));
140                } else {
141                    return None;
142                }
143            }
144            let shared_prefix_len = (node.key ^ key).leading_zeros() as u64;
145            if shared_prefix_len >= node.prefix_len {
146                node_index = self.get_child(node.prefix_len, node_index, *key).0;
147                continue;
148            } else {
149                return None;
150            }
151        }
152    }
153
154    fn size(&self) -> usize {
155        self.leaves.size as usize
156    }
157
158    fn len(&self) -> usize {
159        self.leaves.size as usize
160    }
161
162    fn capacity(&self) -> usize {
163        MAX_SIZE
164    }
165
166    fn iter(&self) -> Box<dyn DoubleEndedIterator<Item = (&u128, &V)> + '_> {
167        Box::new(self._iter())
168    }
169
170    fn iter_mut(&mut self) -> Box<dyn DoubleEndedIterator<Item = (&u128, &mut V)> + '_> {
171        Box::new(self._iter_mut())
172    }
173}
174
175impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
176    OrderedNodeAllocatorMap<u128, V> for Critbit<V, NUM_NODES, MAX_SIZE>
177{
178    fn get_min_index(&mut self) -> u32 {
179        self.find_min(self.root as u32)
180    }
181
182    fn get_max_index(&mut self) -> u32 {
183        self.find_max(self.root as u32)
184    }
185
186    fn get_min(&mut self) -> Option<(u128, V)> {
187        match self.get_min_index() {
188            SENTINEL => None,
189            i => {
190                let node = self.get_node(i);
191                let leaf = self.get_leaf(self.get_leaf_index(i));
192                Some((node.key, *leaf))
193            }
194        }
195    }
196
197    fn get_max(&mut self) -> Option<(u128, V)> {
198        match self.get_max_index() {
199            SENTINEL => None,
200            i => {
201                let node = self.get_node(i);
202                let leaf = self.get_leaf(self.get_leaf_index(i));
203                Some((node.key, *leaf))
204            }
205        }
206    }
207}
208
209impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
210    Critbit<V, NUM_NODES, MAX_SIZE>
211{
212    pub fn new() -> Self {
213        Self::default()
214    }
215
216    pub fn initialize(&mut self) {
217        self.node_allocator.initialize();
218        self.leaves.initialize();
219    }
220
221    pub fn get_leaf(&self, leaf_index: u32) -> &V {
222        self.leaves.get(leaf_index).get_value()
223    }
224
225    pub fn get_leaf_mut(&mut self, leaf_index: u32) -> &mut V {
226        self.leaves.get_mut(leaf_index).get_value_mut()
227    }
228
229    fn get_leaf_index(&self, node: u32) -> u32 {
230        self.node_allocator.get_register(node, Field::Value as u32)
231    }
232
233    pub fn is_inner_node(&self, node: u32) -> bool {
234        self.node_allocator.get_register(node, Field::Value as u32) == SENTINEL
235    }
236
237    pub fn get_node(&self, node: u32) -> CritbitNode {
238        *self.node_allocator.get(node).get_value()
239    }
240
241    pub fn get_key(&self, node: u32) -> &u128 {
242        &self.node_allocator.get(node).get_value().key
243    }
244
245    #[inline(always)]
246    pub fn get_left(&self, node: u32) -> u32 {
247        self.node_allocator.get_register(node, Field::Left as u32)
248    }
249
250    #[inline(always)]
251    pub fn get_right(&self, node: u32) -> u32 {
252        self.node_allocator.get_register(node, Field::Right as u32)
253    }
254
255    #[inline(always)]
256    pub fn get_parent(&self, node: u32) -> u32 {
257        self.node_allocator.get_register(node, Field::Parent as u32)
258    }
259
260    pub fn get_node_mut(&mut self, node: u32) -> &mut CritbitNode {
261        self.node_allocator.get_mut(node).get_value_mut()
262    }
263
264    #[inline(always)]
265    fn replace_leaf(&mut self, leaf_index: u32, value: V) {
266        self.leaves.get_mut(leaf_index).set_value(value);
267    }
268
269    #[inline(always)]
270    fn add_leaf(&mut self, key: u128, value: V) -> (u32, u32) {
271        let node_index = self.node_allocator.add_node(CritbitNode::new(128, key));
272        let leaf_index = self.leaves.add_node(value);
273        self.node_allocator
274            .set_register(node_index, leaf_index, Field::Value as u32);
275        self.leaves.get_mut(leaf_index).set_value(value);
276        (node_index, leaf_index)
277    }
278
279    #[inline(always)]
280    fn get_child(&self, prefix_len: u64, node_index: u32, search_key: u128) -> (u32, bool) {
281        let crit_bit_mask = (1u128 << 127) >> prefix_len;
282        if (search_key & crit_bit_mask) != 0 {
283            (self.get_right(node_index), true)
284        } else {
285            (self.get_left(node_index), false)
286        }
287    }
288
289    #[inline(always)]
290    fn duplicate(&mut self, node_index: u32) -> u32 {
291        let index = self.node_allocator.add_node(self.get_node(node_index));
292        let left = self.get_left(node_index);
293        let right = self.get_right(node_index);
294        let value = self
295            .node_allocator
296            .get_register(node_index, Field::Value as u32);
297        self.node_allocator
298            .set_register(index, value, Field::Value as u32);
299        self.node_allocator
300            .connect(index, left, Field::Left as u32, Field::Parent as u32);
301        self.node_allocator
302            .connect(index, right, Field::Right as u32, Field::Parent as u32);
303        index
304    }
305
306    #[inline(always)]
307    fn replace_node(
308        &mut self,
309        node_index: u32,
310        node_contents: &CritbitNode,
311        left: u32,
312        right: u32,
313    ) {
314        *self.get_node_mut(node_index) = *node_contents;
315        self.node_allocator
316            .clear_register(node_index, Field::Value as u32);
317        self.node_allocator
318            .connect(node_index, left, Field::Left as u32, Field::Parent as u32);
319        self.node_allocator
320            .connect(node_index, right, Field::Right as u32, Field::Parent as u32);
321    }
322
323    #[inline(always)]
324    fn migrate(&mut self, source: u32, target: u32) {
325        let content = self.get_node(source);
326        *self.get_node_mut(target) = content;
327        if !self.is_inner_node(source) {
328            assert!(self.get_left(source) == SENTINEL);
329            assert!(self.get_right(source) == SENTINEL);
330            let leaf_index = self.get_leaf_index(source);
331            self.node_allocator
332                .clear_register(source, Field::Value as u32);
333            self.node_allocator
334                .set_register(target, leaf_index, Field::Value as u32);
335        }
336        assert!(self.get_leaf_index(source) == SENTINEL);
337        self.node_allocator.connect(
338            target,
339            self.get_left(source),
340            Field::Left as u32,
341            Field::Parent as u32,
342        );
343        self.node_allocator.connect(
344            target,
345            self.get_right(source),
346            Field::Right as u32,
347            Field::Parent as u32,
348        );
349        self.node_allocator
350            .clear_register(source, Field::Left as u32);
351        self.node_allocator
352            .clear_register(source, Field::Right as u32);
353        self.node_allocator.remove_node(source);
354    }
355
356    #[inline(always)]
357    fn remove_leaf(&mut self, node_index: u32) -> V {
358        let leaf_index = self.get_leaf_index(node_index);
359        let value = *self.get_leaf(leaf_index);
360        self.node_allocator
361            .clear_register(node_index, Field::Value as u32);
362        assert!(self.get_leaf_index(node_index) == SENTINEL);
363        let parent = self.get_parent(node_index);
364        if node_index == self.get_left(parent) {
365            self.node_allocator.disconnect(
366                node_index,
367                parent,
368                Field::Parent as u32,
369                Field::Left as u32,
370            );
371        } else if node_index == self.get_right(parent) {
372            self.node_allocator.disconnect(
373                node_index,
374                parent,
375                Field::Parent as u32,
376                Field::Right as u32,
377            );
378        } else if parent != SENTINEL {
379            panic!("Parent is not connected to child");
380        }
381        self.leaves.remove_node(leaf_index);
382        self.node_allocator.remove_node(node_index);
383        value
384    }
385
386    pub fn get_addr(&self, key: u128) -> u32 {
387        let mut node_index = self.root as u32;
388        loop {
389            let node = self.get_node(node_index);
390            if !self.is_inner_node(node_index) {
391                if node.key == key {
392                    return node_index;
393                } else {
394                    return SENTINEL;
395                }
396            }
397            let shared_prefix_len = (node.key ^ key).leading_zeros() as u64;
398            if shared_prefix_len >= node.prefix_len {
399                node_index = self.get_child(node.prefix_len, node_index, key).0;
400                continue;
401            } else {
402                return SENTINEL;
403            }
404        }
405    }
406
407    fn _insert(&mut self, key: u128, value: V) -> Option<u32> {
408        if self.root == SENTINEL {
409            let (node_index, _leaf_index) = self.add_leaf(key, value);
410            self.root = node_index;
411            return Some(self.root);
412        }
413        // Return None if the tree is filled up
414        if self.len() >= self.capacity() {
415            return None;
416        }
417        let mut node_index = self.root;
418        loop {
419            let node = self.get_node(node_index);
420            if node.key == key && !self.is_inner_node(node_index) {
421                // Replace the node with the new value
422                let leaf_index = self.get_leaf_index(node_index);
423                self.replace_leaf(leaf_index, value);
424                return Some(node_index);
425            }
426            let shared_prefix_len = (node.key ^ key).leading_zeros() as u64;
427            if shared_prefix_len >= node.prefix_len {
428                node_index = self.get_child(node.prefix_len, node_index, key).0;
429                continue;
430            }
431            let crit_bit_mask: u128 = (1u128 << 127) >> shared_prefix_len;
432            let is_right = (crit_bit_mask & key) != 0;
433            let (node_leaf_index, _leaf_index) = self.add_leaf(key, value);
434            let moved_node_index = self.duplicate(node_index);
435            let new_node = CritbitNode::new(shared_prefix_len, key);
436            if is_right {
437                self.replace_node(node_index, &new_node, moved_node_index, node_leaf_index);
438            } else {
439                self.replace_node(node_index, &new_node, node_leaf_index, moved_node_index);
440            }
441            return Some(node_leaf_index);
442        }
443    }
444
445    fn _remove(&mut self, key: &u128) -> Option<V> {
446        let nsize = self.node_allocator.size;
447        let lsize = self.leaves.size;
448        let mut parent = self.root;
449        let mut child: u32;
450        let mut is_right: bool;
451        if self.len() == 0 {
452            return None;
453        }
454        if self.is_inner_node(parent) {
455            let node = self.get_node(parent);
456            let (c, ir) = self.get_child(node.prefix_len, parent, *key);
457            child = c;
458            is_right = ir;
459        } else {
460            let leaf = self.get_node(parent);
461            if leaf.key == *key {
462                self.root = SENTINEL;
463                assert!(self.len() == 1);
464                return Some(self.remove_leaf(parent));
465            } else {
466                return None;
467            }
468        }
469        loop {
470            let node = self.get_node(child);
471            if self.is_inner_node(child) {
472                let (grandchild, grandchild_crit_bit) =
473                    self.get_child(node.prefix_len, child, *key);
474                parent = child;
475                child = grandchild;
476                is_right = grandchild_crit_bit;
477            } else {
478                if node.key != *key {
479                    return None;
480                }
481                break;
482            }
483        }
484        let sibling = if is_right {
485            self.get_left(parent)
486        } else {
487            self.get_right(parent)
488        };
489        let leaf = self.remove_leaf(child);
490        self.migrate(sibling, parent);
491        assert!(nsize - self.node_allocator.size == 2);
492        assert!(lsize - self.leaves.size == 1);
493        Some(leaf)
494    }
495
496    fn find_min(&self, index: u32) -> u32 {
497        let mut node = index;
498        while self.get_left(node) != SENTINEL {
499            node = self.get_left(node);
500        }
501        node
502    }
503
504    fn find_max(&self, index: u32) -> u32 {
505        let mut node = index;
506        while self.get_right(node) != SENTINEL {
507            node = self.get_right(node);
508        }
509        node
510    }
511
512    fn _iter(&self) -> CritbitIterator<'_, V, NUM_NODES, MAX_SIZE> {
513        if self.root == SENTINEL {
514            CritbitIterator::<V, NUM_NODES, MAX_SIZE> {
515                tree: self,
516                fwd_stack: vec![],
517                fwd_node: None,
518                rev_stack: vec![],
519                rev_node: None,
520                terminated: false,
521            }
522        } else {
523            CritbitIterator::<V, NUM_NODES, MAX_SIZE> {
524                tree: self,
525                fwd_stack: vec![self.root],
526                fwd_node: None,
527                rev_stack: vec![self.root],
528                rev_node: None,
529                terminated: false,
530            }
531        }
532    }
533
534    fn _iter_mut(&mut self) -> CritbitIteratorMut<'_, V, NUM_NODES, MAX_SIZE> {
535        let node = self.root;
536        if node == SENTINEL {
537            CritbitIteratorMut::<V, NUM_NODES, MAX_SIZE> {
538                tree: self,
539                fwd_stack: vec![],
540                fwd_node: None,
541                rev_stack: vec![],
542                rev_node: None,
543                terminated: false,
544            }
545        } else {
546            CritbitIteratorMut::<V, NUM_NODES, MAX_SIZE> {
547                tree: self,
548                fwd_stack: vec![node],
549                fwd_node: None,
550                rev_stack: vec![node],
551                rev_node: None,
552                terminated: false,
553            }
554        }
555    }
556}
557
558impl<
559        'a,
560        V: Default + Copy + Clone + Pod + Zeroable,
561        const MAX_NODES: usize,
562        const MAX_SIZE: usize,
563    > IntoIterator for &'a Critbit<V, MAX_NODES, MAX_SIZE>
564{
565    type Item = (&'a u128, &'a V);
566    type IntoIter = CritbitIterator<'a, V, MAX_NODES, MAX_SIZE>;
567
568    fn into_iter(self) -> Self::IntoIter {
569        self._iter()
570    }
571}
572
573impl<
574        'a,
575        V: Default + Copy + Clone + Pod + Zeroable,
576        const MAX_NODES: usize,
577        const MAX_SIZE: usize,
578    > IntoIterator for &'a mut Critbit<V, MAX_NODES, MAX_SIZE>
579{
580    type Item = (&'a u128, &'a mut V);
581    type IntoIter = CritbitIteratorMut<'a, V, MAX_NODES, MAX_SIZE>;
582
583    fn into_iter(self) -> Self::IntoIter {
584        self._iter_mut()
585    }
586}
587
588pub struct CritbitIterator<
589    'a,
590    V: Default + Copy + Clone + Pod + Zeroable,
591    const MAX_NODES: usize,
592    const MAX_SIZE: usize,
593> {
594    tree: &'a Critbit<V, MAX_NODES, MAX_SIZE>,
595    fwd_stack: Vec<u32>,
596    fwd_node: Option<u32>,
597    rev_stack: Vec<u32>,
598    rev_node: Option<u32>,
599    terminated: bool,
600}
601
602impl<
603        'a,
604        V: Default + Copy + Clone + Pod + Zeroable,
605        const MAX_NODES: usize,
606        const MAX_SIZE: usize,
607    > Iterator for CritbitIterator<'a, V, MAX_NODES, MAX_SIZE>
608{
609    type Item = (&'a u128, &'a V);
610
611    fn next(&mut self) -> Option<Self::Item> {
612        while !self.terminated && !self.fwd_stack.is_empty() {
613            let node = self.fwd_stack.pop();
614            match node {
615                Some(n) => {
616                    if !self.tree.is_inner_node(n) {
617                        let i = self.tree.get_leaf_index(n);
618                        if Some(i) == self.rev_node {
619                            self.terminated = true;
620                            return None;
621                        }
622                        self.fwd_node = Some(i);
623                        let v = self.tree.get_leaf(i);
624                        let k = self.tree.get_key(n);
625                        return Some((k, v));
626                    } else {
627                        self.fwd_stack.push(self.tree.get_right(n));
628                        self.fwd_stack.push(self.tree.get_left(n));
629                    }
630                }
631                _ => return None,
632            }
633        }
634        None
635    }
636}
637
638impl<
639        'a,
640        V: Default + Copy + Clone + Pod + Zeroable,
641        const MAX_NODES: usize,
642        const MAX_SIZE: usize,
643    > DoubleEndedIterator for CritbitIterator<'a, V, MAX_NODES, MAX_SIZE>
644{
645    fn next_back(&mut self) -> Option<Self::Item> {
646        while !self.terminated && !self.rev_stack.is_empty() {
647            let node = self.rev_stack.pop();
648            match node {
649                Some(n) => {
650                    if !self.tree.is_inner_node(n) {
651                        let i = self.tree.get_leaf_index(n);
652                        if Some(i) == self.fwd_node {
653                            self.terminated = true;
654                            return None;
655                        }
656                        self.rev_node = Some(i);
657                        let v = self.tree.get_leaf(i);
658                        let k = self.tree.get_key(n);
659                        return Some((k, v));
660                    } else {
661                        self.rev_stack.push(self.tree.get_left(n));
662                        self.rev_stack.push(self.tree.get_right(n));
663                    }
664                }
665                _ => return None,
666            }
667        }
668        None
669    }
670}
671
672pub struct CritbitIteratorMut<
673    'a,
674    V: Default + Copy + Clone + Pod + Zeroable,
675    const MAX_NODES: usize,
676    const MAX_SIZE: usize,
677> {
678    tree: &'a mut Critbit<V, MAX_NODES, MAX_SIZE>,
679    fwd_stack: Vec<u32>,
680    fwd_node: Option<u32>,
681    rev_stack: Vec<u32>,
682    rev_node: Option<u32>,
683    terminated: bool,
684}
685
686impl<
687        'a,
688        V: Default + Copy + Clone + Pod + Zeroable,
689        const MAX_NODES: usize,
690        const MAX_SIZE: usize,
691    > Iterator for CritbitIteratorMut<'a, V, MAX_NODES, MAX_SIZE>
692{
693    type Item = (&'a u128, &'a mut V);
694
695    fn next(&mut self) -> Option<Self::Item> {
696        while !self.terminated && !self.fwd_stack.is_empty() {
697            let node = self.fwd_stack.pop();
698            match node {
699                Some(n) => {
700                    if !self.tree.is_inner_node(n) {
701                        let i = self.tree.get_leaf_index(n);
702                        if Some(i) == self.rev_node {
703                            self.terminated = true;
704                            return None;
705                        }
706                        self.fwd_node = Some(i);
707                        unsafe {
708                            let key = &(*self
709                                .tree
710                                .node_allocator
711                                .nodes
712                                .as_ptr()
713                                .add((n - 1) as usize))
714                            .get_value()
715                            .key;
716                            let leaf = (*self.tree.leaves.nodes.as_mut_ptr().add((i - 1) as usize))
717                                .get_value_mut();
718                            return Some((key, leaf));
719                        }
720                    } else {
721                        self.fwd_stack.push(self.tree.get_right(n));
722                        self.fwd_stack.push(self.tree.get_left(n));
723                    }
724                }
725                _ => return None,
726            }
727        }
728        None
729    }
730}
731
732impl<
733        'a,
734        V: Default + Copy + Clone + Pod + Zeroable,
735        const MAX_NODES: usize,
736        const MAX_SIZE: usize,
737    > DoubleEndedIterator for CritbitIteratorMut<'a, V, MAX_NODES, MAX_SIZE>
738{
739    fn next_back(&mut self) -> Option<Self::Item> {
740        while !self.terminated && !self.rev_stack.is_empty() {
741            let node = self.rev_stack.pop();
742            match node {
743                Some(n) => {
744                    if !self.tree.is_inner_node(n) {
745                        let i = self.tree.get_leaf_index(n);
746                        if Some(i) == self.fwd_node {
747                            self.terminated = true;
748                            return None;
749                        }
750                        self.rev_node = Some(i);
751                        unsafe {
752                            let key = &(*self
753                                .tree
754                                .node_allocator
755                                .nodes
756                                .as_ptr()
757                                .add((n - 1) as usize))
758                            .get_value()
759                            .key;
760                            let leaf = (*self.tree.leaves.nodes.as_mut_ptr().add((i - 1) as usize))
761                                .get_value_mut();
762                            return Some((key, leaf));
763                        }
764                    } else {
765                        self.rev_stack.push(self.tree.get_left(n));
766                        self.rev_stack.push(self.tree.get_right(n));
767                    }
768                }
769                _ => return None,
770            }
771        }
772        None
773    }
774}
775
776impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
777    Index<u128> for Critbit<V, NUM_NODES, MAX_SIZE>
778{
779    type Output = V;
780
781    fn index(&self, index: u128) -> &Self::Output {
782        self.get(&index).unwrap()
783    }
784}
785
786impl<V: Default + Copy + Clone + Pod + Zeroable, const NUM_NODES: usize, const MAX_SIZE: usize>
787    IndexMut<u128> for Critbit<V, NUM_NODES, MAX_SIZE>
788{
789    fn index_mut(&mut self, index: u128) -> &mut Self::Output {
790        self.get_mut(&index).unwrap()
791    }
792}
sokoban/critbit.rs

sokoban/
critbit.rs
