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.
 *
 * @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);
 
 
 
 
 
 
    return true;
}
 

Rev 2421	Rev 2450
1	/*	1	/*
2	* Copyright (c) 2007 Vojtech Mencl	2	* Copyright (c) 2007 Vojtech Mencl
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/** @addtogroup genericadt	29	/** @addtogroup genericadt
30	* @{	30	* @{
31	*/	31	*/
32		32
33	/**	33	/**
34	* @file	34	* @file
35	* @brief AVL tree implementation.	35	* @brief AVL tree implementation.
36	*	36	*
37	* This file implements AVL tree type and operations.	37	* This file implements AVL tree type and operations.
38	*	38	*
39	* Implemented AVL tree has the following properties:	39	* Implemented AVL tree has the following properties:
40	* @li it is binary search tree with non-unique keys	40	* @li it is binary search tree with non-unique keys
41	* @li Difference of heights of left and right subtree of every node is max 1.	41	* @li Difference of heights of left and right subtree of every node is max 1.
42	*	42	*
43	* Every node has pointer to its parent which allows insertion of multiple identical keys	43	* Every node has pointer to its parent which allows insertion of multiple identical keys
44	* into tree.	44	* into tree.
45	*	45	*
46	* Be careful of using this tree because of base atribute, which is added to every inserted	46	* Be careful of using this tree because of base atribute, which is added to every inserted
47	* node key. There is no rule in which order nodes with the same key are visited.	47	* node key. There is no rule in which order nodes with the same key are visited.
48	*/	48	*/
49		49
50	#include <adt/avl.h>	50	#include <adt/avl.h>
51	#include <debug.h>	51	#include <debug.h>
52	#include <panic.h>	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 node 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.	87	/** Find node with smallest key in AVL tree.
88	*	88	*
89	* @param t AVL tree.	89	* @param t AVL tree.
90	*	90	*
91	* @return Pointer to node or NULL if there is no node in the tree.	91	* @return Pointer to node or NULL if there is no node in the tree.
92	*/	92	*/
93	avltree_node_t avltree_find_min(avltree_t t)	93	avltree_node_t avltree_find_min(avltree_t t)
94	{	94	{
95	avltree_node_t *p = t->root;	95	avltree_node_t *p = t->root;
96		96
97	/*	97	/*
98	* Check whether tree is empty.	98	* Check whether tree is empty.
99	*/	99	*/
100	if (!p) return NULL;	100	if (!p) return NULL;
101		101
102	/*	102	/*
103	* Iteratively descend to the leftmost leaf in the tree.	103	* Iteratively descend to the leftmost leaf in the tree.
104	*/	104	*/
105	while (p->lft != NULL)	105	while (p->lft != NULL)
106	p = p->lft;	106	p = p->lft;
107		107
108	return p;	108	return p;
109	}	109	}
110		110
111	/** Insert new node into AVL tree.	111	/** Insert new node into AVL tree.
112	*	112	*
113	* @param t AVL tree.	113	* @param t AVL tree.
114	* @param newnode New node to be inserted.	114	* @param newnode New node to be inserted.
115	*/	115	*/
116	void avltree_insert(avltree_t t, avltree_node_t newnode)	116	void avltree_insert(avltree_t t, avltree_node_t newnode)
117	{	117	{
118	avltree_node_t *par;	118	avltree_node_t *par;
119	avltree_node_t *gpa;	119	avltree_node_t *gpa;
120	avltree_node_t *top;	120	avltree_node_t *top;
121	avltree_node_t **dpc;	121	avltree_node_t **dpc;
122	uint64_t key;	122	uint64_t key;
123		123
124	ASSERT(t);	124	ASSERT(t);
125	ASSERT(newnode);	125	ASSERT(newnode);
126		126
127	/*	127	/*
128	* Creating absolute key.	128	* Creating absolute key.
129	*/	129	*/
130	key = newnode->key + t->base;	130	key = newnode->key + t->base;
131		131
132		132
133	/*	133	/*
134	* Iteratively descend to the leaf that can will contain new node.	134	* Iteratively descend to the leaf that can will contain new node.
135	* 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 -
136	* it si place of possible balance failure.	136	* it si place of possible balance failure.
137	*/	137	*/
138	dpc = &t->root;	138	dpc = &t->root;
139	gpa = NULL;	139	gpa = NULL;
140	top = t->root;	140	top = t->root;
141	while ((par = (*dpc)) != NULL) {	141	while ((par = (*dpc)) != NULL) {
142	if (par->balance != 0) {	142	if (par->balance != 0) {
143	top = par;	143	top = par;
144	}	144	}
145	gpa = par;	145	gpa = par;
146	dpc = par->key > key? &par->lft: &par->rgt;	146	dpc = par->key > key? &par->lft: &par->rgt;
147	}	147	}
148		148
149	/*	149	/*
150	* Initialize new node.	150	* Initialize new node.
151	*/	151	*/
152	newnode->key = key;	152	newnode->key = key;
153	newnode->lft = NULL;	153	newnode->lft = NULL;
154	newnode->rgt = NULL;	154	newnode->rgt = NULL;
155	newnode->par = gpa;	155	newnode->par = gpa;
156	newnode->balance = 0;	156	newnode->balance = 0;
157		157
158	/*	158	/*
159	* Insert first node into empty tree.	159	* Insert first node into empty tree.
160	*/	160	*/
161	if (t->root == NULL) {	161	if (t->root == NULL) {
162	*dpc = newnode;	162	*dpc = newnode;
163	return;	163	return;
164	}	164	}
165		165
166	/*	166	/*
167	* Insert new node into previously found leaf place.	167	* Insert new node into previously found leaf place.
168	*/	168	*/
169	*dpc = newnode;	169	*dpc = newnode;
170		170
171	/*	171	/*
172	* If tree contains one node - end.	172	* If tree contains one node - end.
173	*/	173	*/
174	if (top == NULL) return;	174	if (top == NULL) return;
175		175
176	/*	176	/*
177	* 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
178	* balance (top).	178	* balance (top).
179	*/	179	*/
180	if (top->par == NULL)	180	if (top->par == NULL)
181	dpc = &t->root;	181	dpc = &t->root;
182	else	182	else
183	if (top->par->lft == top)	183	if (top->par->lft == top)
184	dpc = &(top->par->lft);	184	dpc = &(top->par->lft);
185	else	185	else
186	dpc = &(top->par->rgt);	186	dpc = &(top->par->rgt);
187		187
188	/*	188	/*
189	* 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.
190	*/	190	*/
191	par = top;	191	par = top;
192	while (par != newnode) {	192	while (par != newnode) {
193	if (par->key > key) {	193	if (par->key > key) {
194	par->balance--;	194	par->balance--;
195	par = par->lft;	195	par = par->lft;
196	} else {	196	} else {
197	par->balance++;	197	par->balance++;
198	par = par->rgt;	198	par = par->rgt;
199	}	199	}
200	}	200	}
201		201
202	/*	202	/*
203	* To balance tree we must check and balance top node.	203	* To balance tree we must check and balance top node.
204	*/	204	*/
205	if (top->balance == -2) {	205	if (top->balance == -2) {
206	par = top->lft;	206	par = top->lft;
207	if (par->balance == -1) {	207	if (par->balance == -1) {
208	/*	208	/*
209	* LL rotation.	209	* LL rotation.
210	*/	210	*/
211	top->lft = par->rgt;	211	top->lft = par->rgt;
212	if (top->lft != NULL) top->lft->par = top;	212	if (top->lft != NULL) top->lft->par = top;
213	par->par = top->par;	213	par->par = top->par;
214	top->par = par;	214	top->par = par;
215	par->rgt = top;	215	par->rgt = top;
216	par->balance = top->balance = 0;	216	par->balance = top->balance = 0;
217	*dpc = par;	217	*dpc = par;
218	} else {	218	} else {
219	/*	219	/*
220	* LR rotation.	220	* LR rotation.
221	*/	221	*/
222	ASSERT(par->balance == 1);	222	ASSERT(par->balance == 1);
223		223
224	gpa = par->rgt;	224	gpa = par->rgt;
225	par->rgt = gpa->lft;	225	par->rgt = gpa->lft;
226	if (gpa->lft != NULL) gpa->lft->par = par;	226	if (gpa->lft != NULL) gpa->lft->par = par;
227	gpa->lft = par;	227	gpa->lft = par;
228	par->par = gpa;	228	par->par = gpa;
229	top->lft = gpa->rgt;	229	top->lft = gpa->rgt;
230	if (gpa->rgt != NULL) gpa->rgt->par = top;	230	if (gpa->rgt != NULL) gpa->rgt->par = top;
231	gpa->rgt = top;	231	gpa->rgt = top;
232	gpa->par = top->par;	232	gpa->par = top->par;
233	top->par = gpa;	233	top->par = gpa;
234		234
235	if (gpa->balance == -1) {	235	if (gpa->balance == -1) {
236	par->balance = 0;	236	par->balance = 0;
237	top->balance = 1;	237	top->balance = 1;
238	} else if (gpa->balance == 0) {	238	} else if (gpa->balance == 0) {
239	par->balance = top->balance = 0;	239	par->balance = top->balance = 0;
240	} else {	240	} else {
241	par->balance = -1;	241	par->balance = -1;
242	top->balance = 0;	242	top->balance = 0;
243	}	243	}
244	gpa->balance = 0;	244	gpa->balance = 0;
245	*dpc = gpa;	245	*dpc = gpa;
246	}	246	}
247	} else if (top->balance == 2) {	247	} else if (top->balance == 2) {
248	par = top->rgt;	248	par = top->rgt;
249	if (par->balance == 1) {	249	if (par->balance == 1) {
250	/*	250	/*
251	* RR rotation.	251	* RR rotation.
252	*/	252	*/
253	top->rgt = par->lft;	253	top->rgt = par->lft;
254	if (top->rgt != NULL) top->rgt->par = top;	254	if (top->rgt != NULL) top->rgt->par = top;
255	par->par = top->par;	255	par->par = top->par;
256	top->par = par;	256	top->par = par;
257	par->lft = top;	257	par->lft = top;
258	par->balance = top->balance = 0;	258	par->balance = top->balance = 0;
259	*dpc = par;	259	*dpc = par;
260	} else {	260	} else {
261	/*	261	/*
262	* RL rotation.	262	* RL rotation.
263	*/	263	*/
264	ASSERT(par->balance == -1);	264	ASSERT(par->balance == -1);
265		265
266	gpa = par->lft;	266	gpa = par->lft;
267	par->lft = gpa->rgt;	267	par->lft = gpa->rgt;
268	if (gpa->rgt != NULL) gpa->rgt->par = par;	268	if (gpa->rgt != NULL) gpa->rgt->par = par;
269	gpa->rgt = par;	269	gpa->rgt = par;
270	par->par = gpa;	270	par->par = gpa;
271	top->rgt = gpa->lft;	271	top->rgt = gpa->lft;
272	if (gpa->lft != NULL) gpa->lft->par = top;	272	if (gpa->lft != NULL) gpa->lft->par = top;
273	gpa->lft = top;	273	gpa->lft = top;
274	gpa->par = top->par;	274	gpa->par = top->par;
275	top->par = gpa;	275	top->par = gpa;
276		276
277	if (gpa->balance == 1) {	277	if (gpa->balance == 1) {
278	par->balance = 0;	278	par->balance = 0;
279	top->balance = -1;	279	top->balance = -1;
280	} else if (gpa->balance == 0) {	280	} else if (gpa->balance == 0) {
281	par->balance = top->balance = 0;	281	par->balance = top->balance = 0;
282	} else {	282	} else {
283	par->balance = 1;	283	par->balance = 1;
284	top->balance = 0;	284	top->balance = 0;
285	}	285	}
286	gpa->balance = 0;	286	gpa->balance = 0;
287	*dpc = gpa;	287	*dpc = gpa;
288	}	288	}
289	} else {	289	} else {
290	/*	290	/*
291	* Balance is not broken, insertion is finised.	291	* Balance is not broken, insertion is finised.
292	*/	292	*/
293	return;	293	return;
294	}	294	}
295		295
296	}	296	}
297		297
298	/** Delete node from AVL tree.	298	/** Delete node from AVL tree.
299	*	299	*
300	* Because of allowed multiple identical keys parent pointers are essential	300	* Because of allowed multiple identical keys parent pointers are essential
301	* during deletition.	301	* during deletition.
302	*	302	*
303	* @param t AVL tree structure.	303	* @param t AVL tree structure.
304	* @param node Address of node which will be deleted.	304	* @param node Address of node which will be deleted.
305	*/	305	*/
306	void avltree_delete(avltree_t t, avltree_node_t node)	306	void avltree_delete(avltree_t t, avltree_node_t node)
307	{	307	{
308	avltree_node_t *cur;	308	avltree_node_t *cur;
309	avltree_node_t *par;	309	avltree_node_t *par;
310	avltree_node_t *gpa;	310	avltree_node_t *gpa;
311	uint8_t dir;	311	uint8_t dir;
312		312
313	ASSERT(t);	313	ASSERT(t);
314	ASSERT(node);	314	ASSERT(node);
315		315
316		316
317	if (node->lft == NULL) {	317	if (node->lft == NULL) {
318	if (node->rgt) {	318	if (node->rgt) {
319	/*	319	/*
320	* Replace node with its only right son.	320	* Replace node with its only right son.
321	*	321	*
322	* Balance of right son will be repaired in balancing cycle.	322	* Balance of right son will be repaired in balancing cycle.
323	*/	323	*/
324	cur = node->rgt;	324	cur = node->rgt;
325	cur->par = node->par;	325	cur->par = node->par;
326	gpa = cur;	326	gpa = cur;
327	dir = AVLTREE_RIGHT;	327	dir = AVLTREE_RIGHT;
328	cur->balance = node->balance;	328	cur->balance = node->balance;
329	} else {	329	} else {
330	if (node->par == NULL) {	330	if (node->par == NULL) {
331	/*	331	/*
332	* 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.
333	*/	333	*/
334	t->root = NULL;	334	t->root = NULL;
335	return;	335	return;
336	}	336	}
337	/*	337	/*
338	* Node has no child, will be deleted with no substitution.	338	* Node has no child, will be deleted with no substitution.
339	*/	339	*/
340	gpa = node->par;	340	gpa = node->par;
341	cur = NULL;	341	cur = NULL;
342	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;	342	dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
343	}	343	}
344	} else {	344	} else {
345	/*	345	/*
346	* 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
347	* and replace deleted node with that node.	347	* and replace deleted node with that node.
348	*/	348	*/
349	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)	349	for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
350	;	350	;
351		351
352	//cur obsahuje uzel, ktery vlozim misto uzlu node	352	//cur obsahuje uzel, ktery vlozim misto uzlu node
353		353
354	if (cur != node->lft) {	354	if (cur != node->lft) {
355	/*	355	/*
356	* 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
357	* 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
358	* dependence on its left son.	358	* dependence on its left son.
359	*/	359	*/
360	if (cur->lft) {	360	if (cur->lft) {
361	/*	361	/*
362	* Founded node has left son.	362	* Founded node has left son.
363	*/	363	*/
364	gpa = cur->lft;	364	gpa = cur->lft;
365	gpa->par = cur->par;	365	gpa->par = cur->par;
366	dir = AVLTREE_LEFT;	366	dir = AVLTREE_LEFT;
367	gpa->balance = cur->balance;	367	gpa->balance = cur->balance;
368	} else {	368	} else {
369	dir = AVLTREE_RIGHT;	369	dir = AVLTREE_RIGHT;
370	gpa = cur->par;	370	gpa = cur->par;
371	}	371	}
372	cur->par->rgt = cur->lft;	372	cur->par->rgt = cur->lft;
373	cur->lft = node->lft;	373	cur->lft = node->lft;
374	cur->lft->par = cur;	374	cur->lft->par = cur;
375	} else {	375	} else {
376	/*	376	/*
377	* 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.
378	*/	378	*/
379	dir = AVLTREE_LEFT;	379	dir = AVLTREE_LEFT;
380	gpa = cur;	380	gpa = cur;
381	}	381	}
382	if (node->rgt) node->rgt->par = cur;	382	if (node->rgt) node->rgt->par = cur;
383	cur->rgt = node->rgt;	383	cur->rgt = node->rgt;
384	cur->balance = node->balance;	384	cur->balance = node->balance;
385	cur->par = node->par;	385	cur->par = node->par;
386	}	386	}
387		387
388	/*	388	/*
389	* Repair parent nodes pointer which pointed previously to deleted node.	389	* Repair parent nodes pointer which pointed previously to deleted node.
390	*/	390	*/
391	if (node->par == NULL) {	391	if (node->par == NULL) {
392	t->root = cur;	392	t->root = cur;
393	} else {	393	} else {
394	if (node->par->lft == node) {	394	if (node->par->lft == node) {
395	node->par->lft = cur;	395	node->par->lft = cur;
396	} else {	396	} else {
397	node->par->rgt = cur;	397	node->par->rgt = cur;
398	}	398	}
399	}	399	}
400		400
401	/*	401	/*
402	* 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.
403	*/	403	*/
404	for(;;) {	404	for(;;) {
405	if (dir == AVLTREE_LEFT) {	405	if (dir == AVLTREE_LEFT) {
406	/*	406	/*
407	* Deletition was made in left subtree.	407	* Deletition was made in left subtree.
408	*/	408	*/
409	gpa->balance++;	409	gpa->balance++;
410	if (gpa->balance == +1) {	410	if (gpa->balance == +1) {
411	/*	411	/*
412	* Stop balancing, tree is balanced.	412	* Stop balancing, tree is balanced.
413	*/	413	*/
414	break;	414	break;
415	} else if (gpa->balance == +2) {	415	} else if (gpa->balance == +2) {
416	/*	416	/*
417	* 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.
418	*/	418	*/
419	par = gpa->rgt;	419	par = gpa->rgt;
420		420
421	if (par->balance == -1) {	421	if (par->balance == -1) {
422	/*	422	/*
423	* RL rotation.	423	* RL rotation.
424	*/	424	*/
425		425
426	cur = par->lft;	426	cur = par->lft;
427	par->lft = cur->rgt;	427	par->lft = cur->rgt;
428	cur->rgt = par;	428	cur->rgt = par;
429	gpa->rgt = cur->lft;	429	gpa->rgt = cur->lft;
430	cur->lft = gpa;	430	cur->lft = gpa;
431		431
432	/*	432	/*
433	* Repair balances and paternity of childs in dependence on	433	* Repair balances and paternity of childs in dependence on
434	* balance factor of grand child (cur).	434	* balance factor of grand child (cur).
435	*/	435	*/
436	if (cur->balance == +1) {	436	if (cur->balance == +1) {
437	par->balance = 0;	437	par->balance = 0;
438	gpa->balance = -1;	438	gpa->balance = -1;
439	if (gpa->rgt) gpa->rgt->par = gpa;	439	if (gpa->rgt) gpa->rgt->par = gpa;
440	par->lft->par = par;	440	par->lft->par = par;
441	} else if (cur->balance == 0) {	441	} else if (cur->balance == 0) {
442	par->balance = gpa->balance = 0;	442	par->balance = gpa->balance = 0;
443	if (gpa->rgt) gpa->rgt->par = gpa;	443	if (gpa->rgt) gpa->rgt->par = gpa;
444	if (par->lft) par->lft->par = par;	444	if (par->lft) par->lft->par = par;
445	} else {	445	} else {
446	par->balance = +1;	446	par->balance = +1;
447	gpa->balance = 0;	447	gpa->balance = 0;
448	if (par->lft) par->lft->par = par;	448	if (par->lft) par->lft->par = par;
449	gpa->rgt->par = gpa;	449	gpa->rgt->par = gpa;
450	}	450	}
451	cur->balance = 0;	451	cur->balance = 0;
452		452
453	/*	453	/*
454	* Repair paternity.	454	* Repair paternity.
455	*/	455	*/
456	cur->par = gpa->par;	456	cur->par = gpa->par;
457	gpa->par = cur;	457	gpa->par = cur;
458	par->par = cur;	458	par->par = cur;
459		459
460	/*	460	/*
461	* 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
462	* is finished else continue in next iteration (parent node).	462	* is finished else continue in next iteration (parent node).
463	*/	463	*/
464	if (cur->par == NULL) {	464	if (cur->par == NULL) {
465	t->root = cur;	465	t->root = cur;
466	break;	466	break;
467	} else	467	} else
468	if (cur->par->lft == gpa) {	468	if (cur->par->lft == gpa) {
469	cur->par->lft = cur;	469	cur->par->lft = cur;
470	dir = AVLTREE_LEFT;	470	dir = AVLTREE_LEFT;
471	} else {	471	} else {
472	cur->par->rgt = cur;	472	cur->par->rgt = cur;
473	dir = AVLTREE_RIGHT;	473	dir = AVLTREE_RIGHT;
474	}	474	}
475	gpa = cur->par;	475	gpa = cur->par;
476	} else {	476	} else {
477	/*	477	/*
478	* RR rotation.	478	* RR rotation.
479	*/	479	*/
480		480
481	gpa->rgt = par->lft;	481	gpa->rgt = par->lft;
482	if (par->lft) par->lft->par = gpa;	482	if (par->lft) par->lft->par = gpa;
483	par->lft = gpa;	483	par->lft = gpa;
484		484
485	/*	485	/*
486	* Repair paternity.	486	* Repair paternity.
487	*/	487	*/
488	par->par = gpa->par;	488	par->par = gpa->par;
489	gpa->par = par;	489	gpa->par = par;
490		490
491	if (par->balance == 0) {	491	if (par->balance == 0) {
492	/*	492	/*
493	* 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
494	* tree will be balanced.	494	* tree will be balanced.
495	*/	495	*/
496	par->balance = -1;	496	par->balance = -1;
497	gpa->balance = +1;	497	gpa->balance = +1;
498		498
499	/*	499	/*
500	* 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 2421 → 2450