arctic-wt 0.1.5

Lock-free adaptive radix tree
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

use arctic::Order;
use arctic::concurrent;
use arctic::sequential;
use std::sync::Barrier;

#[test]
fn turso_range_24230c111c599daff93a7abc11c5c72b33d0ebfd() {
    // https://github.com/jennyhour/turso-arctic/blob/2c7cbf300adacf8482346d6f927753c9074d8bd7/core/mvcc/database/mod.rs#L88-L111
    const fn turso_row_id(row_id: i64) -> u128 {
        const SIGN: u64 = 1u64.rotate_right(1);

        let table_id = (-1i64) as u64 ^ SIGN;
        ((table_id as u128) << 64) | (((row_id as u64) ^ SIGN) as u128)
    }

    let mut map = sequential::Map::<u128, u64>::default();
    let entries = (0..10u64)
        .map(|index| (turso_row_id(index as i64), index))
        .collect::<Vec<_>>();

    for (row_id, index) in &entries {
        assert!(map.upsert(*row_id, *index).is_err());
    }

    for (row_id, index) in &entries {
        assert_eq!(map.get(row_id), Some(index));
    }

    let prefix = map.range(turso_row_id(5)..=turso_row_id(i64::MAX));
    let values = prefix.values(Order::Ascend).copied().collect::<Vec<_>>();
    assert_eq!(values, (5..10).collect::<Vec<u64>>());
}

#[test]
fn insert_duplicate_82007770fb876db856313cebf12be21b9182f16a() {
    let map = concurrent::Map::<u64, u64>::default();
    map.insert(0u64, 0u64).unwrap();
    map.insert(0u64, 1u64).unwrap_err();
}

#[test]
fn range_common_prefix_72c2fceda258b00fc2e9d4a805b28e9ad8e8107d() {
    let map = crate::concurrent::Map::<u64, u64>::new();
    const NEEDLE: u64 = 0xE642_3BB1_ADBB_F000;
    const LOWER: u64 = 0x39_9100;
    const UPPER: u64 = 0xFF29_D24D_7E9A_920D;
    map.insert(NEEDLE, 0).unwrap();
    map.range(LOWER..=UPPER)
        .entries(Order::Ascend)
        .for_each(|(key, value)| {
            assert_eq!(key, NEEDLE);
            assert_eq!(value, 0);
        })
}

#[test]
fn disjoint_crud_remains_immediately_visible_under_contention() {
    let map = concurrent::Map::<u64, Box<u64>>::default();
    let barrier = Barrier::new(9);

    std::thread::scope(|scope| {
        for worker in 0..8u64 {
            let map = &map;
            let barrier = &barrier;
            scope.spawn(move || {
                barrier.wait();
                for sequence in 0..10_000u64 {
                    let key = worker * 10_000 + sequence;
                    map.insert(key, Box::new(key + 1))
                        .unwrap_or_else(|_| panic!("disjoint key already existed: {key}"));
                    assert_eq!(map.get(&key).as_deref().copied(), Some(key + 1));
                    assert_eq!(map.remove(&key).as_deref().copied(), Some(key + 1));
                }
            });
        }
        barrier.wait();
    });

    assert!(map.all().entries(Order::Ascend).next().is_none());
}