blart 0.5.0

An implementation of an adaptive radix tree packaged as a BTreeMap replacement
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

use crate::{
    deallocate_tree, maximum_unchecked, minimum_unchecked,
    tests_common::{generate_key_fixed_length, generate_keys_skewed, insert_unchecked},
    LeafNode, NodePtr, OpaqueNodePtr,
};

#[test]
fn leaf_tree_min_max_same() {
    let root: OpaqueNodePtr<Box<[i32; 4]>, String, 16> = NodePtr::allocate_node_ptr(
        LeafNode::with_no_siblings(Box::new([1, 2, 3, 4]), "1234".to_string()),
    )
    .to_opaque();

    let min_leaf = unsafe { minimum_unchecked(root) };
    let max_leaf = unsafe { maximum_unchecked(root) };

    assert_eq!(min_leaf, max_leaf);

    unsafe { deallocate_tree(root) }
}

#[test]
fn large_tree_same_length_keys_min_max() {
    #[cfg(not(miri))]
    const VALUE_STOPS: u8 = 5;
    #[cfg(miri)]
    const VALUE_STOPS: u8 = 2;

    let mut keys = generate_key_fixed_length([VALUE_STOPS; 3]);
    let mut root: OpaqueNodePtr<_, usize, 16> =
        NodePtr::allocate_node_ptr(LeafNode::with_no_siblings(keys.next().unwrap(), 0)).to_opaque();

    for (idx, key) in keys.enumerate() {
        root = unsafe { insert_unchecked(root, key, idx + 1).unwrap().new_root };
    }

    let min_leaf = unsafe { minimum_unchecked(root) };
    let max_leaf = unsafe { maximum_unchecked(root) };

    assert_ne!(min_leaf, max_leaf);
    let min_leaf = min_leaf.read();
    let max_leaf = max_leaf.read();
    assert!(min_leaf.key_ref() < max_leaf.key_ref());
    assert_eq!(min_leaf.key_ref().as_ref(), &[0, 0, 0]);
    if cfg!(miri) {
        assert_eq!(max_leaf.key_ref().as_ref(), &[2, 2, 2]);
    } else {
        assert_eq!(max_leaf.key_ref().as_ref(), &[5, 5, 5]);
    }

    unsafe { deallocate_tree(root) }
}

#[test]
fn skewed_tree_min_max() {
    let mut keys = generate_keys_skewed(12);

    let mut root: OpaqueNodePtr<Box<[u8]>, usize, 16> =
        NodePtr::allocate_node_ptr(LeafNode::with_no_siblings(keys.next().unwrap(), 0)).to_opaque();

    for (idx, key) in keys.enumerate() {
        root = unsafe { insert_unchecked(root, key, idx + 1).unwrap().new_root };
    }

    let min_leaf = unsafe { minimum_unchecked(root) };
    let max_leaf = unsafe { maximum_unchecked(root) };

    assert_ne!(min_leaf, max_leaf);
    let min_leaf = min_leaf.read();
    let max_leaf = max_leaf.read();
    assert!(min_leaf.key_ref() < max_leaf.key_ref());
    assert_eq!(
        min_leaf.key_ref().as_ref(),
        &[
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MIN,
            u8::MAX
        ]
    );
    assert_eq!(max_leaf.key_ref().as_ref(), &[u8::MAX]);

    unsafe { deallocate_tree(root) }
}