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 tree (i.e. BTREE_M = 4)
 * - 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)
 *
 * Some of the functions below take pointer to the right-hand
 * side subtree pointer as parameter. Note that this is sufficient
 * because:
 *  - New root node is passed the left-hand side subtree pointer
 *    directly.
 *  - node_split() always creates the right sibling and preserves
 *    the original node (which becomes the left sibling).
 *    There is always pointer to the left-hand side subtree
 *    (i.e. left sibling) in the parent node.
 *
 * 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 node_initialize(btree_node_t *node);
static void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
void node_remove_key(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);
 
#define ROOT_NODE(n)        (!(n)->parent)
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
 
#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(node, key, value, rsubtree);
    } else {
        btree_node_t *rnode;
        __native median;
       
        /*
         * Node is full.
         * Split it and insert the smallest key from the node containing
         * bigger keys (i.e. the original node) into its parent.
         */
 
        rnode = node_split(node, key, value, rsubtree, &median);
 
        if (LEAF_NODE(node)) {
            list_append(&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);
    }  
       
}
 
/* TODO */
void btree_remove(btree_t *t, __native key)
{
}
 
/** 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;
}
 
/** Get pointer to value with the smallest key within the node.
 *
 * Can be only used on leaf-level nodes.
 *
 * @param node B-tree node.
 *
 * @return Pointer to value assiciated with the smallest key.
 */
void *btree_node_min(btree_node_t *node)
{
    ASSERT(LEAF_NODE(node));
    ASSERT(node->keys);
    return node->value[0];
}
 
/** Get pointer to value with the biggest key within the node.
 *
 * Can be only used on leaf-level nodes.
 *
 * @param node B-tree node.
 *
 * @return Pointer to value assiciated with the biggest key.
 */
void *btree_node_max(btree_node_t *node)
{
    ASSERT(LEAF_NODE(node));
    ASSERT(node->keys);
    return node->value[node->keys - 1];
}
 
/** 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-right-subtree triplet into B-tree non-full 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.
 *
 * @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(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++;
}
 
/** 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(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;
}
 
/** Remove key from B-tree node.
 *
 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key(btree_node_t *node, __native key)
{
}
 
/** Print B-tree.
 *
 * @param t Print out B-tree.
 */
void btree_print(btree_t *t)
{
    int i, depth = t->root->depth;
    link_t head;
   
    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,", node->key[i]);
            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");
}
 

Rev 1121	Rev 1134
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 tree (i.e. BTREE_M = 4)	31	* - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4)
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	* Some of the functions below take pointer to the right-hand	36	* Some of the functions below take pointer to the right-hand
37	* side subtree pointer as parameter. Note that this is sufficient	37	* side subtree pointer as parameter. Note that this is sufficient
38	* because:	38	* because:
39	* - New root node is passed the left-hand side subtree pointer	39	* - New root node is passed the left-hand side subtree pointer
40	* directly.	40	* directly.
41	* - node_split() always creates the right sibling and preserves	41	* - node_split() always creates the right sibling and preserves
42	* the original node (which becomes the left sibling).	42	* the original node (which becomes the left sibling).
43	* There is always pointer to the left-hand side subtree	43	* There is always pointer to the left-hand side subtree
44	* (i.e. left sibling) in the parent node.	44	* (i.e. left sibling) in the parent node.
-		45	*
-		46	* Be carefull when using these trees. They need to allocate
-		47	* and deallocate memory for their index nodes and as such
-		48	* can sleep.
45	*/	49	*/
46		50
47	#include <adt/btree.h>	51	#include <adt/btree.h>
48	#include <adt/list.h>	52	#include <adt/list.h>
49	#include <mm/slab.h>	53	#include <mm/slab.h>
50	#include <debug.h>	54	#include <debug.h>
51	#include <panic.h>	55	#include <panic.h>
52	#include <typedefs.h>	56	#include <typedefs.h>
53	#include <print.h>	57	#include <print.h>
54		58
55	static void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node);	59	static void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node);
56	static void node_initialize(btree_node_t *node);	60	static void node_initialize(btree_node_t *node);
57	static void node_insert_key(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	61	static void node_insert_key(btree_node_t node, __native key, void value, btree_node_t *rsubtree);
-		62	void node_remove_key(btree_node_t *node, __native key);
58	static btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median);	63	static btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median);
59		64
60	#define ROOT_NODE(n) (!(n)->parent)	65	#define ROOT_NODE(n) (!(n)->parent)
61	#define INDEX_NODE(n) ((n)->subtree[0] != NULL)	66	#define INDEX_NODE(n) ((n)->subtree[0] != NULL)
62	#define LEAF_NODE(n) ((n)->subtree[0] == NULL)	67	#define LEAF_NODE(n) ((n)->subtree[0] == NULL)
63		68
64	#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)	69	#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
65	#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2)	70	#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2)
66	#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]);	71	#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]);
67	#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]);	72	#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]);
68		73
69	/** Create empty B-tree.	74	/** Create empty B-tree.
70	*	75	*
71	* @param t B-tree.	76	* @param t B-tree.
72	*/	77	*/
73	void btree_create(btree_t *t)	78	void btree_create(btree_t *t)
74	{	79	{
75	list_initialize(&t->leaf_head);	80	list_initialize(&t->leaf_head);
76	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	81	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
77	node_initialize(t->root);	82	node_initialize(t->root);
78	list_append(&t->root->leaf_link, &t->leaf_head);	83	list_append(&t->root->leaf_link, &t->leaf_head);
79	}	84	}
80		85
81	/** Destroy empty B-tree. */	86	/** Destroy empty B-tree. */
82	void btree_destroy(btree_t *t)	87	void btree_destroy(btree_t *t)
83	{	88	{
84	ASSERT(!t->root->keys);	89	ASSERT(!t->root->keys);
85	free(t->root);	90	free(t->root);
86	}	91	}
87		92
88	/** Insert key-value pair into B-tree.	93	/** Insert key-value pair into B-tree.
89	*	94	*
90	* @param t B-tree.	95	* @param t B-tree.
91	* @param key Key to be inserted.	96	* @param key Key to be inserted.
92	* @param value Value to be inserted.	97	* @param value Value to be inserted.
93	* @param leaf_node Leaf node where the insertion should begin.	98	* @param leaf_node Leaf node where the insertion should begin.
94	*/	99	*/
95	void btree_insert(btree_t t, __native key, void value, btree_node_t *leaf_node)	100	void btree_insert(btree_t t, __native key, void value, btree_node_t *leaf_node)
96	{	101	{
97	btree_node_t *lnode;	102	btree_node_t *lnode;
98		103
99	ASSERT(value);	104	ASSERT(value);
100		105
101	lnode = leaf_node;	106	lnode = leaf_node;
102	if (!lnode) {	107	if (!lnode) {
103	if (btree_search(t, key, &lnode)) {	108	if (btree_search(t, key, &lnode)) {
104	panic("B-tree %P already contains key %d\n", t, key);	109	panic("B-tree %P already contains key %d\n", t, key);
105	}	110	}
106	}	111	}
107		112
108	_btree_insert(t, key, value, NULL, lnode);	113	_btree_insert(t, key, value, NULL, lnode);
109	}	114	}
110		115
111	/** Recursively insert into B-tree.	116	/** Recursively insert into B-tree.
112	*	117	*
113	* @param t B-tree.	118	* @param t B-tree.
114	* @param key Key to be inserted.	119	* @param key Key to be inserted.
115	* @param value Value to be inserted.	120	* @param value Value to be inserted.
116	* @param rsubtree Right subtree of the inserted key.	121	* @param rsubtree Right subtree of the inserted key.
117	* @param node Start inserting into this node.	122	* @param node Start inserting into this node.
118	*/	123	*/
119	void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node)	124	void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node)
120	{	125	{
121	if (node->keys < BTREE_MAX_KEYS) {	126	if (node->keys < BTREE_MAX_KEYS) {
122	/*	127	/*
123	* Node conatins enough space, the key can be stored immediately.	128	* Node conatins enough space, the key can be stored immediately.
124	*/	129	*/
125	node_insert_key(node, key, value, rsubtree);	130	node_insert_key(node, key, value, rsubtree);
126	} else {	131	} else {
127	btree_node_t *rnode;	132	btree_node_t *rnode;
128	__native median;	133	__native median;
129		134
130	/*	135	/*
131	* Node is full.	136	* Node is full.
132	* Split it and insert the smallest key from the node containing	137	* Split it and insert the smallest key from the node containing
133	* bigger keys (i.e. the original node) into its parent.	138	* bigger keys (i.e. the original node) into its parent.
134	*/	139	*/
135		140
136	rnode = node_split(node, key, value, rsubtree, &median);	141	rnode = node_split(node, key, value, rsubtree, &median);
137		142
138	if (LEAF_NODE(node)) {	143	if (LEAF_NODE(node)) {
139	list_append(&rnode->leaf_link, &node->leaf_link);	144	list_append(&rnode->leaf_link, &node->leaf_link);
140	}	145	}
141		146
142	if (ROOT_NODE(node)) {	147	if (ROOT_NODE(node)) {
143	/*	148	/*
144	* We split the root node. Create new root.	149	* We split the root node. Create new root.
145	*/	150	*/
146		151
147	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	152	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
148	node->parent = t->root;	153	node->parent = t->root;
149	rnode->parent = t->root;	154	rnode->parent = t->root;
150	node_initialize(t->root);	155	node_initialize(t->root);
151		156
152	/*	157	/*
153	* Left-hand side subtree will be the old root (i.e. node).	158	* Left-hand side subtree will be the old root (i.e. node).
154	* Right-hand side subtree will be rnode.	159	* Right-hand side subtree will be rnode.
155	*/	160	*/
156	t->root->subtree[0] = node;	161	t->root->subtree[0] = node;
157		162
158	t->root->depth = node->depth + 1;	163	t->root->depth = node->depth + 1;
159	}	164	}
160	_btree_insert(t, median, NULL, rnode, node->parent);	165	_btree_insert(t, median, NULL, rnode, node->parent);
161	}	166	}
162		167
163	}	168	}
164		169
165	/* TODO */	170	/* TODO */
166	void btree_remove(btree_t *t, __native key)	171	void btree_remove(btree_t *t, __native key)
167	{	172	{
168	}	173	}
169		174
170	/** Search key in a B-tree.	175	/** Search key in a B-tree.
171	*	176	*
172	* @param t B-tree.	177	* @param t B-tree.
173	* @param key Key to be searched.	178	* @param key Key to be searched.
174	* @param leaf_node Address where to put pointer to visited leaf node.	179	* @param leaf_node Address where to put pointer to visited leaf node.
175	*	180	*
176	* @return Pointer to value or NULL if there is no such key.	181	* @return Pointer to value or NULL if there is no such key.
177	*/	182	*/
178	void btree_search(btree_t t, __native key, btree_node_t **leaf_node)	183	void btree_search(btree_t t, __native key, btree_node_t **leaf_node)
179	{	184	{
180	btree_node_t cur, next;	185	btree_node_t cur, next;
181	void *val = NULL;	-
182		186
183	/*	187	/*
184	* Iteratively descend to the leaf that can contain searched key.	188	* Iteratively descend to the leaf that can contain the searched key.
185	*/	189	*/
186	for (cur = t->root; cur; cur = next) {	190	for (cur = t->root; cur; cur = next) {
187	int i;	-
188		191
189	/* Last iteration will set this with proper leaf node address. */	192	/* Last iteration will set this with proper leaf node address. */
190	*leaf_node = cur;	193	*leaf_node = cur;
-		194
-		195	/*
191	for (i = 0; i < cur->keys; i++) {	196	* The key can be in the leftmost subtree.
-		197	* Test it separately.
-		198	*/
192	if (key <= cur->key[i]) {	199	if (key < cur->key[0]) {
193	val = cur->value[i];	200	next = cur->subtree[0];
194	next = cur->subtree[i];	201	continue;
-		202	} else {
-		203	void *val;
-		204	int i;
195		205
196	/*	206	/*
197	* Check if there is anywhere to descend.	207	* Now if the key is smaller than cur->key[i]
-		208	* it can only mean that the value is in cur->subtree[i]
-		209	* or it is not in the tree at all.
198	*/	210	*/
-		211	for (i = 1; i < cur->keys; i++) {
199	if (!next) {	212	if (key < cur->key[i]) {
200	/*	213	next = cur->subtree[i];
201	* Leaf-level.	214	val = cur->value[i - 1];
-		215
202	*/	216	if (LEAF_NODE(cur))
203	return (key == cur->key[i]) ? val : NULL;	217	return key == cur->key[i - 1] ? val : NULL;
204	}	218
205	goto descend;	219	goto descend;
-		220	}
206	}	221	}
-		222
-		223	/*
-		224	* Last possibility is that the key is in the rightmost subtree.
-		225	*/
-		226	next = cur->subtree[i];
-		227	val = cur->value[i - 1];
-		228	if (LEAF_NODE(cur))
-		229	return key == cur->key[i - 1] ? val : NULL;
207	}	230	}
208	next = cur->subtree[i];	-
209	descend:	231	descend:
210	;	232	;
211	}	233	}
212		234
213	/*	235	/*
214	* The key was not found in the *leaf_node and is greater than any of its keys.	236	* The key was not found in the *leaf_node and is smaller than any of its keys.
215	*/	237	*/
216	return NULL;	238	return NULL;
217	}	239	}
218		240
219	/** Get pointer to value with the smallest key within the node.	241	/** Get pointer to value with the smallest key within the node.
220	*	242	*
221	* Can be only used on leaf-level nodes.	243	* Can be only used on leaf-level nodes.
222	*	244	*
223	* @param node B-tree node.	245	* @param node B-tree node.
224	*	246	*
225	* @return Pointer to value assiciated with the smallest key.	247	* @return Pointer to value assiciated with the smallest key.
226	*/	248	*/
227	void btree_node_min(btree_node_t node)	249	void btree_node_min(btree_node_t node)
228	{	250	{
229	ASSERT(LEAF_NODE(node));	251	ASSERT(LEAF_NODE(node));
230	ASSERT(node->keys);	252	ASSERT(node->keys);
231	return node->value[0];	253	return node->value[0];
232	}	254	}
233		255
234	/** Get pointer to value with the biggest key within the node.	256	/** Get pointer to value with the biggest key within the node.
235	*	257	*
236	* Can be only used on leaf-level nodes.	258	* Can be only used on leaf-level nodes.
237	*	259	*
238	* @param node B-tree node.	260	* @param node B-tree node.
239	*	261	*
240	* @return Pointer to value assiciated with the biggest key.	262	* @return Pointer to value assiciated with the biggest key.
241	*/	263	*/
242	void btree_node_max(btree_node_t node)	264	void btree_node_max(btree_node_t node)
243	{	265	{
244	ASSERT(LEAF_NODE(node));	266	ASSERT(LEAF_NODE(node));
245	ASSERT(node->keys);	267	ASSERT(node->keys);
246	return node->value[node->keys - 1];	268	return node->value[node->keys - 1];
247	}	269	}
248		270
249	/** Initialize B-tree node.	271	/** Initialize B-tree node.
250	*	272	*
251	* @param node B-tree node.	273	* @param node B-tree node.
252	*/	274	*/
253	void node_initialize(btree_node_t *node)	275	void node_initialize(btree_node_t *node)
254	{	276	{
255	int i;	277	int i;
256		278
257	node->keys = 0;	279	node->keys = 0;
258		280
259	/* Clean also space for the extra key. */	281	/* Clean also space for the extra key. */
260	for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {	282	for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
261	node->key[i] = 0;	283	node->key[i] = 0;
262	node->value[i] = NULL;	284	node->value[i] = NULL;
263	node->subtree[i] = NULL;	285	node->subtree[i] = NULL;
264	}	286	}
265	node->subtree[i] = NULL;	287	node->subtree[i] = NULL;
266		288
267	node->parent = NULL;	289	node->parent = NULL;
268		290
269	link_initialize(&node->leaf_link);	291	link_initialize(&node->leaf_link);
270		292
271	link_initialize(&node->bfs_link);	293	link_initialize(&node->bfs_link);
272	node->depth = 0;	294	node->depth = 0;
273	}	295	}
274		296
275	/** Insert key-value-left-subtree triplet into B-tree non-full node.	297	/** Insert key-value-right-subtree triplet into B-tree non-full node.
276	*	298	*
277	* It is actually possible to have more keys than BTREE_MAX_KEYS.	299	* It is actually possible to have more keys than BTREE_MAX_KEYS.
278	* This feature is used during splitting the node when the	300	* This feature is used during splitting the node when the
279	* number of keys is BTREE_MAX_KEYS + 1.	301	* number of keys is BTREE_MAX_KEYS + 1.
280	*	302	*
281	* @param node B-tree node into wich the new key is to be inserted.	303	* @param node B-tree node into wich the new key is to be inserted.
282	* @param key The key to be inserted.	304	* @param key The key to be inserted.
283	* @param value Pointer to value to be inserted.	305	* @param value Pointer to value to be inserted.
284	* @param rsubtree Pointer to the right subtree.	306	* @param rsubtree Pointer to the right subtree.
285	*/	307	*/
286	void node_insert_key(btree_node_t node, __native key, void value, btree_node_t *rsubtree)	308	void node_insert_key(btree_node_t node, __native key, void value, btree_node_t *rsubtree)
287	{	309	{
288	int i;	310	int i;
289		311
290	for (i = 0; i < node->keys; i++) {	312	for (i = 0; i < node->keys; i++) {
291	if (key < node->key[i]) {	313	if (key < node->key[i]) {
292	int j;	314	int j;
293		315
294	for (j = node->keys; j > i; j--) {	316	for (j = node->keys; j > i; j--) {
295	node->key[j] = node->key[j - 1];	317	node->key[j] = node->key[j - 1];
296	node->value[j] = node->value[j - 1];	318	node->value[j] = node->value[j - 1];
297	node->subtree[j + 1] = node->subtree[j];	319	node->subtree[j + 1] = node->subtree[j];
298	}	320	}
299	break;	321	break;
300	}	322	}
301	}	323	}
302		324
303	node->key[i] = key;	325	node->key[i] = key;
304	node->value[i] = value;	326	node->value[i] = value;
305	node->subtree[i + 1] = rsubtree;	327	node->subtree[i + 1] = rsubtree;
306		328
307	node->keys++;	329	node->keys++;
308	}	330	}
309		331
310	/** Split full B-tree node and insert new key-value-left-subtree triplet.	332	/** Split full B-tree node and insert new key-value-right-subtree triplet.
311	*	333	*
312	* This function will split a node and return pointer to a newly created	334	* This function will split a node and return pointer to a newly created
313	* node containing keys greater than the lesser of medians (or median)	335	* node containing keys greater than or equal to the greater of medians
314	* of the old keys and the newly added key. It will also write the	336	* (or median) of the old keys and the newly added key. It will also write
315	* median key to a memory address supplied by the caller.	337	* the median key to a memory address supplied by the caller.
316	*	338	*
317	* If the node being split is an index node, the median will be	339	* If the node being split is an index node, the median will not be
318	* removed from the original node. If the node is a leaf node,	340	* included in the new node. If the node is a leaf node,
319	* the median will be preserved.	341	* the median will be copied there.
320	*	342	*
321	* @param node B-tree node wich is going to be split.	343	* @param node B-tree node wich is going to be split.
322	* @param key The key to be inserted.	344	* @param key The key to be inserted.
323	* @param value Pointer to the value to be inserted.	345	* @param value Pointer to the value to be inserted.
324	* @param rsubtree Pointer to the right subtree of the key being added.	346	* @param rsubtree Pointer to the right subtree of the key being added.
325	* @param median Address in memory, where the median key will be stored.	347	* @param median Address in memory, where the median key will be stored.
326	*	348	*
327	* @return Newly created right sibling of node.	349	* @return Newly created right sibling of node.
328	*/	350	*/
329	btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median)	351	btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median)
330	{	352	{
331	btree_node_t *rnode;	353	btree_node_t *rnode;
332	int i, j;	354	int i, j;
333		355
334	ASSERT(median);	356	ASSERT(median);
335	ASSERT(node->keys == BTREE_MAX_KEYS);	357	ASSERT(node->keys == BTREE_MAX_KEYS);
336		358
337	/*	359	/*
338	* Use the extra space to store the extra node.	360	* Use the extra space to store the extra node.
339	*/	361	*/
340	node_insert_key(node, key, value, rsubtree);	362	node_insert_key(node, key, value, rsubtree);
341		363
342	/*	364	/*
343	* Compute median of keys.	365	* Compute median of keys.
344	*/	366	*/
345	*median = MEDIAN_LOW(node);	367	*median = MEDIAN_HIGH(node);
346		368
-		369	/*
-		370	* Allocate and initialize new right sibling.
-		371	*/
347	rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	372	rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
348	node_initialize(rnode);	373	node_initialize(rnode);
349	rnode->parent = node->parent;	374	rnode->parent = node->parent;
350	rnode->depth = node->depth;	375	rnode->depth = node->depth;
351		376
352	/*	377	/*
353	* Copy big keys, values and subtree pointers to the new right sibling.	378	* Copy big keys, values and subtree pointers to the new right sibling.
-		379	* If this is an index node, do not copy the median.
354	*/	380	*/
-		381	i = (int) INDEX_NODE(node);
355	for (i = MEDIAN_LOW_INDEX(node) + 1, j = 0; i < node->keys; i++, j++) {	382	for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
356	rnode->key[j] = node->key[i];	383	rnode->key[j] = node->key[i];
357	rnode->value[j] = node->value[i];	384	rnode->value[j] = node->value[i];
358	rnode->subtree[j] = node->subtree[i];	385	rnode->subtree[j] = node->subtree[i];
359		386
360	/*	387	/*
361	* Fix parent links in subtrees.	388	* Fix parent links in subtrees.
362	*/	389	*/
363	if (rnode->subtree[j])	390	if (rnode->subtree[j])
364	rnode->subtree[j]->parent = rnode;	391	rnode->subtree[j]->parent = rnode;
365		392
366	}	393	}
367	rnode->subtree[j] = node->subtree[i];	394	rnode->subtree[j] = node->subtree[i];
368	if (rnode->subtree[j])	395	if (rnode->subtree[j])
369	rnode->subtree[j]->parent = rnode;	396	rnode->subtree[j]->parent = rnode;
370	rnode->keys = j;	-
371		397
372	/*	-
373	* Shrink the old node.	-
374	* If this is an index node, remove the median.	398	rnode->keys = j; /* Set number of keys of the new node. */
375	*/	-
376	node->keys = MEDIAN_LOW_INDEX(node) + 1;	399	node->keys /= 2; /* Shrink the old node. */
377	if (INDEX_NODE(node))	-
378	node->keys--;	-
379		400
380	return rnode;	401	return rnode;
381	}	402	}
-		403
-		404	/** Remove key from B-tree node.
-		405	*
-		406	* @param node B-tree node.
-		407	* @param key Key to be removed.
-		408	*/
-		409	void node_remove_key(btree_node_t *node, __native key)
-		410	{
-		411	}
382		412
383	/** Print B-tree.	413	/** Print B-tree.
384	*	414	*
385	* @param t Print out B-tree.	415	* @param t Print out B-tree.
386	*/	416	*/
387	void btree_print(btree_t *t)	417	void btree_print(btree_t *t)
388	{	418	{
389	int i, depth = t->root->depth;	419	int i, depth = t->root->depth;
390	link_t head;	420	link_t head;
391		421
392	list_initialize(&head);	422	list_initialize(&head);
393	list_append(&t->root->bfs_link, &head);	423	list_append(&t->root->bfs_link, &head);
394		424
395	/*	425	/*
396	* Use BFS search to print out the tree.	426	* Use BFS search to print out the tree.
397	* Levels are distinguished from one another by node->depth.	427	* Levels are distinguished from one another by node->depth.
398	*/	428	*/
399	while (!list_empty(&head)) {	429	while (!list_empty(&head)) {
400	link_t *hlp;	430	link_t *hlp;
401	btree_node_t *node;	431	btree_node_t *node;
402		432
403	hlp = head.next;	433	hlp = head.next;
404	ASSERT(hlp != &head);	434	ASSERT(hlp != &head);
405	node = list_get_instance(hlp, btree_node_t, bfs_link);	435	node = list_get_instance(hlp, btree_node_t, bfs_link);
406	list_remove(hlp);	436	list_remove(hlp);
407		437
408	ASSERT(node);	438	ASSERT(node);
409		439
410	if (node->depth != depth) {	440	if (node->depth != depth) {
411	printf("\n");	441	printf("\n");
412	depth = node->depth;	442	depth = node->depth;
413	}	443	}
414		444
415	printf("(");	445	printf("(");
416	for (i = 0; i < node->keys; i++) {	446	for (i = 0; i < node->keys; i++) {
417	printf("%d,", node->key[i]);	447	printf("%d,", node->key[i]);
418	if (node->depth && node->subtree[i]) {	448	if (node->depth && node->subtree[i]) {
419	list_append(&node->subtree[i]->bfs_link, &head);	449	list_append(&node->subtree[i]->bfs_link, &head);
420	}	450	}
421	}	451	}
422	if (node->depth && node->subtree[i]) {	452	if (node->depth && node->subtree[i]) {
423	list_append(&node->subtree[i]->bfs_link, &head);	453	list_append(&node->subtree[i]->bfs_link, &head);
424	}	454	}
425	printf(")");	455	printf(")");
426	}	456	}
427	printf("\n");	457	printf("\n");
428	}	458	}
429		459

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/adt/btree.c – Rev 1121 → 1134