2 * Copyright (c) 2001 The NetBSD Foundation, Inc.
5 * This code is derived from software contributed to The NetBSD Foundation
6 * by Matt Thomas <matt@3am-software.com>.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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.
29 * Based on: NetBSD: rb.c,v 1.6 2010/04/30 13:58:09 joerg Exp
32 #include "archive_platform.h"
36 #include "archive_rb.h"
38 /* Keep in sync with archive_rb.h */
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]
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)))
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))
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)
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);
89 #define RB_SENTINEL_NODE NULL
95 __archive_rb_tree_init(struct archive_rb_tree
*rbt
,
96 const struct archive_rb_tree_ops
*ops
)
99 *((struct archive_rb_node
**)&rbt
->rbt_root
) = RB_SENTINEL_NODE
;
102 struct archive_rb_node
*
103 __archive_rb_tree_find_node(struct archive_rb_tree
*rbt
, const void *key
)
105 archive_rbto_compare_key_fn compare_key
= rbt
->rbt_ops
->rbto_compare_key
;
106 struct archive_rb_node
*parent
= rbt
->rbt_root
;
108 while (!RB_SENTINEL_P(parent
)) {
109 const signed int diff
= (*compare_key
)(parent
, key
);
112 parent
= parent
->rb_nodes
[diff
> 0];
118 struct archive_rb_node
*
119 __archive_rb_tree_find_node_geq(struct archive_rb_tree
*rbt
, const void *key
)
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
;
125 while (!RB_SENTINEL_P(parent
)) {
126 const signed int diff
= (*compare_key
)(parent
, key
);
131 parent
= parent
->rb_nodes
[diff
> 0];
137 struct archive_rb_node
*
138 __archive_rb_tree_find_node_leq(struct archive_rb_tree
*rbt
, const void *key
)
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
;
144 while (!RB_SENTINEL_P(parent
)) {
145 const signed int diff
= (*compare_key
)(parent
, key
);
150 parent
= parent
->rb_nodes
[diff
> 0];
157 __archive_rb_tree_insert_node(struct archive_rb_tree
*rbt
,
158 struct archive_rb_node
*self
)
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
;
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.
174 parent
= (struct archive_rb_node
*)(void *)&rbt
->rbt_root
;
175 position
= RB_DIR_LEFT
;
178 * Find out where to place this new leaf.
180 while (!RB_SENTINEL_P(tmp
)) {
181 const signed int diff
= (*compare_nodes
)(tmp
, self
);
184 * Node already exists; don't insert.
189 position
= (diff
> 0);
190 tmp
= parent
->rb_nodes
[position
];
194 * Initialize the node and insert as a leaf into the tree.
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 */
203 * All new nodes are colored red. We only need to rebalance
204 * if our parent is also red.
207 rebalance
= RB_RED_P(parent
);
209 self
->rb_left
= parent
->rb_nodes
[position
];
210 self
->rb_right
= parent
->rb_nodes
[position
];
211 parent
->rb_nodes
[position
] = self
;
214 * Rebalance tree after insertion
217 __archive_rb_tree_insert_rebalance(rbt
, self
);
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.
231 __archive_rb_tree_reparent_nodes(
232 struct archive_rb_node
*old_father
, const unsigned int which
)
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
;
240 if (new_father
== NULL
)
243 * Exchange descendant linkages.
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
;
250 * Update ancestor linkages
252 RB_SET_FATHER(new_father
, grandpa
);
253 RB_SET_FATHER(new_child
, new_father
);
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.
259 RB_SWAP_PROPERTIES(new_father
, new_child
);
260 RB_SET_POSITION(new_child
, other
);
263 * Make sure to reparent the new child to ourself.
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
);
273 __archive_rb_tree_insert_rebalance(struct archive_rb_tree
*rbt
,
274 struct archive_rb_node
*self
)
276 struct archive_rb_node
* father
= RB_FATHER(self
);
277 struct archive_rb_node
* grandpa
;
278 struct archive_rb_node
* uncle
;
284 * We are red and our parent is red, therefore we must have a
285 * grandfather and he must be black.
287 grandpa
= RB_FATHER(father
);
288 which
= (father
== grandpa
->rb_right
);
289 other
= which
^ RB_DIR_OTHER
;
290 uncle
= grandpa
->rb_nodes
[other
];
292 if (RB_BLACK_P(uncle
))
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.
301 RB_MARK_BLACK(uncle
);
302 RB_MARK_BLACK(father
);
303 if (RB_ROOT_P(rbt
, grandpa
)) {
305 * If our grandpa is root, don't bother
306 * setting him to red, just return.
310 RB_MARK_RED(grandpa
);
312 father
= RB_FATHER(self
);
313 if (RB_BLACK_P(father
)) {
315 * If our greatgrandpa is black, we're done.
322 * Case 2&3: our uncle is black.
324 if (self
== father
->rb_nodes
[other
]) {
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
331 __archive_rb_tree_reparent_nodes(father
, other
);
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.
339 __archive_rb_tree_reparent_nodes(grandpa
, which
);
342 * Final step: Set the root to black.
344 RB_MARK_BLACK(rbt
->rbt_root
);
348 __archive_rb_tree_prune_node(struct archive_rb_tree
*rbt
,
349 struct archive_rb_node
*self
, int rebalance
)
351 const unsigned int which
= RB_POSITION(self
);
352 struct archive_rb_node
*father
= RB_FATHER(self
);
355 * Since we are childless, we know that self->rb_left is pointing
356 * to the sentinel node.
358 father
->rb_nodes
[which
] = self
->rb_left
;
361 * Rebalance if requested.
364 __archive_rb_tree_removal_rebalance(rbt
, father
, which
);
368 * When deleting an interior node
371 __archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree
*rbt
,
372 struct archive_rb_node
*self
, struct archive_rb_node
*standin
)
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
);
380 if (standin_father
== self
) {
382 * As a child of self, any children would be opposite of
385 standin_son
= standin
->rb_nodes
[standin_which
];
388 * Since we aren't a child of self, any children would be
389 * on the same side as our parent.
391 standin_son
= standin
->rb_nodes
[standin_other
];
394 if (RB_RED_P(standin_son
)) {
396 * We know we have a red child so if we flip it to black
397 * we don't have to rebalance.
399 RB_MARK_BLACK(standin_son
);
402 if (standin_father
!= self
) {
404 * Change the son's parentage to point to his grandpa.
406 RB_SET_FATHER(standin_son
, standin_father
);
407 RB_SET_POSITION(standin_son
, standin_which
);
411 if (standin_father
== self
) {
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
423 * Have our son/standin adopt his brother as his new son.
425 standin_father
= standin
;
429 * | / \ | T --> / \ | / |
430 * | ..... | S --> ..... | T |
432 * Sever standin's connection to his father.
434 standin_father
->rb_nodes
[standin_which
] = standin_son
;
438 standin
->rb_nodes
[standin_other
] = self
->rb_nodes
[standin_other
];
439 RB_SET_FATHER(standin
->rb_nodes
[standin_other
], standin
);
441 * Use standin_other because we need to preserve standin_which
442 * for the removal_rebalance.
444 standin_other
= standin_which
;
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.
451 standin
->rb_nodes
[standin_other
] = self
->rb_nodes
[standin_other
];
452 RB_SET_FATHER(standin
->rb_nodes
[standin_other
], standin
);
455 * Now copy the result of self to standin and then replace
456 * self with standin in the tree.
458 RB_COPY_PROPERTIES(standin
, self
);
459 RB_SET_FATHER(standin
, RB_FATHER(self
));
460 RB_FATHER(standin
)->rb_nodes
[RB_POSITION(standin
)] = standin
;
463 __archive_rb_tree_removal_rebalance(rbt
, standin_father
, standin_which
);
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);
471 * But it's more efficient to just evaluate and recolor the child.
474 __archive_rb_tree_prune_blackred_branch(
475 struct archive_rb_node
*self
, unsigned int which
)
477 struct archive_rb_node
*father
= RB_FATHER(self
);
478 struct archive_rb_node
*son
= self
->rb_nodes
[which
];
481 * Remove ourselves from the tree and give our former child our
482 * properties (position, color, root).
484 RB_COPY_PROPERTIES(son
, self
);
485 father
->rb_nodes
[RB_POSITION(son
)] = son
;
486 RB_SET_FATHER(son
, father
);
492 __archive_rb_tree_remove_node(struct archive_rb_tree
*rbt
,
493 struct archive_rb_node
*self
)
495 struct archive_rb_node
*standin
;
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.
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.
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.
510 * The simplest case is a childless red node or a childless root node:
512 * | T --> T | or | R --> * |
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
);
520 if (!RB_TWOCHILDREN_P(self
)) {
522 * The next simplest case is the node we are deleting is
523 * black and has one red child.
529 which
= RB_LEFT_SENTINEL_P(self
) ? RB_DIR_RIGHT
: RB_DIR_LEFT
;
530 __archive_rb_tree_prune_blackred_branch(self
, which
);
535 * We invert these because we prefer to remove from the inside of
538 which
= RB_POSITION(self
) ^ RB_DIR_OTHER
;
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.
544 standin
= __archive_rb_tree_iterate(rbt
, self
, which
);
545 __archive_rb_tree_swap_prune_and_rebalance(rbt
, self
, standin
);
549 __archive_rb_tree_removal_rebalance(struct archive_rb_tree
*rbt
,
550 struct archive_rb_node
*parent
, unsigned int which
)
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
];
558 return;/* The tree may be broken. */
560 * For cases 1, 2a, and 2b, our brother's children must
561 * be black and our father must be black
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
)) {
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).
578 __archive_rb_tree_reparent_nodes(parent
, other
);
579 brother
= parent
->rb_nodes
[other
];
581 return;/* The tree may be broken. */
584 * Both our parent and brother are black.
585 * Change our brother to red, advance up rank
586 * and go through the loop again.
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
);
601 * Avoid an else here so that case 2a above can hit either
605 && RB_BLACK_P(brother
)
606 && RB_BLACK_P(brother
->rb_left
)
607 && RB_BLACK_P(brother
->rb_right
)) {
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
618 RB_MARK_BLACK(parent
);
619 RB_MARK_RED(brother
);
620 break; /* We're done! */
623 * Our brother must be black and have at least one
624 * red child (it may have two).
626 if (RB_BLACK_P(brother
->rb_nodes
[other
])) {
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).
638 __archive_rb_tree_reparent_nodes(brother
, which
);
639 brother
= parent
->rb_nodes
[other
];
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
650 * If the father is red, we will get a red-black-black
656 * If the father is black, we will get an all black
662 * If we had two red nephews, then after the swap,
663 * our former father would have a red grandson.
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! */
674 struct archive_rb_node
*
675 __archive_rb_tree_iterate(struct archive_rb_tree
*rbt
,
676 struct archive_rb_node
*self
, const unsigned int direction
)
678 const unsigned int other
= direction
^ RB_DIR_OTHER
;
681 self
= rbt
->rbt_root
;
682 if (RB_SENTINEL_P(self
))
684 while (!RB_SENTINEL_P(self
->rb_nodes
[direction
]))
685 self
= self
->rb_nodes
[direction
];
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.
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
);
702 * Advance down one in current direction and go down as far as possible
703 * in the opposite direction.
705 self
= self
->rb_nodes
[direction
];
706 while (!RB_SENTINEL_P(self
->rb_nodes
[other
]))
707 self
= self
->rb_nodes
[other
];