1 /*-
2 * Copyright (c) 2001 The NetBSD Foundation, Inc.
3 * All rights reserved.
4 *
5 * This code is derived from software contributed to The NetBSD Foundation
6 * by Matt Thomas <matt@3am-software.com>.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
18 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
21 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Based on: NetBSD: rb.c,v 1.6 2010/04/30 13:58:09 joerg Exp
30 */
31
32 #include "archive_platform.h"
33
34 #include <stddef.h>
35
36 #include "archive_rb.h"
37
38 /* Keep in sync with archive_rb.h */
39 #define RB_DIR_LEFT 0
40 #define RB_DIR_RIGHT 1
41 #define RB_DIR_OTHER 1
42 #define rb_left rb_nodes[RB_DIR_LEFT]
43 #define rb_right rb_nodes[RB_DIR_RIGHT]
44
45 #define RB_FLAG_POSITION 0x2
46 #define RB_FLAG_RED 0x1
47 #define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED)
48 #define RB_FATHER(rb) \
49 ((struct archive_rb_node *)((rb)->rb_info & ~RB_FLAG_MASK))
50 #define RB_SET_FATHER(rb, father) \
51 ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK)))
52
53 #define RB_SENTINEL_P(rb) ((rb) == NULL)
54 #define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left)
55 #define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right)
56 #define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb)))
57 #define RB_CHILDLESS_P(rb) \
58 (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb)))
59 #define RB_TWOCHILDREN_P(rb) \
60 (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb))
61
62 #define RB_POSITION(rb) \
63 (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT)
64 #define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT)
65 #define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT)
66 #define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)
67 #define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0)
68 #define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED))
69 #define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED))
70 #define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED))
71 #define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb))
72 #define RB_SET_POSITION(rb, position) \
73 ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \
74 ((rb)->rb_info &= ~RB_FLAG_POSITION)))
75 #define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK))
76 #define RB_COPY_PROPERTIES(dst, src) \
77 ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK))
78 #define RB_SWAP_PROPERTIES(a, b) do { \
79 uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \
80 (a)->rb_info ^= xorinfo; \
81 (b)->rb_info ^= xorinfo; \
82 } while (/*CONSTCOND*/ 0)
83
84 static void __archive_rb_tree_insert_rebalance(struct archive_rb_tree *,
85 struct archive_rb_node *);
86 static void __archive_rb_tree_removal_rebalance(struct archive_rb_tree *,
87 struct archive_rb_node *, unsigned int);
88
89 #define RB_SENTINEL_NODE NULL
90
91 #define T 1
92 #define F 0
93
94 void
__archive_rb_tree_init(struct archive_rb_tree * rbt,const struct archive_rb_tree_ops * ops)95 __archive_rb_tree_init(struct archive_rb_tree *rbt,
96 const struct archive_rb_tree_ops *ops)
97 {
98 rbt->rbt_ops = ops;
99 *((struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE;
100 }
101
102 struct archive_rb_node *
__archive_rb_tree_find_node(struct archive_rb_tree * rbt,const void * key)103 __archive_rb_tree_find_node(struct archive_rb_tree *rbt, const void *key)
104 {
105 archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
106 struct archive_rb_node *parent = rbt->rbt_root;
107
108 while (!RB_SENTINEL_P(parent)) {
109 const signed int diff = (*compare_key)(parent, key);
110 if (diff == 0)
111 return parent;
112 parent = parent->rb_nodes[diff > 0];
113 }
114
115 return NULL;
116 }
117
118 struct archive_rb_node *
__archive_rb_tree_find_node_geq(struct archive_rb_tree * rbt,const void * key)119 __archive_rb_tree_find_node_geq(struct archive_rb_tree *rbt, const void *key)
120 {
121 archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
122 struct archive_rb_node *parent = rbt->rbt_root;
123 struct archive_rb_node *last = NULL;
124
125 while (!RB_SENTINEL_P(parent)) {
126 const signed int diff = (*compare_key)(parent, key);
127 if (diff == 0)
128 return parent;
129 if (diff < 0)
130 last = parent;
131 parent = parent->rb_nodes[diff > 0];
132 }
133
134 return last;
135 }
136
137 struct archive_rb_node *
__archive_rb_tree_find_node_leq(struct archive_rb_tree * rbt,const void * key)138 __archive_rb_tree_find_node_leq(struct archive_rb_tree *rbt, const void *key)
139 {
140 archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
141 struct archive_rb_node *parent = rbt->rbt_root;
142 struct archive_rb_node *last = NULL;
143
144 while (!RB_SENTINEL_P(parent)) {
145 const signed int diff = (*compare_key)(parent, key);
146 if (diff == 0)
147 return parent;
148 if (diff > 0)
149 last = parent;
150 parent = parent->rb_nodes[diff > 0];
151 }
152
153 return last;
154 }
155
156 int
__archive_rb_tree_insert_node(struct archive_rb_tree * rbt,struct archive_rb_node * self)157 __archive_rb_tree_insert_node(struct archive_rb_tree *rbt,
158 struct archive_rb_node *self)
159 {
160 archive_rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
161 struct archive_rb_node *parent, *tmp;
162 unsigned int position;
163 int rebalance;
164
165 tmp = rbt->rbt_root;
166 /*
167 * This is a hack. Because rbt->rbt_root is just a
168 * struct archive_rb_node *, just like rb_node->rb_nodes[RB_DIR_LEFT],
169 * we can use this fact to avoid a lot of tests for root and know
170 * that even at root, updating
171 * RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
172 * update rbt->rbt_root.
173 */
174 parent = (struct archive_rb_node *)(void *)&rbt->rbt_root;
175 position = RB_DIR_LEFT;
176
177 /*
178 * Find out where to place this new leaf.
179 */
180 while (!RB_SENTINEL_P(tmp)) {
181 const signed int diff = (*compare_nodes)(tmp, self);
182 if (diff == 0) {
183 /*
184 * Node already exists; don't insert.
185 */
186 return F;
187 }
188 parent = tmp;
189 position = (diff > 0);
190 tmp = parent->rb_nodes[position];
191 }
192
193 /*
194 * Initialize the node and insert as a leaf into the tree.
195 */
196 RB_SET_FATHER(self, parent);
197 RB_SET_POSITION(self, position);
198 if (parent == (struct archive_rb_node *)(void *)&rbt->rbt_root) {
199 RB_MARK_BLACK(self); /* root is always black */
200 rebalance = F;
201 } else {
202 /*
203 * All new nodes are colored red. We only need to rebalance
204 * if our parent is also red.
205 */
206 RB_MARK_RED(self);
207 rebalance = RB_RED_P(parent);
208 }
209 self->rb_left = parent->rb_nodes[position];
210 self->rb_right = parent->rb_nodes[position];
211 parent->rb_nodes[position] = self;
212
213 /*
214 * Rebalance tree after insertion
215 */
216 if (rebalance)
217 __archive_rb_tree_insert_rebalance(rbt, self);
218
219 return T;
220 }
221
222 /*
223 * Swap the location and colors of 'self' and its child @ which. The child
224 * can not be a sentinel node. This is our rotation function. However,
225 * since it preserves coloring, it great simplifies both insertion and
226 * removal since rotation almost always involves the exchanging of colors
227 * as a separate step.
228 */
229 /*ARGSUSED*/
230 static void
__archive_rb_tree_reparent_nodes(struct archive_rb_node * old_father,const unsigned int which)231 __archive_rb_tree_reparent_nodes(
232 struct archive_rb_node *old_father, const unsigned int which)
233 {
234 const unsigned int other = which ^ RB_DIR_OTHER;
235 struct archive_rb_node * const grandpa = RB_FATHER(old_father);
236 struct archive_rb_node * const old_child = old_father->rb_nodes[which];
237 struct archive_rb_node * const new_father = old_child;
238 struct archive_rb_node * const new_child = old_father;
239
240 if (new_father == NULL)
241 return;
242 /*
243 * Exchange descendant linkages.
244 */
245 grandpa->rb_nodes[RB_POSITION(old_father)] = new_father;
246 new_child->rb_nodes[which] = old_child->rb_nodes[other];
247 new_father->rb_nodes[other] = new_child;
248
249 /*
250 * Update ancestor linkages
251 */
252 RB_SET_FATHER(new_father, grandpa);
253 RB_SET_FATHER(new_child, new_father);
254
255 /*
256 * Exchange properties between new_father and new_child. The only
257 * change is that new_child's position is now on the other side.
258 */
259 RB_SWAP_PROPERTIES(new_father, new_child);
260 RB_SET_POSITION(new_child, other);
261
262 /*
263 * Make sure to reparent the new child to ourself.
264 */
265 if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
266 RB_SET_FATHER(new_child->rb_nodes[which], new_child);
267 RB_SET_POSITION(new_child->rb_nodes[which], which);
268 }
269
270 }
271
272 static void
__archive_rb_tree_insert_rebalance(struct archive_rb_tree * rbt,struct archive_rb_node * self)273 __archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt,
274 struct archive_rb_node *self)
275 {
276 struct archive_rb_node * father = RB_FATHER(self);
277 struct archive_rb_node * grandpa;
278 struct archive_rb_node * uncle;
279 unsigned int which;
280 unsigned int other;
281
282 for (;;) {
283 /*
284 * We are red and our parent is red, therefore we must have a
285 * grandfather and he must be black.
286 */
287 grandpa = RB_FATHER(father);
288 which = (father == grandpa->rb_right);
289 other = which ^ RB_DIR_OTHER;
290 uncle = grandpa->rb_nodes[other];
291
292 if (RB_BLACK_P(uncle))
293 break;
294
295 /*
296 * Case 1: our uncle is red
297 * Simply invert the colors of our parent and
298 * uncle and make our grandparent red. And
299 * then solve the problem up at his level.
300 */
301 RB_MARK_BLACK(uncle);
302 RB_MARK_BLACK(father);
303 if (RB_ROOT_P(rbt, grandpa)) {
304 /*
305 * If our grandpa is root, don't bother
306 * setting him to red, just return.
307 */
308 return;
309 }
310 RB_MARK_RED(grandpa);
311 self = grandpa;
312 father = RB_FATHER(self);
313 if (RB_BLACK_P(father)) {
314 /*
315 * If our great-grandpa is black, we're done.
316 */
317 return;
318 }
319 }
320
321 /*
322 * Case 2&3: our uncle is black.
323 */
324 if (self == father->rb_nodes[other]) {
325 /*
326 * Case 2: we are on the same side as our uncle
327 * Swap ourselves with our parent so this case
328 * becomes case 3. Basically our parent becomes our
329 * child.
330 */
331 __archive_rb_tree_reparent_nodes(father, other);
332 }
333 /*
334 * Case 3: we are opposite a child of a black uncle.
335 * Swap our parent and grandparent. Since our grandfather
336 * is black, our father will become black and our new sibling
337 * (former grandparent) will become red.
338 */
339 __archive_rb_tree_reparent_nodes(grandpa, which);
340
341 /*
342 * Final step: Set the root to black.
343 */
344 RB_MARK_BLACK(rbt->rbt_root);
345 }
346
347 static void
__archive_rb_tree_prune_node(struct archive_rb_tree * rbt,struct archive_rb_node * self,int rebalance)348 __archive_rb_tree_prune_node(struct archive_rb_tree *rbt,
349 struct archive_rb_node *self, int rebalance)
350 {
351 const unsigned int which = RB_POSITION(self);
352 struct archive_rb_node *father = RB_FATHER(self);
353
354 /*
355 * Since we are childless, we know that self->rb_left is pointing
356 * to the sentinel node.
357 */
358 father->rb_nodes[which] = self->rb_left;
359
360 /*
361 * Rebalance if requested.
362 */
363 if (rebalance)
364 __archive_rb_tree_removal_rebalance(rbt, father, which);
365 }
366
367 /*
368 * When deleting an interior node
369 */
370 static void
__archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree * rbt,struct archive_rb_node * self,struct archive_rb_node * standin)371 __archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree *rbt,
372 struct archive_rb_node *self, struct archive_rb_node *standin)
373 {
374 const unsigned int standin_which = RB_POSITION(standin);
375 unsigned int standin_other = standin_which ^ RB_DIR_OTHER;
376 struct archive_rb_node *standin_son;
377 struct archive_rb_node *standin_father = RB_FATHER(standin);
378 int rebalance = RB_BLACK_P(standin);
379
380 if (standin_father == self) {
381 /*
382 * As a child of self, any children would be opposite of
383 * our parent.
384 */
385 standin_son = standin->rb_nodes[standin_which];
386 } else {
387 /*
388 * Since we aren't a child of self, any children would be
389 * on the same side as our parent.
390 */
391 standin_son = standin->rb_nodes[standin_other];
392 }
393
394 if (RB_RED_P(standin_son)) {
395 /*
396 * We know we have a red child so if we flip it to black
397 * we don't have to rebalance.
398 */
399 RB_MARK_BLACK(standin_son);
400 rebalance = F;
401
402 if (standin_father != self) {
403 /*
404 * Change the son's parentage to point to his grandpa.
405 */
406 RB_SET_FATHER(standin_son, standin_father);
407 RB_SET_POSITION(standin_son, standin_which);
408 }
409 }
410
411 if (standin_father == self) {
412 /*
413 * If we are about to delete the standin's father, then when
414 * we call rebalance, we need to use ourselves as our father.
415 * Otherwise remember our original father. Also, since we are
416 * our standin's father we only need to reparent the standin's
417 * brother.
418 *
419 * | R --> S |
420 * | Q S --> Q T |
421 * | t --> |
422 *
423 * Have our son/standin adopt his brother as his new son.
424 */
425 standin_father = standin;
426 } else {
427 /*
428 * | R --> S . |
429 * | / \ | T --> / \ | / |
430 * | ..... | S --> ..... | T |
431 *
432 * Sever standin's connection to his father.
433 */
434 standin_father->rb_nodes[standin_which] = standin_son;
435 /*
436 * Adopt the far son.
437 */
438 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
439 RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
440 /*
441 * Use standin_other because we need to preserve standin_which
442 * for the removal_rebalance.
443 */
444 standin_other = standin_which;
445 }
446
447 /*
448 * Move the only remaining son to our standin. If our standin is our
449 * son, this will be the only son needed to be moved.
450 */
451 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
452 RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
453
454 /*
455 * Now copy the result of self to standin and then replace
456 * self with standin in the tree.
457 */
458 RB_COPY_PROPERTIES(standin, self);
459 RB_SET_FATHER(standin, RB_FATHER(self));
460 RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
461
462 if (rebalance)
463 __archive_rb_tree_removal_rebalance(rbt, standin_father, standin_which);
464 }
465
466 /*
467 * We could do this by doing
468 * __archive_rb_tree_node_swap(rbt, self, which);
469 * __archive_rb_tree_prune_node(rbt, self, F);
470 *
471 * But it's more efficient to just evaluate and recolor the child.
472 */
473 static void
__archive_rb_tree_prune_blackred_branch(struct archive_rb_node * self,unsigned int which)474 __archive_rb_tree_prune_blackred_branch(
475 struct archive_rb_node *self, unsigned int which)
476 {
477 struct archive_rb_node *father = RB_FATHER(self);
478 struct archive_rb_node *son = self->rb_nodes[which];
479
480 /*
481 * Remove ourselves from the tree and give our former child our
482 * properties (position, color, root).
483 */
484 RB_COPY_PROPERTIES(son, self);
485 father->rb_nodes[RB_POSITION(son)] = son;
486 RB_SET_FATHER(son, father);
487 }
488 /*
489 *
490 */
491 void
__archive_rb_tree_remove_node(struct archive_rb_tree * rbt,struct archive_rb_node * self)492 __archive_rb_tree_remove_node(struct archive_rb_tree *rbt,
493 struct archive_rb_node *self)
494 {
495 struct archive_rb_node *standin;
496 unsigned int which;
497
498 /*
499 * In the following diagrams, we (the node to be removed) are S. Red
500 * nodes are lowercase. T could be either red or black.
501 *
502 * Remember the major axiom of the red-black tree: the number of
503 * black nodes from the root to each leaf is constant across all
504 * leaves, only the number of red nodes varies.
505 *
506 * Thus removing a red leaf doesn't require any other changes to a
507 * red-black tree. So if we must remove a node, attempt to rearrange
508 * the tree so we can remove a red node.
509 *
510 * The simplest case is a childless red node or a childless root node:
511 *
512 * | T --> T | or | R --> * |
513 * | s --> * |
514 */
515 if (RB_CHILDLESS_P(self)) {
516 const int rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
517 __archive_rb_tree_prune_node(rbt, self, rebalance);
518 return;
519 }
520 if (!RB_TWOCHILDREN_P(self)) {
521 /*
522 * The next simplest case is the node we are deleting is
523 * black and has one red child.
524 *
525 * | T --> T --> T |
526 * | S --> R --> R |
527 * | r --> s --> * |
528 */
529 which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
530 __archive_rb_tree_prune_blackred_branch(self, which);
531 return;
532 }
533
534 /*
535 * We invert these because we prefer to remove from the inside of
536 * the tree.
537 */
538 which = RB_POSITION(self) ^ RB_DIR_OTHER;
539
540 /*
541 * Let's find the node closes to us opposite of our parent
542 * Now swap it with ourself, "prune" it, and rebalance, if needed.
543 */
544 standin = __archive_rb_tree_iterate(rbt, self, which);
545 __archive_rb_tree_swap_prune_and_rebalance(rbt, self, standin);
546 }
547
548 static void
__archive_rb_tree_removal_rebalance(struct archive_rb_tree * rbt,struct archive_rb_node * parent,unsigned int which)549 __archive_rb_tree_removal_rebalance(struct archive_rb_tree *rbt,
550 struct archive_rb_node *parent, unsigned int which)
551 {
552
553 while (RB_BLACK_P(parent->rb_nodes[which])) {
554 unsigned int other = which ^ RB_DIR_OTHER;
555 struct archive_rb_node *brother = parent->rb_nodes[other];
556
557 if (brother == NULL)
558 return;/* The tree may be broken. */
559 /*
560 * For cases 1, 2a, and 2b, our brother's children must
561 * be black and our father must be black
562 */
563 if (RB_BLACK_P(parent)
564 && RB_BLACK_P(brother->rb_left)
565 && RB_BLACK_P(brother->rb_right)) {
566 if (RB_RED_P(brother)) {
567 /*
568 * Case 1: Our brother is red, swap its
569 * position (and colors) with our parent.
570 * This should now be case 2b (unless C or E
571 * has a red child which is case 3; thus no
572 * explicit branch to case 2b).
573 *
574 * B -> D
575 * A d -> b E
576 * C E -> A C
577 */
578 __archive_rb_tree_reparent_nodes(parent, other);
579 brother = parent->rb_nodes[other];
580 if (brother == NULL)
581 return;/* The tree may be broken. */
582 } else {
583 /*
584 * Both our parent and brother are black.
585 * Change our brother to red, advance up rank
586 * and go through the loop again.
587 *
588 * B -> *B
589 * *A D -> A d
590 * C E -> C E
591 */
592 RB_MARK_RED(brother);
593 if (RB_ROOT_P(rbt, parent))
594 return; /* root == parent == black */
595 which = RB_POSITION(parent);
596 parent = RB_FATHER(parent);
597 continue;
598 }
599 }
600 /*
601 * Avoid an else here so that case 2a above can hit either
602 * case 2b, 3, or 4.
603 */
604 if (RB_RED_P(parent)
605 && RB_BLACK_P(brother)
606 && RB_BLACK_P(brother->rb_left)
607 && RB_BLACK_P(brother->rb_right)) {
608 /*
609 * We are black, our father is red, our brother and
610 * both nephews are black. Simply invert/exchange the
611 * colors of our father and brother (to black and red
612 * respectively).
613 *
614 * | f --> F |
615 * | * B --> * b |
616 * | N N --> N N |
617 */
618 RB_MARK_BLACK(parent);
619 RB_MARK_RED(brother);
620 break; /* We're done! */
621 } else {
622 /*
623 * Our brother must be black and have at least one
624 * red child (it may have two).
625 */
626 if (RB_BLACK_P(brother->rb_nodes[other])) {
627 /*
628 * Case 3: our brother is black, our near
629 * nephew is red, and our far nephew is black.
630 * Swap our brother with our near nephew.
631 * This result in a tree that matches case 4.
632 * (Our father could be red or black).
633 *
634 * | F --> F |
635 * | x B --> x B |
636 * | n --> n |
637 */
638 __archive_rb_tree_reparent_nodes(brother, which);
639 brother = parent->rb_nodes[other];
640 }
641 /*
642 * Case 4: our brother is black and our far nephew
643 * is red. Swap our father and brother locations and
644 * change our far nephew to black. (these can be
645 * done in either order so we change the color first).
646 * The result is a valid red-black tree and is a
647 * terminal case. (again we don't care about the
648 * father's color)
649 *
650 * If the father is red, we will get a red-black-black
651 * tree:
652 * | f -> f --> b |
653 * | B -> B --> F N |
654 * | n -> N --> |
655 *
656 * If the father is black, we will get an all black
657 * tree:
658 * | F -> F --> B |
659 * | B -> B --> F N |
660 * | n -> N --> |
661 *
662 * If we had two red nephews, then after the swap,
663 * our former father would have a red grandson.
664 */
665 if (brother->rb_nodes[other] == NULL)
666 return;/* The tree may be broken. */
667 RB_MARK_BLACK(brother->rb_nodes[other]);
668 __archive_rb_tree_reparent_nodes(parent, other);
669 break; /* We're done! */
670 }
671 }
672 }
673
674 struct archive_rb_node *
__archive_rb_tree_iterate(struct archive_rb_tree * rbt,struct archive_rb_node * self,const unsigned int direction)675 __archive_rb_tree_iterate(struct archive_rb_tree *rbt,
676 struct archive_rb_node *self, const unsigned int direction)
677 {
678 const unsigned int other = direction ^ RB_DIR_OTHER;
679
680 if (self == NULL) {
681 self = rbt->rbt_root;
682 if (RB_SENTINEL_P(self))
683 return NULL;
684 while (!RB_SENTINEL_P(self->rb_nodes[direction]))
685 self = self->rb_nodes[direction];
686 return self;
687 }
688 /*
689 * We can't go any further in this direction. We proceed up in the
690 * opposite direction until our parent is in direction we want to go.
691 */
692 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
693 while (!RB_ROOT_P(rbt, self)) {
694 if (other == (unsigned int)RB_POSITION(self))
695 return RB_FATHER(self);
696 self = RB_FATHER(self);
697 }
698 return NULL;
699 }
700
701 /*
702 * Advance down one in current direction and go down as far as possible
703 * in the opposite direction.
704 */
705 self = self->rb_nodes[direction];
706 while (!RB_SENTINEL_P(self->rb_nodes[other]))
707 self = self->rb_nodes[other];
708 return self;
709 }
710