arctic-wt 0.1.5

Lock-free 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

use core::ops::RangeFull;

use crate::raw;
use crate::raw::Cursor;
use crate::raw::Edge;
use crate::raw::Key;
use crate::raw::cursor;
use crate::raw::iter::Order;
use crate::raw::iter::PostorderIter;
use crate::sync::Atomic;

#[repr(transparent)]
pub(crate) struct Map<K: Key>(Atomic<Edge<K::Edge>>);

impl<K: Key> Map<K> {
    /// Constructs a new empty map. Does not allocate.
    #[inline]
    pub(crate) const fn new() -> Self {
        Self(Atomic::from_raw(crate::sync::AtomicU128::new(
            Edge::<K::Edge>::NULL.into_raw(),
        )))
    }

    pub(crate) fn postorder<'g>(&'g mut self, order: Option<Order>) -> PostorderIter<'g, K::Edge> {
        unsafe { PostorderIter::new(self.root(), order) }
    }

    #[inline]
    pub(crate) unsafe fn cursor<'g, 'k, P: cursor::Path<K::Read<'k>>>(
        &'g self,
        key: impl Into<K::Read<'k>>,
    ) -> Cursor<'g, K::Read<'k>, P> {
        unsafe { Cursor::<_, P>::new(self.root(), key.into()) }
    }

    #[inline]
    pub(crate) unsafe fn all(&self) -> raw::Shard<'_, 'static, K, RangeFull> {
        unsafe { raw::Shard::<K>::new_all(self.root()) }
    }

    #[inline]
    pub(crate) unsafe fn prefix<'k>(
        &self,
        prefix: impl Into<K::Read<'k>>,
    ) -> raw::Shard<'_, 'k, K, RangeFull> {
        unsafe { raw::Shard::<K>::new_prefix(self.root(), prefix.into()) }
    }

    #[inline]
    pub(crate) unsafe fn range<'k, R>(
        &self,
        range: R,
        prefix: K::Read<'k>,
    ) -> raw::Shard<'_, 'k, K, R>
    where
        R: raw::iter::Range<K::Read<'k>>,
    {
        unsafe { raw::Shard::new_range(self.root(), range, prefix) }
    }

    #[inline]
    pub(crate) fn root(&self) -> &Atomic<Edge<K::Edge>> {
        &self.0
    }

    /// Replace the root while the map is exclusively owned.
    ///
    /// This is used only by pointer-free topology restoration. The caller must
    /// ensure the current root is empty so no allocation is leaked.
    pub(crate) fn set_empty_root(&mut self, root: ribbit::Packed<Edge<K::Edge>>) {
        validate!(self.0.get_mut_packed().is_null());
        *self.0.get_mut_packed() = root;
    }
}

impl<K> Default for Map<K>
where
    K: Key,
{
    #[inline]
    fn default() -> Self {
        Self(Atomic::new_packed(Edge::NULL))
    }
}