Subversion Repositories HelenOS

Rev

Rev 2503 | Rev 3908 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2007 Vojtech Mencl
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  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
  15.  *   derived from this software without specific prior written permission.
  16.  *
  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
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  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
  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
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup genericadt
  30.  * @{
  31.  */
  32.  
  33. /**
  34.  * @file
  35.  * @brief   AVL tree implementation.
  36.  *
  37.  * This file implements AVL tree type and operations.
  38.  *
  39.  * Implemented AVL tree has the following properties:
  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
  42.  *     one at maximum.
  43.  *
  44.  * Every node has a pointer to its parent which allows insertion of multiple
  45.  * identical keys into the tree.
  46.  *
  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
  49.  * same key are visited.
  50.  */
  51.  
  52. #include <adt/avl.h>
  53. #include <debug.h>
  54.  
  55. #define LEFT    0
  56. #define RIGHT   1
  57.  
  58. /** Search for the first occurence of the given key in an AVL tree.
  59.  *
  60.  * @param t AVL tree.
  61.  * @param key Key to be searched.
  62.  *
  63.  * @return Pointer to a node or NULL if there is no such key.
  64.  */
  65. avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
  66. {
  67.     avltree_node_t *p;
  68.    
  69.     /*
  70.      * Iteratively descend to the leaf that can contain the searched key.
  71.      */
  72.     p = t->root;
  73.     while (p != NULL) {
  74.         if (p->key > key)
  75.             p = p->lft;
  76.         else if (p->key < key)
  77.             p = p->rgt;
  78.         else
  79.             return p;
  80.     }
  81.     return NULL;
  82. }
  83.  
  84.  
  85. /** Find the node with the smallest key in an AVL tree.
  86.  *
  87.  * @param t AVL tree.
  88.  *
  89.  * @return Pointer to a node or NULL if there is no node in the tree.
  90.  */
  91. avltree_node_t *avltree_find_min(avltree_t *t)
  92. {
  93.     avltree_node_t *p = t->root;
  94.    
  95.     /*
  96.      * Check whether the tree is empty.
  97.      */
  98.     if (!p)
  99.         return NULL;
  100.    
  101.     /*
  102.      * Iteratively descend to the leftmost leaf in the tree.
  103.      */
  104.     while (p->lft != NULL)
  105.         p = p->lft;
  106.    
  107.     return p;
  108. }
  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.    
  154. /** Insert new node into AVL tree.
  155.  *
  156.  * @param t AVL tree.
  157.  * @param newnode New node to be inserted.
  158.  */
  159. void avltree_insert(avltree_t *t, avltree_node_t *newnode)
  160. {  
  161.     avltree_node_t *par;
  162.     avltree_node_t *gpa;
  163.     avltree_node_t *top;
  164.     avltree_node_t **dpc;
  165.     avltree_key_t key;
  166.  
  167.     ASSERT(t);
  168.     ASSERT(newnode);
  169.  
  170.     /*
  171.      * Creating absolute key.
  172.      */
  173.     key = newnode->key + t->base;
  174.    
  175.     /*
  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 -
  178.      * it is a place of possible inbalance.
  179.      */
  180.     dpc = &t->root;
  181.     gpa = NULL;
  182.     top = t->root;
  183.     while ((par = (*dpc)) != NULL) {
  184.         if (par->balance != 0) {
  185.             top = par;
  186.         }
  187.         gpa = par;
  188.         dpc = par->key > key ? &par->lft: &par->rgt;
  189.     }
  190.  
  191.     /*
  192.      * Initialize the new node.
  193.      */
  194.     newnode->key = key;
  195.     newnode->lft = NULL;
  196.     newnode->rgt = NULL;
  197.     newnode->par = gpa;
  198.     newnode->balance = 0;
  199.  
  200.     /*
  201.      * Insert first node into the empty tree.
  202.      */
  203.     if (t->root == NULL) {
  204.         *dpc = newnode;
  205.         return;
  206.     }
  207.  
  208.     /*
  209.      * Insert the new node into the previously found leaf position.
  210.      */
  211.     *dpc = newnode;
  212.  
  213.     /*
  214.      * If the tree contains one node - end.
  215.      */
  216.     if (top == NULL)
  217.         return;
  218.  
  219.     /*
  220.      * Store pointer of top's father which points to the node with
  221.      * potentially broken balance (top).
  222.      */
  223.     if (top->par == NULL) {
  224.         dpc = &t->root;
  225.     } else {
  226.         if (top->par->lft == top)
  227.             dpc = &top->par->lft;
  228.         else
  229.             dpc = &top->par->rgt;
  230.     }
  231.  
  232.     /*
  233.      * Repair all balances on the way from top node to the newly inserted
  234.      * node.
  235.      */
  236.     par = top;
  237.     while (par != newnode) {
  238.         if (par->key > key) {
  239.             par->balance--;
  240.             par = par->lft;
  241.         } else {
  242.             par->balance++;
  243.             par = par->rgt;
  244.         }
  245.     }
  246.    
  247.     /*
  248.      * To balance the tree, we must check and balance top node.
  249.      */
  250.     if (top->balance == -2) {
  251.         par = top->lft;
  252.         if (par->balance == -1) {
  253.             /*
  254.              * LL rotation.
  255.              */
  256.             REBALANCE_INSERT_LL();
  257.         } else {
  258.             /*
  259.              * LR rotation.
  260.              */
  261.             ASSERT(par->balance == 1);
  262.            
  263.             REBALANCE_INSERT_LR();
  264.         }
  265.     } else if (top->balance == 2) {
  266.         par = top->rgt;
  267.         if (par->balance == 1) {
  268.             /*
  269.              * RR rotation.
  270.              */
  271.             REBALANCE_INSERT_RR();
  272.         } else {
  273.             /*
  274.              * RL rotation.
  275.              */
  276.             ASSERT(par->balance == -1);
  277.        
  278.             REBALANCE_INSERT_RL();
  279.         }
  280.     } else {
  281.         /*
  282.          * Balance is not broken, insertion is finised.
  283.          */
  284.         return;
  285.     }
  286.  
  287. }
  288.  
  289. /** Repair the tree after reparenting node u.
  290.  *
  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.
  293.  * Replace v with w as node u parent's child (for most uses, u and w will be the
  294.  * same).
  295.  *
  296.  * @param t AVL tree.
  297.  * @param u Node whose new parent has a stale child pointer.
  298.  * @param v Stale 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
  301.  *      about whether w replaced v in the left or the right subtree of
  302.  *      u's new parent.
  303.  * @param ro    Read only operation; do not modify any tree pointers. This is
  304.  *      useful for tracking direction via the dir pointer.
  305.  *
  306.  * @return  Zero if w became the new root of the tree, otherwise return
  307.  *      non-zero.
  308.  */
  309. static int
  310. repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
  311.     int *dir, int ro)
  312. {
  313.     if (u->par == NULL) {
  314.         if (!ro)
  315.             t->root = w;   
  316.         return 0;
  317.     } else {   
  318.         if (u->par->lft == v) {
  319.             if (!ro)
  320.                 u->par->lft = w;
  321.             if (dir)
  322.                 *dir = LEFT;
  323.         } else {
  324.             ASSERT(u->par->rgt == v);
  325.             if (!ro)
  326.                 u->par->rgt = w;
  327.             if (dir)
  328.                 *dir = RIGHT;
  329.         }
  330.     }
  331.     return 1;
  332. }
  333.  
  334. #define REBALANCE_DELETE(DIR1, DIR2, SIGN)  \
  335.     if (cur->balance == -1 * SIGN) {    \
  336.         par->balance = 0;       \
  337.         gpa->balance = 1 * SIGN;    \
  338.         if (gpa->DIR1)          \
  339.             gpa->DIR1->par = gpa;   \
  340.         par->DIR2->par = par;       \
  341.     } else if (cur->balance == 0) {     \
  342.         par->balance = 0;       \
  343.         gpa->balance = 0;       \
  344.         if (gpa->DIR1)          \
  345.             gpa->DIR1->par = gpa;   \
  346.         if (par->DIR2)          \
  347.             par->DIR2->par = par;   \
  348.     } else {                \
  349.         par->balance = -1 * SIGN;   \
  350.         gpa->balance = 0;       \
  351.         if (par->DIR2)          \
  352.             par->DIR2->par = par;   \
  353.         gpa->DIR1->par = gpa;       \
  354.     }                   \
  355.     cur->balance = 0;
  356.  
  357. #define REBALANCE_DELETE_LR()       REBALANCE_DELETE(lft, rgt, 1)
  358. #define REBALANCE_DELETE_RL()       REBALANCE_DELETE(rgt, lft, -1)
  359.  
  360. /** Delete a node from the AVL tree.
  361.  *
  362.  * Because multiple identical keys are allowed, the parent pointers are
  363.  * essential during deletion.
  364.  *
  365.  * @param t AVL tree structure.
  366.  * @param node Address of the node which will be deleted.
  367.  */
  368. void avltree_delete(avltree_t *t, avltree_node_t *node)
  369. {
  370.     avltree_node_t *cur;
  371.     avltree_node_t *par;
  372.     avltree_node_t *gpa;
  373.     int dir;
  374.  
  375.     ASSERT(t);
  376.     ASSERT(node);
  377.    
  378.     if (node->lft == NULL) {
  379.         if (node->rgt) {
  380.             /*
  381.              * Replace the node with its only right son.
  382.              *
  383.              * Balance of the right son will be repaired in the
  384.              * balancing cycle.
  385.              */
  386.             cur = node->rgt;
  387.             cur->par = node->par;
  388.             gpa = cur;
  389.             dir = RIGHT;
  390.             cur->balance = node->balance;
  391.         } else {
  392.             if (node->par == NULL) {
  393.                 /*
  394.                  * The tree has only one node - it will become
  395.                  * an empty tree and the balancing can end.
  396.                  */
  397.                 t->root = NULL;
  398.                 return;
  399.             }
  400.             /*
  401.              * The node has no child, it will be deleted with no
  402.              * substitution.
  403.              */
  404.             gpa = node->par;
  405.             cur = NULL;
  406.             dir = (gpa->lft == node) ? LEFT: RIGHT;
  407.         }
  408.     } else {
  409.         /*
  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
  412.          * node.
  413.          */
  414.         for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
  415.             ;
  416.  
  417.         if (cur != node->lft) {
  418.             /*
  419.              * The rightmost node of the deleted node's left subtree
  420.              * was found. Replace the deleted node with this node.
  421.              * Cutting off of the found node has two cases that
  422.              * depend on its left son.
  423.              */
  424.             if (cur->lft) {
  425.                 /*
  426.                  * The found node has a left son.
  427.                  */
  428.                 gpa = cur->lft;
  429.                 gpa->par = cur->par;
  430.                 dir = LEFT;
  431.                 gpa->balance = cur->balance;
  432.             } else {
  433.                 dir = RIGHT;
  434.                 gpa = cur->par;
  435.             }
  436.             cur->par->rgt = cur->lft;
  437.             cur->lft = node->lft;
  438.             cur->lft->par = cur;
  439.         } else {
  440.             /*
  441.              * The left son of the node hasn't got a right son. The
  442.              * left son will take the deleted node's place.
  443.              */
  444.             dir = LEFT;
  445.             gpa = cur;
  446.         }
  447.         if (node->rgt)
  448.             node->rgt->par = cur;
  449.         cur->rgt = node->rgt;
  450.         cur->balance = node->balance;
  451.         cur->par = node->par;
  452.     }
  453.    
  454.     /*
  455.      * Repair the parent node's pointer which pointed previously to the
  456.      * deleted node.
  457.      */
  458.     (void) repair(t, node, node, cur, NULL, false);
  459.    
  460.     /*
  461.      * Repair cycle which repairs balances of nodes on the way from from the
  462.      * cut-off node up to the root.
  463.      */
  464.     for (;;) {
  465.         if (dir == LEFT) {
  466.             /*
  467.              * Deletion was made in the left subtree.
  468.              */
  469.             gpa->balance++;
  470.             if (gpa->balance == 1) {
  471.                 /*
  472.                  * Stop balancing, the tree is balanced.
  473.                  */
  474.                 break;
  475.             } else if (gpa->balance == 2) {
  476.                 /*
  477.                  * Bad balance, heights of left and right
  478.                  * subtrees differ more than by one.
  479.                  */
  480.                 par = gpa->rgt;
  481.  
  482.                 if (par->balance == -1) {
  483.                     /*
  484.                      * RL rotation.
  485.                      */
  486.                    
  487.                     cur = par->lft;
  488.                     par->lft = cur->rgt;
  489.                     cur->rgt = par;
  490.                     gpa->rgt = cur->lft;
  491.                     cur->lft = gpa;
  492.                    
  493.                     /*
  494.                      * Repair balances and paternity of
  495.                      * children, depending on the balance
  496.                      * factor of the grand child (cur).
  497.                      */
  498.                     REBALANCE_DELETE_RL();
  499.                    
  500.                     /*
  501.                      * Repair paternity.
  502.                      */
  503.                     cur->par = gpa->par;
  504.                     gpa->par = cur;
  505.                     par->par = cur;
  506.  
  507.                     if (!repair(t, cur, gpa, cur, &dir,
  508.                         false))
  509.                         break;
  510.                     gpa = cur->par;
  511.                 } else {
  512.                     /*
  513.                      * RR rotation.
  514.                      */
  515.                    
  516.                     gpa->rgt = par->lft;
  517.                     if (par->lft)
  518.                         par->lft->par = gpa;
  519.                     par->lft = gpa;
  520.                    
  521.                     /*
  522.                      * Repair paternity.
  523.                      */
  524.                     par->par = gpa->par;
  525.                     gpa->par = par;
  526.                    
  527.                     if (par->balance == 0) {
  528.                         /*
  529.                          * The right child of the
  530.                          * balanced node is balanced,
  531.                          * after RR rotation is done,
  532.                          * the whole tree will be
  533.                          * balanced.
  534.                          */
  535.                         par->balance = -1;
  536.                         gpa->balance = 1;
  537.  
  538.                         (void) repair(t, par, gpa, par,
  539.                             NULL, false);
  540.                         break;
  541.                     } else {
  542.                         par->balance = 0;
  543.                         gpa->balance = 0;
  544.                         if (!repair(t, par, gpa, par,
  545.                             &dir, false))
  546.                             break;
  547.                     }
  548.                     gpa = par->par;
  549.                 }
  550.             } else {
  551.                 /*
  552.                  * Repair the pointer which pointed to the
  553.                  * balanced node. If it was root then balancing
  554.                  * is finished else continue with the next
  555.                  * iteration (parent node).
  556.                  */
  557.                 if (!repair(t, gpa, gpa, NULL, &dir, true))
  558.                     break;
  559.                 gpa = gpa->par;
  560.             }
  561.         } else {
  562.             /*
  563.              * Deletion was made in the right subtree.
  564.              */
  565.             gpa->balance--;
  566.             if (gpa->balance == -1) {
  567.                 /*
  568.                  * Stop balancing, the tree is balanced.
  569.                  */
  570.                 break;
  571.             } else if (gpa->balance == -2) {
  572.                 /*
  573.                  * Bad balance, heights of left and right
  574.                  * subtrees differ more than by one.
  575.                  */
  576.                 par = gpa->lft;
  577.                
  578.                 if (par->balance == 1) {
  579.                     /*
  580.                      * LR rotation.
  581.                      */
  582.                    
  583.                     cur = par->rgt;
  584.                     par->rgt = cur->lft;
  585.                     cur->lft = par;
  586.                     gpa->lft = cur->rgt;
  587.                     cur->rgt = gpa;
  588.                    
  589.                     /*
  590.                      * Repair balances and paternity of
  591.                      * children, depending on the balance
  592.                      * factor of the grand child (cur).
  593.                      */
  594.                     REBALANCE_DELETE_LR();
  595.  
  596.                     /*
  597.                      * Repair paternity.
  598.                      */
  599.                     cur->par = gpa->par;
  600.                     gpa->par = cur;
  601.                     par->par = cur;
  602.  
  603.                     if (!repair(t, cur, gpa, cur, &dir,
  604.                         false))
  605.                         break;
  606.                     gpa = cur->par;
  607.                 } else {
  608.                     /*
  609.                      * LL rotation.
  610.                      */
  611.  
  612.                     gpa->lft = par->rgt;
  613.                     if (par->rgt)
  614.                         par->rgt->par = gpa;
  615.                     par->rgt = gpa;
  616.                     /*
  617.                      * Repair paternity.
  618.                      */
  619.                     par->par = gpa->par;
  620.                     gpa->par = par;
  621.                    
  622.                     if (par->balance == 0) {
  623.                         /*
  624.                          * The left child of the
  625.                          * balanced node is balanced,
  626.                          * after LL rotation is done,
  627.                          * the whole tree will be
  628.                          * balanced.
  629.                          */
  630.                         par->balance = 1;
  631.                         gpa->balance = -1;
  632.                        
  633.                         (void) repair(t, par, gpa, par,
  634.                             NULL, false);
  635.                         break;
  636.                     } else {
  637.                         par->balance = 0;
  638.                         gpa->balance = 0;
  639.                        
  640.                         if (!repair(t, par, gpa, par,
  641.                             &dir, false))
  642.                             break;
  643.                     }
  644.                     gpa = par->par;
  645.                 }
  646.             } else {
  647.                 /*
  648.                  * Repair the pointer which pointed to the
  649.                  * balanced node. If it was root then balancing
  650.                  * is finished. Otherwise continue with the next
  651.                  * iteration (parent node).
  652.                  */
  653.                 if (!repair(t, gpa, gpa, NULL, &dir, true))
  654.                     break;
  655.                 gpa = gpa->par;
  656.             }
  657.         }
  658.     }
  659. }
  660.  
  661.  
  662. /** Delete a node with the smallest key from the AVL tree.
  663.  *
  664.  * @param t AVL tree structure.
  665.  */
  666. bool avltree_delete_min(avltree_t *t)
  667. {
  668.     avltree_node_t *node;
  669.    
  670.     /*
  671.      * Start searching for the smallest key in the tree starting in the root
  672.      * node and continue in cycle to the leftmost node in the tree (which
  673.      * must have the smallest key).
  674.      */
  675.      
  676.     node = t->root;
  677.     if (!node)
  678.         return false;
  679.    
  680.     while (node->lft != NULL)
  681.         node = node->lft;
  682.    
  683.     avltree_delete(t, node);
  684.  
  685.     return true;
  686. }
  687.  
  688. /** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
  689.  * visited node.
  690.  *
  691.  * @param node      Node representing the root of an AVL subtree to be
  692.  *          walked.
  693.  * @param walker    Walker function that will be appliad on each visited
  694.  *          node.
  695.  * @param arg       Argument for the walker.
  696.  *
  697.  * @return      Zero if the walk should stop or non-zero otherwise.
  698.  */
  699. static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
  700.     void *arg)
  701. {
  702.     if (node->lft) {
  703.         if (!_avltree_walk(node->lft, walker, arg))
  704.             return false;
  705.     }
  706.     if (!walker(node, arg))
  707.         return false;
  708.     if (node->rgt) {
  709.         if (!_avltree_walk(node->rgt, walker, arg))
  710.             return false;
  711.     }
  712.     return true;
  713. }
  714.  
  715. /** Walk the AVL tree in-order and apply the walker function on each visited
  716.  * node.
  717.  *
  718.  * @param t     AVL tree to be walked.
  719.  * @param walker    Walker function that will be called on each visited
  720.  *          node.
  721.  * @param arg       Argument for the walker.
  722.  */
  723. void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
  724. {
  725.     _avltree_walk(t->root, walker, arg);
  726. }
  727.  
  728. /** @}
  729.  */
  730.  
  731.