fixes

[libucw.git] / lib / redblack.h

diff --git a/lib/redblack.h b/lib/redblack.h
index aacd744d4c97510adfddf1e349365683277ed532..05544c36a04ac22503cca216cee4450c60108494 100644 (file)
--- 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)
 {
@@ -940,13 +958,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 +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