con-art-rust 0.2.0

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

use std::alloc;

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

#[repr(C)]
pub(crate) struct Node256 {
    base: BaseNode,

    children: [NodePtr; 256],
}

impl Node for Node256 {
    fn new(prefix: &[u8]) -> Box<Node256> {
        let layout = alloc::Layout::from_size_align(
            std::mem::size_of::<Node256>(),
            std::mem::align_of::<Node256>(),
        )
        .unwrap();
        unsafe {
            let mem = alloc::alloc_zeroed(layout) as *mut BaseNode;
            let base = BaseNode::new(NodeType::N256, prefix);
            mem.write(base);

            Box::from_raw(mem as *mut Node256)
        }
    }

    fn get_type() -> NodeType {
        NodeType::N256
    }

    fn get_children(&self, start: u8, end: u8) -> Vec<(u8, NodePtr)> {
        let mut children = Vec::with_capacity(48);

        for i in start..=end {
            if !self.children[i as usize].is_null() {
                children.push((i, self.children[i as usize]));
            }
        }

        children
    }

    fn copy_to<N: Node>(&self, dst: &mut N) {
        for i in 0..256 {
            if !self.children[i].is_null() {
                dst.insert(i as u8, self.children[i]);
            }
        }
    }

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

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

    fn is_full(&self) -> bool {
        false
    }

    fn is_under_full(&self) -> bool {
        self.base.count == 37
    }

    fn insert(&mut self, key: u8, node: NodePtr) {
        self.children[key as usize] = node;
        self.base.count += 1;
    }

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

    fn remove(&mut self, k: u8) {
        self.children[k as usize] = NodePtr::from_null();
        self.base.count -= 1;
    }

    fn get_child(&self, key: u8) -> Option<NodePtr> {
        let child = &self.children[key as usize];
        if child.is_null() {
            None
        } else {
            Some(*child)
        }
    }
}