Add a btree_find_first function.

2008-11-12  Neal H. Walfield  <neal@gnu.org>

	* btree.h (find_first): New function.
	(BTREE_CLASS): Generate a find_first function.
	* t-find-first.c (region_compare): New file.
	* Makefile.am (TESTS): Add t-find-first.
	(check_PROGRAMS): Likewise.
	(t_find_first_SOURCES): New variable.
	(t_find_first_CPPFLAGS): Likewise.

4 files changed, 264 insertions, 3 deletions

diff --git a/libhurd-btree/ChangeLog b/libhurd-btree/ChangeLog
index caa5035..3053627 100644
--- a/libhurd-btree/ChangeLog
+++ b/libhurd-btree/ChangeLog
@@ -1,3 +1,13 @@
+2008-11-12  Neal H. Walfield  <neal@gnu.org>
+
+	* btree.h (find_first): New function.
+	(BTREE_CLASS): Generate a find_first function.
+	* t-find-first.c (region_compare): New file.
+	* Makefile.am (TESTS): Add t-find-first.
+	(check_PROGRAMS): Likewise.
+	(t_find_first_SOURCES): New variable.
+	(t_find_first_CPPFLAGS): Likewise.
+
 2008-11-11  Neal H. Walfield  <neal@gnu.org>
 
 	* btree.c: Remove dead code.
diff --git a/libhurd-btree/Makefile.am b/libhurd-btree/Makefile.am
index ffd6656..7c4cf64 100644
--- a/libhurd-btree/Makefile.am
+++ b/libhurd-btree/Makefile.am
@@ -34,8 +34,11 @@ libhurd_btree_a_CFLAGS = $(USER_CFLAGS)
 endif
 libhurd_btree_a_SOURCES = btree.h btree.c
 
-TESTS = btree-test
+TESTS = btree-test t-find-first
 
-check_PROGRAMS = btree-test
+check_PROGRAMS = btree-test t-find-first
 btree_test_SOURCES = btree-test.c btree.h btree.c
 btree_test_CPPFLAGS = $(CHECK_CPPFLAGS)
+
+t_find_first_SOURCES = t-find-first.c btree.h btree.c
+t_find_first_CPPFLAGS = $(CHECK_CPPFLAGS)
diff --git a/libhurd-btree/btree.h b/libhurd-btree/btree.h
index 46d0cb3..8f08a6e 100644
--- a/libhurd-btree/btree.h
+++ b/libhurd-btree/btree.h
@@ -1,5 +1,5 @@
 /* Balanced tree insertion and deletion routines.
-   Copyright (C) 2004, 2007 Free Software Foundation, Inc.
+   Copyright (C) 2004, 2007, 2008 Free Software Foundation, Inc.
    Written by Neal H. Walfield <neal@gnu.org>.
 
    This file is part of the GNU Hurd.
@@ -381,6 +381,45 @@ BTREE_(find) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
   return node;
 }
 
+/* Given the set of nodes that compare equal to KEY according to
+   COMPARE, return the one that occurs lexically first according to
+   the tree's order.  Returns NULL .  */
+BTREE_EXTERN_INLINE BTREE_(node_t) *
+BTREE_(find_first) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
+		    size_t key_offset, const void *key);
+BTREE_EXTERN_INLINE BTREE_(node_t) *
+BTREE_(find_first) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
+		    size_t key_offset, const void *key)
+{
+  struct BTREE_(node_ptr) *nodep = &btree->root;
+  BTREE_(node_t) *first = NULL;
+
+  while (BTREE_NP_CHILD (*nodep))
+    {
+      /* We need NODE not because it is convenient but because if any
+	 rotations are done by BTREE_(maybe_split_internal) then the
+	 value it contains may be invalid.  */
+      BTREE_(node_t) *node = BTREE_NP (*nodep);
+
+      BTREE_(maybe_split_internal) (btree, node, 0);
+      /* If that did any rotations NODEP may now be garbage.  That
+	 doesn't matter, because the value it contains is never used
+	 again in that case.  */
+
+      int r = compare (key, (void *) node + key_offset);
+      if (r == 0)
+	/* NODE compares equal to KEY according to COMPARE.  It must
+	   be the smallest such key that we have seen so far.  */
+	first = node;
+
+      /* Node with a key matching KEY and which is smaller than NODE
+	 must be on the left if r <= 0 or right if r > 0.  */
+      nodep = r <= 0 ? &node->left : &node->right;
+    }
+
+  return first;
+}
+
 /* Insert node NODE into btree BTREE.  COMPARE is the comparison
    function.  NEWNODE's key must be valid.  If MAY_OVERLAP is not
    true, and there exists a node with a key that compares equal to
@@ -551,6 +590,8 @@ BTREE_(prev) (BTREE_(node_t) *node)
     Functions:
      void btree_NAME_tree_init (btree_NAME_t *btree, NODE_TYPE *node);
      NODE_TYPE *btree_NAME_find (btree_NAME_t *btree, const KEY_TYPE *key);
+     NODE_TYPE *btree_NAME_find_first (btree_NAME_t *btree,
+                                       const KEY_TYPE *key);
      NODE_TYPE *btree_NAME_insert (btree_NAME_t *btree, NODE_TYPE *newnode);
      void btree_NAME_detach (btree_NAME_t *btree, NODE_TYPE *node);
      NODE_TYPE *btree_NAME_first (btree_NAME_t *btree);
@@ -636,6 +677,20 @@ BTREE_(name##_find) (BTREE_(name##_t) *btree, const key_type *key)	\
 }									\
 									\
 static inline node_type *						\
+BTREE_(name##_find_first) (BTREE_(name##_t) *btree, const key_type *key) \
+{									\
+  int (*cmp) (const key_type *, const key_type *) = (cmp_function);	\
+  void *n = BTREE_(find_first)						\
+    (&btree->btree,							\
+     (int (*) (const void *, const void *)) cmp,			\
+     offsetof (node_type, key_field)					\
+     - offsetof (node_type, btree_node_field),				\
+     (const void *) key);						\
+									\
+  return n ? n - offsetof (node_type, btree_node_field) : NULL;		\
+}									\
+									\
+static inline node_type *						\
 BTREE_(name##_insert) (BTREE_(name##_t) *btree, node_type *newnode)	\
 {									\
   int (*cmp) (const key_type *, const key_type *) = (cmp_function);	\
diff --git a/libhurd-btree/t-find-first.c b/libhurd-btree/t-find-first.c
new file mode 100644
index 0000000..980a073
--- /dev/null
+++ b/libhurd-btree/t-find-first.c
@@ -0,0 +1,193 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include <errno.h>
+#include <stddef.h>
+#include <string.h>
+
+#include "btree.h"
+
+char *program_name = "btree-test";
+
+int output_debug;
+
+// #define DEBUG
+#ifdef DEBUG
+# ifndef debug
+#  define debug(level, fmt, ...)				\
+  if (level <= output_debug)					\
+    {								\
+      printf (fmt "\n", ##__VA_ARGS__);				\
+      fflush (stddout);						\
+    }
+# else
+#  define debug(level, fmt, ...) do { } while (0)
+# endif
+#endif
+
+struct region
+{
+  uintptr_t start;
+  uintptr_t length;
+};
+
+/* Compare two regions.  Two regions are considered equal if there is
+   any overlap at all.  */
+static int
+region_compare (const struct region *a, const struct region *b)
+{
+  uintptr_t a_end = a->start + (a->length - 1);
+  uintptr_t b_end = b->start + (b->length - 1);
+
+  int ret = 0;
+  if (a_end < b->start)
+    ret = -1;
+  if (a->start > b_end)
+    ret = 1;
+
+  debug (5, "%d+%d %s %d+%d\n",
+	 a->start, a_end,
+	 ret == 0 ? "==" : ret == -1 ? "<" : ">",
+	 b->start, b_end);
+
+  return ret;
+}
+
+struct region_node
+{
+  hurd_btree_node_t node;
+  struct region region;
+};
+
+BTREE_CLASS(region_node, struct region_node, struct region, region, node,
+	    region_compare, true)
+
+void
+print_node (struct region_node *a)
+{
+  printf ("%d+%d%s(%d)",
+	  a->region.start, a->region.start + a->region.length - 1,
+	  BTREE_NODE_RED_P (&a->node) ? "r" : "b",
+	  BTREE_NP (a->node.parent)
+	  ? ((struct region_node *) BTREE_NP (a->node.parent))->region.start
+	  : -1);
+}
+
+bool
+do_print_nodes (struct region_node *a, int depth)
+{
+  bool saw_one = false;
+  if (depth > 0)
+    {
+      if (a)
+	{
+	  struct region_node *l, *r;
+	  l = (struct region_node *) BTREE_NP_CHILD (a->node.left);
+	  r = (struct region_node *) BTREE_NP_CHILD (a->node.right);
+
+	  saw_one = do_print_nodes (l, depth - 1);
+	  saw_one |= do_print_nodes (r, depth - 1);
+	}
+      else
+	{
+	  do_print_nodes (NULL, depth - 1);
+	  do_print_nodes (NULL, depth - 1);
+	}
+    }
+  else
+    {
+      if (a)
+	{
+	  print_node (a);
+	  saw_one = true;
+	}
+      else
+	printf ("NULL");
+      printf (" ");
+    }
+
+  return saw_one;
+}
+
+void
+print_nodes (struct region_node *a, int depth)
+{
+  int i;
+  bool saw_one = true;
+  for (i = 0; i < depth && saw_one; i ++)
+    {
+      saw_one = do_print_nodes (a, i);
+      printf ("\n");
+    }
+}
+
+int
+main (int argc, char *argv[])
+{
+  hurd_btree_region_node_t root;
+  hurd_btree_region_node_tree_init (&root);
+
+  /* 0-5, 2-7, 4-9, ...  */
+#define COUNT 100
+#define LENGTH 5
+
+  int i;
+  for (i = 0; i < 100; i += 2)
+    {
+      struct region_node *node = calloc (sizeof (struct region_node), 1);
+      assert (node);
+      node->region.start = i;
+      node->region.length = 5;
+      struct region_node *conflict
+	= hurd_btree_region_node_insert (&root, node);
+      assert (! conflict);
+
+      int j;
+      for (j = 0; j <= i + 10; j ++)
+	{
+	  struct region region;
+	  region.start = j;
+	  region.length = 20;
+
+	  node = hurd_btree_region_node_find_first (&root, &region);
+
+	  if (node)
+	    debug (5, "Searching for %d-%d and got %d-%d",
+		   region.start, region.start + region.length - 1,
+		   node->region.start,
+		   node->region.start + node->region.length - 1);
+	  else
+	    debug (5, "Searching for %d-%d and got NULL",
+		   region.start, region.start + region.length - 1);
+
+	  if (j >= 0 && j <= i + LENGTH - 1)
+	    {
+	      int expect = j - LENGTH + 1;
+	      if (expect < 0)
+		expect = 0;
+	      if (expect % 2 == 1)
+		expect ++;
+
+	      debug (5, "Expected %d-%d", expect, expect + LENGTH - 1);
+	      if (! node || node->region.start != expect)
+		{
+		  print_nodes (BTREE_NP (root.btree.root), 6);
+		  printf ("\n");
+		  fflush (stdout);
+		}
+
+	      assert (node);
+	      assert (node->region.start == expect);
+	    }
+	  else
+	    {
+	      debug (5, "Expected NULL");
+	      assert (! node);
+	    }
+	}
+    }
+
+  return 0;
+}
+
+