WebSVN – HelenOS – Diff – //branches/dd/kernel/generic/src/adt/btree.c



static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
static btree_node_t *node_combine(btree_node_t *node);
static size_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, size_t idx);
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t 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);
 

 *
 * @param root Root of the subtree.
 */
void btree_destroy_subtree(btree_node_t *root)
{
    size_t i;
 
    if (root->keys) {
        for (i = 0; i < root->keys + 1; i++) {
            if (root->subtree[i])
                btree_destroy_subtree(root->subtree[i]);

        if (!try_rotation_from_left(node))
            try_rotation_from_right(node);
    }
   
    if (node->keys > FILL_FACTOR) {
        size_t i;
 
        /*
         * The key can be immediatelly removed.
         *
         * Note that the right subtree is removed because when

            if (node->parent->key[i] == key)
                node->parent->key[i] = node->key[0];
        }
       
    } else {
        size_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.

        if (key < cur->key[0]) {
            next = cur->subtree[0];
            continue;
        } else {
            void *val;
            size_t 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.

 * @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, btree_key_t key, void *value, btree_node_t *lsubtree)
{
    size_t i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {
            size_t 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];

 * @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, btree_key_t key, void *value, btree_node_t *rsubtree)
{
    size_t i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {
            size_t 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];

 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
{
    size_t 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];

 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
{
    size_t 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];

 * @return Newly created right sibling of node.
 */
btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
{
    btree_node_t *rnode;
    size_t i, j;
 
    ASSERT(median);
    ASSERT(node->keys == BTREE_MAX_KEYS);
 
    /*

   
    /*
     * Copy big keys, values and subtree pointers to the new right sibling.
     * If this is an index node, do not copy the median.
     */
    i = (size_t) 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];
       

 *
 * @return Pointer to the rightmost of the two nodes.
 */
btree_node_t *node_combine(btree_node_t *node)
{
    size_t idx;
    btree_node_t *rnode;
    size_t i;
 
    ASSERT(!ROOT_NODE(node));
   
    idx = find_key_by_subtree(node->parent, node, false);
    if (idx == node->parent->keys) {

 * @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.
 */
size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
{
    size_t i;
   
    for (i = 0; i < node->keys + 1; i++) {
        if (subtree == node->subtree[i])
            return i - (int) (right != false);
    }

 *
 * @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, size_t idx)
{
    btree_key_t key;
 
    key = lnode->key[lnode->keys - 1];
       

 *
 * @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, size_t idx)
{
    btree_key_t key;
 
    key = rnode->key[0];
       

 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
{
    size_t idx;
    btree_node_t *lnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */

 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
{
    size_t idx;
    btree_node_t *rnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */

 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_rotation_from_left(btree_node_t *rnode)
{
    size_t idx;
    btree_node_t *lnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */

 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_rotation_from_right(btree_node_t *lnode)
{
    size_t idx;
    btree_node_t *rnode;
 
    /*
     * If this is root node, the rotation can not be done.
     */

 *
 * @param t Print out B-tree.
 */
void btree_print(btree_t *t)
{
    size_t i;
    int depth = t->root->depth;
    link_t head, *cur;
 
    printf("Printing B-tree:\n");
    list_initialize(&head);

Rev 4055	Rev 4537
Line 61...	Line 61...
61	static void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);	61	static void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);
62	static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);	62	static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
63	static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);	63	static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
64	static btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median);	64	static btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median);
65	static btree_node_t node_combine(btree_node_t node);	65	static btree_node_t node_combine(btree_node_t node);
66	static index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right);	66	static size_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right);
67	static void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx);	67	static void rotate_from_right(btree_node_t lnode, btree_node_t rnode, size_t idx);
68	static void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx);	68	static void rotate_from_left(btree_node_t lnode, btree_node_t rnode, size_t idx);
69	static bool try_insert_by_rotation_to_left(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);	69	static bool try_insert_by_rotation_to_left(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);
70	static bool try_insert_by_rotation_to_right(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);	70	static bool try_insert_by_rotation_to_right(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);
71	static bool try_rotation_from_left(btree_node_t *rnode);	71	static bool try_rotation_from_left(btree_node_t *rnode);
72	static bool try_rotation_from_right(btree_node_t *lnode);	72	static bool try_rotation_from_right(btree_node_t *lnode);
73		73
Line 135...	Line 135...
135	*	135	*
136	* @param root Root of the subtree.	136	* @param root Root of the subtree.
137	*/	137	*/
138	void btree_destroy_subtree(btree_node_t *root)	138	void btree_destroy_subtree(btree_node_t *root)
139	{	139	{
140	count_t i;	140	size_t i;
141		141
142	if (root->keys) {	142	if (root->keys) {
143	for (i = 0; i < root->keys + 1; i++) {	143	for (i = 0; i < root->keys + 1; i++) {
144	if (root->subtree[i])	144	if (root->subtree[i])
145	btree_destroy_subtree(root->subtree[i]);	145	btree_destroy_subtree(root->subtree[i]);
Line 267...	Line 267...
267	if (!try_rotation_from_left(node))	267	if (!try_rotation_from_left(node))
268	try_rotation_from_right(node);	268	try_rotation_from_right(node);
269	}	269	}
270		270
271	if (node->keys > FILL_FACTOR) {	271	if (node->keys > FILL_FACTOR) {
272	count_t i;	272	size_t i;
273		273
274	/*	274	/*
275	* The key can be immediatelly removed.	275	* The key can be immediatelly removed.
276	*	276	*
277	* Note that the right subtree is removed because when	277	* Note that the right subtree is removed because when
Line 283...	Line 283...
283	if (node->parent->key[i] == key)	283	if (node->parent->key[i] == key)
284	node->parent->key[i] = node->key[0];	284	node->parent->key[i] = node->key[0];
285	}	285	}
286		286
287	} else {	287	} else {
288	index_t idx;	288	size_t idx;
289	btree_node_t rnode, parent;	289	btree_node_t rnode, parent;
290		290
291	/*	291	/*
292	* The node is below the fill factor as well as its left and right sibling.	292	* The node is below the fill factor as well as its left and right sibling.
293	* Resort to combining the node with one of its siblings.	293	* Resort to combining the node with one of its siblings.
Line 333...	Line 333...
333	if (key < cur->key[0]) {	333	if (key < cur->key[0]) {
334	next = cur->subtree[0];	334	next = cur->subtree[0];
335	continue;	335	continue;
336	} else {	336	} else {
337	void *val;	337	void *val;
338	count_t i;	338	size_t i;
339		339
340	/*	340	/*
341	* Now if the key is smaller than cur->key[i]	341	* Now if the key is smaller than cur->key[i]
342	* it can only mean that the value is in cur->subtree[i]	342	* it can only mean that the value is in cur->subtree[i]
343	* or it is not in the tree at all.	343	* or it is not in the tree at all.
Line 440...	Line 440...
440	* @param value Pointer to value to be inserted.	440	* @param value Pointer to value to be inserted.
441	* @param lsubtree Pointer to the left subtree.	441	* @param lsubtree Pointer to the left subtree.
442	*/	442	*/
443	void node_insert_key_and_lsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *lsubtree)	443	void node_insert_key_and_lsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *lsubtree)
444	{	444	{
445	count_t i;	445	size_t i;
446		446
447	for (i = 0; i < node->keys; i++) {	447	for (i = 0; i < node->keys; i++) {
448	if (key < node->key[i]) {	448	if (key < node->key[i]) {
449	count_t j;	449	size_t j;
450		450
451	for (j = node->keys; j > i; j--) {	451	for (j = node->keys; j > i; j--) {
452	node->key[j] = node->key[j - 1];	452	node->key[j] = node->key[j - 1];
453	node->value[j] = node->value[j - 1];	453	node->value[j] = node->value[j - 1];
454	node->subtree[j + 1] = node->subtree[j];	454	node->subtree[j + 1] = node->subtree[j];
Line 476...	Line 476...
476	* @param value Pointer to value to be inserted.	476	* @param value Pointer to value to be inserted.
477	* @param rsubtree Pointer to the right subtree.	477	* @param rsubtree Pointer to the right subtree.
478	*/	478	*/
479	void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree)	479	void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree)
480	{	480	{
481	count_t i;	481	size_t i;
482		482
483	for (i = 0; i < node->keys; i++) {	483	for (i = 0; i < node->keys; i++) {
484	if (key < node->key[i]) {	484	if (key < node->key[i]) {
485	count_t j;	485	size_t j;
486		486
487	for (j = node->keys; j > i; j--) {	487	for (j = node->keys; j > i; j--) {
488	node->key[j] = node->key[j - 1];	488	node->key[j] = node->key[j - 1];
489	node->value[j] = node->value[j - 1];	489	node->value[j] = node->value[j - 1];
490	node->subtree[j + 1] = node->subtree[j];	490	node->subtree[j + 1] = node->subtree[j];
Line 508...	Line 508...
508	* @param node B-tree node.	508	* @param node B-tree node.
509	* @param key Key to be removed.	509	* @param key Key to be removed.
510	*/	510	*/
511	void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)	511	void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
512	{	512	{
513	count_t i, j;	513	size_t i, j;
514		514
515	for (i = 0; i < node->keys; i++) {	515	for (i = 0; i < node->keys; i++) {
516	if (key == node->key[i]) {	516	if (key == node->key[i]) {
517	for (j = i + 1; j < node->keys; j++) {	517	for (j = i + 1; j < node->keys; j++) {
518	node->key[j - 1] = node->key[j];	518	node->key[j - 1] = node->key[j];
Line 536...	Line 536...
536	* @param node B-tree node.	536	* @param node B-tree node.
537	* @param key Key to be removed.	537	* @param key Key to be removed.
538	*/	538	*/
539	void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)	539	void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
540	{	540	{
541	count_t i, j;	541	size_t i, j;
542		542
543	for (i = 0; i < node->keys; i++) {	543	for (i = 0; i < node->keys; i++) {
544	if (key == node->key[i]) {	544	if (key == node->key[i]) {
545	for (j = i + 1; j < node->keys; j++) {	545	for (j = i + 1; j < node->keys; j++) {
546	node->key[j - 1] = node->key[j];	546	node->key[j - 1] = node->key[j];
Line 574...	Line 574...
574	* @return Newly created right sibling of node.	574	* @return Newly created right sibling of node.
575	*/	575	*/
576	btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median)	576	btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median)
577	{	577	{
578	btree_node_t *rnode;	578	btree_node_t *rnode;
579	count_t i, j;	579	size_t i, j;
580		580
581	ASSERT(median);	581	ASSERT(median);
582	ASSERT(node->keys == BTREE_MAX_KEYS);	582	ASSERT(node->keys == BTREE_MAX_KEYS);
583		583
584	/*	584	/*
Line 601...	Line 601...
601		601
602	/*	602	/*
603	* Copy big keys, values and subtree pointers to the new right sibling.	603	* Copy big keys, values and subtree pointers to the new right sibling.
604	* If this is an index node, do not copy the median.	604	* If this is an index node, do not copy the median.
605	*/	605	*/
606	i = (count_t) INDEX_NODE(node);	606	i = (size_t) INDEX_NODE(node);
607	for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {	607	for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
608	rnode->key[j] = node->key[i];	608	rnode->key[j] = node->key[i];
609	rnode->value[j] = node->value[i];	609	rnode->value[j] = node->value[i];
610	rnode->subtree[j] = node->subtree[i];	610	rnode->subtree[j] = node->subtree[i];
611		611
Line 634...	Line 634...
634	*	634	*
635	* @return Pointer to the rightmost of the two nodes.	635	* @return Pointer to the rightmost of the two nodes.
636	*/	636	*/
637	btree_node_t node_combine(btree_node_t node)	637	btree_node_t node_combine(btree_node_t node)
638	{	638	{
639	index_t idx;	639	size_t idx;
640	btree_node_t *rnode;	640	btree_node_t *rnode;
641	count_t i;	641	size_t i;
642		642
643	ASSERT(!ROOT_NODE(node));	643	ASSERT(!ROOT_NODE(node));
644		644
645	idx = find_key_by_subtree(node->parent, node, false);	645	idx = find_key_by_subtree(node->parent, node, false);
646	if (idx == node->parent->keys) {	646	if (idx == node->parent->keys) {
Line 683...	Line 683...
683	* @param subtree Left or right subtree of a key found in node.	683	* @param subtree Left or right subtree of a key found in node.
684	* @param right If true, subtree is a right subtree. If false, subtree is a left subtree.	684	* @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
685	*	685	*
686	* @return Index of the key associated with the subtree.	686	* @return Index of the key associated with the subtree.
687	*/	687	*/
688	index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right)	688	size_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right)
689	{	689	{
690	count_t i;	690	size_t i;
691		691
692	for (i = 0; i < node->keys + 1; i++) {	692	for (i = 0; i < node->keys + 1; i++) {
693	if (subtree == node->subtree[i])	693	if (subtree == node->subtree[i])
694	return i - (int) (right != false);	694	return i - (int) (right != false);
695	}	695	}
Line 704...	Line 704...
704	*	704	*
705	* @param lnode Left sibling.	705	* @param lnode Left sibling.
706	* @param rnode Right sibling.	706	* @param rnode Right sibling.
707	* @param idx Index of the parent node key that is taking part in the rotation.	707	* @param idx Index of the parent node key that is taking part in the rotation.
708	*/	708	*/
709	void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx)	709	void rotate_from_left(btree_node_t lnode, btree_node_t rnode, size_t idx)
710	{	710	{
711	btree_key_t key;	711	btree_key_t key;
712		712
713	key = lnode->key[lnode->keys - 1];	713	key = lnode->key[lnode->keys - 1];
714		714
Line 741...	Line 741...
741	*	741	*
742	* @param lnode Left sibling.	742	* @param lnode Left sibling.
743	* @param rnode Right sibling.	743	* @param rnode Right sibling.
744	* @param idx Index of the parent node key that is taking part in the rotation.	744	* @param idx Index of the parent node key that is taking part in the rotation.
745	*/	745	*/
746	void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx)	746	void rotate_from_right(btree_node_t lnode, btree_node_t rnode, size_t idx)
747	{	747	{
748	btree_key_t key;	748	btree_key_t key;
749		749
750	key = rnode->key[0];	750	key = rnode->key[0];
751		751
Line 784...	Line 784...
784	*	784	*
785	* @return True if the rotation was performed, false otherwise.	785	* @return True if the rotation was performed, false otherwise.
786	*/	786	*/
787	bool try_insert_by_rotation_to_left(btree_node_t node, btree_key_t inskey, void insvalue, btree_node_t *rsubtree)	787	bool try_insert_by_rotation_to_left(btree_node_t node, btree_key_t inskey, void insvalue, btree_node_t *rsubtree)
788	{	788	{
789	index_t idx;	789	size_t idx;
790	btree_node_t *lnode;	790	btree_node_t *lnode;
791		791
792	/*	792	/*
793	* If this is root node, the rotation can not be done.	793	* If this is root node, the rotation can not be done.
794	*/	794	*/
Line 831...	Line 831...
831	*	831	*
832	* @return True if the rotation was performed, false otherwise.	832	* @return True if the rotation was performed, false otherwise.
833	*/	833	*/
834	bool try_insert_by_rotation_to_right(btree_node_t node, btree_key_t inskey, void insvalue, btree_node_t *rsubtree)	834	bool try_insert_by_rotation_to_right(btree_node_t node, btree_key_t inskey, void insvalue, btree_node_t *rsubtree)
835	{	835	{
836	index_t idx;	836	size_t idx;
837	btree_node_t *rnode;	837	btree_node_t *rnode;
838		838
839	/*	839	/*
840	* If this is root node, the rotation can not be done.	840	* If this is root node, the rotation can not be done.
841	*/	841	*/
Line 870...	Line 870...
870	*	870	*
871	* @return True if the rotation was performed, false otherwise.	871	* @return True if the rotation was performed, false otherwise.
872	*/	872	*/
873	bool try_rotation_from_left(btree_node_t *rnode)	873	bool try_rotation_from_left(btree_node_t *rnode)
874	{	874	{
875	index_t idx;	875	size_t idx;
876	btree_node_t *lnode;	876	btree_node_t *lnode;
877		877
878	/*	878	/*
879	* If this is root node, the rotation can not be done.	879	* If this is root node, the rotation can not be done.
880	*/	880	*/
Line 905...	Line 905...
905	*	905	*
906	* @return True if the rotation was performed, false otherwise.	906	* @return True if the rotation was performed, false otherwise.
907	*/	907	*/
908	bool try_rotation_from_right(btree_node_t *lnode)	908	bool try_rotation_from_right(btree_node_t *lnode)
909	{	909	{
910	index_t idx;	910	size_t idx;
911	btree_node_t *rnode;	911	btree_node_t *rnode;
912		912
913	/*	913	/*
914	* If this is root node, the rotation can not be done.	914	* If this is root node, the rotation can not be done.
915	*/	915	*/
Line 938...	Line 938...
938	*	938	*
939	* @param t Print out B-tree.	939	* @param t Print out B-tree.
940	*/	940	*/
941	void btree_print(btree_t *t)	941	void btree_print(btree_t *t)
942	{	942	{
943	count_t i;	943	size_t i;
944	int depth = t->root->depth;	944	int depth = t->root->depth;
945	link_t head, *cur;	945	link_t head, *cur;
946		946
947	printf("Printing B-tree:\n");	947	printf("Printing B-tree:\n");
948	list_initialize(&head);	948	list_initialize(&head);

Subversion Repositories HelenOS

(root)//branches/dd/kernel/generic/src/adt/btree.c – Rev 4055 → 4537