Subversion Repositories HelenOS

Rev

Rev 2496 | Rev 2499 | Go to most recent revision | 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.
2416 mencl 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
 
55
 
2496 jermar 56
#define LEFT    0
57
#define RIGHT   1
2416 mencl 58
 
59
 
2496 jermar 60
/** Search for the first occurence of the given key in an AVL tree.
2416 mencl 61
 *
62
 * @param t AVL tree.
63
 * @param key Key to be searched.
64
 *
2496 jermar 65
 * @return Pointer to a node or NULL if there is no such key.
2416 mencl 66
 */
67
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
68
{
69
    avltree_node_t *p;
70
 
71
    /*
72
     * Iteratively descend to the leaf that can contain the searched key.
73
     */
74
    p = t->root;
75
    while (p != NULL) {
76
        if (p->key > key)
77
            p = p->lft;
78
        else if (p->key < key)
79
            p = p->rgt;
2496 jermar 80
        else
2416 mencl 81
            return p;
82
    }
83
    return NULL;
84
}
85
 
86
 
2496 jermar 87
/** Find the node with the smallest key in an AVL tree.
2421 mencl 88
 *
89
 * @param t AVL tree.
90
 *
2496 jermar 91
 * @return Pointer to a node or NULL if there is no node in the tree.
2421 mencl 92
 */
93
avltree_node_t *avltree_find_min(avltree_t *t)
94
{
95
    avltree_node_t *p = t->root;
96
 
97
    /*
2496 jermar 98
     * Check whether the tree is empty.
2421 mencl 99
     */
2496 jermar 100
    if (!p)
101
        return NULL;
2421 mencl 102
 
103
    /*
104
     * Iteratively descend to the leftmost leaf in the tree.
105
     */
106
    while (p->lft != NULL)
107
        p = p->lft;
108
 
109
    return p;
110
}
111
 
2416 mencl 112
/** Insert new node into AVL tree.
113
 *
114
 * @param t AVL tree.
115
 * @param newnode New node to be inserted.
116
 */
117
void avltree_insert(avltree_t *t, avltree_node_t *newnode)
118
{  
119
    avltree_node_t *par;
120
    avltree_node_t *gpa;
121
    avltree_node_t *top;
122
    avltree_node_t **dpc;
123
    uint64_t key;
124
 
125
    ASSERT(t);
126
    ASSERT(newnode);
127
 
128
    /*
129
     * Creating absolute key.
130
     */
131
    key = newnode->key + t->base;
132
 
133
    /*
2496 jermar 134
     * Iteratively descend to the leaf that can contain the new node.
2416 mencl 135
     * Last node with non-zero balance in the way to leaf is stored as top -
2496 jermar 136
     * it is a place of possible inbalance.
2416 mencl 137
     */
138
    dpc = &t->root;
139
    gpa = NULL;
140
    top = t->root;
2421 mencl 141
    while ((par = (*dpc)) != NULL) {
2416 mencl 142
        if (par->balance != 0) {
143
            top = par;
144
        }
145
        gpa = par;
2496 jermar 146
        dpc = par->key > key ? &par->lft: &par->rgt;
2416 mencl 147
    }
148
 
149
    /*
150
     * Initialize new node.
151
     */
152
    newnode->key = key;
153
    newnode->lft = NULL;
154
    newnode->rgt = NULL;
155
    newnode->par = gpa;
156
    newnode->balance = 0;
157
 
158
    /*
2496 jermar 159
     * Insert first node into the empty tree.
2416 mencl 160
     */
161
    if (t->root == NULL) {
162
        *dpc = newnode;
163
        return;
164
    }
165
 
166
    /*
167
     * Insert new node into previously found leaf place.
168
     */
169
    *dpc = newnode;
170
 
171
    /*
2496 jermar 172
     * If the tree contains one node - end.
2416 mencl 173
     */
2496 jermar 174
    if (top == NULL)
175
        return;
2416 mencl 176
 
177
    /*
2496 jermar 178
     * Store pointer of top's father which points to the node with
179
     * potentially broken balance (top).
2416 mencl 180
     */
2496 jermar 181
    if (top->par == NULL) {
2416 mencl 182
        dpc = &t->root;
2496 jermar 183
    } else {
2416 mencl 184
        if (top->par->lft == top)
2496 jermar 185
            dpc = &top->par->lft;
2416 mencl 186
        else
2496 jermar 187
            dpc = &top->par->rgt;
188
    }
2416 mencl 189
 
190
    /*
2496 jermar 191
     * Repair all balances on the way from top node to the newly inserted
192
     * node.
2416 mencl 193
     */
194
    par = top;
195
    while (par != newnode) {
196
        if (par->key > key) {
197
            par->balance--;
198
            par = par->lft;
199
        } else {
200
            par->balance++;
201
            par = par->rgt;
202
        }
203
    }
204
 
205
    /*
2496 jermar 206
     * To balance the tree, we must check and balance top node.
2416 mencl 207
     */
208
    if (top->balance == -2) {
209
        par = top->lft;
210
        if (par->balance == -1) {
211
            /*
212
             * LL rotation.
213
             */
214
            top->lft = par->rgt;
2496 jermar 215
            if (top->lft != NULL)
216
                top->lft->par = top;
2416 mencl 217
            par->par = top->par;
218
            top->par = par;
219
            par->rgt = top;
2497 jermar 220
            par->balance = 0;
221
            top->balance = 0;
2416 mencl 222
            *dpc = par;
223
        } else {
224
            /*
225
             * LR rotation.
226
             */
227
            ASSERT(par->balance == 1);
228
 
229
            gpa = par->rgt;
230
            par->rgt = gpa->lft;
2496 jermar 231
            if (gpa->lft != NULL)
232
                gpa->lft->par = par;
2416 mencl 233
            gpa->lft = par;
234
            par->par = gpa;
235
            top->lft = gpa->rgt;
2496 jermar 236
            if (gpa->rgt != NULL)
237
                gpa->rgt->par = top;
2416 mencl 238
            gpa->rgt = top;
239
            gpa->par = top->par;
240
            top->par = gpa;
241
 
242
            if (gpa->balance == -1) {
243
                par->balance = 0;
244
                top->balance = 1;
245
            } else if (gpa->balance == 0) {
2497 jermar 246
                par->balance = 0;
247
                top->balance = 0;
2416 mencl 248
            } else {
249
                par->balance = -1;
250
                top->balance = 0;
251
            }
252
            gpa->balance = 0;
253
            *dpc = gpa;
254
        }
255
    } else if (top->balance == 2) {
256
        par = top->rgt;
257
        if (par->balance == 1) {
258
            /*
259
             * RR rotation.
260
             */
261
            top->rgt = par->lft;
2496 jermar 262
            if (top->rgt != NULL)
263
                top->rgt->par = top;
2416 mencl 264
            par->par = top->par;
265
            top->par = par;
266
            par->lft = top;
2497 jermar 267
            par->balance = 0;
268
            top->balance = 0;
2416 mencl 269
            *dpc = par;
270
        } else {
271
            /*
272
             * RL rotation.
273
             */
274
            ASSERT(par->balance == -1);
275
 
276
            gpa = par->lft;
277
            par->lft = gpa->rgt;
2496 jermar 278
            if (gpa->rgt != NULL)
279
                gpa->rgt->par = par;
2416 mencl 280
            gpa->rgt = par;
281
            par->par = gpa;
282
            top->rgt = gpa->lft;
2496 jermar 283
            if (gpa->lft != NULL)
284
                gpa->lft->par = top;
2416 mencl 285
            gpa->lft = top;
286
            gpa->par = top->par;
287
            top->par = gpa;
288
 
289
            if (gpa->balance == 1) {
290
                par->balance = 0;
291
                top->balance = -1;
292
            } else if (gpa->balance == 0) {
2497 jermar 293
                par->balance = 0;
294
                top->balance = 0;
2416 mencl 295
            } else {
296
                par->balance = 1;
297
                top->balance = 0;
298
            }
299
            gpa->balance = 0;
300
            *dpc = gpa;
301
        }
302
    } else {
303
        /*
304
         * Balance is not broken, insertion is finised.
305
         */
306
        return;
307
    }
308
 
309
}
310
 
2497 jermar 311
/** Repair the tree after reparenting node u.
312
 *
313
 * If node u has no parent, mark it as the root of the whole tree. Otherwise
314
 * node v represents stale address of one of the children of node u's parent.
315
 * Replace v with w as node u parent's child (for most uses, u and w will be the
316
 * same).
317
 *
318
 * @param t AVL tree.
319
 * @param u Node whose new parent has a stale child pointer.
320
 * @param v Stale child of node u's new parent.
321
 * @param w New child of node u's new parent.
322
 * @param dir   If not NULL, address of the variable where to store information
323
 *      about whether w replaced v in the left or the right subtree of
324
 *      u's new parent.
325
 * @param ro    Read only operation; do not modify any tree pointers. This is
326
 *      useful for tracking direction via the dir pointer.
327
 *
328
 * @return  Zero if w became the new root of the tree, otherwise return
329
 *      non-zero.
330
 */
331
static int
332
repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
333
    int *dir, int ro)
334
{
335
    if (u->par == NULL) {
336
        if (!ro)
337
            t->root = w;   
338
        return 0;
339
    } else {   
340
        if (u->par->lft == v) {
341
            if (!ro)
342
                u->par->lft = w;
343
            if (dir)
344
                *dir = LEFT;
345
        } else {
346
            ASSERT(u->par->rgt == v);
347
            if (!ro)
348
                u->par->rgt = w;
349
            if (dir)
350
                *dir = RIGHT;
351
        }
352
    }
353
    return 1;
354
}
355
 
356
#define REBALANCE(DIR1, DIR2, SIGN)     \
357
    if (cur->balance == -1 * SIGN) {    \
358
        par->balance = 0;       \
359
        gpa->balance = 1 * SIGN;    \
360
        if (gpa->DIR1)          \
361
            gpa->DIR1->par = gpa;   \
362
        par->DIR2->par = par;       \
363
    } else if (cur->balance == 0) {     \
364
        par->balance = 0;       \
365
        gpa->balance = 0;       \
366
        if (gpa->DIR1)          \
367
            gpa->DIR1->par = gpa;   \
368
        if (par->DIR2)          \
369
            par->DIR2->par = par;   \
370
    } else {                \
371
        par->balance = -1 * SIGN;   \
372
        gpa->balance = 0;       \
373
        if (par->DIR2)          \
374
            par->DIR2->par = par;   \
375
        gpa->DIR1->par = gpa;       \
376
    }                   \
377
    cur->balance = 0;
378
 
379
#define REBALANCE_LR()      REBALANCE(lft, rgt, 1)
380
#define REBALANCE_RL()      REBALANCE(rgt, lft, -1)
381
 
2496 jermar 382
/** Delete a node from the AVL tree.
2416 mencl 383
 *
2496 jermar 384
 * Because multiple identical keys are allowed, the parent pointers are
385
 * essential during deletion.
2416 mencl 386
 *
387
 * @param t AVL tree structure.
2496 jermar 388
 * @param node Address of the node which will be deleted.
2416 mencl 389
 */
390
void avltree_delete(avltree_t *t, avltree_node_t *node)
391
{
392
    avltree_node_t *cur;
393
    avltree_node_t *par;
394
    avltree_node_t *gpa;
2497 jermar 395
    int dir;
2416 mencl 396
 
397
    ASSERT(t);
398
    ASSERT(node);
399
 
2497 jermar 400
    if (node->lft == NULL) {
2416 mencl 401
        if (node->rgt) {
402
            /*
2496 jermar 403
             * Replace the node with its only right son.
2416 mencl 404
             *
2496 jermar 405
             * Balance of the right son will be repaired in the
406
             * balancing cycle.
2416 mencl 407
             */
408
            cur = node->rgt;
409
            cur->par = node->par;
410
            gpa = cur;
2496 jermar 411
            dir = RIGHT;
2416 mencl 412
            cur->balance = node->balance;
413
        } else {
414
            if (node->par == NULL) {
415
                /*
2496 jermar 416
                 * The tree has only one node - it will become
417
                 * an empty tree and the balancing can end.
2416 mencl 418
                 */
419
                t->root = NULL;
420
                return;
421
            }
422
            /*
2496 jermar 423
             * The node has no child, it will be deleted with no
424
             * substitution.
2416 mencl 425
             */
426
            gpa = node->par;
427
            cur = NULL;
2496 jermar 428
            dir = (gpa->lft == node) ? LEFT: RIGHT;
2416 mencl 429
        }
430
    } else {
431
        /*
2497 jermar 432
         * The node has the left son. Find a node with the smallest key
433
         * in the left subtree and replace the deleted node with that
434
         * node.
2416 mencl 435
         */
436
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
437
            ;
2496 jermar 438
 
2416 mencl 439
        if (cur != node->lft) {
440
            /*
2496 jermar 441
             * The rightmost node of the deleted node's left subtree
442
             * was found. Replace the deleted node with this node.
443
             * Cutting off of the found node has two cases that
444
             * depend on its left son.
2416 mencl 445
             */
446
            if (cur->lft) {
447
                /*
2496 jermar 448
                 * The found node has a left son.
2416 mencl 449
                 */
450
                gpa = cur->lft;
451
                gpa->par = cur->par;
2496 jermar 452
                dir = LEFT;
2416 mencl 453
                gpa->balance = cur->balance;
454
            } else {
2496 jermar 455
                dir = RIGHT;
2416 mencl 456
                gpa = cur->par;
457
            }
458
            cur->par->rgt = cur->lft;
459
            cur->lft = node->lft;
460
            cur->lft->par = cur;
461
        } else {
462
            /*
2496 jermar 463
             * The left son of the node hasn't got a right son. The
464
             * left son will take the deleted node's place.
2416 mencl 465
             */
2496 jermar 466
            dir = LEFT;
2416 mencl 467
            gpa = cur;
468
        }
2496 jermar 469
        if (node->rgt)
470
            node->rgt->par = cur;
2416 mencl 471
        cur->rgt = node->rgt;
472
        cur->balance = node->balance;
473
        cur->par = node->par;
474
    }
475
 
476
    /*
2496 jermar 477
     * Repair the parent node's pointer which pointed previously to the
478
     * deleted node.
2416 mencl 479
     */
2497 jermar 480
    (void) repair(t, node, node, cur, NULL, false);
2416 mencl 481
 
482
    /*
2496 jermar 483
     * Repair cycle which repairs balances of nodes on the way from from the
484
     * cut-off node up to the root.
2416 mencl 485
     */
2496 jermar 486
    for (;;) {
487
        if (dir == LEFT) {
2416 mencl 488
            /*
2496 jermar 489
             * Deletion was made in the left subtree.
2416 mencl 490
             */
491
            gpa->balance++;
2496 jermar 492
            if (gpa->balance == 1) {
2416 mencl 493
                /*
2496 jermar 494
                 * Stop balancing, the tree is balanced.
2416 mencl 495
                 */
496
                break;
2496 jermar 497
            } else if (gpa->balance == 2) {
2416 mencl 498
                /*
2496 jermar 499
                 * Bad balance, heights of left and right
500
                 * subtrees differ more than by one.
2416 mencl 501
                 */
502
                par = gpa->rgt;
503
 
504
                if (par->balance == -1) {
505
                    /*
506
                     * RL rotation.
507
                     */
508
 
509
                    cur = par->lft;
510
                    par->lft = cur->rgt;
511
                    cur->rgt = par;
512
                    gpa->rgt = cur->lft;
513
                    cur->lft = gpa;
514
 
515
                    /*
2496 jermar 516
                     * Repair balances and paternity of
517
                     * children, depending on the balance
518
                     * factor of the grand child (cur).
2416 mencl 519
                     */
2497 jermar 520
                    REBALANCE_RL();
2416 mencl 521
 
522
                    /*
523
                     * Repair paternity.
524
                     */
525
                    cur->par = gpa->par;
526
                    gpa->par = cur;
527
                    par->par = cur;
528
 
2497 jermar 529
                    if (!repair(t, cur, gpa, cur, &dir,
530
                        false))
2416 mencl 531
                        break;
532
                    gpa = cur->par;
533
                } else {
534
                    /*
535
                     * RR rotation.
536
                     */
537
 
538
                    gpa->rgt = par->lft;
2496 jermar 539
                    if (par->lft)
540
                        par->lft->par = gpa;
2416 mencl 541
                    par->lft = gpa;
542
 
543
                    /*
544
                     * Repair paternity.
545
                     */
546
                    par->par = gpa->par;
547
                    gpa->par = par;
548
 
549
                    if (par->balance == 0) {
550
                        /*
2496 jermar 551
                         * The right child of the
552
                         * balanced node is balanced,
553
                         * after RR rotation is done,
554
                         * the whole tree will be
555
                         * balanced.
2416 mencl 556
                         */
557
                        par->balance = -1;
2496 jermar 558
                        gpa->balance = 1;
2416 mencl 559
 
2497 jermar 560
                        (void) repair(t, par, gpa, par,
561
                            NULL, false);
2416 mencl 562
                        break;
563
                    } else {
2497 jermar 564
                        par->balance = 0;
565
                        gpa->balance = 0;
566
                        if (!repair(t, par, gpa, par,
567
                            &dir, false))
2416 mencl 568
                            break;
569
                    }
570
                    gpa = par->par;
571
                }
572
            } else {
573
                /*
2496 jermar 574
                 * Repair the pointer which pointed to the
575
                 * balanced node. If it was root then balancing
576
                 * is finished else continue with the next
577
                 * iteration (parent node).
2416 mencl 578
                 */
2497 jermar 579
                if (!repair(t, gpa, gpa, NULL, &dir, true))
2496 jermar 580
                    break;
2416 mencl 581
                gpa = gpa->par;
582
            }
583
        } else {
584
            /*
2496 jermar 585
             * Deletion was made in the right subtree.
2416 mencl 586
             */
587
            gpa->balance--;
588
            if (gpa->balance == -1) {
589
                /*
2496 jermar 590
                 * Stop balancing, the tree is balanced.
2416 mencl 591
                 */
592
                break;
593
            } else if (gpa->balance == -2) {
594
                /*
2496 jermar 595
                 * Bad balance, heights of left and right
596
                 * subtrees differ more than by one.
2416 mencl 597
                 */
598
                par = gpa->lft;
599
 
2496 jermar 600
                if (par->balance == 1) {
2416 mencl 601
                    /*
602
                     * LR rotation.
603
                     */
604
 
605
                    cur = par->rgt;
606
                    par->rgt = cur->lft;
607
                    cur->lft = par;
608
                    gpa->lft = cur->rgt;
609
                    cur->rgt = gpa;
610
 
611
                    /*
2496 jermar 612
                     * Repair balances and paternity of
613
                     * children, depending on the balance
614
                     * factor of the grand child (cur).
2416 mencl 615
                     */
2497 jermar 616
                    REBALANCE_LR();
2416 mencl 617
 
618
                    /*
619
                     * Repair paternity.
620
                     */
621
                    cur->par = gpa->par;
622
                    gpa->par = cur;
623
                    par->par = cur;
624
 
2497 jermar 625
                    if (!repair(t, cur, gpa, cur, &dir,
626
                        false))
627
                        break;
2416 mencl 628
                    gpa = cur->par;
629
                } else {
630
                    /*
631
                     * LL rotation.
632
                     */
2497 jermar 633
 
2416 mencl 634
                    gpa->lft = par->rgt;
2496 jermar 635
                    if (par->rgt)
636
                        par->rgt->par = gpa;
2416 mencl 637
                    par->rgt = gpa;
638
                    /*
639
                     * Repair paternity.
640
                     */
641
                    par->par = gpa->par;
642
                    gpa->par = par;
643
 
644
                    if (par->balance == 0) {
645
                        /*
2496 jermar 646
                         * The left child of the
647
                         * balanced node is balanced,
648
                         * after LL rotation is done,
649
                         * the whole tree will be
650
                         * balanced.
2416 mencl 651
                         */
2496 jermar 652
                        par->balance = 1;
2416 mencl 653
                        gpa->balance = -1;
654
 
2497 jermar 655
                        (void) repair(t, par, gpa, par,
656
                            NULL, false);
2416 mencl 657
                        break;
658
                    } else {
2497 jermar 659
                        par->balance = 0;
660
                        gpa->balance = 0;
2416 mencl 661
 
2497 jermar 662
                        if (!repair(t, par, gpa, par,
663
                            &dir, false))
2416 mencl 664
                            break;
665
                    }
666
                    gpa = par->par;
667
                }
668
            } else {
669
                /*
2496 jermar 670
                 * Repair the pointer which pointed to the
671
                 * balanced node. If it was root then balancing
672
                 * is finished. Otherwise continue with the next
673
                 * iteration (parent node).
2416 mencl 674
                 */
2497 jermar 675
                if (!repair(t, gpa, gpa, NULL, &dir, true))
2496 jermar 676
                    break;
2416 mencl 677
                gpa = gpa->par;
678
            }
679
        }
680
    }
681
}
682
 
683
 
2496 jermar 684
/** Delete a node with the smallest key from the AVL tree.
2416 mencl 685
 *
686
 * @param t AVL tree structure.
687
 */
2421 mencl 688
bool avltree_delete_min(avltree_t *t)
2416 mencl 689
{
690
    avltree_node_t *node;
691
 
692
    /*
2496 jermar 693
     * Start searching for the smallest key in the tree starting in the root
694
     * node and continue in cycle to the leftmost node in the tree (which
695
     * must have the smallest key).
2416 mencl 696
     */
2496 jermar 697
 
2416 mencl 698
    node = t->root;
2496 jermar 699
    if (!node)
700
        return false;
2416 mencl 701
 
702
    while (node->lft != NULL)
703
        node = node->lft;
704
 
2496 jermar 705
    avltree_delete(t, node);
2416 mencl 706
 
707
    return true;
708
}
2496 jermar 709
 
710
/** @}
711
 */
2497 jermar 712