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

use std::{fmt::Debug, ptr::NonNull};

use crate::{
    base_node::{BaseNode, Node},
    utils::KeyTracker,
};

pub(crate) struct ChildIsPayload<'a> {
    _marker: std::marker::PhantomData<&'a ()>,
}

impl ChildIsPayload<'_> {
    pub(crate) fn new() -> Self {
        Self {
            _marker: std::marker::PhantomData,
        }
    }
}

pub(crate) struct ChildIsSubNode<'a> {
    _marker: std::marker::PhantomData<&'a ()>,
}

impl ChildIsSubNode<'_> {
    pub(crate) fn new() -> Self {
        Self {
            _marker: std::marker::PhantomData,
        }
    }
}

pub(crate) enum PtrType {
    Payload(usize),
    SubNode(NonNull<BaseNode>),
}

#[derive(Clone, Copy)]
pub(crate) union NodePtr {
    payload: usize,
    sub_node: NonNull<BaseNode>,
}

impl Debug for NodePtr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        unsafe {
            write!(
                f,
                "payload: {:?} or sub_node: {:?}",
                self.payload, self.sub_node
            )
        }
    }
}

impl NodePtr {
    #[inline]
    pub(crate) fn from_node(ptr: &BaseNode) -> Self {
        Self {
            sub_node: NonNull::from(ptr),
        }
    }

    fn from_node_new(ptr: NonNull<BaseNode>) -> Self {
        Self { sub_node: ptr }
    }

    pub(crate) fn from_payload(payload: usize) -> Self {
        Self { payload }
    }

    pub(crate) unsafe fn as_payload_unchecked(&self) -> usize {
        unsafe { self.payload }
    }

    pub(crate) fn downcast<const K_LEN: usize>(&self, current_level: usize) -> PtrType {
        if current_level == (K_LEN - 1) {
            PtrType::Payload(unsafe { self.as_payload_unchecked() })
        } else {
            PtrType::SubNode(unsafe { self.sub_node })
        }
    }

    pub(crate) fn downcast_key_tracker<const K_LEN: usize>(
        &self,
        key_tracker: &KeyTracker<K_LEN>,
    ) -> PtrType {
        self.downcast::<K_LEN>(key_tracker.len() - 1)
    }
}

pub(crate) struct AllocatedNode<N: Node> {
    ptr: NonNull<N>,
}

impl<N: Node> AllocatedNode<N> {
    pub(crate) fn new(ptr: NonNull<N>) -> Self {
        Self { ptr }
    }

    pub(crate) fn as_mut(&mut self) -> &mut N {
        unsafe { self.ptr.as_mut() }
    }

    pub(crate) fn into_note_ptr(self) -> NodePtr {
        let ptr = self.ptr;
        std::mem::forget(self);
        unsafe { NodePtr::from_node_new(std::mem::transmute::<NonNull<N>, NonNull<BaseNode>>(ptr)) }
    }

    pub(crate) fn into_non_null(self) -> NonNull<N> {
        let ptr = self.ptr;
        std::mem::forget(self);
        ptr
    }
}

impl<N: Node> Drop for AllocatedNode<N> {
    fn drop(&mut self) {
        unsafe {
            std::ptr::drop_in_place(self.ptr.as_mut());
        }
    }
}