/*- * Copyright (c) 2001 The NetBSD Foundation, Inc. * All rights reserved. * * This code is derived from software contributed to The NetBSD Foundation * by Matt Thomas . * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. * * Based on: NetBSD: rb.c,v 1.6 2010/04/30 13:58:09 joerg Exp */ #include "archive_platform.h" #include #include "archive_rb.h" /* Keep in sync with archive_rb.h */ #define RB_DIR_LEFT 0 #define RB_DIR_RIGHT 1 #define RB_DIR_OTHER 1 #define rb_left rb_nodes[RB_DIR_LEFT] #define rb_right rb_nodes[RB_DIR_RIGHT] #define RB_FLAG_POSITION 0x2 #define RB_FLAG_RED 0x1 #define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED) #define RB_FATHER(rb) \ ((struct archive_rb_node *)((rb)->rb_info & ~RB_FLAG_MASK)) #define RB_SET_FATHER(rb, father) \ ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK))) #define RB_SENTINEL_P(rb) ((rb) == NULL) #define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left) #define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right) #define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb))) #define RB_CHILDLESS_P(rb) \ (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb))) #define RB_TWOCHILDREN_P(rb) \ (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb)) #define RB_POSITION(rb) \ (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT) #define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT) #define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT) #define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0) #define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0) #define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED)) #define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED)) #define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED)) #define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb)) #define RB_SET_POSITION(rb, position) \ ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \ ((rb)->rb_info &= ~RB_FLAG_POSITION))) #define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK)) #define RB_COPY_PROPERTIES(dst, src) \ ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK)) #define RB_SWAP_PROPERTIES(a, b) do { \ uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \ (a)->rb_info ^= xorinfo; \ (b)->rb_info ^= xorinfo; \ } while (/*CONSTCOND*/ 0) static void __archive_rb_tree_insert_rebalance(struct archive_rb_tree *, struct archive_rb_node *); static void __archive_rb_tree_removal_rebalance(struct archive_rb_tree *, struct archive_rb_node *, unsigned int); #define RB_SENTINEL_NODE NULL #define T 1 #define F 0 void __archive_rb_tree_init(struct archive_rb_tree *rbt, const struct archive_rb_tree_ops *ops) { rbt->rbt_ops = ops; *((struct archive_rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE; } struct archive_rb_node * __archive_rb_tree_find_node(struct archive_rb_tree *rbt, const void *key) { archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; struct archive_rb_node *parent = rbt->rbt_root; while (!RB_SENTINEL_P(parent)) { const signed int diff = (*compare_key)(parent, key); if (diff == 0) return parent; parent = parent->rb_nodes[diff > 0]; } return NULL; } struct archive_rb_node * __archive_rb_tree_find_node_geq(struct archive_rb_tree *rbt, const void *key) { archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; struct archive_rb_node *parent = rbt->rbt_root; struct archive_rb_node *last = NULL; while (!RB_SENTINEL_P(parent)) { const signed int diff = (*compare_key)(parent, key); if (diff == 0) return parent; if (diff < 0) last = parent; parent = parent->rb_nodes[diff > 0]; } return last; } struct archive_rb_node * __archive_rb_tree_find_node_leq(struct archive_rb_tree *rbt, const void *key) { archive_rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key; struct archive_rb_node *parent = rbt->rbt_root; struct archive_rb_node *last = NULL; while (!RB_SENTINEL_P(parent)) { const signed int diff = (*compare_key)(parent, key); if (diff == 0) return parent; if (diff > 0) last = parent; parent = parent->rb_nodes[diff > 0]; } return last; } int __archive_rb_tree_insert_node(struct archive_rb_tree *rbt, struct archive_rb_node *self) { archive_rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes; struct archive_rb_node *parent, *tmp; unsigned int position; int rebalance; tmp = rbt->rbt_root; /* * This is a hack. Because rbt->rbt_root is just a * struct archive_rb_node *, just like rb_node->rb_nodes[RB_DIR_LEFT], * we can use this fact to avoid a lot of tests for root and know * that even at root, updating * RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will * update rbt->rbt_root. */ parent = (struct archive_rb_node *)(void *)&rbt->rbt_root; position = RB_DIR_LEFT; /* * Find out where to place this new leaf. */ while (!RB_SENTINEL_P(tmp)) { const signed int diff = (*compare_nodes)(tmp, self); if (diff == 0) { /* * Node already exists; don't insert. */ return F; } parent = tmp; position = (diff > 0); tmp = parent->rb_nodes[position]; } /* * Initialize the node and insert as a leaf into the tree. */ RB_SET_FATHER(self, parent); RB_SET_POSITION(self, position); if (parent == (struct archive_rb_node *)(void *)&rbt->rbt_root) { RB_MARK_BLACK(self); /* root is always black */ rebalance = F; } else { /* * All new nodes are colored red. We only need to rebalance * if our parent is also red. */ RB_MARK_RED(self); rebalance = RB_RED_P(parent); } self->rb_left = parent->rb_nodes[position]; self->rb_right = parent->rb_nodes[position]; parent->rb_nodes[position] = self; /* * Rebalance tree after insertion */ if (rebalance) __archive_rb_tree_insert_rebalance(rbt, self); return T; } /* * Swap the location and colors of 'self' and its child @ which. The child * can not be a sentinel node. This is our rotation function. However, * since it preserves coloring, it great simplifies both insertion and * removal since rotation almost always involves the exchanging of colors * as a separate step. */ /*ARGSUSED*/ static void __archive_rb_tree_reparent_nodes( struct archive_rb_node *old_father, const unsigned int which) { const unsigned int other = which ^ RB_DIR_OTHER; struct archive_rb_node * const grandpa = RB_FATHER(old_father); struct archive_rb_node * const old_child = old_father->rb_nodes[which]; struct archive_rb_node * const new_father = old_child; struct archive_rb_node * const new_child = old_father; if (new_father == NULL) return; /* * Exchange descendant linkages. */ grandpa->rb_nodes[RB_POSITION(old_father)] = new_father; new_child->rb_nodes[which] = old_child->rb_nodes[other]; new_father->rb_nodes[other] = new_child; /* * Update ancestor linkages */ RB_SET_FATHER(new_father, grandpa); RB_SET_FATHER(new_child, new_father); /* * Exchange properties between new_father and new_child. The only * change is that new_child's position is now on the other side. */ RB_SWAP_PROPERTIES(new_father, new_child); RB_SET_POSITION(new_child, other); /* * Make sure to reparent the new child to ourself. */ if (!RB_SENTINEL_P(new_child->rb_nodes[which])) { RB_SET_FATHER(new_child->rb_nodes[which], new_child); RB_SET_POSITION(new_child->rb_nodes[which], which); } } static void __archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt, struct archive_rb_node *self) { struct archive_rb_node * father = RB_FATHER(self); struct archive_rb_node * grandpa; struct archive_rb_node * uncle; unsigned int which; unsigned int other; for (;;) { /* * We are red and our parent is red, therefore we must have a * grandfather and he must be black. */ grandpa = RB_FATHER(father); which = (father == grandpa->rb_right); other = which ^ RB_DIR_OTHER; uncle = grandpa->rb_nodes[other]; if (RB_BLACK_P(uncle)) break; /* * Case 1: our uncle is red * Simply invert the colors of our parent and * uncle and make our grandparent red. And * then solve the problem up at his level. */ RB_MARK_BLACK(uncle); RB_MARK_BLACK(father); if (RB_ROOT_P(rbt, grandpa)) { /* * If our grandpa is root, don't bother * setting him to red, just return. */ return; } RB_MARK_RED(grandpa); self = grandpa; father = RB_FATHER(self); if (RB_BLACK_P(father)) { /* * If our great-grandpa is black, we're done. */ return; } } /* * Case 2&3: our uncle is black. */ if (self == father->rb_nodes[other]) { /* * Case 2: we are on the same side as our uncle * Swap ourselves with our parent so this case * becomes case 3. Basically our parent becomes our * child. */ __archive_rb_tree_reparent_nodes(father, other); } /* * Case 3: we are opposite a child of a black uncle. * Swap our parent and grandparent. Since our grandfather * is black, our father will become black and our new sibling * (former grandparent) will become red. */ __archive_rb_tree_reparent_nodes(grandpa, which); /* * Final step: Set the root to black. */ RB_MARK_BLACK(rbt->rbt_root); } static void __archive_rb_tree_prune_node(struct archive_rb_tree *rbt, struct archive_rb_node *self, int rebalance) { const unsigned int which = RB_POSITION(self); struct archive_rb_node *father = RB_FATHER(self); /* * Since we are childless, we know that self->rb_left is pointing * to the sentinel node. */ father->rb_nodes[which] = self->rb_left; /* * Rebalance if requested. */ if (rebalance) __archive_rb_tree_removal_rebalance(rbt, father, which); } /* * When deleting an interior node */ static void __archive_rb_tree_swap_prune_and_rebalance(struct archive_rb_tree *rbt, struct archive_rb_node *self, struct archive_rb_node *standin) { const unsigned int standin_which = RB_POSITION(standin); unsigned int standin_other = standin_which ^ RB_DIR_OTHER; struct archive_rb_node *standin_son; struct archive_rb_node *standin_father = RB_FATHER(standin); int rebalance = RB_BLACK_P(standin); if (standin_father == self) { /* * As a child of self, any children would be opposite of * our parent. */ standin_son = standin->rb_nodes[standin_which]; } else { /* * Since we aren't a child of self, any children would be * on the same side as our parent. */ standin_son = standin->rb_nodes[standin_other]; } if (RB_RED_P(standin_son)) { /* * We know we have a red child so if we flip it to black * we don't have to rebalance. */ RB_MARK_BLACK(standin_son); rebalance = F; if (standin_father != self) { /* * Change the son's parentage to point to his grandpa. */ RB_SET_FATHER(standin_son, standin_father); RB_SET_POSITION(standin_son, standin_which); } } if (standin_father == self) { /* * If we are about to delete the standin's father, then when * we call rebalance, we need to use ourselves as our father. * Otherwise remember our original father. Also, since we are * our standin's father we only need to reparent the standin's * brother. * * | R --> S | * | Q S --> Q T | * | t --> | * * Have our son/standin adopt his brother as his new son. */ standin_father = standin; } else { /* * | R --> S . | * | / \ | T --> / \ | / | * | ..... | S --> ..... | T | * * Sever standin's connection to his father. */ standin_father->rb_nodes[standin_which] = standin_son; /* * Adopt the far son. */ standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; RB_SET_FATHER(standin->rb_nodes[standin_other], standin); /* * Use standin_other because we need to preserve standin_which * for the removal_rebalance. */ standin_other = standin_which; } /* * Move the only remaining son to our standin. If our standin is our * son, this will be the only son needed to be moved. */ standin->rb_nodes[standin_other] = self->rb_nodes[standin_other]; RB_SET_FATHER(standin->rb_nodes[standin_other], standin); /* * Now copy the result of self to standin and then replace * self with standin in the tree. */ RB_COPY_PROPERTIES(standin, self); RB_SET_FATHER(standin, RB_FATHER(self)); RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin; if (rebalance) __archive_rb_tree_removal_rebalance(rbt, standin_father, standin_which); } /* * We could do this by doing * __archive_rb_tree_node_swap(rbt, self, which); * __archive_rb_tree_prune_node(rbt, self, F); * * But it's more efficient to just evaluate and recolor the child. */ static void __archive_rb_tree_prune_blackred_branch( struct archive_rb_node *self, unsigned int which) { struct archive_rb_node *father = RB_FATHER(self); struct archive_rb_node *son = self->rb_nodes[which]; /* * Remove ourselves from the tree and give our former child our * properties (position, color, root). */ RB_COPY_PROPERTIES(son, self); father->rb_nodes[RB_POSITION(son)] = son; RB_SET_FATHER(son, father); } /* * */ void __archive_rb_tree_remove_node(struct archive_rb_tree *rbt, struct archive_rb_node *self) { struct archive_rb_node *standin; unsigned int which; /* * In the following diagrams, we (the node to be removed) are S. Red * nodes are lowercase. T could be either red or black. * * Remember the major axiom of the red-black tree: the number of * black nodes from the root to each leaf is constant across all * leaves, only the number of red nodes varies. * * Thus removing a red leaf doesn't require any other changes to a * red-black tree. So if we must remove a node, attempt to rearrange * the tree so we can remove a red node. * * The simplest case is a childless red node or a childless root node: * * | T --> T | or | R --> * | * | s --> * | */ if (RB_CHILDLESS_P(self)) { const int rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self); __archive_rb_tree_prune_node(rbt, self, rebalance); return; } if (!RB_TWOCHILDREN_P(self)) { /* * The next simplest case is the node we are deleting is * black and has one red child. * * | T --> T --> T | * | S --> R --> R | * | r --> s --> * | */ which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT; __archive_rb_tree_prune_blackred_branch(self, which); return; } /* * We invert these because we prefer to remove from the inside of * the tree. */ which = RB_POSITION(self) ^ RB_DIR_OTHER; /* * Let's find the node closes to us opposite of our parent * Now swap it with ourself, "prune" it, and rebalance, if needed. */ standin = __archive_rb_tree_iterate(rbt, self, which); __archive_rb_tree_swap_prune_and_rebalance(rbt, self, standin); } static void __archive_rb_tree_removal_rebalance(struct archive_rb_tree *rbt, struct archive_rb_node *parent, unsigned int which) { while (RB_BLACK_P(parent->rb_nodes[which])) { unsigned int other = which ^ RB_DIR_OTHER; struct archive_rb_node *brother = parent->rb_nodes[other]; if (brother == NULL) return;/* The tree may be broken. */ /* * For cases 1, 2a, and 2b, our brother's children must * be black and our father must be black */ if (RB_BLACK_P(parent) && RB_BLACK_P(brother->rb_left) && RB_BLACK_P(brother->rb_right)) { if (RB_RED_P(brother)) { /* * Case 1: Our brother is red, swap its * position (and colors) with our parent. * This should now be case 2b (unless C or E * has a red child which is case 3; thus no * explicit branch to case 2b). * * B -> D * A d -> b E * C E -> A C */ __archive_rb_tree_reparent_nodes(parent, other); brother = parent->rb_nodes[other]; if (brother == NULL) return;/* The tree may be broken. */ } else { /* * Both our parent and brother are black. * Change our brother to red, advance up rank * and go through the loop again. * * B -> *B * *A D -> A d * C E -> C E */ RB_MARK_RED(brother); if (RB_ROOT_P(rbt, parent)) return; /* root == parent == black */ which = RB_POSITION(parent); parent = RB_FATHER(parent); continue; } } /* * Avoid an else here so that case 2a above can hit either * case 2b, 3, or 4. */ if (RB_RED_P(parent) && RB_BLACK_P(brother) && RB_BLACK_P(brother->rb_left) && RB_BLACK_P(brother->rb_right)) { /* * We are black, our father is red, our brother and * both nephews are black. Simply invert/exchange the * colors of our father and brother (to black and red * respectively). * * | f --> F | * | * B --> * b | * | N N --> N N | */ RB_MARK_BLACK(parent); RB_MARK_RED(brother); break; /* We're done! */ } else { /* * Our brother must be black and have at least one * red child (it may have two). */ if (RB_BLACK_P(brother->rb_nodes[other])) { /* * Case 3: our brother is black, our near * nephew is red, and our far nephew is black. * Swap our brother with our near nephew. * This result in a tree that matches case 4. * (Our father could be red or black). * * | F --> F | * | x B --> x B | * | n --> n | */ __archive_rb_tree_reparent_nodes(brother, which); brother = parent->rb_nodes[other]; } /* * Case 4: our brother is black and our far nephew * is red. Swap our father and brother locations and * change our far nephew to black. (these can be * done in either order so we change the color first). * The result is a valid red-black tree and is a * terminal case. (again we don't care about the * father's color) * * If the father is red, we will get a red-black-black * tree: * | f -> f --> b | * | B -> B --> F N | * | n -> N --> | * * If the father is black, we will get an all black * tree: * | F -> F --> B | * | B -> B --> F N | * | n -> N --> | * * If we had two red nephews, then after the swap, * our former father would have a red grandson. */ if (brother->rb_nodes[other] == NULL) return;/* The tree may be broken. */ RB_MARK_BLACK(brother->rb_nodes[other]); __archive_rb_tree_reparent_nodes(parent, other); break; /* We're done! */ } } } struct archive_rb_node * __archive_rb_tree_iterate(struct archive_rb_tree *rbt, struct archive_rb_node *self, const unsigned int direction) { const unsigned int other = direction ^ RB_DIR_OTHER; if (self == NULL) { self = rbt->rbt_root; if (RB_SENTINEL_P(self)) return NULL; while (!RB_SENTINEL_P(self->rb_nodes[direction])) self = self->rb_nodes[direction]; return self; } /* * We can't go any further in this direction. We proceed up in the * opposite direction until our parent is in direction we want to go. */ if (RB_SENTINEL_P(self->rb_nodes[direction])) { while (!RB_ROOT_P(rbt, self)) { if (other == (unsigned int)RB_POSITION(self)) return RB_FATHER(self); self = RB_FATHER(self); } return NULL; } /* * Advance down one in current direction and go down as far as possible * in the opposite direction. */ self = self->rb_nodes[direction]; while (!RB_SENTINEL_P(self->rb_nodes[other])) self = self->rb_nodes[other]; return self; }