btree interface

btree.rs

 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>> {
        unimplemented!()
    }

    /// Insert a node in the B-tree.
    pub fn insert(&self, key: K, value: V, pool: &NodePool<K, V>) -> Option<Node<K, V>> {
        unimplemented!()
    }

    /// Remove a key from the B-tree.
    pub fn remove(&self, key: K, pool: &NodePool<K, V>) -> bool {
        unimplemented!()
    }
}