X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fredblack.h;h=e278204856afa1c2ff6d4329fd013a2f666834d9;hb=e34560a76a7af3fb428604e4da3cd14cfd1bf454;hp=f140ea5efc14b4b232ab93b82bfd7a336455c9a1;hpb=b3524e137a080e8a37687347e1898cc1f0a91379;p=libucw.git

diff --git a/lib/redblack.h b/lib/redblack.h
index f140ea5e..e2782048 100644
--- a/lib/redblack.h
+++ b/lib/redblack.h
@@ -1,7 +1,7 @@
 /*
- *	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:
  *
@@ -15,7 +15,7 @@
  * 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
@@ -63,18 +63,25 @@
  *  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
@@ -104,9 +111,10 @@
  *  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
@@ -121,7 +129,7 @@
  *    }
  *  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
@@ -255,13 +263,13 @@ typedef struct P(stack_entry) {
 #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.  */
@@ -312,16 +320,29 @@ static inline void P(init_data) (P(node) *n UNUSED)
 #	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)
@@ -349,7 +370,7 @@ STATIC void P(cleanup) (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;
@@ -366,7 +387,7 @@ static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *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;
@@ -384,7 +405,7 @@ static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node,
 	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];
@@ -394,6 +415,45 @@ STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
 }
 #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)
 {
@@ -425,7 +485,7 @@ 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;
@@ -476,14 +536,17 @@ STATIC P(node) * P(search) (T *t, TREE_KEY_DECL)
 }
 #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
@@ -536,7 +599,7 @@ try_it_again:
 		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
@@ -561,14 +624,14 @@ try_it_again:
 		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);
@@ -658,7 +721,7 @@ missing_black:
 			{
 				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])
@@ -847,7 +910,7 @@ STATIC int P(delete) (T *t, TREE_KEY_DECL)
 #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;
@@ -864,7 +927,7 @@ static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket
 	{
 		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);
@@ -921,13 +984,12 @@ static P(node) * P(first_node) (T *t, uns direction)
 #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
@@ -948,6 +1010,8 @@ do											\
 #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
@@ -965,9 +1029,11 @@ do											\
 #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