Skip to content

Instantly share code, notes, and snippets.

@dcci dcci/
Last active Mar 1, 2017

What would you like to do?
btree interface
use std::marker::PhantomData;
/// A B-tree data structure which nodes are allocated from a pool.
pub struct BTree<K, V> {
index : u32,
unused1: PhantomData<K>,
unused2: PhantomData<V>
// A Node reference is a direct index to an element of the pool.
type NodeRef = u32;
/// An enum representing a B-tree node.
/// Keys and values are required to implement Copy and Default.
pub enum Node<K, V> {
Inner {
size: u8,
keys: [K; 7],
nodes: [NodeRef; 8],
Leaf {
size: u8,
keys: [K; 7],
values: [V; 7],
/// Memory pool for nodes.
pub struct NodePool<K, V> {
// The array containing the nodes.
data : Vec<Node<K, V>>,
// A free list
freelist : Vec<Node<K, V>>
impl<K: Copy + Default, V: Copy + Default> NodePool<K, V> {
/// Create a new NodePool.
pub fn new() -> NodePool<K, V> {
NodePool {
data : Vec::new(),
freelist : Vec::new()
impl<K: Copy + Default, V: Copy + Default> BTree<K, V> {
/// Get a B-tree node.
pub fn get(&self, index: u32, pool: &NodePool<K, V>) -> Option<Node<K, V>> {
/// Insert a node in the B-tree.
pub fn insert(&self, key: K, value: V, pool: &NodePool<K, V>) -> Option<Node<K, V>> {
/// Remove a key from the B-tree.
pub fn remove(&self, key: K, pool: &NodePool<K, V>) -> bool {
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.