Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

[libucw.git] / lib / redblack.h

diff --git a/lib/redblack.h b/lib/redblack.h
index b0254c5992c88a3be92da5f12680545c2d638cd5..1776bedbcc20600138dee3decf4c3c3c2e443e6b 100644 (file)
--- a/lib/redblack.h
+++ b/lib/redblack.h
@@ -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,9 @@
  *                     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
@@ -412,6 +415,29 @@ 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)
 {
@@ -984,6 +1010,7 @@ 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