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

mod chunk;
mod inner_skew_list;
pub mod skew_list;
mod subtree;

pub type SkewList<T> = skew_list::SkewList<T>;

mod constants {
    use crate::subtree::Subtree;
    // These seem like good defaults, but they haven't been exhaustively explored.  There are a lot
    // of options regarding how to store nodes that would make larger sizes more viable.  Bringing
    // FANOUT back down to 2 would make the entire upgrade_into_existing code path unnecessary.
    pub const NODE_SIZE: usize = 16;
    pub const FANOUT: usize = 32;

    #[cfg(not(feature = "threadsafe"))]
    pub type Ref<T> = std::rc::Rc<T>;
    #[cfg(feature = "threadsafe")]
    pub type Ref<T> = std::sync::Arc<T>;

    pub type NodeValues<T> = [T; NODE_SIZE];
    pub type ChildNodes<T> = [Subtree<T>; FANOUT];
    pub use crate::chunk::{Chunk, FullChunk};

    pub const fn increment_tree_size(i: usize) -> usize {
        i * FANOUT + NODE_SIZE
    }
    pub const fn decrement_tree_size(i: usize) -> usize {
        (i - NODE_SIZE) / FANOUT
    }

    pub fn get_idx(i: usize, tree_size: usize) -> (usize, usize) {
        match tree_size {
            TREE_SIZE_0 => (i / TREE_SIZE_0, i % TREE_SIZE_0),
            TREE_SIZE_1 => (i / TREE_SIZE_1, i % TREE_SIZE_1),
            TREE_SIZE_2 => (i / TREE_SIZE_2, i % TREE_SIZE_2),
            TREE_SIZE_3 => (i / TREE_SIZE_3, i % TREE_SIZE_3),
            TREE_SIZE_4 => (i / TREE_SIZE_4, i % TREE_SIZE_4),
            TREE_SIZE_5 => (i / TREE_SIZE_5, i % TREE_SIZE_5),
            TREE_SIZE_6 => (i / TREE_SIZE_6, i % TREE_SIZE_6),
            TREE_SIZE_7 => (i / TREE_SIZE_7, i % TREE_SIZE_7),
            TREE_SIZE_8 => (i / TREE_SIZE_8, i % TREE_SIZE_8),
            TREE_SIZE_9 => (i / TREE_SIZE_9, i % TREE_SIZE_9),
            TREE_SIZE_10 => (i / TREE_SIZE_10, i % TREE_SIZE_10),
            TREE_SIZE_11 => (i / TREE_SIZE_11, i % TREE_SIZE_11),
            _ => unreachable!(),
        }
    }

    const TREE_SIZE_0: usize = NODE_SIZE;
    const TREE_SIZE_1: usize = increment_tree_size(TREE_SIZE_0);
    const TREE_SIZE_2: usize = increment_tree_size(TREE_SIZE_1);
    const TREE_SIZE_3: usize = increment_tree_size(TREE_SIZE_2);
    const TREE_SIZE_4: usize = increment_tree_size(TREE_SIZE_3);
    const TREE_SIZE_5: usize = increment_tree_size(TREE_SIZE_4);
    const TREE_SIZE_6: usize = increment_tree_size(TREE_SIZE_5);
    const TREE_SIZE_7: usize = increment_tree_size(TREE_SIZE_6);
    const TREE_SIZE_8: usize = increment_tree_size(TREE_SIZE_7);
    const TREE_SIZE_9: usize = increment_tree_size(TREE_SIZE_8);
    const TREE_SIZE_10: usize = increment_tree_size(TREE_SIZE_9);
    const TREE_SIZE_11: usize = increment_tree_size(TREE_SIZE_10);
    #[cfg(test)]
    pub const TREE_SIZE_MAX: usize = TREE_SIZE_11;
}