/*-
* Copyright (C) 2006 Jason Evans .
* All rights reserved.
*
* 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(s), this list of conditions and the following disclaimer as
* the first lines of this file unmodified other than the possible
* addition of one or more copyright notices.
* 2. Redistributions in binary form must reproduce the above copyright
* notice(s), 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 COPYRIGHT HOLDER(S) ``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 COPYRIGHT HOLDER(S) 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.
*******************************************************************************
*
* cpp macro implementation of red-black trees. Red-black trees are difficult
* to explain without lots of diagrams, so little attempt is made to document
* this code. However, an excellent discussion can be found in the following
* book, which was used as the reference for writing this implementation:
*
* Introduction to Algorithms
* Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest
* MIT Press (1990)
* ISBN 0-07-013143-0
*
* Some macros use a comparison function pointer, which is expected to have the
* following prototype:
*
* int (compare *)( *a_a, *a_b);
*
* Interpretation of comparision function return values:
*
* -1 : a_a < a_b
* 0 : a_a == a_b
* 1 : a_a > a_b
*
* Some of the macros expand out to be quite a bit of code, so if they are
* called in a program in more than a couple of places for a particular type, it
* is probably a good idea to create functions that wrap the macros to keep code
* size down.
*
*******************************************************************************
*/
/* Node structure. */
#define rb_node(a_type) struct { \
a_type *rbn_par; \
a_type *rbn_left; \
a_type *rbn_right; \
bool rbn_red; \
}
#define rb_node_new(a_tree, a_node, a_field) do { \
(a_node)->a_field.rbn_par = &(a_tree)->rbt_nil; \
(a_node)->a_field.rbn_left = &(a_tree)->rbt_nil; \
(a_node)->a_field.rbn_right = &(a_tree)->rbt_nil; \
(a_node)->a_field.rbn_red = false; \
} while (0)
/* Root structure. */
#define rb_tree(a_type) struct { \
a_type *rbt_root; \
a_type rbt_nil; \
}
#define rb_tree_new(a_tree, a_field) do { \
(a_tree)->rbt_root = &((a_tree)->rbt_nil); \
rb_node_new(a_tree, &(a_tree)->rbt_nil, a_field); \
} while (0)
#define rb_tree_nil(a_tree) (&(a_tree)->rbt_nil)
/* Operations. */
#define rb_root(a_tree) (a_tree)->rbt_root
#define rb_p_first(a_tree, a_root, a_field, r_node) do { \
for ((r_node) = (a_root); \
(r_node)->a_field.rbn_left != &(a_tree)->rbt_nil; \
(r_node) = (r_node)->a_field.rbn_left); \
} while (0)
#define rb_p_last(a_tree, a_root, a_field, r_node) do { \
for ((r_node) = (a_root); \
(r_node)->a_field.rbn_right != &(a_tree)->rbt_nil; \
(r_node) = (r_node)->a_field.rbn_right); \
} while (0)
#define rb_first(a_tree, a_field, r_node) \
rb_p_first(a_tree, rb_root(a_tree), a_field, r_node)
#define rb_last(a_tree, a_field, r_node) \
rb_p_last(a_tree, rb_root(a_tree), a_field, r_node)
#define rb_next(a_tree, a_node, a_type, a_field, r_node) do { \
if ((a_node)->a_field.rbn_right != &(a_tree)->rbt_nil) { \
rb_p_first(a_tree, (a_node)->a_field.rbn_right, \
a_field, r_node); \
} else { \
a_type *t = (a_node); \
(r_node) = (a_node)->a_field.rbn_par; \
while ((r_node) != &(a_tree)->rbt_nil \
&& t == (r_node)->a_field.rbn_right) { \
t = (r_node); \
(r_node) = (r_node)->a_field.rbn_par; \
} \
} \
} while (0)
#define rb_prev(a_tree, a_node, a_type, a_field, r_node) do { \
if ((a_node)->a_field.rbn_left != &(a_tree)->rbt_nil) { \
rb_p_last(a_tree, (a_node)->a_field.rbn_left, \
a_field, r_node); \
} else { \
a_type *t = (a_node); \
(r_node) = (a_node)->a_field.rbn_par; \
while ((r_node) != &(a_tree)->rbt_nil \
&& t == (r_node)->a_field.rbn_left) { \
t = (r_node); \
(r_node) = (r_node)->a_field.rbn_par; \
} \
} \
} while (0)
/* a_key is always the first argument to a_comp. */
#define rb_search(a_tree, a_key, a_comp, a_field, r_node) do { \
int t; \
(r_node) = (a_tree)->rbt_root; \
while ((r_node) != &(a_tree)->rbt_nil \
&& (t = (a_comp)((a_key), (r_node))) != 0) { \
if (t == -1) \
(r_node) = (r_node)->a_field.rbn_left; \
else \
(r_node) = (r_node)->a_field.rbn_right; \
} \
} while (0)
/*
* Find a match if it exists. Otherwise, find the next greater node, if one
* exists.
*/
#define rb_nsearch(a_tree, a_key, a_comp, a_type, a_field, r_node) do { \
int t; \
(r_node) = (a_tree)->rbt_root; \
while ((r_node) != &(a_tree)->rbt_nil \
&& (t = (a_comp)((a_key), (r_node))) != 0) { \
if (t == -1) { \
if ((r_node)->a_field.rbn_left == \
&(a_tree)->rbt_nil) \
break; \
(r_node) = (r_node)->a_field.rbn_left; \
} else { \
if ((r_node)->a_field.rbn_right \
== &(a_tree)->rbt_nil) { \
a_type *n = (r_node); \
(r_node) = (r_node)->a_field.rbn_par; \
while ((r_node) != &(a_tree)->rbt_nil &&\
n == (r_node)->a_field.rbn_right) { \
n = (r_node); \
(r_node) = \
(r_node)->a_field.rbn_par; \
} \
break; \
} \
(r_node) = (r_node)->a_field.rbn_right; \
} \
} \
} while (0)
#define rb_p_left_rotate(a_tree, a_node, a_type, a_field) do { \
a_type *t = (a_node)->a_field.rbn_right; \
(a_node)->a_field.rbn_right = t->a_field.rbn_left; \
if (t->a_field.rbn_left != &(a_tree)->rbt_nil) \
t->a_field.rbn_left->a_field.rbn_par = (a_node); \
t->a_field.rbn_par = (a_node)->a_field.rbn_par; \
if ((a_node)->a_field.rbn_par == &(a_tree)->rbt_nil) \
(a_tree)->rbt_root = t; \
else if ((a_node) \
== (a_node)->a_field.rbn_par->a_field.rbn_left) \
(a_node)->a_field.rbn_par->a_field.rbn_left = t; \
else \
(a_node)->a_field.rbn_par->a_field.rbn_right = t; \
t->a_field.rbn_left = (a_node); \
(a_node)->a_field.rbn_par = t; \
} while (0)
#define rb_p_right_rotate(a_tree, a_node, a_type, a_field) do { \
a_type *t = (a_node)->a_field.rbn_left; \
(a_node)->a_field.rbn_left = t->a_field.rbn_right; \
if (t->a_field.rbn_right != &(a_tree)->rbt_nil) \
t->a_field.rbn_right->a_field.rbn_par = (a_node); \
t->a_field.rbn_par = (a_node)->a_field.rbn_par; \
if ((a_node)->a_field.rbn_par == &(a_tree)->rbt_nil) \
(a_tree)->rbt_root = t; \
else if ((a_node) \
== (a_node)->a_field.rbn_par->a_field.rbn_right) \
(a_node)->a_field.rbn_par->a_field.rbn_right = t; \
else \
(a_node)->a_field.rbn_par->a_field.rbn_left = t; \
t->a_field.rbn_right = (a_node); \
(a_node)->a_field.rbn_par = t; \
} while (0)
/* a_node is always the first argument to a_comp. */
#define rb_insert(a_tree, a_node, a_comp, a_type, a_field) do { \
/* Insert. */ \
a_type *x = &(a_tree)->rbt_nil; \
a_type *y = (a_tree)->rbt_root; \
int c; \
while (y != &(a_tree)->rbt_nil) { \
x = y; \
c = (a_comp)((a_node), y); \
if (c == -1) \
y = y->a_field.rbn_left; \
else \
y = y->a_field.rbn_right; \
} \
(a_node)->a_field.rbn_par = x; \
if (x == &(a_tree)->rbt_nil) \
(a_tree)->rbt_root = (a_node); \
else if (c == -1) \
x->a_field.rbn_left = (a_node); \
else \
x->a_field.rbn_right = (a_node); \
/* Fix up. */ \
x = (a_node); \
x->a_field.rbn_red = true; \
while (x != (a_tree)->rbt_root \
&& x->a_field.rbn_par->a_field.rbn_red) { \
y = x->a_field.rbn_par; \
if (y == y->a_field.rbn_par->a_field.rbn_left) { \
y = y->a_field.rbn_par->a_field.rbn_right; \
if (y->a_field.rbn_red) { \
x->a_field.rbn_par->a_field.rbn_red = \
false; \
y->a_field.rbn_red = false; \
x->a_field.rbn_par->a_field.rbn_par \
->a_field.rbn_red = true; \
x = x->a_field.rbn_par->a_field.rbn_par;\
} else { \
if (x == x->a_field.rbn_par \
->a_field.rbn_right) { \
x = x->a_field.rbn_par; \
rb_p_left_rotate(a_tree, x, \
a_type, a_field); \
} \
x->a_field.rbn_par->a_field.rbn_red = \
false; \
x->a_field.rbn_par->a_field.rbn_par \
->a_field.rbn_red = true; \
x = x->a_field.rbn_par->a_field.rbn_par;\
rb_p_right_rotate(a_tree, x, a_type, \
a_field); \
} \
} else { \
y = y->a_field.rbn_par->a_field.rbn_left; \
if (y->a_field.rbn_red) { \
x->a_field.rbn_par->a_field.rbn_red = \
false; \
y->a_field.rbn_red = false; \
x->a_field.rbn_par->a_field.rbn_par \
->a_field.rbn_red = true; \
x = x->a_field.rbn_par->a_field.rbn_par;\
} else { \
if (x == x->a_field.rbn_par \
->a_field.rbn_left) { \
x = x->a_field.rbn_par; \
rb_p_right_rotate(a_tree, x, \
a_type, a_field); \
} \
x->a_field.rbn_par->a_field.rbn_red = \
false; \
x->a_field.rbn_par->a_field.rbn_par \
->a_field.rbn_red = true; \
x = x->a_field.rbn_par->a_field.rbn_par;\
rb_p_left_rotate(a_tree, x, a_type, \
a_field); \
} \
} \
} \
(a_tree)->rbt_root->a_field.rbn_red = false; \
} while (0)
#define rb_remove(a_tree, a_node, a_type, a_field) do { \
bool fixup; \
a_type *x, *y; \
if ((a_node)->a_field.rbn_left == &(a_tree)->rbt_nil \
|| (a_node)->a_field.rbn_right == &(a_tree)->rbt_nil) \
y = (a_node); \
else \
rb_next(a_tree, a_node, a_type, a_field, y); \
if (y->a_field.rbn_left != &(a_tree)->rbt_nil) \
x = y->a_field.rbn_left; \
else \
x = y->a_field.rbn_right; \
x->a_field.rbn_par = y->a_field.rbn_par; \
if (y->a_field.rbn_par == &(a_tree)->rbt_nil) \
(a_tree)->rbt_root = x; \
else if (y == y->a_field.rbn_par->a_field.rbn_left) \
y->a_field.rbn_par->a_field.rbn_left = x; \
else \
y->a_field.rbn_par->a_field.rbn_right = x; \
if (y->a_field.rbn_red == false) \
fixup = true; \
else \
fixup = false; \
if (y != (a_node)) { \
/* Splice y into a_node's location. */ \
y->a_field.rbn_par = (a_node)->a_field.rbn_par; \
y->a_field.rbn_left = (a_node)->a_field.rbn_left; \
y->a_field.rbn_right = (a_node)->a_field.rbn_right; \
y->a_field.rbn_red = (a_node)->a_field.rbn_red; \
if (y->a_field.rbn_par != &(a_tree)->rbt_nil) { \
if (y->a_field.rbn_par->a_field.rbn_left == \
(a_node)) { \
y->a_field.rbn_par->a_field.rbn_left = \
y; \
} else { \
y->a_field.rbn_par->a_field.rbn_right = \
y; \
} \
} else \
(a_tree)->rbt_root = y; \
y->a_field.rbn_right->a_field.rbn_par = y; \
y->a_field.rbn_left->a_field.rbn_par = y; \
} \
rb_node_new(a_tree, a_node, a_field); \
if (fixup) { \
/* Fix up. */ \
a_type *v, *w; \
while (x != (a_tree)->rbt_root \
&& x->a_field.rbn_red == false) { \
if (x == x->a_field.rbn_par->a_field.rbn_left) {\
w = x->a_field.rbn_par \
->a_field.rbn_right; \
if (w->a_field.rbn_red) { \
w->a_field.rbn_red = false; \
v = x->a_field.rbn_par; \
v->a_field.rbn_red = true; \
rb_p_left_rotate(a_tree, v, \
a_type, a_field); \
w = x->a_field.rbn_par \
->a_field.rbn_right; \
} \
if (w->a_field.rbn_left->a_field.rbn_red\
== false && w->a_field.rbn_right \
->a_field.rbn_red == false) { \
w->a_field.rbn_red = true; \
x = x->a_field.rbn_par; \
} else { \
if (w->a_field.rbn_right \
->a_field.rbn_red == \
false) { \
w->a_field.rbn_left \
->a_field.rbn_red \
= false; \
w->a_field.rbn_red = \
true; \
rb_p_right_rotate( \
a_tree, w, a_type, \
a_field); \
w = x->a_field.rbn_par \
->a_field.rbn_right;\
} \
w->a_field.rbn_red \
= x->a_field.rbn_par \
->a_field.rbn_red; \
x->a_field.rbn_par \
->a_field.rbn_red = false; \
w->a_field.rbn_right \
->a_field.rbn_red = false; \
v = x->a_field.rbn_par; \
rb_p_left_rotate(a_tree, v, \
a_type, a_field); \
break; \
} \
} \
else \
{ \
w = x->a_field.rbn_par \
->a_field.rbn_left; \
if (w->a_field.rbn_red) { \
w->a_field.rbn_red = false; \
v = x->a_field.rbn_par; \
v->a_field.rbn_red = true; \
rb_p_right_rotate(a_tree, v, \
a_type, a_field); \
w = x->a_field.rbn_par \
->a_field.rbn_left; \
} \
if (w->a_field.rbn_right \
->a_field.rbn_red == false && \
w->a_field.rbn_left->a_field.rbn_red\
== false) { \
w->a_field.rbn_red = true; \
x = x->a_field.rbn_par; \
} else { \
if (w->a_field.rbn_left \
->a_field.rbn_red \
== false) { \
w->a_field.rbn_right \
->a_field.rbn_red \
= false; \
w->a_field.rbn_red = \
true; \
rb_p_left_rotate(a_tree,\
w, a_type, a_field);\
w = x->a_field.rbn_par \
->a_field.rbn_left; \
} \
w->a_field.rbn_red = \
x->a_field.rbn_par \
->a_field.rbn_red; \
x->a_field.rbn_par \
->a_field.rbn_red = false; \
w->a_field.rbn_left \
->a_field.rbn_red = false; \
v = x->a_field.rbn_par; \
rb_p_right_rotate(a_tree, v, \
a_type, a_field); \
break; \
} \
} \
} \
x->a_field.rbn_red = false; \
} \
} while (0)
|
