WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/adt/btree.c


/*
 * Copyright (C) 2006 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/*
 * This B-tree has the following properties:
 * - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
 * - values (i.e. pointers to values) are stored only in leaves
 * - leaves are linked in a list
 * - technically, it is a B+-tree (because of the previous properties)
 *
 * Be carefull when using these trees. They need to allocate
 * and deallocate memory for their index nodes and as such
 * can sleep.
 */
 
#include <adt/btree.h>
#include <adt/list.h>
#include <mm/slab.h>
#include <debug.h>
#include <panic.h>
#include <typedefs.h>
#include <print.h>
 
static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
static void node_initialize(btree_node_t *node);
static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree);
static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
 
 
static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
static btree_node_t *node_combine(btree_node_t *node);
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
static bool try_insert_by_rotation_to_left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
static bool try_insert_by_rotation_to_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
static bool try_rotation_from_left(btree_node_t *rnode);
static bool try_rotation_from_right(btree_node_t *lnode);
 
#define ROOT_NODE(n)        (!(n)->parent)
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
 
#define FILL_FACTOR     ((BTREE_M-1)/2)
 
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
#define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
#define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
 
/** Create empty B-tree.
 *
 * @param t B-tree.
 */
void btree_create(btree_t *t)
{
    list_initialize(&t->leaf_head);
    t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
    node_initialize(t->root);
    list_append(&t->root->leaf_link, &t->leaf_head);
}
 
/** Destroy empty B-tree. */
void btree_destroy(btree_t *t)
{
    ASSERT(!t->root->keys);
    free(t->root);
}
 
/** Insert key-value pair into B-tree.
 *
 * @param t B-tree.
 * @param key Key to be inserted.
 * @param value Value to be inserted.
 * @param leaf_node Leaf node where the insertion should begin.
 */
void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node)
{
    btree_node_t *lnode;
   
    ASSERT(value);
   
    lnode = leaf_node;
    if (!lnode) {
        if (btree_search(t, key, &lnode)) {
            panic("B-tree %P already contains key %d\n", t, key);
        }
    }
   
    _btree_insert(t, key, value, NULL, lnode);
}
 
/** Recursively insert into B-tree.
 *
 * @param t B-tree.
 * @param key Key to be inserted.
 * @param value Value to be inserted.
 * @param rsubtree Right subtree of the inserted key.
 * @param node Start inserting into this node.
 */
void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node)
{
    if (node->keys < BTREE_MAX_KEYS) {
        /*
         * Node conatins enough space, the key can be stored immediately.
         */
        node_insert_key_and_rsubtree(node, key, value, rsubtree);
    } else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) {
        /*
         * The key-value-rsubtree triplet has been inserted because
         * some keys could have been moved to the left sibling.
         */
    } else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) {
        /*
         * The key-value-rsubtree triplet has been inserted because
         * some keys could have been moved to the right sibling.
         */
    } else {
        btree_node_t *rnode;
        __native median;
       
        /*
         * Node is full and both siblings (if both exist) are full too.
         * Split the node and insert the smallest key from the node containing
         * bigger keys (i.e. the new node) into its parent.
         */
 
        rnode = node_split(node, key, value, rsubtree, &median);
 
        if (LEAF_NODE(node)) {
            list_prepend(&rnode->leaf_link, &node->leaf_link);
        }
       
        if (ROOT_NODE(node)) {
            /*
             * We split the root node. Create new root.
             */
            t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
            node->parent = t->root;
            rnode->parent = t->root;
            node_initialize(t->root);
           
            /*
             * Left-hand side subtree will be the old root (i.e. node).
             * Right-hand side subtree will be rnode.
             */        
            t->root->subtree[0] = node;
 
            t->root->depth = node->depth + 1;
        }
        _btree_insert(t, median, NULL, rnode, node->parent);
    }  
       
}
 
/** Remove B-tree node.
 *
 * @param B-tree.
 * @param key Key to be removed from the B-tree along with its associated value.
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
 */
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
{
    btree_node_t *lnode;
   
 
    lnode = leaf_node;
    if (!lnode) {
        if (!btree_search(t, key, &lnode)) {
            panic("B-tree %P does not contain key %d\n", t, key);
        }
    }
   
    _btree_remove(t, key, lnode);
}
 
/** Recursively remove B-tree node.
 *
 * @param B-tree.
 * @param key Key to be removed from the B-tree along with its associated value.
 * @param node Node where the key being removed resides.
 */
void _btree_remove(btree_t *t, __native key, btree_node_t *node)
{
    if (ROOT_NODE(node)) {
        if (node->keys == 1 && node->subtree[0]) {
            /*
             * Free the current root and set new root.
             */
            t->root = node->subtree[0];
            t->root->parent = NULL;
            free(node);
        } else {
            /*
             * Remove the key from the root node.
             * Note that the right subtree is removed because when
             * combining two nodes, the left-side sibling is preserved
             * and the right-side sibling is freed.
             */
            node_remove_key_and_rsubtree(node, key);
        }
        return;
    }
   
    if (node->keys <= FILL_FACTOR) {
        /*
         * If the node is below the fill factor,
         * try to borrow keys from left or right sibling.
         */
        if (!try_rotation_from_left(node))
            try_rotation_from_right(node);
    }
   
    if (node->keys > FILL_FACTOR) {
        int i;
 
        /*
         * The key can be immediatelly removed.
         *
         * Note that the right subtree is removed because when
         * combining two nodes, the left-side sibling is preserved
         * and the right-side sibling is freed.
         */
        node_remove_key_and_rsubtree(node, key);
        for (i = 0; i < node->parent->keys; i++) {
            if (node->parent->key[i] == key)
                node->parent->key[i] = node->key[0];
        }
       
    } else {
        index_t idx;
        btree_node_t *rnode, *parent;
 
        /*
         * The node is below the fill factor as well as its left and right sibling.
         * Resort to combining the node with one of its siblings.
         * The node which is on the left is preserved and the node on the right is
         * freed.
         */
        parent = node->parent;
        node_remove_key_and_rsubtree(node, key);
        rnode = node_combine(node);
        if (LEAF_NODE(rnode))
            list_remove(&rnode->leaf_link);
        idx = find_key_by_subtree(parent, rnode, true);
        ASSERT((int) idx != -1);
        free(rnode);
        _btree_remove(t, parent->key[idx], parent);
    }
}
 
/** Search key in a B-tree.
 *
 * @param t B-tree.
 * @param key Key to be searched.
 * @param leaf_node Address where to put pointer to visited leaf node.
 *
 * @return Pointer to value or NULL if there is no such key.
 */
void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node)
{
    btree_node_t *cur, *next;
   
    /*
     * Iteratively descend to the leaf that can contain the searched key.
     */
    for (cur = t->root; cur; cur = next) {
 
        /* Last iteration will set this with proper leaf node address. */
        *leaf_node = cur;
       
        /*
         * The key can be in the leftmost subtree.
         * Test it separately.
         */
        if (key < cur->key[0]) {
            next = cur->subtree[0];
            continue;
        } else {
            void *val;
            int i;
       
            /*
             * Now if the key is smaller than cur->key[i]
             * it can only mean that the value is in cur->subtree[i]
             * or it is not in the tree at all.
             */
            for (i = 1; i < cur->keys; i++) {
                if (key < cur->key[i]) {
                    next = cur->subtree[i];
                    val = cur->value[i - 1];
 
                    if (LEAF_NODE(cur))
                        return key == cur->key[i - 1] ? val : NULL;
 
                    goto descend;
                }
            }
           
            /*
             * Last possibility is that the key is in the rightmost subtree.
             */
            next = cur->subtree[i];
            val = cur->value[i - 1];
            if (LEAF_NODE(cur))
                return key == cur->key[i - 1] ? val : NULL;
        }
        descend:
            ;
    }
 
    /*
     * The key was not found in the *leaf_node and is smaller than any of its keys.
     */
    return NULL;
}
 
/** Initialize B-tree node.
 *
 * @param node B-tree node.
 */
void node_initialize(btree_node_t *node)
{
    int i;
 
    node->keys = 0;
   
    /* Clean also space for the extra key. */
    for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
        node->key[i] = 0;
        node->value[i] = NULL;
        node->subtree[i] = NULL;
    }
    node->subtree[i] = NULL;
   
    node->parent = NULL;
   
    link_initialize(&node->leaf_link);
 
    link_initialize(&node->bfs_link);
    node->depth = 0;
}
 
/** Insert key-value-lsubtree triplet into B-tree node.
 *
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
 * This feature is used during insert by right rotation.
 *
 * @param node B-tree node into wich the new key is to be inserted.
 * @param key The key to be inserted.
 * @param value Pointer to value to be inserted.
 * @param lsubtree Pointer to the left subtree.
 */
void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
{
    int i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {
            int j;
       
            for (j = node->keys; j > i; j--) {
                node->key[j] = node->key[j - 1];
                node->value[j] = node->value[j - 1];
                node->subtree[j + 1] = node->subtree[j];
            }
            node->subtree[j + 1] = node->subtree[j];
            break; 
        }
    }
    node->key[i] = key;
    node->value[i] = value;
    node->subtree[i] = lsubtree;
           
    node->keys++;
}
 
/** Insert key-value-rsubtree triplet into B-tree node.
 *
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
 * This feature is used during splitting the node when the
 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
 * also makes use of this feature.
 *
 * @param node B-tree node into wich the new key is to be inserted.
 * @param key The key to be inserted.
 * @param value Pointer to value to be inserted.
 * @param rsubtree Pointer to the right subtree.
 */
void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
{
    int i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {
            int j;
       
            for (j = node->keys; j > i; j--) {
                node->key[j] = node->key[j - 1];
                node->value[j] = node->value[j - 1];
                node->subtree[j + 1] = node->subtree[j];
            }
            break; 
        }
    }
    node->key[i] = key;
    node->value[i] = value;
    node->subtree[i + 1] = rsubtree;
           
    node->keys++;
}
 
/** Remove key and its left subtree pointer from B-tree node.
 *
 * Remove the key and eliminate gaps in node->key array.
 * Note that the value pointer and the left subtree pointer
 * is removed from the node as well.
 *
 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
{
    int i, j;
   
    for (i = 0; i < node->keys; i++) {
        if (key == node->key[i]) {
            for (j = i + 1; j < node->keys; j++) {
                node->key[j - 1] = node->key[j];
                node->value[j - 1] = node->value[j];
                node->subtree[j - 1] = node->subtree[j];
            }
            node->subtree[j - 1] = node->subtree[j];
            node->keys--;
            return;
        }
    }
    panic("node %P does not contain key %d\n", node, key);
}
 
/** Remove key and its right subtree pointer from B-tree node.
 *
 * Remove the key and eliminate gaps in node->key array.
 * Note that the value pointer and the right subtree pointer
 * is removed from the node as well.
 *
 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
{
    int i, j;
   
    for (i = 0; i < node->keys; i++) {
        if (key == node->key[i]) {
            for (j = i + 1; j < node->keys; j++) {
                node->key[j - 1] = node->key[j];
                node->value[j - 1] = node->value[j];
                node->subtree[j] = node->subtree[j + 1];
            }
            node->keys--;
            return;
        }
    }
    panic("node %P does not contain key %d\n", node, key);
}
 
/** Split full B-tree node and insert new key-value-right-subtree triplet.
 *
 * This function will split a node and return pointer to a newly created
 * node containing keys greater than or equal to the greater of medians
 * (or median) of the old keys and the newly added key. It will also write
 * the median key to a memory address supplied by the caller.
 *
 * If the node being split is an index node, the median will not be
 * included in the new node. If the node is a leaf node,
 * the median will be copied there.
 *
 * @param node B-tree node wich is going to be split.
 * @param key The key to be inserted.
 * @param value Pointer to the value to be inserted.
 * @param rsubtree Pointer to the right subtree of the key being added.
 * @param median Address in memory, where the median key will be stored.
 *
 * @return Newly created right sibling of node.
 */
btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
{
    btree_node_t *rnode;
    int i, j;
 
    ASSERT(median);
    ASSERT(node->keys == BTREE_MAX_KEYS);
 
    /*
     * Use the extra space to store the extra node.
     */
    node_insert_key_and_rsubtree(node, key, value, rsubtree);
 
    /*
     * Compute median of keys.
     */
    *median = MEDIAN_HIGH(node);
       
    /*
     * Allocate and initialize new right sibling.
     */
    rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
    node_initialize(rnode);
    rnode->parent = node->parent;
    rnode->depth = node->depth;
   
    /*
     * Copy big keys, values and subtree pointers to the new right sibling.
     * If this is an index node, do not copy the median.
     */
    i = (int) INDEX_NODE(node);
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
        rnode->key[j] = node->key[i];
        rnode->value[j] = node->value[i];
        rnode->subtree[j] = node->subtree[i];
       
        /*
         * Fix parent links in subtrees.
         */
        if (rnode->subtree[j])
            rnode->subtree[j]->parent = rnode;
           
    }
    rnode->subtree[j] = node->subtree[i];
    if (rnode->subtree[j])
        rnode->subtree[j]->parent = rnode;
 
    rnode->keys = j;    /* Set number of keys of the new node. */
    node->keys /= 2;    /* Shrink the old node. */
       
    return rnode;
}
 
/** Combine node with any of its siblings.
 *
 * The siblings are required to be below the fill factor.
 *
 * @param node Node to combine with one of its siblings.
 *
 * @return Pointer to the rightmost of the two nodes.
 */
btree_node_t *node_combine(btree_node_t *node)
{
    index_t idx;
    btree_node_t *rnode;
    int i;
 
    ASSERT(!ROOT_NODE(node));
   
    idx = find_key_by_subtree(node->parent, node, false);
    if (idx == node->parent->keys) {
        /*
         * Rightmost subtree of its parent, combine with the left sibling.
         */
        idx--;
        rnode = node;
        node = node->parent->subtree[idx];
    } else {
        rnode = node->parent->subtree[idx + 1];
    }
 
    /* Index nodes need to insert parent node key in between left and right node. */
    if (INDEX_NODE(node))
        node->key[node->keys++] = node->parent->key[idx];
   
    /* Copy the key-value-subtree triplets from the right node. */
    for (i = 0; i < rnode->keys; i++) {
        node->key[node->keys + i] = rnode->key[i];
        node->value[node->keys + i] = rnode->value[i];
        if (INDEX_NODE(node)) {
            node->subtree[node->keys + i] = rnode->subtree[i];
            rnode->subtree[i]->parent = node;
        }
    }
    if (INDEX_NODE(node)) {
        node->subtree[node->keys + i] = rnode->subtree[i];
        rnode->subtree[i]->parent = node;
    }
 
    node->keys += rnode->keys;
 
    return rnode;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
/** Find key by its left or right subtree.
 *
 * @param node B-tree node.
 * @param subtree Left or right subtree of a key found in node.
 * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
 *
 * @return Index of the key associated with the subtree.
 */
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
{
    int i;
   
    for (i = 0; i < node->keys + 1; i++) {
        if (subtree == node->subtree[i])
            return i - (int) (right != false);
    }
    panic("node %P does not contain subtree %P\n", node, subtree);
}
 
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
 *
 * The biggest key and its value and right subtree is rotated from the left node
 * to the right. If the node is an index node, than the parent node key belonging to
 * the left node takes part in the rotation.
 *
 * @param lnode Left sibling.
 * @param rnode Right sibling.
 * @param idx Index of the parent node key that is taking part in the rotation.
 */
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
{
    __native key;
 
    key = lnode->key[lnode->keys - 1];
       
    if (LEAF_NODE(lnode)) {
        void *value;
 
        value = lnode->value[lnode->keys - 1];
        node_remove_key_and_rsubtree(lnode, key);
        node_insert_key_and_lsubtree(rnode, key, value, NULL);
        lnode->parent->key[idx] = key;
    } else {
        btree_node_t *rsubtree;
 
        rsubtree = lnode->subtree[lnode->keys];
        node_remove_key_and_rsubtree(lnode, key);
        node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
        lnode->parent->key[idx] = key;
 
        /* Fix parent link of the reconnected right subtree. */
        rsubtree->parent = rnode;
    }
 
}
 
/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
 *
 * The smallest key and its value and left subtree is rotated from the right node
 * to the left. If the node is an index node, than the parent node key belonging to
 * the right node takes part in the rotation.
 *
 * @param lnode Left sibling.
 * @param rnode Right sibling.
 * @param idx Index of the parent node key that is taking part in the rotation.
 */
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
{
    __native key;
 
    key = rnode->key[0];
       
    if (LEAF_NODE(rnode)) {
        void *value;
 
        value = rnode->value[0];
        node_remove_key_and_lsubtree(rnode, key);
        node_insert_key_and_rsubtree(lnode, key, value, NULL);
        rnode->parent->key[idx] = rnode->key[0];
    } else {
        btree_node_t *lsubtree;
 
        lsubtree = rnode->subtree[0];
        node_remove_key_and_lsubtree(rnode, key);
        node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
        rnode->parent->key[idx] = key;
 
        /* Fix parent link of the reconnected left subtree. */
        lsubtree->parent = lnode;
    }
 
}
 
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
 *
 * Left sibling of the node (if it exists) is checked for free space.
 * If there is free space, the key is inserted and the smallest key of
 * the node is moved there. The index node which is the parent of both
 * nodes is fixed.
 *
 * @param node B-tree node.
 * @param inskey Key to be inserted.
 * @param insvalue Value to be inserted.
 * @param rsubtree Right subtree of inskey.
 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_insert_by_rotation_to_left(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
{
    index_t idx;
    btree_node_t *lnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */
    if (ROOT_NODE(node))
        return false;
   
    idx = find_key_by_subtree(node->parent, node, true);
    if ((int) idx == -1) {
        /*
         * If this node is the leftmost subtree of its parent,
         * the rotation can not be done.
         */
        return false;
    }
       
    lnode = node->parent->subtree[idx];
    if (lnode->keys < BTREE_MAX_KEYS) {
        /*
         * The rotaion can be done. The left sibling has free space.
         */
        node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
        rotate_from_right(lnode, node, idx);
        return true;
    }
 
    return false;
}
 
/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
 *
 * Right sibling of the node (if it exists) is checked for free space.
 * If there is free space, the key is inserted and the biggest key of
 * the node is moved there. The index node which is the parent of both
 * nodes is fixed.
 *
 * @param node B-tree node.
 * @param inskey Key to be inserted.
 * @param insvalue Value to be inserted.
 * @param rsubtree Right subtree of inskey.
 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_insert_by_rotation_to_right(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
{
    index_t idx;
    btree_node_t *rnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */
    if (ROOT_NODE(node))
        return false;
   
    idx = find_key_by_subtree(node->parent, node, false);
    if (idx == node->parent->keys) {
        /*
         * If this node is the rightmost subtree of its parent,
         * the rotation can not be done.
         */
        return false;
    }
       
    rnode = node->parent->subtree[idx + 1];
    if (rnode->keys < BTREE_MAX_KEYS) {
        /*
         * The rotaion can be done. The right sibling has free space.
         */
        node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
        rotate_from_left(node, rnode, idx);
        return true;
    }
 
    return false;
}
 
/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
 *
 * @param rnode Node into which to add key from its left sibling or from the index node.
 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_rotation_from_left(btree_node_t *rnode)
{
    index_t idx;
    btree_node_t *lnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */
    if (ROOT_NODE(rnode))
        return false;
   
    idx = find_key_by_subtree(rnode->parent, rnode, true);
    if ((int) idx == -1) {
        /*
         * If this node is the leftmost subtree of its parent,
         * the rotation can not be done.
         */
        return false;
    }
       
    lnode = rnode->parent->subtree[idx];
    if (lnode->keys > FILL_FACTOR) {
        rotate_from_left(lnode, rnode, idx);
        return true;
    }
   
    return false;
}
 
/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
 *
 * @param rnode Node into which to add key from its right sibling or from the index node.
 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_rotation_from_right(btree_node_t *lnode)
{
    index_t idx;
    btree_node_t *rnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */
    if (ROOT_NODE(lnode))
        return false;
   
    idx = find_key_by_subtree(lnode->parent, lnode, false);
    if (idx == lnode->parent->keys) {
        /*
         * If this node is the rightmost subtree of its parent,
         * the rotation can not be done.
         */
        return false;
    }
       
    rnode = lnode->parent->subtree[idx + 1];
    if (rnode->keys > FILL_FACTOR) {
        rotate_from_right(lnode, rnode, idx);
        return true;
    }  
 
    return false;
}
 
/** Print B-tree.
 *
 * @param t Print out B-tree.
 */
void btree_print(btree_t *t)
{
    int i, depth = t->root->depth;
    link_t head, *cur;
 
    printf("Printing B-tree:\n");
    list_initialize(&head);
    list_append(&t->root->bfs_link, &head);
 
    /*
     * Use BFS search to print out the tree.
     * Levels are distinguished from one another by node->depth.
     */
    while (!list_empty(&head)) {
        link_t *hlp;
        btree_node_t *node;
       
        hlp = head.next;
        ASSERT(hlp != &head);
        node = list_get_instance(hlp, btree_node_t, bfs_link);
        list_remove(hlp);
       
        ASSERT(node);
       
        if (node->depth != depth) {
            printf("\n");
            depth = node->depth;
        }
 
        printf("(");
        for (i = 0; i < node->keys; i++) {
            printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
            if (node->depth && node->subtree[i]) {
                list_append(&node->subtree[i]->bfs_link, &head);
            }
        }
        if (node->depth && node->subtree[i]) {
            list_append(&node->subtree[i]->bfs_link, &head);
        }
        printf(")");
    }
    printf("\n");
   
    printf("Printing list of leaves:\n");
    for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
        btree_node_t *node;
       
        node = list_get_instance(cur, btree_node_t, leaf_link);
       
        ASSERT(node);
 
        printf("(");
        for (i = 0; i < node->keys; i++)
            printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
        printf(")");
    }
    printf("\n");
}
 

Rev 1142	Rev 1144
1	/*	1	/*
2	* Copyright (C) 2006 Jakub Jermar	2	* Copyright (C) 2006 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/*	29	/*
30	* This B-tree has the following properties:	30	* This B-tree has the following properties:
31	* - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)	31	* - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
32	* - values (i.e. pointers to values) are stored only in leaves	32	* - values (i.e. pointers to values) are stored only in leaves
33	* - leaves are linked in a list	33	* - leaves are linked in a list
34	* - technically, it is a B+-tree (because of the previous properties)	34	* - technically, it is a B+-tree (because of the previous properties)
35	*	35	*
36	* Be carefull when using these trees. They need to allocate	36	* Be carefull when using these trees. They need to allocate
37	* and deallocate memory for their index nodes and as such	37	* and deallocate memory for their index nodes and as such
38	* can sleep.	38	* can sleep.
39	*/	39	*/
40		40
41	#include <adt/btree.h>	41	#include <adt/btree.h>
42	#include <adt/list.h>	42	#include <adt/list.h>
43	#include <mm/slab.h>	43	#include <mm/slab.h>
44	#include <debug.h>	44	#include <debug.h>
45	#include <panic.h>	45	#include <panic.h>
46	#include <typedefs.h>	46	#include <typedefs.h>
47	#include <print.h>	47	#include <print.h>
48		48
49	static void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node);	49	static void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node);
50	static void _btree_remove(btree_t t, __native key, btree_node_t node);	50	static void _btree_remove(btree_t t, __native key, btree_node_t node);
51	static void node_initialize(btree_node_t *node);	51	static void node_initialize(btree_node_t *node);
52	static void node_insert_key_and_lsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	52	static void node_insert_key_and_lsubtree(btree_node_t node, __native key, void value, btree_node_t *lsubtree);
53	static void node_insert_key_and_rsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	53	static void node_insert_key_and_rsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree);
54	static btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median);	-
55	static btree_node_t node_combine(btree_node_t node);	-
56	static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);	54	static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
57	static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);	55	static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
-		56	static btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median);
-		57	static btree_node_t node_combine(btree_node_t node);
58	static index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right);	58	static index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right);
59	static void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx);	59	static void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx);
60	static void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx);	60	static void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx);
61	static bool try_insert_by_rotation_to_left(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	61	static bool try_insert_by_rotation_to_left(btree_node_t node, __native key, void value, btree_node_t *rsubtree);
62	static bool try_insert_by_rotation_to_right(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	62	static bool try_insert_by_rotation_to_right(btree_node_t node, __native key, void value, btree_node_t *rsubtree);
63	static bool try_rotation_from_left(btree_node_t *rnode);	63	static bool try_rotation_from_left(btree_node_t *rnode);
64	static bool try_rotation_from_right(btree_node_t *lnode);	64	static bool try_rotation_from_right(btree_node_t *lnode);
65		65
66	#define ROOT_NODE(n) (!(n)->parent)	66	#define ROOT_NODE(n) (!(n)->parent)
67	#define INDEX_NODE(n) ((n)->subtree[0] != NULL)	67	#define INDEX_NODE(n) ((n)->subtree[0] != NULL)
68	#define LEAF_NODE(n) ((n)->subtree[0] == NULL)	68	#define LEAF_NODE(n) ((n)->subtree[0] == NULL)
69		69
70	#define FILL_FACTOR ((BTREE_M-1)/2)	70	#define FILL_FACTOR ((BTREE_M-1)/2)
71		71
72	#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)	72	#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
73	#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2)	73	#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2)
74	#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]);	74	#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]);
75	#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]);	75	#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]);
76		76
77	/** Create empty B-tree.	77	/** Create empty B-tree.
78	*	78	*
79	* @param t B-tree.	79	* @param t B-tree.
80	*/	80	*/
81	void btree_create(btree_t *t)	81	void btree_create(btree_t *t)
82	{	82	{
83	list_initialize(&t->leaf_head);	83	list_initialize(&t->leaf_head);
84	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	84	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
85	node_initialize(t->root);	85	node_initialize(t->root);
86	list_append(&t->root->leaf_link, &t->leaf_head);	86	list_append(&t->root->leaf_link, &t->leaf_head);
87	}	87	}
88		88
89	/** Destroy empty B-tree. */	89	/** Destroy empty B-tree. */
90	void btree_destroy(btree_t *t)	90	void btree_destroy(btree_t *t)
91	{	91	{
92	ASSERT(!t->root->keys);	92	ASSERT(!t->root->keys);
93	free(t->root);	93	free(t->root);
94	}	94	}
95		95
96	/** Insert key-value pair into B-tree.	96	/** Insert key-value pair into B-tree.
97	*	97	*
98	* @param t B-tree.	98	* @param t B-tree.
99	* @param key Key to be inserted.	99	* @param key Key to be inserted.
100	* @param value Value to be inserted.	100	* @param value Value to be inserted.
101	* @param leaf_node Leaf node where the insertion should begin.	101	* @param leaf_node Leaf node where the insertion should begin.
102	*/	102	*/
103	void btree_insert(btree_t t, __native key, void value, btree_node_t *leaf_node)	103	void btree_insert(btree_t t, __native key, void value, btree_node_t *leaf_node)
104	{	104	{
105	btree_node_t *lnode;	105	btree_node_t *lnode;
106		106
107	ASSERT(value);	107	ASSERT(value);
108		108
109	lnode = leaf_node;	109	lnode = leaf_node;
110	if (!lnode) {	110	if (!lnode) {
111	if (btree_search(t, key, &lnode)) {	111	if (btree_search(t, key, &lnode)) {
112	panic("B-tree %P already contains key %d\n", t, key);	112	panic("B-tree %P already contains key %d\n", t, key);
113	}	113	}
114	}	114	}
115		115
116	_btree_insert(t, key, value, NULL, lnode);	116	_btree_insert(t, key, value, NULL, lnode);
117	}	117	}
118		118
119	/** Recursively insert into B-tree.	119	/** Recursively insert into B-tree.
120	*	120	*
121	* @param t B-tree.	121	* @param t B-tree.
122	* @param key Key to be inserted.	122	* @param key Key to be inserted.
123	* @param value Value to be inserted.	123	* @param value Value to be inserted.
124	* @param rsubtree Right subtree of the inserted key.	124	* @param rsubtree Right subtree of the inserted key.
125	* @param node Start inserting into this node.	125	* @param node Start inserting into this node.
126	*/	126	*/
127	void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node)	127	void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node)
128	{	128	{
129	if (node->keys < BTREE_MAX_KEYS) {	129	if (node->keys < BTREE_MAX_KEYS) {
130	/*	130	/*
131	* Node conatins enough space, the key can be stored immediately.	131	* Node conatins enough space, the key can be stored immediately.
132	*/	132	*/
133	node_insert_key_and_rsubtree(node, key, value, rsubtree);	133	node_insert_key_and_rsubtree(node, key, value, rsubtree);
134	} else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) {	134	} else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) {
135	/*	135	/*
136	* The key-value-rsubtree triplet has been inserted because	136	* The key-value-rsubtree triplet has been inserted because
137	* some keys could have been moved to the left sibling.	137	* some keys could have been moved to the left sibling.
138	*/	138	*/
139	} else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) {	139	} else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) {
140	/*	140	/*
141	* The key-value-rsubtree triplet has been inserted because	141	* The key-value-rsubtree triplet has been inserted because
142	* some keys could have been moved to the right sibling.	142	* some keys could have been moved to the right sibling.
143	*/	143	*/
144	} else {	144	} else {
145	btree_node_t *rnode;	145	btree_node_t *rnode;
146	__native median;	146	__native median;
147		147
148	/*	148	/*
149	* Node is full and both siblings (if both exist) are full too.	149	* Node is full and both siblings (if both exist) are full too.
150	* Split the node and insert the smallest key from the node containing	150	* Split the node and insert the smallest key from the node containing
151	* bigger keys (i.e. the new node) into its parent.	151	* bigger keys (i.e. the new node) into its parent.
152	*/	152	*/
153		153
154	rnode = node_split(node, key, value, rsubtree, &median);	154	rnode = node_split(node, key, value, rsubtree, &median);
155		155
156	if (LEAF_NODE(node)) {	156	if (LEAF_NODE(node)) {
157	list_append(&rnode->leaf_link, &node->leaf_link);	157	list_prepend(&rnode->leaf_link, &node->leaf_link);
158	}	158	}
159		159
160	if (ROOT_NODE(node)) {	160	if (ROOT_NODE(node)) {
161	/*	161	/*
162	* We split the root node. Create new root.	162	* We split the root node. Create new root.
163	*/	163	*/
164	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	164	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
165	node->parent = t->root;	165	node->parent = t->root;
166	rnode->parent = t->root;	166	rnode->parent = t->root;
167	node_initialize(t->root);	167	node_initialize(t->root);
168		168
169	/*	169	/*
170	* Left-hand side subtree will be the old root (i.e. node).	170	* Left-hand side subtree will be the old root (i.e. node).
171	* Right-hand side subtree will be rnode.	171	* Right-hand side subtree will be rnode.
172	*/	172	*/
173	t->root->subtree[0] = node;	173	t->root->subtree[0] = node;
174		174
175	t->root->depth = node->depth + 1;	175	t->root->depth = node->depth + 1;
176	}	176	}
177	_btree_insert(t, median, NULL, rnode, node->parent);	177	_btree_insert(t, median, NULL, rnode, node->parent);
178	}	178	}
179		179
180	}	180	}
181		181
182	/** Remove B-tree node.	182	/** Remove B-tree node.
183	*	183	*
184	* @param B-tree.	184	* @param B-tree.
185	* @param key Key to be removed from the B-tree along with its associated value.	185	* @param key Key to be removed from the B-tree along with its associated value.
186	* @param leaf_node If not NULL, pointer to the leaf node where the key is found.	186	* @param leaf_node If not NULL, pointer to the leaf node where the key is found.
187	*/	187	*/
188	void btree_remove(btree_t t, __native key, btree_node_t leaf_node)	188	void btree_remove(btree_t t, __native key, btree_node_t leaf_node)
189	{	189	{
190	btree_node_t *lnode;	190	btree_node_t *lnode;
191		191
192	panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);	-
193	lnode = leaf_node;	192	lnode = leaf_node;
194	if (!lnode) {	193	if (!lnode) {
195	if (!btree_search(t, key, &lnode)) {	194	if (!btree_search(t, key, &lnode)) {
196	panic("B-tree %P does not contain key %d\n", t, key);	195	panic("B-tree %P does not contain key %d\n", t, key);
197	}	196	}
198	}	197	}
199		198
200	_btree_remove(t, key, lnode);	199	_btree_remove(t, key, lnode);
201	}	200	}
202		201
203	/** Recursively remove B-tree node.	202	/** Recursively remove B-tree node.
204	*	203	*
205	* @param B-tree.	204	* @param B-tree.
206	* @param key Key to be removed from the B-tree along with its associated value.	205	* @param key Key to be removed from the B-tree along with its associated value.
207	* @param node Node where the key being removed resides.	206	* @param node Node where the key being removed resides.
208	*/	207	*/
209	void _btree_remove(btree_t t, __native key, btree_node_t node)	208	void _btree_remove(btree_t t, __native key, btree_node_t node)
210	{	209	{
211	if (ROOT_NODE(node)) {	210	if (ROOT_NODE(node)) {
212	if (node->keys == 1 && node->subtree[0]) {	211	if (node->keys == 1 && node->subtree[0]) {
213	/*	212	/*
214	* Free the current root and set new root.	213	* Free the current root and set new root.
215	*/	214	*/
216	t->root = node->subtree[0];	215	t->root = node->subtree[0];
217	t->root->parent = NULL;	216	t->root->parent = NULL;
218	free(node);	217	free(node);
219	} else {	218	} else {
220	/*	219	/*
221	* Remove the key from the root node.	220	* Remove the key from the root node.
222	* Note that the right subtree is removed because when	221	* Note that the right subtree is removed because when
223	* combining two nodes, the left-side sibling is preserved	222	* combining two nodes, the left-side sibling is preserved
224	* and the right-side sibling is freed.	223	* and the right-side sibling is freed.
225	*/	224	*/
226	node_remove_key_and_rsubtree(node, key);	225	node_remove_key_and_rsubtree(node, key);
227	}	226	}
228	return;	227	return;
229	}	228	}
230		229
231	if (node->keys <= FILL_FACTOR) {	230	if (node->keys <= FILL_FACTOR) {
232	/*	231	/*
233	* If the node is below the fill factor,	232	* If the node is below the fill factor,
234	* try to borrow keys from left or right sibling.	233	* try to borrow keys from left or right sibling.
235	*/	234	*/
236	if (!try_rotation_from_left(node))	235	if (!try_rotation_from_left(node))
237	try_rotation_from_right(node);	236	try_rotation_from_right(node);
238	}	237	}
239		238
240	if (node->keys > FILL_FACTOR) {	239	if (node->keys > FILL_FACTOR) {
241	int i;	240	int i;
242		241
243	/*	242	/*
244	* The key can be immediatelly removed.	243	* The key can be immediatelly removed.
245	*	244	*
246	* Note that the right subtree is removed because when	245	* Note that the right subtree is removed because when
247	* combining two nodes, the left-side sibling is preserved	246	* combining two nodes, the left-side sibling is preserved
248	* and the right-side sibling is freed.	247	* and the right-side sibling is freed.
249	*/	248	*/
250	node_remove_key_and_rsubtree(node, key);	249	node_remove_key_and_rsubtree(node, key);
251	for (i = 0; i < node->parent->keys; i++) {	250	for (i = 0; i < node->parent->keys; i++) {
252	if (node->parent->key[i] == key)	251	if (node->parent->key[i] == key)
253	node->parent->key[i] = node->key[0];	252	node->parent->key[i] = node->key[0];
254	}	253	}
255		254
256	} else {	255	} else {
257	index_t idx;	256	index_t idx;
258	btree_node_t rnode, parent;	257	btree_node_t rnode, parent;
259		258
260	/*	259	/*
261	* The node is below the fill factor as well as its left and right sibling.	260	* The node is below the fill factor as well as its left and right sibling.
262	* Resort to combining the node with one of its siblings.	261	* Resort to combining the node with one of its siblings.
263	* The node which is on the left is preserved and the node on the right is	262	* The node which is on the left is preserved and the node on the right is
264	* freed.	263	* freed.
265	*/	264	*/
266	parent = node->parent;	265	parent = node->parent;
267	node_remove_key_and_rsubtree(node, key);	266	node_remove_key_and_rsubtree(node, key);
268	rnode = node_combine(node);	267	rnode = node_combine(node);
269	if (LEAF_NODE(rnode))	268	if (LEAF_NODE(rnode))
270	list_remove(&rnode->leaf_link);	269	list_remove(&rnode->leaf_link);
271	idx = find_key_by_subtree(parent, rnode, true);	270	idx = find_key_by_subtree(parent, rnode, true);
272	ASSERT((int) idx != -1);	271	ASSERT((int) idx != -1);
273	free(rnode);	272	free(rnode);
274	_btree_remove(t, parent->key[idx], parent);	273	_btree_remove(t, parent->key[idx], parent);
275	}	274	}
276	}	275	}
277		276
278	/** Search key in a B-tree.	277	/** Search key in a B-tree.
279	*	278	*
280	* @param t B-tree.	279	* @param t B-tree.
281	* @param key Key to be searched.	280	* @param key Key to be searched.
282	* @param leaf_node Address where to put pointer to visited leaf node.	281	* @param leaf_node Address where to put pointer to visited leaf node.
283	*	282	*
284	* @return Pointer to value or NULL if there is no such key.	283	* @return Pointer to value or NULL if there is no such key.
285	*/	284	*/
286	void btree_search(btree_t t, __native key, btree_node_t **leaf_node)	285	void btree_search(btree_t t, __native key, btree_node_t **leaf_node)
287	{	286	{
288	btree_node_t cur, next;	287	btree_node_t cur, next;
289		288
290	/*	289	/*
291	* Iteratively descend to the leaf that can contain the searched key.	290	* Iteratively descend to the leaf that can contain the searched key.
292	*/	291	*/
293	for (cur = t->root; cur; cur = next) {	292	for (cur = t->root; cur; cur = next) {
294		293
295	/* Last iteration will set this with proper leaf node address. */	294	/* Last iteration will set this with proper leaf node address. */
296	*leaf_node = cur;	295	*leaf_node = cur;
297		296
298	/*	297	/*
299	* The key can be in the leftmost subtree.	298	* The key can be in the leftmost subtree.
300	* Test it separately.	299	* Test it separately.
301	*/	300	*/
302	if (key < cur->key[0]) {	301	if (key < cur->key[0]) {
303	next = cur->subtree[0];	302	next = cur->subtree[0];
304	continue;	303	continue;
305	} else {	304	} else {
306	void *val;	305	void *val;
307	int i;	306	int i;
308		307
309	/*	308	/*
310	* Now if the key is smaller than cur->key[i]	309	* Now if the key is smaller than cur->key[i]
311	* it can only mean that the value is in cur->subtree[i]	310	* it can only mean that the value is in cur->subtree[i]
312	* or it is not in the tree at all.	311	* or it is not in the tree at all.
313	*/	312	*/
314	for (i = 1; i < cur->keys; i++) {	313	for (i = 1; i < cur->keys; i++) {
315	if (key < cur->key[i]) {	314	if (key < cur->key[i]) {
316	next = cur->subtree[i];	315	next = cur->subtree[i];
317	val = cur->value[i - 1];	316	val = cur->value[i - 1];
318		317
319	if (LEAF_NODE(cur))	318	if (LEAF_NODE(cur))
320	return key == cur->key[i - 1] ? val : NULL;	319	return key == cur->key[i - 1] ? val : NULL;
321		320
322	goto descend;	321	goto descend;
323	}	322	}
324	}	323	}
325		324
326	/*	325	/*
327	* Last possibility is that the key is in the rightmost subtree.	326	* Last possibility is that the key is in the rightmost subtree.
328	*/	327	*/
329	next = cur->subtree[i];	328	next = cur->subtree[i];
330	val = cur->value[i - 1];	329	val = cur->value[i - 1];
331	if (LEAF_NODE(cur))	330	if (LEAF_NODE(cur))
332	return key == cur->key[i - 1] ? val : NULL;	331	return key == cur->key[i - 1] ? val : NULL;
333	}	332	}
334	descend:	333	descend:
335	;	334	;
336	}	335	}
337		336
338	/*	337	/*
339	* The key was not found in the *leaf_node and is smaller than any of its keys.	338	* The key was not found in the *leaf_node and is smaller than any of its keys.
340	*/	339	*/
341	return NULL;	340	return NULL;
342	}	341	}
343		342
344	/** Initialize B-tree node.	343	/** Initialize B-tree node.
345	*	344	*
346	* @param node B-tree node.	345	* @param node B-tree node.
347	*/	346	*/
348	void node_initialize(btree_node_t *node)	347	void node_initialize(btree_node_t *node)
349	{	348	{
350	int i;	349	int i;
351		350
352	node->keys = 0;	351	node->keys = 0;
353		352
354	/* Clean also space for the extra key. */	353	/* Clean also space for the extra key. */
355	for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {	354	for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
356	node->key[i] = 0;	355	node->key[i] = 0;
357	node->value[i] = NULL;	356	node->value[i] = NULL;
358	node->subtree[i] = NULL;	357	node->subtree[i] = NULL;
359	}	358	}
360	node->subtree[i] = NULL;	359	node->subtree[i] = NULL;
361		360
362	node->parent = NULL;	361	node->parent = NULL;
363		362
364	link_initialize(&node->leaf_link);	363	link_initialize(&node->leaf_link);
365		364
366	link_initialize(&node->bfs_link);	365	link_initialize(&node->bfs_link);
367	node->depth = 0;	366	node->depth = 0;
368	}	367	}
369		368
370	/** Insert key-value-lsubtree triplet into B-tree node.	369	/** Insert key-value-lsubtree triplet into B-tree node.
371	*	370	*
372	* It is actually possible to have more keys than BTREE_MAX_KEYS.	371	* It is actually possible to have more keys than BTREE_MAX_KEYS.
373	* This feature is used during insert by right rotation.	372	* This feature is used during insert by right rotation.
374	*	373	*
375	* @param node B-tree node into wich the new key is to be inserted.	374	* @param node B-tree node into wich the new key is to be inserted.
376	* @param key The key to be inserted.	375	* @param key The key to be inserted.
377	* @param value Pointer to value to be inserted.	376	* @param value Pointer to value to be inserted.
378	* @param lsubtree Pointer to the left subtree.	377	* @param lsubtree Pointer to the left subtree.
379	*/	378	*/
380	void node_insert_key_and_lsubtree(btree_node_t node, __native key, void value, btree_node_t *lsubtree)	379	void node_insert_key_and_lsubtree(btree_node_t node, __native key, void value, btree_node_t *lsubtree)
381	{	380	{
382	int i;	381	int i;
383		382
384	for (i = 0; i < node->keys; i++) {	383	for (i = 0; i < node->keys; i++) {
385	if (key < node->key[i]) {	384	if (key < node->key[i]) {
386	int j;	385	int j;
387		386
388	for (j = node->keys; j > i; j--) {	387	for (j = node->keys; j > i; j--) {
389	node->key[j] = node->key[j - 1];	388	node->key[j] = node->key[j - 1];
390	node->value[j] = node->value[j - 1];	389	node->value[j] = node->value[j - 1];
391	node->subtree[j + 1] = node->subtree[j];	390	node->subtree[j + 1] = node->subtree[j];
392	}	391	}
393	node->subtree[j + 1] = node->subtree[j];	392	node->subtree[j + 1] = node->subtree[j];
394	break;	393	break;
395	}	394	}
396	}	395	}
397	node->key[i] = key;	396	node->key[i] = key;
398	node->value[i] = value;	397	node->value[i] = value;
399	node->subtree[i] = lsubtree;	398	node->subtree[i] = lsubtree;
400		399
401	node->keys++;	400	node->keys++;
402	}	401	}
403		402
404	/** Insert key-value-rsubtree triplet into B-tree node.	403	/** Insert key-value-rsubtree triplet into B-tree node.
405	*	404	*
406	* It is actually possible to have more keys than BTREE_MAX_KEYS.	405	* It is actually possible to have more keys than BTREE_MAX_KEYS.
407	* This feature is used during splitting the node when the	406	* This feature is used during splitting the node when the
408	* number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation	407	* number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
409	* also makes use of this feature.	408	* also makes use of this feature.
410	*	409	*
411	* @param node B-tree node into wich the new key is to be inserted.	410	* @param node B-tree node into wich the new key is to be inserted.
412	* @param key The key to be inserted.	411	* @param key The key to be inserted.
413	* @param value Pointer to value to be inserted.	412	* @param value Pointer to value to be inserted.
414	* @param rsubtree Pointer to the right subtree.	413	* @param rsubtree Pointer to the right subtree.
415	*/	414	*/
416	void node_insert_key_and_rsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree)	415	void node_insert_key_and_rsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree)
417	{	416	{
418	int i;	417	int i;
419		418
420	for (i = 0; i < node->keys; i++) {	419	for (i = 0; i < node->keys; i++) {
421	if (key < node->key[i]) {	420	if (key < node->key[i]) {
422	int j;	421	int j;
423		422
424	for (j = node->keys; j > i; j--) {	423	for (j = node->keys; j > i; j--) {
425	node->key[j] = node->key[j - 1];	424	node->key[j] = node->key[j - 1];
426	node->value[j] = node->value[j - 1];	425	node->value[j] = node->value[j - 1];
427	node->subtree[j + 1] = node->subtree[j];	426	node->subtree[j + 1] = node->subtree[j];
428	}	427	}
429	break;	428	break;
430	}	429	}
431	}	430	}
432	node->key[i] = key;	431	node->key[i] = key;
433	node->value[i] = value;	432	node->value[i] = value;
434	node->subtree[i + 1] = rsubtree;	433	node->subtree[i + 1] = rsubtree;
435		434
436	node->keys++;	435	node->keys++;
437	}	436	}
438		437
-		438	/** Remove key and its left subtree pointer from B-tree node.
-		439	*
-		440	* Remove the key and eliminate gaps in node->key array.
-		441	* Note that the value pointer and the left subtree pointer
-		442	* is removed from the node as well.
-		443	*
-		444	* @param node B-tree node.
-		445	* @param key Key to be removed.
-		446	*/
-		447	void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
-		448	{
-		449	int i, j;
-		450
-		451	for (i = 0; i < node->keys; i++) {
-		452	if (key == node->key[i]) {
-		453	for (j = i + 1; j < node->keys; j++) {
-		454	node->key[j - 1] = node->key[j];
-		455	node->value[j - 1] = node->value[j];
-		456	node->subtree[j - 1] = node->subtree[j];
-		457	}
-		458	node->subtree[j - 1] = node->subtree[j];
-		459	node->keys--;
-		460	return;
-		461	}
-		462	}
-		463	panic("node %P does not contain key %d\n", node, key);
-		464	}
-		465
-		466	/** Remove key and its right subtree pointer from B-tree node.
-		467	*
-		468	* Remove the key and eliminate gaps in node->key array.
-		469	* Note that the value pointer and the right subtree pointer
-		470	* is removed from the node as well.
-		471	*
-		472	* @param node B-tree node.
-		473	* @param key Key to be removed.
-		474	*/
-		475	void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
-		476	{
-		477	int i, j;
-		478
-		479	for (i = 0; i < node->keys; i++) {
-		480	if (key == node->key[i]) {
-		481	for (j = i + 1; j < node->keys; j++) {
-		482	node->key[j - 1] = node->key[j];
-		483	node->value[j - 1] = node->value[j];
-		484	node->subtree[j] = node->subtree[j + 1];
-		485	}
-		486	node->keys--;
-		487	return;
-		488	}
-		489	}
-		490	panic("node %P does not contain key %d\n", node, key);
-		491	}
-		492
439	/** Split full B-tree node and insert new key-value-right-subtree triplet.	493	/** Split full B-tree node and insert new key-value-right-subtree triplet.
440	*	494	*
441	* This function will split a node and return pointer to a newly created	495	* This function will split a node and return pointer to a newly created
442	* node containing keys greater than or equal to the greater of medians	496	* node containing keys greater than or equal to the greater of medians
443	* (or median) of the old keys and the newly added key. It will also write	497	* (or median) of the old keys and the newly added key. It will also write

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/adt/btree.c – Rev 1142 → 1144