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

//! Basic CRUD operations on a ConcurrentSkipList.
//!
//! Demonstrates insert, get, get_live, delete, iteration, cursors, and sealing.

use fastskip::ConcurrentSkipList;

fn main() {
    let sl = ConcurrentSkipList::new();

    // ── Insert ────────────────────────────────────────────────────────────
    sl.insert(b"user:1001", b"alice");
    sl.insert(b"user:1002", b"bob");
    sl.insert(b"user:1003", b"charlie");
    sl.insert(b"user:1004", b"diana");
    sl.insert(b"user:1005", b"eve");

    // Duplicate keys are rejected (first value wins)
    assert!(!sl.insert(b"user:1001", b"ALICE"));

    // ── Point lookup ──────────────────────────────────────────────────────
    let (val, tombstone) = sl.get(b"user:1002").unwrap();
    assert_eq!(val, b"bob");
    assert!(!tombstone);

    assert_eq!(sl.get_live(b"user:1002"), Some(b"bob".as_slice()));
    assert_eq!(sl.get_live(b"user:9999"), None);

    // ── Delete (tombstone) ────────────────────────────────────────────────
    assert!(sl.delete(b"user:1002")); // returns true: found and tombstoned
    assert!(!sl.delete(b"user:1002")); // already tombstoned

    let (_, tomb) = sl.get(b"user:1002").unwrap();
    assert!(tomb);
    assert_eq!(sl.get_live(b"user:1002"), None);

    // ── Iteration ─────────────────────────────────────────────────────────
    println!("All entries (including tombstones):");
    for entry in sl.iter() {
        let status = if entry.is_tombstone {
            " [TOMBSTONE]"
        } else {
            ""
        };
        println!(
            "  {} -> {}{}",
            std::str::from_utf8(entry.key).unwrap(),
            std::str::from_utf8(entry.value).unwrap(),
            status,
        );
    }

    // ── Cursor (range scan) ───────────────────────────────────────────────
    println!("\nCursor scan from user:1003:");
    if let Some(cursor) = sl.cursor_at(b"user:1003") {
        for entry in cursor {
            if !entry.is_tombstone {
                println!(
                    "  {} -> {}",
                    std::str::from_utf8(entry.key).unwrap(),
                    std::str::from_utf8(entry.value).unwrap(),
                );
            }
        }
    }

    // ── Snapshot ──────────────────────────────────────────────────────────
    let snap = sl.snapshot();
    println!(
        "\nSnapshot sees {} entries (including tombstones)",
        snap.iter().count()
    );

    // ── Seal ──────────────────────────────────────────────────────────────
    let (frozen, fresh) = sl.seal().unwrap();

    println!(
        "\nFrozen memtable: len={}, memory={} bytes",
        frozen.len(),
        frozen.memory_usage()
    );
    println!(
        "Fresh memtable: len={}, memory={} bytes",
        fresh.len(),
        fresh.memory_usage()
    );

    // Fresh memtable accepts new writes
    fresh.insert(b"user:2001", b"frank");
    println!("After insert: fresh len={}", fresh.len());

    // Drop frozen to reclaim memory
    std::mem::drop(frozen);
    println!("\nFrozen dropped. Fresh is ready for production use.");
}