akar_storage/
art_node.rs

1//! ART (Adaptive Radix Tree) node types with arena allocation.
2//!
3//! Four node sizes matching the C++ ART implementation:
4//! - `Node4`: Up to 4 children — smallest, best for sparse branches
5//! - `Node16`: Up to 16 children — transitions from Node4 at 5 children
6//! - `Node48`: Up to 48 children — uses indirect index for compact storage
7//! - `Node256`: Up to 256 children — full fan-out, direct array
8//!
9//! Each node carries:
10//! - A `prefix` (compressed path from parent)
11//! - A set of `offsets` (row IDs stored at this leaf)
12//! - `overflow_offsets` (additional row IDs for duplicate keys)
13//!
14//! Port of C++ `ArtPrimaryKeyIndex::Node` from `art_index.h` (lines 95–145)
15//! and `art_index.cpp`.
16
17use std::fmt;
18
19/// Maximum number of nodes per arena block.
20pub const NODE_BLOCK_CAPACITY: usize = 16 * 1024;
21
22/// ART node kind.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub enum NodeKind {
25    Node4 = 0,
26    Node16 = 1,
27    Node48 = 2,
28    Node256 = 3,
29}
30
31/// The growth threshold from one node type to the next.
32pub const NODE4_MAX: u16 = 4;
33pub const NODE16_MAX: u16 = 16;
34pub const NODE48_MAX: u16 = 48;
35
36/// Marker for unused child slots in Node48's indirect index.
37pub const EMPTY_MARKER: u8 = u8::MAX;
38
39/// An ART node — stores a prefix, child pointers, and value offsets.
40///
41/// Uses a flat enum to model the four growth stages. Each variant stores
42/// a fixed-size array of children (or indirect index + compact array).
43#[derive(Clone)]
44pub enum ArtNode {
45    Node4 {
46        prefix: Vec<u8>,
47        keys: [u8; 4],
48        children: [Option<Box<ArtNode>>; 4],
49        offsets: Vec<u64>,
50        overflow_offsets: Vec<u64>,
51        count: u16,
52    },
53    Node16 {
54        prefix: Vec<u8>,
55        keys: [u8; 16],
56        children: [Option<Box<ArtNode>>; 16],
57        offsets: Vec<u64>,
58        overflow_offsets: Vec<u64>,
59        count: u16,
60    },
61    Node48 {
62        prefix: Vec<u8>,
63        child_index: [u8; 256],
64        children: Box<[Option<Box<ArtNode>>; 48]>,
65        offsets: Vec<u64>,
66        overflow_offsets: Vec<u64>,
67        count: u16,
68    },
69    Node256 {
70        prefix: Vec<u8>,
71        children: Box<[Option<Box<ArtNode>>; 256]>,
72        offsets: Vec<u64>,
73        overflow_offsets: Vec<u64>,
74        count: u16,
75    },
76}
77
78impl ArtNode {
79    /// Create a new empty Node4.
80    pub fn new_node4() -> Self {
81        ArtNode::Node4 {
82            prefix: Vec::new(),
83            keys: [0u8; 4],
84            children: Default::default(),
85            offsets: Vec::new(),
86            overflow_offsets: Vec::new(),
87            count: 0,
88        }
89    }
90
91    /// Get the node kind.
92    pub fn kind(&self) -> NodeKind {
93        match self {
94            ArtNode::Node4 { .. } => NodeKind::Node4,
95            ArtNode::Node16 { .. } => NodeKind::Node16,
96            ArtNode::Node48 { .. } => NodeKind::Node48,
97            ArtNode::Node256 { .. } => NodeKind::Node256,
98        }
99    }
100
101    /// Get the number of children.
102    pub fn count(&self) -> u16 {
103        match self {
104            ArtNode::Node4 { count, .. }
105            | ArtNode::Node16 { count, .. }
106            | ArtNode::Node48 { count, .. }
107            | ArtNode::Node256 { count, .. } => *count,
108        }
109    }
110
111    /// Get the prefix bytes.
112    pub fn prefix(&self) -> &[u8] {
113        match self {
114            ArtNode::Node4 { prefix, .. }
115            | ArtNode::Node16 { prefix, .. }
116            | ArtNode::Node48 { prefix, .. }
117            | ArtNode::Node256 { prefix, .. } => prefix,
118        }
119    }
120
121    /// Get the prefix bytes (mutable).
122    pub fn prefix_mut(&mut self) -> &mut Vec<u8> {
123        match self {
124            ArtNode::Node4 { prefix, .. }
125            | ArtNode::Node16 { prefix, .. }
126            | ArtNode::Node48 { prefix, .. }
127            | ArtNode::Node256 { prefix, .. } => prefix,
128        }
129    }
130
131    /// Returns `true` if this node has any offsets (i.e., it's a leaf or contains leaves).
132    pub fn has_offsets(&self) -> bool {
133        let (offsets, overflow) = match self {
134            ArtNode::Node4 {
135                offsets,
136                overflow_offsets,
137                ..
138            } => (offsets, overflow_offsets),
139            ArtNode::Node16 {
140                offsets,
141                overflow_offsets,
142                ..
143            } => (offsets, overflow_offsets),
144            ArtNode::Node48 {
145                offsets,
146                overflow_offsets,
147                ..
148            } => (offsets, overflow_offsets),
149            ArtNode::Node256 {
150                offsets,
151                overflow_offsets,
152                ..
153            } => (offsets, overflow_offsets),
154        };
155        !offsets.is_empty() || !overflow.is_empty()
156    }
157
158    /// Get all offsets (primary + overflow) as a slice.
159    pub fn all_offsets(&self) -> Vec<u64> {
160        let (offsets, overflow) = match self {
161            ArtNode::Node4 {
162                offsets,
163                overflow_offsets,
164                ..
165            } => (offsets, overflow_offsets),
166            ArtNode::Node16 {
167                offsets,
168                overflow_offsets,
169                ..
170            } => (offsets, overflow_offsets),
171            ArtNode::Node48 {
172                offsets,
173                overflow_offsets,
174                ..
175            } => (offsets, overflow_offsets),
176            ArtNode::Node256 {
177                offsets,
178                overflow_offsets,
179                ..
180            } => (offsets, overflow_offsets),
181        };
182        let mut result = offsets.clone();
183        result.extend_from_slice(overflow);
184        result
185    }
186
187    /// Insert a child at the given byte.
188    /// Grows the node if necessary.
189    pub fn insert_child(&mut self, byte: u8, child: Box<ArtNode>) {
190        match self {
191            ArtNode::Node4 {
192                prefix,
193                keys,
194                children,
195                offsets,
196                overflow_offsets,
197                count,
198            } => {
199                if *count < NODE4_MAX {
200                    keys[*count as usize] = byte;
201                    children[*count as usize] = Some(child);
202                    *count += 1;
203                } else {
204                    let old_prefix = std::mem::take(prefix);
205                    let old_offsets = std::mem::take(offsets);
206                    let old_overflow = std::mem::take(overflow_offsets);
207                    let old_keys = std::mem::take(keys);
208                    let old_children = std::mem::take(children);
209                    let old_count = *count;
210                    *self = ArtNode::grow_node4_to_node16(
211                        old_prefix,
212                        old_offsets,
213                        old_overflow,
214                        old_keys,
215                        old_children,
216                        old_count,
217                    );
218                    self.insert_child(byte, child);
219                }
220            }
221            ArtNode::Node16 {
222                prefix,
223                keys,
224                children,
225                offsets,
226                overflow_offsets,
227                count,
228            } => {
229                if *count < NODE16_MAX {
230                    keys[*count as usize] = byte;
231                    children[*count as usize] = Some(child);
232                    *count += 1;
233                } else {
234                    let old_prefix = std::mem::take(prefix);
235                    let old_offsets = std::mem::take(offsets);
236                    let old_overflow = std::mem::take(overflow_offsets);
237                    let old_keys = std::mem::take(keys);
238                    let old_children = std::mem::take(children);
239                    let old_count = *count;
240                    *self = ArtNode::grow_node16_to_node48(
241                        old_prefix,
242                        old_offsets,
243                        old_overflow,
244                        old_keys,
245                        old_children,
246                        old_count,
247                    );
248                    self.insert_child(byte, child);
249                }
250            }
251            ArtNode::Node48 {
252                prefix,
253                child_index,
254                children,
255                offsets,
256                overflow_offsets,
257                count,
258            } => {
259                if *count < NODE48_MAX {
260                    child_index[byte as usize] = *count as u8;
261                    children[*count as usize] = Some(child);
262                    *count += 1;
263                } else {
264                    let old_prefix = std::mem::take(prefix);
265                    let old_offsets = std::mem::take(offsets);
266                    let old_overflow = std::mem::take(overflow_offsets);
267                    let old_child_index = std::mem::replace(child_index, [EMPTY_MARKER; 256]);
268                    let old_children = std::mem::replace(children, Box::new(std::array::from_fn(|_| None)));
269                    let old_count = *count;
270                    *self = ArtNode::grow_node48_to_node256(
271                        old_prefix,
272                        old_offsets,
273                        old_overflow,
274                        old_child_index,
275                        old_children,
276                        old_count,
277                    );
278                    self.insert_child(byte, child);
279                }
280            }
281            ArtNode::Node256 { children, count, .. } => {
282                if children[byte as usize].is_none() {
283                    children[byte as usize] = Some(child);
284                    *count += 1;
285                }
286            }
287        }
288    }
289
290    /// Get a child by byte, if it exists.
291    pub fn get_child(&self, byte: u8) -> Option<&ArtNode> {
292        match self {
293            ArtNode::Node4 {
294                keys, children, count, ..
295            } => {
296                for i in 0..*count as usize {
297                    if keys[i] == byte {
298                        return children[i].as_deref();
299                    }
300                }
301                None
302            }
303            ArtNode::Node16 {
304                keys, children, count, ..
305            } => {
306                for i in 0..*count as usize {
307                    if keys[i] == byte {
308                        return children[i].as_deref();
309                    }
310                }
311                None
312            }
313            ArtNode::Node48 {
314                child_index, children, ..
315            } => {
316                let idx = child_index[byte as usize];
317                if idx == EMPTY_MARKER {
318                    None
319                } else {
320                    children[idx as usize].as_deref()
321                }
322            }
323            ArtNode::Node256 { children, .. } => children[byte as usize].as_deref(),
324        }
325    }
326
327    /// Get a mutable child by byte, if it exists.
328    pub fn get_child_mut(&mut self, byte: u8) -> Option<&mut Box<ArtNode>> {
329        match self {
330            ArtNode::Node4 {
331                keys, children, count, ..
332            } => {
333                for i in 0..*count as usize {
334                    if keys[i] == byte {
335                        return children[i].as_mut();
336                    }
337                }
338                None
339            }
340            ArtNode::Node16 {
341                keys, children, count, ..
342            } => {
343                for i in 0..*count as usize {
344                    if keys[i] == byte {
345                        return children[i].as_mut();
346                    }
347                }
348                None
349            }
350            ArtNode::Node48 {
351                child_index, children, ..
352            } => {
353                let idx = child_index[byte as usize];
354                if idx == EMPTY_MARKER {
355                    None
356                } else {
357                    children[idx as usize].as_mut()
358                }
359            }
360            ArtNode::Node256 { children, .. } => children[byte as usize].as_mut(),
361        }
362    }
363
364    /// Get or insert a child node at the given byte.
365    /// Returns a mutable reference to the child, creating a new empty Node4 if needed.
366    pub fn get_or_insert_child(&mut self, byte: u8) -> &mut Box<ArtNode> {
367        if self.get_child(byte).is_some() {
368            return self.get_child_mut(byte).unwrap();
369        }
370        let new_child = Box::new(ArtNode::new_node4());
371        self.insert_child(byte, new_child);
372        self.get_child_mut(byte).unwrap()
373    }
374
375    /// Remove a child by byte. Does not shrink the node.
376    pub fn remove_child(&mut self, byte: u8) {
377        match self {
378            ArtNode::Node4 {
379                keys, children, count, ..
380            } => {
381                for i in 0..*count as usize {
382                    if keys[i] == byte {
383                        // Shift remaining keys/children left
384                        for j in i..(*count as usize - 1) {
385                            keys[j] = keys[j + 1];
386                            children[j] = children[j + 1].take();
387                        }
388                        children[*count as usize - 1] = None;
389                        *count -= 1;
390                        return;
391                    }
392                }
393            }
394            ArtNode::Node16 {
395                keys, children, count, ..
396            } => {
397                for i in 0..*count as usize {
398                    if keys[i] == byte {
399                        for j in i..(*count as usize - 1) {
400                            keys[j] = keys[j + 1];
401                            children[j] = children[j + 1].take();
402                        }
403                        children[*count as usize - 1] = None;
404                        *count -= 1;
405                        // Could shrink to Node4 if count <= 4
406                        return;
407                    }
408                }
409            }
410            ArtNode::Node48 {
411                child_index,
412                children,
413                count,
414                ..
415            } => {
416                let idx = child_index[byte as usize];
417                if idx != EMPTY_MARKER {
418                    children[idx as usize] = None;
419                    child_index[byte as usize] = EMPTY_MARKER;
420                    *count -= 1;
421                }
422            }
423            ArtNode::Node256 { children, count, .. } => {
424                if children[byte as usize].take().is_some() {
425                    *count -= 1;
426                }
427            }
428        }
429    }
430
431    /// Add a value offset to this node.
432    pub fn add_offset(&mut self, offset: u64) {
433        let (offsets, overflow) = match self {
434            ArtNode::Node4 {
435                offsets,
436                overflow_offsets,
437                ..
438            }
439            | ArtNode::Node16 {
440                offsets,
441                overflow_offsets,
442                ..
443            }
444            | ArtNode::Node48 {
445                offsets,
446                overflow_offsets,
447                ..
448            }
449            | ArtNode::Node256 {
450                offsets,
451                overflow_offsets,
452                ..
453            } => (offsets, overflow_offsets),
454        };
455        if offsets.is_empty() {
456            offsets.push(offset);
457        } else {
458            overflow.push(offset);
459        }
460    }
461
462    /// Remove a specific offset from this node's offsets or overflow.
463    /// Returns `true` if the offset was found and removed.
464    pub fn remove_offset(&mut self, offset: u64) -> bool {
465        let (offsets, overflow) = match self {
466            ArtNode::Node4 {
467                offsets,
468                overflow_offsets,
469                ..
470            }
471            | ArtNode::Node16 {
472                offsets,
473                overflow_offsets,
474                ..
475            }
476            | ArtNode::Node48 {
477                offsets,
478                overflow_offsets,
479                ..
480            }
481            | ArtNode::Node256 {
482                offsets,
483                overflow_offsets,
484                ..
485            } => (offsets, overflow_offsets),
486        };
487        if let Some(pos) = offsets.iter().position(|&o| o == offset) {
488            offsets.remove(pos);
489            // If overflow exists, promote one
490            if !overflow.is_empty() {
491                offsets.push(overflow.remove(0));
492            }
493            return true;
494        }
495        if let Some(pos) = overflow.iter().position(|&o| o == offset) {
496            overflow.remove(pos);
497            return true;
498        }
499        false
500    }
501
502    /// Clear all offsets from this node.
503    pub fn clear_offsets(&mut self) {
504        match self {
505            ArtNode::Node4 {
506                offsets,
507                overflow_offsets,
508                ..
509            }
510            | ArtNode::Node16 {
511                offsets,
512                overflow_offsets,
513                ..
514            }
515            | ArtNode::Node48 {
516                offsets,
517                overflow_offsets,
518                ..
519            }
520            | ArtNode::Node256 {
521                offsets,
522                overflow_offsets,
523                ..
524            } => {
525                offsets.clear();
526                overflow_offsets.clear();
527            }
528        }
529    }
530
531    /// Returns `true` if this node is empty (no children, no offsets, no prefix).
532    pub fn is_empty(&self) -> bool {
533        !self.has_offsets() && self.count() == 0 && self.prefix().is_empty()
534    }
535
536    // ---- Growth helpers ----
537
538    fn grow_node4_to_node16(
539        old_prefix: Vec<u8>,
540        old_offsets: Vec<u64>,
541        old_overflow: Vec<u64>,
542        old_keys: [u8; 4],
543        mut old_children: [Option<Box<ArtNode>>; 4],
544        old_count: u16,
545    ) -> Self {
546        let mut keys = [0u8; 16];
547        let mut children: [Option<Box<ArtNode>>; 16] = Default::default();
548        for i in 0..old_count as usize {
549            keys[i] = old_keys[i];
550            children[i] = old_children[i].take();
551        }
552        ArtNode::Node16 {
553            prefix: old_prefix,
554            keys,
555            children,
556            offsets: old_offsets,
557            overflow_offsets: old_overflow,
558            count: old_count,
559        }
560    }
561
562    fn grow_node16_to_node48(
563        old_prefix: Vec<u8>,
564        old_offsets: Vec<u64>,
565        old_overflow: Vec<u64>,
566        old_keys: [u8; 16],
567        mut old_children: [Option<Box<ArtNode>>; 16],
568        old_count: u16,
569    ) -> Self {
570        let mut child_index = [EMPTY_MARKER; 256];
571        let mut children: Box<[Option<Box<ArtNode>>; 48]> = Box::new(std::array::from_fn(|_| None));
572        for i in 0..old_count as usize {
573            let byte = old_keys[i];
574            child_index[byte as usize] = i as u8;
575            children[i] = old_children[i].take();
576        }
577        ArtNode::Node48 {
578            prefix: old_prefix,
579            child_index,
580            children,
581            offsets: old_offsets,
582            overflow_offsets: old_overflow,
583            count: old_count,
584        }
585    }
586
587    fn grow_node48_to_node256(
588        old_prefix: Vec<u8>,
589        old_offsets: Vec<u64>,
590        old_overflow: Vec<u64>,
591        old_child_index: [u8; 256],
592        mut old_children: Box<[Option<Box<ArtNode>>; 48]>,
593        old_count: u16,
594    ) -> Self {
595        let mut children: Box<[Option<Box<ArtNode>>; 256]> = Box::new(std::array::from_fn(|_| None));
596        for byte in 0..256u16 {
597            let idx = old_child_index[byte as usize];
598            if idx != EMPTY_MARKER {
599                children[byte as usize] = old_children[idx as usize].take();
600            }
601        }
602        ArtNode::Node256 {
603            prefix: old_prefix,
604            children,
605            offsets: old_offsets,
606            overflow_offsets: old_overflow,
607            count: old_count,
608        }
609    }
610}
611
612impl fmt::Debug for ArtNode {
613    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
614        match self {
615            ArtNode::Node4 {
616                prefix,
617                offsets,
618                overflow_offsets,
619                count,
620                ..
621            } => f
622                .debug_struct("Node4")
623                .field("prefix", &prefix)
624                .field("count", count)
625                .field("offsets", offsets)
626                .field("overflow", overflow_offsets)
627                .finish(),
628            ArtNode::Node16 {
629                prefix,
630                offsets,
631                overflow_offsets,
632                count,
633                ..
634            } => f
635                .debug_struct("Node16")
636                .field("prefix", &prefix)
637                .field("count", count)
638                .field("offsets", offsets)
639                .field("overflow", overflow_offsets)
640                .finish(),
641            ArtNode::Node48 {
642                prefix,
643                offsets,
644                overflow_offsets,
645                count,
646                ..
647            } => f
648                .debug_struct("Node48")
649                .field("prefix", &prefix)
650                .field("count", count)
651                .field("offsets", offsets)
652                .field("overflow", overflow_offsets)
653                .finish(),
654            ArtNode::Node256 {
655                prefix,
656                offsets,
657                overflow_offsets,
658                count,
659                ..
660            } => f
661                .debug_struct("Node256")
662                .field("prefix", &prefix)
663                .field("count", count)
664                .field("offsets", offsets)
665                .field("overflow", overflow_offsets)
666                .finish(),
667        }
668    }
669}
670
671// ---- Arena block for fixed-size node storage ----
672
673/// A block of nodes in contiguous memory, used for arena allocation.
674///
675/// Each block holds up to `NODE_BLOCK_CAPACITY` nodes allocated in
676/// a `Vec<ArtNode>`. New nodes are appended; existing nodes are never
677/// individually freed (the entire block is freed on clear).
678///
679/// Port of C++ `NodeBlock` from `art_index.h` (lines 148–163).
680#[derive(Clone)]
681pub struct NodeBlock {
682    nodes: Vec<ArtNode>,
683    used: usize,
684}
685
686impl NodeBlock {
687    pub fn new() -> Self {
688        Self {
689            nodes: Vec::with_capacity(NODE_BLOCK_CAPACITY),
690            used: 0,
691        }
692    }
693
694    /// Allocate a new node in this block.
695    /// Returns the index within the block.
696    pub fn allocate(&mut self, node: ArtNode) -> usize {
697        let idx = self.used;
698        if idx < NODE_BLOCK_CAPACITY {
699            self.nodes.push(node);
700            self.used += 1;
701            idx
702        } else {
703            panic!("NodeBlock full (capacity={NODE_BLOCK_CAPACITY})");
704        }
705    }
706
707    /// Get a reference to a node by index.
708    pub fn get(&self, idx: usize) -> Option<&ArtNode> {
709        self.nodes.get(idx)
710    }
711
712    /// Get a mutable reference to a node by index.
713    pub fn get_mut(&mut self, idx: usize) -> Option<&mut ArtNode> {
714        self.nodes.get_mut(idx)
715    }
716
717    /// Number of used slots.
718    pub fn len(&self) -> usize {
719        self.used
720    }
721
722    pub fn is_empty(&self) -> bool {
723        self.used == 0
724    }
725
726    /// Capacity of this block.
727    pub fn capacity(&self) -> usize {
728        NODE_BLOCK_CAPACITY
729    }
730
731    /// How many slots are remaining.
732    pub fn remaining(&self) -> usize {
733        NODE_BLOCK_CAPACITY - self.used
734    }
735
736    /// Clear all nodes (drops them).
737    pub fn clear(&mut self) {
738        self.nodes.clear();
739        self.used = 0;
740    }
741}
742
743impl Default for NodeBlock {
744    fn default() -> Self {
745        Self::new()
746    }
747}
748
749#[cfg(test)]
750mod tests {
751    use super::*;
752
753    #[test]
754    fn test_node4_insert_and_get() {
755        let mut node = ArtNode::new_node4();
756        let child = Box::new(ArtNode::new_node4());
757        node.insert_child(0x42, child);
758
759        assert_eq!(node.count(), 1);
760        assert!(node.get_child(0x42).is_some());
761        assert!(node.get_child(0x00).is_none());
762    }
763
764    #[test]
765    fn test_node4_grows_to_node16() {
766        let mut node = ArtNode::new_node4();
767        for b in 0..5u8 {
768            node.insert_child(b, Box::new(ArtNode::new_node4()));
769        }
770        assert_eq!(node.kind(), NodeKind::Node16);
771        assert_eq!(node.count(), 5);
772        for b in 0..5u8 {
773            assert!(node.get_child(b).is_some(), "child {b} should exist");
774        }
775    }
776
777    #[test]
778    fn test_node16_grows_to_node48() {
779        let mut node = ArtNode::new_node4();
780        for b in 0..18u8 {
781            node.insert_child(b, Box::new(ArtNode::new_node4()));
782        }
783        assert_eq!(node.kind(), NodeKind::Node48);
784        assert_eq!(node.count(), 18);
785    }
786
787    #[test]
788    fn test_node48_grows_to_node256() {
789        let mut node = ArtNode::new_node4();
790        for b in 0..50u8 {
791            node.insert_child(b, Box::new(ArtNode::new_node4()));
792        }
793        assert_eq!(node.kind(), NodeKind::Node256);
794        assert_eq!(node.count(), 50);
795    }
796
797    #[test]
798    fn test_remove_child() {
799        let mut node = ArtNode::new_node4();
800        node.insert_child(0x10, Box::new(ArtNode::new_node4()));
801        node.insert_child(0x20, Box::new(ArtNode::new_node4()));
802        assert_eq!(node.count(), 2);
803
804        node.remove_child(0x10);
805        assert_eq!(node.count(), 1);
806        assert!(node.get_child(0x10).is_none());
807        assert!(node.get_child(0x20).is_some());
808    }
809
810    #[test]
811    fn test_add_and_remove_offset() {
812        let mut node = ArtNode::new_node4();
813        assert!(!node.has_offsets());
814        node.add_offset(42);
815        assert!(node.has_offsets());
816        assert_eq!(node.all_offsets(), vec![42]);
817
818        node.add_offset(99);
819        assert_eq!(node.all_offsets(), vec![42, 99]);
820
821        assert!(node.remove_offset(42));
822        assert!(!node.remove_offset(999));
823        assert_eq!(node.all_offsets(), vec![99]);
824    }
825
826    #[test]
827    fn test_node_block_allocate() {
828        let mut block = NodeBlock::new();
829        let idx = block.allocate(ArtNode::new_node4());
830        assert_eq!(idx, 0);
831        assert_eq!(block.len(), 1);
832        assert!(block.get(0).is_some());
833    }
834
835    #[test]
836    fn test_get_or_insert_child() {
837        let mut node = ArtNode::new_node4();
838        let _child = node.get_or_insert_child(0xAB);
839        assert_eq!(node.count(), 1);
840
841        // Getting again should not create a new child
842        let _same = node.get_or_insert_child(0xAB);
843        assert_eq!(node.count(), 1);
844    }
845}
akar_storage/art_node.rs

akar_storage/
art_node.rs
