Subversion Repositories HelenOS

Rev

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