Subversion Repositories HelenOS

Rev

Rev 2416 | Rev 2450 | 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 binary search tree with non-unique keys
  41.  * @li Difference of heights of left and right subtree of every node is max 1.
  42.  *
  43.  * Every node has pointer to its parent which allows insertion of multiple identical keys
  44.  * into tree.
  45.  *
  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.
  48.  */
  49.  
  50. #include <adt/avl.h>
  51. #include <debug.h>
  52. #include <panic.h>
  53.  
  54.  
  55. #define AVLTREE_LEFT 0
  56. #define AVLTREE_RIGHT 1
  57.  
  58.  
  59. /** Search first occurence of given key in AVL tree.
  60.  *
  61.  * @param t AVL tree.
  62.  * @param key Key to be searched.
  63.  *
  64.  * @return Pointer to node or NULL if there is no such key.
  65.  */
  66. avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
  67. {
  68.     avltree_node_t *p;
  69.    
  70.     /*
  71.      * Iteratively descend to the leaf that can contain the searched key.
  72.      */
  73.     p = t->root;
  74.     while (p != NULL) {
  75.         if (p->key > key)
  76.             p = p->lft;
  77.         else if (p->key < key)
  78.             p = p->rgt;
  79.         else {
  80.             return p;
  81.         }
  82.     }
  83.     return NULL;
  84. }
  85.  
  86.  
  87. /** Find node with smallest key in AVL tree.
  88.  *
  89.  * @param t AVL tree.
  90.  *
  91.  * @return Pointer to 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 tree is empty.
  99.      */
  100.     if (!p) return NULL;
  101.    
  102.     /*
  103.      * Iteratively descend to the leftmost leaf in the tree.
  104.      */
  105.     while (p->lft != NULL)
  106.         p = p->lft;
  107.    
  108.     return p;
  109. }
  110.  
  111. /** Insert new node into AVL tree.
  112.  *
  113.  * @param t AVL tree.
  114.  * @param newnode New node to be inserted.
  115.  */
  116. void avltree_insert(avltree_t *t, avltree_node_t *newnode)
  117. {  
  118.     avltree_node_t *par;
  119.     avltree_node_t *gpa;
  120.     avltree_node_t *top;
  121.     avltree_node_t **dpc;
  122.     uint64_t key;
  123.  
  124.     ASSERT(t);
  125.     ASSERT(newnode);
  126.  
  127.     /*
  128.      * Creating absolute key.
  129.      */
  130.     key = newnode->key + t->base;
  131.    
  132.  
  133.     /*
  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 -
  136.      * it si place of possible balance failure.
  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 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 tree contains one node - end.
  173.      */
  174.     if (top == NULL) return;
  175.  
  176.     /*
  177.      * Store pointer of top's father which points to the node with potentialy broken
  178.      * balance (top).
  179.      */
  180.     if (top->par == NULL)
  181.         dpc = &t->root;
  182.     else
  183.         if (top->par->lft == top)
  184.             dpc = &(top->par->lft);
  185.         else
  186.             dpc = &(top->par->rgt);
  187.  
  188.     /*
  189.      * Repair all balances on the way from top node to newly inserted node.
  190.      */
  191.     par = top;
  192.     while (par != newnode) {
  193.         if (par->key > key) {
  194.             par->balance--;
  195.             par = par->lft;
  196.         } else {
  197.             par->balance++;
  198.             par = par->rgt;
  199.         }
  200.     }
  201.    
  202.     /*
  203.      * To balance tree we must check and balance top node.
  204.      */
  205.     if (top->balance == -2) {
  206.         par = top->lft;
  207.         if (par->balance == -1) {
  208.             /*
  209.              * LL rotation.
  210.              */
  211.             top->lft = par->rgt;
  212.             if (top->lft != NULL) top->lft->par = top;
  213.             par->par = top->par;
  214.             top->par = par;
  215.             par->rgt = top;
  216.             par->balance = top->balance = 0;
  217.             *dpc = par;
  218.         } else {
  219.             /*
  220.              * LR rotation.
  221.              */
  222.             ASSERT(par->balance == 1);
  223.            
  224.             gpa = par->rgt;
  225.             par->rgt = gpa->lft;
  226.             if (gpa->lft != NULL) gpa->lft->par = par;
  227.             gpa->lft = par;
  228.             par->par = gpa;
  229.             top->lft = gpa->rgt;
  230.             if (gpa->rgt != NULL) gpa->rgt->par = top;
  231.             gpa->rgt = top;
  232.             gpa->par = top->par;
  233.             top->par = gpa;
  234.            
  235.             if (gpa->balance == -1) {
  236.                 par->balance = 0;
  237.                 top->balance = 1;
  238.             } else if (gpa->balance == 0) {
  239.                 par->balance = top->balance = 0;
  240.             } else {
  241.                 par->balance = -1;
  242.                 top->balance = 0;
  243.             }
  244.             gpa->balance = 0;
  245.             *dpc = gpa;
  246.         }
  247.     } else if (top->balance == 2) {
  248.         par = top->rgt;
  249.         if (par->balance == 1) {
  250.             /*
  251.              * RR rotation.
  252.              */
  253.             top->rgt = par->lft;
  254.             if (top->rgt != NULL) top->rgt->par = top;
  255.             par->par = top->par;
  256.             top->par = par;
  257.             par->lft = top;
  258.             par->balance = top->balance = 0;
  259.             *dpc = par;
  260.         } else {
  261.             /*
  262.              * RL rotation.
  263.              */
  264.             ASSERT(par->balance == -1);
  265.            
  266.             gpa = par->lft;
  267.             par->lft = gpa->rgt;
  268.             if (gpa->rgt != NULL) gpa->rgt->par = par;
  269.             gpa->rgt = par;
  270.             par->par = gpa;
  271.             top->rgt = gpa->lft;
  272.             if (gpa->lft != NULL) gpa->lft->par = top;
  273.             gpa->lft = top;
  274.             gpa->par = top->par;
  275.             top->par = gpa;
  276.  
  277.             if (gpa->balance == 1) {
  278.                 par->balance = 0;
  279.                 top->balance = -1;
  280.             } else if (gpa->balance == 0) {
  281.                 par->balance = top->balance = 0;
  282.             } else {
  283.                 par->balance = 1;
  284.                 top->balance = 0;
  285.             }
  286.             gpa->balance = 0;
  287.             *dpc = gpa;
  288.         }
  289.     } else {
  290.         /*
  291.          * Balance is not broken, insertion is finised.
  292.          */
  293.         return;
  294.     }
  295.  
  296. }
  297.  
  298. /** Delete node from AVL tree.
  299.  *
  300.  * Because of allowed multiple identical keys parent pointers are essential
  301.  * during deletition.
  302.  *
  303.  * @param t AVL tree structure.
  304.  * @param node Address of node which will be deleted.
  305.  */
  306. void avltree_delete(avltree_t *t, avltree_node_t *node)
  307. {
  308.     avltree_node_t *cur;
  309.     avltree_node_t *par;
  310.     avltree_node_t *gpa;
  311.     uint8_t dir;
  312.  
  313.     ASSERT(t);
  314.     ASSERT(node);
  315.    
  316.    
  317.     if (node->lft == NULL) {
  318.         if (node->rgt) {
  319.             /*
  320.              * Replace node with its only right son.
  321.              *
  322.              * Balance of right son will be repaired in balancing cycle.
  323.              */
  324.             cur = node->rgt;
  325.             cur->par = node->par;
  326.             gpa = cur;
  327.             dir = AVLTREE_RIGHT;
  328.             cur->balance = node->balance;
  329.         } else {
  330.             if (node->par == NULL) {
  331.                 /*
  332.                  * Tree has only one node - it will be empty tree and balancing can end.
  333.                  */
  334.                 t->root = NULL;
  335.                 return;
  336.             }
  337.             /*
  338.              * Node has no child, will be deleted with no substitution.
  339.              */
  340.             gpa = node->par;
  341.             cur = NULL;
  342.             dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
  343.         }
  344.     } else {
  345.         /*
  346.          * Node has left and right son. Find a node with smallest key in left subtree
  347.          * and replace deleted node with that node.
  348.          */
  349.         for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
  350.             ;
  351.        
  352.         //cur obsahuje uzel, ktery vlozim misto uzlu node
  353.        
  354.         if (cur != node->lft) {
  355.             /*
  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
  358.              * dependence on its left son.
  359.              */
  360.             if (cur->lft) {
  361.                 /*
  362.                  * Founded node has left son.
  363.                  */
  364.                 gpa = cur->lft;
  365.                 gpa->par = cur->par;
  366.                 dir = AVLTREE_LEFT;
  367.                 gpa->balance = cur->balance;
  368.             } else {
  369.                 dir = AVLTREE_RIGHT;
  370.                 gpa = cur->par;
  371.             }
  372.             cur->par->rgt = cur->lft;
  373.             cur->lft = node->lft;
  374.             cur->lft->par = cur;
  375.         } else {
  376.             /*
  377.              * Left son of node hasn't got right son. Left son will take deleted node's place.
  378.              */
  379.             dir = AVLTREE_LEFT;
  380.             gpa = cur;
  381.         }
  382.         if (node->rgt) node->rgt->par = cur;
  383.         cur->rgt = node->rgt;
  384.         cur->balance = node->balance;
  385.         cur->par = node->par;
  386.     }
  387.    
  388.     /*
  389.      * Repair parent nodes pointer which pointed previously to deleted node.
  390.      */
  391.     if (node->par == NULL) {
  392.         t->root = cur;
  393.     } else {
  394.         if (node->par->lft == node) {
  395.             node->par->lft = cur;
  396.         } else {
  397.             node->par->rgt = cur;
  398.         }
  399.     }
  400.    
  401.     /*
  402.      * Repair cycle which repairs balances of nodes in way from cutted noded down to root.
  403.      */
  404.     for(;;) {
  405.         if (dir == AVLTREE_LEFT) {
  406.             /*
  407.              * Deletition was made in left subtree.
  408.              */
  409.             gpa->balance++;
  410.             if (gpa->balance == +1) {
  411.                 /*
  412.                  * Stop balancing, tree is balanced.
  413.                  */
  414.                 break;
  415.             } else if (gpa->balance == +2) {
  416.                 /*
  417.                  * Bad balance, heights of left and right subtrees differs more then is allowed.
  418.                  */
  419.                 par = gpa->rgt;
  420.  
  421.                 if (par->balance == -1) {
  422.                     /*
  423.                      * RL rotation.
  424.                      */
  425.                    
  426.                     cur = par->lft;
  427.                     par->lft = cur->rgt;
  428.                     cur->rgt = par;
  429.                     gpa->rgt = cur->lft;
  430.                     cur->lft = gpa;
  431.                    
  432.                     /*
  433.                      * Repair balances and paternity of childs in dependence on
  434.                      * balance factor of grand child (cur).
  435.                      */
  436.                     if (cur->balance == +1) {
  437.                         par->balance = 0;
  438.                         gpa->balance = -1;
  439.                         if (gpa->rgt) gpa->rgt->par = gpa;
  440.                         par->lft->par = par;
  441.                     } else if (cur->balance == 0) {
  442.                         par->balance = gpa->balance = 0;
  443.                         if (gpa->rgt) gpa->rgt->par = gpa;
  444.                         if (par->lft) par->lft->par = par;
  445.                     } else {
  446.                         par->balance = +1;
  447.                         gpa->balance = 0;
  448.                         if (par->lft) par->lft->par = par;
  449.                         gpa->rgt->par = gpa;
  450.                     }
  451.                     cur->balance = 0;
  452.                    
  453.                     /*
  454.                      * Repair paternity.
  455.                      */
  456.                     cur->par = gpa->par;
  457.                     gpa->par = cur;
  458.                     par->par = cur;
  459.  
  460.                     /*
  461.                      * Repair pointer which pointed to balanced node. If it was root then balancing
  462.                      * is finished else continue in next iteration (parent node).
  463.                      */
  464.                     if (cur->par == NULL) {
  465.                         t->root = cur; 
  466.                         break;
  467.                     } else
  468.                         if (cur->par->lft == gpa) {
  469.                             cur->par->lft = cur;
  470.                             dir = AVLTREE_LEFT;
  471.                         } else {
  472.                             cur->par->rgt = cur;
  473.                             dir = AVLTREE_RIGHT;
  474.                         }
  475.                     gpa = cur->par;
  476.                 } else {
  477.                     /*
  478.                      * RR rotation.
  479.                      */
  480.                    
  481.                     gpa->rgt = par->lft;
  482.                     if (par->lft) par->lft->par = gpa;
  483.                     par->lft = gpa;
  484.                    
  485.                     /*
  486.                      * Repair paternity.
  487.                      */
  488.                     par->par = gpa->par;
  489.                     gpa->par = par;
  490.                    
  491.                     if (par->balance == 0) {
  492.                         /*
  493.                          * Right child of balanced node is balanced, after RR rotation is done, whole
  494.                          * tree will be balanced.
  495.                          */
  496.                         par->balance = -1;
  497.                         gpa->balance = +1;
  498.  
  499.                         /*
  500.                          * Repair pointer which pointed to balanced node and finish balancing.
  501.                          */
  502.                         if (par->par == NULL) {
  503.                             t->root = par; 
  504.                         } else
  505.                             if (par->par->lft == gpa) {
  506.                                 par->par->lft = par;
  507.                             } else {
  508.                                 par->par->rgt = par;
  509.                             }
  510.                         break;
  511.                     } else {
  512.                         par->balance = gpa->balance = 0;
  513.                         /*
  514.                          * Repair pointer which pointed to balanced node. If it was root then balancing
  515.                          * is finished else continue in next iteration (parent node).
  516.                          */
  517.                         if (par->par == NULL) {
  518.                             t->root = par; 
  519.                             break;
  520.                         } else {
  521.                            
  522.                             if (par->par->lft == gpa) {
  523.                                 par->par->lft = par;
  524.                                 dir = AVLTREE_LEFT;
  525.                             } else {
  526.                                 par->par->rgt = par;
  527.                                 dir = AVLTREE_RIGHT;
  528.                             }
  529.                         }
  530.                     }
  531.                     gpa = par->par;
  532.                 }
  533.             } else {
  534.                 /*
  535.                  * Repair pointer which pointed to balanced node. If it was root then balancing
  536.                  * is finished else continue in next iteration (parent node).
  537.                  */
  538.                 if (!gpa->par) break;
  539.  
  540.                 if (gpa->par->lft == gpa) {
  541.                     dir = AVLTREE_LEFT;
  542.                 } else {
  543.                     dir = AVLTREE_RIGHT;
  544.                 }
  545.                 gpa = gpa->par;
  546.             }
  547.         } else {
  548.             /*
  549.              * Deletition was made in right subtree.
  550.              */
  551.             gpa->balance--;
  552.             if (gpa->balance == -1) {
  553.                 /*
  554.                  * Stop balancing, tree is balanced.
  555.                  */
  556.                 break;
  557.             } else if (gpa->balance == -2) {
  558.                 /*
  559.                  * Bad balance, heights of left and right subtrees differs more then is allowed.
  560.                  */
  561.                 par = gpa->lft;
  562.                
  563.                 if (par->balance == +1) {
  564.                     /*
  565.                      * LR rotation.
  566.                      */
  567.                    
  568.                     cur = par->rgt;
  569.                     par->rgt = cur->lft;
  570.                     cur->lft = par;
  571.                     gpa->lft = cur->rgt;
  572.                     cur->rgt = gpa;
  573.                    
  574.                     /*
  575.                      * Repair balances and paternity of childs in dependence on
  576.                      * balance factor of grand child (cur).
  577.                      */
  578.                     if (cur->balance == -1) {
  579.                         par->balance = 0;
  580.                         gpa->balance = +1;
  581.                         if (gpa->lft) gpa->lft->par = gpa;
  582.                         par->rgt->par = par;
  583.                     } else if (cur->balance == 0) {
  584.                         par->balance = gpa->balance = 0;
  585.                         if (gpa->lft) gpa->lft->par = gpa;
  586.                         if (par->rgt) par->rgt->par = par;
  587.                     } else {
  588.                         par->balance = -1;
  589.                         gpa->balance = 0;
  590.                         if (par->rgt) par->rgt->par = par;
  591.                         gpa->lft->par = gpa;
  592.                     }
  593.                     cur->balance = 0;
  594.  
  595.                     /*
  596.                      * Repair paternity.
  597.                      */
  598.                     cur->par = gpa->par;
  599.                     gpa->par = cur;
  600.                     par->par = cur;
  601.  
  602.                     /*
  603.                      * Repair pointer which pointed to balanced node. If it was root then balancing
  604.                      * is finished else continue in next iteration (parent node).
  605.                      */
  606.                     if (cur->par == NULL) {
  607.                         t->root = cur; 
  608.                         break;
  609.                     } else
  610.                         if (cur->par->lft == gpa) {
  611.                             cur->par->lft = cur;
  612.                             dir = AVLTREE_LEFT;
  613.                         } else {
  614.                             cur->par->rgt = cur;
  615.                             dir = AVLTREE_RIGHT;
  616.                         }
  617.                     gpa = cur->par;
  618.                 } else {
  619.                     /*
  620.                      * LL rotation.
  621.                      */
  622.                    
  623.                     gpa->lft = par->rgt;
  624.                     if (par->rgt) par->rgt->par = gpa;
  625.                     par->rgt = gpa;
  626.                     /*
  627.                      * Repair paternity.
  628.                      */
  629.                     par->par = gpa->par;
  630.                     gpa->par = par;
  631.                    
  632.                     if (par->balance == 0) {
  633.                         /*
  634.                          * Left child of balanced node is balanced, after RR rotation is done, whole
  635.                          * tree will be balanced.
  636.                          */
  637.                         par->balance = +1;
  638.                         gpa->balance = -1;
  639.                        
  640.                         /*
  641.                          * Repair pointer which pointed to balanced node and finish balancing.
  642.                          */
  643.                         if (par->par == NULL) {
  644.                             t->root = par;
  645.                         } else
  646.                             if (par->par->lft == gpa) {
  647.                                 par->par->lft = par;
  648.                             } else {
  649.                                 par->par->rgt = par;
  650.                             }
  651.                         break;
  652.                     } else {
  653.                         par->balance = gpa->balance = 0;
  654.                        
  655.                         /*
  656.                          * Repair pointer which pointed to balanced node. If it was root then balancing
  657.                          * is finished else continue in next iteration (parent node).
  658.                          */
  659.                         if (par->par == NULL) {
  660.                             t->root = par;
  661.                             break;
  662.                         } else {
  663.                             if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
  664.                                 par->par->lft = par;
  665.                                 dir = AVLTREE_LEFT;
  666.                             } else {
  667.                                 par->par->rgt = par;
  668.                                 dir = AVLTREE_RIGHT;
  669.                             }
  670.                         }
  671.                     }
  672.                     gpa = par->par;
  673.                 }
  674.             } else {
  675.                 /*
  676.                  * Repair pointer which pointed to balanced node. If it was root then balancing
  677.                  * is finished else continue in next iteration (parent node).
  678.                  */
  679.                 if (!gpa->par) break;
  680.  
  681.                 if (gpa->par->lft == gpa) {
  682.                     dir = AVLTREE_LEFT;
  683.                 } else {
  684.                     dir = AVLTREE_RIGHT;
  685.                 }
  686.                 gpa = gpa->par;
  687.             }
  688.         }
  689.     }
  690. }
  691.  
  692.  
  693. /** Delete node from AVL tree with the smallest key and set base of tree to that key.
  694.  *
  695.  * @param t AVL tree structure.
  696.  */
  697. bool avltree_delete_min(avltree_t *t)
  698. {
  699.     avltree_node_t *node;
  700.     uint64_t key;
  701.    
  702.     /*
  703.      * Start search of smallest key in tree in the root node and
  704.      * continue in cycle to the most left node in the tree which
  705.      * must have smallest key.
  706.      */
  707.     node = t->root;
  708.     if (!node) return false;
  709.    
  710.     while (node->lft != NULL)
  711.         node = node->lft;
  712.    
  713.     /*
  714.      * Store key and use avltree_delete function to delete node from tree.
  715.      */
  716.     key = node->key;
  717.     avltree_delete(t,node);
  718.  
  719.     /*
  720.      * Change base to the key of deleted node.
  721.      */
  722.     t->base = key;
  723.  
  724.     return true;
  725. }
  726.