Subversion Repositories HelenOS

Rev

Rev 2421 | 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 with relative keys implementation.
  36.  *
  37.  * This file implements Extended AVL tree with relative keys type and operations.
  38.  *
  39.  * Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties:
  40.  * @li it is binary search tree with unique real 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 real 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 real keys, node key is
  46.  *     only difference between previous real node's key and its real node's key
  47.  * @li real key is either equal node key if node is leftmost node in tree or sum of all
  48.  *     node keys with smaller real key
  49.  *
  50.  * Be careful of using this tree because node keys are not equal real keys (except leftmost node).
  51.  */
  52.  
  53. #include <adt/extavlrel.h>
  54. #include <debug.h>
  55. #include <panic.h>
  56.  
  57.  
  58. #define AVLTREE_LEFT 0
  59. #define AVLTREE_RIGHT 1
  60.  
  61.  
  62. /* Returns height of tree -1 */
  63. #define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
  64.  
  65. /** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree.
  66.  *
  67.  * @param t ExtAVLrel tree.
  68.  * @param key Key to be searched.
  69.  *
  70.  * @return Pointer to node or NULL if there is no such key.
  71.  */
  72. extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key)
  73. {
  74.     extavlreltree_node_t *cur;
  75.     uint64_t sum, s;
  76.    
  77.     /*
  78.      * Find right subtree in way up to the root where can be node with given key.
  79.      * Root node is the last node in the way up, when we reach root, it means,
  80.      * that searched node belongs to the right subtree of root.
  81.      */
  82.     sum = 0;
  83.     cur = t->head.next;
  84.     while (1) {
  85.         sum += cur->key + cur->rgt_sum;
  86.         if ((key <= sum) || (cur == t->root))
  87.             break;
  88.         else
  89.             cur = cur->par;
  90.     }
  91.  
  92.     /*
  93.      * Sorting for cycle.
  94.      * Search for key in choosen subtree. Searching start at cur node which we have found
  95.      * in previous step. It is common search algorithm for binary search tree.
  96.      */
  97.     while (cur != NULL) {
  98.         s = sum - cur->rgt_sum;
  99.         if (key < s) {
  100.             /*
  101.              * Left subtree. Find max value in left subtree of cur.
  102.              */
  103.             sum -= cur->key + cur->rgt_sum;
  104.             cur = cur->lft;
  105.         } else if (key > s) {
  106.             /*
  107.              * Right subtree. sum has still max value in the right subtree of cur.
  108.              */
  109.             cur = cur->rgt;
  110.         } else {
  111.             /*
  112.              * Equal values. We have found node with given key.
  113.              */
  114.             return cur;
  115.         }
  116.     }
  117.     return NULL;
  118. }
  119.  
  120.  
  121. /** Insert new node into ExtAVL tree.
  122.  *
  123.  * New node's key must be set.
  124.  *
  125.  * @param t ExtAVL tree structure.
  126.  * @param newnode New node to be inserted.
  127.  */
  128. void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode)
  129. {  
  130.     extavlreltree_node_t *cur;
  131.     extavlreltree_node_t *son;
  132.     extavlreltree_node_t *gpa;
  133.     extavlreltree_node_t *par;
  134.     uint64_t sum, s;
  135.     uint8_t dir;
  136.     /*
  137.      * Condition var - all rgt_sums in the way down to root must be repaired in condition
  138.      * that we came there from right and on the way from repaired node to new node we
  139.      * never turn to the left. Reparation is done in the reparation cycle.
  140.      */
  141.     bool repair_rgt_sum;
  142.    
  143.     ASSERT(t);
  144.     ASSERT(newnode);
  145.    
  146.     /*
  147.      * Insert first node into empty tree. Key is left without change (according to definition).
  148.      */
  149.     cur = t->head.next;
  150.     if (cur == &t->head) {
  151.         newnode->lft = NULL;
  152.         newnode->rgt = NULL;
  153.         newnode->lft_height = 0;
  154.         newnode->rgt_height = 0;
  155.         newnode->par = NULL;
  156.         newnode->next = &t->head;
  157.         newnode->prev = &t->head;
  158.         newnode->rgt_sum = 0;
  159.  
  160.         t->head.prev = newnode;
  161.         t->head.next = newnode;
  162.         t->root = newnode;
  163.         return;
  164.     }
  165.  
  166.     /*
  167.      * Find right subtree in way up to the root where newnode will be placed.
  168.      * Root node is the last node in the way up, when we reach root, it means,
  169.      * that newnode belongs to the right subtree of root.
  170.      *
  171.      * When max key of cur's right subtree is inserted, while cycle overjumps
  172.      * right node and stops. But in the next sorting for cycle is this situation
  173.      * solved (for cycle jumps back to the left child).
  174.      */
  175.     sum = 0;
  176.     while (1) {
  177.         sum += cur->key + cur->rgt_sum;
  178.         if ((newnode->key <= sum) || (cur == t->root))
  179.             break;
  180.         else
  181.             cur = cur->par;
  182.     }
  183.    
  184.  
  185.     /*
  186.      * Sorting for cycle.
  187.      * Find a place for newnode. Searching start at cur node which we have found
  188.      * in previous step. It is common search algorithm for binary search tree.
  189.      */
  190.     for (;;) {
  191.         s = sum - cur->rgt_sum;
  192.         if (newnode->key < s) {
  193.             /*
  194.              * Left subtree. Find max value in left subtree of cur.
  195.              */
  196.             sum -= cur->key + cur->rgt_sum;
  197.  
  198.             if (!cur->lft) {
  199.                 /*
  200.                  * Insert new node to the left.
  201.                  */
  202.                         cur->lft = newnode;
  203.  
  204.                 newnode->lft = NULL;
  205.                 newnode->rgt = NULL;
  206.                 newnode->lft_height = 0;
  207.                 newnode->rgt_height = 0;
  208.                         newnode->par = cur;
  209.                 /*
  210.                  * Insert newnode to list.
  211.                  */
  212.                 newnode->next = cur;
  213.                 newnode->prev = cur->prev;
  214.                 cur->prev->next = newnode;
  215.                 cur->prev = newnode;
  216.                
  217.                 newnode->key -= sum;
  218.                 newnode->rgt_sum = 0;
  219.                 /*
  220.                  * Repair key of next value (next node always exists). newnode->key
  221.                  * has been already set. Needn't check whether newnode->next is head
  222.                  * beacause newnode is left child (next node is his father).
  223.                  */
  224.                 newnode->next->key -= newnode->key;
  225.  
  226.                 repair_rgt_sum = false;
  227.                 dir = AVLTREE_LEFT;
  228.                 break;
  229.                     }
  230.             cur = cur->lft;
  231.         } else if (newnode->key > s) {
  232.             /*
  233.              * Right subtree. sum has still max value in the right subtree of cur.
  234.              */
  235.  
  236.             if (!cur->rgt) {
  237.                         cur->rgt = newnode;
  238.  
  239.                 newnode->lft = NULL;
  240.                 newnode->rgt = NULL;
  241.                 newnode->lft_height = 0;
  242.                 newnode->rgt_height = 0;
  243.                         newnode->par = cur;
  244.                
  245.                 /*
  246.                  * Find last node in the chain with the same key as cur node.
  247.                  */
  248.                 gpa = cur->next;
  249.                 while (gpa != &t->head && gpa->key == 0)
  250.                     gpa = gpa->next;
  251.                
  252.                 /*
  253.                  * Insert new node to list. Right place in the list was found in
  254.                  * previous cycle.
  255.                  */
  256.                 newnode->prev = gpa->prev;
  257.                 newnode->next = gpa;
  258.                 gpa->prev->next = newnode;
  259.                 gpa->prev = newnode;
  260.                
  261.                 newnode->key -= sum;
  262.                 newnode->rgt_sum = 0;
  263.                 /*
  264.                  * Repair key of next value (next node always exists). newnode->key
  265.                  * has been already set.
  266.                  */
  267.                 if (newnode->next != &t->head)
  268.                     newnode->next->key -= newnode->key;
  269.                 /*
  270.                  * All rgt_sums in the way down to root must be repaired in condition
  271.                  * that we came there from right and on the way from node to new node we
  272.                  * never turn left.
  273.                  */
  274.                 repair_rgt_sum = true;
  275.                 dir = AVLTREE_RIGHT;
  276.                         break;
  277.                     }
  278.             cur = cur->rgt;
  279.  
  280.         } else {
  281.             /*
  282.              * Equal values. Give newnode to the last position of chain with the cur head and
  283.              * end insertion.
  284.              */
  285.             gpa = cur->next;
  286.             while (gpa != &t->head && gpa->key == 0)
  287.                 gpa = gpa->next;
  288.             /*
  289.              * Insert new node to list in right place.
  290.              */
  291.             newnode->prev = gpa->prev;
  292.             newnode->next = gpa;
  293.             gpa->prev->next = newnode;
  294.             gpa->prev = newnode;
  295.  
  296.             newnode->par = NULL;
  297.             newnode->lft = NULL;
  298.             newnode->rgt = NULL;
  299.             newnode->lft_height = 0;
  300.             newnode->rgt_height = 0;
  301.            
  302.             /*
  303.              * Nodes in chains has key equal 0, because difference between previous node and them is 0.
  304.              */
  305.             newnode->key = 0;
  306.             newnode->rgt_sum = 0;
  307.             return;
  308.         }
  309.     }
  310.  
  311.     /*
  312.      * Balancing all nodes from newnode's parent down to root.
  313.      */
  314.     cur = newnode->par;
  315.     while (true) {
  316.         if (dir == AVLTREE_LEFT) {
  317.             /*
  318.              * Insertion was made in the left subtree - repair left height, stop
  319.              * repairing rgt_sum and check balance of current node.
  320.              */
  321.             cur->lft_height = extavlreltree_tree_height(cur->lft) + 1;
  322.  
  323.             repair_rgt_sum = false;
  324.  
  325.             if ((cur->rgt_height - cur->lft_height) <= -2) {
  326.                 /*
  327.                  * Balance was corrupted, must be repaired through LL or LR rotation.
  328.                  */
  329.                 par = cur->par;
  330.                 son = cur->lft;
  331.                 if ((son->rgt_height - son->lft_height) != 1) {
  332.                     /*
  333.                      * LL rotation.
  334.                      */
  335.                     gpa = son;
  336.                     cur->lft = son->rgt;
  337.                     if (cur->lft != NULL) cur->lft->par = cur;
  338.                     cur->par = son;
  339.                     son->rgt = cur;
  340.                     /*
  341.                      * Repair heights.
  342.                      */
  343.                     cur->lft_height = son->rgt_height;
  344.                     son->rgt_height = extavlreltree_tree_height(cur) + 1;
  345.                     /*
  346.                      * Repair rgt_sum.
  347.                      */
  348.                     son->rgt_sum += cur->key + cur->rgt_sum;
  349.                 } else {
  350.                     /*
  351.                      * LR rotation.
  352.                      */
  353.                     gpa = son->rgt;
  354.                     son->rgt = gpa->lft;
  355.                     if (gpa->lft != NULL) gpa->lft->par = son;
  356.                     gpa->lft = son;
  357.                     son->par = gpa;
  358.                     cur->lft = gpa->rgt;
  359.                     if (gpa->rgt != NULL) gpa->rgt->par = cur;
  360.                     gpa->rgt = cur;
  361.                     cur->par = gpa;
  362.                     /*
  363.                      * Repair heights.
  364.                      */
  365.                     cur->lft_height = gpa->rgt_height;
  366.                     son->rgt_height = gpa->lft_height;
  367.                     gpa->rgt_height = extavlreltree_tree_height(cur) + 1;
  368.                     gpa->lft_height = extavlreltree_tree_height(son) + 1;
  369.                     /*
  370.                      * Repair rgt_sums.
  371.                      */
  372.                     son->rgt_sum -= gpa->key + gpa->rgt_sum;
  373.                     gpa->rgt_sum += cur->key + cur->rgt_sum;
  374.                 }
  375.                 /*
  376.                  * Repair parent of current node.
  377.                  */
  378.                 gpa->par = par;
  379.             } else {
  380.                 /*
  381.                  * Balance is correct, continue balancing at parent node.
  382.                  */
  383.                 par = cur->par;
  384.                 gpa = cur;
  385.             }
  386.         } else {
  387.             /*
  388.              * Insertion was made in the right subtree - repair right height, try to
  389.              * repair rgt_sum and check balance of current node.
  390.              */
  391.             cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1;
  392.  
  393.             if (repair_rgt_sum) {
  394.                 cur->rgt_sum += newnode->key;
  395.             }
  396.  
  397.             if ((cur->rgt_height - cur->lft_height) >= 2) {
  398.                 /*
  399.                  * Balance was corrupted, must be repaired through RL or RR rotation.
  400.                  */
  401.                 par = cur->par;
  402.                 son = cur->rgt;
  403.                 if ((son->rgt_height - son->lft_height) != -1) {
  404.                         /*
  405.                      * RR rotation.
  406.                      */
  407.                     gpa = son;
  408.                     cur->rgt = son->lft;
  409.                     if (cur->rgt != NULL) cur->rgt->par = cur;
  410.                     cur->par = son;
  411.                     son->lft = cur;
  412.                     /*
  413.                      * Repair heights.
  414.                      */
  415.                     cur->rgt_height = son->lft_height;
  416.                     son->lft_height = extavlreltree_tree_height(cur) + 1;
  417.                     /*
  418.                      * Repair rgt_sum.
  419.                      */
  420.                     cur->rgt_sum -= son->rgt_sum + son->key;
  421.                 } else {
  422.                     /*
  423.                      * RL rotation.
  424.                      */
  425.                     gpa = son->lft;
  426.                     son->lft = gpa->rgt;
  427.                     if (gpa->rgt != NULL) gpa->rgt->par = son;
  428.                     gpa->rgt = son;
  429.                     son->par = gpa;
  430.                     cur->rgt = gpa->lft;
  431.                     if (gpa->lft != NULL) gpa->lft->par = cur;
  432.                     gpa->lft = cur;
  433.                     cur->par = gpa;
  434.                     /*
  435.                      * Repair heights.
  436.                      */
  437.                     cur->rgt_height = gpa->lft_height;
  438.                     son->lft_height = gpa->rgt_height;
  439.                     gpa->lft_height = extavlreltree_tree_height(cur) + 1;
  440.                     gpa->rgt_height = extavlreltree_tree_height(son) + 1;
  441.                     /*
  442.                      * Repair rgt_sums.
  443.                      */
  444.                     cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum;
  445.                     gpa->rgt_sum += son->key + son->rgt_sum;
  446.                 }
  447.  
  448.                 /*
  449.                  * Repair parent of current node.
  450.                  */
  451.                 gpa->par = par;
  452.             } else {
  453.                 /*
  454.                  * Balance is correct, continue balancing at parent node.
  455.                  */
  456.                 par = cur->par;
  457.                 gpa = cur;
  458.             }
  459.         }
  460.         /*
  461.          * Change parent pointers, set direction where is newnode and
  462.          * continue balancing at parent node or if current node
  463.          * is root then change root atribute pointer and stop
  464.          */
  465.         if (par) {
  466.             if (par->lft == cur) {
  467.                 par->lft = gpa;
  468.                 dir = AVLTREE_LEFT;
  469.             } else {
  470.                 par->rgt = gpa;
  471.                 dir = AVLTREE_RIGHT;
  472.             }
  473.         } else {
  474.             t->root = gpa;
  475.             break;
  476.         }
  477.         cur = par;
  478.     }
  479. }
  480.  
  481.  
  482. /** Delete node from ExtAVLrel tree.
  483.  *
  484.  * @param t ExtAVLrel tree structure.
  485.  * @param node Address of node which will be deleted.
  486.  */
  487. void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node)
  488. {
  489.     extavlreltree_node_t **gpapar;
  490.     extavlreltree_node_t *cur;
  491.     extavlreltree_node_t *par;
  492.     extavlreltree_node_t *gpa;
  493.     int8_t dir;
  494.     int8_t dir2=0;
  495.     uint64_t key=0;
  496.     int16_t balance;
  497.     /*
  498.      * Condition var - if true then all rgt_sums in the way down to root must be repaired in condition
  499.      * that we came there from right and on the way from repaired node to new node we
  500.      * never turn to the left. Reparation is done in the reparation cycle.
  501.      */
  502.     bool repair_rgt_sum;
  503.  
  504.    
  505.     ASSERT(t);
  506.     ASSERT(node);
  507.    
  508.     /*
  509.      * Delete node from list.
  510.      */
  511.     node->next->prev = node->prev;
  512.     node->prev->next = node->next;
  513.    
  514.     if (!node->par) {
  515.         if (t->root != node) {
  516.             /*
  517.              * It is list node (not a tree node). Needn't repair tree or anything else.
  518.              */
  519.             return;
  520.         }
  521.         repair_rgt_sum = false;
  522.         gpapar = &(t->root);
  523.     } else {
  524.         /*
  525.          * Find tree pointer which points to node.
  526.          */
  527.         if (node->par->lft == node) {
  528.             gpapar = &(node->par->lft);
  529.             repair_rgt_sum = false;
  530.         } else {
  531.             gpapar = &(node->par->rgt);
  532.             /*
  533.              * Node is right child - rgt_sum might be repaired.
  534.              */
  535.             repair_rgt_sum = true;
  536.         }
  537.     }
  538.  
  539.        
  540.     if (&t->head != node->next && node->next->key == 0) {
  541.         /*
  542.          * Deleted node has at least one node node with the same key which is closest next
  543.          * neighbor in the list, copy node atributes into next node and end.
  544.          */
  545.         cur = node->next;
  546.         cur->lft = node->lft;
  547.         cur->rgt = node->rgt;
  548.         cur->par = node->par;
  549.         cur->lft_height = node->lft_height;
  550.         cur->rgt_height = node->rgt_height;
  551.         *gpapar = cur;
  552.  
  553.         if (node->lft) node->lft->par = cur;
  554.         if (node->rgt) node->rgt->par = cur;
  555.  
  556.         cur->key = node->key;
  557.         cur->rgt_sum = node->rgt_sum;
  558.         return;
  559.     }
  560.  
  561.     /*
  562.      * Repair next node's key (it must be difference between previous key and its key).
  563.      */
  564.     if (node->next != &t->head) {
  565.         node->next->key += node->key;
  566.     }
  567.  
  568.     /*
  569.      * Check situation in the tree around deleted node.
  570.      */
  571.     if (!node->lft) {
  572.         /*
  573.          * Deleted node has not left son. Right son will take deleted node's place.
  574.          */
  575.         gpa = node->par;
  576.         if (node->rgt) {
  577.             /*
  578.              * rgt_sum is not corrupted because the biggest key is in right subtree of node
  579.              */
  580.             node->rgt->par = gpa;
  581.             repair_rgt_sum = false;
  582.         } else {
  583.             /*
  584.              * node is the biggest key and rgt_sum might be repaired according to which
  585.              * child is node.
  586.              */
  587.             key = node->key;
  588.         }
  589.  
  590.         if (!gpa) {
  591.             /*
  592.              * Deleted node is root node. Balancing is finished, change only
  593.              * root pointer in extavltree structure.
  594.              */
  595.             *gpapar = node->rgt;
  596.             return;
  597.         }
  598.         dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
  599.        
  600.         *gpapar = node->rgt;
  601.     } else {
  602.         /*
  603.          * Node has left son.
  604.          */
  605.         cur = node->lft;
  606.         if (!cur->rgt) {
  607.             /*
  608.              * Left son of node hasn't got right son. Left son will take deleted node's place.
  609.              */
  610.             *gpapar = cur;
  611.             cur->par = node->par;
  612.             dir = AVLTREE_LEFT;
  613.             cur->rgt = node->rgt;
  614.             if (node->rgt) node->rgt->par = cur;
  615.             gpa = cur;
  616.             cur->rgt_height = node->rgt_height;
  617.             cur->lft_height = node->lft_height;
  618.             /*
  619.              * cur->lft_height will be decreased in repair cycle.
  620.              */
  621.            
  622.             if (repair_rgt_sum == false && node->rgt_sum == 0) {
  623.                 /*
  624.                  * node hasn't got right son so right sum is 0.
  625.                  */
  626.                 cur->rgt_sum = 0;
  627.             } else {
  628.                 cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu
  629.                 if (repair_rgt_sum == true && node->rgt_sum != 0) {
  630.                     /*
  631.                      * node has got right son so node's key is not the biggest key in any subtree.
  632.                      */
  633.                     repair_rgt_sum = false;
  634.                 } else {
  635.                     /*
  636.                      * node is the biggest key and predecessors might be repaired.
  637.                      */
  638.                     key = node->key;
  639.                 }
  640.             }
  641.         } else {
  642.             /*
  643.              * Node has left and right son. Find a node with smallest key in left subtree
  644.              * and change that node with deleted node.
  645.              */
  646.             while (cur->rgt != NULL)
  647.                 cur = cur->rgt;
  648.  
  649.             *gpapar = cur;
  650.             cur->rgt = node->rgt;
  651.             if (node->rgt) node->rgt->par = cur;
  652.             gpa = cur->par;
  653.             gpa->rgt = cur->lft;
  654.             if (cur->lft) cur->lft->par = gpa;
  655.             cur->lft = node->lft;
  656.             cur->lft->par = cur;
  657.             cur->par = node->par;
  658.             dir = AVLTREE_RIGHT;
  659.             cur->lft_height = node->lft_height;
  660.             cur->rgt_height = node->rgt_height;
  661.             /*
  662.              * gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
  663.              */
  664.            
  665.             /*
  666.              * node must have always rgt child otherwise its malfunction of extavltree definition
  667.              * so we can add node->key. If it was to the contrary, we wouldn't know where
  668.              */
  669.             cur->rgt_sum = node->rgt_sum + node->key;
  670.             /*
  671.              * The biggest key in at least one subtree was changed - rgt_sum must be repaired.
  672.              */
  673.             repair_rgt_sum = true;
  674.             key = cur->key;
  675.         }
  676.         /*
  677.          * Deleted node is root node. Balancing is finished.
  678.          */
  679.         if (!gpa) return;
  680.     }
  681.    
  682.     /*
  683.      * Repair cycle which goes from gpa node down to root.
  684.      */
  685.     for(;;) {
  686.         if (repair_rgt_sum) {
  687.             /*
  688.              * The biggest key in right subtree was deleted so rgt_sum must be changed.
  689.              */
  690.             gpa->rgt_sum -= key;
  691.         }
  692.        
  693.         /*
  694.          * Find tree pointer which points to the currently balanced node. When balanced
  695.          * node is root, root pointer from extavltree structure is taken.
  696.          */
  697.         if (!gpa->par)
  698.             gpapar = &(t->root);
  699.         else {
  700.             if (gpa->par->lft == gpa) {
  701.                 gpapar = &(gpa->par->lft);
  702.                 dir2 = AVLTREE_LEFT;
  703.                 repair_rgt_sum = false;
  704.             } else {
  705.                 gpapar = &(gpa->par->rgt);
  706.                 dir2 = AVLTREE_RIGHT;
  707.             }
  708.         }
  709.  
  710.         if (dir == AVLTREE_LEFT) {
  711.             /*
  712.              * Deletition was made in left subtree.
  713.              */
  714.             gpa->lft_height--;
  715.             balance = gpa->rgt_height - gpa->lft_height;
  716.             if (balance == 1) {
  717.                 /*
  718.                  * Stop balancing, tree is balanced.
  719.                  */
  720.                 break;
  721.             } else if (balance == 2) {
  722.                 /*
  723.                  * Bad balance, heights of left and right subtrees differs more then is allowed.
  724.                  */
  725.                 par = gpa->rgt;
  726.  
  727.                 if ((par->rgt_height - par->lft_height) == -1) {
  728.                     /*
  729.                      * RL rotation
  730.                      */
  731.                    
  732.                     cur = par->lft;
  733.                     par->lft = cur->rgt;
  734.                     cur->rgt = par;
  735.                     gpa->rgt = cur->lft;
  736.                     cur->lft = gpa;
  737.                    
  738.                     /*
  739.                      * Repair balances.
  740.                      */
  741.                     par->lft_height = cur->rgt_height;
  742.                     gpa->rgt_height = cur->lft_height;
  743.                     cur->lft_height = extavlreltree_tree_height(gpa) + 1;
  744.                     cur->rgt_height = par->rgt_height + 1;
  745.                    
  746.                     /*
  747.                      * Repair paternity.
  748.                      */
  749.                     if (gpa->rgt) gpa->rgt->par = gpa;
  750.                     if (par->lft) par->lft->par = par;
  751.                     cur->par = gpa->par;
  752.                     gpa->par = cur;
  753.                     par->par = cur;
  754.  
  755.                     /*
  756.                      * Repair tree pointer which points to the current node.
  757.                      */
  758.                     *gpapar = cur;
  759.                    
  760.                     /*
  761.                      * Repair rgt_sums after rotation was done.
  762.                      */
  763.                     gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum;
  764.                     cur->rgt_sum += par->key + par->rgt_sum;
  765.                    
  766.                     /*
  767.                      * Next balancing at parent node.
  768.                      */
  769.                     gpa = cur->par;
  770.                 } else {
  771.                     /*
  772.                      * RR rotation
  773.                      */
  774.                     gpa->rgt = par->lft;
  775.                     gpa->rgt_height = par->lft_height;
  776.                     if (par->lft) par->lft->par = gpa;
  777.                     par->lft = gpa;
  778.                    
  779.                     /*
  780.                      * Repair paternity.
  781.                      */
  782.                     par->par = gpa->par;
  783.                     gpa->par = par;
  784.                    
  785.                     /*
  786.                      * Repair heights and tree pointer which points to the current node.
  787.                      */
  788.                     balance = par->rgt_height - par->lft_height;
  789.                     par->lft_height++;
  790.                     *gpapar = par;
  791.                    
  792.                     /*
  793.                      * Repair rgt_sums after rotation was done.
  794.                      */
  795.                     gpa->rgt_sum -= par->key + par->rgt_sum;
  796.                    
  797.                     /*
  798.                      * Ends when tree is balanced or do the next step.
  799.                      */
  800.                     if (balance == 0) return;
  801.                     gpa = par->par;
  802.                 }
  803.             } else {
  804.                 /*
  805.                  * Current node is balanced - perform balance check of its parent.
  806.                  */
  807.                 gpa = gpa->par;
  808.             }
  809.         } else {
  810.             /*
  811.              * Balance right son.
  812.              */
  813.             gpa->rgt_height--;
  814.             balance = gpa->rgt_height - gpa->lft_height;
  815.             if (balance == -1) {
  816.                 /*
  817.                  * Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
  818.                  */
  819.                 break;
  820.             } else if (balance == -2) {
  821.                 /*
  822.                  * Balance was corrupted - must be repaired.
  823.                  */
  824.                 par = gpa->lft;
  825.  
  826.                 if ((par->rgt_height - par->lft_height) >= +1) {
  827.                     /*
  828.                      * If balance is -2 then par node always exists.
  829.                      */
  830.                     if ((gpa->lft_height - (extavlreltree_tree_height(par))) == 1) {
  831.                         /*
  832.                          * LR rotation. Height of par subtree is not decreased due to timeout operation.
  833.                          */
  834.  
  835.                         cur = par->rgt;
  836.                         par->rgt = cur->lft;
  837.                         cur->lft = par;
  838.                         gpa->lft = cur->rgt;
  839.                         cur->rgt = gpa;
  840.                        
  841.                         /*
  842.                          * Repair balances.
  843.                          */
  844.                         par->rgt_height = cur->lft_height;
  845.                         gpa->lft_height = cur->rgt_height;
  846.                         cur->rgt_height = gpa->rgt_height + 1;
  847.                         cur->lft_height = extavlreltree_tree_height(par) + 1;
  848.  
  849.                         /*
  850.                          * Repair paternity.
  851.                          */
  852.                         if (gpa->lft) gpa->lft->par = gpa;
  853.                         if (par->rgt) par->rgt->par = par;
  854.                         cur->par = gpa->par;
  855.                         gpa->par = cur;
  856.                         par->par = cur;
  857.  
  858.                         /*
  859.                          * Repair tree pointer which points to the current node.
  860.                          */
  861.                         *gpapar = cur;
  862.                        
  863.                         /*
  864.                          * Repair rgt_sums after rotation was done.
  865.                          */
  866.                         par->rgt_sum -= cur->key + cur->rgt_sum;
  867.                         cur->rgt_sum += gpa->key + gpa->rgt_sum;
  868.  
  869.                         /*
  870.                          * Next balancing at parent node.
  871.                          */
  872.                         gpa = cur->par;
  873.                     } else {
  874.                         /*
  875.                          * Left subtree of cur has been already decreased by timeout operation.
  876.                          */
  877.                         gpa = gpa->par;
  878.                     }
  879.                 } else {
  880.                     /*
  881.                      * LL rotation.
  882.                      */
  883.                    
  884.                     int prevlftheight = gpa->lft_height;
  885.                     gpa->lft = par->rgt;
  886.                     gpa->lft_height = par->rgt_height;
  887.                     if (par->rgt) par->rgt->par = gpa;
  888.                     par->rgt = gpa;
  889.                    
  890.                     /*
  891.                      * Repair paternity.
  892.                      */
  893.                     par->par = gpa->par;
  894.                     gpa->par = par;
  895.                    
  896.                     /*
  897.                      * Repair heights and tree pointer which points to the current node.
  898.                      */
  899.                     balance = par->rgt_height - par->lft_height;
  900.                     par->rgt_height = extavlreltree_tree_height(gpa) + 1;
  901.                     *gpapar = par;
  902.                    
  903.                     /*
  904.                      * Repair rgt_sums after rotation was done.
  905.                      */
  906.                     par->rgt_sum += gpa->key + gpa->rgt_sum;
  907.  
  908.                     /*
  909.                      * Ends balancing when heights in par nodes are balanced and height
  910.                      * of par subtree wasn't decreased due to timeout operation or do
  911.                      * the next step.
  912.                      */
  913.                     if (balance == 0 && par->rgt_height == prevlftheight) {
  914.                         gpa = par;
  915.                         break;
  916.                     }
  917.                     gpa = par->par;
  918.                 }
  919.             } else {
  920.                 /*
  921.                  * Current node is balanced - perform balance check of its parent.
  922.                  */
  923.                 gpa = gpa->par;
  924.             }
  925.         }
  926.         /*
  927.          * When root is reached then end balancing.
  928.          */
  929.         if (!gpa) return;
  930.  
  931.         dir = dir2;
  932.     }
  933.  
  934.     /*
  935.      * End balancing. We must continue in repairing rgt_sum until we
  936.      * reach first left child.
  937.      */
  938.     if (repair_rgt_sum) {
  939.         cur = gpa;
  940.         gpa = gpa->par;
  941.         while (gpa) {
  942.             if (gpa->lft == cur)
  943.                 break;
  944.             gpa->rgt_sum -= key;
  945.             cur = gpa;
  946.             gpa = gpa->par;
  947.         }
  948.     }
  949. }
  950.  
  951.  
  952. /** Delete node from ExtAVLirel tree with the smallest key.
  953.  *
  954.  * Be careful deleted node must have key equal 0 to perform regular timeout.
  955.  *
  956.  * @param t ExtAVLrel tree structure.
  957.  */
  958. bool extavlreltree_delete_min(extavlreltree_t *t)
  959. {
  960.     extavlreltree_node_t *expnode;
  961.     extavlreltree_node_t *nextnode;
  962.    
  963.     ASSERT(t);
  964.    
  965.     expnode = t->head.next;
  966.     nextnode = expnode->next;
  967.  
  968.     if (&t->head == expnode) return false;
  969.  
  970.     if (nextnode != &t->head) {
  971.         /*
  972.          * Only first node in the list can be tree node and its key can be 0 (nextnode is the second).
  973.          */
  974.         if (nextnode->key == 0) {
  975.             /*
  976.              * Next node of expnode is its chain node. Copy expnode into nextnode.
  977.              */
  978.            
  979.             nextnode->lft = expnode->lft;
  980.             nextnode->rgt = expnode->rgt;
  981.             nextnode->par = expnode->par;
  982.             nextnode->lft_height = expnode->lft_height;
  983.             nextnode->rgt_height = expnode->rgt_height;
  984.             if (t->root == expnode)
  985.                 t->root = nextnode;
  986.             else
  987.                 if (expnode->par->lft == expnode)
  988.                     expnode->par->lft = nextnode;
  989.                 else
  990.                     expnode->par->rgt = nextnode;
  991.  
  992.             if (expnode->lft) expnode->lft->par = nextnode;
  993.             if (expnode->rgt) expnode->rgt->par = nextnode;
  994.  
  995.             nextnode->rgt_sum = expnode->rgt_sum;
  996.         } else if (!expnode->par) {
  997.             /*
  998.              * Delete root node which musn't have left son.
  999.              */
  1000.            
  1001.             t->root = expnode->rgt;
  1002.             if (expnode->rgt) expnode->rgt->par = NULL;
  1003.         } else if (expnode->rgt) {
  1004.             /*
  1005.              * Always delete parent of left son.
  1006.              */
  1007.            
  1008.             expnode->rgt->par = expnode->par;
  1009.             expnode->par->lft = expnode->rgt;
  1010.             expnode->par->lft_height = expnode->rgt_height;
  1011.         } else {
  1012.             /*
  1013.              * Deleted node doesn't have right son.
  1014.              */
  1015.            
  1016.             expnode->par->lft = NULL;
  1017.             expnode->par->lft_height = 0;
  1018.         }
  1019.         nextnode->key += expnode->key;
  1020.     } else {
  1021.         /*
  1022.          * Delete last node in tree.
  1023.          */
  1024.         t->root = NULL;
  1025.     }
  1026.  
  1027.     /*
  1028.      * Delete node from the list.
  1029.      */
  1030.     t->head.next = nextnode;
  1031.     nextnode->prev = &t->head;
  1032.    
  1033.     return true;
  1034. }
  1035.