armdb 0.1.13

sharded bitcask key-value storage optimized for NVMe
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

use std::marker::PhantomData;
use std::ops::Bound;

#[cfg(feature = "loom")]
use loom::sync::atomic::Ordering;
#[cfg(not(feature = "loom"))]
use std::sync::atomic::Ordering;

use super::SkipList;
use super::node::SkipNode;
use super::strip_mark;

/// Iterator over skip list nodes with configurable bounds.
///
/// Used by tree-level iterators internally. The `end` bound is compared
/// using natural byte order (not reversed) — callers compute bounds
/// with the reversed flag already accounted for.
#[allow(dead_code)]
pub struct Iter<'g, N: SkipNode> {
    current: *mut N,
    end: Bound<Vec<u8>>,
    _guard: PhantomData<&'g N>,
}

#[allow(dead_code)]
impl<'g, N: SkipNode> Iter<'g, N> {
    /// Iterate all entries from the beginning.
    pub fn all(list: &SkipList<N>, guard: &'g seize::LocalGuard<'_>) -> Self {
        let _ = guard;
        let first = strip_mark(unsafe { (*list.head_ptr()).tower(0).load(Ordering::Acquire) });
        Self {
            current: first,
            end: Bound::Unbounded,
            _guard: PhantomData,
        }
    }

    /// Iterate from `start` with an end bound.
    pub fn from(
        list: &SkipList<N>,
        start: &[u8],
        end: Bound<Vec<u8>>,
        guard: &'g seize::LocalGuard<'_>,
    ) -> Self {
        let first = list.find_first_ge(start, guard);
        Self {
            current: first,
            end,
            _guard: PhantomData,
        }
    }
}

impl<'g, N: SkipNode> Iterator for Iter<'g, N> {
    type Item = &'g N;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if self.current.is_null() {
                return None;
            }
            let node = unsafe { &*self.current };
            self.current = strip_mark(node.tower(0).load(Ordering::Acquire));

            if node.is_marked() {
                continue;
            }

            match &self.end {
                Bound::Unbounded => {}
                Bound::Excluded(end) => {
                    if node.key_bytes() >= end.as_slice() {
                        self.current = std::ptr::null_mut();
                        return None;
                    }
                }
                Bound::Included(end) => {
                    if node.key_bytes() > end.as_slice() {
                        self.current = std::ptr::null_mut();
                        return None;
                    }
                }
            }

            return Some(node);
        }
    }
}