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



 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/*
 * This B-tree has the following properties:
 * - it is a ballanced 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

#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))]);
 
static slab_cache_t *btree_node_slab;
 
/** Initialize B-trees. */
void btree_init(void)
{
    btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
}
 
/** Create empty B-tree.
 *
 * @param t B-tree.
 */
void btree_create(btree_t *t)
{
    list_initialize(&t->leaf_head);
    t->root = (btree_node_t *) slab_alloc(btree_node_slab, 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);
    slab_free(btree_node_slab, t->root);
}
 
/** Insert key-value pair into B-tree.
 *
 * @param t B-tree.

       
        if (ROOT_NODE(node)) {
            /*
             * We split the root node. Create new root.
             */
            t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
            node->parent = t->root;
            rnode->parent = t->root;
            node_initialize(t->root);
           
            /*

            /*
             * Free the current root and set new root.
             */
            t->root = node->subtree[0];
            t->root->parent = NULL;
            slab_free(btree_node_slab, 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

        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);
        slab_free(btree_node_slab, rnode);
        _btree_remove(t, parent->key[idx], parent);
    }
}
 
/** Search key in a B-tree.

    *median = MEDIAN_HIGH(node);
       
    /*
     * Allocate and initialize new right sibling.
     */
    rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
    node_initialize(rnode);
    rnode->parent = node->parent;
    rnode->depth = node->depth;
   
    /*

Rev 1150	Rev 1164
Line 26...	Line 26...
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 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
Line 72...	Line 72...
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	static slab_cache_t *btree_node_slab;
-		78
-		79	/** Initialize B-trees. */
-		80	void btree_init(void)
-		81	{
-		82	btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
-		83	}
-		84
77	/** Create empty B-tree.	85	/** Create empty B-tree.
78	*	86	*
79	* @param t B-tree.	87	* @param t B-tree.
80	*/	88	*/
81	void btree_create(btree_t *t)	89	void btree_create(btree_t *t)
82	{	90	{
83	list_initialize(&t->leaf_head);	91	list_initialize(&t->leaf_head);
84	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	92	t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
85	node_initialize(t->root);	93	node_initialize(t->root);
86	list_append(&t->root->leaf_link, &t->leaf_head);	94	list_append(&t->root->leaf_link, &t->leaf_head);
87	}	95	}
88		96
89	/** Destroy empty B-tree. */	97	/** Destroy empty B-tree. */
90	void btree_destroy(btree_t *t)	98	void btree_destroy(btree_t *t)
91	{	99	{
92	ASSERT(!t->root->keys);	100	ASSERT(!t->root->keys);
93	free(t->root);	101	slab_free(btree_node_slab, t->root);
94	}	102	}
95		103
96	/** Insert key-value pair into B-tree.	104	/** Insert key-value pair into B-tree.
97	*	105	*
98	* @param t B-tree.	106	* @param t B-tree.
Line 159...	Line 167...
159		167
160	if (ROOT_NODE(node)) {	168	if (ROOT_NODE(node)) {
161	/*	169	/*
162	* We split the root node. Create new root.	170	* We split the root node. Create new root.
163	*/	171	*/
164	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	172	t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
165	node->parent = t->root;	173	node->parent = t->root;
166	rnode->parent = t->root;	174	rnode->parent = t->root;
167	node_initialize(t->root);	175	node_initialize(t->root);
168		176
169	/*	177	/*
Line 212...	Line 220...
212	/*	220	/*
213	* Free the current root and set new root.	221	* Free the current root and set new root.
214	*/	222	*/
215	t->root = node->subtree[0];	223	t->root = node->subtree[0];
216	t->root->parent = NULL;	224	t->root->parent = NULL;
217	free(node);	225	slab_free(btree_node_slab, node);
218	} else {	226	} else {
219	/*	227	/*
220	* Remove the key from the root node.	228	* Remove the key from the root node.
221	* Note that the right subtree is removed because when	229	* Note that the right subtree is removed because when
222	* combining two nodes, the left-side sibling is preserved	230	* combining two nodes, the left-side sibling is preserved
Line 267...	Line 275...
267	rnode = node_combine(node);	275	rnode = node_combine(node);
268	if (LEAF_NODE(rnode))	276	if (LEAF_NODE(rnode))
269	list_remove(&rnode->leaf_link);	277	list_remove(&rnode->leaf_link);
270	idx = find_key_by_subtree(parent, rnode, true);	278	idx = find_key_by_subtree(parent, rnode, true);
271	ASSERT((int) idx != -1);	279	ASSERT((int) idx != -1);
272	free(rnode);	280	slab_free(btree_node_slab, rnode);
273	_btree_remove(t, parent->key[idx], parent);	281	_btree_remove(t, parent->key[idx], parent);
274	}	282	}
275	}	283	}
276		284
277	/** Search key in a B-tree.	285	/** Search key in a B-tree.
Line 560...	Line 568...
560	*median = MEDIAN_HIGH(node);	568	*median = MEDIAN_HIGH(node);
561		569
562	/*	570	/*
563	* Allocate and initialize new right sibling.	571	* Allocate and initialize new right sibling.
564	*/	572	*/
565	rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);	573	rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
566	node_initialize(rnode);	574	node_initialize(rnode);
567	rnode->parent = node->parent;	575	rnode->parent = node->parent;
568	rnode->depth = node->depth;	576	rnode->depth = node->depth;
569		577
570	/*	578	/*

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/adt/btree.c – Rev 1150 → 1164