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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

use core::marker::PhantomData;
use core::ops::RangeFull;
use core::sync::atomic::Ordering;

use crate::raw;
use crate::raw::Cursor;
use crate::raw::Edge;
use crate::raw::Key;
use crate::raw::cursor::path;
use crate::raw::iter::EntryIter;
use crate::raw::iter::Order;
use crate::raw::iter::Range;
use crate::raw::iter::RangeIter;
use crate::raw::iter::ValueIter;
use crate::raw::key::Read as _;
use crate::sync::Atomic;

pub(crate) struct Shard<'g, 'k, K, R = RangeFull>
where
    K: Key,
{
    root: *mut Atomic<Edge<K::Edge>>,
    edge: ribbit::Packed<Edge<K::Edge>>,
    prefix: K::Read<'k>,
    range: R,
    _global: PhantomData<&'g Atomic<Edge<K::Edge>>>,
}

impl<'g, 'k, K, R> Shard<'g, 'k, K, R>
where
    K: Key,
    R: raw::iter::Range<K::Read<'k>>,
{
    #[inline]
    pub(crate) unsafe fn new_all(root: &'g Atomic<Edge<K::Edge>>) -> Shard<'g, 'k, K, RangeFull> {
        let edge = root.load_packed(Ordering::Relaxed);
        unsafe { Shard::new(root as *const _ as *mut _, edge, K::Read::default(), ..) }
    }

    pub(crate) unsafe fn new_prefix(
        root: &'g Atomic<Edge<K::Edge>>,
        prefix: K::Read<'k>,
    ) -> Shard<'g, 'k, K, RangeFull> {
        let mut cursor = unsafe { Cursor::<_, path::Len<_>>::new(root, prefix) };
        let Some(edge) = cursor.traverse_prefix() else {
            return unsafe { Shard::new(core::ptr::null_mut(), Edge::NULL, prefix, ..) };
        };
        let len = cursor.len();
        let prefix = prefix.prefix(len);
        unsafe { Shard::new(cursor.edge() as *const _ as *mut _, edge, prefix, ..) }
    }

    pub(crate) unsafe fn new_range(
        root: &'g Atomic<Edge<K::Edge>>,
        range: R,
        prefix: K::Read<'k>,
    ) -> Shard<'g, 'k, K, R>
    where
        R: Range<K::Read<'k>>,
    {
        validate_eq!(prefix, range.common_prefix());
        let mut cursor = unsafe { Cursor::<_, path::Len<_>>::new(root, prefix) };
        let Some(edge) = cursor.traverse_prefix() else {
            return unsafe { Shard::new(core::ptr::null_mut(), Edge::NULL, prefix, range) };
        };
        let len = cursor.len();
        let prefix = prefix.prefix(len);
        unsafe { Shard::new(cursor.edge() as *const _ as *mut _, edge, prefix, range) }
    }

    #[inline]
    unsafe fn new(
        root: *mut Atomic<Edge<K::Edge>>,
        edge: ribbit::Packed<Edge<K::Edge>>,
        prefix: K::Read<'k>,
        range: R,
    ) -> Shard<'g, 'k, K, R> {
        Shard {
            root,
            edge,
            prefix,
            range,
            _global: PhantomData,
        }
    }

    #[inline]
    pub(crate) fn entries(&self, order: Option<Order>) -> EntryIter<'g, 'k, K, R> {
        EntryIter(unsafe {
            RangeIter::new_unchecked(self.root, self.edge, self.prefix, order, &self.range)
        })
    }

    #[inline]
    pub(crate) fn values(&self, order: Option<Order>) -> ValueIter<'g, 'k, K, R> {
        ValueIter(unsafe {
            RangeIter::new_unchecked(self.root, self.edge, self.prefix, order, &self.range)
        })
    }
}