WebSVN – HelenOS – Diff – /branches/network/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;
}
 
static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker)
{
    if (node->lft)
        _avltree_walk(node->lft, walker);
    walker(node);
    if (node->rgt)
        _avltree_walk(node->rgt, walker);
}
 
/** Walk the AVL tree 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.
 */
void avltree_walk(avltree_t *t, avltree_walker_t walker)
{
    _avltree_walk(t->root, walker);
}
 
/** @}
 */
 
 

Rev 2501	Rev 2503
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) \
-		111	top->DIR1 = par->DIR2; \
-		112	if (top->DIR1 != NULL) \
-		113	top->DIR1->par = top; \
-		114	par->par = top->par; \
-		115	top->par = par; \
-		116	par->DIR2 = top; \
-		117	par->balance = 0; \
-		118	top->balance = 0; \
-		119	*dpc = par;
-		120
-		121	#define REBALANCE_INSERT_LL() REBALANCE_INSERT_XX(lft, rgt)
-		122	#define REBALANCE_INSERT_RR() REBALANCE_INSERT_XX(rgt, lft)
-		123
-		124	#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN) \
-		125	gpa = par->DIR2; \
-		126	par->DIR2 = gpa->DIR1; \
-		127	if (gpa->DIR1 != NULL) \
-		128	gpa->DIR1->par = par; \
-		129	gpa->DIR1 = par; \
-		130	par->par = gpa; \
-		131	top->DIR1 = gpa->DIR2; \
-		132	if (gpa->DIR2 != NULL) \
-		133	gpa->DIR2->par = top; \
-		134	gpa->DIR2 = top; \
-		135	gpa->par = top->par; \
-		136	top->par = gpa; \
-		137	\
-		138	if (gpa->balance == -1 * SGN) { \
-		139	par->balance = 0; \
-		140	top->balance = 1 * SGN; \
-		141	} else if (gpa->balance == 0) { \
-		142	par->balance = 0; \
-		143	top->balance = 0; \
-		144	} else { \
-		145	par->balance = -1 * SGN; \
-		146	top->balance = 0; \
-		147	} \
-		148	gpa->balance = 0; \
-		149	*dpc = gpa;
-		150
-		151	#define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1)
-		152	#define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1)
-		153
110	/** Insert new node into AVL tree.	154	/** Insert new node into AVL tree.
111	*	155	*
112	* @param t AVL tree.	156	* @param t AVL tree.
113	* @param newnode New node to be inserted.	157	* @param newnode New node to be inserted.
114	*/	158	*/
115	void avltree_insert(avltree_t t, avltree_node_t newnode)	159	void avltree_insert(avltree_t t, avltree_node_t newnode)
116	{	160	{
117	avltree_node_t *par;	161	avltree_node_t *par;
118	avltree_node_t *gpa;	162	avltree_node_t *gpa;
119	avltree_node_t *top;	163	avltree_node_t *top;
120	avltree_node_t **dpc;	164	avltree_node_t **dpc;
121	avltree_key_t key;	165	avltree_key_t key;
122		166
123	ASSERT(t);	167	ASSERT(t);
124	ASSERT(newnode);	168	ASSERT(newnode);
125		169
126	/*	170	/*
127	* Creating absolute key.	171	* Creating absolute key.
128	*/	172	*/
129	key = newnode->key + t->base;	173	key = newnode->key + t->base;
130		174
131	/*	175	/*
132	* Iteratively descend to the leaf that can contain the new node.	176	* Iteratively descend to the leaf that can contain the new node.
133	* 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 -
134	* it is a place of possible inbalance.	178	* it is a place of possible inbalance.
135	*/	179	*/
136	dpc = &t->root;	180	dpc = &t->root;
137	gpa = NULL;	181	gpa = NULL;
138	top = t->root;	182	top = t->root;
139	while ((par = (*dpc)) != NULL) {	183	while ((par = (*dpc)) != NULL) {
140	if (par->balance != 0) {	184	if (par->balance != 0) {
141	top = par;	185	top = par;
142	}	186	}
143	gpa = par;	187	gpa = par;
144	dpc = par->key > key ? &par->lft: &par->rgt;	188	dpc = par->key > key ? &par->lft: &par->rgt;
145	}	189	}
146		190
147	/*	191	/*
148	* Initialize new node.	192	* Initialize the new node.
149	*/	193	*/
150	newnode->key = key;	194	newnode->key = key;
151	newnode->lft = NULL;	195	newnode->lft = NULL;
152	newnode->rgt = NULL;	196	newnode->rgt = NULL;
153	newnode->par = gpa;	197	newnode->par = gpa;
154	newnode->balance = 0;	198	newnode->balance = 0;
155		199
156	/*	200	/*
157	* Insert first node into the empty tree.	201	* Insert first node into the empty tree.
158	*/	202	*/
159	if (t->root == NULL) {	203	if (t->root == NULL) {
160	*dpc = newnode;	204	*dpc = newnode;
161	return;	205	return;
162	}	206	}
163		207
164	/*	208	/*
165	* Insert new node into previously found leaf place.	209	* Insert the new node into the previously found leaf position.
166	*/	210	*/
167	*dpc = newnode;	211	*dpc = newnode;
168		212
169	/*	213	/*
170	* If the tree contains one node - end.	214	* If the tree contains one node - end.
171	*/	215	*/
172	if (top == NULL)	216	if (top == NULL)
173	return;	217	return;
174		218
175	/*	219	/*
176	* 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
177	* potentially broken balance (top).	221	* potentially broken balance (top).
178	*/	222	*/
179	if (top->par == NULL) {	223	if (top->par == NULL) {
180	dpc = &t->root;	224	dpc = &t->root;
181	} else {	225	} else {
182	if (top->par->lft == top)	226	if (top->par->lft == top)
183	dpc = &top->par->lft;	227	dpc = &top->par->lft;
184	else	228	else
185	dpc = &top->par->rgt;	229	dpc = &top->par->rgt;
186	}	230	}
187		231
188	/*	232	/*
189	* 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
190	* node.	234	* node.
191	*/	235	*/
192	par = top;	236	par = top;
193	while (par != newnode) {	237	while (par != newnode) {
194	if (par->key > key) {	238	if (par->key > key) {
195	par->balance--;	239	par->balance--;
196	par = par->lft;	240	par = par->lft;
197	} else {	241	} else {
198	par->balance++;	242	par->balance++;
199	par = par->rgt;	243	par = par->rgt;
200	}	244	}
201	}	245	}
202		246
203	/*	247	/*
204	* To balance the tree, we must check and balance top node.	248	* To balance the tree, we must check and balance top node.
205	*/	249	*/
206	if (top->balance == -2) {	250	if (top->balance == -2) {
207	par = top->lft;	251	par = top->lft;
208	if (par->balance == -1) {	252	if (par->balance == -1) {
209	/*	253	/*
210	* LL rotation.	254	* LL rotation.
211	*/	255	*/
212	top->lft = par->rgt;	-
213	if (top->lft != NULL)	256	REBALANCE_INSERT_LL();
214	top->lft->par = top;	-
215	par->par = top->par;	-
216	top->par = par;	-
217	par->rgt = top;	-
218	par->balance = 0;	-
219	top->balance = 0;	-
220	*dpc = par;	-
221	} else {	257	} else {
222	/*	258	/*
223	* LR rotation.	259	* LR rotation.
224	*/	260	*/
225	ASSERT(par->balance == 1);	261	ASSERT(par->balance == 1);
226		262
227	gpa = par->rgt;	-
228	par->rgt = gpa->lft;	-
229	if (gpa->lft != NULL)	-
230	gpa->lft->par = par;	263	REBALANCE_INSERT_LR();
231	gpa->lft = par;	-
232	par->par = gpa;	-
233	top->lft = gpa->rgt;	-
234	if (gpa->rgt != NULL)	-
235	gpa->rgt->par = top;	-
236	gpa->rgt = top;	-
237	gpa->par = top->par;	-
238	top->par = gpa;	-
239		-
240	if (gpa->balance == -1) {	-
241	par->balance = 0;	-
242	top->balance = 1;	-
243	} else if (gpa->balance == 0) {	-
244	par->balance = 0;	-
245	top->balance = 0;	-
246	} else {	-
247	par->balance = -1;	-
248	top->balance = 0;	-
249	}	-
250	gpa->balance = 0;	-
251	*dpc = gpa;	-
252	}	264	}
253	} else if (top->balance == 2) {	265	} else if (top->balance == 2) {
254	par = top->rgt;	266	par = top->rgt;
255	if (par->balance == 1) {	267	if (par->balance == 1) {
256	/*	268	/*
257	* RR rotation.	269	* RR rotation.
258	*/	270	*/
259	top->rgt = par->lft;	-
260	if (top->rgt != NULL)	-
261	top->rgt->par = top;	271	REBALANCE_INSERT_RR();
262	par->par = top->par;	-
263	top->par = par;	-
264	par->lft = top;	-
265	par->balance = 0;	-
266	top->balance = 0;	-
267	*dpc = par;	-
268	} else {	272	} else {
269	/*	273	/*
270	* RL rotation.	274	* RL rotation.
271	*/	275	*/
272	ASSERT(par->balance == -1);	276	ASSERT(par->balance == -1);
273		277
274	gpa = par->lft;	-
275	par->lft = gpa->rgt;	-
276	if (gpa->rgt != NULL)	-
277	gpa->rgt->par = par;	-
278	gpa->rgt = par;	-
279	par->par = gpa;	-
280	top->rgt = gpa->lft;	-
281	if (gpa->lft != NULL)	278	REBALANCE_INSERT_RL();
282	gpa->lft->par = top;	-
283	gpa->lft = top;	-
284	gpa->par = top->par;	-
285	top->par = gpa;	-
286		-
287	if (gpa->balance == 1) {	-
288	par->balance = 0;	-
289	top->balance = -1;	-
290	} else if (gpa->balance == 0) {	-
291	par->balance = 0;	-
292	top->balance = 0;	-
293	} else {	-
294	par->balance = 1;	-
295	top->balance = 0;	-
296	}	-
297	gpa->balance = 0;	-
298	*dpc = gpa;	-
299	}	279	}
300	} else {	280	} else {
301	/*	281	/*
302	* Balance is not broken, insertion is finised.	282	* Balance is not broken, insertion is finised.
303	*/	283	*/
304	return;	284	return;
305	}	285	}
306		286
307	}	287	}
308		288
309	/** Repair the tree after reparenting node u.	289	/** Repair the tree after reparenting node u.
310	*	290	*
311	* 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
312	* 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.
313	* 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
314	* same).	294	* same).
315	*	295	*
316	* @param t AVL tree.	296	* @param t AVL tree.
317	* @param u Node whose new parent has a stale child pointer.	297	* @param u Node whose new parent has a stale child pointer.
318	* @param v Stale child of node u's new parent.	298	* @param v Stale child of node u's new parent.
319	* @param w New child of node u's new parent.	299	* @param w New child of node u's new parent.
320	* @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
321	* 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
322	* u's new parent.	302	* u's new parent.
323	* @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
324	* useful for tracking direction via the dir pointer.	304	* useful for tracking direction via the dir pointer.
325	*	305	*
326	* @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
327	* non-zero.	307	* non-zero.
328	*/	308	*/
329	static int	309	static int
330	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,
331	int *dir, int ro)	311	int *dir, int ro)
332	{	312	{
333	if (u->par == NULL) {	313	if (u->par == NULL) {
334	if (!ro)	314	if (!ro)
335	t->root = w;	315	t->root = w;
336	return 0;	316	return 0;
337	} else {	317	} else {
338	if (u->par->lft == v) {	318	if (u->par->lft == v) {
339	if (!ro)	319	if (!ro)
340	u->par->lft = w;	320	u->par->lft = w;
341	if (dir)	321	if (dir)
342	*dir = LEFT;	322	*dir = LEFT;
343	} else {	323	} else {
344	ASSERT(u->par->rgt == v);	324	ASSERT(u->par->rgt == v);
345	if (!ro)	325	if (!ro)
346	u->par->rgt = w;	326	u->par->rgt = w;
347	if (dir)	327	if (dir)
348	*dir = RIGHT;	328	*dir = RIGHT;
349	}	329	}
350	}	330	}
351	return 1;	331	return 1;
352	}	332	}
353		333
354	#define REBALANCE(DIR1, DIR2, SIGN) \	334	#define REBALANCE_DELETE(DIR1, DIR2, SIGN) \
355	if (cur->balance == -1 * SIGN) { \	335	if (cur->balance == -1 * SIGN) { \
356	par->balance = 0; \	336	par->balance = 0; \
357	gpa->balance = 1 * SIGN; \	337	gpa->balance = 1 * SIGN; \
358	if (gpa->DIR1) \	338	if (gpa->DIR1) \
359	gpa->DIR1->par = gpa; \	339	gpa->DIR1->par = gpa; \
360	par->DIR2->par = par; \	340	par->DIR2->par = par; \
361	} else if (cur->balance == 0) { \	341	} else if (cur->balance == 0) { \
362	par->balance = 0; \	342	par->balance = 0; \
363	gpa->balance = 0; \	343	gpa->balance = 0; \
364	if (gpa->DIR1) \	344	if (gpa->DIR1) \
365	gpa->DIR1->par = gpa; \	345	gpa->DIR1->par = gpa; \
366	if (par->DIR2) \	346	if (par->DIR2) \
367	par->DIR2->par = par; \	347	par->DIR2->par = par; \
368	} else { \	348	} else { \
369	par->balance = -1 * SIGN; \	349	par->balance = -1 * SIGN; \
370	gpa->balance = 0; \	350	gpa->balance = 0; \
371	if (par->DIR2) \	351	if (par->DIR2) \
372	par->DIR2->par = par; \	352	par->DIR2->par = par; \
373	gpa->DIR1->par = gpa; \	353	gpa->DIR1->par = gpa; \
374	} \	354	} \
375	cur->balance = 0;	355	cur->balance = 0;
376		356
377	#define REBALANCE_LR() REBALANCE(lft, rgt, 1)	357	#define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1)
378	#define REBALANCE_RL() REBALANCE(rgt, lft, -1)	358	#define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1)
379		359
380	/** Delete a node from the AVL tree.	360	/** Delete a node from the AVL tree.
381	*	361	*
382	* Because multiple identical keys are allowed, the parent pointers are	362	* Because multiple identical keys are allowed, the parent pointers are
383	* essential during deletion.	363	* essential during deletion.
384	*	364	*
385	* @param t AVL tree structure.	365	* @param t AVL tree structure.
386	* @param node Address of the node which will be deleted.	366	* @param node Address of the node which will be deleted.
387	*/	367	*/
388	void avltree_delete(avltree_t t, avltree_node_t node)	368	void avltree_delete(avltree_t t, avltree_node_t node)
389	{	369	{
390	avltree_node_t *cur;	370	avltree_node_t *cur;
391	avltree_node_t *par;	371	avltree_node_t *par;
392	avltree_node_t *gpa;	372	avltree_node_t *gpa;
393	int dir;	373	int dir;
394		374
395	ASSERT(t);	375	ASSERT(t);
396	ASSERT(node);	376	ASSERT(node);
397		377
398	if (node->lft == NULL) {	378	if (node->lft == NULL) {
399	if (node->rgt) {	379	if (node->rgt) {
400	/*	380	/*
401	* Replace the node with its only right son.	381	* Replace the node with its only right son.
402	*	382	*
403	* Balance of the right son will be repaired in the	383	* Balance of the right son will be repaired in the
404	* balancing cycle.	384	* balancing cycle.
405	*/	385	*/
406	cur = node->rgt;	386	cur = node->rgt;
407	cur->par = node->par;	387	cur->par = node->par;
408	gpa = cur;	388	gpa = cur;
409	dir = RIGHT;	389	dir = RIGHT;
410	cur->balance = node->balance;	390	cur->balance = node->balance;
411	} else {	391	} else {
412	if (node->par == NULL) {	392	if (node->par == NULL) {
413	/*	393	/*
414	* The tree has only one node - it will become	394	* The tree has only one node - it will become
415	* an empty tree and the balancing can end.	395	* an empty tree and the balancing can end.
416	*/	396	*/
417	t->root = NULL;	397	t->root = NULL;
418	return;	398	return;
419	}	399	}
420	/*	400	/*
421	* The node has no child, it will be deleted with no	401	* The node has no child, it will be deleted with no
422	* substitution.	402	* substitution.
423	*/	403	*/
424	gpa = node->par;	404	gpa = node->par;
425	cur = NULL;	405	cur = NULL;
426	dir = (gpa->lft == node) ? LEFT: RIGHT;	406	dir = (gpa->lft == node) ? LEFT: RIGHT;
427	}	407	}
428	} else {	408	} else {
429	/*	409	/*
430	* 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
431	* in the left subtree and replace the deleted node with that	411	* in the left subtree and replace the deleted node with that
432	* node.	412	* node.
433	*/	413	*/
434	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)	414	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
435	;	415	;
436		416
437	if (cur != node->lft) {	417	if (cur != node->lft) {
438	/*	418	/*
439	* The rightmost node of the deleted node's left subtree	419	* The rightmost node of the deleted node's left subtree
440	* was found. Replace the deleted node with this node.	420	* was found. Replace the deleted node with this node.
441	* Cutting off of the found node has two cases that	421	* Cutting off of the found node has two cases that
442	* depend on its left son.	422	* depend on its left son.
443	*/	423	*/
444	if (cur->lft) {	424	if (cur->lft) {
445	/*	425	/*
446	* The found node has a left son.	426	* The found node has a left son.
447	*/	427	*/
448	gpa = cur->lft;	428	gpa = cur->lft;
449	gpa->par = cur->par;	429	gpa->par = cur->par;
450	dir = LEFT;	430	dir = LEFT;
451	gpa->balance = cur->balance;	431	gpa->balance = cur->balance;
452	} else {	432	} else {
453	dir = RIGHT;	433	dir = RIGHT;
454	gpa = cur->par;	434	gpa = cur->par;
455	}	435	}
456	cur->par->rgt = cur->lft;	436	cur->par->rgt = cur->lft;

Subversion Repositories HelenOS

(root)/branches/network/kernel/generic/src/adt/avl.c @ 4263 – Rev 2501 → 2503