/*
- * Red-black trees
+ * UCW Library -- Red-black trees
*
- * (c) 2002, Robert Spalek <robert@ucw.cz>
+ * (c) 2002--2005, Robert Spalek <robert@ucw.cz>
*
* Skeleton based on hash-tables by:
*
* TREE_WANT_CLEANUP cleanup() -- deallocate the tree.
* TREE_WANT_FIND node *find(key) -- find first node with the specified
* key, return NULL if no such node exists.
- * TREE_WANT_FIND_NEXT node *find(node *start) -- find next node with the
+ * TREE_WANT_FIND_NEXT node *find_next(node *start) -- find next node with the
* specified key, return NULL if no such node exists.
+ * Implies TREE_DUPLICATES.
* TREE_WANT_SEARCH node *search(key) -- find the node with the specified
* or, if it does not exist, the nearest one.
- * TREE_WANT_ADJACENT node *adjacent(node *) -- finds next/previous node.
+ * TREE_WANT_BOUNDARY node *boundary(uns direction) -- finds smallest
+ * (direction==0) or largest (direction==1) node.
+ * TREE_WANT_ADJACENT node *adjacent(node *, uns direction) -- finds next
+ * (direction==1) or previous (direction==0) node.
* TREE_WANT_NEW node *new(key) -- create new node with given key.
* If it already exists, it is created as the last one.
* TREE_WANT_LOOKUP node *lookup(key) -- find node with given key,
* if it doesn't exist, create it. Defining
* TREE_GIVE_INIT_DATA is strongly recommended.
* TREE_WANT_DELETE int delete(key) -- delete and deallocate node
- * with given key. Returns success.
+ * with a given key. Returns success.
* TREE_WANT_REMOVE remove(node *) -- delete and deallocate given node.
*
* TREE_WANT_DUMP dump() -- dumps the whole tree to stdout
* TREE_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
* TREE_USE_POOL=pool Allocate all nodes from given mempool.
* Collides with delete/remove functions.
- * TREE_STATIC Functions are declared as static.
+ * TREE_GLOBAL Functions are exported (i.e., not static).
* TREE_CONSERVE_SPACE Use as little space as possible at the price of a
* little slowdown.
+ * TREE_DUPLICATES Records with duplicate keys are allowed.
* TREE_MAX_DEPTH Maximal depth of a tree (for stack allocation).
*
* If you set TREE_WANT_ITERATOR, you also get a iterator macro at no
* }
* TREE_END_FOR;
*
- * Then include <lib/redblack.h> and voila, you have a tree suiting all your
+ * Then include "lib/redblack.h" and voila, you have a tree suiting all your
* needs (at least those which you've revealed :) ).
*
* After including this file, all parameter macros are automatically
#else
/* Pointers are aligned, hence we can use lower bits. */
static inline uns P(red_flag) (P(bucket) *node)
- { return ((long) node->son[0]) & 1L; }
+ { return ((addr_int_t) node->son[0]) & 1L; }
static inline void P(set_red_flag) (P(bucket) *node, uns flag)
- { (long) node->son[0] = (((long) node->son[0]) & ~1L) | (flag & 1L); }
+ { (addr_int_t) node->son[0] = (((addr_int_t) node->son[0]) & ~1L) | (flag & 1L); }
static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
- { return (void *) (((long) node->son[id]) & ~1L); }
+ { return (void *) (((addr_int_t) node->son[id]) & ~1L); }
static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
- { node->son[id] = (void *) ((long) son | (((long) node->son[id]) & 1L) ); }
+ { node->son[id] = (void *) ((addr_int_t) son | (((addr_int_t) node->son[id]) & 1L) ); }
#endif
/* Defaults for missing parameters. */
# define TREE_SAFE_FREE(x) P(free) (x)
#endif
-#ifdef TREE_STATIC
-# define STATIC static
-#else
+#ifdef TREE_GLOBAL
# define STATIC
+#else
+# define STATIC static
#endif
#ifndef TREE_MAX_DEPTH
# define TREE_MAX_DEPTH 64
#endif
+#if defined(TREE_WANT_FIND_NEXT) && !defined(TREE_DUPLICATES)
+# define TREE_DUPLICATES
+#endif
+
+#ifdef TREE_WANT_LOOKUP
+#ifndef TREE_WANT_FIND
+# define TREE_WANT_FIND
+#endif
+#ifndef TREE_WANT_NEW
+# define TREE_WANT_NEW
+#endif
+#endif
+
/* Now the operations */
STATIC void P(init) (T *t)
}
#endif
-static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, TREE_KEY_DECL, uns son_id)
+static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, TREE_KEY_DECL, uns son_id UNUSED)
{
uns i;
stack[0].buck = node;
ASSERT(i+1 < max_depth);
stack[i+1].buck = P(tree_son) (stack[i].buck, stack[i].son);
}
-#ifdef TREE_WANT_FIND_NEXT
+#ifdef TREE_DUPLICATES
if (stack[i].buck)
{
uns idx;
return i;
}
-#if defined(TREE_WANT_FIND) || defined(TREE_WANT_LOOKUP)
+#ifdef TREE_WANT_FIND
STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
{
P(stack_entry) stack[TREE_MAX_DEPTH];
}
#endif
+#ifdef TREE_WANT_BOUNDARY
+STATIC P(node) * P(boundary) (T *t, uns direction)
+{
+ P(bucket) *n = t->root, *ns;
+ if (!n)
+ return NULL;
+ else
+ {
+ uns son = !!direction;
+ while ((ns = P(tree_son) (n, son)))
+ n = ns;
+ return &n->n;
+ }
+}
+#endif
+
#ifdef TREE_STORE_PARENT
STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
{
}
#endif
-#if defined(TREE_WANT_FIND_NEXT) || defined(TREE_WANT_DELETE) || defined(TREE_WANT_REMOVE)
+#if defined(TREE_DUPLICATES) || defined(TREE_WANT_DELETE) || defined(TREE_WANT_REMOVE)
static int P(find_next_node) (P(stack_entry) *stack, uns max_depth, uns direction)
{
uns depth = 0;
}
#endif
-//#define TRACE(txt...) do { printf(txt); fflush(stdout); } while (0)
-#define TRACE(txt...)
+#if 0
+#define TREE_TRACE(txt...) do { printf(txt); fflush(stdout); } while (0)
+#else
+#define TREE_TRACE(txt...)
+#endif
static inline P(bucket) * P(rotation) (P(bucket) *node, uns son_id)
{
/* Destroys red_flag's in node, son. Returns new root. */
P(bucket) *son = P(tree_son) (node, son_id);
- TRACE("Rotation (node %d, son %d), direction %d\n", node->n.key, son->n.key, son_id);
+ TREE_TRACE("Rotation (node %d, son %d), direction %d\n", node->n.key, son->n.key, son_id);
node->son[son_id] = P(tree_son) (son, 1-son_id);
son->son[1-son_id] = node;
#ifdef TREE_STORE_PARENT
P(set_red_flag) (uncle, 0);
P(set_red_flag) (grand, 1);
depth -= 2;
- TRACE("Swapping colours (parent %d, uncle %d, grand %d), passing thru\n", parent->n.key, uncle->n.key, grand->n.key);
+ TREE_TRACE("Swapping colours (parent %d, uncle %d, grand %d), passing thru\n", parent->n.key, uncle->n.key, grand->n.key);
goto try_it_again;
}
/* Black uncle and grandparent, we need to rotate. Test
t->root = node;
}
-#if defined(TREE_WANT_NEW) || defined(TREE_WANT_LOOKUP)
+#ifdef TREE_WANT_NEW
STATIC P(node) * P(new) (T *t, TREE_KEY_DECL)
{
P(stack_entry) stack[TREE_MAX_DEPTH];
P(bucket) *added;
uns depth;
depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);
-#ifdef TREE_WANT_FIND_NEXT
+#ifdef TREE_DUPLICATES
/* It is the last found value, hence everything in the right subtree is
* strongly _bigger_. */
depth += P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);
{
depth--;
iteration++;
- TRACE("Swapping colours (parent %d, sibling %d), passing thru\n", parent->n.key, sibling->n.key);
+ TREE_TRACE("Swapping colours (parent %d, sibling %d), passing thru\n", parent->n.key, sibling->n.key);
goto missing_black;
}
} else if (!red[del_son])
#endif
#ifdef TREE_WANT_DUMP
-static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket) *parent, int cmp_res, int level, int black)
+static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket) *parent, int cmp_res, int level, uns black)
{
uns flag;
int i;
{
ASSERT(!flag || !P(red_flag) (parent));
cmp_res *= P(cmp) (TREE_KEY(node->n.), TREE_KEY(parent->n.));
-#ifdef TREE_WANT_FIND_NEXT
+#ifdef TREE_DUPLICATES
ASSERT(cmp_res >= 0);
#else
ASSERT(cmp_res > 0);
#define TREE_FOR_ALL(t_px, t_ptr, t_var) \
do \
{ \
- TREE_GLUE(t_px,node) *t_var = TREE_GLUE(t_px,first_node)(t_ptr, 0); \
- for (; t_var; t_var = TREE_GLUE(t_px,adjacent)(t_var, 1)) \
+ GLUE_(t_px,node) *t_var = GLUE_(t_px,first_node)(t_ptr, 0); \
+ for (; t_var; t_var = GLUE_(t_px,adjacent)(t_var, 1)) \
{
#define TREE_END_FOR } } while(0)
#define TREE_BREAK break
#define TREE_CONTINUE continue
-#define TREE_GLUE(x,y) x##_##y
#endif
#endif
#undef TREE_WANT_FIND
#undef TREE_WANT_FIND_NEXT
#undef TREE_WANT_SEARCH
+#undef TREE_WANT_BOUNDARY
#undef TREE_WANT_ADJACENT
#undef TREE_WANT_NEW
#undef TREE_WANT_LOOKUP
#undef TREE_USE_POOL
#undef TREE_STATIC
#undef TREE_CONSERVE_SPACE
+#undef TREE_DUPLICATES
#undef TREE_MAX_DEPTH
#undef TREE_STORE_PARENT
#undef TREE_KEY
#undef TREE_EXTRA_SIZE
#undef TREE_SAFE_FREE
+#undef TREE_TRACE
#undef STATIC