← Back to branch summary

~ubuntu-branches/ubuntu/utopic/cmake/utopic

« back to all changes in this revision

Viewing changes to Utilities/cmlibarchive/libarchive/archive_rb.c

  • Committer: Package Import Robot
  • Author(s): Harald Sitter
  • Date: 2013-10-10 12:54:39 UTC
  • mfrom: (1.14.7)
  • Revision ID: package-import@ubuntu.com-20131010125439-h0ahaj004on6oj92
Tags: 2.8.12-0ubuntu1
https://launchpad.net/bugs/1246701
New upstream release LP: #1246701

Show diffs side-by-side

added added

removed removed

Lines of Context:
Utilities/cmlibarchive/libarchive/archive_rb.c
96
96
    const struct archive_rb_tree_ops *ops)
97
97
{
98
98
        rbt->rbt_ops = ops;
99
 
        *((const struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE;
 
99
        *((struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE;
100
100
}
101
101
 
102
102
struct archive_rb_node *
237
237
        struct archive_rb_node * const new_father = old_child;
238
238
        struct archive_rb_node * const new_child = old_father;
239
239
 
 
240
        if (new_father == NULL)
 
241
                return;
240
242
        /*
241
243
         * Exchange descendant linkages.
242
244
         */
377
379
 
378
380
        if (standin_father == self) {
379
381
                /*
380
 
                 * As a child of self, any childen would be opposite of
 
382
                 * As a child of self, any children would be opposite of
381
383
                 * our parent.
382
384
                 */
383
385
                standin_son = standin->rb_nodes[standin_which];
384
386
        } else {
385
387
                /*
386
 
                 * Since we aren't a child of self, any childen would be
 
388
                 * Since we aren't a child of self, any children would be
387
389
                 * on the same side as our parent.
388
390
                 */
389
391
                standin_son = standin->rb_nodes[standin_other];
410
412
                /*
411
413
                 * If we are about to delete the standin's father, then when
412
414
                 * we call rebalance, we need to use ourselves as our father.
413
 
                 * Otherwise remember our original father.  Also, sincef we are
 
415
                 * Otherwise remember our original father.  Also, since we are
414
416
                 * our standin's father we only need to reparent the standin's
415
417
                 * brother.
416
418
                 *
466
468
 *      __archive_rb_tree_node_swap(rbt, self, which);
467
469
 *      __archive_rb_tree_prune_node(rbt, self, F);
468
470
 *
469
 
 * But it's more efficient to just evalate and recolor the child.
 
471
 * But it's more efficient to just evaluate and recolor the child.
470
472
 */
471
473
static void
472
474
__archive_rb_tree_prune_blackred_branch(
505
507
         * red-black tree.  So if we must remove a node, attempt to rearrange
506
508
         * the tree so we can remove a red node.
507
509
         *
508
 
         * The simpliest case is a childless red node or a childless root node:
 
510
         * The simplest case is a childless red node or a childless root node:
509
511
         *
510
512
         * |    T  -->    T  |    or    |  R  -->  *  |
511
513
         * |  s    -->  *    |
517
519
        }
518
520
        if (!RB_TWOCHILDREN_P(self)) {
519
521
                /*
520
 
                 * The next simpliest case is the node we are deleting is
 
522
                 * The next simplest case is the node we are deleting is
521
523
                 * black and has one red child.
522
524
                 *
523
525
                 * |      T  -->      T  -->      T  |
552
554
                unsigned int other = which ^ RB_DIR_OTHER;
553
555
                struct archive_rb_node *brother = parent->rb_nodes[other];
554
556
 
 
557
                if (brother == NULL)
 
558
                        return;/* The tree may be broken. */
555
559
                /*
556
560
                 * For cases 1, 2a, and 2b, our brother's children must
557
561
                 * be black and our father must be black
573
577
                                 */
574
578
                                __archive_rb_tree_reparent_nodes(parent, other);
575
579
                                brother = parent->rb_nodes[other];
 
580
                                if (brother == NULL)
 
581
                                        return;/* The tree may be broken. */
576
582
                        } else {
577
583
                                /*
578
584
                                 * Both our parent and brother are black.
656
662
                         * If we had two red nephews, then after the swap,
657
663
                         * our former father would have a red grandson. 
658
664
                         */
 
665
                        if (brother->rb_nodes[other] == NULL)
 
666
                                return;/* The tree may be broken. */
659
667
                        RB_MARK_BLACK(brother->rb_nodes[other]);
660
668
                        __archive_rb_tree_reparent_nodes(parent, other);
661
669
                        break;          /* We're done! */
683
691
         */
684
692
        if (RB_SENTINEL_P(self->rb_nodes[direction])) {
685
693
                while (!RB_ROOT_P(rbt, self)) {
686
 
                        if (other == RB_POSITION(self))
 
694
                        if (other == (unsigned int)RB_POSITION(self))
687
695
                                return RB_FATHER(self);
688
696
                        self = RB_FATHER(self);
689
697
                }