skippydb 0.2.2

A high-performance verifiable key-value store with SHA256 Merkle trees and optional CUDA GPU acceleration, designed for blockchain state storage.
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

pub mod hybrid;
pub mod inmem;

#[cfg(feature = "use_hybridindexer")]
pub type Indexer = hybrid::HybridIndexer;

#[cfg(not(feature = "use_hybridindexer"))]
pub type Indexer = inmem::InMemIndexer;

#[cfg(test)]
mod tests {
    use crate::test_helper::to_k80;

    use super::*;

    fn get_all_values(bt: &Indexer, k80: &[u8]) -> Vec<i64> {
        let mut res = Vec::new();
        bt.for_each_value(-1, k80, |v| -> bool {
            res.push(v);
            false
        });
        res
    }

    fn get_all_adjacent_values(bt: &Indexer, k80: &[u8]) -> Vec<([u8; 10], i64)> {
        let mut kv_out = Vec::new();
        bt.for_each_adjacent_value(-1, k80, |k, v| -> bool {
            let mut _k = [0u8; 10];
            _k.copy_from_slice(k);
            kv_out.push((_k, v));
            false
        });
        kv_out
    }

    //#[test]
    //#[should_panic(expected = "Add Duplicated KV")]
    //fn test_panic_duplicate_add_kv() {
    //    let bt = Indexer::new(32);
    //    bt.add_kv(&to_k80(0x0004000300020001), 0x10, 0);
    //    bt.add_kv(&to_k80(0x0004000300020001), 0x10, 0);
    //}

    #[test]
    #[should_panic(expected = "Cannot Erase Non-existent KV")]
    fn test_panic_erase_non_existent_kv() {
        let bt = Indexer::new(32);
        bt.add_kv(&to_k80(0x0004000300020001), 0x10, 0);
        bt.erase_kv(&to_k80(0x0004000300020000), 0x10, 0);
    }

    #[test]
    fn test_add_kv() {
        let bt = Indexer::new(65535);
        bt.add_kv(&to_k80(0x1111_2222_3333_4444), 888, 0);
        bt.erase_kv(&to_k80(0x1111_2222_3333_4444), 888, 0);
    }

    #[test]
    fn test_btree() {
        let bt = Indexer::new(32);
        assert_eq!(0, bt.len(0));
        bt.add_kv(&to_k80(0x0004000300020001), 0x10, 0);
        assert_eq!(1, bt.len(0));
        bt.add_kv(&to_k80(0x0005000300020001), 0x10, 0);
        assert_eq!(2, bt.len(0));
        bt.add_kv(&to_k80(0x0004000300020001), 0x00, 0);

        assert_eq!(
            [
                (to_k80(0x0004000300020001), 0),
                (to_k80(0x0004000300020001), 0x10)
            ],
            get_all_adjacent_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );

        bt.add_kv(&to_k80(0x0004000300020000), 0x20, 0);
        bt.add_kv(&to_k80(0x0004000300020000), 0x30, 0);
        assert_eq!(5, bt.len(0));

        assert_eq!(
            [0x0, 0x10],
            get_all_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );
        assert_eq!(
            [0x30, 0x20],
            get_all_values(&bt, &to_k80(0x0004000300020000)).as_slice()
        );
        assert_eq!(
            [
                (to_k80(0x0004000300020001), 0),
                (to_k80(0x0004000300020001), 0x10),
                (to_k80(0x0004000300020000), 0x20),
                (to_k80(0x0004000300020000), 0x30),
            ],
            get_all_adjacent_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );

        assert_eq!(
            [
                (to_k80(0x0004000300020000), 0x30),
                (to_k80(0x0004000300020000), 0x20),
            ],
            get_all_adjacent_values(&bt, &to_k80(0x0004000300020000)).as_slice()
        );

        bt.add_kv(&to_k80(0x0004000300020001), 0x100, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x110, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x120, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x130, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x140, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x150, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x160, 0);
        bt.add_kv(&to_k80(0x0004000300020001), 0x170, 0);
        assert_eq!(
            [0x170, 0x160, 0x150, 0x140, 0x130, 0x120, 0x110, 0x100, 0, 0x10],
            get_all_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );
        bt.change_kv(&to_k80(0x0004000300020001), 0x170, 0x710, 0, 0);
        assert_eq!(
            [0x710, 0x160, 0x150, 0x140, 0x130, 0x120, 0x110, 0x100, 0, 0x10],
            get_all_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );
        bt.add_kv(&to_k80(0x0004000300020002), 0x180, 0);
        assert_eq!(
            [
                (to_k80(0x0004000300020002), 0x180),
                (to_k80(0x0004000300020001), 0x10),
                (to_k80(0x0004000300020001), 0),
                (to_k80(0x0004000300020001), 0x100),
                (to_k80(0x0004000300020001), 0x110),
                (to_k80(0x0004000300020001), 0x120),
                (to_k80(0x0004000300020001), 0x130),
                (to_k80(0x0004000300020001), 0x140),
                (to_k80(0x0004000300020001), 0x150),
                (to_k80(0x0004000300020001), 0x160),
                (to_k80(0x0004000300020001), 0x710),
            ],
            get_all_adjacent_values(&bt, &to_k80(0x0004000300020002)).as_slice()
        );
        bt.erase_kv(&to_k80(0x0004000300020001), 0x150, 0);
        assert_eq!(
            [
                (to_k80(0x0004000300020001), 0x710),
                (to_k80(0x0004000300020001), 0x160),
                (to_k80(0x0004000300020001), 0x140),
                (to_k80(0x0004000300020001), 0x130),
                (to_k80(0x0004000300020001), 0x120),
                (to_k80(0x0004000300020001), 0x110),
                (to_k80(0x0004000300020001), 0x100),
                (to_k80(0x0004000300020001), 0),
                (to_k80(0x0004000300020001), 0x10),
                (to_k80(0x0004000300020000), 0x20),
                (to_k80(0x0004000300020000), 0x30),
            ],
            get_all_adjacent_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );
        bt.add_kv(&to_k80(0x000400030001FFFF), 0x150, 0);
        assert_eq!(
            [
                (to_k80(0x0004000300020001), 0x710),
                (to_k80(0x0004000300020001), 0x160),
                (to_k80(0x0004000300020001), 0x140),
                (to_k80(0x0004000300020001), 0x130),
                (to_k80(0x0004000300020001), 0x120),
                (to_k80(0x0004000300020001), 0x110),
                (to_k80(0x0004000300020001), 0x100),
                (to_k80(0x0004000300020001), 0),
                (to_k80(0x0004000300020001), 0x10),
                (to_k80(0x0004000300020000), 0x20),
                (to_k80(0x0004000300020000), 0x30),
            ],
            get_all_adjacent_values(&bt, &to_k80(0x0004000300020001)).as_slice()
        );
    }

    #[test]
    fn test_key_exists() {
        let indexer = Indexer::new(32);
        indexer.add_kv(&to_k80(111), 88, 0);
        indexer.add_kv(&to_k80(222), 888, 0);

        assert!(!indexer.key_exists(&to_k80(333), 123, 0));
        assert!(!indexer.key_exists(&to_k80(111), 123, 0));
        assert!(!indexer.key_exists(&to_k80(111), 888, 0));
        assert!(indexer.key_exists(&to_k80(111), 88, 0));
        assert!(indexer.key_exists(&to_k80(222), 888, 0));
    }
}