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

	* btree.h (struct BTREE_(node_ptr)): New structure.
	(struct BTREE_(node_pptr)): Likewise.
	(struct BTREE_(node)): Make parent a struct BTREE_(node_pptr).
	left a struct BTREE_(node_ptr).  Likewise for right.  Fold red
	into the parent field.  Update all users.
	(BTREE_NP): New macro.
	(BTREE_NP_SET): Likewise.
	(BTREE_NP_THREAD_P): Likewise.
	(BTREE_NP_THREAD_P_SET): Likewise.
	(BTREE_NP_THREAD): Likewise.
	(BTREE_NP_THREAD_SET): Likewise.
	(BTREE_NP_CHILD): Likewise.
	(BTREE_NP_CHILD_SET): Likewise.
	(BTREE_NODE_RED_P): Likewise.
	(BTREE_NODE_RED_SET): Likewise.
	(struct BTREE_(t)): Make root a struct BTREE_(node_ptr).
	(BTREE_(link_internal)): Remove function.
	(BTREE_(check_tree_internal)): New declaration.
	(BTREE_(insert)): Make NEWNODE->LEFT a thread.  Call
	BTREE_(check_tree_internal).
	(BTREE_(prev_hard)): New declaration.
	(BTREE_(prev)): New function.
	(BTREE_CLASS:detach): Call BTREE_(check_tree_internal).
	* btree.c (BTREE_): Take additional parameter, check_colors.
	Update callers.  If COMPARE is NULL, don't compare values.  Check
	if the threads are correct.
	(BTREE_(check_tree_internal)): Take additional parameter,
	check_colors.
	(BTREE_(next_hard)): Remove static qualifier.
	(BTREE_(prev)): Rename from this...
	(BTREE_(prev_hard)): ... to this.  If
	(selfp): Change return type to a struct BTREE_(node_ptr) *.
	Update users.
	(BTREE_(detach)): Also adjust the left thread as appropriate.

3 files changed, 592 insertions, 380 deletions

diff --git a/libhurd-btree/ChangeLog b/libhurd-btree/ChangeLog
index 671ab45..5917646 100644
--- a/libhurd-btree/ChangeLog
+++ b/libhurd-btree/ChangeLog
@@ -1,5 +1,42 @@
 2007-12-17  Neal H. Walfield  <neal@gnu.org>
 
+	* btree.h (struct BTREE_(node_ptr)): New structure.
+	(struct BTREE_(node_pptr)): Likewise.
+	(struct BTREE_(node)): Make parent a struct BTREE_(node_pptr).
+	left a struct BTREE_(node_ptr).  Likewise for right.  Fold red
+	into the parent field.  Update all users.
+	(BTREE_NP): New macro.
+	(BTREE_NP_SET): Likewise.
+	(BTREE_NP_THREAD_P): Likewise.
+	(BTREE_NP_THREAD_P_SET): Likewise.
+	(BTREE_NP_THREAD): Likewise.
+	(BTREE_NP_THREAD_SET): Likewise.
+	(BTREE_NP_CHILD): Likewise.
+	(BTREE_NP_CHILD_SET): Likewise.
+	(BTREE_NODE_RED_P): Likewise.
+	(BTREE_NODE_RED_SET): Likewise.
+	(struct BTREE_(t)): Make root a struct BTREE_(node_ptr).
+	(BTREE_(link_internal)): Remove function.
+	(BTREE_(check_tree_internal)): New declaration.
+	(BTREE_(insert)): Make NEWNODE->LEFT a thread.  Call
+	BTREE_(check_tree_internal).
+	(BTREE_(prev_hard)): New declaration.
+	(BTREE_(prev)): New function.
+	(BTREE_CLASS:detach): Call BTREE_(check_tree_internal).
+	* btree.c (BTREE_): Take additional parameter, check_colors.
+	Update callers.  If COMPARE is NULL, don't compare values.  Check
+	if the threads are correct.
+	(BTREE_(check_tree_internal)): Take additional parameter,
+	check_colors.
+	(BTREE_(next_hard)): Remove static qualifier.
+	(BTREE_(prev)): Rename from this...
+	(BTREE_(prev_hard)): ... to this.  If
+	(selfp): Change return type to a struct BTREE_(node_ptr) *.
+	Update users.
+	(BTREE_(detach)): Also adjust the left thread as appropriate.
+
+2007-12-17  Neal H. Walfield  <neal@gnu.org>
+
 	* Makefile.am (AM_CPPFLAGS): Add -D_GNU_SOURCE.
 	(TESTS): New variable.
 	(check_PROGRAMS): Likewise.
diff --git a/libhurd-btree/btree.c b/libhurd-btree/btree.c
index 1ee85cd..0efb600 100644
--- a/libhurd-btree/btree.c
+++ b/libhurd-btree/btree.c
@@ -149,7 +149,7 @@ typedef const struct node_t *const_node;
 typedef BTREE_(node_t) *node;
 
 #undef DEBUGGING
-// #define DEBUGGING
+#define DEBUGGING
 #ifdef DEBUGGING
 
 /* Routines to check tree invariants.  */
@@ -160,47 +160,80 @@ typedef BTREE_(node_t) *node;
 
 static void
 check_tree_recurse (node p, BTREE_(key_compare_t) compare, size_t key_offset,
-		    int d_sofar, int d_total)
+		    int d_sofar, int d_total, bool check_colors)
 {
   if (p == NULL)
     {
-      assert (d_sofar == d_total);
+      if (check_colors)
+	assert (d_sofar == d_total);
       return;
     }
 
-  check_tree_recurse (p->left, compare, key_offset,
-		      d_sofar + (p->left && !p->left->red), d_total);
-  check_tree_recurse (BTREE_(link_internal) (p->right), compare, key_offset, 
-		      d_sofar + (BTREE_(link_internal) (p->right)
-				 && !p->right->red), d_total);
-  if (p->left)
+  check_tree_recurse (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, 
+		      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))
     {
-      assert (!(p->left->red && p->red));
-      assert (p->left->parent == p);
-      assert (compare ((void *) p->left + key_offset,
-		       (void *) p + key_offset) < 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);
     }
-  if (BTREE_(link_internal) (p->right))
+  if (BTREE_NP_CHILD (p->right))
     {
-      assert (!(p->right->red && p->red));
-      assert (p->right->parent == p);
-      assert (compare ((void *) p->right + key_offset,
-		       (void *) p + key_offset) > 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);
+    }
+  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,
-			     size_t key_offset)
+			     size_t key_offset, bool check_colors)
 {
   int cnt = 0;
   node p;
   if (root == NULL)
     return;
-  root->red = 0;
-  for(p = root->left; p; p = p->left)
-    cnt += !p->red;
-  check_tree_recurse (root, compare, key_offset, 0, cnt);
+  BTREE_NODE_RED_SET (root, 0);
+  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);
 }
 
 
@@ -214,12 +247,12 @@ BTREE_(check_tree_internal) (node root, BTREE_(key_compare_t) compare,
    (i.e. largest) node in the tree.  The tree needs to be sane,
    however, unlike with BTREE_(next), leaf nodes may have right pointers
    which are NULL.  */
-static BTREE_(node_t) *
+BTREE_(node_t) *
 BTREE_(next_hard) (BTREE_(node_t) *node)
 {
-  if (((uintptr_t) node->right & 1) == 1)
+  if (BTREE_NP_THREAD_P (node->right))
     /* We have a right thread, use it.  */
-    return (BTREE_(node_t) *) (((uintptr_t) node->right) & ~1);
+    return BTREE_NP_THREAD (node->right);
 
   /* If NODE has a right child node then the left most child of
      NODE->RIGHT is the next node.
@@ -231,11 +264,11 @@ BTREE_(next_hard) (BTREE_(node_t) *node)
      The node after 2 is 3, the node after 4 is 5, the node after 6 is
      7. */
   /* NODE->RIGHT must be a link.  */
-  if (node->right)
+  if (BTREE_NP_CHILD (node->right))
     {
-      node = node->right;
-      while (node->left)
-	node = node->left;
+      node = BTREE_NP_CHILD (node->right);
+      while (BTREE_NP_CHILD (node->left))
+	node = BTREE_NP_CHILD (node->left);
       return node;
     }
 
@@ -246,31 +279,36 @@ BTREE_(next_hard) (BTREE_(node_t) *node)
                 O
 
      In either case, NODE is the last node.  */
-  if (! node->parent)
+  if (! BTREE_NP (node->parent))
     return NULL;
 
   /* If NODE is the left child node of its parent (and NODE has no
      right nodes) then the parent is the next node.  The node after 1
      is 2, the node after 5 is 6.  */
-  if (node->parent->left == node)
-    return node->parent;
+  if (BTREE_NP_CHILD (BTREE_NP (node->parent)->left) == node)
+    return BTREE_NP (node->parent);
 
   /* If NODE is the right node of its parent (and NODE has no right
      nodes and is not the left not of its parent) then the parent of
      the first ancestor which is a left node of its parent is the next
      node.  The node after 3 is 4.  */
-  assert (node->parent->right == node);
+  assert (BTREE_NP_CHILD (BTREE_NP (node->parent)->right) == node);
 
-  while (node->parent && node == node->parent->right)
-    node = node->parent;
-  return node->parent;
+  while (BTREE_NP (node->parent)
+	 && node == BTREE_NP_CHILD (BTREE_NP (node->parent)->right))
+    node = BTREE_NP (node->parent);
+  return BTREE_NP (node->parent);
 }
 
 /* Return the node preceding node NODE or NULL if NODE is the first
    (i.e. smallest) node in the tree.  */
 BTREE_(node_t) *
-BTREE_(prev) (BTREE_(node_t) *node)
+BTREE_(prev_hard) (BTREE_(node_t) *node)
 {
+  if (BTREE_NP_THREAD_P (node->left))
+    /* We have a left thread, use it.  */
+    return BTREE_NP_THREAD (node->left);
+
   /* If NODE has a left child node then the right most child of it
      (NODE->RIGHT) is the previous node.
 
@@ -279,11 +317,11 @@ BTREE_(prev) (BTREE_(node_t) *node)
                    1   3   5   7
 
      The node before 2 is 1, 4 is 3, 6 is 5. */
-  if (node->left)
+  if (BTREE_NP_CHILD (node->left))
     {
-      node = node->left;
-      while (BTREE_(link_internal) (node->right))
-	node = BTREE_(link_internal) (node->right);
+      node = BTREE_NP_CHILD (node->left);
+      while (BTREE_NP_CHILD (node->right))
+	node = BTREE_NP_CHILD (node->right);
       return node;
     }
 
@@ -294,42 +332,44 @@ BTREE_(prev) (BTREE_(node_t) *node)
                     O
 
      In either case, NODE is the first node.  */
-  if (! node->parent)
+  if (! BTREE_NP (node->parent))
     return NULL;
 
   /* If NODE is the right child node of its parent (and NODE has no
      right nodes) then the parent is the next node.  The node before 3
      is 2, the node before 7 is 6.  */
-  if (node->parent->right == node)
-    return node->parent;
+  if (BTREE_NP_CHILD (BTREE_NP (node->parent)->right) == node)
+    return BTREE_NP (node->parent);
 
   /* If NODE is the left node of its parent (and NODE has no left
      nodes and is not the right not of its parent) then the parent of
      the first ancestor which is a right node of its parent is the
      next node.  The node before 3 is 4.  */
-  assert (node->parent->left == node);
+  assert (BTREE_NP_CHILD (BTREE_NP (node->parent)->left) == node);
 
-  while (node->parent && node == node->parent->left)
-    node = node->parent;
-  return node->parent;
+  while (BTREE_NP (node->parent)
+	 && node == BTREE_NP_CHILD (BTREE_NP (node->parent)->left))
+    node = BTREE_NP (node->parent);
+  return BTREE_NP (node->parent);
 }
 
-static BTREE_(node_t) **
+/* Return the location of the NODE's parent's child pointer that
+   designates NODE, i.e., either &node->parent->left,
+   &node->parent->right, or &root.  */
+static struct BTREE_(node_ptr) *
 selfp (BTREE_(t) *btree, BTREE_(node_t) *node)
 {
-  assert (((uintptr_t) node & 1) == 0);
-
-  if (! node->parent)
+  if (! BTREE_NP (node->parent))
     {
-      assert (btree->root == node);
+      assert (BTREE_NP (btree->root) == node);
       return &btree->root;
     }
-  else if (node->parent->left == node)
-    return &node->parent->left;
+  else if (BTREE_NP_CHILD (BTREE_NP (node->parent)->left) == node)
+    return &BTREE_NP (node->parent)->left;
   else
     {
-      assert (node->parent->right == node);
-      return &node->parent->right;
+      assert (BTREE_NP_CHILD (BTREE_NP (node->parent)->right) == node);
+      return &BTREE_NP (node->parent)->right;
     }
 }
 
@@ -337,59 +377,59 @@ selfp (BTREE_(t) *btree, BTREE_(node_t) *node)
    edges in a row.  ROOTP is a pointer to the lowest node we visited, PARENTP
    and GPARENTP pointers to its parent/grandparent.  P_R and GP_R contain the
    comparison values that determined which way was taken in the tree to reach
-   ROOTP.  MODE is 1 if we need not do the split, but must check for two red
+   ROOTP.  MODE is 0 if we need not do the split, but must check for two red
    edges between GPARENTP and ROOTP.  */
 void
 BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
 {
-  node *rp, *lp;
+  struct BTREE_(node_ptr) *rp, *lp;
   rp = &root->right;
   lp = &root->left;
 
-  /* Make sure we didn't get a right thread.  */
-  assert (((uintptr_t) root & 1) == 0);
-
   /* See if we have to split this node (both successors red).  */
   if (mode == 1
-      || (BTREE_(link_internal) (*rp) && (*lp) && (*rp)->red && (*lp)->red))
+      || (BTREE_NP_CHILD (*rp) && BTREE_NP_CHILD (*lp)
+	  && BTREE_NODE_RED_P (BTREE_NP_CHILD (*rp))
+	  && BTREE_NODE_RED_P (BTREE_NP_CHILD (*lp))))
     {
       /* This node becomes red, its successors black.  */
-      root->red = 1;
-      if (BTREE_(link_internal) (*rp))
-	(*rp)->red = 0;
-      if (*lp)
-	(*lp)->red = 0;
+      BTREE_NODE_RED_SET (root, 1);
+      if (BTREE_NP_CHILD (*rp))
+	BTREE_NODE_RED_SET (BTREE_NP_CHILD (*rp), 0);
+      if (BTREE_NP_CHILD (*lp))
+	BTREE_NODE_RED_SET (BTREE_NP_CHILD (*lp), 0);
 
       /* If the parent of this node is also red, we have to do
 	 rotations.  */
-      if (root->parent && root->parent->red)
+      if (BTREE_NP (root->parent)
+	  && BTREE_NODE_RED_P (BTREE_NP (root->parent)))
 	{
 	  node gp, p;
-	  node *parentp, *gparentp;
+	  struct BTREE_(node_ptr) *parentp, *gparentp;
 	  int p_r, gp_r;
 
-	  p = root->parent;
+	  p = BTREE_NP (root->parent);
 	  /* P cannot be the root of the tree: it is red and the root
 	     is black.  */
-	  assert (p->parent);
+	  assert (BTREE_NP (p->parent));
 
 	  /* Avoid a branch.  -1 is left, 1 is right.  */
-	  p_r = (p->right == root) * 2 - 1;
+	  p_r = (BTREE_NP_CHILD (p->right) == root) * 2 - 1;
 
-	  if (p->parent->left == p)
+	  if (BTREE_NP_CHILD (BTREE_NP (p->parent)->left) == p)
 	    {
-	      parentp = &p->parent->left;
+	      parentp = &BTREE_NP (p->parent)->left;
 	      gp_r = -1;
 	    }
 	  else
 	    {
-	      assert (p->parent->right == p);
-	      parentp = &p->parent->right;
+	      assert (BTREE_NP_CHILD (BTREE_NP (p->parent)->right) == p);
+	      parentp = &BTREE_NP (p->parent)->right;
 	      gp_r = 1;
 	    }
 
 	  /* P must have a parent since it cannot be the root.  */
-	  gp = p->parent;
+	  gp = BTREE_NP (p->parent);
 	  assert (gp);
 	  gparentp = selfp (btree, gp);
 
@@ -402,12 +442,12 @@ BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
 	    {
 	      /* Put the child at the top of the tree, with its parent
 		 and grandparent as successors.  */
-	      p->red = 1;
-	      gp->red = 1;
-	      root->red = 0;
+	      BTREE_NODE_RED_SET (p, 1);
+	      BTREE_NODE_RED_SET (gp, 1);
+	      BTREE_NODE_RED_SET (root, 0);
 
-	      *gparentp = root;
-	      root->parent = gp->parent;
+	      BTREE_NP_CHILD_SET (gparentp, root);
+	      BTREE_NP_SET (&root->parent, BTREE_NP (gp->parent));
 
 	      if (p_r < 0)
 		{
@@ -420,24 +460,22 @@ BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
                      root        l  r
                      /  \
                     l    r */
-		  p->left = BTREE_(link_internal) (*rp);
-		  if (p->left)
-		    p->left->parent = p;
+		  BTREE_NP_CHILD_SET (&p->left, BTREE_NP_CHILD (*rp));
+		  if (BTREE_NP_CHILD (p->left))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (p->left)->parent, p);
 
-		  *rp = p;
-		  p->parent = root;
+		  BTREE_NP_CHILD_SET (rp, p);
+		  BTREE_NP_SET (&p->parent, root);
 
-		  gp->right = *lp;
-		  if (gp->right)
-		    gp->right->parent = gp;
+		  BTREE_NP_CHILD_SET (&gp->right, BTREE_NP_CHILD (*lp));
+		  if (BTREE_NP_CHILD (gp->right))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (gp->right)->parent, gp);
 
-		  *lp = gp;
-		  gp->parent = root;
+		  BTREE_NP_CHILD_SET (lp, gp);
+		  BTREE_NP_SET (&gp->parent, root);
 
-		  if (! gp->right)
-		    gp->right
-		      = (BTREE_(node_t) *) ((uintptr_t ) BTREE_(next_hard) (gp)
-					    | 1);
+		  if (! BTREE_NP_CHILD (gp->right))
+		    BTREE_NP_THREAD_SET (&gp->right, BTREE_(next_hard) (gp));
 		}
 	      else
 		{
@@ -450,35 +488,33 @@ BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
                      root        l  r
                      /  \
                     l    r */
-		  p->right = *lp;
-		  if (p->right)
-		    p->right->parent = p;
+		  BTREE_NP_CHILD_SET (&p->right, BTREE_NP_CHILD (*lp));
+		  if (BTREE_NP_CHILD (p->right))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (p->right)->parent, p);
 
-		  *lp = p;
-		  p->parent = root;
+		  BTREE_NP_CHILD_SET (lp, p);
+		  BTREE_NP_SET (&p->parent, root);
 
-		  gp->left = BTREE_(link_internal) (*rp);
-		  if (gp->left)
-		    gp->left->parent = gp;
+		  BTREE_NP_CHILD_SET (&gp->left, BTREE_NP_CHILD (*rp));
+		  if (BTREE_NP_CHILD (gp->left))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (gp->left)->parent, gp);
 
-		  *rp = gp;
-		  gp->parent = root;
+		  BTREE_NP_CHILD_SET (rp, gp);
+		  BTREE_NP_SET (&gp->parent, root);
 
-		  if (! p->right)
-		    p->right
-		      = (BTREE_(node_t) *) ((uintptr_t ) BTREE_(next_hard) (p)
-					    | 1);
+		  if (! BTREE_NP_CHILD (p->right))
+		    BTREE_NP_THREAD_SET (&p->right, BTREE_(next_hard) (p));
 		}
 	    }
 	  else
 	    {
 	      /* Parent becomes the top of the tree, grandparent and
 		 child are its successors.  */
-	      p->red = 0;
-	      gp->red = 1;
+	      BTREE_NODE_RED_SET (p, 0);
+	      BTREE_NODE_RED_SET (gp, 1);
 
-	      *gparentp = p;
-	      p->parent = gp->parent;
+	      BTREE_NP_CHILD_SET (gparentp, p);
+	      BTREE_NP_SET (&p->parent, BTREE_NP (gp->parent));
 
 	      if (p_r < 0)
 		{
@@ -491,11 +527,11 @@ BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
                    root  pr          pr
                    /  \
 		   */
-		  gp->left = BTREE_(link_internal) (p->right);
-		  if (gp->left)
-		    gp->left->parent = gp;
-		  p->right = gp;
-		  gp->parent = p;
+		  BTREE_NP_CHILD_SET (&gp->left, BTREE_NP_CHILD (p->right));
+		  if (BTREE_NP_CHILD (gp->left))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (gp->left)->parent, gp);
+		  BTREE_NP_CHILD_SET (&p->right, gp);
+		  BTREE_NP_SET (&gp->parent, p);
 		}
 	      else
 		{
@@ -508,17 +544,14 @@ BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
                      pl  root    pl
                          /  \
 		   */
-		  gp->right = p->left;
-		  if (gp->right)
-		    gp->right->parent = gp;
-		  p->left = gp;
-		  gp->parent = p;
-
-		  if (! gp->right)
-		    gp->right
-		      = (BTREE_(node_t) *) ((uintptr_t) BTREE_(next_hard) (gp)
-					    | 1);
-
+		  BTREE_NP_CHILD_SET (&gp->right, BTREE_NP_CHILD (p->left));
+		  if (BTREE_NP_CHILD (gp->right))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (gp->right)->parent, gp);
+		  BTREE_NP_CHILD_SET (&p->left, gp);
+		  BTREE_NP_SET (&gp->parent, p);
+
+		  if (! BTREE_NP_CHILD (gp->right))
+		    BTREE_NP_THREAD_SET (&gp->right, BTREE_(next_hard) (gp));
 		}
 	    }
 	}
@@ -527,7 +560,7 @@ BTREE_(maybe_split2_internal) (BTREE_(t) *btree, node root, int mode)
 	 Making the root node black never changes the black height of
 	 the tree, however, it does eliminate a bit of work when both
 	 its children are red.  */
-      btree->root->red = 0;
+      BTREE_NODE_RED_SET (BTREE_NP (btree->root), 0);
     }
 }
 
@@ -681,12 +714,12 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 }
 #endif
 
-/* Detach node NODE from the tree BTREE.  */
+/* Detach node ROOT from the tree BTREE.  */
 void
 BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
 {
-  node p, q, r;
-  node *rootp;
+  node p, q, child;
+  struct BTREE_(node_ptr) *rootp;
   node unchained;
   int unchained_is_red;
 
@@ -709,11 +742,11 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
      was but what happens to the other branch?  Well the successor
      will always be a node with less than two children.  Replacing the
      node we want to delete with the successor maintains the ordering
-     and means we just have to deal with the successor (the trivial
-     case).
+     and means we just have to deal with its successor (the trivial
+     case--we just move it up).
 
      In this example, the successor, UNCHAINED, would be 4 which has
-     less than two children.  The child, R, is node 5.  We unchain 4
+     less than two children.  The child, CHILD, is node 5.  We unchain 4
      and insert R where it was.  Then we replace ROOT with UNCHAINED.
      The resulting tree is thus:
      
@@ -725,7 +758,7 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
 	   / \   / \
 	  0   2 5   7
 
-     Assume that we want to remove a node one child, for instance,
+     Assume that we want to remove a node with one child, for instance,
      ROOT=4 (from the first figure).  This is trivially detached as it
      need merely be removed from the tree and its one child moved up
      to take its place.  The resulting tree would be:
@@ -742,96 +775,107 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
    */
 
   rootp = selfp (btree, root);
-  r = BTREE_(link_internal) (root->right);
-  q = root->left;
 
-  if (q == NULL || r == NULL)
+  child = BTREE_NP_CHILD (root->right);
+  q = BTREE_NP_CHILD (root->left);
+
+  if (q == NULL || child == NULL)
     unchained = root;
   else
     {
       unchained = BTREE_(next) (root);
-      assert (!unchained->left || ! BTREE_(link_internal) (unchained->right));
+      assert (!BTREE_NP_CHILD (unchained->left)
+	      || !BTREE_NP_CHILD (unchained->right));
     }
 
-  /* We know that at least the left or right successor of UNCHAINED is
-     NULL.  R becomes the other one, it is chained into the parent of
-     UNCHAINED.  */
-  r = unchained->left;
-  if (r == NULL)
-    r = BTREE_(link_internal) (unchained->right);
+  /* We know that at least either, but perhaps both, of the left or
+     right children of UNCHAINED is NULL.  CHILD becomes the other one
+     and is chained into the parent of UNCHAINED.  */
+  child = BTREE_NP_CHILD (unchained->left);
+  if (child == NULL)
+    child = BTREE_NP_CHILD (unchained->right);
+  else
+    assert (! BTREE_NP_CHILD (unchained->right));
+
+  /* Update ROOT's predecessor's and successor's threads.  This is
+     required to avoid dangling pointers.  */
+  node pred = BTREE_(prev) (root);
+  node succ;
+  if (unchained != root)
+    /* UNCHAINED is the successor.  */
+    succ = unchained;
   else
-    assert (! BTREE_(link_internal) (unchained->right));
-
-  /* Update ROOT's predecessor (if it has a right thread) to point to
-     ROOT's successor.  */
-  q = BTREE_(prev) (root);
-  if (q && ! BTREE_(link_internal) (q->right))
-    q->right = (BTREE_(node_t) *) ((uintptr_t) (unchained == root
-						? BTREE_(next) (root)
-						: unchained) | 1);
-
-  /* Cache the parent as we may not be able to recover it if R is
-     NULL and unchained is clobbered.  */
-  if (unchained->parent == root)
+    succ = BTREE_(next) (root);
+
+  if (pred && BTREE_NP_THREAD_P (pred->right))
+    BTREE_NP_THREAD_SET (&pred->right, succ);
+  if (succ && BTREE_NP_THREAD_P (succ->left))
+    BTREE_NP_THREAD_SET (&succ->left, pred);
+
+  /* Cache CHILD's parent as we may not be able to recover it if CHILD is
+     NULL and UNCHAINED is clobbered.  */
+  if (BTREE_NP (unchained->parent) == root)
     p = unchained;
   else
-    p = unchained->parent;
+    p = BTREE_NP (unchained->parent);
 
-  /* And get UNCHAINED's parent to point to R.  */
-  if (! unchained->parent)
+  /* And get UNCHAINED's parent to point to CHILD.  */
+  if (! BTREE_NP (unchained->parent))
     {
       /* UNCHAINED is only ever the root when either there is one or
 	 two nodes in the tree.  */
       assert (unchained == root);
-      btree->root = r;
+      BTREE_NP_SET (&btree->root, child);
     }
-  else if (unchained->parent->left == unchained)
+  else if (BTREE_NP_CHILD (BTREE_NP (unchained->parent)->left) == unchained)
     {
       /* UNCHAINED can't be to the immediate left of ROOT as it is
 	 ROOT's successor.  */
-      assert (unchained->parent != root);
-      unchained->parent->left = r;
+      assert (BTREE_NP (unchained->parent) != root);
+      BTREE_NP_CHILD_SET (&BTREE_NP (unchained->parent)->left, child);
     }
   else
     {
-      assert (unchained->parent->right == unchained);
+      assert (BTREE_NP_CHILD (BTREE_NP (unchained->parent)->right)
+	      == unchained);
 
-      if (r)
-	unchained->parent->right = r;
+      if (child)
+	BTREE_NP_SET (&BTREE_NP (unchained->parent)->right, child);
       else
-	/* R is NULL and this is a right leaf.  */
-	unchained->parent->right
-	  = (BTREE_(node_t) *) ((uintptr_t) BTREE_(next_hard) (unchained) | 1);
+	/* CHILD is NULL and this is a right leaf.  */
+	BTREE_NP_THREAD_SET (&BTREE_NP (unchained->parent)->right,
+			     BTREE_(next_hard) (unchained));
     }
 
-  /* Adjust R's parent pointer (we can't do it earlier as the call to
+  /* Adjust CHILD's parent pointer (we could't do this earlier as the call to
      BTREE_(next_hard) would fail because we wouldn't have a proper
      tree).  */
-  if (r)
-    r->parent = p;
+  if (child)
+    BTREE_NP_SET (&child->parent, p);
 
-  unchained_is_red = unchained->red;
+  unchained_is_red = BTREE_NODE_RED_P (unchained);
 
   /* Replace the element to detach with its now unchained
      successor.  */
   if (unchained != root)
     {
-      unchained->left = root->left;
-      if (unchained->left)
-	unchained->left->parent = unchained;
+      BTREE_NP_CHILD_SET (&unchained->left, BTREE_NP_CHILD (root->left));
+      if (BTREE_NP_CHILD (unchained->left))
+	BTREE_NP_SET (&BTREE_NP (unchained->left)->parent, unchained);
 
       /* If ROOT->RIGHT is a right thread then it remains correct.  */
-      if (BTREE_(link_internal) (root->right))
+      if (BTREE_NP_CHILD (root->right))
 	{
-	  unchained->right = root->right;
-	  if (unchained->right)
-	    unchained->right->parent = unchained;
+	  BTREE_NP_CHILD_SET (&unchained->right, BTREE_NP_CHILD (root->right));
+	  if (BTREE_NP_CHILD (unchained->right))
+	    BTREE_NP_SET (&BTREE_NP_CHILD (unchained->right)->parent,
+			  unchained);
 	}
 
-      unchained->parent = root->parent;
-      unchained->red = root->red;
+      BTREE_NP_SET (&unchained->parent, BTREE_NP (root->parent));
+      BTREE_NODE_RED_SET (unchained, BTREE_NODE_RED_P (root));
 
-      *rootp = unchained;
+      BTREE_NP_CHILD_SET (rootp, unchained);
     }
 
   if (!unchained_is_red)
@@ -839,29 +883,33 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
       /* Now we lost a black edge, which means that the number of black
 	 edges on every path is no longer constant.  We must balance the
 	 tree.  */
-      /* P is the parent of R (now that UNCHAINED has been detached).
-	 R is likely to be NULL in the first iteration.  */
+      /* P is the parent of CHILD (now that UNCHAINED has been detached).
+	 CHILD is likely to be NULL in the first iteration.  */
       /* NULL nodes are considered black throughout - this is necessary for
 	 correctness.  */
-      for (; p && (r == NULL || !r->red); p = p->parent)
+      for (; p && (child == NULL || !BTREE_NODE_RED_P (child));
+	   p = BTREE_NP (p->parent))
 	{
-	  node *pp = selfp (btree, p);
+	  BTREE_ (check_tree_internal) (BTREE_NP (btree->root), 0, 0, false);
+
+	  struct BTREE_(node_ptr) *pp = selfp (btree, p);
 
-	  assert (! r || r->parent == p);
+	  assert (! child || BTREE_NP (child->parent) == p);
 
 	  /* Two symmetric cases.  */
-	  if (r == p->left)
+	  if (child == BTREE_NP_CHILD (p->left))
 	    {
-	      /* Q is R's brother, P is R's parent.  The subtree with root
-		 R has one black edge less than the subtree with root Q.
+	      /* Q is CHILD's brother, P is CHILD's parent.  The
+		 subtree with root CHILD has one black edge less than
+		 the subtree with root Q.
 
 		             p
 			    / \
-			   r   q
+		       child   q
 	       */
-	      q = p->right;
-	      assert (BTREE_(link_internal) (q));
-	      if (q->red)
+	      q = BTREE_NP_CHILD (p->right);
+	      assert (q);
+	      if (BTREE_NODE_RED_P (q))
 		{
 		  /* If Q is red, we know that P is black. We rotate P left
 		     so that Q becomes the top node in the tree, with P below
@@ -875,39 +923,38 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
 		               / \
 		      ->      p   pr
 			     / \
-			    r   ql
+		        child   ql
 
 		   */
-		  q->red = 0;
-		  p->red = 1;
+		  BTREE_NODE_RED_SET (q, 0);
+		  BTREE_NODE_RED_SET (p, 1);
 		  /* Left rotate p.  */
-		  q->parent = p->parent;
-		  p->right = q->left;
-		  if (p->right)
-		    p->right->parent = p;
+		  BTREE_NP_SET (&q->parent, BTREE_NP (p->parent));
+		  BTREE_NP_CHILD_SET (&p->right, BTREE_NP_CHILD (q->left));
+		  if (BTREE_NP_CHILD (p->right))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (p->right)->parent, p);
 
-		  q->left = p;
-		  p->parent = q;
+		  BTREE_NP_CHILD_SET (&q->left, p);
+		  BTREE_NP_SET (&p->parent, q);
 		  
-		  *pp = q;
+		  BTREE_NP_CHILD_SET (pp, q);
 		  /* Make sure pp is right if the case below tries to use
 		     it.  */
 		  pp = &q->left;
-		  q = p->right;
-		  assert (BTREE_(link_internal) (q));
+		  q = BTREE_NP_CHILD (p->right);
+		  assert (q);
 
-		  if (! p->right)
-		    p->right
-		      = (BTREE_(node_t) *) ((uintptr_t) BTREE_(next_hard) (p)
-					    | 1);
+		  if (! BTREE_NP_CHILD (p->right))
+		    BTREE_NP_THREAD_SET (&p->right, BTREE_(next_hard) (p));
 		}
 	      /* We know that Q can't be NULL here.  We also know that Q is
 		 black.  */
-	      assert (! q->red);
+	      assert (! BTREE_NODE_RED_P (q));
 
-	      if ((q->left == NULL || !q->left->red)
-		  && (BTREE_(link_internal) (q->right) == NULL
-		      || !q->right->red))
+	      if ((BTREE_NP_CHILD (q->left) == NULL
+		   || !BTREE_NODE_RED_P (BTREE_NP_CHILD (q->left)))
+		  && (BTREE_NP_CHILD (q->right) == NULL
+		      || !BTREE_NODE_RED_P (BTREE_NP_CHILD (q->right))))
 		{
 		  /* Q has two black successors.  We can simply color Q red.
 		     The whole subtree with root P is now missing one black
@@ -917,93 +964,93 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
 		     valid and also makes the black edge count come out
 		     right.  If P is black, we are at least one step closer
 		     to the root and we'll try again the next iteration.  */
-		  q->red = 1;
-		  r = p;
+		  BTREE_NODE_RED_SET (q, 1);
+		  child = p;
 		}
 	      else
 		{
 		  /* Q is black, one of Q's successors is red.  We can
 		     repair the tree with one operation and will exit the
 		     loop afterwards.  */
-		  if (! BTREE_(link_internal) (q->right) || !q->right->red)
+		  if (! BTREE_NP_CHILD (q->right)
+		      || !BTREE_NODE_RED_P (BTREE_NP_CHILD (q->right)))
 		    {
-		      /* The left one is red.  We perform the same action as
-			 in maybe_split_for_insert where two red edges are
-			 adjacent but point in different directions:
-			 Q's left successor (let's call it Q2) becomes the
-			 top of the subtree we are looking at, its parent (Q)
-			 and grandparent (P) become its successors. The former
-			 successors of Q2 are placed below P and Q.
-			 P becomes black, and Q2 gets the color that P had.
-			 This changes the black edge count only for node R and
-			 its successors.
+		      /* The left one is red.  We perform the same
+			 action as in maybe_split_for_insert where two
+			 red edges are adjacent but point in different
+			 directions: Q's left successor (let's call it
+			 Q2) becomes the top of the subtree we are
+			 looking at, its parent (Q) and grandparent
+			 (P) become its successors. The former
+			 successors of Q2 are placed below P and Q.  P
+			 becomes black, and Q2 gets the color that P
+			 had.  This changes the black edge count only
+			 for node CHILD and its successors.
 
 		             p                q2
 			    / \             /    \
-			   r   q    ->     p      q
+		       child   q    ->     p      q
                               / \         / \    / \
-                             q2          r  q2l
+                             q2      child  q2l
 		      */
-		      node q2 = q->left;
-		      q2->red = p->red;
+		      node q2 = BTREE_NP_CHILD (q->left);
+		      BTREE_NODE_RED_SET (q2, BTREE_NODE_RED_P (p));
 
-		      q2->parent = p->parent;
+		      BTREE_NP_SET (&q2->parent, BTREE_NP (p->parent));
 
-		      p->right = q2->left;
-		      if (p->right)
-			p->right->parent = p;
+		      BTREE_NP_CHILD_SET (&p->right, BTREE_NP_CHILD (q2->left));
+		      if (BTREE_NP_CHILD (p->right))
+			BTREE_NP_SET (&BTREE_NP_CHILD (p->right)->parent, p);
 
-		      q->left = BTREE_(link_internal) (q2->right);
-		      if (q->left)
-			q->left->parent = q;
+		      BTREE_NP_CHILD_SET (&q->left, BTREE_NP_CHILD (q2->right));
+		      if (BTREE_NP_CHILD (q->left))
+			BTREE_NP_SET (&BTREE_NP_CHILD (q->left)->parent, q);
 
-		      q2->right = q;
-		      q->parent = q2;
+		      BTREE_NP_CHILD_SET (&q2->right, q);
+		      BTREE_NP_SET (&q->parent, q2);
 
-		      q2->left = p;
-		      p->parent = q2;
+		      BTREE_NP_CHILD_SET (&q2->left, p);
+		      BTREE_NP_SET (&p->parent, q2);
 
-		      *pp = q2;
-		      p->red = 0;
+		      BTREE_NP_CHILD_SET (pp, q2);
+		      BTREE_NODE_RED_SET (p, 0);
 
-		      if (! p->right)
-			p->right = (BTREE_(node_t) *)
-			  ((uintptr_t) BTREE_(next_hard) (p) | 1);
+		      if (! BTREE_NP_CHILD (p->right))
+			BTREE_NP_THREAD_SET (&p->right, BTREE_(next_hard) (p));
 		    }
 		  else
 		    {
 		      /* It's the right one.  Rotate P left. P becomes black,
 			 and Q gets the color that P had.  Q's right successor
 			 also becomes black.  This changes the black edge
-			 count only for node R and its successors.
+			 count only for node CHILD and its successors.
 
 		                q
 		               / \
 		      ->      p   pr
 			     / \
-			    r   ql
+			child   ql
 		       */
 
-		      q->red = p->red;
-		      p->red = 0;
+		      BTREE_NODE_RED_SET (q, BTREE_NODE_RED_P (p));
+		      BTREE_NODE_RED_SET (p, 0);
 
-		      q->parent = p->parent;
+		      BTREE_NP_SET (&q->parent, BTREE_NP (p->parent));
 
-		      q->right->red = 0;
+		      BTREE_NODE_RED_SET (BTREE_NP_CHILD (q->right), 0);
 
 		      /* left rotate p */
-		      p->right = q->left;
-		      if (p->right)
-			p->right->parent = p;
+		      BTREE_NP_CHILD_SET (&p->right, BTREE_NP_CHILD (q->left));
+		      if (BTREE_NP_CHILD (p->right))
+			BTREE_NP_SET (&BTREE_NP_CHILD (p->right)->parent, p);
 
-		      q->left = p;
-		      p->parent = q;
+		      BTREE_NP_CHILD_SET (&q->left, p);
+		      BTREE_NP_SET (&p->parent, q);
 
-		      *pp = q;
+		      BTREE_NP_CHILD_SET (pp, q);
 
-		      if (! p->right)
-			p->right = (BTREE_(node_t) *)
-			  ((uintptr_t) BTREE_(next_hard) (p) | 1);
+		      if (! BTREE_NP_CHILD (p->right))
+			BTREE_NP_THREAD_SET (&p->right, BTREE_(next_hard) (p));
 		    }
 
 		  /* We're done.  */
@@ -1012,75 +1059,75 @@ BTREE_(detach) (BTREE_(t) *btree, BTREE_(node_t) *root)
 	    }
 	  else
 	    {
-	      assert (r == BTREE_(link_internal) (p->right));
+	      assert (child == BTREE_NP_CHILD (p->right));
 	      /* Comments: see above.  */
-	      q = p->left;
-	      assert (BTREE_(link_internal) (q));
-	      if (q != NULL && q->red)
+	      q = BTREE_NP_CHILD (p->left);
+	      if (q != NULL && BTREE_NODE_RED_P (q))
 		{
-		  q->red = 0;
-		  p->red = 1;
-		  q->parent = p->parent;
-		  p->left = BTREE_(link_internal) (q->right);
-		  if (p->left)
-		    p->left->parent = p;
-		  q->right = p;
-		  p->parent = q;
-		  *pp = q;
+		  BTREE_NODE_RED_SET (q, 0);
+		  BTREE_NODE_RED_SET (p, 1);
+		  BTREE_NP_SET (&q->parent, BTREE_NP (p->parent));
+		  BTREE_NP_CHILD_SET (&p->left, BTREE_NP_CHILD (q->right));
+		  if (BTREE_NP_CHILD (p->left))
+		    BTREE_NP_SET (&BTREE_NP_CHILD (p->left)->parent, p);
+		  BTREE_NP_CHILD_SET (&q->right, p);
+		  BTREE_NP_SET (&p->parent, q);
+		  BTREE_NP_CHILD_SET (pp, q);
 		  pp = &q->right;
-		  q = p->left;
-		  assert (BTREE_(link_internal) (q));
+		  q = BTREE_NP_CHILD (p->left);
 		}
-	      assert (! q->red);
-	      if ((! BTREE_(link_internal) (q->right) || !q->right->red)
-		       && (q->left == NULL || !q->left->red))
+	      assert (! BTREE_NODE_RED_P (q));
+	      if ((! BTREE_NP_CHILD (q->right)
+		   || ! BTREE_NODE_RED_P (BTREE_NP_CHILD (q->right)))
+		  && (BTREE_NP_CHILD (q->left) == NULL
+		      || ! BTREE_NODE_RED_P (BTREE_NP_CHILD (q->left))))
 		{
-		  q->red = 1;
-		  r = p;
+		  BTREE_NODE_RED_SET (q, 1);
+		  child = p;
 		}
 	      else
 		{
-		  if (q->left == NULL || !q->left->red)
+		  if (!BTREE_NP_CHILD (q->left)
+		      || !BTREE_NODE_RED_P (BTREE_NP_CHILD (q->left)))
 		    {
-		      node q2 = q->right;
-		      q2->red = p->red;
-		      q2->parent = p->parent;
-		      p->left = BTREE_(link_internal) (q2->right);
-		      if (p->left)
-			p->left->parent = p;
-		      q->right = q2->left;
-		      if (q->right)
-			q->right->parent = q;
-		      q2->left = q;
-		      q->parent = q2;
-		      q2->right = p;
-		      p->parent = q2;
-		      *pp = q2;
-		      p->red = 0;
-
-		      if (! q->right)
-			q->right = (BTREE_(node_t) *)
-			  ((uintptr_t) BTREE_(next_hard) (q) | 1);
+		      node q2 = BTREE_NP_CHILD (q->right);
+		      BTREE_NODE_RED_SET (q2, BTREE_NODE_RED_P (p));
+		      BTREE_NP_SET (&q2->parent, BTREE_NP (p->parent));
+		      BTREE_NP_CHILD_SET (&p->left, BTREE_NP_CHILD (q2->right));
+		      if (BTREE_NP_CHILD (p->left))
+			BTREE_NP_SET (&BTREE_NP_CHILD (p->left)->parent, p);
+		      BTREE_NP_CHILD_SET (&q->right, BTREE_NP_CHILD (q2->left));
+		      if (BTREE_NP_CHILD (q->right))
+			BTREE_NP_SET (&BTREE_NP_CHILD (q->right)->parent, q);
+		      BTREE_NP_CHILD_SET (&q2->left, q);
+		      BTREE_NP_SET (&q->parent, q2);
+		      BTREE_NP_CHILD_SET (&q2->right, p);
+		      BTREE_NP_SET (&p->parent, q2);
+		      BTREE_NP_CHILD_SET (pp, q2);
+		      BTREE_NODE_RED_SET (p, 0);
+
+		      if (! BTREE_NP_CHILD (q->right))
+			BTREE_NP_THREAD_SET (&q->right, BTREE_(next_hard) (q));
 		    }
 		  else
 		    {
-		      q->red = p->red;
-		      p->red = 0;
-		      q->left->red = 0;
-		      q->parent = p->parent;
-		      p->left = BTREE_(link_internal) (q->right);
-		      if (p->left)
-			p->left->parent = p;
-		      q->right = p;
-		      p->parent = q;
-		      *pp = q;
+		      BTREE_NODE_RED_SET (q, BTREE_NODE_RED_P (p));
+		      BTREE_NODE_RED_SET (p, 0);
+		      BTREE_NODE_RED_SET (BTREE_NP_CHILD (q->left), 0);
+		      BTREE_NP_SET (&q->parent, BTREE_NP (p->parent));
+		      BTREE_NP_CHILD_SET (&p->left, BTREE_NP_CHILD (q->right));
+		      if (BTREE_NP_CHILD (p->left))
+			BTREE_NP_SET (&BTREE_NP_CHILD (p->left)->parent, p);
+		      BTREE_NP_CHILD_SET (&q->right, p);
+		      BTREE_NP_SET (&p->parent, q);
+		      BTREE_NP_CHILD_SET (pp, q);
 		    }
 		  return;
 		}
 	    }
 	}
-      if (r != NULL)
-	r->red = 0;
+      if (child != NULL)
+	BTREE_NODE_RED_SET (child, 0);
     }
 }
 
diff --git a/libhurd-btree/btree.h b/libhurd-btree/btree.h
index ce8e21b..b472695 100644
--- a/libhurd-btree/btree.h
+++ b/libhurd-btree/btree.h
@@ -111,24 +111,110 @@
    memory is allocated and deallocated and it eliminates a level of
    indirection where user data is pointed to by the node which is
    present in many btree implementations.  */
+struct BTREE_(node_ptr)
+{
+  union
+  {
+    struct
+    {
+      /* Whether PTR is a child (=0) or a thread pointer (=1).  */
+      uintptr_t thread : 1;
+      /* The value of the pointer >> 1.  */
+      uintptr_t ptr : (sizeof (uintptr_t) * 8 - 1);
+    };
+    uintptr_t raw;
+    struct BTREE_(node) *ptr;
+  };
+};
+
+struct BTREE_(node_pptr)
+{
+  union
+  {
+    struct
+    {
+      /* Whether the node is red (=1) or black (=0).  */
+      uintptr_t red : 1;
+      /* The value of the pointer >> 1.  */
+      uintptr_t ptr : (sizeof (uintptr_t) * 8 - 1);
+    };
+    uintptr_t raw;
+    struct BTREE_(node) *ptr;
+  };
+};
+
 struct BTREE_(node)
 {
   /* All members are private to the implementation.  */
-  struct BTREE_(node) *left;
-  /* If the least significant bit is 0, right is not a right link but
-     a right thread (i.e. a pointer to the current node's
-     successor).  */
-  struct BTREE_(node) *right;
-  struct BTREE_(node) *parent;
-  bool red;
+  struct BTREE_(node_pptr) parent;
+  struct BTREE_(node_ptr) left;
+  struct BTREE_(node_ptr) right;
 };
 typedef struct BTREE_(node) BTREE_(node_t);
 
+/* Internal accessors functions.  */
+
+/* Give a struct BTREE_(node_ptr), return a BTREE_(node_t).  This
+   function does not distinguish between child links and thread
+   links.  */
+#define BTREE_NP(__bn_node_ptr)				\
+  ((BTREE_(node_t) *) ((__bn_node_ptr).ptr << 1))
+/* Set a struct BTREE_(node_ptr) * to point to BTREE_(node_t).  */
+#define BTREE_NP_SET(__bnp_node_ptrp, __bnp_value)		\
+  do								\
+    {								\
+      BTREE_(node_t) *__bnp_val = (__bnp_value);		\
+      (__bnp_node_ptrp)->ptr = ((uintptr_t) __bnp_val) >> 1;	\
+    }								\
+  while (0)
+
+/* Return whether the BTREE_(node_ptr) contains a thread pointer (if
+   not, then it contains a child pointer).  */
+#define BTREE_NP_THREAD_P(__bntp_node_ptr)	\
+  ((__bntp_node_ptr).thread)
+#define BTREE_NP_THREAD_P_SET(__bntps_node_ptrp, __bntps_value)	\
+  (((__bntps_node_ptrp)->thread) = __bntps_value)
+
+#define BTREE_NP_THREAD(__bnt_node_ptr)				\
+  (BTREE_NP_THREAD_P ((__bnt_node_ptr))				\
+   ? BTREE_NP ((__bnt_node_ptr)) : NULL)
+#define BTREE_NP_THREAD_SET(__bnts_node_ptrp, __bnts_value)	\
+  do								\
+    {								\
+      struct BTREE_(node_ptr) *__bnts_n = (__bnts_node_ptrp);	\
+      BTREE_(node_t) *__bnts_val = (__bnts_value);		\
+								\
+      BTREE_NP_SET (__bnts_n, __bnts_val);			\
+      BTREE_NP_THREAD_P_SET (__bnts_n, 1);			\
+    }								\
+  while (0)
+
+#define BTREE_NP_CHILD(__bnc_node_ptr)			\
+  (BTREE_NP_THREAD_P ((__bnc_node_ptr))			\
+   ? NULL : BTREE_NP ((__bnc_node_ptr)))
+#define BTREE_NP_CHILD_SET(__bncs_node_ptrp, __bncs_value)	\
+  do								\
+    {								\
+      struct BTREE_(node_ptr) *__bncs_np = (__bncs_node_ptrp);	\
+      BTREE_(node_t) *__bncs_val = (__bncs_value);		\
+								\
+      BTREE_NP_SET (__bncs_np, __bncs_val);			\
+      BTREE_NP_THREAD_P_SET (__bncs_np, 0);			\
+    }								\
+  while (0)
+
+/* Return whether a BTREE_(node) * designates a red node.  */
+#define BTREE_NODE_RED_P(__bnrp_node)		\
+  ((__bnrp_node)->parent.red)
+/* Set whether the BTREE_(node) * designates a red node.  */
+#define BTREE_NODE_RED_SET(__bnrs_node, __bnrs_value)	\
+  (((__bnrs_node)->parent.red) = __bnrs_value)
+
 /* The root of a btree.  */
 typedef struct 
 {
   /* All members are private to the implementation.  */
-  struct BTREE_(node) *root;
+  struct BTREE_(node_ptr) root;
 } BTREE_(t);
 
 /* Compare two keys.  Return 0 if A and B are equal, less then 0 if a
@@ -147,21 +233,16 @@ BTREE_EXTERN_INLINE void BTREE_(tree_init) (BTREE_(t) *btree);
 BTREE_EXTERN_INLINE void
 BTREE_(tree_init) (BTREE_(t) *btree)
 {
-  btree->root = 0;
+  BTREE_NP_CHILD_SET (&btree->root, 0);
 }
 
 /* This is a private function do not call it from user code!
 
-   Given a node pointer return the link portion (i.e. return NULL if
-   LINK is a thread and not a child pointer).  */
-static inline BTREE_(node_t) *
-BTREE_(link_internal) (BTREE_(node_t) *link)
-{
-  if ((((uintptr_t) link) & 0x1) == 1)
-    /* This is a right thread, not a child.  */
-    return NULL;
-  return link;
-}
+   Internal function.  Perform a consistent check on the tree rooted
+   at ROOT.  */
+extern void BTREE_(check_tree_internal) (BTREE_(node_t) *root,
+					 BTREE_(key_compare_t) compare,
+					 size_t key_offset, bool check_colors);
 
 /* This is a private function do not call it from user code!
 
@@ -185,9 +266,11 @@ BTREE_(maybe_split_internal) (BTREE_(t) *tree, BTREE_(node_t) *node,
 			      int force)
 {
   if (force
-      || (node->left && node->left->red
-	  && BTREE_(link_internal) (node->right)
-	  && node->right->red))
+      /* Are both children red?  */
+      || (BTREE_NP_CHILD (node->left)
+	  && BTREE_NODE_RED_P (BTREE_NP_CHILD (node->left))
+	  && BTREE_NP_CHILD (node->right)
+	  && BTREE_NODE_RED_P (BTREE_NP_CHILD (node->right))))
     BTREE_(maybe_split2_internal) (tree, node, force);
 }
 
@@ -211,26 +294,28 @@ BTREE_(maybe_split_internal) (BTREE_(t) *tree, BTREE_(node_t) *node,
 BTREE_EXTERN_INLINE error_t
 BTREE_(find_internal) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 		       size_t key_offset, const void *key,
-		       BTREE_(node_t) ***nodepp, BTREE_(node_t) **predp,
-		       BTREE_(node_t) **succp, BTREE_(node_t) **parentp);
+		       struct BTREE_(node_ptr) **nodepp,
+		       BTREE_(node_t) **predp, BTREE_(node_t) **succp,
+		       BTREE_(node_t) **parentp);
 BTREE_EXTERN_INLINE error_t
 BTREE_(find_internal) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 		       size_t key_offset, const void *key,
-		       BTREE_(node_t) ***nodepp, BTREE_(node_t) **predp,
-		       BTREE_(node_t) **succp, BTREE_(node_t) **parentp)
+		       struct BTREE_(node_ptr) **nodepp,
+		       BTREE_(node_t) **predp, BTREE_(node_t) **succp,
+		       BTREE_(node_t) **parentp)
 {
   int r;
   error_t err = ESRCH;
-  BTREE_(node_t) **nodep = &btree->root;
-  *parentp = NULL;
-  *predp = *succp = NULL;
+  struct BTREE_(node_ptr) *nodep = &btree->root;
+  *parentp = 0;
+  *predp = *succp = 0;
 
-  while (BTREE_(link_internal) (*nodep))
+  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 = *nodep;
+      BTREE_(node_t) *node = BTREE_NP (*nodep);
 
       r = compare (key, (void *) node + key_offset);
       if (r == 0)
@@ -273,11 +358,12 @@ BTREE_(find) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 	      size_t key_offset, const void *key)
 {
   error_t err;
-  BTREE_(node_t) **nodep, *node, *pred, *succ, *parent;
+  struct BTREE_(node_ptr) *nodep;
+  BTREE_(node_t) *node, *pred, *succ, *parent;
 
   err = BTREE_(find_internal) (btree, compare, key_offset, key,
 			       &nodep, &pred, &succ, &parent);
-  node = BTREE_(link_internal) (*nodep);
+  node = BTREE_NP_CHILD (*nodep);
   /* If not found, NODE will be NULL.  */
   assert ((err == ESRCH && ! node) || (err == 0 && node));
   return node;
@@ -295,34 +381,46 @@ BTREE_(insert) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
 		size_t key_offset, BTREE_(node_t) *newnode)
 {
   error_t err;
-  BTREE_(node_t) **nodep, *pred, *succ, *parent;
+  struct BTREE_(node_ptr) *nodep;
+  BTREE_(node_t) *pred, *succ, *parent;
 
   err = BTREE_(find_internal) (btree, compare, key_offset,
 			       (void *) newnode + key_offset,
 			       &nodep, &pred, &succ, &parent);
   if (! err)
     /* Overlap!  Bail.  */
-    return BTREE_(link_internal) (*nodep);
+    {
+      assert (! BTREE_NP_THREAD_P (*nodep));
+      return BTREE_NP_CHILD (*nodep);
+    }
 
   assert (err == ESRCH);
-  assert (BTREE_(link_internal) (*nodep) == NULL);
+  assert (BTREE_NP_CHILD (*nodep) == NULL);
 
   /* A node with the same key as NEWNODE does not exist in the tree
      BTREE.  NODEP is a pointer to the location where NODE should be
      installed (i.e. either &PARENT->LEFT or &PARENT->RIGHT).  PARENT
      is the parent of *NODEP.  */
-  *nodep = newnode;
-  newnode->parent = parent;
-  newnode->left = NULL;
-  newnode->right = (BTREE_(node_t) *) ((uintptr_t) succ | 1);
-  newnode->red = 1;
-
-  if (pred && ((uintptr_t) pred->right & 1) == 1)
-    /* NEWNODE's predecessor has a right thread.  */
+  BTREE_NP_CHILD_SET (nodep, newnode);
+  BTREE_NP_SET (&newnode->parent, parent);
+  BTREE_NP_THREAD_SET (&newnode->left, pred);
+  BTREE_NP_THREAD_SET (&newnode->right, succ);
+  BTREE_NODE_RED_SET (newnode, true);
+
+  if (pred && BTREE_NP_THREAD_P (pred->right))
+    /* NEWNODE's predecessor has a right thread, update it.  */
     {
-      assert (pred->right == (BTREE_(node_t) *) ((uintptr_t) succ | 1));
-      /* But more importantly, we must point it to us.  */
-      pred->right = (BTREE_(node_t) *) (((uintptr_t) newnode) | 1);
+      assert (BTREE_NP_CHILD (pred->right) == succ);
+      BTREE_NP_THREAD_SET (&pred->right, newnode);
+    }
+
+  if (succ && (BTREE_NP_THREAD_P (succ->left)
+	       || ! BTREE_NP_CHILD (succ->left)))
+    /* NEWNODE's successor has a left thread, update it.  */
+    {
+      if (BTREE_NP_THREAD_P (succ->left))
+	assert (BTREE_NP_CHILD (succ->left) == pred);
+      BTREE_NP_THREAD_SET (&succ->left, newnode);
     }
 
   if (parent)
@@ -332,7 +430,10 @@ BTREE_(insert) (BTREE_(t) *btree, BTREE_(key_compare_t) compare,
   else
     /* NEWNODE is the top of the tree.  Making it black means less
        balancing later on.  */
-    newnode->red = 0;
+    BTREE_NODE_RED_SET (newnode, false);
+
+  BTREE_(check_tree_internal) (BTREE_NP_CHILD (btree->root),
+			       compare, key_offset, true);
 
   return 0;
 }
@@ -364,16 +465,21 @@ BTREE_(first) (BTREE_(t) *btree)
 {
   BTREE_(node_t) *node;
 
-  node = btree->root;
+  node = BTREE_NP (btree->root);
 
   if (! node)
     return NULL;
 
-  while (node->left)
-    node = node->left;
+  while (BTREE_NP_CHILD (node->left))
+    node = BTREE_NP_CHILD (node->left);
   return node;
 }
 
+/* Internal function, do not call from user code.  */
+extern BTREE_(node_t) *BTREE_(next_hard) (BTREE_(node_t) *node);
+/* Internal function, do not call from user code.  */
+extern BTREE_(node_t) *BTREE_(prev_hard) (BTREE_(node_t) *node);
+
 /* Return the node following node NODE or NULL if NODE is the last
    (i.e. largest) node in the tree.  This function is guaranteed to
    never touch a node which is lexically less than NODE.  */
@@ -381,22 +487,37 @@ BTREE_EXTERN_INLINE BTREE_(node_t) *BTREE_(next) (BTREE_(node_t) *node);
 BTREE_EXTERN_INLINE BTREE_(node_t) *
 BTREE_(next) (BTREE_(node_t) *node)
 {
-  if (((uintptr_t) node->right & 1) == 1)
+  if (BTREE_NP_THREAD_P (node->right))
     /* We have a right thread, use it.  */
-    return (BTREE_(node_t) *) (((uintptr_t) node->right) & ~1);
-  assert (node->right);
+    return BTREE_NP_THREAD (node->right);
+  assert (BTREE_NP_CHILD (node->right));
 
   /* NODE has a right child node.  The left most child of NODE->RIGHT
      is the next node.  */
-  node = node->right;
-  while (node->left)
-    node = node->left;
+  node = BTREE_NP_CHILD (node->right);
+  while (BTREE_NP_CHILD (node->left))
+    node = BTREE_NP_CHILD (node->left);
   return node;
 }
 
 /* Return the node preceding node NODE or NULL if NODE is the first
    (i.e. smallest) node in the tree.  */
-extern BTREE_(node_t) *BTREE_(prev) (BTREE_(node_t) *node);
+BTREE_EXTERN_INLINE BTREE_(node_t) *BTREE_(prev) (BTREE_(node_t) *node);
+BTREE_EXTERN_INLINE BTREE_(node_t) *
+BTREE_(prev) (BTREE_(node_t) *node)
+{
+  if (BTREE_NP_THREAD_P (node->left))
+    /* We have a left thread, use it.  */
+    return BTREE_NP_THREAD (node->left);
+
+  /* We have to do it the hard way.  */
+  BTREE_(node_t) *prev = BTREE_(prev_hard) (node);
+
+  if (! BTREE_NP_CHILD (node->left))
+    BTREE_NP_THREAD_SET (&node->left, node);
+
+  return prev;
+}
 
 /* Create a more strongly typed btree interface a la C++'s templates.
 
@@ -514,6 +635,13 @@ static inline void							\
 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_(key_compare_t)) cmp,		\
+			       offsetof (node_type, key_field)		\
+			       - offsetof (node_type, btree_node_field), \
+			       true);					\
 }									\
 									\
 static inline node_type *						\