congee 0.4.1

A Rust implementation of ART-OLC concurrent adaptive radix tree.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

use crate::{
    base_node::{BaseNode, Node, NodeIter, NodeType},
    node_ptr::NodePtr,
};

pub(crate) const EMPTY_MARKER: u8 = 48;

#[repr(C)]
#[repr(align(8))]
pub(crate) struct Node48 {
    base: BaseNode,

    pub(crate) child_idx: [u8; 256],
    next_empty: u8,
    children: [NodePtr; 48],
}
#[cfg(not(feature = "shuttle"))]
const _: () = assert!(std::mem::size_of::<Node48>() == 672);

#[cfg(not(feature = "shuttle"))]
const _: () = assert!(std::mem::align_of::<Node48>() == 8);

impl Node48 {
    pub(crate) fn init_empty(&mut self) {
        for v in self.child_idx.iter_mut() {
            *v = EMPTY_MARKER;
        }
        self.next_empty = 0;
        for (i, child) in self.children.iter_mut().enumerate() {
            *child = NodePtr::from_payload(i + 1);
        }
    }
}

pub(crate) struct Node48Iter<'a> {
    start: u16,
    end: u16,
    node: &'a Node48,
}

impl Iterator for Node48Iter<'_> {
    type Item = (u8, NodePtr);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if self.start > self.end {
                return None;
            }

            let key = self.start as usize;
            self.start += 1;

            let child_loc = self.node.child_idx[key];
            if child_loc != EMPTY_MARKER {
                return Some((key as u8, self.node.children[child_loc as usize]));
            }
        }
    }
}

impl Node for Node48 {
    fn get_type() -> NodeType {
        NodeType::N48
    }

    fn remove(&mut self, k: u8) {
        debug_assert!(self.child_idx[k as usize] != EMPTY_MARKER);
        let pos = self.child_idx[k as usize];
        self.children[pos as usize] = NodePtr::from_payload(self.next_empty as usize);
        self.child_idx[k as usize] = EMPTY_MARKER;
        self.next_empty = pos;
        self.base.meta.count -= 1;
        debug_assert!(self.get_child(k).is_none());
    }

    fn get_children(&self, start: u8, end: u8) -> NodeIter {
        NodeIter::N48(Node48Iter {
            start: start as u16,
            end: end as u16,
            node: self,
        })
    }

    fn copy_to<N: Node>(&self, dst: &mut N) {
        for (i, c) in self.child_idx.iter().enumerate() {
            if *c != EMPTY_MARKER {
                dst.insert(i as u8, self.children[*c as usize]);
            }
        }
    }

    fn base(&self) -> &BaseNode {
        &self.base
    }

    fn is_full(&self) -> bool {
        self.base.meta.count == 48
    }

    fn insert(&mut self, key: u8, node: NodePtr) {
        let pos = self.next_empty as usize;
        self.next_empty = unsafe { self.children[pos].as_payload_unchecked() } as u8;

        debug_assert!(pos < 48);

        self.children[pos] = node;
        self.child_idx[key as usize] = pos as u8;
        self.base.meta.count += 1;
    }

    fn change(&mut self, key: u8, val: NodePtr) -> NodePtr {
        let old = self.children[self.child_idx[key as usize] as usize];
        self.children[self.child_idx[key as usize] as usize] = val;
        old
    }

    fn get_child(&self, key: u8) -> Option<NodePtr> {
        let pos = unsafe { self.child_idx.get_unchecked(key as usize) };
        if *pos == EMPTY_MARKER {
            None
        } else {
            let child = unsafe { self.children.get_unchecked(*pos as usize) };
            Some(*child)
        }
    }
}