2007-12-17 Neal H. Walfield <neal@gnu.org>

	* btree.h (BTREE_(check_tree_internal)): Take additional
	parameter, the btree.  Update users.
	(BTREE_check_tree_internal_): Take additional parameter, the
	btree.  Update users.
	(BTREE_(find_internal)): Take additional parameter, may_overlap.
	If true, then don't break out when a matching node is found.
	Update users.
	(BTREE_(insert)): Take additional parameter, may_overlap.
	If true, don't require that nodes have a unique key.
	(BTREE_CLASS): Take additional parameter, may_overlap.  Generate
	stubs appropriate.
	* btree.c (BTREE_): New function.
	(check_tree_recurse): Take additional parameter, btree.  Update
	users.  Add additional tests.
	(BTREE_(check_tree_internal)): Take additional parameter, btree.
	Update users.
	* btree-test.c: Add tests for checking trees with overlapping keys.

4 files changed, 207 insertions, 57 deletions

diff --git a/libhurd-btree/ChangeLog b/libhurd-btree/ChangeLog
index 7641e24..377112f 100644
--- a/libhurd-btree/ChangeLog
+++ b/libhurd-btree/ChangeLog
@@ -1,5 +1,25 @@
 2007-12-17  Neal H. Walfield  <neal@gnu.org>
 
+	* btree.h (BTREE_(check_tree_internal)): Take additional
+	parameter, the btree.  Update users.
+	(BTREE_check_tree_internal_): Take additional parameter, the
+	btree.  Update users.
+	(BTREE_(find_internal)): Take additional parameter, may_overlap.
+	If true, then don't break out when a matching node is found.
+	Update users.
+	(BTREE_(insert)): Take additional parameter, may_overlap.  
+	If true, don't require that nodes have a unique key.
+	(BTREE_CLASS): Take additional parameter, may_overlap.  Generate
+	stubs appropriate.
+	* btree.c (BTREE_): New function.
+	(check_tree_recurse): Take additional parameter, btree.  Update
+	users.  Add additional tests.
+	(BTREE_(check_tree_internal)): Take additional parameter, btree.
+	Update users.
+	* btree-test.c: Add tests for checking trees with overlapping keys.
+
+2007-12-17  Neal H. Walfield  <neal@gnu.org>
+
 	* btree.c (DEBUGGING): Don't define.  Use !NDEBUG instead.
 	(BTREE_(check_tree_internal) [NDEBUG]): Define.
 	* btree.h (BTREE_check_tree_internal_): Define.  Update users to
diff --git a/libhurd-btree/btree-test.c b/libhurd-btree/btree-test.c
index 21b6a26..2107de6 100644
--- a/libhurd-btree/btree-test.c
+++ b/libhurd-btree/btree-test.c
@@ -23,7 +23,9 @@ struct int_node
   int key;
 };
 
-BTREE_CLASS(int_node, struct int_node, int, key, node, int_node_compare)
+BTREE_CLASS(int_node, struct int_node, int, key, node, int_node_compare, false)
+
+BTREE_CLASS(intd_node, struct int_node, int, key, node, int_node_compare, true)
 
 static int
 int_node_compare (const int *a, const int *b)
@@ -65,8 +67,8 @@ print_nodes (struct int_node *a, int depth)
 }
 
 #define A 0
-#define B 5000
-#define C 10000
+#define B 500
+#define C 1000
 
 int
 main (int argc, char *argv[])
@@ -520,6 +522,77 @@ main (int argc, char *argv[])
   node = hurd_btree_int_node_first (&root);
   assert (! node);
 
+  /* Test whether we can insert nodes with the same value into a true
+     with MAY_OVERLAP set to true.  */
+  hurd_btree_intd_node_t droot;
+  hurd_btree_intd_node_tree_init (&droot);
+
+  node = hurd_btree_intd_node_first (&droot);
+  assert (! node);
+
+  /* Insert 0, 1, ..., max - 1, 10 times.  */
+  const int max = 10;
+  for (i = 0; i < 10; i ++)
+    for (j = 0; j < max; j ++)
+      {
+	debug ("Inserting %d... ", j);
+	node = malloc (sizeof (struct int_node));
+	assert (node);
+
+	node->key = j;
+	ret = hurd_btree_intd_node_insert (&droot, node);
+	assert (! ret);
+
+	int cnt = 0;
+	node = hurd_btree_intd_node_first (&droot);
+	while (node)
+	  {
+	    /* Consider:
+
+	       We've added:
+
+	         0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2
+
+	       thus, max = 4, and i = 2, j = 2.
+
+	       As we traverse the list, we expect:
+	       
+	         0  1  2  3  4  5  6  7  8  9 10 11 12
+
+	         0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4
+		 \     /  \     /  \     /  \  /  \  /
+		 i+1 0's  i+1 1's  i+1 2's  i 3's  i 4's
+
+	       Thus, we expect that if CNT <= (i+1)*(j+1),
+
+	         key(node(cnt)) = cnt / (i + 1)
+
+	       e.g., 7 / (2 + 1) = 2, as expected
+
+	       Otherwise,
+
+	         key(node(cnt)) = j + 1 + ((cnt - ((i + 1) * (j + 1))) / i)
+
+	       e.g., 2 + 1 + ((11 - ((2 + 1) * (2 + 1))) / 2) = 4
+	    */
+
+	    if (i == 0)
+	      assert (node->key == cnt);
+	    else if (cnt <= (i + 1) * (j + 1))
+	      assert (node->key == cnt / (i + 1));
+	    else
+	      assert (node->key == j + 1 + ((cnt - ((i + 1) * (j + 1))) / i));
+	    cnt ++;
+
+	    struct int_node *next = hurd_btree_intd_node_next (node);
+	    if (next)
+	      assert (hurd_btree_intd_node_prev (next) == node);
+	    node = next;
+	  }
+	assert (cnt == max * i + j + 1);
+      }
+
+
   printf (". done\n"); fflush (stdout);
 
   return 0;
diff --git a/libhurd-btree/btree.c b/libhurd-btree/btree.c
index ce55c6e..a2ec3bb 100644
--- a/libhurd-btree/btree.c
+++ b/libhurd-btree/btree.c
@@ -157,7 +157,47 @@ typedef BTREE_(node_t) *node;
 #define CHECK_TREE(a) check_tree(a)
 
 static void
-check_tree_recurse (node p, BTREE_(key_compare_t) compare, size_t key_offset,
+dump_tree (node root, int indent)
+{
+  int i;
+  for (i = 0; i < indent; i ++)
+    printf (".");
+
+  char g = ' ';
+  if (root && BTREE_NP (root->parent)
+      && BTREE_NP (BTREE_NP (root->parent)->parent))
+    g = BTREE_NODE_RED_P (BTREE_NP (BTREE_NP (root->parent)->parent))
+      ? 'r' : 'b';
+
+  char p = ' ';
+  if (root && BTREE_NP (root->parent))
+    p = BTREE_NODE_RED_P (BTREE_NP (root->parent)) ? 'r' : 'b';
+
+  char n = root ? (BTREE_NODE_RED_P (root) ? 'r' : 'b') : ' ';
+
+  char l = ' ';
+  if (root && BTREE_NP_CHILD (root->left))
+    l = BTREE_NODE_RED_P (BTREE_NP_CHILD (root->left)) ? 'r' : 'b';
+  char r = ' ';
+  if (root && BTREE_NP_CHILD (root->right))
+    r = BTREE_NODE_RED_P (BTREE_NP_CHILD (root->right)) ? 'r' : 'b';
+
+  int bad = (p == 'r' && n == 'r')
+    || (n == 'r' && (l == 'r' || r == 'r'));
+
+  printf ("%p: %c (%c -> %c -> *%c* -> %c %c) %s\n",
+	  root, n, g, p, n, l, r, bad ? "***" : "");
+
+  if (! root)
+    return;
+
+  dump_tree (BTREE_NP_CHILD (root->left), indent + 1);
+  dump_tree (BTREE_NP_CHILD (root->right), indent + 1);
+}
+
+static void
+check_tree_recurse (BTREE_(t) *btree, node p,
+		    BTREE_(key_compare_t) compare, size_t key_offset,
 		    int d_sofar, int d_total, bool check_colors)
 {
   if (p == NULL)
@@ -167,60 +207,67 @@ check_tree_recurse (node p, BTREE_(key_compare_t) compare, size_t key_offset,
       return;
     }
 
-  check_tree_recurse (BTREE_NP_CHILD (p->left), compare, key_offset,
+  if (BTREE_NP_THREAD_P (p->left))
+    {
+      node orig_prev = BTREE_NP_THREAD (p->left);
+      BTREE_NP_CHILD_SET (&p->left, NULL);
+      node prev = BTREE_(prev_hard) (p);
+      assert (orig_prev == prev);
+      BTREE_NP_THREAD_SET (&p->left, prev);
+    }
+
+  if (BTREE_NP_THREAD_P (p->right))
+    {
+      node orig_next = BTREE_NP_THREAD (p->right);
+      BTREE_NP_CHILD_SET (&p->right, NULL);
+      node next = BTREE_(next_hard) (p);
+      assert (orig_next == next);
+      BTREE_NP_THREAD_SET (&p->right, next);
+    }
+
+  check_tree_recurse (btree, BTREE_NP_CHILD (p->left), compare, key_offset,
 		      d_sofar
 		      + (BTREE_NP_CHILD (p->left)
 			 && !BTREE_NODE_RED_P (BTREE_NP_CHILD (p->left))),
 		      d_total, check_colors);
-  check_tree_recurse (BTREE_NP_CHILD (p->right), compare, key_offset, 
+  check_tree_recurse (btree, BTREE_NP_CHILD (p->right), compare, key_offset, 
 		      d_sofar
 		      + (BTREE_NP_CHILD (p->right)
 			 && !BTREE_NODE_RED_P (BTREE_NP_CHILD (p->right))),
 		      d_total, check_colors);
   if (BTREE_NP_CHILD (p->left))
     {
+      if (BTREE_NODE_RED_P (BTREE_NP_CHILD (p->left))
+	  && BTREE_NODE_RED_P (p))
+	dump_tree (BTREE_NP (btree->root), 0);
       assert (!(BTREE_NODE_RED_P (BTREE_NP_CHILD (p->left))
 		&& BTREE_NODE_RED_P (p)));
       assert (BTREE_NP (BTREE_NP_CHILD (p->left)->parent) == p);
       if (compare)
 	assert (compare ((void *) BTREE_NP_CHILD (p->left) + key_offset,
-			 (void *) p + key_offset) < 0);
+			 (void *) p + key_offset) <= 0);
     }
   if (BTREE_NP_CHILD (p->right))
     {
+      if (BTREE_NODE_RED_P (BTREE_NP_CHILD (p->right))
+	  && BTREE_NODE_RED_P (p))
+	dump_tree (BTREE_NP (btree->root), 0);
       assert (!(BTREE_NODE_RED_P (BTREE_NP_CHILD (p->right))
 		&& BTREE_NODE_RED_P (p)));
       assert (BTREE_NP (BTREE_NP_CHILD (p->right)->parent) == p);
       if (compare)
 	assert (compare ((void *) BTREE_NP_CHILD (p->right) + key_offset,
-			 (void *) p + key_offset) > 0);
+			 (void *) p + key_offset) >= 0);
     }
   else
     /* If it doesn't have a child, then it better have a right
        thread.  */
     assert (BTREE_NP_THREAD_P (p->right));
-
-  if (BTREE_NP_THREAD_P (p->left))
-    {
-      node orig_prev = BTREE_NP_THREAD (p->left);
-      BTREE_NP_CHILD_SET (&p->left, NULL);
-      node prev = BTREE_(prev_hard) (p);
-      assert (orig_prev == prev);
-      BTREE_NP_THREAD_SET (&p->left, prev);
-    }
-
-  if (BTREE_NP_THREAD_P (p->right))
-    {
-      node orig_next = BTREE_NP_THREAD (p->right);
-      BTREE_NP_CHILD_SET (&p->right, NULL);
-      node next = BTREE_(next_hard) (p);
-      assert (orig_next == next);
-      BTREE_NP_THREAD_SET (&p->right, next);
-    }
 }
 
 void
-BTREE_(check_tree_internal) (node root, BTREE_(key_compare_t) compare,
+BTREE_(check_tree_internal) (BTREE_(t) *btree, node root,
+			     BTREE_(key_compare_t) compare,
 			     size_t key_offset, bool check_colors)
 {
   int cnt = 0;
@@ -231,7 +278,7 @@ BTREE_(check_tree_internal) (node root, BTREE_(key_compare_t) compare,
   if (check_colors)
     for(p = BTREE_NP_CHILD (root->left); p; p = BTREE_NP_CHILD (p->left))
       cnt += !BTREE_NODE_RED_P (p);
-  check_tree_recurse (root, compare, key_offset, 0, cnt, check_colors);
+  check_tree_recurse (btree, root, compare, key_offset, 0, cnt, check_colors);
 }
 
 
@@ -240,7 +287,8 @@ BTREE_(check_tree_internal) (node root, BTREE_(key_compare_t) compare,
 #define CHECK_TREE(a)
 
 static void
-BTREE_(check_tree_internal) (node root, BTREE_(key_compare_t) compare,
+BTREE_(check_tree_internal) (BTREE_(t) *btree, node root,
+			     BTREE_(key_compare_t) compare,
 			     size_t key_offset, bool check_colors)
 {
 }
@@ -894,7 +942,8 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
       for (; p && (child == NULL || !BTREE_NODE_RED_P (child));
 	   p = BTREE_NP (p->parent))
 	{
-	  BTREE_ (check_tree_internal) (BTREE_NP (btree->root), 0, 0, false);
+	  BTREE_ (check_tree_internal) (btree, BTREE_NP (btree->root),
+					0, 0, false);
 
 	  struct BTREE_(node_ptr) *pp = selfp (btree, p);
 
diff --git a/libhurd-btree/btree.h b/libhurd-btree/btree.h
index 47ac099..2f9ea0e 100644
--- a/libhurd-btree/btree.h
+++ b/libhurd-btree/btree.h
@@ -241,13 +241,14 @@ BTREE_(tree_init) (BTREE_(t) *btree)
    Internal function.  Perform a consistent check on the tree rooted
    at ROOT.  */
 #ifndef NDEBUG
-extern void BTREE_(check_tree_internal) (BTREE_(node_t) *root,
+extern void BTREE_(check_tree_internal) (BTREE_(t) *btree,
+					 BTREE_(node_t) *root,
 					 BTREE_(key_compare_t) compare,
 					 size_t key_offset, bool check_colors);
-#define BTREE_check_tree_internal_(r, c, k, cc) \
-  BTREE_(check_tree_internal) (r, c, k, cc)
+#define BTREE_check_tree_internal_(bt, r, c, k, cc)	\
+  BTREE_(check_tree_internal) (bt, r, c, k, cc)
 #else
-#define BTREE_check_tree_internal_(r, c, k, c) do { } while (0)
+#define BTREE_check_tree_internal_(bt, r, c, k, c) do { } while (0)
 #endif
 
 /* This is a private function do not call it from user code!
@@ -290,25 +291,30 @@ BTREE_(maybe_split_internal) (BTREE_(t) *tree, BTREE_(node_t) *node,
    be if it was in the tree) in *NODEPP, e.g. if KEY is larger than
    the parent's, *NODEPP is set to &(*parent)->right.  Returns
    (whether or not the node with KEY is found) the parent node in
-   *PARENT (or sets it to NULL if the tree is empty).  If no node is
-   found in the tree with key KEY, then *PREDP is set to the node with
-   the largest key which compares less than KEY or NULL if key is
-   smaller than all nodes in the tree.  *SUCCP is set similarly to
-   *PREDP expect that it points to the node with the smallest key
-   which compares greater than KEY or NULL if key is larger than all
-   nodes in the tree.  Returns 0 if found and ESRCH otherwise.  */
+   *PARENT (or sets it to NULL if the tree is empty).
+
+   If no node is found in the tree with key KEY, then *PREDP is set to
+   the node with the largest key which compares less than KEY or NULL
+   if key is smaller than all nodes in the tree.  *SUCCP is set
+   similarly to *PREDP expect that it points to the node with the
+   smallest key which compares greater than KEY or NULL if key is
+   larger than all nodes in the tree.  Returns 0 if found and ESRCH
+   otherwise.
+
+   If MAY_OVERLAP is true, then finds a slot to insert a node with key
+   KEY even if such a node already exists.  */
 BTREE_EXTERN_INLINE error_t
 BTREE_(find_internal) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 		       size_t key_offset, const void *key,
 		       struct BTREE_(node_ptr) **nodepp,
 		       BTREE_(node_t) **predp, BTREE_(node_t) **succp,
-		       BTREE_(node_t) **parentp);
+		       BTREE_(node_t) **parentp, bool may_overlap);
 BTREE_EXTERN_INLINE error_t
 BTREE_(find_internal) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 		       size_t key_offset, const void *key,
 		       struct BTREE_(node_ptr) **nodepp,
 		       BTREE_(node_t) **predp, BTREE_(node_t) **succp,
-		       BTREE_(node_t) **parentp)
+		       BTREE_(node_t) **parentp, bool may_overlap)
 {
   int r;
   error_t err = ESRCH;
@@ -324,7 +330,7 @@ BTREE_(find_internal) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
       BTREE_(node_t) *node = BTREE_NP (*nodep);
 
       r = compare (key, (void *) node + key_offset);
-      if (r == 0)
+      if (r == 0 && ! may_overlap)
 	/* Found it.  */
 	{
 	  err = 0;
@@ -368,7 +374,7 @@ BTREE_(find) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
   BTREE_(node_t) *node, *pred, *succ, *parent;
 
   err = BTREE_(find_internal) (btree, compare, key_offset, key,
-			       &nodep, &pred, &succ, &parent);
+			       &nodep, &pred, &succ, &parent, false);
   node = BTREE_NP_CHILD (*nodep);
   /* If not found, NODE will be NULL.  */
   assert ((err == ESRCH && ! node) || (err == 0 && node));
@@ -376,15 +382,15 @@ BTREE_(find) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 }
 
 /* Insert node NODE into btree BTREE.  COMPARE is the comparison
-   function.  NEWNODE's key must be valid.  If the node cannot be
-   inserted as a node with the key already exists, returns the node.
-   Otherwise, returns 0.  */
+   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
+   NEWNODE's key, such a node is returned.  Otherwise, returns 0.  */
 BTREE_EXTERN_INLINE BTREE_(node_t) *
 BTREE_(insert) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
-		size_t key_offset, BTREE_(node_t) *newnode);
+		size_t key_offset, bool may_overlap, BTREE_(node_t) *newnode);
 BTREE_EXTERN_INLINE BTREE_(node_t) *
 BTREE_(insert) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
-		size_t key_offset, BTREE_(node_t) *newnode)
+		size_t key_offset, bool may_overlap, BTREE_(node_t) *newnode)
 {
   error_t err;
   struct BTREE_(node_ptr) *nodep;
@@ -392,9 +398,10 @@ BTREE_(insert) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 
   err = BTREE_(find_internal) (btree, compare, key_offset,
 			       (void *) newnode + key_offset,
-			       &nodep, &pred, &succ, &parent);
+			       &nodep, &pred, &succ, &parent,
+			       may_overlap);
   if (! err)
-    /* Overlap!  Bail.  */
+    /* Overlap!  */
     {
       assert (! BTREE_NP_THREAD_P (*nodep));
       return BTREE_NP_CHILD (*nodep);
@@ -438,7 +445,7 @@ BTREE_(insert) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
        balancing later on.  */
     BTREE_NODE_RED_SET (newnode, false);
 
-  BTREE_check_tree_internal_ (BTREE_NP_CHILD (btree->root),
+  BTREE_check_tree_internal_ (btree, BTREE_NP_CHILD (btree->root),
 			      compare, key_offset, true);
 
   return 0;
@@ -587,7 +594,7 @@ BTREE_(prev) (BTREE_(node_t) *node)
      };
      
      BTREE_CLASS (int, struct my_int_node, int, key, node,
-                  my_int_node_compare)
+                  my_int_node_compare, false)
      
      int
      int_node_compare (const int *a, const int *b)
@@ -598,7 +605,7 @@ BTREE_(prev) (BTREE_(node_t) *node)
    Would make btree_int_node_find, btree_int_node_insert, etc.
    available.  */
 #define BTREE_CLASS(name, node_type, key_type, key_field,		\
-		    btree_node_field, cmp_function)			\
+		    btree_node_field, cmp_function, may_overlap)	\
 									\
 typedef struct								\
 {									\
@@ -634,7 +641,7 @@ BTREE_(name##_insert) (BTREE_(name##_t) *btree, node_type *newnode)	\
 		    (int (*) (const void *, const void *)) cmp,		\
 		    offsetof (node_type, key_field)			\
 		    - offsetof (node_type, btree_node_field),		\
-		    &newnode->btree_node_field);			\
+		    may_overlap, &newnode->btree_node_field);		\
 }									\
 									\
 static inline void							\
@@ -643,7 +650,8 @@ BTREE_(name##_detach) (BTREE_(name##_t) *btree, node_type *node)	\
   BTREE_(detach) (&btree->btree, &node->btree_node_field);		\
 									\
   int (*cmp) (const key_type *, const key_type *) = (cmp_function);	\
-  BTREE_check_tree_internal_ (BTREE_NP_CHILD (btree->btree.root),	\
+  BTREE_check_tree_internal_ (&btree->btree,				\
+			      BTREE_NP_CHILD (btree->btree.root),	\
 			      (BTREE_(key_compare_t)) cmp,		\
 			      offsetof (node_type, key_field)		\
 			      - offsetof (node_type, btree_node_field), \