ppom 0.7.0

Left Leaning Red Black index in Rust-lang
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

use std::sync::Arc;

// Node corresponds to a single entry in Mdb instance.
#[derive(Clone)]
pub struct Node<K, V> {
    pub key: K,
    pub entry: Arc<Entry<V>>,
    pub black: bool,                    // store: black or red
    pub left: Option<Arc<Node<K, V>>>,  // store: left child
    pub right: Option<Arc<Node<K, V>>>, // store: right child
}

impl<K, V> Node<K, V> {
    pub fn set(&mut self, value: V, seqno: u64)
    where
        K: Clone,
        V: Clone,
    {
        let mut entry = self.entry.as_ref().clone();
        entry.set(value, seqno);
        self.entry = Arc::new(entry);
    }

    #[inline]
    pub fn set_red(&mut self) {
        self.black = false
    }

    #[inline]
    pub fn set_black(&mut self) {
        self.black = true
    }

    #[inline]
    pub fn toggle_link(&mut self) {
        self.black = !self.black
    }
}

impl<K, V> Node<K, V> {
    #[inline]
    pub fn as_left_ref(&self) -> Option<&Node<K, V>> {
        self.left.as_deref()
    }

    #[inline]
    pub fn as_right_ref(&self) -> Option<&Node<K, V>> {
        self.right.as_deref()
    }

    #[inline]
    pub fn is_black(&self) -> bool {
        self.black
    }

    #[inline]
    pub fn as_key(&self) -> &K {
        &self.key
    }

    #[inline]
    pub fn to_seqno(&self) -> u64 {
        self.entry.to_seqno()
    }
}

impl<K, V> From<(K, Entry<V>)> for Node<K, V> {
    fn from((key, entry): (K, Entry<V>)) -> Node<K, V> {
        Node {
            key,
            entry: Arc::new(entry),
            black: false,
            left: None,
            right: None,
        }
    }
}

#[derive(Clone, Eq, PartialEq)]
pub struct Entry<V> {
    value: V,
    seqno: u64,
}

impl<V> Entry<V> {
    pub fn new(value: V, seqno: u64) -> Self {
        Entry { value, seqno }
    }

    pub fn to_seqno(&self) -> u64 {
        self.seqno
    }

    pub fn to_value(&self) -> V
    where
        V: Clone,
    {
        self.value.clone()
    }

    pub fn into_value(self) -> V {
        self.value
    }

    fn set(&mut self, value: V, seqno: u64) {
        self.value = value;
        self.seqno = seqno;
    }
}

#[cfg(test)]
#[path = "mdb_node_test.rs"]
mod mdb_node_test;