prolly-map 0.3.0

Content-addressed versioned map storage primitives.
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

use prolly::{Config, MemStore, Prolly, RangeCursor};

fn small_node_config() -> Config {
    Config::builder()
        .min_chunk_size(2)
        .max_chunk_size(4)
        .chunking_factor(2)
        .hash_seed(177)
        .build()
}

fn populated_tree(count: usize) -> (Prolly<MemStore>, prolly::Tree) {
    let prolly = Prolly::new(MemStore::new(), small_node_config());
    let mut tree = prolly.create();

    for idx in 0..count {
        tree = prolly
            .put(
                &tree,
                format!("k{idx:03}").into_bytes(),
                format!("v{idx:03}").into_bytes(),
            )
            .unwrap();
    }

    (prolly, tree)
}

#[test]
fn range_after_resumes_without_duplicate_for_exact_and_gap_keys() {
    let (prolly, tree) = populated_tree(12);

    let exact_resume = prolly
        .range_after(&tree, b"k004", Some(b"k008"))
        .unwrap()
        .collect::<Result<Vec<_>, _>>()
        .unwrap();
    assert_eq!(
        exact_resume,
        vec![
            (b"k005".to_vec(), b"v005".to_vec()),
            (b"k006".to_vec(), b"v006".to_vec()),
            (b"k007".to_vec(), b"v007".to_vec()),
        ]
    );

    let gap_resume = prolly
        .range_after(&tree, b"k004a", Some(b"k007"))
        .unwrap()
        .collect::<Result<Vec<_>, _>>()
        .unwrap();
    assert_eq!(
        gap_resume,
        vec![
            (b"k005".to_vec(), b"v005".to_vec()),
            (b"k006".to_vec(), b"v006".to_vec()),
        ]
    );
}

#[test]
fn range_pages_resume_to_reconstruct_bounded_scan() {
    let (prolly, tree) = populated_tree(27);
    let expected = prolly
        .range(&tree, b"k004", Some(b"k021"))
        .unwrap()
        .collect::<Result<Vec<_>, _>>()
        .unwrap();

    let mut cursor = RangeCursor::after_key(b"k003".to_vec());
    let mut actual = Vec::new();
    let mut page_count = 0usize;

    loop {
        let page = prolly.range_page(&tree, &cursor, Some(b"k021"), 5).unwrap();
        page_count += 1;
        actual.extend(page.entries);

        let Some(next) = page.next_cursor else {
            break;
        };
        assert!(!next.is_start());
        cursor = next;
    }

    assert_eq!(actual, expected);
    assert!(page_count > 1);
}

#[test]
fn range_cursor_tracks_iterator_progress_and_zero_limit_is_noop() {
    let (prolly, tree) = populated_tree(4);

    let mut iter = prolly
        .range_from_cursor(&tree, &RangeCursor::start(), None)
        .unwrap();
    assert!(iter.resume_cursor().is_start());

    let first = iter.next().unwrap().unwrap();
    assert_eq!(first.0, b"k000".to_vec());
    assert_eq!(iter.resume_cursor().after(), Some(b"k000".as_slice()));

    let cursor = RangeCursor::after_key(b"k001".to_vec());
    let page = prolly.range_page(&tree, &cursor, None, 0).unwrap();
    assert!(page.entries.is_empty());
    assert_eq!(page.next_cursor, Some(cursor));
}