Subversion Repositories HelenOS

Rev

Rev 2496 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2496 Rev 2497
Line 215... Line 215...
215
            if (top->lft != NULL)
215
            if (top->lft != NULL)
216
                top->lft->par = top;
216
                top->lft->par = top;
217
            par->par = top->par;
217
            par->par = top->par;
218
            top->par = par;
218
            top->par = par;
219
            par->rgt = top;
219
            par->rgt = top;
-
 
220
            par->balance = 0;
220
            par->balance = top->balance = 0;
221
            top->balance = 0;
221
            *dpc = par;
222
            *dpc = par;
222
        } else {
223
        } else {
223
            /*
224
            /*
224
             * LR rotation.
225
             * LR rotation.
225
             */
226
             */
Line 240... Line 241...
240
           
241
           
241
            if (gpa->balance == -1) {
242
            if (gpa->balance == -1) {
242
                par->balance = 0;
243
                par->balance = 0;
243
                top->balance = 1;
244
                top->balance = 1;
244
            } else if (gpa->balance == 0) {
245
            } else if (gpa->balance == 0) {
-
 
246
                par->balance = 0;
245
                par->balance = top->balance = 0;
247
                top->balance = 0;
246
            } else {
248
            } else {
247
                par->balance = -1;
249
                par->balance = -1;
248
                top->balance = 0;
250
                top->balance = 0;
249
            }
251
            }
250
            gpa->balance = 0;
252
            gpa->balance = 0;
Line 260... Line 262...
260
            if (top->rgt != NULL)
262
            if (top->rgt != NULL)
261
                top->rgt->par = top;
263
                top->rgt->par = top;
262
            par->par = top->par;
264
            par->par = top->par;
263
            top->par = par;
265
            top->par = par;
264
            par->lft = top;
266
            par->lft = top;
-
 
267
            par->balance = 0;
265
            par->balance = top->balance = 0;
268
            top->balance = 0;
266
            *dpc = par;
269
            *dpc = par;
267
        } else {
270
        } else {
268
            /*
271
            /*
269
             * RL rotation.
272
             * RL rotation.
270
             */
273
             */
Line 285... Line 288...
285
 
288
 
286
            if (gpa->balance == 1) {
289
            if (gpa->balance == 1) {
287
                par->balance = 0;
290
                par->balance = 0;
288
                top->balance = -1;
291
                top->balance = -1;
289
            } else if (gpa->balance == 0) {
292
            } else if (gpa->balance == 0) {
-
 
293
                par->balance = 0;
290
                par->balance = top->balance = 0;
294
                top->balance = 0;
291
            } else {
295
            } else {
292
                par->balance = 1;
296
                par->balance = 1;
293
                top->balance = 0;
297
                top->balance = 0;
294
            }
298
            }
295
            gpa->balance = 0;
299
            gpa->balance = 0;
Line 302... Line 306...
302
        return;
306
        return;
303
    }
307
    }
304
 
308
 
305
}
309
}
306
 
310
 
-
 
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
 
307
/** Delete a node from the AVL tree.
382
/** Delete a node from the AVL tree.
308
 *
383
 *
309
 * Because multiple identical keys are allowed, the parent pointers are
384
 * Because multiple identical keys are allowed, the parent pointers are
310
 * essential during deletion.
385
 * essential during deletion.
311
 *
386
 *
Line 315... Line 390...
315
void avltree_delete(avltree_t *t, avltree_node_t *node)
390
void avltree_delete(avltree_t *t, avltree_node_t *node)
316
{
391
{
317
    avltree_node_t *cur;
392
    avltree_node_t *cur;
318
    avltree_node_t *par;
393
    avltree_node_t *par;
319
    avltree_node_t *gpa;
394
    avltree_node_t *gpa;
320
    uint8_t dir;
395
    int dir;
321
 
396
 
322
    ASSERT(t);
397
    ASSERT(t);
323
    ASSERT(node);
398
    ASSERT(node);
324
   
399
   
325
    if (node->lft == NULL) {
400
    if (node->lft == NULL) {
326
        if (node->rgt) {
401
        if (node->rgt) {
327
            /*
402
            /*
328
             * Replace the node with its only right son.
403
             * Replace the node with its only right son.
329
             *
404
             *
330
             * Balance of the right son will be repaired in the
405
             * Balance of the right son will be repaired in the
Line 352... Line 427...
352
            cur = NULL;
427
            cur = NULL;
353
            dir = (gpa->lft == node) ? LEFT: RIGHT;
428
            dir = (gpa->lft == node) ? LEFT: RIGHT;
354
        }
429
        }
355
    } else {
430
    } else {
356
        /*
431
        /*
357
         * The node has left and right son. Find a node with the
432
         * The node has the left son. Find a node with the smallest key
358
         * smallest key in the left subtree and replace the deleted node
433
         * in the left subtree and replace the deleted node with that
359
         * with that node.
434
         * node.
360
         */
435
         */
361
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
436
        for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
362
            ;
437
            ;
363
 
438
 
364
        if (cur != node->lft) {
439
        if (cur != node->lft) {
Line 400... Line 475...
400
   
475
   
401
    /*
476
    /*
402
     * Repair the parent node's pointer which pointed previously to the
477
     * Repair the parent node's pointer which pointed previously to the
403
     * deleted node.
478
     * deleted node.
404
     */
479
     */
405
    if (node->par == NULL) {
480
    (void) repair(t, node, node, cur, NULL, false);
406
        t->root = cur;
-
 
407
    } else {
-
 
408
        if (node->par->lft == node) {
-
 
409
            node->par->lft = cur;
-
 
410
        } else {
-
 
411
            node->par->rgt = cur;
-
 
412
        }
-
 
413
    }
-
 
414
   
481
   
415
    /*
482
    /*
416
     * Repair cycle which repairs balances of nodes on the way from from the
483
     * Repair cycle which repairs balances of nodes on the way from from the
417
     * cut-off node up to the root.
484
     * cut-off node up to the root.
418
     */
485
     */
Line 448... Line 515...
448
                    /*
515
                    /*
449
                     * Repair balances and paternity of
516
                     * Repair balances and paternity of
450
                     * children, depending on the balance
517
                     * children, depending on the balance
451
                     * factor of the grand child (cur).
518
                     * factor of the grand child (cur).
452
                     */
519
                     */
453
                    if (cur->balance == 1) {
-
 
454
                        par->balance = 0;
-
 
455
                        gpa->balance = -1;
-
 
456
                        if (gpa->rgt)
520
                    REBALANCE_RL();
457
                            gpa->rgt->par = gpa;
-
 
458
                        par->lft->par = par;
-
 
459
                    } else if (cur->balance == 0) {
-
 
460
                        par->balance = gpa->balance = 0;
-
 
461
                        if (gpa->rgt)
-
 
462
                            gpa->rgt->par = gpa;
-
 
463
                        if (par->lft)
-
 
464
                            par->lft->par = par;
-
 
465
                    } else {
-
 
466
                        par->balance = 1;
-
 
467
                        gpa->balance = 0;
-
 
468
                        if (par->lft)
-
 
469
                            par->lft->par = par;
-
 
470
                        gpa->rgt->par = gpa;
-
 
471
                    }
-
 
472
                    cur->balance = 0;
-
 
473
                   
521
                   
474
                    /*
522
                    /*
475
                     * Repair paternity.
523
                     * Repair paternity.
476
                     */
524
                     */
477
                    cur->par = gpa->par;
525
                    cur->par = gpa->par;
478
                    gpa->par = cur;
526
                    gpa->par = cur;
479
                    par->par = cur;
527
                    par->par = cur;
480
 
528
 
481
                    /*
-
 
482
                     * Repair the pointer which pointed to
529
                    if (!repair(t, cur, gpa, cur, &dir,
483
                     * the balanced node. If it was root
-
 
484
                     * then the balancing is finished.
-
 
485
                     * Otherwise continue with the next
-
 
486
                     * iteration (parent node).
-
 
487
                     */
530
                        false))
488
                    if (cur->par == NULL) {
-
 
489
                        t->root = cur; 
-
 
490
                        break;
531
                        break;
491
                    } else {
-
 
492
                        if (cur->par->lft == gpa) {
-
 
493
                            cur->par->lft = cur;
-
 
494
                            dir = LEFT;
-
 
495
                        } else {
-
 
496
                            cur->par->rgt = cur;
-
 
497
                            dir = RIGHT;
-
 
498
                        }
-
 
499
                    }
-
 
500
                    gpa = cur->par;
532
                    gpa = cur->par;
501
                } else {
533
                } else {
502
                    /*
534
                    /*
503
                     * RR rotation.
535
                     * RR rotation.
504
                     */
536
                     */
Line 523... Line 555...
523
                         * balanced.
555
                         * balanced.
524
                         */
556
                         */
525
                        par->balance = -1;
557
                        par->balance = -1;
526
                        gpa->balance = 1;
558
                        gpa->balance = 1;
527
 
559
 
528
                        /*
-
 
529
                         * Repair the pointer which
-
 
530
                         * pointed to the balanced node
-
 
531
                         * and finish balancing.
-
 
532
                         */
-
 
533
                        if (par->par == NULL) {
-
 
534
                            t->root = par; 
-
 
535
                        } else {
-
 
536
                            if (par->par->lft ==
560
                        (void) repair(t, par, gpa, par,
537
                                gpa) {
-
 
538
                                par->par->lft =
-
 
539
                                    par;
-
 
540
                            } else {
-
 
541
                                par->par->rgt =
-
 
542
                                    par;
561
                            NULL, false);
543
                            }
-
 
544
                        }
-
 
545
                        break;
562
                        break;
546
                    } else {
563
                    } else {
547
                        par->balance = gpa->balance = 0;
564
                        par->balance = 0;
548
                        /*
-
 
549
                         * Repair the pointer which
-
 
550
                         * pointed to the balanced node.
565
                        gpa->balance = 0;
551
                         * If it was root then balancing
-
 
552
                         * is finished. Otherwise
-
 
553
                         * continue with the next
-
 
554
                         * iteration (parent node).
-
 
555
                         */
-
 
556
                        if (par->par == NULL) {
566
                        if (!repair(t, par, gpa, par,
557
                            t->root = par; 
567
                            &dir, false))
558
                            break;
568
                            break;
559
                        } else {   
-
 
560
                            if (par->par->lft ==
-
 
561
                                gpa) {
-
 
562
                                par->par->lft =
-
 
563
                                    par;
-
 
564
                                dir = LEFT;
-
 
565
                            } else {
-
 
566
                                par->par->rgt =
-
 
567
                                    par;
-
 
568
                                dir = RIGHT;
-
 
569
                            }
-
 
570
                        }
-
 
571
                    }
569
                    }
572
                    gpa = par->par;
570
                    gpa = par->par;
573
                }
571
                }
574
            } else {
572
            } else {
575
                /*
573
                /*
576
                 * Repair the pointer which pointed to the
574
                 * Repair the pointer which pointed to the
577
                 * balanced node. If it was root then balancing
575
                 * balanced node. If it was root then balancing
578
                 * is finished else continue with the next
576
                 * is finished else continue with the next
579
                 * iteration (parent node).
577
                 * iteration (parent node).
580
                 */
578
                 */
581
                if (!gpa->par)
579
                if (!repair(t, gpa, gpa, NULL, &dir, true))
582
                    break;
580
                    break;
583
 
-
 
584
                if (gpa->par->lft == gpa) {
-
 
585
                    dir = LEFT;
-
 
586
                } else {
-
 
587
                    dir = RIGHT;
-
 
588
                }
-
 
589
                gpa = gpa->par;
581
                gpa = gpa->par;
590
            }
582
            }
591
        } else {
583
        } else {
592
            /*
584
            /*
593
             * Deletion was made in the right subtree.
585
             * Deletion was made in the right subtree.
Line 619... Line 611...
619
                    /*
611
                    /*
620
                     * Repair balances and paternity of
612
                     * Repair balances and paternity of
621
                     * children, depending on the balance
613
                     * children, depending on the balance
622
                     * factor of the grand child (cur).
614
                     * factor of the grand child (cur).
623
                     */
615
                     */
624
                    if (cur->balance == -1) {
-
 
625
                        par->balance = 0;
-
 
626
                        gpa->balance = 1;
-
 
627
                        if (gpa->lft)
616
                    REBALANCE_LR();
628
                            gpa->lft->par = gpa;
-
 
629
                        par->rgt->par = par;
-
 
630
                    } else if (cur->balance == 0) {
-
 
631
                        par->balance = gpa->balance = 0;
-
 
632
                        if (gpa->lft)
-
 
633
                            gpa->lft->par = gpa;
-
 
634
                        if (par->rgt)
-
 
635
                            par->rgt->par = par;
-
 
636
                    } else {
-
 
637
                        par->balance = -1;
-
 
638
                        gpa->balance = 0;
-
 
639
                        if (par->rgt)
-
 
640
                            par->rgt->par = par;
-
 
641
                        gpa->lft->par = gpa;
-
 
642
                    }
-
 
643
                    cur->balance = 0;
-
 
644
 
617
 
645
                    /*
618
                    /*
646
                     * Repair paternity.
619
                     * Repair paternity.
647
                     */
620
                     */
648
                    cur->par = gpa->par;
621
                    cur->par = gpa->par;
649
                    gpa->par = cur;
622
                    gpa->par = cur;
650
                    par->par = cur;
623
                    par->par = cur;
651
 
624
 
652
                    /*
-
 
653
                     * Repair the pointer which pointed to
625
                    if (!repair(t, cur, gpa, cur, &dir,
654
                     * the balanced node. If it was root
-
 
655
                     * then balancing is finished. Otherwise
-
 
656
                     * continue with the next iteration
-
 
657
                     * (parent node).
626
                        false))
658
                     */
-
 
659
                    if (cur->par == NULL) {
-
 
660
                        t->root = cur; 
-
 
661
                        break;
627
                        break;
662
                    } else {
-
 
663
                        if (cur->par->lft == gpa) {
-
 
664
                            cur->par->lft = cur;
-
 
665
                            dir = LEFT;
-
 
666
                        } else {
-
 
667
                            cur->par->rgt = cur;
-
 
668
                            dir = RIGHT;
-
 
669
                        }
-
 
670
                    }
-
 
671
                    gpa = cur->par;
628
                    gpa = cur->par;
672
                } else {
629
                } else {
673
                    /*
630
                    /*
674
                     * LL rotation.
631
                     * LL rotation.
675
                     */
632
                     */
676
                   
633
 
677
                    gpa->lft = par->rgt;
634
                    gpa->lft = par->rgt;
678
                    if (par->rgt)
635
                    if (par->rgt)
679
                        par->rgt->par = gpa;
636
                        par->rgt->par = gpa;
680
                    par->rgt = gpa;
637
                    par->rgt = gpa;
681
                    /*
638
                    /*
Line 693... Line 650...
693
                         * balanced.
650
                         * balanced.
694
                         */
651
                         */
695
                        par->balance = 1;
652
                        par->balance = 1;
696
                        gpa->balance = -1;
653
                        gpa->balance = -1;
697
                       
654
                       
698
                        /*
-
 
699
                         * Repair the pointer which
-
 
700
                         * pointed to the balanced node
-
 
701
                         * and finish balancing.
-
 
702
                         */
-
 
703
                        if (par->par == NULL) {
-
 
704
                            t->root = par;
-
 
705
                        } else {
-
 
706
                            if (par->par->lft ==
655
                        (void) repair(t, par, gpa, par,
707
                                gpa) {
-
 
708
                                par->par->lft =
-
 
709
                                    par;
-
 
710
                            } else {
-
 
711
                                par->par->rgt =
-
 
712
                                    par;
656
                            NULL, false);
713
                            }
-
 
714
                        }
-
 
715
                        break;
657
                        break;
716
                    } else {
658
                    } else {
-
 
659
                        par->balance = 0;
717
                        par->balance = gpa->balance = 0;
660
                        gpa->balance = 0;
718
                       
661
                       
719
                        /*
-
 
720
                         * Repair the pointer which
-
 
721
                         * pointed to the balanced node.
-
 
722
                         * If it was root then balancing
-
 
723
                         * is finished. Otherwise
-
 
724
                         * continue with the next
-
 
725
                         * iteration (parent node).
-
 
726
                         */
-
 
727
                        if (par->par == NULL) {
662
                        if (!repair(t, par, gpa, par,
728
                            t->root = par;
663
                            &dir, false))
729
                            break;
664
                            break;
730
                        } else {
-
 
731
                            if (par->par->lft ==
-
 
732
                                gpa) {
-
 
733
                                par->par->lft =
-
 
734
                                    par;
-
 
735
                                dir = LEFT;
-
 
736
                            } else {
-
 
737
                                par->par->rgt =
-
 
738
                                    par;
-
 
739
                                dir = RIGHT;
-
 
740
                            }
-
 
741
                        }
-
 
742
                    }
665
                    }
743
                    gpa = par->par;
666
                    gpa = par->par;
744
                }
667
                }
745
            } else {
668
            } else {
746
                /*
669
                /*
747
                 * Repair the pointer which pointed to the
670
                 * Repair the pointer which pointed to the
748
                 * balanced node. If it was root then balancing
671
                 * balanced node. If it was root then balancing
749
                 * is finished. Otherwise continue with the next
672
                 * is finished. Otherwise continue with the next
750
                 * iteration (parent node).
673
                 * iteration (parent node).
751
                 */
674
                 */
752
                if (!gpa->par)
675
                if (!repair(t, gpa, gpa, NULL, &dir, true))
753
                    break;
676
                    break;
754
 
-
 
755
                if (gpa->par->lft == gpa) {
-
 
756
                    dir = LEFT;
-
 
757
                } else {
-
 
758
                    dir = RIGHT;
-
 
759
                }
-
 
760
                gpa = gpa->par;
677
                gpa = gpa->par;
761
            }
678
            }
762
        }
679
        }
763
    }
680
    }
764
}
681
}
Line 790... Line 707...
790
    return true;
707
    return true;
791
}
708
}
792
 
709
 
793
/** @}
710
/** @}
794
 */
711
 */
-
 
712