fastskip 0.1.1

Lock-free arena-backed skip list memtable for LSM-tree storage engines
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

use fastskip::ConcurrentSkipList;

#[test]
fn test_insert_10k_sequential() {
    let sl = ConcurrentSkipList::new();
    for i in 0..10_000 {
        let key = format!("key_{:06}", i);
        let val = format!("val_{:06}", i);
        assert!(sl.insert(key.as_bytes(), val.as_bytes()));
    }

    for i in 0..10_000 {
        let key = format!("key_{:06}", i);
        let expected = format!("val_{:06}", i);
        match sl.get(key.as_bytes()) {
            Some((v, false)) => assert_eq!(v, expected.as_bytes(), "mismatch at key {}", i),
            other => panic!("expected value for key {}, got {:?}", i, other),
        }
    }

    assert_eq!(sl.len(), 10_000);
}

#[test]
fn test_insert_10k_random() {
    use std::collections::HashSet;

    let sl = ConcurrentSkipList::new();
    let mut keys = HashSet::new();

    for i in 0u64..10_000 {
        let k = (i.wrapping_mul(2654435761) % 10_000) as u32;
        let key = format!("key_{:06}", k);
        let val = format!("val_{:06}", k);
        if keys.insert(k) {
            assert!(sl.insert(key.as_bytes(), val.as_bytes()));
        } else {
            assert!(!sl.insert(key.as_bytes(), val.as_bytes()));
        }
    }

    for &k in &keys {
        let key = format!("key_{:06}", k);
        let expected = format!("val_{:06}", k);
        match sl.get(key.as_bytes()) {
            Some((v, false)) => assert_eq!(v, expected.as_bytes()),
            other => panic!("expected value for key {}, got {:?}", k, other),
        }
    }
}

#[test]
fn test_delete_half() {
    let sl = ConcurrentSkipList::new();

    for i in 0..1000 {
        let key = format!("key_{:04}", i);
        let val = format!("val_{:04}", i);
        sl.insert(key.as_bytes(), val.as_bytes());
    }

    for i in (0..1000).step_by(2) {
        let key = format!("key_{:04}", i);
        assert!(sl.delete(key.as_bytes()));
    }

    for i in 0..1000 {
        let key = format!("key_{:04}", i);
        if i % 2 == 0 {
            match sl.get(key.as_bytes()) {
                Some((_, true)) => {}
                other => panic!("expected tombstone for key {}, got {:?}", i, other),
            }
            assert_eq!(sl.get_live(key.as_bytes()), None);
        } else {
            let expected = format!("val_{:04}", i);
            match sl.get(key.as_bytes()) {
                Some((v, false)) => assert_eq!(v, expected.as_bytes()),
                other => panic!("expected live value for key {}, got {:?}", i, other),
            }
        }
    }
}

#[test]
fn test_snapshot_consistency() {
    let sl = ConcurrentSkipList::new();
    for i in 0..100 {
        let key = format!("key_{:04}", i);
        let val = format!("val_{:04}", i);
        sl.insert(key.as_bytes(), val.as_bytes());
    }

    let snap = sl.snapshot();
    let entries: Vec<_> = snap.iter().collect();
    assert_eq!(entries.len(), 100);

    for (i, entry) in entries.iter().enumerate() {
        let expected_key = format!("key_{:04}", i);
        assert_eq!(entry.key, expected_key.as_bytes());
    }
}

#[test]
fn test_get_live_returns_none_for_missing() {
    let sl = ConcurrentSkipList::new();
    assert_eq!(sl.get_live(b"nonexistent"), None);
    assert_eq!(sl.get(b"nonexistent"), None);
}

#[test]
fn test_duplicate_insert() {
    let sl = ConcurrentSkipList::new();
    assert!(sl.insert(b"key", b"val1"));
    assert!(!sl.insert(b"key", b"val2"));

    match sl.get(b"key") {
        Some((v, false)) => assert_eq!(v, b"val1"),
        other => panic!("expected val1, got {:?}", other),
    }
}

#[test]
fn test_memory_usage() {
    let sl = ConcurrentSkipList::new();
    let initial = sl.memory_usage();

    for i in 0..100 {
        let key = format!("key_{:04}", i);
        let val = format!("val_{:04}", i);
        sl.insert(key.as_bytes(), val.as_bytes());
    }

    let after = sl.memory_usage();
    assert!(after > initial, "memory should increase after inserts");
}