Subversion Repositories HelenOS

Rev

Rev 2421 | Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2416 mencl 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) : max(((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 value 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;
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 = falsi;
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
    }
1021
 
1022
    /*
1023
     * Delete node from the list.
1024
     */
1025
    t->head.next = nextnode;
1026
    nextnode->prev = &t->head;
1027
 
1028
    return true;
1029
}