bplustree 0.1.0

Concurrent in-memory B+ Tree featuring optimistic lock coupling
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

use crate::{BPlusTree, Node, InternalNode, LeafNode};
use crate::latch::HybridLatch;
use smallvec::smallvec;
use crossbeam_epoch::Atomic;

use serde::Deserialize;
use std::sync::atomic::AtomicUsize;

type DefaultNode<K, V> = Node<K, V, 128, 256>;

#[derive(Deserialize, Debug)]
struct Edge {
    key: String,
    child: TreeNode
}

#[derive(Deserialize, Debug)]
struct Value {
    key: String,
    value: u64
}

#[derive(Deserialize, Debug)]
#[serde(untagged)]
enum TreeNode {
    Internal {
        edges: Vec<Edge>,
        upper_edge: Box<Option<TreeNode>>,
        lower_fence: Option<String>,
        upper_fence: Option<String>,
        sample_key: Option<String>
    },
    Leaf {
        values: Vec<Value>,
        lower_fence: Option<String>,
        upper_fence: Option<String>,
        sample_key: Option<String>
    }
}

#[derive(Deserialize, Debug)]
struct Tree {
    root: TreeNode,
    height: usize
}

fn translate_node(tree_node: TreeNode) -> Atomic<HybridLatch<DefaultNode<String, u64>>> {
    match tree_node {
        TreeNode::Internal { edges, upper_edge, lower_fence, upper_fence, sample_key } => {
            let mut out_keys = smallvec![];
            let mut out_edges = smallvec![];
            for edge in edges {
                out_keys.push(edge.key);
                out_edges.push(translate_node(edge.child));
            }

            let out_upper_edge = upper_edge.map(|tn| translate_node(tn));

            return Atomic::new(HybridLatch::new(Node::Internal(
                        InternalNode {
                            len: out_keys.len() as u16,
                            keys: out_keys,
                            edges: out_edges,
                            upper_edge: out_upper_edge,
                            lower_fence,
                            upper_fence,
                            sample_key
                        }
            )))
        }
        TreeNode::Leaf { values, lower_fence, upper_fence, sample_key } => {
            let mut out_keys = smallvec![];
            let mut out_values = smallvec![];
            for value in values {
                out_keys.push(value.key);
                out_values.push(value.value);
            }

            return Atomic::new(HybridLatch::new(Node::Leaf(
                        LeafNode {
                            len: out_keys.len() as u16,
                            keys: out_keys,
                            values: out_values,
                            lower_fence,
                            upper_fence,
                            sample_key
                        }
            )))
        }
    }
}

pub fn sample_tree<P: AsRef<std::path::Path>>(path: P) -> BPlusTree<String, u64> {
    let file = std::fs::File::open(path).expect("failed to find file");
    let tree: Tree = serde_json::from_reader(file).unwrap();
    let translated = translate_node(tree.root);
    BPlusTree {
        root: HybridLatch::new(translated),
        height: AtomicUsize::new(tree.height)
    }
}