X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fredblack.h;h=05544c36a04ac22503cca216cee4450c60108494;hb=8188ec7d7f7a806adf458a85d6099d0a1d3273ec;hp=2af759f1a65431b90832119cb7f9745d2551e15d;hpb=5fde39419d77b4d1c65ebafa3c8d6696d0e94426;p=libucw.git

diff --git a/lib/redblack.h b/lib/redblack.h
index 2af759f1..05544c36 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:
  *
@@ -68,6 +68,8 @@
  *			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_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.
@@ -410,6 +412,22 @@ STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
 }
 #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)
 {
@@ -966,6 +984,7 @@ do											\
 #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