Subversion Repositories HelenOS

Rev

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

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