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>
#include <panic.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 will contain new node.
     * Last node with non-zero balance in the way to leaf is stored as top -
     * it si place of possible balance failure.
     */
    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 and set base of tree to that key.
 *
 * @param t AVL tree structure.
 */
bool avltree_delete_min(avltree_t *t)
{
    avltree_node_t *node;
    uint64_t key;
   
    /*
     * 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;
   
    /*
     * Store key and use avltree_delete function to delete node from tree.
     */
    key = node->key;
    avltree_delete(t,node);
 
    /*
     * Change base to the key of deleted node.
     */
    t->base = key;
 
    return true;
}
 

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

Subversion Repositories HelenOS

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