Subversion Repositories HelenOS

Rev

Rev 3386 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2416 mencl 1
/*
2421 mencl 2
 * Copyright (c) 2007 Vojtech Mencl
2416 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:
2496 jermar 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.
2416 mencl 43
 *
2496 jermar 44
 * Every node has a pointer to its parent which allows insertion of multiple
45
 * identical keys into the tree.
4153 mejdrech 46
 *
2496 jermar 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.
2416 mencl 50
 */
51
 
52
#include <adt/avl.h>
53
#include <debug.h>
54
 
2496 jermar 55
#define LEFT    0
56
#define RIGHT   1
2416 mencl 57
 
2496 jermar 58
/** Search for the first occurence of the given key in an AVL tree.
2416 mencl 59
 *
60
 * @param t AVL tree.
61
 * @param key Key to be searched.
62
 *
2496 jermar 63
 * @return Pointer to a node or NULL if there is no such key.
2416 mencl 64
 */
2501 jermar 65
avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
2416 mencl 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;
2496 jermar 78
        else
2416 mencl 79
            return p;
80
    }
81
    return NULL;
82
}
83
 
84
 
2496 jermar 85
/** Find the node with the smallest key in an AVL tree.
2421 mencl 86
 *
87
 * @param t AVL tree.
88
 *
2496 jermar 89
 * @return Pointer to a node or NULL if there is no node in the tree.
2421 mencl 90
 */
91
avltree_node_t *avltree_find_min(avltree_t *t)
92
{
93
    avltree_node_t *p = t->root;
94
 
95
    /*
2496 jermar 96
     * Check whether the tree is empty.
2421 mencl 97
     */
2496 jermar 98
    if (!p)
99
        return NULL;
2421 mencl 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
 
2503 jermar 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
 
2416 mencl 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;
2501 jermar 165
    avltree_key_t key;
2416 mencl 166
 
167
    ASSERT(t);
168
    ASSERT(newnode);
169
 
170
    /*
171
     * Creating absolute key.
172
     */
173
    key = newnode->key + t->base;
174
 
175
    /*
2496 jermar 176
     * Iteratively descend to the leaf that can contain the new node.
2416 mencl 177
     * Last node with non-zero balance in the way to leaf is stored as top -
2496 jermar 178
     * it is a place of possible inbalance.
2416 mencl 179
     */
180
    dpc = &t->root;
181
    gpa = NULL;
182
    top = t->root;
2421 mencl 183
    while ((par = (*dpc)) != NULL) {
2416 mencl 184
        if (par->balance != 0) {
185
            top = par;
186
        }
187
        gpa = par;
2496 jermar 188
        dpc = par->key > key ? &par->lft: &par->rgt;
2416 mencl 189
    }
190
 
191
    /*
2503 jermar 192
     * Initialize the new node.
2416 mencl 193
     */
194
    newnode->key = key;
195
    newnode->lft = NULL;
196
    newnode->rgt = NULL;
197
    newnode->par = gpa;
198
    newnode->balance = 0;
199
 
200
    /*
2496 jermar 201
     * Insert first node into the empty tree.
2416 mencl 202
     */
203
    if (t->root == NULL) {
204
        *dpc = newnode;
205
        return;
206
    }
207
 
208
    /*
2503 jermar 209
     * Insert the new node into the previously found leaf position.
2416 mencl 210
     */
211
    *dpc = newnode;
212
 
213
    /*
2496 jermar 214
     * If the tree contains one node - end.
2416 mencl 215
     */
2496 jermar 216
    if (top == NULL)
217
        return;
2416 mencl 218
 
219
    /*
2496 jermar 220
     * Store pointer of top's father which points to the node with
221
     * potentially broken balance (top).
2416 mencl 222
     */
2496 jermar 223
    if (top->par == NULL) {
2416 mencl 224
        dpc = &t->root;
2496 jermar 225
    } else {
2416 mencl 226
        if (top->par->lft == top)
2496 jermar 227
            dpc = &top->par->lft;
2416 mencl 228
        else
2496 jermar 229
            dpc = &top->par->rgt;
230
    }
2416 mencl 231
 
232
    /*
2496 jermar 233
     * Repair all balances on the way from top node to the newly inserted
234
     * node.
2416 mencl 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
    /*
2496 jermar 248
     * To balance the tree, we must check and balance top node.
2416 mencl 249
     */
250
    if (top->balance == -2) {
251
        par = top->lft;
252
        if (par->balance == -1) {
253
            /*
254
             * LL rotation.
255
             */
2503 jermar 256
            REBALANCE_INSERT_LL();
2416 mencl 257
        } else {
258
            /*
259
             * LR rotation.
260
             */
261
            ASSERT(par->balance == 1);
262
 
2503 jermar 263
            REBALANCE_INSERT_LR();
2416 mencl 264
        }
265
    } else if (top->balance == 2) {
266
        par = top->rgt;
267
        if (par->balance == 1) {
268
            /*
269
             * RR rotation.
270
             */
2503 jermar 271
            REBALANCE_INSERT_RR();
2416 mencl 272
        } else {
273
            /*
274
             * RL rotation.
275
             */
276
            ASSERT(par->balance == -1);
2503 jermar 277
 
278
            REBALANCE_INSERT_RL();
2416 mencl 279
        }
280
    } else {
281
        /*
282
         * Balance is not broken, insertion is finised.
283
         */
284
        return;
285
    }
286
 
287
}
288
 
2497 jermar 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
 
2503 jermar 334
#define REBALANCE_DELETE(DIR1, DIR2, SIGN)  \
2497 jermar 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
 
2503 jermar 357
#define REBALANCE_DELETE_LR()       REBALANCE_DELETE(lft, rgt, 1)
358
#define REBALANCE_DELETE_RL()       REBALANCE_DELETE(rgt, lft, -1)
2497 jermar 359
 
2496 jermar 360
/** Delete a node from the AVL tree.
2416 mencl 361
 *
2496 jermar 362
 * Because multiple identical keys are allowed, the parent pointers are
363
 * essential during deletion.
2416 mencl 364
 *
365
 * @param t AVL tree structure.
2496 jermar 366
 * @param node Address of the node which will be deleted.
2416 mencl 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;
2497 jermar 373
    int dir;
2416 mencl 374
 
375
    ASSERT(t);
376
    ASSERT(node);
377
 
2497 jermar 378
    if (node->lft == NULL) {
2416 mencl 379
        if (node->rgt) {
380
            /*
2496 jermar 381
             * Replace the node with its only right son.
2416 mencl 382
             *
2496 jermar 383
             * Balance of the right son will be repaired in the
384
             * balancing cycle.
2416 mencl 385
             */
386
            cur = node->rgt;
387
            cur->par = node->par;
388
            gpa = cur;
2496 jermar 389
            dir = RIGHT;
2416 mencl 390
            cur->balance = node->balance;
391
        } else {
392
            if (node->par == NULL) {
393
                /*
2496 jermar 394
                 * The tree has only one node - it will become
395
                 * an empty tree and the balancing can end.
2416 mencl 396
                 */
397
                t->root = NULL;
398
                return;
399
            }
400
            /*
2496 jermar 401
             * The node has no child, it will be deleted with no
402
             * substitution.
2416 mencl 403
             */
404
            gpa = node->par;
405
            cur = NULL;
2496 jermar 406
            dir = (gpa->lft == node) ? LEFT: RIGHT;
2416 mencl 407
        }
408
    } else {
409
        /*
2497 jermar 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.
2416 mencl 413
         */
414
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
415
            ;
2496 jermar 416
 
2416 mencl 417
        if (cur != node->lft) {
418
            /*
2496 jermar 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.
2416 mencl 423
             */
424
            if (cur->lft) {
425
                /*
2496 jermar 426
                 * The found node has a left son.
2416 mencl 427
                 */
428
                gpa = cur->lft;
429
                gpa->par = cur->par;
2496 jermar 430
                dir = LEFT;
2416 mencl 431
                gpa->balance = cur->balance;
432
            } else {
2496 jermar 433
                dir = RIGHT;
2416 mencl 434
                gpa = cur->par;
435
            }
436
            cur->par->rgt = cur->lft;
437
            cur->lft = node->lft;
438
            cur->lft->par = cur;
439
        } else {
440
            /*
2496 jermar 441
             * The left son of the node hasn't got a right son. The
442
             * left son will take the deleted node's place.
2416 mencl 443
             */
2496 jermar 444
            dir = LEFT;
2416 mencl 445
            gpa = cur;
446
        }
2496 jermar 447
        if (node->rgt)
448
            node->rgt->par = cur;
2416 mencl 449
        cur->rgt = node->rgt;
450
        cur->balance = node->balance;
451
        cur->par = node->par;
452
    }
453
 
454
    /*
2496 jermar 455
     * Repair the parent node's pointer which pointed previously to the
456
     * deleted node.
2416 mencl 457
     */
2497 jermar 458
    (void) repair(t, node, node, cur, NULL, false);
2416 mencl 459
 
460
    /*
2496 jermar 461
     * Repair cycle which repairs balances of nodes on the way from from the
462
     * cut-off node up to the root.
2416 mencl 463
     */
2496 jermar 464
    for (;;) {
465
        if (dir == LEFT) {
2416 mencl 466
            /*
2496 jermar 467
             * Deletion was made in the left subtree.
2416 mencl 468
             */
469
            gpa->balance++;
2496 jermar 470
            if (gpa->balance == 1) {
2416 mencl 471
                /*
2496 jermar 472
                 * Stop balancing, the tree is balanced.
2416 mencl 473
                 */
474
                break;
2496 jermar 475
            } else if (gpa->balance == 2) {
2416 mencl 476
                /*
2496 jermar 477
                 * Bad balance, heights of left and right
478
                 * subtrees differ more than by one.
2416 mencl 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
                    /*
2496 jermar 494
                     * Repair balances and paternity of
495
                     * children, depending on the balance
496
                     * factor of the grand child (cur).
2416 mencl 497
                     */
2503 jermar 498
                    REBALANCE_DELETE_RL();
2416 mencl 499
 
500
                    /*
501
                     * Repair paternity.
502
                     */
503
                    cur->par = gpa->par;
504
                    gpa->par = cur;
505
                    par->par = cur;
506
 
2497 jermar 507
                    if (!repair(t, cur, gpa, cur, &dir,
508
                        false))
2416 mencl 509
                        break;
510
                    gpa = cur->par;
511
                } else {
512
                    /*
513
                     * RR rotation.
514
                     */
515
 
516
                    gpa->rgt = par->lft;
2496 jermar 517
                    if (par->lft)
518
                        par->lft->par = gpa;
2416 mencl 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
                        /*
2496 jermar 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.
2416 mencl 534
                         */
535
                        par->balance = -1;
2496 jermar 536
                        gpa->balance = 1;
2416 mencl 537
 
2497 jermar 538
                        (void) repair(t, par, gpa, par,
539
                            NULL, false);
2416 mencl 540
                        break;
541
                    } else {
2497 jermar 542
                        par->balance = 0;
543
                        gpa->balance = 0;
544
                        if (!repair(t, par, gpa, par,
545
                            &dir, false))
2416 mencl 546
                            break;
547
                    }
548
                    gpa = par->par;
549
                }
550
            } else {
551
                /*
2496 jermar 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).
2416 mencl 556
                 */
2497 jermar 557
                if (!repair(t, gpa, gpa, NULL, &dir, true))
2496 jermar 558
                    break;
2416 mencl 559
                gpa = gpa->par;
560
            }
561
        } else {
562
            /*
2496 jermar 563
             * Deletion was made in the right subtree.
2416 mencl 564
             */
565
            gpa->balance--;
566
            if (gpa->balance == -1) {
567
                /*
2496 jermar 568
                 * Stop balancing, the tree is balanced.
2416 mencl 569
                 */
570
                break;
571
            } else if (gpa->balance == -2) {
572
                /*
2496 jermar 573
                 * Bad balance, heights of left and right
574
                 * subtrees differ more than by one.
2416 mencl 575
                 */
576
                par = gpa->lft;
577
 
2496 jermar 578
                if (par->balance == 1) {
2416 mencl 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
                    /*
2496 jermar 590
                     * Repair balances and paternity of
591
                     * children, depending on the balance
592
                     * factor of the grand child (cur).
2416 mencl 593
                     */
2503 jermar 594
                    REBALANCE_DELETE_LR();
2416 mencl 595
 
596
                    /*
597
                     * Repair paternity.
598
                     */
599
                    cur->par = gpa->par;
600
                    gpa->par = cur;
601
                    par->par = cur;
602
 
2497 jermar 603
                    if (!repair(t, cur, gpa, cur, &dir,
604
                        false))
605
                        break;
2416 mencl 606
                    gpa = cur->par;
607
                } else {
608
                    /*
609
                     * LL rotation.
610
                     */
2497 jermar 611
 
2416 mencl 612
                    gpa->lft = par->rgt;
2496 jermar 613
                    if (par->rgt)
614
                        par->rgt->par = gpa;
2416 mencl 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
                        /*
2496 jermar 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.
2416 mencl 629
                         */
2496 jermar 630
                        par->balance = 1;
2416 mencl 631
                        gpa->balance = -1;
632
 
2497 jermar 633
                        (void) repair(t, par, gpa, par,
634
                            NULL, false);
2416 mencl 635
                        break;
636
                    } else {
2497 jermar 637
                        par->balance = 0;
638
                        gpa->balance = 0;
2416 mencl 639
 
2497 jermar 640
                        if (!repair(t, par, gpa, par,
641
                            &dir, false))
2416 mencl 642
                            break;
643
                    }
644
                    gpa = par->par;
645
                }
646
            } else {
647
                /*
2496 jermar 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).
2416 mencl 652
                 */
2497 jermar 653
                if (!repair(t, gpa, gpa, NULL, &dir, true))
2496 jermar 654
                    break;
2416 mencl 655
                gpa = gpa->par;
656
            }
657
        }
658
    }
659
}
660
 
661
 
2496 jermar 662
/** Delete a node with the smallest key from the AVL tree.
2416 mencl 663
 *
664
 * @param t AVL tree structure.
665
 */
2421 mencl 666
bool avltree_delete_min(avltree_t *t)
2416 mencl 667
{
668
    avltree_node_t *node;
669
 
670
    /*
2496 jermar 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).
2416 mencl 674
     */
2496 jermar 675
 
2416 mencl 676
    node = t->root;
2496 jermar 677
    if (!node)
678
        return false;
2416 mencl 679
 
680
    while (node->lft != NULL)
681
        node = node->lft;
682
 
2496 jermar 683
    avltree_delete(t, node);
2416 mencl 684
 
685
    return true;
686
}
2496 jermar 687
 
2504 jermar 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)
2501 jermar 701
{
2504 jermar 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;
2501 jermar 713
}
714
 
2504 jermar 715
/** Walk the AVL tree in-order and apply the walker function on each visited
716
 * node.
2501 jermar 717
 *
718
 * @param t     AVL tree to be walked.
719
 * @param walker    Walker function that will be called on each visited
720
 *          node.
2504 jermar 721
 * @param arg       Argument for the walker.
2501 jermar 722
 */
2504 jermar 723
void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
2501 jermar 724
{
2504 jermar 725
    _avltree_walk(t->root, walker, arg);
2501 jermar 726
}
727
 
2496 jermar 728
/** @}
729
 */
2497 jermar 730