btree_insert.rs

fn insert_node<K: Eq + Ord, V>(tree: &mut BTree<K, V>, key: K,
                               value: V) -> bool {
    debug!("insert key-value pair: %? -> %?", key, value);

    if tree.is_empty() {
        insert_leaf(tree, 0, key, value);
        return true;
    }

    let capacity = tree.nodes.len();

    // If the node contains fewer than the maximum legal number of
    // elements, then there is room for the new element.
    if tree.used < capacity {
        // Insert the new element in the node, keeping the node's elements
        // ordered.
        let mut pos = 0;

        while pos < capacity {
            debug!("pos: %u", pos);

            match tree.nodes[pos] {
                Some(TreeNode { key: ref k, value: ref mut tree }) => {
                    if key < *k {
                        tree.insert(key, value);
                        break;
                    } else if key == *k {
                        fail!("TODO: key == *k");
                    }
                }
                Some(TreeLeaf { key: ref k, value: ref mut v }) => {
                    if key < *k {
                        let mut i = capacity - 1;

                        while i >= pos {
                            match tree.nodes[i] {
                                Some(_) => {
                                    swap(&mut tree.nodes[i + 1],
                                         &mut tree.nodes[i]);
                                }
                                None => { }
                            }

                            i -= 1;
                        }

                        replace(v, value);
                        break;
                    } else if key == *k {
                        replace(v, value);
                        break;
                    }
                }
                None => {
                    insert_leaf(tree, pos, key, value);
                    break;
                }
            }

            pos += 1;
        }

        assert!(pos < capacity);

        // TODO: move into right node.

        true
    }
    // Otherwise the node is full, evenly split it into two nodes.
    else {
        fail!("node is full. Not implemented yet");
    }
}

/*
btree.rs:173:41: 173:62 error: cannot borrow `(*tree).nodes[]` as mutable because it is also borrowed as immutable
btree.rs:173                                     swap(&mut tree.nodes[i + 1],
                                                      ^~~~~~~~~~~~~~~~~~~~~
btree.rs:166:37: 166:42 note: second borrow of `(*tree).nodes[]` occurs here
btree.rs:166                 Some(TreeLeaf { key: ref k, value: ref mut v }) => {
                                                  ^~~~~
btree.rs:173:41: 173:62 error: cannot borrow `(*tree).nodes[]` as mutable more than once at a time
btree.rs:173                                     swap(&mut tree.nodes[i + 1],
                                                      ^~~~~~~~~~~~~~~~~~~~~
btree.rs:166:51: 166:60 note: second borrow of `(*tree).nodes[]` as mutable occurs here
btree.rs:166                 Some(TreeLeaf { key: ref k, value: ref mut v }) => {
                                                                ^~~~~~~~~
*/