WebSVN – HelenOS – Diff – /branches/dd/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 a binary search tree with non-unique keys.
 * @li Difference of heights of the left and the right subtree of every node is
 *     one at maximum.
 *
 * Every node has a pointer to its parent which allows insertion of multiple
 * identical keys into the tree.
 *
 * Be careful when using this tree because of the 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 LEFT    0
#define RIGHT   1
 
/** Search for the first occurence of the given key in an AVL tree.
 *
 * @param t AVL tree.
 * @param key Key to be searched.
 *
 * @return Pointer to a node or NULL if there is no such key.
 */
avltree_node_t *avltree_search(avltree_t *t, avltree_key_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 the node with the smallest key in an AVL tree.
 *
 * @param t AVL tree.
 *
 * @return Pointer to a 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 the 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;
}
 
#define REBALANCE_INSERT_XX(DIR1, DIR2)     \
    top->DIR1 = par->DIR2;          \
    if (top->DIR1 != NULL)          \
        top->DIR1->par = top;       \
    par->par = top->par;            \
    top->par = par;             \
    par->DIR2 = top;            \
    par->balance = 0;           \
    top->balance = 0;           \
    *dpc = par;
 
#define REBALANCE_INSERT_LL()       REBALANCE_INSERT_XX(lft, rgt)
#define REBALANCE_INSERT_RR()       REBALANCE_INSERT_XX(rgt, lft)
 
#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN)    \
    gpa = par->DIR2;            \
    par->DIR2 = gpa->DIR1;          \
    if (gpa->DIR1 != NULL)          \
        gpa->DIR1->par = par;       \
    gpa->DIR1 = par;            \
    par->par = gpa;             \
    top->DIR1 = gpa->DIR2;          \
    if (gpa->DIR2 != NULL)          \
        gpa->DIR2->par = top;       \
    gpa->DIR2 = top;            \
    gpa->par = top->par;            \
    top->par = gpa;             \
                        \
    if (gpa->balance == -1 * SGN) {     \
        par->balance = 0;       \
        top->balance = 1 * SGN;     \
    } else if (gpa->balance == 0) {     \
        par->balance = 0;       \
        top->balance = 0;       \
    } else {                \
        par->balance = -1 * SGN;    \
        top->balance = 0;       \
    }                   \
    gpa->balance = 0;           \
    *dpc = gpa;
 
#define REBALANCE_INSERT_LR()       REBALANCE_INSERT_XY(lft, rgt, 1)
#define REBALANCE_INSERT_RL()       REBALANCE_INSERT_XY(rgt, lft, -1)
   
/** 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;
    avltree_key_t key;
 
    ASSERT(t);
    ASSERT(newnode);
 
    /*
     * Creating absolute key.
     */
    key = newnode->key + t->base;
   
    /*
     * Iteratively descend to the leaf that can contain the new node.
     * Last node with non-zero balance in the way to leaf is stored as top -
     * it is a place of possible inbalance.
     */
    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 the new node.
     */
    newnode->key = key;
    newnode->lft = NULL;
    newnode->rgt = NULL;
    newnode->par = gpa;
    newnode->balance = 0;
 
    /*
     * Insert first node into the empty tree.
     */
    if (t->root == NULL) {
        *dpc = newnode;
        return;
    }
 
    /*
     * Insert the new node into the previously found leaf position.
     */
    *dpc = newnode;
 
    /*
     * If the tree contains one node - end.
     */
    if (top == NULL)
        return;
 
    /*
     * Store pointer of top's father which points to the node with
     * potentially 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 the 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 the tree, we must check and balance top node.
     */
    if (top->balance == -2) {
        par = top->lft;
        if (par->balance == -1) {
            /*
             * LL rotation.
             */
            REBALANCE_INSERT_LL();
        } else {
            /*
             * LR rotation.
             */
            ASSERT(par->balance == 1);
           
            REBALANCE_INSERT_LR();
        }
    } else if (top->balance == 2) {
        par = top->rgt;
        if (par->balance == 1) {
            /*
             * RR rotation.
             */
            REBALANCE_INSERT_RR();
        } else {
            /*
             * RL rotation.
             */
            ASSERT(par->balance == -1);
       
            REBALANCE_INSERT_RL();
        }
    } else {
        /*
         * Balance is not broken, insertion is finised.
         */
        return;
    }
 
}
 
/** Repair the tree after reparenting node u.
 *
 * If node u has no parent, mark it as the root of the whole tree. Otherwise
 * node v represents stale address of one of the children of node u's parent.
 * Replace v with w as node u parent's child (for most uses, u and w will be the
 * same).
 *
 * @param t AVL tree.
 * @param u Node whose new parent has a stale child pointer.
 * @param v Stale child of node u's new parent.
 * @param w New child of node u's new parent.
 * @param dir   If not NULL, address of the variable where to store information
 *      about whether w replaced v in the left or the right subtree of
 *      u's new parent.
 * @param ro    Read only operation; do not modify any tree pointers. This is
 *      useful for tracking direction via the dir pointer.
 *
 * @return  Zero if w became the new root of the tree, otherwise return
 *      non-zero.
 */
static int
repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
    int *dir, int ro)
{
    if (u->par == NULL) {
        if (!ro)
            t->root = w;   
        return 0;
    } else {   
        if (u->par->lft == v) {
            if (!ro)
                u->par->lft = w;
            if (dir)
                *dir = LEFT;
        } else {
            ASSERT(u->par->rgt == v);
            if (!ro)
                u->par->rgt = w;
            if (dir)
                *dir = RIGHT;
        }
    }
    return 1;
}
 
#define REBALANCE_DELETE(DIR1, DIR2, SIGN)  \
    if (cur->balance == -1 * SIGN) {    \
        par->balance = 0;       \
        gpa->balance = 1 * SIGN;    \
        if (gpa->DIR1)          \
            gpa->DIR1->par = gpa;   \
        par->DIR2->par = par;       \
    } else if (cur->balance == 0) {     \
        par->balance = 0;       \
        gpa->balance = 0;       \
        if (gpa->DIR1)          \
            gpa->DIR1->par = gpa;   \
        if (par->DIR2)          \
            par->DIR2->par = par;   \
    } else {                \
        par->balance = -1 * SIGN;   \
        gpa->balance = 0;       \
        if (par->DIR2)          \
            par->DIR2->par = par;   \
        gpa->DIR1->par = gpa;       \
    }                   \
    cur->balance = 0;
 
#define REBALANCE_DELETE_LR()       REBALANCE_DELETE(lft, rgt, 1)
#define REBALANCE_DELETE_RL()       REBALANCE_DELETE(rgt, lft, -1)
 
/** Delete a node from the AVL tree.
 *
 * Because multiple identical keys are allowed, the parent pointers are
 * essential during deletion.
 *
 * @param t AVL tree structure.
 * @param node Address of the 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;
    int dir;
 
    ASSERT(t);
    ASSERT(node);
   
    if (node->lft == NULL) {
        if (node->rgt) {
            /*
             * Replace the node with its only right son.
             *
             * Balance of the right son will be repaired in the
             * balancing cycle.
             */
            cur = node->rgt;
            cur->par = node->par;
            gpa = cur;
            dir = RIGHT;
            cur->balance = node->balance;
        } else {
            if (node->par == NULL) {
                /*
                 * The tree has only one node - it will become
                 * an empty tree and the balancing can end.
                 */
                t->root = NULL;
                return;
            }
            /*
             * The node has no child, it will be deleted with no
             * substitution.
             */
            gpa = node->par;
            cur = NULL;
            dir = (gpa->lft == node) ? LEFT: RIGHT;
        }
    } else {
        /*
         * The node has the left son. Find a node with the smallest key
         * in the left subtree and replace the deleted node with that
         * node.
         */
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
            ;
 
        if (cur != node->lft) {
            /*
             * The rightmost node of the deleted node's left subtree
             * was found. Replace the deleted node with this node.
             * Cutting off of the found node has two cases that
             * depend on its left son.
             */
            if (cur->lft) {
                /*
                 * The found node has a left son.
                 */
                gpa = cur->lft;
                gpa->par = cur->par;
                dir = LEFT;
                gpa->balance = cur->balance;
            } else {
                dir = RIGHT;
                gpa = cur->par;
            }
            cur->par->rgt = cur->lft;
            cur->lft = node->lft;
            cur->lft->par = cur;
        } else {
            /*
             * The left son of the node hasn't got a right son. The
             * left son will take the deleted node's place.
             */
            dir = LEFT;
            gpa = cur;
        }
        if (node->rgt)
            node->rgt->par = cur;
        cur->rgt = node->rgt;
        cur->balance = node->balance;
        cur->par = node->par;
    }
   
    /*
     * Repair the parent node's pointer which pointed previously to the
     * deleted node.
     */
    (void) repair(t, node, node, cur, NULL, false);
   
    /*
     * Repair cycle which repairs balances of nodes on the way from from the
     * cut-off node up to the root.
     */
    for (;;) {
        if (dir == LEFT) {
            /*
             * Deletion was made in the left subtree.
             */
            gpa->balance++;
            if (gpa->balance == 1) {
                /*
                 * Stop balancing, the tree is balanced.
                 */
                break;
            } else if (gpa->balance == 2) {
                /*
                 * Bad balance, heights of left and right
                 * subtrees differ more than by one.
                 */
                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
                     * children, depending on the balance
                     * factor of the grand child (cur).
                     */
                    REBALANCE_DELETE_RL();
                   
                    /*
                     * Repair paternity.
                     */
                    cur->par = gpa->par;
                    gpa->par = cur;
                    par->par = cur;
 
                    if (!repair(t, cur, gpa, cur, &dir,
                        false))
                        break;
                    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) {
                        /*
                         * The right child of the
                         * balanced node is balanced,
                         * after RR rotation is done,
                         * the whole tree will be
                         * balanced.
                         */
                        par->balance = -1;
                        gpa->balance = 1;
 
                        (void) repair(t, par, gpa, par,
                            NULL, false);
                        break;
                    } else {
                        par->balance = 0;
                        gpa->balance = 0;
                        if (!repair(t, par, gpa, par,
                            &dir, false))
                            break;
                    }
                    gpa = par->par;
                }
            } else {
                /*
                 * Repair the pointer which pointed to the
                 * balanced node. If it was root then balancing
                 * is finished else continue with the next
                 * iteration (parent node).
                 */
                if (!repair(t, gpa, gpa, NULL, &dir, true))
                    break;
                gpa = gpa->par;
            }
        } else {
            /*
             * Deletion was made in the right subtree.
             */
            gpa->balance--;
            if (gpa->balance == -1) {
                /*
                 * Stop balancing, the tree is balanced.
                 */
                break;
            } else if (gpa->balance == -2) {
                /*
                 * Bad balance, heights of left and right
                 * subtrees differ more than by one.
                 */
                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
                     * children, depending on the balance
                     * factor of the grand child (cur).
                     */
                    REBALANCE_DELETE_LR();
 
                    /*
                     * Repair paternity.
                     */
                    cur->par = gpa->par;
                    gpa->par = cur;
                    par->par = cur;
 
                    if (!repair(t, cur, gpa, cur, &dir,
                        false))
                        break;
                    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) {
                        /*
                         * The left child of the
                         * balanced node is balanced,
                         * after LL rotation is done,
                         * the whole tree will be
                         * balanced.
                         */
                        par->balance = 1;
                        gpa->balance = -1;
                       
                        (void) repair(t, par, gpa, par,
                            NULL, false);
                        break;
                    } else {
                        par->balance = 0;
                        gpa->balance = 0;
                       
                        if (!repair(t, par, gpa, par,
                            &dir, false))
                            break;
                    }
                    gpa = par->par;
                }
            } else {
                /*
                 * Repair the pointer which pointed to the
                 * balanced node. If it was root then balancing
                 * is finished. Otherwise continue with the next
                 * iteration (parent node).
                 */
                if (!repair(t, gpa, gpa, NULL, &dir, true))
                    break;
                gpa = gpa->par;
            }
        }
    }
}
 
 
/** Delete a node with the smallest key from the AVL tree.
 *
 * @param t AVL tree structure.
 */
bool avltree_delete_min(avltree_t *t)
{
    avltree_node_t *node;
   
    /*
     * Start searching for the smallest key in the tree starting in the root
     * node and continue in cycle to the leftmost node in the tree (which
     * must have the smallest key).
     */
     
    node = t->root;
    if (!node)
        return false;
   
    while (node->lft != NULL)
        node = node->lft;
   
    avltree_delete(t, node);
 
    return true;
}
 
/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
 * visited node.
 *
 * @param node      Node representing the root of an AVL subtree to be
 *          walked.
 * @param walker    Walker function that will be appliad on each visited
 *          node.
 * @param arg       Argument for the walker.
 *
 * @return      Zero if the walk should stop or non-zero otherwise.
 */
static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
    void *arg)
{
    if (node->lft) {
        if (!_avltree_walk(node->lft, walker, arg))
            return false;
    }
    if (!walker(node, arg))
        return false;
    if (node->rgt) {
        if (!_avltree_walk(node->rgt, walker, arg))
            return false;
    }
    return true;
}
 
/** Walk the AVL tree in-order and apply the walker function on each visited
 * node.
 *
 * @param t     AVL tree to be walked.
 * @param walker    Walker function that will be called on each visited
 *          node.
 * @param arg       Argument for the walker.
 */
void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
{
    _avltree_walk(t->root, walker, arg);
}
 
/** @}
 */
 
 

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

Subversion Repositories HelenOS

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