X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fredblack.h;h=a89149b20afedaea67ff28ae7550fb634afa5c73;hb=08ec58075cd87236ea502c2c3b89e38126478167;hp=aacd744d4c97510adfddf1e349365683277ed532;hpb=08e5c05f94dc87662f79670a40ea2edcd2012e1e;p=libucw.git

diff --git a/lib/redblack.h b/lib/redblack.h
index aacd744d..a89149b2 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
@@ -68,6 +68,11 @@
  *			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_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.
@@ -131,6 +136,7 @@
  *  undef'd.
  */
 
+#include <stdio.h>
 #include <string.h>
 
 #if !defined(TREE_NODE) || !defined(TREE_PREFIX)
@@ -258,13 +264,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 ((addr_int_t) node->son[0]) & 1L; }
+	{ return ((uintptr_t) node->son[0]) & 1L; }
 	static inline void P(set_red_flag) (P(bucket) *node, uns flag)
-	{ (addr_int_t) node->son[0] = (((addr_int_t) 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 *) (((addr_int_t) 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 *) ((addr_int_t) son | (((addr_int_t) node->son[id]) & 1L) ); }
+	{ node->son[id] = (void *) ((uintptr_t) son | (((uintptr_t) node->son[id]) & 1L) ); }
 #endif
 
 /* Defaults for missing parameters.  */
@@ -410,6 +416,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)
 {
@@ -940,13 +985,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
@@ -967,6 +1011,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