Subversion Repositories HelenOS

Rev

Rev 2496 | Rev 2499 | 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.  
  56. #define LEFT    0
  57. #define RIGHT   1
  58.  
  59.  
  60. /** Search for the first occurence of the given key in an AVL tree.
  61.  *
  62.  * @param t AVL tree.
  63.  * @param key Key to be searched.
  64.  *
  65.  * @return Pointer to a node or NULL if there is no such key.
  66.  */
  67. avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
  68. {
  69.     avltree_node_t *p;
  70.    
  71.     /*
  72.      * Iteratively descend to the leaf that can contain the searched key.
  73.      */
  74.     p = t->root;
  75.     while (p != NULL) {
  76.         if (p->key > key)
  77.             p = p->lft;
  78.         else if (p->key < key)
  79.             p = p->rgt;
  80.         else
  81.             return p;
  82.     }
  83.     return NULL;
  84. }
  85.  
  86.  
  87. /** Find the node with the smallest key in an AVL tree.
  88.  *
  89.  * @param t AVL tree.
  90.  *
  91.  * @return Pointer to a node or NULL if there is no node in the tree.
  92.  */
  93. avltree_node_t *avltree_find_min(avltree_t *t)
  94. {
  95.     avltree_node_t *p = t->root;
  96.    
  97.     /*
  98.      * Check whether the tree is empty.
  99.      */
  100.     if (!p)
  101.         return NULL;
  102.    
  103.     /*
  104.      * Iteratively descend to the leftmost leaf in the tree.
  105.      */
  106.     while (p->lft != NULL)
  107.         p = p->lft;
  108.    
  109.     return p;
  110. }
  111.  
  112. /** Insert new node into AVL tree.
  113.  *
  114.  * @param t AVL tree.
  115.  * @param newnode New node to be inserted.
  116.  */
  117. void avltree_insert(avltree_t *t, avltree_node_t *newnode)
  118. {  
  119.     avltree_node_t *par;
  120.     avltree_node_t *gpa;
  121.     avltree_node_t *top;
  122.     avltree_node_t **dpc;
  123.     uint64_t key;
  124.  
  125.     ASSERT(t);
  126.     ASSERT(newnode);
  127.  
  128.     /*
  129.      * Creating absolute key.
  130.      */
  131.     key = newnode->key + t->base;
  132.    
  133.     /*
  134.      * Iteratively descend to the leaf that can contain the new node.
  135.      * Last node with non-zero balance in the way to leaf is stored as top -
  136.      * it is a place of possible inbalance.
  137.      */
  138.     dpc = &t->root;
  139.     gpa = NULL;
  140.     top = t->root;
  141.     while ((par = (*dpc)) != NULL) {
  142.         if (par->balance != 0) {
  143.             top = par;
  144.         }
  145.         gpa = par;
  146.         dpc = par->key > key ? &par->lft: &par->rgt;
  147.     }
  148.  
  149.     /*
  150.      * Initialize new node.
  151.      */
  152.     newnode->key = key;
  153.     newnode->lft = NULL;
  154.     newnode->rgt = NULL;
  155.     newnode->par = gpa;
  156.     newnode->balance = 0;
  157.  
  158.     /*
  159.      * Insert first node into the empty tree.
  160.      */
  161.     if (t->root == NULL) {
  162.         *dpc = newnode;
  163.         return;
  164.     }
  165.  
  166.     /*
  167.      * Insert new node into previously found leaf place.
  168.      */
  169.     *dpc = newnode;
  170.  
  171.     /*
  172.      * If the tree contains one node - end.
  173.      */
  174.     if (top == NULL)
  175.         return;
  176.  
  177.     /*
  178.      * Store pointer of top's father which points to the node with
  179.      * potentially broken balance (top).
  180.      */
  181.     if (top->par == NULL) {
  182.         dpc = &t->root;
  183.     } else {
  184.         if (top->par->lft == top)
  185.             dpc = &top->par->lft;
  186.         else
  187.             dpc = &top->par->rgt;
  188.     }
  189.  
  190.     /*
  191.      * Repair all balances on the way from top node to the newly inserted
  192.      * node.
  193.      */
  194.     par = top;
  195.     while (par != newnode) {
  196.         if (par->key > key) {
  197.             par->balance--;
  198.             par = par->lft;
  199.         } else {
  200.             par->balance++;
  201.             par = par->rgt;
  202.         }
  203.     }
  204.    
  205.     /*
  206.      * To balance the tree, we must check and balance top node.
  207.      */
  208.     if (top->balance == -2) {
  209.         par = top->lft;
  210.         if (par->balance == -1) {
  211.             /*
  212.              * LL rotation.
  213.              */
  214.             top->lft = par->rgt;
  215.             if (top->lft != NULL)
  216.                 top->lft->par = top;
  217.             par->par = top->par;
  218.             top->par = par;
  219.             par->rgt = top;
  220.             par->balance = 0;
  221.             top->balance = 0;
  222.             *dpc = par;
  223.         } else {
  224.             /*
  225.              * LR rotation.
  226.              */
  227.             ASSERT(par->balance == 1);
  228.            
  229.             gpa = par->rgt;
  230.             par->rgt = gpa->lft;
  231.             if (gpa->lft != NULL)
  232.                 gpa->lft->par = par;
  233.             gpa->lft = par;
  234.             par->par = gpa;
  235.             top->lft = gpa->rgt;
  236.             if (gpa->rgt != NULL)
  237.                 gpa->rgt->par = top;
  238.             gpa->rgt = top;
  239.             gpa->par = top->par;
  240.             top->par = gpa;
  241.            
  242.             if (gpa->balance == -1) {
  243.                 par->balance = 0;
  244.                 top->balance = 1;
  245.             } else if (gpa->balance == 0) {
  246.                 par->balance = 0;
  247.                 top->balance = 0;
  248.             } else {
  249.                 par->balance = -1;
  250.                 top->balance = 0;
  251.             }
  252.             gpa->balance = 0;
  253.             *dpc = gpa;
  254.         }
  255.     } else if (top->balance == 2) {
  256.         par = top->rgt;
  257.         if (par->balance == 1) {
  258.             /*
  259.              * RR rotation.
  260.              */
  261.             top->rgt = par->lft;
  262.             if (top->rgt != NULL)
  263.                 top->rgt->par = top;
  264.             par->par = top->par;
  265.             top->par = par;
  266.             par->lft = top;
  267.             par->balance = 0;
  268.             top->balance = 0;
  269.             *dpc = par;
  270.         } else {
  271.             /*
  272.              * RL rotation.
  273.              */
  274.             ASSERT(par->balance == -1);
  275.            
  276.             gpa = par->lft;
  277.             par->lft = gpa->rgt;
  278.             if (gpa->rgt != NULL)
  279.                 gpa->rgt->par = par;
  280.             gpa->rgt = par;
  281.             par->par = gpa;
  282.             top->rgt = gpa->lft;
  283.             if (gpa->lft != NULL)
  284.                 gpa->lft->par = top;
  285.             gpa->lft = top;
  286.             gpa->par = top->par;
  287.             top->par = gpa;
  288.  
  289.             if (gpa->balance == 1) {
  290.                 par->balance = 0;
  291.                 top->balance = -1;
  292.             } else if (gpa->balance == 0) {
  293.                 par->balance = 0;
  294.                 top->balance = 0;
  295.             } else {
  296.                 par->balance = 1;
  297.                 top->balance = 0;
  298.             }
  299.             gpa->balance = 0;
  300.             *dpc = gpa;
  301.         }
  302.     } else {
  303.         /*
  304.          * Balance is not broken, insertion is finised.
  305.          */
  306.         return;
  307.     }
  308.  
  309. }
  310.  
  311. /** Repair the tree after reparenting node u.
  312.  *
  313.  * If node u has no parent, mark it as the root of the whole tree. Otherwise
  314.  * node v represents stale address of one of the children of node u's parent.
  315.  * Replace v with w as node u parent's child (for most uses, u and w will be the
  316.  * same).
  317.  *
  318.  * @param t AVL tree.
  319.  * @param u Node whose new parent has a stale child pointer.
  320.  * @param v Stale child of node u's new parent.
  321.  * @param w New child of node u's new parent.
  322.  * @param dir   If not NULL, address of the variable where to store information
  323.  *      about whether w replaced v in the left or the right subtree of
  324.  *      u's new parent.
  325.  * @param ro    Read only operation; do not modify any tree pointers. This is
  326.  *      useful for tracking direction via the dir pointer.
  327.  *
  328.  * @return  Zero if w became the new root of the tree, otherwise return
  329.  *      non-zero.
  330.  */
  331. static int
  332. repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
  333.     int *dir, int ro)
  334. {
  335.     if (u->par == NULL) {
  336.         if (!ro)
  337.             t->root = w;   
  338.         return 0;
  339.     } else {   
  340.         if (u->par->lft == v) {
  341.             if (!ro)
  342.                 u->par->lft = w;
  343.             if (dir)
  344.                 *dir = LEFT;
  345.         } else {
  346.             ASSERT(u->par->rgt == v);
  347.             if (!ro)
  348.                 u->par->rgt = w;
  349.             if (dir)
  350.                 *dir = RIGHT;
  351.         }
  352.     }
  353.     return 1;
  354. }
  355.  
  356. #define REBALANCE(DIR1, DIR2, SIGN)     \
  357.     if (cur->balance == -1 * SIGN) {    \
  358.         par->balance = 0;       \
  359.         gpa->balance = 1 * SIGN;    \
  360.         if (gpa->DIR1)          \
  361.             gpa->DIR1->par = gpa;   \
  362.         par->DIR2->par = par;       \
  363.     } else if (cur->balance == 0) {     \
  364.         par->balance = 0;       \
  365.         gpa->balance = 0;       \
  366.         if (gpa->DIR1)          \
  367.             gpa->DIR1->par = gpa;   \
  368.         if (par->DIR2)          \
  369.             par->DIR2->par = par;   \
  370.     } else {                \
  371.         par->balance = -1 * SIGN;   \
  372.         gpa->balance = 0;       \
  373.         if (par->DIR2)          \
  374.             par->DIR2->par = par;   \
  375.         gpa->DIR1->par = gpa;       \
  376.     }                   \
  377.     cur->balance = 0;
  378.  
  379. #define REBALANCE_LR()      REBALANCE(lft, rgt, 1)
  380. #define REBALANCE_RL()      REBALANCE(rgt, lft, -1)
  381.  
  382. /** Delete a node from the AVL tree.
  383.  *
  384.  * Because multiple identical keys are allowed, the parent pointers are
  385.  * essential during deletion.
  386.  *
  387.  * @param t AVL tree structure.
  388.  * @param node Address of the node which will be deleted.
  389.  */
  390. void avltree_delete(avltree_t *t, avltree_node_t *node)
  391. {
  392.     avltree_node_t *cur;
  393.     avltree_node_t *par;
  394.     avltree_node_t *gpa;
  395.     int dir;
  396.  
  397.     ASSERT(t);
  398.     ASSERT(node);
  399.    
  400.     if (node->lft == NULL) {
  401.         if (node->rgt) {
  402.             /*
  403.              * Replace the node with its only right son.
  404.              *
  405.              * Balance of the right son will be repaired in the
  406.              * balancing cycle.
  407.              */
  408.             cur = node->rgt;
  409.             cur->par = node->par;
  410.             gpa = cur;
  411.             dir = RIGHT;
  412.             cur->balance = node->balance;
  413.         } else {
  414.             if (node->par == NULL) {
  415.                 /*
  416.                  * The tree has only one node - it will become
  417.                  * an empty tree and the balancing can end.
  418.                  */
  419.                 t->root = NULL;
  420.                 return;
  421.             }
  422.             /*
  423.              * The node has no child, it will be deleted with no
  424.              * substitution.
  425.              */
  426.             gpa = node->par;
  427.             cur = NULL;
  428.             dir = (gpa->lft == node) ? LEFT: RIGHT;
  429.         }
  430.     } else {
  431.         /*
  432.          * The node has the left son. Find a node with the smallest key
  433.          * in the left subtree and replace the deleted node with that
  434.          * node.
  435.          */
  436.         for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
  437.             ;
  438.  
  439.         if (cur != node->lft) {
  440.             /*
  441.              * The rightmost node of the deleted node's left subtree
  442.              * was found. Replace the deleted node with this node.
  443.              * Cutting off of the found node has two cases that
  444.              * depend on its left son.
  445.              */
  446.             if (cur->lft) {
  447.                 /*
  448.                  * The found node has a left son.
  449.                  */
  450.                 gpa = cur->lft;
  451.                 gpa->par = cur->par;
  452.                 dir = LEFT;
  453.                 gpa->balance = cur->balance;
  454.             } else {
  455.                 dir = RIGHT;
  456.                 gpa = cur->par;
  457.             }
  458.             cur->par->rgt = cur->lft;
  459.             cur->lft = node->lft;
  460.             cur->lft->par = cur;
  461.         } else {
  462.             /*
  463.              * The left son of the node hasn't got a right son. The
  464.              * left son will take the deleted node's place.
  465.              */
  466.             dir = LEFT;
  467.             gpa = cur;
  468.         }
  469.         if (node->rgt)
  470.             node->rgt->par = cur;
  471.         cur->rgt = node->rgt;
  472.         cur->balance = node->balance;
  473.         cur->par = node->par;
  474.     }
  475.    
  476.     /*
  477.      * Repair the parent node's pointer which pointed previously to the
  478.      * deleted node.
  479.      */
  480.     (void) repair(t, node, node, cur, NULL, false);
  481.    
  482.     /*
  483.      * Repair cycle which repairs balances of nodes on the way from from the
  484.      * cut-off node up to the root.
  485.      */
  486.     for (;;) {
  487.         if (dir == LEFT) {
  488.             /*
  489.              * Deletion was made in the left subtree.
  490.              */
  491.             gpa->balance++;
  492.             if (gpa->balance == 1) {
  493.                 /*
  494.                  * Stop balancing, the tree is balanced.
  495.                  */
  496.                 break;
  497.             } else if (gpa->balance == 2) {
  498.                 /*
  499.                  * Bad balance, heights of left and right
  500.                  * subtrees differ more than by one.
  501.                  */
  502.                 par = gpa->rgt;
  503.  
  504.                 if (par->balance == -1) {
  505.                     /*
  506.                      * RL rotation.
  507.                      */
  508.                    
  509.                     cur = par->lft;
  510.                     par->lft = cur->rgt;
  511.                     cur->rgt = par;
  512.                     gpa->rgt = cur->lft;
  513.                     cur->lft = gpa;
  514.                    
  515.                     /*
  516.                      * Repair balances and paternity of
  517.                      * children, depending on the balance
  518.                      * factor of the grand child (cur).
  519.                      */
  520.                     REBALANCE_RL();
  521.                    
  522.                     /*
  523.                      * Repair paternity.
  524.                      */
  525.                     cur->par = gpa->par;
  526.                     gpa->par = cur;
  527.                     par->par = cur;
  528.  
  529.                     if (!repair(t, cur, gpa, cur, &dir,
  530.                         false))
  531.                         break;
  532.                     gpa = cur->par;
  533.                 } else {
  534.                     /*
  535.                      * RR rotation.
  536.                      */
  537.                    
  538.                     gpa->rgt = par->lft;
  539.                     if (par->lft)
  540.                         par->lft->par = gpa;
  541.                     par->lft = gpa;
  542.                    
  543.                     /*
  544.                      * Repair paternity.
  545.                      */
  546.                     par->par = gpa->par;
  547.                     gpa->par = par;
  548.                    
  549.                     if (par->balance == 0) {
  550.                         /*
  551.                          * The right child of the
  552.                          * balanced node is balanced,
  553.                          * after RR rotation is done,
  554.                          * the whole tree will be
  555.                          * balanced.
  556.                          */
  557.                         par->balance = -1;
  558.                         gpa->balance = 1;
  559.  
  560.                         (void) repair(t, par, gpa, par,
  561.                             NULL, false);
  562.                         break;
  563.                     } else {
  564.                         par->balance = 0;
  565.                         gpa->balance = 0;
  566.                         if (!repair(t, par, gpa, par,
  567.                             &dir, false))
  568.                             break;
  569.                     }
  570.                     gpa = par->par;
  571.                 }
  572.             } else {
  573.                 /*
  574.                  * Repair the pointer which pointed to the
  575.                  * balanced node. If it was root then balancing
  576.                  * is finished else continue with the next
  577.                  * iteration (parent node).
  578.                  */
  579.                 if (!repair(t, gpa, gpa, NULL, &dir, true))
  580.                     break;
  581.                 gpa = gpa->par;
  582.             }
  583.         } else {
  584.             /*
  585.              * Deletion was made in the right subtree.
  586.              */
  587.             gpa->balance--;
  588.             if (gpa->balance == -1) {
  589.                 /*
  590.                  * Stop balancing, the tree is balanced.
  591.                  */
  592.                 break;
  593.             } else if (gpa->balance == -2) {
  594.                 /*
  595.                  * Bad balance, heights of left and right
  596.                  * subtrees differ more than by one.
  597.                  */
  598.                 par = gpa->lft;
  599.                
  600.                 if (par->balance == 1) {
  601.                     /*
  602.                      * LR rotation.
  603.                      */
  604.                    
  605.                     cur = par->rgt;
  606.                     par->rgt = cur->lft;
  607.                     cur->lft = par;
  608.                     gpa->lft = cur->rgt;
  609.                     cur->rgt = gpa;
  610.                    
  611.                     /*
  612.                      * Repair balances and paternity of
  613.                      * children, depending on the balance
  614.                      * factor of the grand child (cur).
  615.                      */
  616.                     REBALANCE_LR();
  617.  
  618.                     /*
  619.                      * Repair paternity.
  620.                      */
  621.                     cur->par = gpa->par;
  622.                     gpa->par = cur;
  623.                     par->par = cur;
  624.  
  625.                     if (!repair(t, cur, gpa, cur, &dir,
  626.                         false))
  627.                         break;
  628.                     gpa = cur->par;
  629.                 } else {
  630.                     /*
  631.                      * LL rotation.
  632.                      */
  633.  
  634.                     gpa->lft = par->rgt;
  635.                     if (par->rgt)
  636.                         par->rgt->par = gpa;
  637.                     par->rgt = gpa;
  638.                     /*
  639.                      * Repair paternity.
  640.                      */
  641.                     par->par = gpa->par;
  642.                     gpa->par = par;
  643.                    
  644.                     if (par->balance == 0) {
  645.                         /*
  646.                          * The left child of the
  647.                          * balanced node is balanced,
  648.                          * after LL rotation is done,
  649.                          * the whole tree will be
  650.                          * balanced.
  651.                          */
  652.                         par->balance = 1;
  653.                         gpa->balance = -1;
  654.                        
  655.                         (void) repair(t, par, gpa, par,
  656.                             NULL, false);
  657.                         break;
  658.                     } else {
  659.                         par->balance = 0;
  660.                         gpa->balance = 0;
  661.                        
  662.                         if (!repair(t, par, gpa, par,
  663.                             &dir, false))
  664.                             break;
  665.                     }
  666.                     gpa = par->par;
  667.                 }
  668.             } else {
  669.                 /*
  670.                  * Repair the pointer which pointed to the
  671.                  * balanced node. If it was root then balancing
  672.                  * is finished. Otherwise continue with the next
  673.                  * iteration (parent node).
  674.                  */
  675.                 if (!repair(t, gpa, gpa, NULL, &dir, true))
  676.                     break;
  677.                 gpa = gpa->par;
  678.             }
  679.         }
  680.     }
  681. }
  682.  
  683.  
  684. /** Delete a node with the smallest key from the AVL tree.
  685.  *
  686.  * @param t AVL tree structure.
  687.  */
  688. bool avltree_delete_min(avltree_t *t)
  689. {
  690.     avltree_node_t *node;
  691.    
  692.     /*
  693.      * Start searching for the smallest key in the tree starting in the root
  694.      * node and continue in cycle to the leftmost node in the tree (which
  695.      * must have the smallest key).
  696.      */
  697.      
  698.     node = t->root;
  699.     if (!node)
  700.         return false;
  701.    
  702.     while (node->lft != NULL)
  703.         node = node->lft;
  704.    
  705.     avltree_delete(t, node);
  706.  
  707.     return true;
  708. }
  709.  
  710. /** @}
  711.  */
  712.  
  713.