Subversion Repositories HelenOS

Rev

Rev 2421 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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