Reduce memory size of tsearch red-black tree.

A tsearch red-black tree node contains 3 pointers (key, left, right)
and 1 bit to hold the red-black flag. When allocating new nodes
this 1 bit is expanded to a full word. Causing the overhead per node
to be 3 times the key size.

We can reduce this overhead to just 2 times the key size.
malloc returns naturally aligned memory. All nodes are internally
allocated with malloc and the left/right node pointers are used
as implementation details. So we can use the low bits of the
left/right node pointers to store extra information.

Replace all direct accesses of the struct node_t node pointers and
red-black value with defines that take care of the red-black flag in
the low bit of the (left) node pointer. This reduces the size of the
nodes on 32-bit systems from 16 to 12 bytes and on 64-bit systems
from 32 to 24 bytes.

Also fix a call to CHECK_TREE so the code can be build (and tested)
with DEBUGGING defined again.

V2 changes:

- Add assert after malloc to catch any odd pointers from bad
  interposed mallocs.
- Rename implementation flag to USE_MALLOC_LOW_BIT.

ChangeLog:

       * misc/tsearch.c (struct node_t): Reduce to 3 pointers if
       USE_MALLOC_LOW_BIT.  Define pointer/value accessors.
       (check_tree_recurse): Use newly defined accessors.
       (check_tree): Likewise.
       (maybe_split_for_insert): Likewise.
       (__tfind): Likewise.
       (__tdelete): Likewise.
       (trecurse): Likewise.
       (tdestroy_recurse): Likewise.
       (__tsearch): Likewise. And add asserts for malloc alignment.
       (__twalk): Cast root to node in case CHECK_TREE is defined.

2 files changed, 259 insertions, 153 deletions

diff --git a/ChangeLog b/ChangeLog
index 4e172c467a..7205de46dc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2016-08-25  Mark Wielaard  <mark@klomp.org>
+
+	* misc/tsearch.c (struct node_t): Reduce to 3 pointers if
+	USE_MALLOC_LOW_BIT.  Define pointer/value accessors.
+	(check_tree_recurse): Use newly defined accessors.
+	(check_tree): Likewise.
+	(maybe_split_for_insert): Likewise.
+	(__tfind): Likewise.
+	(__tdelete): Likewise.
+	(trecurse): Likewise.
+	(tdestroy_recurse): Likewise.
+	(__tsearch): Likewise. And add asserts for malloc alignment.
+	(__twalk): Cast root to node in case CHECK_TREE is defined.
+
 2016-08-21  Samuel Thibault  <samuel.thibault@ens-lyon.org>
 
 	* scripts/check-local-headers.sh (exclude): Add mach_debug/.
diff --git a/misc/tsearch.c b/misc/tsearch.c
index ffb89ec0f8..c07e606708 100644
--- a/misc/tsearch.c
+++ b/misc/tsearch.c
@@ -83,19 +83,70 @@
    In this case, A has been rotated left.  This preserves the ordering of the
    binary tree.  */
 
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 #include <search.h>
 
+/* Assume malloc returns naturally aligned (alignof (max_align_t))
+   pointers so we can use the low bits to store some extra info.  This
+   works for the left/right node pointers since they are not user
+   visible and always allocated by malloc.  The user provides the key
+   pointer and so that can point anywhere and doesn't have to be
+   aligned.  */
+#define USE_MALLOC_LOW_BIT 1
+
+#ifndef USE_MALLOC_LOW_BIT
+typedef struct node_t
+{
+  /* Callers expect this to be the first element in the structure - do not
+     move!  */
+  const void *key;
+  struct node_t *left_node;
+  struct node_t *right_node;
+  unsigned int is_red:1;
+} *node;
+
+#define RED(N) (N)->is_red
+#define SETRED(N) (N)->is_red = 1
+#define SETBLACK(N) (N)->is_red = 0
+#define SETNODEPTR(NP,P) (*NP) = (P)
+#define LEFT(N) (N)->left_node
+#define LEFTPTR(N) (&(N)->left_node)
+#define SETLEFT(N,L) (N)->left_node = (L)
+#define RIGHT(N) (N)->right_node
+#define RIGHTPTR(N) (&(N)->right_node)
+#define SETRIGHT(N,R) (N)->right_node = (R)
+#define DEREFNODEPTR(NP) (*(NP))
+
+#else /* USE_MALLOC_LOW_BIT */
+
 typedef struct node_t
 {
   /* Callers expect this to be the first element in the structure - do not
      move!  */
   const void *key;
-  struct node_t *left;
-  struct node_t *right;
-  unsigned int red:1;
+  uintptr_t left_node; /* Includes whether the node is red in low-bit. */
+  uintptr_t right_node;
 } *node;
+
+#define RED(N) (node)((N)->left_node & ((uintptr_t) 0x1))
+#define SETRED(N) (N)->left_node |= ((uintptr_t) 0x1)
+#define SETBLACK(N) (N)->left_node &= ~((uintptr_t) 0x1)
+#define SETNODEPTR(NP,P) (*NP) = (node)((((uintptr_t)(*NP)) \
+					 & (uintptr_t) 0x1) | (uintptr_t)(P))
+#define LEFT(N) (node)((N)->left_node & ~((uintptr_t) 0x1))
+#define LEFTPTR(N) (node *)(&(N)->left_node)
+#define SETLEFT(N,L) (N)->left_node = (((N)->left_node & (uintptr_t) 0x1) \
+				       | (uintptr_t)(L))
+#define RIGHT(N) (node)((N)->right_node)
+#define RIGHTPTR(N) (node *)(&(N)->right_node)
+#define SETRIGHT(N,R) (N)->right_node = (uintptr_t)(R)
+#define DEREFNODEPTR(NP) (node)((uintptr_t)(*(NP)) & ~((uintptr_t) 0x1))
+
+#endif /* USE_MALLOC_LOW_BIT */
 typedef const struct node_t *const_node;
 
 #undef DEBUGGING
@@ -104,8 +155,6 @@ typedef const struct node_t *const_node;
 
 /* Routines to check tree invariants.  */
 
-#include <assert.h>
-
 #define CHECK_TREE(a) check_tree(a)
 
 static void
@@ -117,12 +166,14 @@ check_tree_recurse (node p, int d_sofar, int d_total)
       return;
     }
 
-  check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total);
-  check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total);
-  if (p->left)
-    assert (!(p->left->red && p->red));
-  if (p->right)
-    assert (!(p->right->red && p->red));
+  check_tree_recurse (LEFT(p), d_sofar + (LEFT(p) && !RED(LEFT(p))),
+		      d_total);
+  check_tree_recurse (RIGHT(p), d_sofar + (RIGHT(p) && !RED(RIGHT(p))),
+		      d_total);
+  if (LEFT(p))
+    assert (!(RED(LEFT(p)) && RED(p)));
+  if (RIGHT(p))
+    assert (!(RED(RIGHT(p)) && RED(p)));
 }
 
 static void
@@ -132,13 +183,12 @@ check_tree (node root)
   node p;
   if (root == NULL)
     return;
-  root->red = 0;
-  for(p = root->left; p; p = p->left)
-    cnt += !p->red;
+  SETBLACK(root);
+  for(p = LEFT(root); p; p = LEFT(p))
+    cnt += !RED(p);
   check_tree_recurse (root, 0, cnt);
 }
 
-
 #else
 
 #define CHECK_TREE(a)
@@ -155,28 +205,31 @@ static void
 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 			int p_r, int gp_r, int mode)
 {
-  node root = *rootp;
+  node root = DEREFNODEPTR(rootp);
   node *rp, *lp;
-  rp = &(*rootp)->right;
-  lp = &(*rootp)->left;
+  node rpn, lpn;
+  rp = RIGHTPTR(root);
+  rpn = RIGHT(root);
+  lp = LEFTPTR(root);
+  lpn = LEFT(root);
 
   /* See if we have to split this node (both successors red).  */
   if (mode == 1
-      || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
+      || ((rpn) != NULL && (lpn) != NULL && RED(rpn) && RED(lpn)))
     {
       /* This node becomes red, its successors black.  */
-      root->red = 1;
-      if (*rp)
-	(*rp)->red = 0;
-      if (*lp)
-	(*lp)->red = 0;
+      SETRED(root);
+      if (rpn)
+	SETBLACK(rpn);
+      if (lpn)
+	SETBLACK(lpn);
 
       /* If the parent of this node is also red, we have to do
 	 rotations.  */
-      if (parentp != NULL && (*parentp)->red)
+      if (parentp != NULL && RED(DEREFNODEPTR(parentp)))
 	{
-	  node gp = *gparentp;
-	  node p = *parentp;
+	  node gp = DEREFNODEPTR(gparentp);
+	  node p = DEREFNODEPTR(parentp);
 	  /* There are two main cases:
 	     1. The edge types (left or right) of the two red edges differ.
 	     2. Both red edges are of the same type.
@@ -186,45 +239,45 @@ maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 	    {
 	      /* 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;
+	      SETRED(p);
+	      SETRED(gp);
+	      SETBLACK(root);
 	      if (p_r < 0)
 		{
 		  /* Child is left of parent.  */
-		  p->left = *rp;
-		  *rp = p;
-		  gp->right = *lp;
-		  *lp = gp;
+		  SETLEFT(p,rpn);
+		  SETNODEPTR(rp,p);
+		  SETRIGHT(gp,lpn);
+		  SETNODEPTR(lp,gp);
 		}
 	      else
 		{
 		  /* Child is right of parent.  */
-		  p->right = *lp;
-		  *lp = p;
-		  gp->left = *rp;
-		  *rp = gp;
+		  SETRIGHT(p,lpn);
+		  SETNODEPTR(lp,p);
+		  SETLEFT(gp,rpn);
+		  SETNODEPTR(rp,gp);
 		}
-	      *gparentp = root;
+	      SETNODEPTR(gparentp,root);
 	    }
 	  else
 	    {
-	      *gparentp = *parentp;
+	      SETNODEPTR(gparentp,p);
 	      /* Parent becomes the top of the tree, grandparent and
 		 child are its successors.  */
-	      p->red = 0;
-	      gp->red = 1;
+	      SETBLACK(p);
+	      SETRED(gp);
 	      if (p_r < 0)
 		{
 		  /* Left edges.  */
-		  gp->left = p->right;
-		  p->right = gp;
+		  SETLEFT(gp,RIGHT(p));
+		  SETRIGHT(p,gp);
 		}
 	      else
 		{
 		  /* Right edges.  */
-		  gp->right = p->left;
-		  p->left = gp;
+		  SETRIGHT(gp,LEFT(p));
+		  SETLEFT(p,gp);
 		}
 	    }
 	}
@@ -237,25 +290,30 @@ maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 void *
 __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 {
-  node q;
+  node q, root;
   node *parentp = NULL, *gparentp = NULL;
   node *rootp = (node *) vrootp;
   node *nextp;
   int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler.  */
 
+#ifdef USE_MALLOC_LOW_BIT
+  static_assert (alignof (max_align_t) > 1, "malloc must return aligned ptrs");
+#endif
+
   if (rootp == NULL)
     return NULL;
 
   /* This saves some additional tests below.  */
-  if (*rootp != NULL)
-    (*rootp)->red = 0;
+  root = DEREFNODEPTR(rootp);
+  if (root != NULL)
+    SETBLACK(root);
 
-  CHECK_TREE (*rootp);
+  CHECK_TREE (root);
 
   nextp = rootp;
-  while (*nextp != NULL)
+  while (DEREFNODEPTR(nextp) != NULL)
     {
-      node root = *rootp;
+      root = DEREFNODEPTR(rootp);
       r = (*compar) (key, root->key);
       if (r == 0)
 	return root;
@@ -265,8 +323,8 @@ __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 	 That doesn't matter, because the values they contain are never
 	 used again in that case.  */
 
-      nextp = r < 0 ? &root->left : &root->right;
-      if (*nextp == NULL)
+      nextp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root);
+      if (DEREFNODEPTR(nextp) == NULL)
 	break;
 
       gparentp = parentp;
@@ -280,10 +338,20 @@ __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
   q = (struct node_t *) malloc (sizeof (struct node_t));
   if (q != NULL)
     {
-      *nextp = q;			/* link new node to old */
+      /* Make sure the malloc implementation returns naturally aligned
+	 memory blocks when expected.  Or at least even pointers, so we
+	 can use the low bit as red/black flag.  Even though we have a
+	 static_assert to make sure alignof (max_align_t) > 1 there could
+	 be an interposed malloc implementation that might cause havoc by
+	 not obeying the malloc contract.  */
+#ifdef USE_MALLOC_LOW_BIT
+      assert (((uintptr_t) q & (uintptr_t) 0x1) == 0);
+#endif
+      SETNODEPTR(nextp,q);		/* link new node to old */
       q->key = key;			/* initialize new node */
-      q->red = 1;
-      q->left = q->right = NULL;
+      SETRED(q);
+      SETLEFT(q,NULL);
+      SETRIGHT(q,NULL);
 
       if (nextp != rootp)
 	/* There may be two red edges in a row now, which we must avoid by
@@ -303,23 +371,25 @@ weak_alias (__tsearch, tsearch)
 void *
 __tfind (const void *key, void *const *vrootp, __compar_fn_t compar)
 {
+  node root;
   node *rootp = (node *) vrootp;
 
   if (rootp == NULL)
     return NULL;
 
-  CHECK_TREE (*rootp);
+  root = DEREFNODEPTR(rootp);
+  CHECK_TREE (root);
 
-  while (*rootp != NULL)
+  while (DEREFNODEPTR(rootp) != NULL)
     {
-      node root = *rootp;
+      root = DEREFNODEPTR(rootp);
       int r;
 
       r = (*compar) (key, root->key);
       if (r == 0)
 	return root;
 
-      rootp = r < 0 ? &root->left : &root->right;
+      rootp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root);
     }
   return NULL;
 }
@@ -346,13 +416,14 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 
   if (rootp == NULL)
     return NULL;
-  p = *rootp;
+  p = DEREFNODEPTR(rootp);
   if (p == NULL)
     return NULL;
 
   CHECK_TREE (p);
 
-  while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
+  root = DEREFNODEPTR(rootp);
+  while ((cmp = (*compar) (key, root->key)) != 0)
     {
       if (sp == stacksize)
 	{
@@ -363,11 +434,18 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 	}
 
       nodestack[sp++] = rootp;
-      p = *rootp;
-      rootp = ((cmp < 0)
-	       ? &(*rootp)->left
-	       : &(*rootp)->right);
-      if (*rootp == NULL)
+      p = DEREFNODEPTR(rootp);
+      if (cmp < 0)
+	{
+	  rootp = LEFTPTR(p);
+	  root = LEFT(p);
+	}
+      else
+	{
+	  rootp = RIGHTPTR(p);
+	  root = RIGHT(p);
+	}
+      if (root == NULL)
 	return NULL;
     }
 
@@ -380,16 +458,17 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
      it with its successor and unchain the successor.  If there is no
      successor, we really unchain the node to be deleted.  */
 
-  root = *rootp;
+  root = DEREFNODEPTR(rootp);
 
-  r = root->right;
-  q = root->left;
+  r = RIGHT(root);
+  q = LEFT(root);
 
   if (q == NULL || r == NULL)
     unchained = root;
   else
     {
-      node *parent = rootp, *up = &root->right;
+      node *parentp = rootp, *up = RIGHTPTR(root);
+      node upn;
       for (;;)
 	{
 	  if (sp == stacksize)
@@ -399,34 +478,35 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 	      newstack = alloca (sizeof (node *) * stacksize);
 	      nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
 	    }
-	  nodestack[sp++] = parent;
-	  parent = up;
-	  if ((*up)->left == NULL)
+	  nodestack[sp++] = parentp;
+	  parentp = up;
+	  upn = DEREFNODEPTR(up);
+	  if (LEFT(upn) == NULL)
 	    break;
-	  up = &(*up)->left;
+	  up = LEFTPTR(upn);
 	}
-      unchained = *up;
+      unchained = DEREFNODEPTR(up);
     }
 
   /* We know that either 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;
+  r = LEFT(unchained);
   if (r == NULL)
-    r = unchained->right;
+    r = RIGHT(unchained);
   if (sp == 0)
-    *rootp = r;
+    SETNODEPTR(rootp,r);
   else
     {
-      q = *nodestack[sp-1];
-      if (unchained == q->right)
-	q->right = r;
+      q = DEREFNODEPTR(nodestack[sp-1]);
+      if (unchained == RIGHT(q))
+	SETRIGHT(q,r);
       else
-	q->left = r;
+	SETLEFT(q,r);
     }
 
   if (unchained != root)
     root->key = unchained->key;
-  if (!unchained->red)
+  if (!RED(unchained))
     {
       /* 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
@@ -435,17 +515,17 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 	 in the first iteration.  */
       /* NULL nodes are considered black throughout - this is necessary for
 	 correctness.  */
-      while (sp > 0 && (r == NULL || !r->red))
+      while (sp > 0 && (r == NULL || !RED(r)))
 	{
 	  node *pp = nodestack[sp - 1];
-	  p = *pp;
+	  p = DEREFNODEPTR(pp);
 	  /* Two symmetric cases.  */
-	  if (r == p->left)
+	  if (r == LEFT(p))
 	    {
 	      /* 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 = p->right;
-	      if (q->red)
+	      q = RIGHT(p);
+	      if (RED(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
@@ -454,21 +534,21 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 		     leaf in the tree, but we will be able to recognize one
 		     of the following situations, which all require that Q
 		     is black.  */
-		  q->red = 0;
-		  p->red = 1;
+		  SETBLACK(q);
+		  SETRED(p);
 		  /* Left rotate p.  */
-		  p->right = q->left;
-		  q->left = p;
-		  *pp = q;
+		  SETRIGHT(p,LEFT(q));
+		  SETLEFT(q,p);
+		  SETNODEPTR(pp,q);
 		  /* Make sure pp is right if the case below tries to use
 		     it.  */
-		  nodestack[sp++] = pp = &q->left;
-		  q = p->right;
+		  nodestack[sp++] = pp = LEFTPTR(q);
+		  q = RIGHT(p);
 		}
 	      /* We know that Q can't be NULL here.  We also know that Q is
 		 black.  */
-	      if ((q->left == NULL || !q->left->red)
-		  && (q->right == NULL || !q->right->red))
+	      if ((LEFT(q) == NULL || !RED(LEFT(q)))
+		  && (RIGHT(q) == NULL || !RED(RIGHT(q))))
 		{
 		  /* Q has two black successors.  We can simply color Q red.
 		     The whole subtree with root P is now missing one black
@@ -478,7 +558,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 		     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;
+		  SETRED(q);
 		  r = p;
 		}
 	      else
@@ -486,7 +566,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 		  /* 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 (q->right == NULL || !q->right->red)
+		  if (RIGHT(q) == NULL || !RED(RIGHT(q)))
 		    {
 		      /* The left one is red.  We perform the same action as
 			 in maybe_split_for_insert where two red edges are
@@ -498,14 +578,17 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 			 P becomes black, and Q2 gets the color that P had.
 			 This changes the black edge count only for node R and
 			 its successors.  */
-		      node q2 = q->left;
-		      q2->red = p->red;
-		      p->right = q2->left;
-		      q->left = q2->right;
-		      q2->right = q;
-		      q2->left = p;
-		      *pp = q2;
-		      p->red = 0;
+		      node q2 = LEFT(q);
+		      if (RED(p))
+			SETRED(q2);
+		      else
+			SETBLACK(q2);
+		      SETRIGHT(p,LEFT(q2));
+		      SETLEFT(q,RIGHT(q2));
+		      SETRIGHT(q2,q);
+		      SETLEFT(q2,p);
+		      SETNODEPTR(pp,q2);
+		      SETBLACK(p);
 		    }
 		  else
 		    {
@@ -513,15 +596,18 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 			 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.  */
-		      q->red = p->red;
-		      p->red = 0;
+		      if (RED(p))
+			SETRED(q);
+		      else
+			SETBLACK(q);
+		      SETBLACK(p);
 
-		      q->right->red = 0;
+		      SETBLACK(RIGHT(q));
 
 		      /* left rotate p */
-		      p->right = q->left;
-		      q->left = p;
-		      *pp = q;
+		      SETRIGHT(p,LEFT(q));
+		      SETLEFT(q,p);
+		      SETNODEPTR(pp,q);
 		    }
 
 		  /* We're done.  */
@@ -532,44 +618,50 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 	  else
 	    {
 	      /* Comments: see above.  */
-	      q = p->left;
-	      if (q->red)
+	      q = LEFT(p);
+	      if (RED(q))
 		{
-		  q->red = 0;
-		  p->red = 1;
-		  p->left = q->right;
-		  q->right = p;
-		  *pp = q;
-		  nodestack[sp++] = pp = &q->right;
-		  q = p->left;
+		  SETBLACK(q);
+		  SETRED(p);
+		  SETLEFT(p,RIGHT(q));
+		  SETRIGHT(q,p);
+		  SETNODEPTR(pp,q);
+		  nodestack[sp++] = pp = RIGHTPTR(q);
+		  q = LEFT(p);
 		}
-	      if ((q->right == NULL || !q->right->red)
-		       && (q->left == NULL || !q->left->red))
+	      if ((RIGHT(q) == NULL || !RED(RIGHT(q)))
+		  && (LEFT(q) == NULL || !RED(LEFT(q))))
 		{
-		  q->red = 1;
+		  SETRED(q);
 		  r = p;
 		}
 	      else
 		{
-		  if (q->left == NULL || !q->left->red)
+		  if (LEFT(q) == NULL || !RED(LEFT(q)))
 		    {
-		      node q2 = q->right;
-		      q2->red = p->red;
-		      p->left = q2->right;
-		      q->right = q2->left;
-		      q2->left = q;
-		      q2->right = p;
-		      *pp = q2;
-		      p->red = 0;
+		      node q2 = RIGHT(q);
+		      if (RED(p))
+			SETRED(q2);
+		      else
+			SETBLACK(q2);
+		      SETLEFT(p,RIGHT(q2));
+		      SETRIGHT(q,LEFT(q2));
+		      SETLEFT(q2,q);
+		      SETRIGHT(q2,p);
+		      SETNODEPTR(pp,q2);
+		      SETBLACK(p);
 		    }
 		  else
 		    {
-		      q->red = p->red;
-		      p->red = 0;
-		      q->left->red = 0;
-		      p->left = q->right;
-		      q->right = p;
-		      *pp = q;
+		      if (RED(p))
+			SETRED(q);
+		      else
+			SETBLACK(q);
+		      SETBLACK(p);
+		      SETBLACK(LEFT(q));
+		      SETLEFT(p,RIGHT(q));
+		      SETRIGHT(q,p);
+		      SETNODEPTR(pp,q);
 		    }
 		  sp = 1;
 		  r = NULL;
@@ -578,7 +670,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 	  --sp;
 	}
       if (r != NULL)
-	r->red = 0;
+	SETBLACK(r);
     }
 
   free (unchained);
@@ -597,16 +689,16 @@ trecurse (const void *vroot, __action_fn_t action, int level)
 {
   const_node root = (const_node) vroot;
 
-  if (root->left == NULL && root->right == NULL)
+  if (LEFT(root) == NULL && RIGHT(root) == NULL)
     (*action) (root, leaf, level);
   else
     {
       (*action) (root, preorder, level);
-      if (root->left != NULL)
-	trecurse (root->left, action, level + 1);
+      if (LEFT(root) != NULL)
+	trecurse (LEFT(root), action, level + 1);
       (*action) (root, postorder, level);
-      if (root->right != NULL)
-	trecurse (root->right, action, level + 1);
+      if (RIGHT(root) != NULL)
+	trecurse (RIGHT(root), action, level + 1);
       (*action) (root, endorder, level);
     }
 }
@@ -620,7 +712,7 @@ __twalk (const void *vroot, __action_fn_t action)
 {
   const_node root = (const_node) vroot;
 
-  CHECK_TREE (root);
+  CHECK_TREE ((node) root);
 
   if (root != NULL && action != NULL)
     trecurse (root, action, 0);
@@ -636,10 +728,10 @@ static void
 internal_function
 tdestroy_recurse (node root, __free_fn_t freefct)
 {
-  if (root->left != NULL)
-    tdestroy_recurse (root->left, freefct);
-  if (root->right != NULL)
-    tdestroy_recurse (root->right, freefct);
+  if (LEFT(root) != NULL)
+    tdestroy_recurse (LEFT(root), freefct);
+  if (RIGHT(root) != NULL)
+    tdestroy_recurse (RIGHT(root), freefct);
   (*freefct) ((void *) root->key);
   /* Free the node itself.  */
   free (root);