Subversion Repositories HelenOS

Rev

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