← Back to branch summary

~martin-decky/helenos/rcu

« back to all changes in this revision

Viewing changes to kernel/generic/src/adt/avl.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
kernel/generic/src/adt/avl.c
 
1
/*
 
2
 * Copyright (c) 2007 Vojtech Mencl
 
3
 * All rights reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 *
 
9
 * - Redistributions of source code must retain the above copyright
 
10
 *   notice, this list of conditions and the following disclaimer.
 
11
 * - Redistributions in binary form must reproduce the above copyright
 
12
 *   notice, this list of conditions and the following disclaimer in the
 
13
 *   documentation and/or other materials provided with the distribution.
 
14
 * - The name of the author may not be used to endorse or promote products
 
15
 *   derived from this software without specific prior written permission.
 
16
 *
 
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
27
 */
 
28
 
 
29
/** @addtogroup genericadt
 
30
 * @{
 
31
 */
 
32
 
 
33
/**
 
34
 * @file
 
35
 * @brief       AVL tree implementation.
 
36
 *
 
37
 * This file implements AVL tree type and operations.
 
38
 *
 
39
 * Implemented AVL tree has the following properties:
 
40
 * @li It is a binary search tree with non-unique keys.
 
41
 * @li Difference of heights of the left and the right subtree of every node is
 
42
 *     one at maximum.
 
43
 *
 
44
 * Every node has a pointer to its parent which allows insertion of multiple
 
45
 * identical keys into the tree.
 
46
 *
 
47
 * Be careful when using this tree because of the base atribute which is added
 
48
 * to every inserted node key. There is no rule in which order nodes with the
 
49
 * same key are visited.
 
50
 */
 
51
 
 
52
#include <adt/avl.h>
 
53
#include <debug.h>
 
54
 
 
55
#define LEFT    0
 
56
#define RIGHT   1
 
57
 
 
58
/** Search for the first occurence of the given key in an AVL tree.
 
59
 *
 
60
 * @param t AVL tree.
 
61
 * @param key Key to be searched.
 
62
 *
 
63
 * @return Pointer to a node or NULL if there is no such key.
 
64
 */
 
65
avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
 
66
{
 
67
        avltree_node_t *p;
 
68
        
 
69
        /*
 
70
         * Iteratively descend to the leaf that can contain the searched key.
 
71
         */
 
72
        p = t->root;
 
73
        while (p != NULL) {
 
74
                if (p->key > key)
 
75
                        p = p->lft;
 
76
                else if (p->key < key)
 
77
                        p = p->rgt;
 
78
                else 
 
79
                        return p;
 
80
        }
 
81
        return NULL;
 
82
}
 
83
 
 
84
 
 
85
/** Find the node with the smallest key in an AVL tree.
 
86
 *
 
87
 * @param t AVL tree.
 
88
 *
 
89
 * @return Pointer to a node or NULL if there is no node in the tree.
 
90
 */
 
91
avltree_node_t *avltree_find_min(avltree_t *t)
 
92
{
 
93
        avltree_node_t *p = t->root;
 
94
        
 
95
        /*
 
96
         * Check whether the tree is empty.
 
97
         */
 
98
        if (!p)
 
99
                return NULL;
 
100
        
 
101
        /*
 
102
         * Iteratively descend to the leftmost leaf in the tree.
 
103
         */
 
104
        while (p->lft != NULL) 
 
105
                p = p->lft;
 
106
        
 
107
        return p;
 
108
}
 
109
 
 
110
#define REBALANCE_INSERT_XX(DIR1, DIR2)         \
 
111
        top->DIR1 = par->DIR2;                  \
 
112
        if (top->DIR1 != NULL)                  \
 
113
                top->DIR1->par = top;           \
 
114
        par->par = top->par;                    \
 
115
        top->par = par;                         \
 
116
        par->DIR2 = top;                        \
 
117
        par->balance = 0;                       \
 
118
        top->balance = 0;                       \
 
119
        *dpc = par;
 
120
 
 
121
#define REBALANCE_INSERT_LL()           REBALANCE_INSERT_XX(lft, rgt)
 
122
#define REBALANCE_INSERT_RR()           REBALANCE_INSERT_XX(rgt, lft)
 
123
 
 
124
#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN)    \
 
125
        gpa = par->DIR2;                        \
 
126
        par->DIR2 = gpa->DIR1;                  \
 
127
        if (gpa->DIR1 != NULL)                  \
 
128
                gpa->DIR1->par = par;           \
 
129
        gpa->DIR1 = par;                        \
 
130
        par->par = gpa;                         \
 
131
        top->DIR1 = gpa->DIR2;                  \
 
132
        if (gpa->DIR2 != NULL)                  \
 
133
                gpa->DIR2->par = top;           \
 
134
        gpa->DIR2 = top;                        \
 
135
        gpa->par = top->par;                    \
 
136
        top->par = gpa;                         \
 
137
                                                \
 
138
        if (gpa->balance == -1 * SGN) {         \
 
139
                par->balance = 0;               \
 
140
                top->balance = 1 * SGN;         \
 
141
        } else if (gpa->balance == 0) {         \
 
142
                par->balance = 0;               \
 
143
                top->balance = 0;               \
 
144
        } else {                                \
 
145
                par->balance = -1 * SGN;        \
 
146
                top->balance = 0;               \
 
147
        }                                       \
 
148
        gpa->balance = 0;                       \
 
149
        *dpc = gpa;
 
150
 
 
151
#define REBALANCE_INSERT_LR()           REBALANCE_INSERT_XY(lft, rgt, 1)
 
152
#define REBALANCE_INSERT_RL()           REBALANCE_INSERT_XY(rgt, lft, -1)
 
153
        
 
154
/** Insert new node into AVL tree.
 
155
 *
 
156
 * @param t AVL tree.
 
157
 * @param newnode New node to be inserted.
 
158
 */ 
 
159
void avltree_insert(avltree_t *t, avltree_node_t *newnode)
 
160
{       
 
161
        avltree_node_t *par; 
 
162
        avltree_node_t *gpa;
 
163
        avltree_node_t *top;
 
164
        avltree_node_t **dpc;
 
165
        avltree_key_t key;
 
166
 
 
167
        ASSERT(t);
 
168
        ASSERT(newnode);
 
169
 
 
170
        /*
 
171
         * Creating absolute key.
 
172
         */     
 
173
        key = newnode->key + t->base;
 
174
        
 
175
        /*
 
176
         * Iteratively descend to the leaf that can contain the new node.
 
177
         * Last node with non-zero balance in the way to leaf is stored as top -
 
178
         * it is a place of possible inbalance.
 
179
         */
 
180
        dpc = &t->root;
 
181
        gpa = NULL;
 
182
        top = t->root;
 
183
        while ((par = (*dpc)) != NULL) {
 
184
                if (par->balance != 0) {
 
185
                        top = par;
 
186
                }
 
187
                gpa = par;
 
188
                dpc = par->key > key ? &par->lft: &par->rgt;
 
189
        }
 
190
 
 
191
        /*
 
192
         * Initialize the new node.
 
193
         */
 
194
        newnode->key = key;
 
195
        newnode->lft = NULL;
 
196
        newnode->rgt = NULL;
 
197
        newnode->par = gpa;
 
198
        newnode->balance = 0;
 
199
 
 
200
        /*
 
201
         * Insert first node into the empty tree.
 
202
         */
 
203
        if (t->root == NULL) {
 
204
                *dpc = newnode;
 
205
                return;
 
206
        }
 
207
 
 
208
        /*
 
209
         * Insert the new node into the previously found leaf position.
 
210
         */
 
211
        *dpc = newnode;
 
212
 
 
213
        /*
 
214
         * If the tree contains one node - end.
 
215
         */
 
216
        if (top == NULL)
 
217
                return;
 
218
 
 
219
        /*
 
220
         * Store pointer of top's father which points to the node with
 
221
         * potentially broken balance (top).
 
222
         */
 
223
        if (top->par == NULL) {
 
224
                dpc = &t->root;
 
225
        } else { 
 
226
                if (top->par->lft == top)
 
227
                        dpc = &top->par->lft;
 
228
                else
 
229
                        dpc = &top->par->rgt;
 
230
        }
 
231
 
 
232
        /*
 
233
         * Repair all balances on the way from top node to the newly inserted
 
234
         * node.
 
235
         */
 
236
        par = top;
 
237
        while (par != newnode) {
 
238
                if (par->key > key) {
 
239
                        par->balance--;
 
240
                        par = par->lft;
 
241
                } else {
 
242
                        par->balance++;
 
243
                        par = par->rgt;
 
244
                }
 
245
        }
 
246
        
 
247
        /*
 
248
         * To balance the tree, we must check and balance top node.
 
249
         */
 
250
        if (top->balance == -2) {
 
251
                par = top->lft;
 
252
                if (par->balance == -1) {
 
253
                        /*
 
254
                         * LL rotation.
 
255
                         */
 
256
                        REBALANCE_INSERT_LL();
 
257
                } else { 
 
258
                        /*
 
259
                         * LR rotation.
 
260
                         */
 
261
                        ASSERT(par->balance == 1);
 
262
                        
 
263
                        REBALANCE_INSERT_LR();
 
264
                }
 
265
        } else if (top->balance == 2) { 
 
266
                par = top->rgt;
 
267
                if (par->balance == 1) {
 
268
                        /*
 
269
                         * RR rotation.
 
270
                         */
 
271
                        REBALANCE_INSERT_RR();
 
272
                } else {
 
273
                        /*
 
274
                         * RL rotation.
 
275
                         */
 
276
                        ASSERT(par->balance == -1);
 
277
                
 
278
                        REBALANCE_INSERT_RL();
 
279
                }
 
280
        } else { 
 
281
                /*
 
282
                 * Balance is not broken, insertion is finised.
 
283
                 */
 
284
                return;
 
285
        }
 
286
 
 
287
}
 
288
 
 
289
/** Repair the tree after reparenting node u.
 
290
 *
 
291
 * If node u has no parent, mark it as the root of the whole tree. Otherwise
 
292
 * node v represents stale address of one of the children of node u's parent.
 
293
 * Replace v with w as node u parent's child (for most uses, u and w will be the
 
294
 * same).
 
295
 *
 
296
 * @param t     AVL tree.
 
297
 * @param u     Node whose new parent has a stale child pointer.
 
298
 * @param v     Stale child of node u's new parent.
 
299
 * @param w     New child of node u's new parent.
 
300
 * @param dir   If not NULL, address of the variable where to store information
 
301
 *              about whether w replaced v in the left or the right subtree of
 
302
 *              u's new parent.
 
303
 * @param ro    Read only operation; do not modify any tree pointers. This is
 
304
 *              useful for tracking direction via the dir pointer.
 
305
 * 
 
306
 * @return      Zero if w became the new root of the tree, otherwise return
 
307
 *              non-zero.
 
308
 */
 
309
static int
 
310
repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
 
311
    int *dir, int ro)
 
312
{
 
313
        if (u->par == NULL) {
 
314
                if (!ro)
 
315
                        t->root = w;    
 
316
                return 0;
 
317
        } else {        
 
318
                if (u->par->lft == v) {
 
319
                        if (!ro)
 
320
                                u->par->lft = w;
 
321
                        if (dir)
 
322
                                *dir = LEFT;
 
323
                } else {
 
324
                        ASSERT(u->par->rgt == v);
 
325
                        if (!ro)
 
326
                                u->par->rgt = w;
 
327
                        if (dir)
 
328
                                *dir = RIGHT;
 
329
                }
 
330
        }
 
331
        return 1;
 
332
}
 
333
 
 
334
#define REBALANCE_DELETE(DIR1, DIR2, SIGN)      \
 
335
        if (cur->balance == -1 * SIGN) {        \
 
336
                par->balance = 0;               \
 
337
                gpa->balance = 1 * SIGN;        \
 
338
                if (gpa->DIR1)                  \
 
339
                        gpa->DIR1->par = gpa;   \
 
340
                par->DIR2->par = par;           \
 
341
        } else if (cur->balance == 0) {         \
 
342
                par->balance = 0;               \
 
343
                gpa->balance = 0;               \
 
344
                if (gpa->DIR1)                  \
 
345
                        gpa->DIR1->par = gpa;   \
 
346
                if (par->DIR2)                  \
 
347
                        par->DIR2->par = par;   \
 
348
        } else {                                \
 
349
                par->balance = -1 * SIGN;       \
 
350
                gpa->balance = 0;               \
 
351
                if (par->DIR2)                  \
 
352
                        par->DIR2->par = par;   \
 
353
                gpa->DIR1->par = gpa;           \
 
354
        }                                       \
 
355
        cur->balance = 0;
 
356
 
 
357
#define REBALANCE_DELETE_LR()           REBALANCE_DELETE(lft, rgt, 1)
 
358
#define REBALANCE_DELETE_RL()           REBALANCE_DELETE(rgt, lft, -1)
 
359
 
 
360
/** Delete a node from the AVL tree.
 
361
 *
 
362
 * Because multiple identical keys are allowed, the parent pointers are
 
363
 * essential during deletion.
 
364
 * 
 
365
 * @param t AVL tree structure.
 
366
 * @param node Address of the node which will be deleted.
 
367
 */
 
368
void avltree_delete(avltree_t *t, avltree_node_t *node)
 
369
{
 
370
        avltree_node_t *cur;
 
371
        avltree_node_t *par;
 
372
        avltree_node_t *gpa;
 
373
        int dir;
 
374
 
 
375
        ASSERT(t);
 
376
        ASSERT(node);
 
377
        
 
378
        if (node->lft == NULL) {
 
379
                if (node->rgt) {
 
380
                        /*
 
381
                         * Replace the node with its only right son. 
 
382
                         *
 
383
                         * Balance of the right son will be repaired in the
 
384
                         * balancing cycle.
 
385
                         */
 
386
                        cur = node->rgt;
 
387
                        cur->par = node->par;
 
388
                        gpa = cur;
 
389
                        dir = RIGHT;
 
390
                        cur->balance = node->balance; 
 
391
                } else {
 
392
                        if (node->par == NULL) {
 
393
                                /*
 
394
                                 * The tree has only one node - it will become
 
395
                                 * an empty tree and the balancing can end.
 
396
                                 */
 
397
                                t->root = NULL;
 
398
                                return;
 
399
                        }
 
400
                        /*
 
401
                         * The node has no child, it will be deleted with no
 
402
                         * substitution.
 
403
                         */
 
404
                        gpa = node->par;
 
405
                        cur = NULL;
 
406
                        dir = (gpa->lft == node) ? LEFT: RIGHT;
 
407
                }
 
408
        } else {
 
409
                /*
 
410
                 * The node has the left son. Find a node with the smallest key
 
411
                 * in the left subtree and replace the deleted node with that
 
412
                 * node.
 
413
                 */
 
414
                for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
 
415
                        ;
 
416
 
 
417
                if (cur != node->lft) {
 
418
                        /*
 
419
                         * The rightmost node of the deleted node's left subtree
 
420
                         * was found. Replace the deleted node with this node.
 
421
                         * Cutting off of the found node has two cases that
 
422
                         * depend on its left son.
 
423
                         */ 
 
424
                        if (cur->lft) {
 
425
                                /*
 
426
                                 * The found node has a left son.
 
427
                                 */
 
428
                                gpa = cur->lft;
 
429
                                gpa->par = cur->par;
 
430
                                dir = LEFT;
 
431
                                gpa->balance = cur->balance; 
 
432
                        } else {
 
433
                                dir = RIGHT;
 
434
                                gpa = cur->par;
 
435
                        }
 
436
                        cur->par->rgt = cur->lft;
 
437
                        cur->lft = node->lft;
 
438
                        cur->lft->par = cur; 
 
439
                } else { 
 
440
                        /*
 
441
                         * The left son of the node hasn't got a right son. The
 
442
                         * left son will take the deleted node's place.
 
443
                         */
 
444
                        dir = LEFT;
 
445
                        gpa = cur; 
 
446
                }
 
447
                if (node->rgt)
 
448
                        node->rgt->par = cur; 
 
449
                cur->rgt = node->rgt;
 
450
                cur->balance = node->balance;
 
451
                cur->par = node->par;
 
452
        }
 
453
        
 
454
        /*
 
455
         * Repair the parent node's pointer which pointed previously to the
 
456
         * deleted node.
 
457
         */
 
458
        (void) repair(t, node, node, cur, NULL, false);
 
459
        
 
460
        /*
 
461
         * Repair cycle which repairs balances of nodes on the way from from the
 
462
         * cut-off node up to the root.
 
463
         */
 
464
        for (;;) {
 
465
                if (dir == LEFT) {
 
466
                        /*
 
467
                         * Deletion was made in the left subtree.
 
468
                         */
 
469
                        gpa->balance++;
 
470
                        if (gpa->balance == 1) {
 
471
                                /*
 
472
                                 * Stop balancing, the tree is balanced.
 
473
                                 */
 
474
                                break;
 
475
                        } else if (gpa->balance == 2) { 
 
476
                                /*
 
477
                                 * Bad balance, heights of left and right
 
478
                                 * subtrees differ more than by one.
 
479
                                 */
 
480
                                par = gpa->rgt;
 
481
 
 
482
                                if (par->balance == -1) {
 
483
                                        /*
 
484
                                         * RL rotation.
 
485
                                         */
 
486
                                        
 
487
                                        cur = par->lft;
 
488
                                        par->lft = cur->rgt;
 
489
                                        cur->rgt = par;
 
490
                                        gpa->rgt = cur->lft;
 
491
                                        cur->lft = gpa;
 
492
                                        
 
493
                                        /*
 
494
                                         * Repair balances and paternity of
 
495
                                         * children, depending on the balance
 
496
                                         * factor of the grand child (cur).
 
497
                                         */
 
498
                                        REBALANCE_DELETE_RL();
 
499
                                        
 
500
                                        /*
 
501
                                         * Repair paternity.
 
502
                                         */
 
503
                                        cur->par = gpa->par;
 
504
                                        gpa->par = cur;
 
505
                                        par->par = cur;
 
506
 
 
507
                                        if (!repair(t, cur, gpa, cur, &dir,
 
508
                                            false))
 
509
                                                break;
 
510
                                        gpa = cur->par;
 
511
                                } else {
 
512
                                        /*
 
513
                                         * RR rotation.
 
514
                                         */
 
515
                                        
 
516
                                        gpa->rgt = par->lft;
 
517
                                        if (par->lft)
 
518
                                                par->lft->par = gpa;
 
519
                                        par->lft = gpa;
 
520
                                        
 
521
                                        /*
 
522
                                         * Repair paternity.
 
523
                                         */
 
524
                                        par->par = gpa->par;
 
525
                                        gpa->par = par;
 
526
                                        
 
527
                                        if (par->balance == 0) {
 
528
                                                /*
 
529
                                                 * The right child of the
 
530
                                                 * balanced node is balanced,
 
531
                                                 * after RR rotation is done,
 
532
                                                 * the whole tree will be
 
533
                                                 * balanced.
 
534
                                                 */
 
535
                                                par->balance = -1;
 
536
                                                gpa->balance = 1;
 
537
 
 
538
                                                (void) repair(t, par, gpa, par,
 
539
                                                    NULL, false);
 
540
                                                break; 
 
541
                                        } else {
 
542
                                                par->balance = 0;
 
543
                                                gpa->balance = 0;
 
544
                                                if (!repair(t, par, gpa, par,
 
545
                                                    &dir, false))
 
546
                                                        break;
 
547
                                        }
 
548
                                        gpa = par->par;
 
549
                                }
 
550
                        } else {
 
551
                                /*
 
552
                                 * Repair the pointer which pointed to the
 
553
                                 * balanced node. If it was root then balancing
 
554
                                 * is finished else continue with the next
 
555
                                 * iteration (parent node).
 
556
                                 */
 
557
                                if (!repair(t, gpa, gpa, NULL, &dir, true))
 
558
                                        break;
 
559
                                gpa = gpa->par;
 
560
                        }
 
561
                } else { 
 
562
                        /*
 
563
                         * Deletion was made in the right subtree.
 
564
                         */
 
565
                        gpa->balance--;
 
566
                        if (gpa->balance == -1) {
 
567
                                /*
 
568
                                 * Stop balancing, the tree is balanced.
 
569
                                 */
 
570
                                break;
 
571
                        } else if (gpa->balance == -2) {
 
572
                                /*
 
573
                                 * Bad balance, heights of left and right
 
574
                                 * subtrees differ more than by one.
 
575
                                 */
 
576
                                par = gpa->lft;
 
577
                                
 
578
                                if (par->balance == 1) {
 
579
                                        /*
 
580
                                         * LR rotation.
 
581
                                         */
 
582
                                        
 
583
                                        cur = par->rgt;
 
584
                                        par->rgt = cur->lft;
 
585
                                        cur->lft = par;
 
586
                                        gpa->lft = cur->rgt;
 
587
                                        cur->rgt = gpa;
 
588
                                        
 
589
                                        /*
 
590
                                         * Repair balances and paternity of
 
591
                                         * children, depending on the balance
 
592
                                         * factor of the grand child (cur).
 
593
                                         */
 
594
                                        REBALANCE_DELETE_LR();
 
595
 
 
596
                                        /*
 
597
                                         * Repair paternity.
 
598
                                         */
 
599
                                        cur->par = gpa->par;
 
600
                                        gpa->par = cur;
 
601
                                        par->par = cur;
 
602
 
 
603
                                        if (!repair(t, cur, gpa, cur, &dir,
 
604
                                            false))
 
605
                                                break;
 
606
                                        gpa = cur->par;
 
607
                                } else { 
 
608
                                        /*
 
609
                                         * LL rotation.
 
610
                                         */
 
611
 
 
612
                                        gpa->lft = par->rgt;
 
613
                                        if (par->rgt)
 
614
                                                par->rgt->par = gpa;
 
615
                                        par->rgt = gpa;
 
616
                                        /*
 
617
                                         * Repair paternity.
 
618
                                         */
 
619
                                        par->par = gpa->par;
 
620
                                        gpa->par = par;
 
621
                                        
 
622
                                        if (par->balance == 0) {
 
623
                                                /*
 
624
                                                 * The left child of the
 
625
                                                 * balanced node is balanced,
 
626
                                                 * after LL rotation is done,
 
627
                                                 * the whole tree will be
 
628
                                                 * balanced.
 
629
                                                 */
 
630
                                                par->balance = 1;
 
631
                                                gpa->balance = -1;
 
632
                                                
 
633
                                                (void) repair(t, par, gpa, par,
 
634
                                                    NULL, false);
 
635
                                                break;
 
636
                                        } else {
 
637
                                                par->balance = 0;
 
638
                                                gpa->balance = 0;
 
639
                                                
 
640
                                                if (!repair(t, par, gpa, par,
 
641
                                                    &dir, false))
 
642
                                                        break;
 
643
                                        }
 
644
                                        gpa = par->par;
 
645
                                }
 
646
                        } else {
 
647
                                /*
 
648
                                 * Repair the pointer which pointed to the
 
649
                                 * balanced node. If it was root then balancing
 
650
                                 * is finished. Otherwise continue with the next
 
651
                                 * iteration (parent node).
 
652
                                 */
 
653
                                if (!repair(t, gpa, gpa, NULL, &dir, true))
 
654
                                        break;
 
655
                                gpa = gpa->par;
 
656
                        }
 
657
                }
 
658
        }
 
659
}
 
660
 
 
661
 
 
662
/** Delete a node with the smallest key from the AVL tree.
 
663
 *
 
664
 * @param t AVL tree structure.
 
665
 */
 
666
bool avltree_delete_min(avltree_t *t)
 
667
{
 
668
        avltree_node_t *node;
 
669
        
 
670
        /*
 
671
         * Start searching for the smallest key in the tree starting in the root
 
672
         * node and continue in cycle to the leftmost node in the tree (which
 
673
         * must have the smallest key).
 
674
         */
 
675
         
 
676
        node = t->root;
 
677
        if (!node)
 
678
                return false;
 
679
        
 
680
        while (node->lft != NULL)
 
681
                node = node->lft;
 
682
        
 
683
        avltree_delete(t, node); 
 
684
 
 
685
        return true;
 
686
}
 
687
 
 
688
/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
 
689
 * visited node.
 
690
 *
 
691
 * @param node          Node representing the root of an AVL subtree to be
 
692
 *                      walked.
 
693
 * @param walker        Walker function that will be appliad on each visited
 
694
 *                      node.
 
695
 * @param arg           Argument for the walker.
 
696
 *
 
697
 * @return              Zero if the walk should stop or non-zero otherwise.
 
698
 */
 
699
static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
 
700
    void *arg)
 
701
{
 
702
        if (node->lft) {
 
703
                if (!_avltree_walk(node->lft, walker, arg))
 
704
                        return false;
 
705
        }
 
706
        if (!walker(node, arg))
 
707
                return false;
 
708
        if (node->rgt) {
 
709
                if (!_avltree_walk(node->rgt, walker, arg))
 
710
                        return false;
 
711
        }
 
712
        return true;
 
713
}
 
714
 
 
715
/** Walk the AVL tree in-order and apply the walker function on each visited
 
716
 * node.
 
717
 *
 
718
 * @param t             AVL tree to be walked.
 
719
 * @param walker        Walker function that will be called on each visited
 
720
 *                      node.
 
721
 * @param arg           Argument for the walker.
 
722
 */
 
723
void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
 
724
{
 
725
        _avltree_walk(t->root, walker, arg);
 
726
}
 
727
 
 
728
/** @}
 
729
 */
 
730