Remove rbt_nil

Since this is an intrusive tree, rbt_nil is the whole size of the node
and can be quite large.  For example, miscelm is ~100 bytes.

2 files changed, 86 insertions, 109 deletions

diff --git a/include/jemalloc/internal/rb.h b/include/jemalloc/internal/rb.h
index 30ccab4..3770342 100644
--- a/include/jemalloc/internal/rb.h
+++ b/include/jemalloc/internal/rb.h
@@ -42,7 +42,6 @@ struct {								\
 #define	rb_tree(a_type)							\
 struct {								\
     a_type *rbt_root;							\
-    a_type rbt_nil;							\
 }
 
 /* Left accessors. */
@@ -84,8 +83,8 @@ struct {								\
 #define	rbt_node_new(a_type, a_field, a_rbt, a_node) do {		\
     /* Bookkeeping bit cannot be used by node pointer. */		\
     assert(((uintptr_t)(a_node) & 0x1) == 0);				\
-    rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil);	\
-    rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil);	\
+    rbtn_left_set(a_type, a_field, (a_node), NULL);	\
+    rbtn_right_set(a_type, a_field, (a_node), NULL);	\
     rbtn_red_set(a_type, a_field, (a_node));				\
 } while (0)
 #else
@@ -111,25 +110,23 @@ struct {								\
 
 /* Node initializer. */
 #define	rbt_node_new(a_type, a_field, a_rbt, a_node) do {		\
-    rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil);	\
-    rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil);	\
+    rbtn_left_set(a_type, a_field, (a_node), NULL);	\
+    rbtn_right_set(a_type, a_field, (a_node), NULL);	\
     rbtn_red_set(a_type, a_field, (a_node));				\
 } while (0)
 #endif
 
 /* Tree initializer. */
 #define	rb_new(a_type, a_field, a_rbt) do {				\
-    (a_rbt)->rbt_root = &(a_rbt)->rbt_nil;				\
-    rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil);		\
-    rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil);			\
+    (a_rbt)->rbt_root = NULL;						\
 } while (0)
 
 /* Internal utility macros. */
 #define	rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do {		\
     (r_node) = (a_root);						\
-    if ((r_node) != &(a_rbt)->rbt_nil) {				\
+    if ((r_node) != NULL) {						\
 	for (;								\
-	  rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\
+	  rbtn_left_get(a_type, a_field, (r_node)) != NULL;		\
 	  (r_node) = rbtn_left_get(a_type, a_field, (r_node))) {	\
 	}								\
     }									\
@@ -137,10 +134,9 @@ struct {								\
 
 #define	rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do {		\
     (r_node) = (a_root);						\
-    if ((r_node) != &(a_rbt)->rbt_nil) {				\
-	for (; rbtn_right_get(a_type, a_field, (r_node)) !=		\
-	  &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field,	\
-	  (r_node))) {							\
+    if ((r_node) != NULL) {						\
+	for (; rbtn_right_get(a_type, a_field, (r_node)) != NULL;	\
+	  (r_node) = rbtn_right_get(a_type, a_field, (r_node))) {	\
 	}								\
     }									\
 } while (0)
@@ -335,8 +331,8 @@ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *),	\
  *       Args:
  *         tree: Pointer to an initialized red-black tree object.
  *         cb  : Callback function, which, if non-null, is called for each node
- *               during iteration.  There is no way to stop iteration once it has
- *               begun.
+ *               during iteration.  There is no way to stop iteration once it
+ *               has begun.
  *         arg : Opaque pointer passed to cb().
  */
 #define	rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp)	\
@@ -346,36 +342,30 @@ a_prefix##new(a_rbt_type *rbtree) {					\
 }									\
 a_attr bool								\
 a_prefix##empty(a_rbt_type *rbtree) {					\
-    return (rbtree->rbt_root == &rbtree->rbt_nil);			\
+    return (rbtree->rbt_root == NULL);					\
 }									\
 a_attr a_type *								\
 a_prefix##first(a_rbt_type *rbtree) {					\
     a_type *ret;							\
     rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret);		\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = NULL;							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
 a_prefix##last(a_rbt_type *rbtree) {					\
     a_type *ret;							\
     rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret);		\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = NULL;							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
 a_prefix##next(a_rbt_type *rbtree, a_type *node) {			\
     a_type *ret;							\
-    if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) {	\
+    if (rbtn_right_get(a_type, a_field, node) != NULL) {		\
 	rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type,	\
 	  a_field, node), ret);						\
     } else {								\
 	a_type *tnode = rbtree->rbt_root;				\
-	assert(tnode != &rbtree->rbt_nil);				\
-	ret = &rbtree->rbt_nil;						\
+	assert(tnode != NULL);						\
+	ret = NULL;							\
 	while (true) {							\
 	    int cmp = (a_cmp)(node, tnode);				\
 	    if (cmp < 0) {						\
@@ -386,24 +376,21 @@ a_prefix##next(a_rbt_type *rbtree, a_type *node) {			\
 	    } else {							\
 		break;							\
 	    }								\
-	    assert(tnode != &rbtree->rbt_nil);				\
+	    assert(tnode != NULL);					\
 	}								\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = (NULL);							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
 a_prefix##prev(a_rbt_type *rbtree, a_type *node) {			\
     a_type *ret;							\
-    if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) {	\
+    if (rbtn_left_get(a_type, a_field, node) != NULL) {			\
 	rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type,	\
 	  a_field, node), ret);						\
     } else {								\
 	a_type *tnode = rbtree->rbt_root;				\
-	assert(tnode != &rbtree->rbt_nil);				\
-	ret = &rbtree->rbt_nil;						\
+	assert(tnode != NULL);						\
+	ret = NULL;							\
 	while (true) {							\
 	    int cmp = (a_cmp)(node, tnode);				\
 	    if (cmp < 0) {						\
@@ -414,12 +401,9 @@ a_prefix##prev(a_rbt_type *rbtree, a_type *node) {			\
 	    } else {							\
 		break;							\
 	    }								\
-	    assert(tnode != &rbtree->rbt_nil);				\
+	    assert(tnode != NULL);					\
 	}								\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = (NULL);							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
@@ -427,7 +411,7 @@ a_prefix##search(a_rbt_type *rbtree, const a_type *key) {		\
     a_type *ret;							\
     int cmp;								\
     ret = rbtree->rbt_root;						\
-    while (ret != &rbtree->rbt_nil					\
+    while (ret != NULL							\
       && (cmp = (a_cmp)(key, ret)) != 0) {				\
 	if (cmp < 0) {							\
 	    ret = rbtn_left_get(a_type, a_field, ret);			\
@@ -435,17 +419,14 @@ a_prefix##search(a_rbt_type *rbtree, const a_type *key) {		\
 	    ret = rbtn_right_get(a_type, a_field, ret);			\
 	}								\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = (NULL);							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
 a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) {		\
     a_type *ret;							\
     a_type *tnode = rbtree->rbt_root;					\
-    ret = &rbtree->rbt_nil;						\
-    while (tnode != &rbtree->rbt_nil) {					\
+    ret = NULL;								\
+    while (tnode != NULL) {						\
 	int cmp = (a_cmp)(key, tnode);					\
 	if (cmp < 0) {							\
 	    ret = tnode;						\
@@ -457,17 +438,14 @@ a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) {		\
 	    break;							\
 	}								\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = (NULL);							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
 a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) {		\
     a_type *ret;							\
     a_type *tnode = rbtree->rbt_root;					\
-    ret = &rbtree->rbt_nil;						\
-    while (tnode != &rbtree->rbt_nil) {					\
+    ret = NULL;								\
+    while (tnode != NULL) {						\
 	int cmp = (a_cmp)(key, tnode);					\
 	if (cmp < 0) {							\
 	    tnode = rbtn_left_get(a_type, a_field, tnode);		\
@@ -479,9 +457,6 @@ a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) {		\
 	    break;							\
 	}								\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = (NULL);							\
-    }									\
     return (ret);							\
 }									\
 a_attr void								\
@@ -493,7 +468,7 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) {			\
     rbt_node_new(a_type, a_field, rbtree, node);			\
     /* Wind. */								\
     path->node = rbtree->rbt_root;					\
-    for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) {	\
+    for (pathp = path; pathp->node != NULL; pathp++) {			\
 	int cmp = pathp->cmp = a_cmp(node, pathp->node);		\
 	assert(cmp != 0);						\
 	if (cmp < 0) {							\
@@ -513,7 +488,8 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) {			\
 	    rbtn_left_set(a_type, a_field, cnode, left);		\
 	    if (rbtn_red_get(a_type, a_field, left)) {			\
 		a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
-		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
+		if (leftleft != NULL && rbtn_red_get(a_type, a_field,	\
+		  leftleft)) {						\
 		    /* Fix up 4-node. */				\
 		    a_type *tnode;					\
 		    rbtn_black_set(a_type, a_field, leftleft);		\
@@ -528,7 +504,8 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) {			\
 	    rbtn_right_set(a_type, a_field, cnode, right);		\
 	    if (rbtn_red_get(a_type, a_field, right)) {			\
 		a_type *left = rbtn_left_get(a_type, a_field, cnode);	\
-		if (rbtn_red_get(a_type, a_field, left)) {		\
+		if (left != NULL && rbtn_red_get(a_type, a_field,	\
+		  left)) {						\
 		    /* Split 4-node. */					\
 		    rbtn_black_set(a_type, a_field, left);		\
 		    rbtn_black_set(a_type, a_field, right);		\
@@ -561,7 +538,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
     /* Wind. */								\
     nodep = NULL; /* Silence compiler warning. */			\
     path->node = rbtree->rbt_root;					\
-    for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) {	\
+    for (pathp = path; pathp->node != NULL; pathp++) {			\
 	int cmp = pathp->cmp = a_cmp(node, pathp->node);		\
 	if (cmp < 0) {							\
 	    pathp[1].node = rbtn_left_get(a_type, a_field,		\
@@ -573,7 +550,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 	        /* Find node's successor, in preparation for swap. */	\
 		pathp->cmp = 1;						\
 		nodep = pathp;						\
-		for (pathp++; pathp->node != &rbtree->rbt_nil;		\
+		for (pathp++; pathp->node != NULL;			\
 		  pathp++) {						\
 		    pathp->cmp = -1;					\
 		    pathp[1].node = rbtn_left_get(a_type, a_field,	\
@@ -616,7 +593,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 	}								\
     } else {								\
 	a_type *left = rbtn_left_get(a_type, a_field, node);		\
-	if (left != &rbtree->rbt_nil) {					\
+	if (left != NULL) {						\
 	    /* node has no successor, but it has a left child.        */\
 	    /* Splice node out, without losing the left child.        */\
 	    assert(!rbtn_red_get(a_type, a_field, node));		\
@@ -636,33 +613,32 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 	    return;							\
 	} else if (pathp == path) {					\
 	    /* The tree only contained one node. */			\
-	    rbtree->rbt_root = &rbtree->rbt_nil;			\
+	    rbtree->rbt_root = NULL;					\
 	    return;							\
 	}								\
     }									\
     if (rbtn_red_get(a_type, a_field, pathp->node)) {			\
 	/* Prune red node, which requires no fixup. */			\
 	assert(pathp[-1].cmp < 0);					\
-	rbtn_left_set(a_type, a_field, pathp[-1].node,			\
-	  &rbtree->rbt_nil);						\
+	rbtn_left_set(a_type, a_field, pathp[-1].node, NULL);		\
 	return;								\
     }									\
     /* The node to be pruned is black, so unwind until balance is     */\
     /* restored.                                                      */\
-    pathp->node = &rbtree->rbt_nil;					\
+    pathp->node = NULL;							\
     for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {	\
 	assert(pathp->cmp != 0);					\
 	if (pathp->cmp < 0) {						\
 	    rbtn_left_set(a_type, a_field, pathp->node,			\
 	      pathp[1].node);						\
-	    assert(!rbtn_red_get(a_type, a_field, pathp[1].node));	\
 	    if (rbtn_red_get(a_type, a_field, pathp->node)) {		\
 		a_type *right = rbtn_right_get(a_type, a_field,		\
 		  pathp->node);						\
 		a_type *rightleft = rbtn_left_get(a_type, a_field,	\
 		  right);						\
 		a_type *tnode;						\
-		if (rbtn_red_get(a_type, a_field, rightleft)) {		\
+		if (rightleft != NULL && rbtn_red_get(a_type, a_field,	\
+		  rightleft)) {						\
 		    /* In the following diagrams, ||, //, and \\      */\
 		    /* indicate the path to the removed node.         */\
 		    /*                                                */\
@@ -705,7 +681,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 		  pathp->node);						\
 		a_type *rightleft = rbtn_left_get(a_type, a_field,	\
 		  right);						\
-		if (rbtn_red_get(a_type, a_field, rightleft)) {		\
+		if (rightleft != NULL && rbtn_red_get(a_type, a_field,	\
+		  rightleft)) {						\
 		    /*      ||                                        */\
 		    /*    pathp(b)                                    */\
 		    /*  //        \                                   */\
@@ -759,7 +736,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 		  left);						\
 		a_type *leftrightleft = rbtn_left_get(a_type, a_field,	\
 		  leftright);						\
-		if (rbtn_red_get(a_type, a_field, leftrightleft)) {	\
+		if (leftrightleft != NULL && rbtn_red_get(a_type,	\
+		  a_field, leftrightleft)) {				\
 		    /*      ||                                        */\
 		    /*    pathp(b)                                    */\
 		    /*   /        \\                                  */\
@@ -785,7 +763,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 		    /*   (b)                                          */\
 		    /*   /                                            */\
 		    /* (b)                                            */\
-		    assert(leftright != &rbtree->rbt_nil);		\
+		    assert(leftright != NULL);				\
 		    rbtn_red_set(a_type, a_field, leftright);		\
 		    rbtn_rotate_right(a_type, a_field, pathp->node,	\
 		      tnode);						\
@@ -808,7 +786,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 		return;							\
 	    } else if (rbtn_red_get(a_type, a_field, pathp->node)) {	\
 		a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
-		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
+		if (leftleft != NULL && rbtn_red_get(a_type, a_field,	\
+		  leftleft)) {						\
 		    /*        ||                                      */\
 		    /*      pathp(r)                                  */\
 		    /*     /        \\                                */\
@@ -846,7 +825,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 		}							\
 	    } else {							\
 		a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
-		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
+		if (leftleft != NULL && rbtn_red_get(a_type, a_field,	\
+		  leftleft)) {						\
 		    /*               ||                               */\
 		    /*             pathp(b)                           */\
 		    /*            /        \\                         */\
@@ -892,13 +872,13 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) {			\
 a_attr a_type *								\
 a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node,		\
   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {		\
-    if (node == &rbtree->rbt_nil) {					\
-	return (&rbtree->rbt_nil);					\
+    if (node == NULL) {							\
+	return (NULL);							\
     } else {								\
 	a_type *ret;							\
 	if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type,	\
-	  a_field, node), cb, arg)) != &rbtree->rbt_nil			\
-	  || (ret = cb(rbtree, node, arg)) != NULL) {			\
+	  a_field, node), cb, arg)) != NULL || (ret = cb(rbtree, node,	\
+	  arg)) != NULL) {						\
 	    return (ret);						\
 	}								\
 	return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,	\
@@ -912,8 +892,8 @@ a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node,	\
     if (cmp < 0) {							\
 	a_type *ret;							\
 	if ((ret = a_prefix##iter_start(rbtree, start,			\
-	  rbtn_left_get(a_type, a_field, node), cb, arg)) !=		\
-	  &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) {	\
+	  rbtn_left_get(a_type, a_field, node), cb, arg)) != NULL ||	\
+	  (ret = cb(rbtree, node, arg)) != NULL) {			\
 	    return (ret);						\
 	}								\
 	return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,	\
@@ -940,21 +920,18 @@ a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)(	\
     } else {								\
 	ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = NULL;							\
-    }									\
     return (ret);							\
 }									\
 a_attr a_type *								\
 a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node,	\
   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {		\
-    if (node == &rbtree->rbt_nil) {					\
-	return (&rbtree->rbt_nil);					\
+    if (node == NULL) {							\
+	return (NULL);							\
     } else {								\
 	a_type *ret;							\
 	if ((ret = a_prefix##reverse_iter_recurse(rbtree,		\
-	  rbtn_right_get(a_type, a_field, node), cb, arg)) !=		\
-	  &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) {	\
+	  rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL ||	\
+	  (ret = cb(rbtree, node, arg)) != NULL) {			\
 	    return (ret);						\
 	}								\
 	return (a_prefix##reverse_iter_recurse(rbtree,			\
@@ -969,8 +946,8 @@ a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start,		\
     if (cmp > 0) {							\
 	a_type *ret;							\
 	if ((ret = a_prefix##reverse_iter_start(rbtree, start,		\
-	  rbtn_right_get(a_type, a_field, node), cb, arg)) !=		\
-	  &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) {	\
+	  rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL ||	\
+	  (ret = cb(rbtree, node, arg)) != NULL) {			\
 	    return (ret);						\
 	}								\
 	return (a_prefix##reverse_iter_recurse(rbtree,			\
@@ -998,23 +975,20 @@ a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start,		\
 	ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root,	\
 	  cb, arg);							\
     }									\
-    if (ret == &rbtree->rbt_nil) {					\
-	ret = NULL;							\
-    }									\
     return (ret);							\
 }									\
 a_attr void								\
 a_prefix##destroy_recurse(a_rbt_type *rbtree, a_type *node, void (*cb)(	\
   a_type *, void *), void *arg) {					\
-    if (node == &rbtree->rbt_nil) {					\
+    if (node == NULL) {							\
 	return;								\
     }									\
     a_prefix##destroy_recurse(rbtree, rbtn_left_get(a_type, a_field,	\
       node), cb, arg);							\
-    rbtn_left_set(a_type, a_field, (node), &rbtree->rbt_nil);		\
+    rbtn_left_set(a_type, a_field, (node), NULL);			\
     a_prefix##destroy_recurse(rbtree, rbtn_right_get(a_type, a_field,	\
       node), cb, arg);							\
-    rbtn_right_set(a_type, a_field, (node), &rbtree->rbt_nil);		\
+    rbtn_right_set(a_type, a_field, (node), NULL);			\
     if (cb) {								\
 	cb(node, arg);							\
     }									\
@@ -1023,7 +997,7 @@ a_attr void								\
 a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *),	\
   void *arg) {								\
     a_prefix##destroy_recurse(rbtree, rbtree->rbt_root, cb, arg);	\
-    rbtree->rbt_root = &rbtree->rbt_nil;				\
+    rbtree->rbt_root = NULL;						\
 }
 
 #endif /* RB_H_ */
diff --git a/test/unit/rb.c b/test/unit/rb.c
index 14132c1..cf3d3a7 100644
--- a/test/unit/rb.c
+++ b/test/unit/rb.c
@@ -3,7 +3,7 @@
 #define	rbtn_black_height(a_type, a_field, a_rbt, r_height) do {	\
     a_type *rbp_bh_t;							\
     for (rbp_bh_t = (a_rbt)->rbt_root, (r_height) = 0;			\
-      rbp_bh_t != &(a_rbt)->rbt_nil;					\
+	 rbp_bh_t != NULL;						\
       rbp_bh_t = rbtn_left_get(a_type, a_field, rbp_bh_t)) {		\
 	if (!rbtn_red_get(a_type, a_field, rbp_bh_t)) {			\
 	    (r_height)++;						\
@@ -68,38 +68,43 @@ TEST_BEGIN(test_rb_empty)
 TEST_END
 
 static unsigned
-tree_recurse(node_t *node, unsigned black_height, unsigned black_depth,
-    node_t *nil)
+tree_recurse(node_t *node, unsigned black_height, unsigned black_depth)
 {
 	unsigned ret = 0;
-	node_t *left_node = rbtn_left_get(node_t, link, node);
-	node_t *right_node = rbtn_right_get(node_t, link, node);
+	node_t *left_node;
+	node_t *right_node;
+
+	if (node == NULL)
+		return (ret);
+
+	left_node = rbtn_left_get(node_t, link, node);
+	right_node = rbtn_right_get(node_t, link, node);
 
 	if (!rbtn_red_get(node_t, link, node))
 		black_depth++;
 
 	/* Red nodes must be interleaved with black nodes. */
 	if (rbtn_red_get(node_t, link, node)) {
-		assert_false(rbtn_red_get(node_t, link, left_node),
-		    "Node should be black");
-		assert_false(rbtn_red_get(node_t, link, right_node),
-		    "Node should be black");
+		if (left_node != NULL)
+			assert_false(rbtn_red_get(node_t, link, left_node),
+				"Node should be black");
+		if (right_node != NULL)
+			assert_false(rbtn_red_get(node_t, link, right_node),
+			    "Node should be black");
 	}
 
-	if (node == nil)
-		return (ret);
 	/* Self. */
 	assert_u32_eq(node->magic, NODE_MAGIC, "Bad magic");
 
 	/* Left subtree. */
-	if (left_node != nil)
-		ret += tree_recurse(left_node, black_height, black_depth, nil);
+	if (left_node != NULL)
+		ret += tree_recurse(left_node, black_height, black_depth);
 	else
 		ret += (black_depth != black_height);
 
 	/* Right subtree. */
-	if (right_node != nil)
-		ret += tree_recurse(right_node, black_height, black_depth, nil);
+	if (right_node != NULL)
+		ret += tree_recurse(right_node, black_height, black_depth);
 	else
 		ret += (black_depth != black_height);
 
@@ -181,8 +186,7 @@ node_remove(tree_t *tree, node_t *node, unsigned nnodes)
 	node->magic = 0;
 
 	rbtn_black_height(node_t, link, tree, black_height);
-	imbalances = tree_recurse(tree->rbt_root, black_height, 0,
-	    &(tree->rbt_nil));
+	imbalances = tree_recurse(tree->rbt_root, black_height, 0);
 	assert_u_eq(imbalances, 0, "Tree is unbalanced");
 	assert_u_eq(tree_iterate(tree), nnodes-1,
 	    "Unexpected node iteration count");
@@ -253,7 +257,6 @@ TEST_BEGIN(test_rb_random)
 		for (j = 1; j <= NNODES; j++) {
 			/* Initialize tree and nodes. */
 			tree_new(&tree);
-			tree.rbt_nil.magic = 0;
 			for (k = 0; k < j; k++) {
 				nodes[k].magic = NODE_MAGIC;
 				nodes[k].key = bag[k];
@@ -266,7 +269,7 @@ TEST_BEGIN(test_rb_random)
 				rbtn_black_height(node_t, link, &tree,
 				    black_height);
 				imbalances = tree_recurse(tree.rbt_root,
-				    black_height, 0, &(tree.rbt_nil));
+				    black_height, 0);
 				assert_u_eq(imbalances, 0,
 				    "Tree is unbalanced");