Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

710 lines (649 sloc) 21.34 kb
/*-
* Copyright (c) 2001 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Matt Thomas <matt@3am-software.com>.
*
* 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 <stddef.h>
#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 greatgrandpa 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;
}
Jump to Line
Something went wrong with that request. Please try again.