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

mod common;

#[test]
#[cfg(not(miri))]
fn test_memory_usage() {
    use blart::{testing, TreeMap};
    use common::{get_profiler, test_heap};

    const KEY_LENGTH_LIMIT: usize = u8::MAX as usize;

    let keys: Vec<_> = testing::generate_keys_skewed(KEY_LENGTH_LIMIT).collect();

    let prof = get_profiler(file!());

    test_heap(&prof, |stats| {
        dhat::assert_eq!(stats.total_blocks, 0);
        dhat::assert_eq!(stats.total_bytes, 0);
    });

    {
        let keys = keys.into_iter();
        let mut tree = TreeMap::new();

        for (idx, key) in keys.enumerate() {
            tree.try_insert(key, idx).unwrap();
        }

        for (value, key) in testing::generate_keys_skewed(KEY_LENGTH_LIMIT).enumerate() {
            let result = tree.get(&key).unwrap();

            assert_eq!(result, &value);
        }
    }

    test_heap(&prof, |stats| {
        dhat::assert_eq!(stats.curr_blocks, 0);
        dhat::assert_eq!(stats.curr_bytes, 0);

        dhat::assert_eq!(stats.max_blocks, 511);
        dhat::assert_eq!(stats.max_bytes, 27218);

        let mean_blocks_per_key = (stats.max_blocks as f64) / (KEY_LENGTH_LIMIT as f64);
        let mean_bytes_per_key = (stats.max_bytes as f64) / (KEY_LENGTH_LIMIT as f64);

        eprintln!(
            "Inserting {KEY_LENGTH_LIMIT} keys, this comes to [{mean_blocks_per_key} mean blocks \
             per key] and [{mean_bytes_per_key} mean bytes per key].",
        )
    });
}