/*
- * 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:
*
* A red-black tree is a binary search tree, where records are stored
* in nodes (may be also leaves). Every node has a colour. The
* following restrictions hold:
- *
+ *
* - a parent of a red node is black
* - every path from the root to a node with less than 2 children
* contains the same number of black nodes
* 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_SEARCH_DOWN node *search_down(key) -- find either the node with
+ * specified value, or if it does not exist, the node
+ * with nearest smaller value.
+ * 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_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
* undef'd.
*/
+#include <stdio.h>
#include <string.h>
#if !defined(TREE_NODE) || !defined(TREE_PREFIX)
#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 ((uintptr_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); }
+ { node->son[0] = (void*) ( (((uintptr_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 *) (((uintptr_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 *) ((uintptr_t) son | (((uintptr_t) node->son[id]) & 1L) ); }
#endif
/* Defaults for missing parameters. */
# 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)
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_SEARCH_DOWN
+STATIC P(node) * P(search_down) (T *t, TREE_KEY_DECL)
+{
+ P(node) *last_right=NULL;
+ P(bucket) *node=t->root;
+ while(node)
+ {
+ int cmp;
+ cmp = P(cmp) (TREE_KEY(), TREE_KEY(node->n.));
+ if (cmp == 0)
+ return &node->n;
+ else if (cmp < 0)
+ node=P(tree_son) (node, 0);
+ else
+ {
+ last_right=&node->n;
+ node=P(tree_son) (node, 1);
+ }
+ }
+ return last_right;
+}
+#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;
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);
{
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_SEARCH_DOWN
+#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
projects / libucw.git / blobdiff