WebSVN – HelenOS – Diff – /branches/rcu/kernel/generic/src/adt/avl.c


/*
 * Copyright (c) 2007 Vojtech Mencl
 * 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.
 */
 
/** @addtogroup genericadt
 * @{
 */
 
/**
 * @file
 * @brief   AVL tree implementation.
 *
 * This file implements AVL tree type and operations.
 *
 * Implemented AVL tree has the following properties:
 * @li It is binary search tree with non-unique keys.
 * @li Difference of heights of left and right subtree of every node is max 1.
 *
 * Every node has pointer to its parent which allows insertion of multiple identical keys
 * into tree.
 *
 * Be careful of using this tree because of base atribute, which is added to every inserted
 * node key. There is no rule in which order nodes with the same key are visited.
 */
 
#include <adt/avl.h>
#include <debug.h>
 
 
 
#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1
 
 
/** Search first occurence of given key in AVL tree.
 *
 * @param t AVL tree.
 * @param key Key to be searched.
 *
 * @return Pointer to node or NULL if there is no such key.
 */
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
    avltree_node_t *p;
   
    /*
     * Iteratively descend to the leaf that can contain the searched key.
     */
    p = t->root;
    while (p != NULL) {
        if (p->key > key)
            p = p->lft;
        else if (p->key < key)
            p = p->rgt;
        else {
            return p;
        }
    }
    return NULL;
}
 
 
/** Find node with smallest key in AVL tree.
 *
 * @param t AVL tree.
 *
 * @return Pointer to node or NULL if there is no node in the tree.
 */
avltree_node_t *avltree_find_min(avltree_t *t)
{
    avltree_node_t *p = t->root;
   
    /*
     * Check whether tree is empty.
     */
    if (!p) return NULL;
   
    /*
     * Iteratively descend to the leftmost leaf in the tree.
     */
    while (p->lft != NULL)
        p = p->lft;
   
    return p;
}
 
/** Insert new node into AVL tree.
 *
 * @param t AVL tree.
 * @param newnode New node to be inserted.
 */
void avltree_insert(avltree_t *t, avltree_node_t *newnode)
{  
    avltree_node_t *par;
    avltree_node_t *gpa;
    avltree_node_t *top;
    avltree_node_t **dpc;
    uint64_t key;
 
    ASSERT(t);
    ASSERT(newnode);
 
    /*
     * Creating absolute key.
     */
    key = newnode->key + t->base;
   
 
    /*
     * Iteratively descend to the leaf that can contain new node.
     * Last node with non-zero balance in the way to leaf is stored as top -
     * it si place of possible balance fault.
     */
    dpc = &t->root;
    gpa = NULL;
    top = t->root;
    while ((par = (*dpc)) != NULL) {
        if (par->balance != 0) {
            top = par;
        }
        gpa = par;
        dpc = par->key > key? &par->lft: &par->rgt;
    }
 
    /*
     * Initialize new node.
     */
    newnode->key = key;
    newnode->lft = NULL;
    newnode->rgt = NULL;
    newnode->par = gpa;
    newnode->balance = 0;
 
    /*
     * Insert first node into empty tree.
     */
    if (t->root == NULL) {
        *dpc = newnode;
        return;
    }
 
    /*
     * Insert new node into previously found leaf place.
     */
    *dpc = newnode;
 
    /*
     * If tree contains one node - end.
     */
    if (top == NULL) return;
 
    /*
     * Store pointer of top's father which points to the node with potentialy broken
     * balance (top).
     */
    if (top->par == NULL)
        dpc = &t->root;
    else
        if (top->par->lft == top)
            dpc = &(top->par->lft);
        else
            dpc = &(top->par->rgt);
 
    /*
     * Repair all balances on the way from top node to newly inserted node.
     */
    par = top;
    while (par != newnode) {
        if (par->key > key) {
            par->balance--;
            par = par->lft;
        } else {
            par->balance++;
            par = par->rgt;
        }
    }
   
    /*
     * To balance tree we must check and balance top node.
     */
    if (top->balance == -2) {
        par = top->lft;
        if (par->balance == -1) {
            /*
             * LL rotation.
             */
            top->lft = par->rgt;
            if (top->lft != NULL) top->lft->par = top;
            par->par = top->par;
            top->par = par;
            par->rgt = top;
            par->balance = top->balance = 0;
            *dpc = par;
        } else {
            /*
             * LR rotation.
             */
            ASSERT(par->balance == 1);
           
            gpa = par->rgt;
            par->rgt = gpa->lft;
            if (gpa->lft != NULL) gpa->lft->par = par;
            gpa->lft = par;
            par->par = gpa;
            top->lft = gpa->rgt;
            if (gpa->rgt != NULL) gpa->rgt->par = top;
            gpa->rgt = top;
            gpa->par = top->par;
            top->par = gpa;
           
            if (gpa->balance == -1) {
                par->balance = 0;
                top->balance = 1;
            } else if (gpa->balance == 0) {
                par->balance = top->balance = 0;
            } else {
                par->balance = -1;
                top->balance = 0;
            }
            gpa->balance = 0;
            *dpc = gpa;
        }
    } else if (top->balance == 2) {
        par = top->rgt;
        if (par->balance == 1) {
            /*
             * RR rotation.
             */
            top->rgt = par->lft;
            if (top->rgt != NULL) top->rgt->par = top;
            par->par = top->par;
            top->par = par;
            par->lft = top;
            par->balance = top->balance = 0;
            *dpc = par;
        } else {
            /*
             * RL rotation.
             */
            ASSERT(par->balance == -1);
           
            gpa = par->lft;
            par->lft = gpa->rgt;
            if (gpa->rgt != NULL) gpa->rgt->par = par;
            gpa->rgt = par;
            par->par = gpa;
            top->rgt = gpa->lft;
            if (gpa->lft != NULL) gpa->lft->par = top;
            gpa->lft = top;
            gpa->par = top->par;
            top->par = gpa;
 
            if (gpa->balance == 1) {
                par->balance = 0;
                top->balance = -1;
            } else if (gpa->balance == 0) {
                par->balance = top->balance = 0;
            } else {
                par->balance = 1;
                top->balance = 0;
            }
            gpa->balance = 0;
            *dpc = gpa;
        }
    } else {
        /*
         * Balance is not broken, insertion is finised.
         */
        return;
    }
 
}
 
/** Delete node from AVL tree.
 *
 * Because of allowed multiple identical keys parent pointers are essential
 * during deletition.
 *
 * @param t AVL tree structure.
 * @param node Address of node which will be deleted.
 */
void avltree_delete(avltree_t *t, avltree_node_t *node)
{
    avltree_node_t *cur;
    avltree_node_t *par;
    avltree_node_t *gpa;
    uint8_t dir;
 
    ASSERT(t);
    ASSERT(node);
   
   
    if (node->lft == NULL) {
        if (node->rgt) {
            /*
             * Replace node with its only right son.
             *
             * Balance of right son will be repaired in balancing cycle.
             */
            cur = node->rgt;
            cur->par = node->par;
            gpa = cur;
            dir = AVLTREE_RIGHT;
            cur->balance = node->balance;
        } else {
            if (node->par == NULL) {
                /*
                 * Tree has only one node - it will be empty tree and balancing can end.
                 */
                t->root = NULL;
                return;
            }
            /*
             * Node has no child, will be deleted with no substitution.
             */
            gpa = node->par;
            cur = NULL;
            dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
        }
    } else {
        /*
         * Node has left and right son. Find a node with smallest key in left subtree
         * and replace deleted node with that node.
         */
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
            ;
       
        //cur obsahuje uzel, ktery vlozim misto uzlu node
       
        if (cur != node->lft) {
            /*
             * The most right node of deleted node's left subtree was found. Replace
             * deleted node with this node. Cutting founded node has two cases in
             * dependence on its left son.
             */
            if (cur->lft) {
                /*
                 * Founded node has left son.
                 */
                gpa = cur->lft;
                gpa->par = cur->par;
                dir = AVLTREE_LEFT;
                gpa->balance = cur->balance;
            } else {
                dir = AVLTREE_RIGHT;
                gpa = cur->par;
            }
            cur->par->rgt = cur->lft;
            cur->lft = node->lft;
            cur->lft->par = cur;
        } else {
            /*
             * Left son of node hasn't got right son. Left son will take deleted node's place.
             */
            dir = AVLTREE_LEFT;
            gpa = cur;
        }
        if (node->rgt) node->rgt->par = cur;
        cur->rgt = node->rgt;
        cur->balance = node->balance;
        cur->par = node->par;
    }
   
    /*
     * Repair parent nodes pointer which pointed previously to deleted node.
     */
    if (node->par == NULL) {
        t->root = cur;
    } else {
        if (node->par->lft == node) {
            node->par->lft = cur;
        } else {
            node->par->rgt = cur;
        }
    }
   
    /*
     * Repair cycle which repairs balances of nodes in way from cutted noded down to root.
     */
    for(;;) {
        if (dir == AVLTREE_LEFT) {
            /*
             * Deletition was made in left subtree.
             */
            gpa->balance++;
            if (gpa->balance == +1) {
                /*
                 * Stop balancing, tree is balanced.
                 */
                break;
            } else if (gpa->balance == +2) {
                /*
                 * Bad balance, heights of left and right subtrees differs more then is allowed.
                 */
                par = gpa->rgt;
 
                if (par->balance == -1) {
                    /*
                     * RL rotation.
                     */
                   
                    cur = par->lft;
                    par->lft = cur->rgt;
                    cur->rgt = par;
                    gpa->rgt = cur->lft;
                    cur->lft = gpa;
                   
                    /*
                     * Repair balances and paternity of childs in dependence on
                     * balance factor of grand child (cur).
                     */
                    if (cur->balance == +1) {
                        par->balance = 0;
                        gpa->balance = -1;
                        if (gpa->rgt) gpa->rgt->par = gpa;
                        par->lft->par = par;
                    } else if (cur->balance == 0) {
                        par->balance = gpa->balance = 0;
                        if (gpa->rgt) gpa->rgt->par = gpa;
                        if (par->lft) par->lft->par = par;
                    } else {
                        par->balance = +1;
                        gpa->balance = 0;
                        if (par->lft) par->lft->par = par;
                        gpa->rgt->par = gpa;
                    }
                    cur->balance = 0;
                   
                    /*
                     * Repair paternity.
                     */
                    cur->par = gpa->par;
                    gpa->par = cur;
                    par->par = cur;
 
                    /*
                     * Repair pointer which pointed to balanced node. If it was root then balancing
                     * is finished else continue in next iteration (parent node).
                     */
                    if (cur->par == NULL) {
                        t->root = cur; 
                        break;
                    } else
                        if (cur->par->lft == gpa) {
                            cur->par->lft = cur;
                            dir = AVLTREE_LEFT;
                        } else {
                            cur->par->rgt = cur;
                            dir = AVLTREE_RIGHT;
                        }
                    gpa = cur->par;
                } else {
                    /*
                     * RR rotation.
                     */
                   
                    gpa->rgt = par->lft;
                    if (par->lft) par->lft->par = gpa;
                    par->lft = gpa;
                   
                    /*
                     * Repair paternity.
                     */
                    par->par = gpa->par;
                    gpa->par = par;
                   
                    if (par->balance == 0) {
                        /*
                         * Right child of balanced node is balanced, after RR rotation is done, whole
                         * tree will be balanced.
                         */
                        par->balance = -1;
                        gpa->balance = +1;
 
                        /*
                         * Repair pointer which pointed to balanced node and finish balancing.
                         */
                        if (par->par == NULL) {
                            t->root = par; 
                        } else
                            if (par->par->lft == gpa) {
                                par->par->lft = par;
                            } else {
                                par->par->rgt = par;
                            }
                        break;
                    } else {
                        par->balance = gpa->balance = 0;
                        /*
                         * Repair pointer which pointed to balanced node. If it was root then balancing
                         * is finished else continue in next iteration (parent node).
                         */
                        if (par->par == NULL) {
                            t->root = par; 
                            break;
                        } else {
                           
                            if (par->par->lft == gpa) {
                                par->par->lft = par;
                                dir = AVLTREE_LEFT;
                            } else {
                                par->par->rgt = par;
                                dir = AVLTREE_RIGHT;
                            }
                        }
                    }
                    gpa = par->par;
                }
            } else {
                /*
                 * Repair pointer which pointed to balanced node. If it was root then balancing
                 * is finished else continue in next iteration (parent node).
                 */
                if (!gpa->par) break;
 
                if (gpa->par->lft == gpa) {
                    dir = AVLTREE_LEFT;
                } else {
                    dir = AVLTREE_RIGHT;
                }
                gpa = gpa->par;
            }
        } else {
            /*
             * Deletition was made in right subtree.
             */
            gpa->balance--;
            if (gpa->balance == -1) {
                /*
                 * Stop balancing, tree is balanced.
                 */
                break;
            } else if (gpa->balance == -2) {
                /*
                 * Bad balance, heights of left and right subtrees differs more then is allowed.
                 */
                par = gpa->lft;
               
                if (par->balance == +1) {
                    /*
                     * LR rotation.
                     */
                   
                    cur = par->rgt;
                    par->rgt = cur->lft;
                    cur->lft = par;
                    gpa->lft = cur->rgt;
                    cur->rgt = gpa;
                   
                    /*
                     * Repair balances and paternity of childs in dependence on
                     * balance factor of grand child (cur).
                     */
                    if (cur->balance == -1) {
                        par->balance = 0;
                        gpa->balance = +1;
                        if (gpa->lft) gpa->lft->par = gpa;
                        par->rgt->par = par;
                    } else if (cur->balance == 0) {
                        par->balance = gpa->balance = 0;
                        if (gpa->lft) gpa->lft->par = gpa;
                        if (par->rgt) par->rgt->par = par;
                    } else {
                        par->balance = -1;
                        gpa->balance = 0;
                        if (par->rgt) par->rgt->par = par;
                        gpa->lft->par = gpa;
                    }
                    cur->balance = 0;
 
                    /*
                     * Repair paternity.
                     */
                    cur->par = gpa->par;
                    gpa->par = cur;
                    par->par = cur;
 
                    /*
                     * Repair pointer which pointed to balanced node. If it was root then balancing
                     * is finished else continue in next iteration (parent node).
                     */
                    if (cur->par == NULL) {
                        t->root = cur; 
                        break;
                    } else
                        if (cur->par->lft == gpa) {
                            cur->par->lft = cur;
                            dir = AVLTREE_LEFT;
                        } else {
                            cur->par->rgt = cur;
                            dir = AVLTREE_RIGHT;
                        }
                    gpa = cur->par;
                } else {
                    /*
                     * LL rotation.
                     */
                   
                    gpa->lft = par->rgt;
                    if (par->rgt) par->rgt->par = gpa;
                    par->rgt = gpa;
                    /*
                     * Repair paternity.
                     */
                    par->par = gpa->par;
                    gpa->par = par;
                   
                    if (par->balance == 0) {
                        /*
                         * Left child of balanced node is balanced, after RR rotation is done, whole
                         * tree will be balanced.
                         */
                        par->balance = +1;
                        gpa->balance = -1;
                       
                        /*
                         * Repair pointer which pointed to balanced node and finish balancing.
                         */
                        if (par->par == NULL) {
                            t->root = par;
                        } else
                            if (par->par->lft == gpa) {
                                par->par->lft = par;
                            } else {
                                par->par->rgt = par;
                            }
                        break;
                    } else {
                        par->balance = gpa->balance = 0;
                       
                        /*
                         * Repair pointer which pointed to balanced node. If it was root then balancing
                         * is finished else continue in next iteration (parent node).
                         */
                        if (par->par == NULL) {
                            t->root = par;
                            break;
                        } else {
                            if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
                                par->par->lft = par;
                                dir = AVLTREE_LEFT;
                            } else {
                                par->par->rgt = par;
                                dir = AVLTREE_RIGHT;
                            }
                        }
                    }
                    gpa = par->par;
                }
            } else {
                /*
                 * Repair pointer which pointed to balanced node. If it was root then balancing
                 * is finished else continue in next iteration (parent node).
                 */
                if (!gpa->par) break;
 
                if (gpa->par->lft == gpa) {
                    dir = AVLTREE_LEFT;
                } else {
                    dir = AVLTREE_RIGHT;
                }
                gpa = gpa->par;
            }
        }
    }
}
 
 
/** Delete node from AVL tree with the smallest key.
 *
 * @param t AVL tree structure.
 */
bool avltree_delete_min(avltree_t *t)
{
    avltree_node_t *node;
 
   
    /*
     * Start search of smallest key in tree in the root node and
     * continue in cycle to the most left node in the tree which
     * must have smallest key.
     */
    node = t->root;
    if (!node) return false;
   
    while (node->lft != NULL)
        node = node->lft;
   
    /*
     * Use avltree_delete function to delete node from tree.
     */
 
    avltree_delete(t,node);
 
    return true;
}
 

Rev 2450	Rev 2461
1	/*	1	/*
2	* Copyright (c) 2007 Vojtech Mencl	2	* Copyright (c) 2007 Vojtech Mencl
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	/** @addtogroup genericadt	29	/** @addtogroup genericadt
30	* @{	30	* @{
31	*/	31	*/
32		32
33	/**	33	/**
34	* @file	34	* @file
35	* @brief AVL tree implementation.	35	* @brief AVL tree implementation.
36	*	36	*
37	* This file implements AVL tree type and operations.	37	* This file implements AVL tree type and operations.
38	*	38	*
39	* Implemented AVL tree has the following properties:	39	* Implemented AVL tree has the following properties:
40	* @li it is binary search tree with non-unique keys	40	* @li It is binary search tree with non-unique keys.
41	* @li Difference of heights of left and right subtree of every node is max 1.	41	* @li Difference of heights of left and right subtree of every node is max 1.
42	*	42	*
43	* Every node has pointer to its parent which allows insertion of multiple identical keys	43	* Every node has pointer to its parent which allows insertion of multiple identical keys
44	* into tree.	44	* into tree.
45	*	45	*
46	* Be careful of using this tree because of base atribute, which is added to every inserted	46	* Be careful of using this tree because of base atribute, which is added to every inserted
47	* node key. There is no rule in which order nodes with the same key are visited.	47	* node key. There is no rule in which order nodes with the same key are visited.
48	*/	48	*/
49		49
50	#include <adt/avl.h>	50	#include <adt/avl.h>
51	#include <debug.h>	51	#include <debug.h>
52	#include <panic.h>	-
53		52
54		53
55	#define AVLTREE_LEFT 0	54	#define AVLTREE_LEFT 0
56	#define AVLTREE_RIGHT 1	55	#define AVLTREE_RIGHT 1
57		56
58		57
59	/** Search first occurence of given key in AVL tree.	58	/** Search first occurence of given key in AVL tree.
60	*	59	*
61	* @param t AVL tree.	60	* @param t AVL tree.
62	* @param key Key to be searched.	61	* @param key Key to be searched.
63	*	62	*
64	* @return Pointer to node or NULL if there is no such key.	63	* @return Pointer to node or NULL if there is no such key.
65	*/	64	*/
66	avltree_node_t avltree_search(avltree_t t, uint64_t key)	65	avltree_node_t avltree_search(avltree_t t, uint64_t key)
67	{	66	{
68	avltree_node_t *p;	67	avltree_node_t *p;
69		68
70	/*	69	/*
71	* Iteratively descend to the leaf that can contain the searched key.	70	* Iteratively descend to the leaf that can contain the searched key.
72	*/	71	*/
73	p = t->root;	72	p = t->root;
74	while (p != NULL) {	73	while (p != NULL) {
75	if (p->key > key)	74	if (p->key > key)
76	p = p->lft;	75	p = p->lft;
77	else if (p->key < key)	76	else if (p->key < key)
78	p = p->rgt;	77	p = p->rgt;
79	else {	78	else {
80	return p;	79	return p;
81	}	80	}
82	}	81	}
83	return NULL;	82	return NULL;
84	}	83	}
85		84
86		85
87	/** Find node with smallest key in AVL tree.	86	/** Find node with smallest key in AVL tree.
88	*	87	*
89	* @param t AVL tree.	88	* @param t AVL tree.
90	*	89	*
91	* @return Pointer to node or NULL if there is no node in the tree.	90	* @return Pointer to node or NULL if there is no node in the tree.
92	*/	91	*/
93	avltree_node_t avltree_find_min(avltree_t t)	92	avltree_node_t avltree_find_min(avltree_t t)
94	{	93	{
95	avltree_node_t *p = t->root;	94	avltree_node_t *p = t->root;
96		95
97	/*	96	/*
98	* Check whether tree is empty.	97	* Check whether tree is empty.
99	*/	98	*/
100	if (!p) return NULL;	99	if (!p) return NULL;
101		100
102	/*	101	/*
103	* Iteratively descend to the leftmost leaf in the tree.	102	* Iteratively descend to the leftmost leaf in the tree.
104	*/	103	*/
105	while (p->lft != NULL)	104	while (p->lft != NULL)
106	p = p->lft;	105	p = p->lft;
107		106
108	return p;	107	return p;
109	}	108	}
110		109
111	/** Insert new node into AVL tree.	110	/** Insert new node into AVL tree.
112	*	111	*
113	* @param t AVL tree.	112	* @param t AVL tree.
114	* @param newnode New node to be inserted.	113	* @param newnode New node to be inserted.
115	*/	114	*/
116	void avltree_insert(avltree_t t, avltree_node_t newnode)	115	void avltree_insert(avltree_t t, avltree_node_t newnode)
117	{	116	{
118	avltree_node_t *par;	117	avltree_node_t *par;
119	avltree_node_t *gpa;	118	avltree_node_t *gpa;
120	avltree_node_t *top;	119	avltree_node_t *top;
121	avltree_node_t **dpc;	120	avltree_node_t **dpc;
122	uint64_t key;	121	uint64_t key;
123		122
124	ASSERT(t);	123	ASSERT(t);
125	ASSERT(newnode);	124	ASSERT(newnode);
126		125
127	/*	126	/*
128	* Creating absolute key.	127	* Creating absolute key.
129	*/	128	*/
130	key = newnode->key + t->base;	129	key = newnode->key + t->base;
131		130
132		131
133	/*	132	/*
134	* Iteratively descend to the leaf that can will contain new node.	133	* Iteratively descend to the leaf that can contain new node.
135	* Last node with non-zero balance in the way to leaf is stored as top -	134	* Last node with non-zero balance in the way to leaf is stored as top -
136	* it si place of possible balance failure.	135	* it si place of possible balance fault.
137	*/	136	*/
138	dpc = &t->root;	137	dpc = &t->root;
139	gpa = NULL;	138	gpa = NULL;
140	top = t->root;	139	top = t->root;
141	while ((par = (*dpc)) != NULL) {	140	while ((par = (*dpc)) != NULL) {
142	if (par->balance != 0) {	141	if (par->balance != 0) {
143	top = par;	142	top = par;
144	}	143	}
145	gpa = par;	144	gpa = par;
146	dpc = par->key > key? &par->lft: &par->rgt;	145	dpc = par->key > key? &par->lft: &par->rgt;
147	}	146	}
148		147
149	/*	148	/*
150	* Initialize new node.	149	* Initialize new node.
151	*/	150	*/
152	newnode->key = key;	151	newnode->key = key;
153	newnode->lft = NULL;	152	newnode->lft = NULL;
154	newnode->rgt = NULL;	153	newnode->rgt = NULL;
155	newnode->par = gpa;	154	newnode->par = gpa;
156	newnode->balance = 0;	155	newnode->balance = 0;
157		156
158	/*	157	/*
159	* Insert first node into empty tree.	158	* Insert first node into empty tree.
160	*/	159	*/
161	if (t->root == NULL) {	160	if (t->root == NULL) {
162	*dpc = newnode;	161	*dpc = newnode;
163	return;	162	return;
164	}	163	}
165		164
166	/*	165	/*
167	* Insert new node into previously found leaf place.	166	* Insert new node into previously found leaf place.
168	*/	167	*/
169	*dpc = newnode;	168	*dpc = newnode;
170		169
171	/*	170	/*
172	* If tree contains one node - end.	171	* If tree contains one node - end.
173	*/	172	*/
174	if (top == NULL) return;	173	if (top == NULL) return;
175		174
176	/*	175	/*
177	* Store pointer of top's father which points to the node with potentialy broken	176	* Store pointer of top's father which points to the node with potentialy broken
178	* balance (top).	177	* balance (top).
179	*/	178	*/
180	if (top->par == NULL)	179	if (top->par == NULL)
181	dpc = &t->root;	180	dpc = &t->root;
182	else	181	else
183	if (top->par->lft == top)	182	if (top->par->lft == top)
184	dpc = &(top->par->lft);	183	dpc = &(top->par->lft);
185	else	184	else
186	dpc = &(top->par->rgt);	185	dpc = &(top->par->rgt);
187		186
188	/*	187	/*
189	* Repair all balances on the way from top node to newly inserted node.	188	* Repair all balances on the way from top node to newly inserted node.
190	*/	189	*/
191	par = top;	190	par = top;
192	while (par != newnode) {	191	while (par != newnode) {
193	if (par->key > key) {	192	if (par->key > key) {
194	par->balance--;	193	par->balance--;
195	par = par->lft;	194	par = par->lft;
196	} else {	195	} else {
197	par->balance++;	196	par->balance++;
198	par = par->rgt;	197	par = par->rgt;
199	}	198	}
200	}	199	}
201		200
202	/*	201	/*
203	* To balance tree we must check and balance top node.	202	* To balance tree we must check and balance top node.
204	*/	203	*/
205	if (top->balance == -2) {	204	if (top->balance == -2) {
206	par = top->lft;	205	par = top->lft;
207	if (par->balance == -1) {	206	if (par->balance == -1) {
208	/*	207	/*
209	* LL rotation.	208	* LL rotation.
210	*/	209	*/
211	top->lft = par->rgt;	210	top->lft = par->rgt;
212	if (top->lft != NULL) top->lft->par = top;	211	if (top->lft != NULL) top->lft->par = top;
213	par->par = top->par;	212	par->par = top->par;
214	top->par = par;	213	top->par = par;
215	par->rgt = top;	214	par->rgt = top;
216	par->balance = top->balance = 0;	215	par->balance = top->balance = 0;
217	*dpc = par;	216	*dpc = par;
218	} else {	217	} else {
219	/*	218	/*
220	* LR rotation.	219	* LR rotation.
221	*/	220	*/
222	ASSERT(par->balance == 1);	221	ASSERT(par->balance == 1);
223		222
224	gpa = par->rgt;	223	gpa = par->rgt;
225	par->rgt = gpa->lft;	224	par->rgt = gpa->lft;
226	if (gpa->lft != NULL) gpa->lft->par = par;	225	if (gpa->lft != NULL) gpa->lft->par = par;
227	gpa->lft = par;	226	gpa->lft = par;
228	par->par = gpa;	227	par->par = gpa;
229	top->lft = gpa->rgt;	228	top->lft = gpa->rgt;
230	if (gpa->rgt != NULL) gpa->rgt->par = top;	229	if (gpa->rgt != NULL) gpa->rgt->par = top;
231	gpa->rgt = top;	230	gpa->rgt = top;
232	gpa->par = top->par;	231	gpa->par = top->par;
233	top->par = gpa;	232	top->par = gpa;
234		233
235	if (gpa->balance == -1) {	234	if (gpa->balance == -1) {
236	par->balance = 0;	235	par->balance = 0;
237	top->balance = 1;	236	top->balance = 1;
238	} else if (gpa->balance == 0) {	237	} else if (gpa->balance == 0) {
239	par->balance = top->balance = 0;	238	par->balance = top->balance = 0;
240	} else {	239	} else {
241	par->balance = -1;	240	par->balance = -1;
242	top->balance = 0;	241	top->balance = 0;
243	}	242	}
244	gpa->balance = 0;	243	gpa->balance = 0;
245	*dpc = gpa;	244	*dpc = gpa;
246	}	245	}
247	} else if (top->balance == 2) {	246	} else if (top->balance == 2) {
248	par = top->rgt;	247	par = top->rgt;
249	if (par->balance == 1) {	248	if (par->balance == 1) {
250	/*	249	/*
251	* RR rotation.	250	* RR rotation.
252	*/	251	*/
253	top->rgt = par->lft;	252	top->rgt = par->lft;
254	if (top->rgt != NULL) top->rgt->par = top;	253	if (top->rgt != NULL) top->rgt->par = top;
255	par->par = top->par;	254	par->par = top->par;
256	top->par = par;	255	top->par = par;
257	par->lft = top;	256	par->lft = top;
258	par->balance = top->balance = 0;	257	par->balance = top->balance = 0;
259	*dpc = par;	258	*dpc = par;
260	} else {	259	} else {
261	/*	260	/*
262	* RL rotation.	261	* RL rotation.
263	*/	262	*/
264	ASSERT(par->balance == -1);	263	ASSERT(par->balance == -1);
265		264
266	gpa = par->lft;	265	gpa = par->lft;
267	par->lft = gpa->rgt;	266	par->lft = gpa->rgt;
268	if (gpa->rgt != NULL) gpa->rgt->par = par;	267	if (gpa->rgt != NULL) gpa->rgt->par = par;
269	gpa->rgt = par;	268	gpa->rgt = par;
270	par->par = gpa;	269	par->par = gpa;
271	top->rgt = gpa->lft;	270	top->rgt = gpa->lft;
272	if (gpa->lft != NULL) gpa->lft->par = top;	271	if (gpa->lft != NULL) gpa->lft->par = top;
273	gpa->lft = top;	272	gpa->lft = top;
274	gpa->par = top->par;	273	gpa->par = top->par;
275	top->par = gpa;	274	top->par = gpa;
276		275
277	if (gpa->balance == 1) {	276	if (gpa->balance == 1) {
278	par->balance = 0;	277	par->balance = 0;
279	top->balance = -1;	278	top->balance = -1;
280	} else if (gpa->balance == 0) {	279	} else if (gpa->balance == 0) {
281	par->balance = top->balance = 0;	280	par->balance = top->balance = 0;
282	} else {	281	} else {
283	par->balance = 1;	282	par->balance = 1;
284	top->balance = 0;	283	top->balance = 0;
285	}	284	}
286	gpa->balance = 0;	285	gpa->balance = 0;
287	*dpc = gpa;	286	*dpc = gpa;
288	}	287	}
289	} else {	288	} else {
290	/*	289	/*
291	* Balance is not broken, insertion is finised.	290	* Balance is not broken, insertion is finised.
292	*/	291	*/
293	return;	292	return;
294	}	293	}
295		294
296	}	295	}
297		296
298	/** Delete node from AVL tree.	297	/** Delete node from AVL tree.
299	*	298	*
300	* Because of allowed multiple identical keys parent pointers are essential	299	* Because of allowed multiple identical keys parent pointers are essential
301	* during deletition.	300	* during deletition.
302	*	301	*
303	* @param t AVL tree structure.	302	* @param t AVL tree structure.
304	* @param node Address of node which will be deleted.	303	* @param node Address of node which will be deleted.
305	*/	304	*/
306	void avltree_delete(avltree_t t, avltree_node_t node)	305	void avltree_delete(avltree_t t, avltree_node_t node)
307	{	306	{
308	avltree_node_t *cur;	307	avltree_node_t *cur;
309	avltree_node_t *par;	308	avltree_node_t *par;
310	avltree_node_t *gpa;	309	avltree_node_t *gpa;
311	uint8_t dir;	310	uint8_t dir;
312		311
313	ASSERT(t);	312	ASSERT(t);
314	ASSERT(node);	313	ASSERT(node);
315		314
316		315
317	if (node->lft == NULL) {	316	if (node->lft == NULL) {
318	if (node->rgt) {	317	if (node->rgt) {
319	/*	318	/*
320	* Replace node with its only right son.	319	* Replace node with its only right son.
321	*	320	*
322	* Balance of right son will be repaired in balancing cycle.	321	* Balance of right son will be repaired in balancing cycle.
323	*/	322	*/
324	cur = node->rgt;	323	cur = node->rgt;
325	cur->par = node->par;	324	cur->par = node->par;
326	gpa = cur;	325	gpa = cur;
327	dir = AVLTREE_RIGHT;	326	dir = AVLTREE_RIGHT;
328	cur->balance = node->balance;	327	cur->balance = node->balance;
329	} else {	328	} else {
330	if (node->par == NULL) {	329	if (node->par == NULL) {
331	/*	330	/*
332	* Tree has only one node - it will be empty tree and balancing can end.	331	* Tree has only one node - it will be empty tree and balancing can end.
333	*/	332	*/
334	t->root = NULL;	333	t->root = NULL;
335	return;	334	return;
336	}	335	}
337	/*	336	/*
338	* Node has no child, will be deleted with no substitution.	337	* Node has no child, will be deleted with no substitution.
339	*/	338	*/
340	gpa = node->par;	339	gpa = node->par;
341	cur = NULL;	340	cur = NULL;
342	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;	341	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
343	}	342	}
344	} else {	343	} else {
345	/*	344	/*
346	* Node has left and right son. Find a node with smallest key in left subtree	345	* Node has left and right son. Find a node with smallest key in left subtree
347	* and replace deleted node with that node.	346	* and replace deleted node with that node.
348	*/	347	*/
349	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)	348	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
350	;	349	;
351		350
352	//cur obsahuje uzel, ktery vlozim misto uzlu node	351	//cur obsahuje uzel, ktery vlozim misto uzlu node
353		352
354	if (cur != node->lft) {	353	if (cur != node->lft) {
355	/*	354	/*
356	* The most right node of deleted node's left subtree was found. Replace	355	* The most right node of deleted node's left subtree was found. Replace
357	* deleted node with this node. Cutting founded node has two cases in	356	* deleted node with this node. Cutting founded node has two cases in
358	* dependence on its left son.	357	* dependence on its left son.
359	*/	358	*/
360	if (cur->lft) {	359	if (cur->lft) {
361	/*	360	/*
362	* Founded node has left son.	361	* Founded node has left son.
363	*/	362	*/
364	gpa = cur->lft;	363	gpa = cur->lft;
365	gpa->par = cur->par;	364	gpa->par = cur->par;
366	dir = AVLTREE_LEFT;	365	dir = AVLTREE_LEFT;
367	gpa->balance = cur->balance;	366	gpa->balance = cur->balance;
368	} else {	367	} else {
369	dir = AVLTREE_RIGHT;	368	dir = AVLTREE_RIGHT;
370	gpa = cur->par;	369	gpa = cur->par;
371	}	370	}
372	cur->par->rgt = cur->lft;	371	cur->par->rgt = cur->lft;
373	cur->lft = node->lft;	372	cur->lft = node->lft;
374	cur->lft->par = cur;	373	cur->lft->par = cur;
375	} else {	374	} else {
376	/*	375	/*
377	* Left son of node hasn't got right son. Left son will take deleted node's place.	376	* Left son of node hasn't got right son. Left son will take deleted node's place.
378	*/	377	*/
379	dir = AVLTREE_LEFT;	378	dir = AVLTREE_LEFT;
380	gpa = cur;	379	gpa = cur;
381	}	380	}
382	if (node->rgt) node->rgt->par = cur;	381	if (node->rgt) node->rgt->par = cur;
383	cur->rgt = node->rgt;	382	cur->rgt = node->rgt;
384	cur->balance = node->balance;	383	cur->balance = node->balance;
385	cur->par = node->par;	384	cur->par = node->par;
386	}	385	}
387		386
388	/*	387	/*
389	* Repair parent nodes pointer which pointed previously to deleted node.	388	* Repair parent nodes pointer which pointed previously to deleted node.
390	*/	389	*/
391	if (node->par == NULL) {	390	if (node->par == NULL) {
392	t->root = cur;	391	t->root = cur;
393	} else {	392	} else {
394	if (node->par->lft == node) {	393	if (node->par->lft == node) {
395	node->par->lft = cur;	394	node->par->lft = cur;
396	} else {	395	} else {
397	node->par->rgt = cur;	396	node->par->rgt = cur;
398	}	397	}
399	}	398	}
400		399
401	/*	400	/*
402	* Repair cycle which repairs balances of nodes in way from cutted noded down to root.	401	* Repair cycle which repairs balances of nodes in way from cutted noded down to root.
403	*/	402	*/
404	for(;;) {	403	for(;;) {
405	if (dir == AVLTREE_LEFT) {	404	if (dir == AVLTREE_LEFT) {
406	/*	405	/*
407	* Deletition was made in left subtree.	406	* Deletition was made in left subtree.
408	*/	407	*/
409	gpa->balance++;	408	gpa->balance++;
410	if (gpa->balance == +1) {	409	if (gpa->balance == +1) {
411	/*	410	/*
412	* Stop balancing, tree is balanced.	411	* Stop balancing, tree is balanced.
413	*/	412	*/
414	break;	413	break;
415	} else if (gpa->balance == +2) {	414	} else if (gpa->balance == +2) {
416	/*	415	/*
417	* Bad balance, heights of left and right subtrees differs more then is allowed.	416	* Bad balance, heights of left and right subtrees differs more then is allowed.
418	*/	417	*/
419	par = gpa->rgt;	418	par = gpa->rgt;
420		419
421	if (par->balance == -1) {	420	if (par->balance == -1) {
422	/*	421	/*
423	* RL rotation.	422	* RL rotation.
424	*/	423	*/
425		424
426	cur = par->lft;	425	cur = par->lft;
427	par->lft = cur->rgt;	426	par->lft = cur->rgt;
428	cur->rgt = par;	427	cur->rgt = par;
429	gpa->rgt = cur->lft;	428	gpa->rgt = cur->lft;
430	cur->lft = gpa;	429	cur->lft = gpa;
431		430
432	/*	431	/*
433	* Repair balances and paternity of childs in dependence on	432	* Repair balances and paternity of childs in dependence on
434	* balance factor of grand child (cur).	433	* balance factor of grand child (cur).
435	*/	434	*/
436	if (cur->balance == +1) {	435	if (cur->balance == +1) {
437	par->balance = 0;	436	par->balance = 0;
438	gpa->balance = -1;	437	gpa->balance = -1;
439	if (gpa->rgt) gpa->rgt->par = gpa;	438	if (gpa->rgt) gpa->rgt->par = gpa;
440	par->lft->par = par;	439	par->lft->par = par;
441	} else if (cur->balance == 0) {	440	} else if (cur->balance == 0) {
442	par->balance = gpa->balance = 0;	441	par->balance = gpa->balance = 0;
443	if (gpa->rgt) gpa->rgt->par = gpa;	442	if (gpa->rgt) gpa->rgt->par = gpa;
444	if (par->lft) par->lft->par = par;	443	if (par->lft) par->lft->par = par;
445	} else {	444	} else {
446	par->balance = +1;	445	par->balance = +1;
447	gpa->balance = 0;	446	gpa->balance = 0;
448	if (par->lft) par->lft->par = par;	447	if (par->lft) par->lft->par = par;
449	gpa->rgt->par = gpa;	448	gpa->rgt->par = gpa;
450	}	449	}
451	cur->balance = 0;	450	cur->balance = 0;
452		451
453	/*	452	/*
454	* Repair paternity.	453	* Repair paternity.
455	*/	454	*/
456	cur->par = gpa->par;	455	cur->par = gpa->par;
457	gpa->par = cur;	456	gpa->par = cur;
458	par->par = cur;	457	par->par = cur;
459		458
460	/*	459	/*
461	* Repair pointer which pointed to balanced node. If it was root then balancing	460	* Repair pointer which pointed to balanced node. If it was root then balancing
462	* is finished else continue in next iteration (parent node).	461	* is finished else continue in next iteration (parent node).
463	*/	462	*/
464	if (cur->par == NULL) {	463	if (cur->par == NULL) {
465	t->root = cur;	464	t->root = cur;
466	break;	465	break;
467	} else	466	} else
468	if (cur->par->lft == gpa) {	467	if (cur->par->lft == gpa) {
469	cur->par->lft = cur;	468	cur->par->lft = cur;
470	dir = AVLTREE_LEFT;	469	dir = AVLTREE_LEFT;
471	} else {	470	} else {
472	cur->par->rgt = cur;	471	cur->par->rgt = cur;
473	dir = AVLTREE_RIGHT;	472	dir = AVLTREE_RIGHT;
474	}	473	}
475	gpa = cur->par;	474	gpa = cur->par;
476	} else {	475	} else {
477	/*	476	/*
478	* RR rotation.	477	* RR rotation.
479	*/	478	*/
480		479
481	gpa->rgt = par->lft;	480	gpa->rgt = par->lft;
482	if (par->lft) par->lft->par = gpa;	481	if (par->lft) par->lft->par = gpa;
483	par->lft = gpa;	482	par->lft = gpa;
484		483
485	/*	484	/*
486	* Repair paternity.	485	* Repair paternity.
487	*/	486	*/
488	par->par = gpa->par;	487	par->par = gpa->par;
489	gpa->par = par;	488	gpa->par = par;
490		489
491	if (par->balance == 0) {	490	if (par->balance == 0) {
492	/*	491	/*
493	* Right child of balanced node is balanced, after RR rotation is done, whole	492	* Right child of balanced node is balanced, after RR rotation is done, whole
494	* tree will be balanced.	493	* tree will be balanced.
495	*/	494	*/
496	par->balance = -1;	495	par->balance = -1;
497	gpa->balance = +1;	496	gpa->balance = +1;
498		497
499	/*	498	/*
500	* Repair pointer which pointed to balanced node and finish balancing.	499	* Repair pointer which pointed to balanced node and finish balancing.

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/adt/avl.c – Rev 2450 → 2461