Subversion Repositories HelenOS

Rev

Rev 2416 | Rev 2431 | 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   Extended AVL tree implementation.
  36.  *
  37.  * This file implements Extended AVL tree type and operations.
  38.  *
  39.  * Extended AVL tree (ExtAvl tree) has the following properties:
  40.  * @li it is binary search tree with unique keys
  41.  * @li right subtree of every node is Avl tree
  42.  * @li height of left subtree of every node is not greater then height of right subtree + 1
  43.  * @li nodes with the same keys are linked to the tree nodes of the same key, they are not tree nodes
  44.  * @li every node is part of doubly linked list with head
  45.  * @li nodes are connected in the list ascendentaly according to their keys
  46.  *
  47.  * Be careful of using this tree because of base atribute, which is added to every inserted
  48.  * node key.
  49.  */
  50.  
  51. #include <adt/extavl.h>
  52. #include <debug.h>
  53. #include <panic.h>
  54.  
  55. #define AVLTREE_LEFT 0
  56. #define AVLTREE_RIGHT 1
  57.  
  58. /* Returns height of tree -1 */
  59. #define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
  60.  
  61. /** Search first occurence (oldest node with this key) of given key in Extended AVL tree.
  62.  *
  63.  * @param t Extended AVL tree.
  64.  * @param key Key to be searched.
  65.  *
  66.  * @return Pointer to node or NULL if there is no such key.
  67.  */
  68. extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
  69. {
  70.     extavltree_node_t *cur;
  71.  
  72.     cur = t->root;
  73.     while (cur != NULL) {
  74.         if (cur->key < key) {
  75.             cur = cur->rgt;
  76.         } else if (cur->key > key) {
  77.             cur = cur->lft;
  78.         } else {
  79.             return cur;
  80.         }
  81.     }
  82.     return NULL;
  83. }
  84.                                    
  85. /** Insert new node into ExtAVL tree.
  86.  *
  87.  * New node's key must be set.
  88.  *
  89.  * @param t ExtAVL tree structure.
  90.  * @param newnode New node to be inserted.
  91.  */
  92. void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode)
  93. {  
  94.     extavltree_node_t *cur;
  95.     extavltree_node_t *son;
  96.     extavltree_node_t *gpa;
  97.     extavltree_node_t *par;
  98.     uint64_t key;
  99.  
  100.     ASSERT(t);
  101.     ASSERT(newnode);
  102.    
  103.     /*
  104.      * Creating absolute key.
  105.      */
  106.     newnode->key = key = newnode->key + t->base;
  107.    
  108.  
  109.     /*
  110.      * Insert first node into empty tree.
  111.      */
  112.     if (t->root == NULL) {
  113.         newnode->lft = NULL;
  114.         newnode->rgt = NULL;
  115.         newnode->lft_height = 0;
  116.         newnode->rgt_height = 0;
  117.         newnode->par = NULL;
  118.         newnode->next = &t->head;
  119.         newnode->prev = &t->head;
  120.  
  121.         t->head.prev = newnode;
  122.         t->head.next = newnode;
  123.         t->root = newnode;
  124.         return;
  125.     }
  126.  
  127.     /*
  128.      * Tree is not empty - search for the right place for new node.
  129.      */
  130.     cur = t->root;
  131.     while(true) {
  132.         if (cur->key < key) {
  133.             if (!cur->rgt) {
  134.                         /*
  135.                  * We have reach leaf. New node will be right son.
  136.                  */
  137.                 cur->rgt = newnode;
  138.  
  139.                 newnode->lft = NULL;
  140.                 newnode->rgt = NULL;
  141.                 newnode->lft_height = 0;
  142.                 newnode->rgt_height = 0;
  143.                         newnode->par = cur;
  144.                
  145.                 newnode->prev = cur;
  146.                 newnode->next = cur->next;
  147.                 cur->next->prev = newnode;
  148.                 cur->next = newnode;
  149.                         break;
  150.                     }
  151.             cur = cur->rgt;
  152.         } else if (cur->key > key) {
  153.             if (!cur->lft) {
  154.                         /*
  155.                  * We have reach leaf. New node will be left son.
  156.                  */
  157.                 cur->lft = newnode;
  158.  
  159.                 newnode->lft = NULL;
  160.                 newnode->rgt = NULL;
  161.                 newnode->lft_height = 0;
  162.                 newnode->rgt_height = 0;
  163.                 newnode->par = cur;
  164.                
  165.                 gpa = cur;
  166.                 while (gpa != &t->head && gpa->key == cur->key)
  167.                     gpa = gpa->prev;
  168.                 newnode->next = gpa->next;
  169.                 newnode->prev = gpa;
  170.                 gpa->next->prev = newnode;
  171.                 gpa->next = newnode;
  172.                 break;
  173.                     }
  174.             cur = cur->lft;
  175.         } else {
  176.             /*
  177.              * Key has been previously inserted into tree. Make new node as a tree node
  178.              * and old tree node move to the prev. Old tree node will be list node.
  179.              */
  180.            
  181.             newnode->prev = cur;
  182.             newnode->next = cur->next;
  183.             cur->next->prev = newnode;
  184.             cur->next = newnode;
  185.  
  186.             newnode->par = cur->par;
  187.             cur->par = NULL;
  188.             newnode->lft = cur->lft;
  189.             cur->lft = NULL;
  190.             newnode->rgt = cur->rgt;
  191.             cur->rgt = NULL;
  192.             newnode->lft_height = cur->lft_height;
  193.             cur->lft_height = 0;
  194.             newnode->rgt_height = cur->rgt_height;
  195.             cur->rgt_height = 0;
  196.  
  197.             if (newnode->lft) newnode->lft->par = newnode;
  198.             if (newnode->rgt) newnode->rgt->par = newnode;
  199.             if (newnode->par) {
  200.                 if (newnode->par->lft == cur)
  201.                     newnode->par->lft = newnode;
  202.                 else
  203.                     newnode->par->rgt = newnode;
  204.             } else {
  205.                 t->root = newnode;
  206.             }
  207.             return;
  208.         }
  209.     }
  210.  
  211.     /*
  212.      * Balancing all nodes from newnode's parent down to root. All nodes must be checked
  213.      * because delete min operation can corrupt heights and only insert operation can
  214.      * repair it.
  215.      */
  216.     cur = newnode->par;
  217.     while (cur) {
  218.         if (cur->key > key) {
  219.             /*
  220.              * Insertion was made in the left subtree - repair left height
  221.              * and check balance of current node.
  222.              */
  223.             cur->lft_height = extavltree_tree_height(cur->lft) + 1;
  224.  
  225.             if ((cur->rgt_height - cur->lft_height) <= -2) {
  226.                 /*
  227.                  * Balance was corrupted, must be repaired through LL or LR rotation.
  228.                  */
  229.                 par = cur->par;
  230.                 son = cur->lft;
  231.                 if ((son->rgt_height - son->lft_height) != 1) {
  232.                     /*
  233.                      * LL rotation
  234.                      */
  235.                    
  236.                     gpa = son;
  237.                     cur->lft = son->rgt;
  238.                     if (cur->lft != NULL) cur->lft->par = cur;
  239.                     cur->par = son;
  240.                     son->rgt = cur;
  241.                     /*
  242.                      * Repair heights.
  243.                      */
  244.                     cur->lft_height = son->rgt_height;
  245.                     son->rgt_height = extavltree_tree_height(cur) + 1;
  246.                 } else {
  247.                     /*
  248.                      * LR rotation
  249.                      */
  250.                    
  251.                     gpa = son->rgt;
  252.                     son->rgt = gpa->lft;
  253.                     if (gpa->lft != NULL) gpa->lft->par = son;
  254.                     gpa->lft = son;
  255.                     son->par = gpa;
  256.                     cur->lft = gpa->rgt;
  257.                     if (gpa->rgt != NULL) gpa->rgt->par = cur;
  258.                     gpa->rgt = cur;
  259.                     cur->par = gpa;
  260.                     /*
  261.                      * Repair heights.
  262.                      */
  263.                     cur->lft_height = gpa->rgt_height;
  264.                     son->rgt_height = gpa->lft_height;
  265.                     gpa->rgt_height = extavltree_tree_height(cur) + 1;
  266.                     gpa->lft_height = extavltree_tree_height(son) + 1;
  267.                 }
  268.  
  269.                 /*
  270.                  * Change parent pointers or if current node is root then
  271.                  * change root atribute pointer.
  272.                  */
  273.                 gpa->par = par;
  274.                 if (par) {
  275.                     if (par->lft == cur)
  276.                         par->lft = gpa;
  277.                     else
  278.                         par->rgt = gpa;
  279.                 } else {
  280.                     t->root = gpa;
  281.                 }
  282.                 cur = par;
  283.             } else {
  284.                 /*
  285.                  * Current node is balanced, continue balancing of its parent.
  286.                  */
  287.                 cur = cur->par;
  288.             }
  289.         } else {
  290.             /*
  291.              * Insertion was made in the right subtree - repair right height
  292.              * and check balance of current node.
  293.              */
  294.             cur->rgt_height = extavltree_tree_height(cur->rgt) + 1;
  295.  
  296.             if ((cur->rgt_height - cur->lft_height) >= 2) {
  297.                 /*
  298.                  * Balance was corrupted, must be repaired through LL or LR rotation.
  299.                  */
  300.                 par = cur->par;
  301.                 son = cur->rgt;
  302.                 if ((son->rgt_height - son->lft_height) != -1) {
  303.                     /*
  304.                      * RR rotation
  305.                      */
  306.                     gpa = son;
  307.                     cur->rgt = son->lft;
  308.                     if (cur->rgt != NULL) cur->rgt->par = cur;
  309.                     cur->par = son;
  310.                     son->lft = cur;
  311.                     /*
  312.                      * Repair heights.
  313.                      */
  314.                     cur->rgt_height = son->lft_height;
  315.                     son->lft_height = extavltree_tree_height(cur) + 1;
  316.                 } else {
  317.                     /*
  318.                      * RL rotation
  319.                      */
  320.                     gpa = son->lft;
  321.                     son->lft = gpa->rgt;
  322.                     if (gpa->rgt != NULL) gpa->rgt->par = son;
  323.                     gpa->rgt = son;
  324.                     son->par = gpa;
  325.                     cur->rgt = gpa->lft;
  326.                     if (gpa->lft != NULL) gpa->lft->par = cur;
  327.                     gpa->lft = cur;
  328.                     cur->par = gpa;
  329.                     /*
  330.                      * Repair heights.
  331.                      */
  332.                     cur->rgt_height = gpa->lft_height;
  333.                     son->lft_height = gpa->rgt_height;
  334.                     gpa->lft_height = extavltree_tree_height(cur) + 1;
  335.                     gpa->rgt_height = extavltree_tree_height(son) + 1;
  336.                 }
  337.  
  338.                 /*
  339.                  * Change parent pointers or if current node is root then
  340.                  * change root atribute pointer.
  341.                  */            
  342.                 gpa->par = par;
  343.                 if (par) {
  344.                     if (par->lft == cur)
  345.                         par->lft = gpa;
  346.                     else
  347.                         par->rgt = gpa;
  348.                 } else {
  349.                     t->root = gpa;
  350.                 }
  351.                 cur = par;
  352.             } else {
  353.                 /*
  354.                  * Current node is balanced, continue balancing of its parent.
  355.                  */
  356.                 cur = cur->par;
  357.             }
  358.         }
  359.     }
  360. }
  361.  
  362. /** Delete node from ExtAVL tree.
  363.  *
  364.  * @param t ExtAVL tree structure.
  365.  * @param node Address of node which will be deleted.
  366.  */
  367. void extavltree_delete(extavltree_t *t, extavltree_node_t *node)
  368. {
  369.     extavltree_node_t **gpapar;
  370.     extavltree_node_t *cur;
  371.     extavltree_node_t *par;
  372.     extavltree_node_t *gpa;
  373.     int8_t dir;
  374.     int8_t dir2=0;
  375.     int16_t balance;
  376.    
  377.     ASSERT(t);
  378.     ASSERT(node);
  379.  
  380.     /*
  381.      * Delete node from list.
  382.      */
  383.     node->next->prev = node->prev;
  384.     node->prev->next = node->next;
  385.  
  386.     if (!node->par) {
  387.         if (t->root != node) {
  388.             /*
  389.              * It is list node (not a tree node). Needn't repair tree or anything else.
  390.              */
  391.             return;
  392.         }
  393.         gpapar = &(t->root);
  394.     } else {
  395.         /*
  396.          * Find tree pointer which points to node.
  397.          */
  398.         if (node->par->lft == node) {
  399.             gpapar = &(node->par->lft);
  400.         } else {
  401.             gpapar = &(node->par->rgt);
  402.         }
  403.     }
  404.    
  405.    
  406.     if (&t->head != node->prev && node->prev->key == node->key) {
  407.         /*
  408.          * Deleted node has at least one node node with the same key which is closest previous
  409.          * neighbor in the list, copy node atributes into previous node and end.
  410.          */
  411.         cur = node->prev;
  412.         cur->lft = node->lft;
  413.         cur->rgt = node->rgt;
  414.         cur->par = node->par;
  415.         cur->lft_height = node->lft_height;
  416.         cur->rgt_height = node->rgt_height;
  417.         *gpapar = cur;
  418.  
  419.         if (node->lft) node->lft->par = cur;
  420.         if (node->rgt) node->rgt->par = cur;
  421.         return;
  422.     }
  423.    
  424.     /*
  425.      * Check situation in the tree around deleted node.
  426.      */
  427.     if (!node->lft) {
  428.         /*
  429.          * Deleted node has not left son. Right son will take deleted node's place.
  430.          */
  431.         gpa = node->par;
  432.         if (node->rgt) node->rgt->par = gpa;
  433.         if (!gpa) {
  434.             /*
  435.              * Deleted node is root node. Balancing is finished, change only
  436.              * root pointer in extavltree structure.
  437.              */
  438.             *gpapar = node->rgt;   
  439.             return;
  440.         }
  441.         dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
  442.         *gpapar = node->rgt;
  443.     } else {
  444.         /*
  445.          * Node has left son.
  446.          */
  447.         cur = node->lft;
  448.         if (!cur->rgt) {
  449.             /*
  450.              * Left son of node hasn't got right son. Left son will take deleted node's place.
  451.              */
  452.             *gpapar = cur;
  453.             cur->par = node->par;
  454.             dir = AVLTREE_LEFT;
  455.             cur->rgt = node->rgt;
  456.             if (node->rgt) node->rgt->par = cur;
  457.             gpa = cur;
  458.             cur->rgt_height = node->rgt_height;
  459.             cur->lft_height = node->lft_height;
  460.             /*
  461.              * cur->lft_height will be decreased in repair cycle.
  462.              */
  463.         } else {
  464.             /*
  465.              * Node has left and right son. Find a node with smallest key in left subtree
  466.              * and change that node with deleted node.
  467.              */
  468.             while (cur->rgt != NULL)
  469.                 cur = cur->rgt;
  470.            
  471.             *gpapar = cur;
  472.             cur->rgt = node->rgt;
  473.             if (node->rgt) node->rgt->par = cur;
  474.             gpa = cur->par;
  475.             gpa->rgt = cur->lft;
  476.             if (cur->lft) cur->lft->par = gpa;
  477.             cur->lft = node->lft;
  478.             cur->lft->par = cur;
  479.             cur->par = node->par;
  480.             dir = AVLTREE_RIGHT;
  481.             cur->lft_height = node->lft_height;
  482.             cur->rgt_height = node->rgt_height;
  483.             /*
  484.              * gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
  485.              */
  486.         }
  487.         /*
  488.          * Deleted node is root node. Balancing is finished.
  489.          */
  490.         if (!gpa) return;
  491.     }
  492.    
  493.     /*
  494.      * Repair cycle which goes from gpa node down to root.
  495.      */
  496.     for(;;) {
  497.         /*
  498.          * Find tree pointer which points to the currently balanced node. When balanced
  499.          * node is root, root pointer from extavltree structure is taken.
  500.          */
  501.         if (!gpa->par)
  502.             gpapar = &(t->root);
  503.         else {
  504.             if (gpa->par->lft == gpa) {
  505.                 gpapar = &(gpa->par->lft);
  506.                 dir2 = AVLTREE_LEFT;
  507.             } else {
  508.                 gpapar = &(gpa->par->rgt);
  509.                 dir2 = AVLTREE_RIGHT;
  510.             }
  511.         }
  512.  
  513.         if (dir == AVLTREE_LEFT) {
  514.             /*
  515.              * Deletition was made in left subtree.
  516.              */
  517.             gpa->lft_height--;
  518.             balance = gpa->rgt_height - gpa->lft_height;
  519.             if (balance == 1) {
  520.                 /*
  521.                  * Stop balancing, tree is balanced.
  522.                  */
  523.                 break;
  524.             } else if (balance == 2) {
  525.                 /*
  526.                  * Bad balance, heights of left and right subtrees differs more then is allowed.
  527.                  */
  528.                 par = gpa->rgt;
  529.  
  530.                 if ((par->rgt_height - par->lft_height) == -1) {
  531.                     /*
  532.                      * RL rotation
  533.                      */
  534.                    
  535.                     cur = par->lft;
  536.                     par->lft = cur->rgt;
  537.                     cur->rgt = par;
  538.                     gpa->rgt = cur->lft;
  539.                     cur->lft = gpa;
  540.                    
  541.                     /*
  542.                      * Repair balances.
  543.                      */
  544.                     par->lft_height = cur->rgt_height;
  545.                     gpa->rgt_height = cur->lft_height;
  546.                     cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni
  547.                     cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1;
  548.                    
  549.                     /*
  550.                      * Repair paternity.
  551.                      */
  552.                     if (gpa->rgt) gpa->rgt->par = gpa;
  553.                     if (par->lft) par->lft->par = par;
  554.                     cur->par = gpa->par;
  555.                     gpa->par = cur;
  556.                     par->par = cur;
  557.  
  558.                     /*
  559.                      * Repair tree pointer which points to the current node and do the next step.
  560.                      */
  561.                     *gpapar = cur;
  562.                     gpa = cur->par;
  563.                 } else {
  564.                     /*
  565.                      * RR rotation
  566.                      */
  567.                    
  568.                     gpa->rgt = par->lft;
  569.                     gpa->rgt_height = par->lft_height;
  570.                     if (par->lft) par->lft->par = gpa;
  571.                     par->lft = gpa;
  572.                    
  573.                     /*
  574.                      * Repair paternity.
  575.                      */
  576.                     par->par = gpa->par;
  577.                     gpa->par = par;
  578.                    
  579.                     /*
  580.                      * Repair balances.
  581.                      */
  582.                     balance = par->rgt_height - par->lft_height;
  583.                     par->lft_height++;
  584.                    
  585.                     /*
  586.                      * Repair tree pointer which points to the current node, ends when tree is balanced
  587.                      * or do the next step.
  588.                      */
  589.                     *gpapar = par;
  590.                     if (balance == 0) break;
  591.                     gpa = par->par;
  592.                 }
  593.             } else {
  594.                 /*
  595.                  * Current node is balanced - perform balance check of its parent.
  596.                  */
  597.                 gpa = gpa->par;
  598.             }
  599.         } else {
  600.             /*
  601.              * Balance right son.
  602.              */
  603.             gpa->rgt_height--;
  604.             balance = gpa->rgt_height - gpa->lft_height;
  605.             if (balance == -1) {
  606.                 /*
  607.                  * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
  608.                  */
  609.                 break;
  610.             } else if (balance == -2) {
  611.                 /*
  612.                  * Balance was corrupted - must be repaired.
  613.                  */
  614.                 par = gpa->lft;
  615.  
  616.                 if ((par->rgt_height - par->lft_height) >= +1) {
  617.                     /*
  618.                      * If balance is -2 then par node always exists.
  619.                      */
  620.                     if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) {
  621.                         /*
  622.                          * LR rotation. Height of par subtree is not decreased due to timeout operation.
  623.                          */
  624.                        
  625.                         cur = par->rgt;
  626.                         par->rgt = cur->lft;
  627.                         cur->lft = par;
  628.                         gpa->lft = cur->rgt;
  629.                         cur->rgt = gpa;
  630.                        
  631.                         /*
  632.                          * Repair balances.
  633.                          */                    
  634.                         par->rgt_height = cur->lft_height;
  635.                         gpa->lft_height = cur->rgt_height;
  636.                         cur->rgt_height = gpa->rgt_height + 1;
  637.                         cur->lft_height = extavltree_tree_height(par) + 1;
  638.  
  639.                         /*
  640.                          * Repair paternity.
  641.                          */
  642.                         if (gpa->lft) gpa->lft->par = gpa;
  643.                         if (par->rgt) par->rgt->par = par;
  644.                         cur->par = gpa->par;
  645.                         gpa->par = cur;
  646.                         par->par = cur;
  647.  
  648.                         /*
  649.                          * Repair tree pointer which points to the current node and do the next step.
  650.                          */
  651.                         *gpapar = cur;
  652.                         gpa = cur->par;
  653.                     } else {
  654.                             /*
  655.                          * Left subtree of cur has been already decreased by timeout operation.
  656.                          */
  657.                         gpa = gpa->par;
  658.                     }
  659.                 } else {
  660.                     /*
  661.                      * LL rotation.
  662.                      */
  663.                    
  664.                     int prevlftheight = gpa->lft_height;
  665.                     gpa->lft = par->rgt;
  666.                     gpa->lft_height = par->rgt_height;
  667.                     if (par->rgt) par->rgt->par = gpa;
  668.                     par->rgt = gpa;
  669.                    
  670.                     /*
  671.                      * Repair paternity.
  672.                      */
  673.                     par->par = gpa->par;
  674.                     gpa->par = par;
  675.                    
  676.                     /*
  677.                      * Repair height.
  678.                      */
  679.                     balance = par->rgt_height - par->lft_height;
  680.                     par->rgt_height = extavltree_tree_height(gpa) + 1;
  681.                    
  682.                     /*
  683.                      * Repair tree pointer which points to the current node, ends when heights in par nodes are
  684.                      * balanced and height of par subtree wasn't decreased due to timeout operation orr do
  685.                      * the next step.
  686.                      */
  687.                     *gpapar = par; 
  688.                     if (balance == 0 && par->rgt_height == prevlftheight) return;
  689.                     gpa = par->par;
  690.                 }
  691.             } else {
  692.                 /*
  693.                  * Current node is balanced - perform balance check of its parent.
  694.                  */
  695.                 gpa = gpa->par;
  696.             }
  697.         }
  698.         /*
  699.          * When root is reached then end balancing.
  700.          */
  701.         if (!gpa) return;
  702.  
  703.         dir = dir2;
  704.     }
  705. }
  706.  
  707.  
  708. /** Delete node from ExtAVL tree with the smallest key and set base of tree to that key.
  709.  *
  710.  * @param t ExtAVL tree structure.
  711.  */
  712. bool extavltree_delete_min(extavltree_t *t)
  713. {
  714.     extavltree_node_t *expnode;
  715.    
  716.     ASSERT(t);
  717.    
  718.     expnode = t->head.next;
  719.    
  720.     if (&t->head == expnode) return false;
  721.  
  722.     if (expnode->key != expnode->next->key) {
  723.         /*
  724.          * Repair tree data structure.
  725.          */
  726.         if (!expnode->par) {
  727.             /*
  728.              * Delete root node which musn't have left son.
  729.              */
  730.            
  731.             ASSERT(!expnode->lft);
  732.             t->root = expnode->rgt;
  733.             if (expnode->rgt) expnode->rgt->par = NULL;
  734.         } else if (expnode->rgt) {
  735.             /*
  736.              * Always delete parent of left son.
  737.              */
  738.            
  739.             expnode->rgt->par = expnode->par;
  740.             expnode->par->lft = expnode->rgt;
  741.             expnode->par->lft_height = expnode->rgt_height;
  742.         } else {
  743.             /*
  744.              * Deleted node doesn't have right son.
  745.              */
  746.            
  747.             expnode->par->lft = NULL;
  748.             expnode->par->lft_height = 0;
  749.         }
  750.     }
  751.  
  752.     /*
  753.      * Delete node from the list.
  754.      */
  755.     t->head.next = expnode->next;
  756.     expnode->next->prev = &t->head;
  757.  
  758.     return true;
  759. }
  760.