Implement red-black trees without using parent pointers, and store the

color bit in the least significant bit of the right child pointer, in
order to reduce red-black tree linkage overhead by ~2X as compared to
sys/tree.h.

Use the new red-black tree implementation in malloc, which drops
memory usage by ~0.5 or ~1%, for 32- and 64-bit systems, respectively.

2 files changed, 947 insertions, 116 deletions

diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index 0d10b06..990cec9 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -142,7 +142,6 @@ __FBSDID("$FreeBSD$");
 #include <sys/time.h>
 #include <sys/types.h>
 #include <sys/sysctl.h>
-#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/ktrace.h> /* Must come after several other sys/ includes. */
 
@@ -175,6 +174,8 @@ __FBSDID("$FreeBSD$");
 #endif
 #include <assert.h>
 
+#include "rb.h"
+
 #ifdef MALLOC_DEBUG
    /* Disable inlining to make debugging easier. */
 #  define inline
@@ -439,10 +440,10 @@ struct chunk_stats_s {
 typedef struct extent_node_s extent_node_t;
 struct extent_node_s {
 	/* Linkage for the size/address-ordered tree. */
-	RB_ENTRY(extent_node_s) link_szad;
+	rb_node(extent_node_t) link_szad;
 
 	/* Linkage for the address-ordered tree. */
-	RB_ENTRY(extent_node_s) link_ad;
+	rb_node(extent_node_t) link_ad;
 
 	/* Pointer to the extent that this tree node is responsible for. */
 	void	*addr;
@@ -450,10 +451,7 @@ struct extent_node_s {
 	/* Total region size. */
 	size_t	size;
 };
-typedef struct extent_tree_szad_s extent_tree_szad_t;
-RB_HEAD(extent_tree_szad_s, extent_node_s);
-typedef struct extent_tree_ad_s extent_tree_ad_t;
-RB_HEAD(extent_tree_ad_s, extent_node_s);
+typedef rb_tree(extent_node_t) extent_tree_t;
 
 /******************************************************************************/
 /*
@@ -480,7 +478,7 @@ struct arena_chunk_s {
 	arena_t		*arena;
 
 	/* Linkage for the arena's chunk tree. */
-	RB_ENTRY(arena_chunk_s) link;
+	rb_node(arena_chunk_t) link;
 
 	/*
 	 * Number of pages in use.  This is maintained in order to make
@@ -495,7 +493,7 @@ struct arena_chunk_s {
 	 * Tree of extent nodes that are embedded in the arena chunk header
 	 * page(s).  These nodes are used by arena_chunk_node_alloc().
 	 */
-	extent_tree_ad_t nodes;
+	extent_tree_t	nodes;
 	extent_node_t	*nodes_past;
 
 	/*
@@ -505,13 +503,12 @@ struct arena_chunk_s {
 	 */
 	arena_chunk_map_t map[1]; /* Dynamically sized. */
 };
-typedef struct arena_chunk_tree_s arena_chunk_tree_t;
-RB_HEAD(arena_chunk_tree_s, arena_chunk_s);
+typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;
 
 typedef struct arena_run_s arena_run_t;
 struct arena_run_s {
 	/* Linkage for run trees. */
-	RB_ENTRY(arena_run_s) link;
+	rb_node(arena_run_t) link;
 
 #ifdef MALLOC_DEBUG
 	uint32_t	magic;
@@ -530,8 +527,7 @@ struct arena_run_s {
 	/* Bitmask of in-use regions (0: in use, 1: free). */
 	unsigned	regs_mask[1]; /* Dynamically sized. */
 };
-typedef struct arena_run_tree_s arena_run_tree_t;
-RB_HEAD(arena_run_tree_s, arena_run_s);
+typedef rb_tree(arena_run_t) arena_run_tree_t;
 
 struct arena_bin_s {
 	/*
@@ -613,11 +609,11 @@ struct arena_s {
 	 * using one set of nodes, since one is needed for first-best-fit run
 	 * allocation, and the other is needed for coalescing.
 	 */
-	extent_tree_szad_t	runs_avail_szad;
-	extent_tree_ad_t	runs_avail_ad;
+	extent_tree_t		runs_avail_szad;
+	extent_tree_t		runs_avail_ad;
 
 	/* Tree of this arena's allocated (in-use) runs. */
-	extent_tree_ad_t	runs_alloced_ad;
+	extent_tree_t		runs_alloced_ad;
 
 #ifdef MALLOC_BALANCE
 	/*
@@ -694,7 +690,7 @@ static size_t		arena_maxclass; /* Max size class for arenas. */
 static malloc_mutex_t	huge_mtx;
 
 /* Tree of chunks that are stand-alone huge allocations. */
-static extent_tree_ad_t	huge;
+static extent_tree_t	huge;
 
 #ifdef MALLOC_DSS
 /*
@@ -715,8 +711,8 @@ static void		*dss_max;
  * address space.  Depending on function, different tree orderings are needed,
  * which is why there are two trees with the same contents.
  */
-static extent_tree_szad_t dss_chunks_szad;
-static extent_tree_ad_t	dss_chunks_ad;
+static extent_tree_t	dss_chunks_szad;
+static extent_tree_t	dss_chunks_ad;
 #endif
 
 #ifdef MALLOC_STATS
@@ -1431,9 +1427,20 @@ extent_szad_comp(extent_node_t *a, extent_node_t *b)
 	return (ret);
 }
 
-/* Generate red-black tree code for size/address-ordered extents. */
-RB_GENERATE_STATIC(extent_tree_szad_s, extent_node_s, link_szad,
-    extent_szad_comp)
+/* Wrap large red-black tree macros in functions. */
+static void
+extent_tree_szad_insert(extent_tree_t *tree, extent_node_t *extent)
+{
+
+	rb_insert(extent_node_t, link_szad, extent_szad_comp, tree, extent);
+}
+
+static void
+extent_tree_szad_remove(extent_tree_t *tree, extent_node_t *extent)
+{
+
+	rb_remove(extent_node_t, link_szad, extent_szad_comp, tree, extent);
+}
 
 static inline int
 extent_ad_comp(extent_node_t *a, extent_node_t *b)
@@ -1444,8 +1451,20 @@ extent_ad_comp(extent_node_t *a, extent_node_t *b)
 	return ((a_addr > b_addr) - (a_addr < b_addr));
 }
 
-/* Generate red-black tree code for address-ordered extents. */
-RB_GENERATE_STATIC(extent_tree_ad_s, extent_node_s, link_ad, extent_ad_comp)
+/* Wrap large red-black tree macros in functions. */
+static void
+extent_tree_ad_insert(extent_tree_t *tree, extent_node_t *extent)
+{
+
+	rb_insert(extent_node_t, link_ad, extent_ad_comp, tree, extent);
+}
+
+static void
+extent_tree_ad_remove(extent_tree_t *tree, extent_node_t *extent)
+{
+
+	rb_remove(extent_node_t, link_ad, extent_ad_comp, tree, extent);
+}
 
 /*
  * End extent tree code.
@@ -1561,14 +1580,15 @@ chunk_recycle_dss(size_t size, bool zero)
 	key.addr = NULL;
 	key.size = size;
 	malloc_mutex_lock(&dss_mtx);
-	node = RB_NFIND(extent_tree_szad_s, &dss_chunks_szad, &key);
+	rb_nsearch(extent_node_t, link_szad, extent_szad_comp, &dss_chunks_szad,
+	    &key, node);
 	if (node != NULL) {
 		void *ret = node->addr;
 
 		/* Remove node from the tree. */
-		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
+		extent_tree_szad_remove(&dss_chunks_szad, node);
 		if (node->size == size) {
-			RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad, node);
+			extent_tree_ad_remove(&dss_chunks_ad, node);
 			base_node_dealloc(node);
 		} else {
 			/*
@@ -1579,7 +1599,7 @@ chunk_recycle_dss(size_t size, bool zero)
 			assert(node->size > size);
 			node->addr = (void *)((uintptr_t)node->addr + size);
 			node->size -= size;
-			RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
+			extent_tree_szad_insert(&dss_chunks_szad, node);
 		}
 		malloc_mutex_unlock(&dss_mtx);
 
@@ -1719,7 +1739,8 @@ chunk_dealloc_dss_record(void *chunk, size_t size)
 	extent_node_t *node, *prev, key;
 
 	key.addr = (void *)((uintptr_t)chunk + size);
-	node = RB_NFIND(extent_tree_ad_s, &dss_chunks_ad, &key);
+	rb_nsearch(extent_node_t, link_ad, extent_ad_comp, &dss_chunks_ad,
+	    &key, node);
 	/* Try to coalesce forward. */
 	if (node != NULL && node->addr == key.addr) {
 		/*
@@ -1727,10 +1748,10 @@ chunk_dealloc_dss_record(void *chunk, size_t size)
 		 * not change the position within dss_chunks_ad, so only
 		 * remove/insert from/into dss_chunks_szad.
 		 */
-		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
+		extent_tree_szad_remove(&dss_chunks_szad, node);
 		node->addr = chunk;
 		node->size += size;
-		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
+		extent_tree_szad_insert(&dss_chunks_szad, node);
 	} else {
 		/*
 		 * Coalescing forward failed, so insert a new node.  Drop
@@ -1744,12 +1765,13 @@ chunk_dealloc_dss_record(void *chunk, size_t size)
 			return (NULL);
 		node->addr = chunk;
 		node->size = size;
-		RB_INSERT(extent_tree_ad_s, &dss_chunks_ad, node);
-		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
+		extent_tree_ad_insert(&dss_chunks_ad, node);
+		extent_tree_szad_insert(&dss_chunks_szad, node);
 	}
 
 	/* Try to coalesce backward. */
-	prev = RB_PREV(extent_tree_ad_s, &dss_chunks_ad, node);
+	rb_prev(extent_node_t, link_ad, extent_ad_comp, &dss_chunks_ad, node,
+	    prev);
 	if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
 	    chunk) {
 		/*
@@ -1757,13 +1779,13 @@ chunk_dealloc_dss_record(void *chunk, size_t size)
 		 * not change the position within dss_chunks_ad, so only
 		 * remove/insert node from/into dss_chunks_szad.
 		 */
-		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, prev);
-		RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad, prev);
+		extent_tree_szad_remove(&dss_chunks_szad, prev);
+		extent_tree_ad_remove(&dss_chunks_ad, prev);
 
-		RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad, node);
+		extent_tree_szad_remove(&dss_chunks_szad, node);
 		node->addr = prev->addr;
 		node->size += prev->size;
-		RB_INSERT(extent_tree_szad_s, &dss_chunks_szad, node);
+		extent_tree_szad_insert(&dss_chunks_szad, node);
 
 		base_node_dealloc(prev);
 	}
@@ -1803,10 +1825,8 @@ chunk_dealloc_dss(void *chunk, size_t size)
 			dss_max = (void *)((intptr_t)dss_prev - (intptr_t)size);
 
 			if (node != NULL) {
-				RB_REMOVE(extent_tree_szad_s, &dss_chunks_szad,
-				    node);
-				RB_REMOVE(extent_tree_ad_s, &dss_chunks_ad,
-				    node);
+				extent_tree_szad_remove(&dss_chunks_szad, node);
+				extent_tree_ad_remove(&dss_chunks_ad, node);
 				base_node_dealloc(node);
 			}
 			malloc_mutex_unlock(&dss_mtx);
@@ -1991,8 +2011,20 @@ arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
 	return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
 }
 
-/* Generate red-black tree code for arena chunks. */
-RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp)
+/* Wrap large red-black tree macros in functions. */
+static void
+arena_chunk_tree_insert(arena_chunk_tree_t *tree, arena_chunk_t *chunk)
+{
+
+	rb_insert(arena_chunk_t, link, arena_chunk_comp, tree, chunk);
+}
+
+static void
+arena_chunk_tree_remove(arena_chunk_tree_t *tree, arena_chunk_t *chunk)
+{
+
+	rb_remove(arena_chunk_t, link, arena_chunk_comp, tree, chunk);
+}
 
 static inline int
 arena_run_comp(arena_run_t *a, arena_run_t *b)
@@ -2006,17 +2038,29 @@ arena_run_comp(arena_run_t *a, arena_run_t *b)
 	return ((a_run > b_run) - (a_run < b_run));
 }
 
-/* Generate red-black tree code for arena runs. */
-RB_GENERATE_STATIC(arena_run_tree_s, arena_run_s, link, arena_run_comp)
+/* Wrap large red-black tree macros in functions. */
+static void
+arena_run_tree_insert(arena_run_tree_t *tree, arena_run_t *run)
+{
+
+	rb_insert(arena_run_t, link, arena_run_comp, tree, run);
+}
+
+static void
+arena_run_tree_remove(arena_run_tree_t *tree, arena_run_t *run)
+{
+
+	rb_remove(arena_run_t, link, arena_run_comp, tree, run);
+}
 
 static extent_node_t *
 arena_chunk_node_alloc(arena_chunk_t *chunk)
 {
 	extent_node_t *ret;
 
-	ret = RB_MIN(extent_tree_ad_s, &chunk->nodes);
+	rb_first(extent_node_t, link_ad, &chunk->nodes, ret);
 	if (ret != NULL)
-		RB_REMOVE(extent_tree_ad_s, &chunk->nodes, ret);
+		extent_tree_ad_remove(&chunk->nodes, ret);
 	else {
 		ret = chunk->nodes_past;
 		chunk->nodes_past = (extent_node_t *)
@@ -2034,7 +2078,7 @@ arena_chunk_node_dealloc(arena_chunk_t *chunk, extent_node_t *node)
 {
 
 	node->addr = (void *)node;
-	RB_INSERT(extent_tree_ad_s, &chunk->nodes, node);
+	extent_tree_ad_insert(&chunk->nodes, node);
 }
 
 static inline void *
@@ -2213,10 +2257,11 @@ arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small,
 	nodeA = arena_chunk_node_alloc(chunk);
 	nodeA->addr = run;
 	nodeA->size = size;
-	RB_INSERT(extent_tree_ad_s, &arena->runs_alloced_ad, nodeA);
+	extent_tree_ad_insert(&arena->runs_alloced_ad, nodeA);
 
 	key.addr = run;
-	nodeB = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	rb_search(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad,
+	    &key, nodeB);
 	assert(nodeB != NULL);
 
 	run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
@@ -2253,7 +2298,7 @@ arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small,
 	}
 
 	/* Keep track of trailing unused pages for later use. */
-	RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+	extent_tree_szad_remove(&arena->runs_avail_szad, nodeB);
 	if (rem_pages > 0) {
 		/*
 		 * Update nodeB in runs_avail_*.  Its position within
@@ -2261,10 +2306,10 @@ arena_run_split(arena_t *arena, arena_run_t *run, size_t size, bool small,
 		 */
 		nodeB->addr = (void *)((uintptr_t)nodeB->addr + size);
 		nodeB->size -= size;
-		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+		extent_tree_szad_insert(&arena->runs_avail_szad, nodeB);
 	} else {
 		/* Remove nodeB from runs_avail_*. */
-		RB_REMOVE(extent_tree_ad_s, &arena->runs_avail_ad, nodeB);
+		extent_tree_ad_remove(&arena->runs_avail_ad, nodeB);
 		arena_chunk_node_dealloc(chunk, nodeB);
 	}
 
@@ -2290,7 +2335,7 @@ arena_chunk_alloc(arena_t *arena)
 
 		chunk->arena = arena;
 
-		RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
+		arena_chunk_tree_insert(&arena->chunks, chunk);
 
 		/*
 		 * Claim that no pages are in use, since the header is merely
@@ -2310,7 +2355,7 @@ arena_chunk_alloc(arena_t *arena)
 		    arena_chunk_header_npages));
 
 		/* Initialize the tree of unused extent nodes. */
-		RB_INIT(&chunk->nodes);
+		rb_tree_new(extent_node_t, link_ad, &chunk->nodes);
 		chunk->nodes_past = (extent_node_t *)QUANTUM_CEILING(
 		    (uintptr_t)&chunk->map[chunk_npages]);
 	}
@@ -2320,8 +2365,8 @@ arena_chunk_alloc(arena_t *arena)
 	node->addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages <<
 	    pagesize_2pow));
 	node->size = chunksize - (arena_chunk_header_npages << pagesize_2pow);
-	RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, node);
-	RB_INSERT(extent_tree_ad_s, &arena->runs_avail_ad, node);
+	extent_tree_szad_insert(&arena->runs_avail_szad, node);
+	extent_tree_ad_insert(&arena->runs_avail_ad, node);
 
 	return (chunk);
 }
@@ -2332,8 +2377,7 @@ arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
 	extent_node_t *node, key;
 
 	if (arena->spare != NULL) {
-		RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks,
-		    arena->spare);
+		arena_chunk_tree_remove(&chunk->arena->chunks, arena->spare);
 		arena->ndirty -= arena->spare->ndirty;
 		chunk_dealloc((void *)arena->spare, chunksize);
 #ifdef MALLOC_STATS
@@ -2349,10 +2393,11 @@ arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
 	 */
 	key.addr = (void *)((uintptr_t)chunk + (arena_chunk_header_npages <<
 	    pagesize_2pow));
-	node = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	rb_search(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad,
+	    &key, node);
 	assert(node != NULL);
-	RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, node);
-	RB_REMOVE(extent_tree_ad_s, &arena->runs_avail_ad, node);
+	extent_tree_szad_remove(&arena->runs_avail_szad, node);
+	extent_tree_ad_remove(&arena->runs_avail_ad, node);
 	arena_chunk_node_dealloc(chunk, node);
 
 	arena->spare = chunk;
@@ -2372,7 +2417,8 @@ arena_run_alloc(arena_t *arena, size_t size, bool small, bool zero)
 	/* Search the arena's chunks for the lowest best fit. */
 	key.addr = NULL;
 	key.size = size;
-	node = RB_NFIND(extent_tree_szad_s, &arena->runs_avail_szad, &key);
+	rb_nsearch(extent_node_t, link_szad, extent_szad_comp,
+	    &arena->runs_avail_szad, &key, node);
 	if (node != NULL) {
 		run = (arena_run_t *)node->addr;
 		arena_run_split(arena, run, size, small, zero);
@@ -2400,9 +2446,9 @@ arena_purge(arena_t *arena)
 	size_t ndirty;
 
 	ndirty = 0;
-	RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
+	rb_foreach_begin(arena_chunk_t, link, &arena->chunks, chunk) {
 		ndirty += chunk->ndirty;
-	}
+	} rb_foreach_end(arena_chunk_t, link, &arena->chunks, chunk)
 	assert(ndirty == arena->ndirty);
 #endif
 	assert(arena->ndirty > opt_dirty_max);
@@ -2415,7 +2461,7 @@ arena_purge(arena_t *arena)
 	 * Iterate downward through chunks until enough dirty memory has been
 	 * purged.
 	 */
-	RB_FOREACH_REVERSE(chunk, arena_chunk_tree_s, &arena->chunks) {
+	rb_foreach_reverse_begin(arena_chunk_t, link, &arena->chunks, chunk) {
 		if (chunk->ndirty > 0) {
 			size_t i;
 
@@ -2453,7 +2499,7 @@ arena_purge(arena_t *arena)
 				}
 			}
 		}
-	}
+	} rb_foreach_reverse_end(arena_chunk_t, link, &arena->chunks, chunk)
 }
 
 static void
@@ -2465,9 +2511,10 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
 
 	/* Remove run from runs_alloced_ad. */
 	key.addr = run;
-	nodeB = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+	rb_search(extent_node_t, link_ad, extent_ad_comp,
+	    &arena->runs_alloced_ad, &key, nodeB);
 	assert(nodeB != NULL);
-	RB_REMOVE(extent_tree_ad_s, &arena->runs_alloced_ad, nodeB);
+	extent_tree_ad_remove(&arena->runs_alloced_ad, nodeB);
 	size = nodeB->size;
 
 	chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
@@ -2505,29 +2552,31 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
 
 	/* Try to coalesce forward. */
 	key.addr = (void *)((uintptr_t)run + size);
-	nodeC = RB_NFIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	rb_nsearch(extent_node_t, link_ad, extent_ad_comp,
+	    &arena->runs_avail_ad, &key, nodeC);
 	if (nodeC != NULL && nodeC->addr == key.addr) {
 		/*
 		 * Coalesce forward.  This does not change the position within
 		 * runs_avail_ad, so only remove/insert from/into
 		 * runs_avail_szad.
 		 */
-		RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeC);
+		extent_tree_szad_remove(&arena->runs_avail_szad, nodeC);
 		nodeC->addr = (void *)run;
 		nodeC->size += size;
-		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeC);
+		extent_tree_szad_insert(&arena->runs_avail_szad, nodeC);
 		arena_chunk_node_dealloc(chunk, nodeB);
 		nodeB = nodeC;
 	} else {
 		/*
 		 * Coalescing forward failed, so insert nodeB into runs_avail_*.
 		 */
-		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
-		RB_INSERT(extent_tree_ad_s, &arena->runs_avail_ad, nodeB);
+		extent_tree_szad_insert(&arena->runs_avail_szad, nodeB);
+		extent_tree_ad_insert(&arena->runs_avail_ad, nodeB);
 	}
 
 	/* Try to coalesce backward. */
-	nodeA = RB_PREV(extent_tree_ad_s, &arena->runs_avail_ad, nodeB);
+	rb_prev(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad,
+	    nodeB, nodeA);
 	if (nodeA != NULL && (void *)((uintptr_t)nodeA->addr + nodeA->size) ==
 	    (void *)run) {
 		/*
@@ -2535,13 +2584,13 @@ arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
 		 * position within runs_avail_ad, so only remove/insert
 		 * from/into runs_avail_szad.
 		 */
-		RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeA);
-		RB_REMOVE(extent_tree_ad_s, &arena->runs_avail_ad, nodeA);
+		extent_tree_szad_remove(&arena->runs_avail_szad, nodeA);
+		extent_tree_ad_remove(&arena->runs_avail_ad, nodeA);
 
-		RB_REMOVE(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+		extent_tree_szad_remove(&arena->runs_avail_szad, nodeB);
 		nodeB->addr = nodeA->addr;
 		nodeB->size += nodeA->size;
-		RB_INSERT(extent_tree_szad_s, &arena->runs_avail_szad, nodeB);
+		extent_tree_szad_insert(&arena->runs_avail_szad, nodeB);
 
 		arena_chunk_node_dealloc(chunk, nodeA);
 	}
@@ -2579,7 +2628,7 @@ arena_run_trim_head(arena_t *arena, arena_chunk_t *chunk, extent_node_t *nodeB,
 	nodeA = arena_chunk_node_alloc(chunk);
 	nodeA->addr = (void *)run;
 	nodeA->size = oldsize - newsize;
-	RB_INSERT(extent_tree_ad_s, &arena->runs_alloced_ad, nodeA);
+	extent_tree_ad_insert(&arena->runs_alloced_ad, nodeA);
 
 	arena_run_dalloc(arena, (arena_run_t *)run, false);
 }
@@ -2607,7 +2656,7 @@ arena_run_trim_tail(arena_t *arena, arena_chunk_t *chunk, extent_node_t *nodeA,
 	nodeB = arena_chunk_node_alloc(chunk);
 	nodeB->addr = (void *)((uintptr_t)run + newsize);
 	nodeB->size = oldsize - newsize;
-	RB_INSERT(extent_tree_ad_s, &arena->runs_alloced_ad, nodeB);
+	extent_tree_ad_insert(&arena->runs_alloced_ad, nodeB);
 
 	arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)run + newsize),
 	    dirty);
@@ -2620,9 +2669,10 @@ arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
 	unsigned i, remainder;
 
 	/* Look for a usable run. */
-	if ((run = RB_MIN(arena_run_tree_s, &bin->runs)) != NULL) {
+	rb_first(arena_run_t, link, &bin->runs, run);
+	if (run != NULL) {
 		/* run is guaranteed to have available space. */
-		RB_REMOVE(arena_run_tree_s, &bin->runs, run);
+		arena_run_tree_remove(&bin->runs, run);
 #ifdef MALLOC_STATS
 		bin->stats.reruns++;
 #endif
@@ -2991,7 +3041,8 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
 		 * does not change.
 		 */
 		key.addr = ret;
-		node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp,
+		    &arena->runs_alloced_ad, &key, node);
 		assert(node != NULL);
 
 		arena_run_trim_tail(arena, chunk, node, ret, alloc_size, size,
@@ -3004,7 +3055,8 @@ arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
 		 * does not change.
 		 */
 		key.addr = ret;
-		node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp,
+		    &arena->runs_alloced_ad, &key, node);
 		assert(node != NULL);
 
 		leadsize = alignment - offset;
@@ -3164,7 +3216,8 @@ arena_salloc(const void *ptr)
 		arena = chunk->arena;
 		malloc_spin_lock(&arena->lock);
 		key.addr = (void *)ptr;
-		node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp,
+		    &arena->runs_alloced_ad, &key, node);
 		assert(node != NULL);
 		ret = node->size;
 		malloc_spin_unlock(&arena->lock);
@@ -3196,7 +3249,8 @@ isalloc(const void *ptr)
 
 		/* Extract from tree of huge allocations. */
 		key.addr = __DECONST(void *, ptr);
-		node = RB_FIND(extent_tree_ad_s, &huge, &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp, &huge, &key,
+		    node);
 		assert(node != NULL);
 
 		ret = node->size;
@@ -3238,7 +3292,7 @@ arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 			 * run only contains one region, then it never gets
 			 * inserted into the non-full runs tree.
 			 */
-			RB_REMOVE(arena_run_tree_s, &bin->runs, run);
+			arena_run_tree_remove(&bin->runs, run);
 		}
 #ifdef MALLOC_DEBUG
 		run->magic = 0;
@@ -3258,12 +3312,11 @@ arena_dalloc_small(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 			/* Switch runcur. */
 			if (bin->runcur->nfree > 0) {
 				/* Insert runcur. */
-				RB_INSERT(arena_run_tree_s, &bin->runs,
-				    bin->runcur);
+				arena_run_tree_insert(&bin->runs, bin->runcur);
 			}
 			bin->runcur = run;
 		} else
-			RB_INSERT(arena_run_tree_s, &bin->runs, run);
+			arena_run_tree_insert(&bin->runs, run);
 	}
 #ifdef MALLOC_STATS
 	arena->stats.allocated_small -= size;
@@ -3285,8 +3338,8 @@ arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr)
 		size_t size;
 
 		key.addr = ptr;
-		node = RB_FIND(extent_tree_ad_s,
-		    &arena->runs_alloced_ad, &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp,
+		    &arena->runs_alloced_ad, &key, node);
 		assert(node != NULL);
 		size = node->size;
 #ifdef MALLOC_STATS
@@ -3362,7 +3415,8 @@ arena_ralloc_large_shrink(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 #else
 	malloc_spin_lock(&arena->lock);
 #endif
-	node = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad, &key);
+	rb_search(extent_node_t, link_ad, extent_ad_comp,
+	    &arena->runs_alloced_ad, &key, node);
 	assert(node != NULL);
 	arena_run_trim_tail(arena, chunk, node, (arena_run_t *)ptr, oldsize,
 	    size, true);
@@ -3386,7 +3440,8 @@ arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 #else
 	malloc_spin_lock(&arena->lock);
 #endif
-	nodeC = RB_FIND(extent_tree_ad_s, &arena->runs_avail_ad, &key);
+	rb_search(extent_node_t, link_ad, extent_ad_comp, &arena->runs_avail_ad,
+	    &key, nodeC);
 	if (nodeC != NULL && oldsize + nodeC->size >= size) {
 		extent_node_t *nodeA, *nodeB;
 
@@ -3401,18 +3456,18 @@ arena_ralloc_large_grow(arena_t *arena, arena_chunk_t *chunk, void *ptr,
 		    oldsize, false, false);
 
 		key.addr = ptr;
-		nodeA = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad,
-		    &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp,
+		    &arena->runs_alloced_ad, &key, nodeA);
 		assert(nodeA != NULL);
 
 		key.addr = (void *)((uintptr_t)ptr + oldsize);
-		nodeB = RB_FIND(extent_tree_ad_s, &arena->runs_alloced_ad,
-		    &key);
+		rb_search(extent_node_t, link_ad, extent_ad_comp,
+		    &arena->runs_alloced_ad, &key, nodeB);
 		assert(nodeB != NULL);
 
 		nodeA->size += nodeB->size;
 
-		RB_REMOVE(extent_tree_ad_s, &arena->runs_alloced_ad, nodeB);
+		extent_tree_ad_remove(&arena->runs_alloced_ad, nodeB);
 		arena_chunk_node_dealloc(chunk, nodeB);
 
 #ifdef MALLOC_STATS
@@ -3552,14 +3607,14 @@ arena_new(arena_t *arena)
 #endif
 
 	/* Initialize chunks. */
-	RB_INIT(&arena->chunks);
+	rb_tree_new(arena_chunk_t, link, &arena->chunks);
 	arena->spare = NULL;
 
 	arena->ndirty = 0;
 
-	RB_INIT(&arena->runs_avail_szad);
-	RB_INIT(&arena->runs_avail_ad);
-	RB_INIT(&arena->runs_alloced_ad);
+	rb_tree_new(extent_node_t, link_szad, &arena->runs_avail_szad);
+	rb_tree_new(extent_node_t, link_ad, &arena->runs_avail_ad);
+	rb_tree_new(extent_node_t, link_ad, &arena->runs_alloced_ad);
 
 #ifdef MALLOC_BALANCE
 	arena->contention = 0;
@@ -3572,7 +3627,7 @@ arena_new(arena_t *arena)
 	for (i = 0; i < ntbins; i++) {
 		bin = &arena->bins[i];
 		bin->runcur = NULL;
-		RB_INIT(&bin->runs);
+		rb_tree_new(arena_run_t, link, &bin->runs);
 
 		bin->reg_size = (1U << (TINY_MIN_2POW + i));
 
@@ -3587,7 +3642,7 @@ arena_new(arena_t *arena)
 	for (; i < ntbins + nqbins; i++) {
 		bin = &arena->bins[i];
 		bin->runcur = NULL;
-		RB_INIT(&bin->runs);
+		rb_tree_new(arena_run_t, link, &bin->runs);
 
 		bin->reg_size = quantum * (i - ntbins + 1);
 
@@ -3603,7 +3658,7 @@ arena_new(arena_t *arena)
 	for (; i < ntbins + nqbins + nsbins; i++) {
 		bin = &arena->bins[i];
 		bin->runcur = NULL;
-		RB_INIT(&bin->runs);
+		rb_tree_new(arena_run_t, link, &bin->runs);
 
 		bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1));
 
@@ -3689,7 +3744,7 @@ huge_malloc(size_t size, bool zero)
 	node->size = csize;
 
 	malloc_mutex_lock(&huge_mtx);
-	RB_INSERT(extent_tree_ad_s, &huge, node);
+	extent_tree_ad_insert(&huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += csize;
@@ -3771,7 +3826,7 @@ huge_palloc(size_t alignment, size_t size)
 	node->size = chunk_size;
 
 	malloc_mutex_lock(&huge_mtx);
-	RB_INSERT(extent_tree_ad_s, &huge, node);
+	extent_tree_ad_insert(&huge, node);
 #ifdef MALLOC_STATS
 	huge_nmalloc++;
 	huge_allocated += chunk_size;
@@ -3829,10 +3884,10 @@ huge_dalloc(void *ptr)
 
 	/* Extract from tree of huge allocations. */
 	key.addr = ptr;
-	node = RB_FIND(extent_tree_ad_s, &huge, &key);
+	rb_search(extent_node_t, link_ad, extent_ad_comp, &huge, &key, node);
 	assert(node != NULL);
 	assert(node->addr == ptr);
-	RB_REMOVE(extent_tree_ad_s, &huge, node);
+	extent_tree_ad_remove(&huge, node);
 
 #ifdef MALLOC_STATS
 	huge_ndalloc++;
@@ -4329,14 +4384,14 @@ MALLOC_OUT:
 
 	/* Initialize chunks data. */
 	malloc_mutex_init(&huge_mtx);
-	RB_INIT(&huge);
+	rb_tree_new(extent_node_t, link_ad, &huge);
 #ifdef MALLOC_DSS
 	malloc_mutex_init(&dss_mtx);
 	dss_base = sbrk(0);
 	dss_prev = dss_base;
 	dss_max = dss_base;
-	RB_INIT(&dss_chunks_szad);
-	RB_INIT(&dss_chunks_ad);
+	rb_tree_new(extent_node_t, link_szad, &dss_chunks_szad);
+	rb_tree_new(extent_node_t, link_ad, &dss_chunks_ad);
 #endif
 #ifdef MALLOC_STATS
 	huge_nmalloc = 0;
diff --git a/lib/libc/stdlib/rb.h b/lib/libc/stdlib/rb.h
new file mode 100644
index 0000000..7978534
--- /dev/null
+++ b/lib/libc/stdlib/rb.h
@@ -0,0 +1,776 @@
+/******************************************************************************
+ *
+ * Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice(s), this list of conditions and the following disclaimer
+ *    unmodified other than the allowable addition of one or more
+ *    copyright notices.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice(s), this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+ * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ ******************************************************************************
+ *
+ * cpp macro implementation of left-leaning red-black trees.  All operations
+ * are done non-recursively.  Parent pointers are not used, and color bits are
+ * stored in the least significant bit of right-child pointers, thus making
+ * node linkage as compact as is possible for red-black trees.
+ *
+ * Some macros use a comparison function pointer, which is expected to have the
+ * following prototype:
+ *
+ *   int (a_cmp *)(a_type *a_node, a_type *a_other);
+ *                         ^^^^^^
+ *                      or a_key
+ *
+ * Interpretation of comparision function return values:
+ *
+ *   -1 : a_node <  a_other
+ *    0 : a_node == a_other
+ *    1 : a_node >  a_other
+ *
+ * In all cases, the a_node or a_key macro argument is the first argument to the
+ * comparison function, which makes it possible to write comparison functions
+ * that treat the first argument specially.
+ *
+ ******************************************************************************/
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+/* To disable assertions, #define NDEBUG before #include'ing rb.h. */
+#include <assert.h>
+
+/* Node structure. */
+#define rb_node(a_type)							\
+struct {								\
+    a_type *rbn_left;							\
+    a_type *rbn_right_red;						\
+}
+
+/* Root structure. */
+#define rb_tree(a_type)							\
+struct {								\
+    a_type *rbt_root;							\
+    a_type rbt_nil;							\
+}
+
+/* Left accessors. */
+#define rbp_left_get(a_type, a_field, a_node)				\
+    ((a_node)->a_field.rbn_left)
+#define rbp_left_set(a_type, a_field, a_node, a_left) do {		\
+    (a_node)->a_field.rbn_left = a_left;				\
+} while (0)
+
+/* Right accessors. */
+#define rbp_right_get(a_type, a_field, a_node)				\
+    ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)		\
+      & ((ssize_t)-2)))
+#define rbp_right_set(a_type, a_field, a_node, a_right) do {		\
+    (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right)	\
+      | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1)));	\
+} while (0)
+
+/* Color accessors. */
+#define rbp_red_get(a_type, a_field, a_node)				\
+    ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)		\
+      & ((size_t)1)))
+#define rbp_color_set(a_type, a_field, a_node, a_red) do {		\
+    (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)		\
+      (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))			\
+      | ((ssize_t)a_red));						\
+} while (0)
+#define rbp_red_set(a_type, a_field, a_node) do {			\
+    (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)		\
+      (a_node)->a_field.rbn_right_red) | ((size_t)1));			\
+} while (0)
+#define rbp_black_set(a_type, a_field, a_node) do {			\
+    (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)		\
+      (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));		\
+} while (0)
+
+/* Node initializer. */
+#define rbp_node_new(a_type, a_field, a_tree, a_node) do {		\
+    rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);	\
+    rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);	\
+    rbp_red_set(a_type, a_field, (a_node));				\
+} while (0)
+
+/* Tree initializer. */
+#define rb_tree_new(a_type, a_field, a_tree) do {			\
+    (a_tree)->rbt_root = &(a_tree)->rbt_nil;				\
+    rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);		\
+    rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);			\
+} while (0)
+
+/* Tree operations. */
+#define rbp_black_height(a_type, a_field, a_tree, r_height) do {	\
+    a_type *rbp_bh_t;							\
+    for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;			\
+      rbp_bh_t != &(a_tree)->rbt_nil;					\
+      rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {		\
+	if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {		\
+	    (r_height)++;						\
+	}								\
+    }									\
+} while (0)
+
+#define rbp_first(a_type, a_field, a_tree, a_root, r_node) do {		\
+    for ((r_node) = (a_root);						\
+      rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;	\
+      (r_node) = rbp_left_get(a_type, a_field, (r_node))) {		\
+    }									\
+} while (0)
+
+#define rbp_last(a_type, a_field, a_tree, a_root, r_node) do {		\
+    for ((r_node) = (a_root);						\
+      rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;	\
+      (r_node) = rbp_right_get(a_type, a_field, (r_node))) {		\
+    }									\
+} while (0)
+
+#define rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {	\
+    if (rbp_right_get(a_type, a_field, (a_node))			\
+      != &(a_tree)->rbt_nil) {						\
+	rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type,	\
+	  a_field, (a_node)), (r_node));				\
+    } else {								\
+	a_type *rbp_n_t = (a_tree)->rbt_root;				\
+	assert(rbp_n_t != &(a_tree)->rbt_nil);				\
+	(r_node) = &(a_tree)->rbt_nil;					\
+	while (true) {							\
+	    int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t);			\
+	    if (rbp_n_cmp < 0) {					\
+		(r_node) = rbp_n_t;					\
+		rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t);	\
+	    } else if (rbp_n_cmp > 0) {					\
+		rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t);	\
+	    } else {							\
+		break;							\
+	    }								\
+	    assert(rbp_n_t != &(a_tree)->rbt_nil);			\
+	}								\
+    }									\
+} while (0)
+
+#define rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {	\
+    if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\
+	rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type,		\
+	  a_field, (a_node)), (r_node));				\
+    } else {								\
+	a_type *rbp_p_t = (a_tree)->rbt_root;				\
+	assert(rbp_p_t != &(a_tree)->rbt_nil);				\
+	(r_node) = &(a_tree)->rbt_nil;					\
+	while (true) {							\
+	    int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t);			\
+	    if (rbp_p_cmp < 0) {					\
+		rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t);	\
+	    } else if (rbp_p_cmp > 0) {					\
+		(r_node) = rbp_p_t;					\
+		rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t);	\
+	    } else {							\
+		break;							\
+	    }								\
+	    assert(rbp_p_t != &(a_tree)->rbt_nil);			\
+	}								\
+    }									\
+} while (0)
+
+#define rb_first(a_type, a_field, a_tree, r_node) do {			\
+    rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node));	\
+    if ((r_node) == &(a_tree)->rbt_nil) {				\
+	(r_node) = NULL;						\
+    }									\
+} while (0)
+
+#define rb_last(a_type, a_field, a_tree, r_node) do {			\
+    rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node);	\
+    if ((r_node) == &(a_tree)->rbt_nil) {				\
+	(r_node) = NULL;						\
+    }									\
+} while (0)
+
+#define rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {	\
+    rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));	\
+    if ((r_node) == &(a_tree)->rbt_nil) {				\
+	(r_node) = NULL;						\
+    }									\
+} while (0)
+
+#define rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {	\
+    rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));	\
+    if ((r_node) == &(a_tree)->rbt_nil) {				\
+	(r_node) = NULL;						\
+    }									\
+} while (0)
+
+#define rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {	\
+    int rbp_se_cmp;							\
+    (r_node) = (a_tree)->rbt_root;					\
+    while ((r_node) != &(a_tree)->rbt_nil				\
+      && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) {		\
+	if (rbp_se_cmp < 0) {						\
+	    (r_node) = rbp_left_get(a_type, a_field, (r_node));		\
+	} else {							\
+	    (r_node) = rbp_right_get(a_type, a_field, (r_node));	\
+	}								\
+    }									\
+    if ((r_node) == &(a_tree)->rbt_nil) {				\
+	(r_node) = NULL;						\
+    }									\
+} while (0)
+
+/*
+ * Find a match if it exists.  Otherwise, find the next greater node, if one
+ * exists.
+ */
+#define rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {	\
+    a_type *rbp_ns_t = (a_tree)->rbt_root;				\
+    (r_node) = NULL;							\
+    while (rbp_ns_t != &(a_tree)->rbt_nil) {				\
+	int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t);			\
+	if (rbp_ns_cmp < 0) {						\
+	    (r_node) = rbp_ns_t;					\
+	    rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t);		\
+	} else if (rbp_ns_cmp > 0) {					\
+	    rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t);	\
+	} else {							\
+	    (r_node) = rbp_ns_t;					\
+	    break;							\
+	}								\
+    }									\
+} while (0)
+
+/*
+ * Find a match if it exists.  Otherwise, find the previous lesser node, if one
+ * exists.
+ */
+#define rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {	\
+    a_type *rbp_ps_t = (a_tree)->rbt_root;				\
+    (r_node) = NULL;							\
+    while (rbp_ps_t != &(a_tree)->rbt_nil) {				\
+	int rbp_ps_cmp = (a_cmp)((a_key), rbp_ps_t);			\
+	if (rbp_ps_cmp < 0) {						\
+	    rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t);		\
+	} else if (rbp_ps_cmp > 0) {					\
+	    (r_node) = rbp_ps_t;					\
+	    rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t);	\
+	} else {							\
+	    (r_node) = rbp_ps_t;					\
+	    break;							\
+	}								\
+    }									\
+} while (0)
+
+#define rbp_rotate_left(a_type, a_field, a_node, r_node) do {		\
+    (r_node) = rbp_right_get(a_type, a_field, (a_node));		\
+    rbp_right_set(a_type, a_field, (a_node),				\
+      rbp_left_get(a_type, a_field, (r_node)));				\
+    rbp_left_set(a_type, a_field, (r_node), (a_node));			\
+} while (0)
+
+#define rbp_rotate_right(a_type, a_field, a_node, r_node) do {		\
+    (r_node) = rbp_left_get(a_type, a_field, (a_node));			\
+    rbp_left_set(a_type, a_field, (a_node),				\
+      rbp_right_get(a_type, a_field, (r_node)));			\
+    rbp_right_set(a_type, a_field, (r_node), (a_node));			\
+} while (0)
+
+#define rbp_lean_left(a_type, a_field, a_node, r_node) do {		\
+    bool rbp_ll_red;							\
+    rbp_rotate_left(a_type, a_field, (a_node), (r_node));		\
+    rbp_ll_red = rbp_red_get(a_type, a_field, (a_node));		\
+    rbp_color_set(a_type, a_field, (r_node), rbp_ll_red);		\
+    rbp_red_set(a_type, a_field, (a_node));				\
+} while (0)
+
+#define rbp_lean_right(a_type, a_field, a_node, r_node) do {		\
+    bool rbp_lr_red;							\
+    rbp_rotate_right(a_type, a_field, (a_node), (r_node));		\
+    rbp_lr_red = rbp_red_get(a_type, a_field, (a_node));		\
+    rbp_color_set(a_type, a_field, (r_node), rbp_lr_red);		\
+    rbp_red_set(a_type, a_field, (a_node));				\
+} while (0)
+
+#define rbp_move_red_left(a_type, a_field, a_node, r_node) do {		\
+    a_type *rbp_mrl_t, *rbp_mrl_u;					\
+    rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node));		\
+    rbp_red_set(a_type, a_field, rbp_mrl_t);				\
+    rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));		\
+    rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t);		\
+    if (rbp_red_get(a_type, a_field, rbp_mrl_u)) {			\
+	rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u);	\
+	rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u);		\
+	rbp_rotate_left(a_type, a_field, (a_node), (r_node));		\
+	rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));		\
+	if (rbp_red_get(a_type, a_field, rbp_mrl_t)) {			\
+	    rbp_black_set(a_type, a_field, rbp_mrl_t);			\
+	    rbp_red_set(a_type, a_field, (a_node));			\
+	    rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t);	\
+	    rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t);		\
+	} else {							\
+	    rbp_black_set(a_type, a_field, (a_node));			\
+	}								\
+    } else {								\
+	rbp_red_set(a_type, a_field, (a_node));				\
+	rbp_rotate_left(a_type, a_field, (a_node), (r_node));		\
+    }									\
+} while (0)
+
+#define rbp_move_red_right(a_type, a_field, a_node, r_node) do {	\
+    a_type *rbp_mrr_t;							\
+    rbp_mrr_t = rbp_left_get(a_type, a_field, (a_node));		\
+    if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {			\
+	a_type *rbp_mrr_u, *rbp_mrr_v;					\
+	rbp_mrr_u = rbp_right_get(a_type, a_field, rbp_mrr_t);		\
+	rbp_mrr_v = rbp_left_get(a_type, a_field, rbp_mrr_u);		\
+	if (rbp_red_get(a_type, a_field, rbp_mrr_v)) {			\
+	    rbp_color_set(a_type, a_field, rbp_mrr_u,			\
+	      rbp_red_get(a_type, a_field, (a_node)));			\
+	    rbp_black_set(a_type, a_field, rbp_mrr_v);			\
+	    rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u);	\
+	    rbp_left_set(a_type, a_field, (a_node), rbp_mrr_u);		\
+	    rbp_rotate_right(a_type, a_field, (a_node), (r_node));	\
+	    rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);	\
+	    rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);	\
+	} else {							\
+	    rbp_color_set(a_type, a_field, rbp_mrr_t,			\
+	      rbp_red_get(a_type, a_field, (a_node)));			\
+	    rbp_red_set(a_type, a_field, rbp_mrr_u);			\
+	    rbp_rotate_right(a_type, a_field, (a_node), (r_node));	\
+	    rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);	\
+	    rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);	\
+	}								\
+	rbp_red_set(a_type, a_field, (a_node));				\
+    } else {								\
+	rbp_red_set(a_type, a_field, rbp_mrr_t);			\
+	rbp_mrr_t = rbp_left_get(a_type, a_field, rbp_mrr_t);		\
+	if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {			\
+	    rbp_black_set(a_type, a_field, rbp_mrr_t);			\
+	    rbp_rotate_right(a_type, a_field, (a_node), (r_node));	\
+	    rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);	\
+	    rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);	\
+	} else {							\
+	    rbp_rotate_left(a_type, a_field, (a_node), (r_node));	\
+	}								\
+    }									\
+} while (0)
+
+#define rb_insert(a_type, a_field, a_cmp, a_tree, a_node) do {		\
+    a_type rbp_i_s;							\
+    a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u;		\
+    int rbp_i_cmp = 0;							\
+    rbp_i_g = &(a_tree)->rbt_nil;					\
+    rbp_left_set(a_type, a_field, &rbp_i_s, (a_tree)->rbt_root);	\
+    rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil);	\
+    rbp_black_set(a_type, a_field, &rbp_i_s);				\
+    rbp_i_p = &rbp_i_s;							\
+    rbp_i_c = (a_tree)->rbt_root;					\
+    /* Iteratively search down the tree for the insertion point,      */\
+    /* splitting 4-nodes as they are encountered.  At the end of each */\
+    /* iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down    */\
+    /* the tree, assuming a sufficiently deep tree.                   */\
+    while (rbp_i_c != &(a_tree)->rbt_nil) {				\
+	rbp_i_t = rbp_left_get(a_type, a_field, rbp_i_c);		\
+	rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);		\
+	if (rbp_red_get(a_type, a_field, rbp_i_t)			\
+	  && rbp_red_get(a_type, a_field, rbp_i_u)) {			\
+	    /* rbp_i_c is the top of a logical 4-node, so split it.   */\
+	    /* This iteration does not move down the tree, due to the */\
+	    /* disruptiveness of node splitting.                      */\
+	    /*                                                        */\
+	    /* Rotate right.                                          */\
+	    rbp_rotate_right(a_type, a_field, rbp_i_c, rbp_i_t);	\
+	    /* Pass red links up one level.                           */\
+	    rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);		\
+	    rbp_black_set(a_type, a_field, rbp_i_u);			\
+	    if (rbp_left_get(a_type, a_field, rbp_i_p) == rbp_i_c) {	\
+		rbp_left_set(a_type, a_field, rbp_i_p, rbp_i_t);	\
+		rbp_i_c = rbp_i_t;					\
+	    } else {							\
+		/* rbp_i_c was the right child of rbp_i_p, so rotate  */\
+		/* left in order to maintain the left-leaning         */\
+		/* invariant.                                         */\
+		assert(rbp_right_get(a_type, a_field, rbp_i_p)		\
+		  == rbp_i_c);						\
+		rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t);	\
+		rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u);	\
+		if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
+		    rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_u);	\
+		} else {						\
+		    assert(rbp_right_get(a_type, a_field, rbp_i_g)	\
+		      == rbp_i_p);					\
+		    rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u);	\
+		}							\
+		rbp_i_p = rbp_i_u;					\
+		rbp_i_cmp = (a_cmp)((a_node), rbp_i_p);			\
+		if (rbp_i_cmp < 0) {					\
+		    rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_p);	\
+		} else {						\
+		    assert(rbp_i_cmp > 0);				\
+		    rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_p);	\
+		}							\
+		continue;						\
+	    }								\
+	}								\
+	rbp_i_g = rbp_i_p;						\
+	rbp_i_p = rbp_i_c;						\
+	rbp_i_cmp = (a_cmp)((a_node), rbp_i_c);				\
+	if (rbp_i_cmp < 0) {						\
+	    rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_c);		\
+	} else {							\
+	    assert(rbp_i_cmp > 0);					\
+	    rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_c);		\
+	}								\
+    }									\
+    /* rbp_i_p now refers to the node under which to insert.          */\
+    rbp_node_new(a_type, a_field, a_tree, (a_node));			\
+    if (rbp_i_cmp > 0) {						\
+	rbp_right_set(a_type, a_field, rbp_i_p, (a_node));		\
+	rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t);		\
+	if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {	\
+	    rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_t);		\
+	} else if (rbp_right_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
+	    rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t);		\
+	}								\
+    } else {								\
+	rbp_left_set(a_type, a_field, rbp_i_p, (a_node));		\
+    }									\
+    /* Update the root and make sure that it is black.                */\
+    (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_i_s);	\
+    rbp_black_set(a_type, a_field, (a_tree)->rbt_root);			\
+} while (0)
+
+#define rb_remove(a_type, a_field, a_cmp, a_tree, a_node) do {		\
+    a_type rbp_r_s;							\
+    a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u;		\
+    int rbp_r_cmp;							\
+    rbp_left_set(a_type, a_field, &rbp_r_s, (a_tree)->rbt_root);	\
+    rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil);	\
+    rbp_black_set(a_type, a_field, &rbp_r_s);				\
+    rbp_r_p = &rbp_r_s;							\
+    rbp_r_c = (a_tree)->rbt_root;					\
+    rbp_r_xp = &(a_tree)->rbt_nil;					\
+    /* Iterate down the tree, but always transform 2-nodes to 3- or   */\
+    /* 4-nodes in order to maintain the invariant that the current    */\
+    /* node is not a 2-node.  This allows simple deletion once a leaf */\
+    /* is reached.  Handle the root specially though, since there may */\
+    /* be no way to convert it from a 2-node to a 3-node.             */\
+    rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);				\
+    if (rbp_r_cmp < 0) {						\
+	rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);		\
+	rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);		\
+	if (rbp_red_get(a_type, a_field, rbp_r_t) == false		\
+	  && rbp_red_get(a_type, a_field, rbp_r_u) == false) {		\
+	    /* Apply standard transform to prepare for left move.     */\
+	    rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t);	\
+	    rbp_black_set(a_type, a_field, rbp_r_t);			\
+	    rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);		\
+	    rbp_r_c = rbp_r_t;						\
+	} else {							\
+	    /* Move left.                                             */\
+	    rbp_r_p = rbp_r_c;						\
+	    rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);		\
+	}								\
+    } else {								\
+	if (rbp_r_cmp == 0) {						\
+	    assert((a_node) == rbp_r_c);				\
+	    if (rbp_right_get(a_type, a_field, rbp_r_c)			\
+	      == &(a_tree)->rbt_nil) {					\
+		/* Delete root node (which is also a leaf node).      */\
+		if (rbp_left_get(a_type, a_field, rbp_r_c)		\
+		  != &(a_tree)->rbt_nil) {				\
+		    rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t);	\
+		    rbp_right_set(a_type, a_field, rbp_r_t,		\
+		      &(a_tree)->rbt_nil);				\
+		} else {						\
+		    rbp_r_t = &(a_tree)->rbt_nil;			\
+		}							\
+		rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);	\
+	    } else {							\
+		/* This is the node we want to delete, but we will    */\
+		/* instead swap it with its successor and delete the  */\
+		/* successor.  Record enough information to do the    */\
+		/* swap later.  rbp_r_xp is the a_node's parent.      */\
+		rbp_r_xp = rbp_r_p;					\
+		rbp_r_cmp = 1; /* Note that deletion is incomplete.   */\
+	    }								\
+	}								\
+	if (rbp_r_cmp == 1) {						\
+	    if (rbp_red_get(a_type, a_field, rbp_left_get(a_type,	\
+	      a_field, rbp_right_get(a_type, a_field, rbp_r_c)))	\
+	      == false) {						\
+		rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);	\
+		if (rbp_red_get(a_type, a_field, rbp_r_t)) {		\
+		    /* Standard transform.                            */\
+		    rbp_move_red_right(a_type, a_field, rbp_r_c,	\
+		      rbp_r_t);						\
+		} else {						\
+		    /* Root-specific transform.                       */\
+		    rbp_red_set(a_type, a_field, rbp_r_c);		\
+		    rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);	\
+		    if (rbp_red_get(a_type, a_field, rbp_r_u)) {	\
+			rbp_black_set(a_type, a_field, rbp_r_u);	\
+			rbp_rotate_right(a_type, a_field, rbp_r_c,	\
+			  rbp_r_t);					\
+			rbp_rotate_left(a_type, a_field, rbp_r_c,	\
+			  rbp_r_u);					\
+			rbp_right_set(a_type, a_field, rbp_r_t,		\
+			  rbp_r_u);					\
+		    } else {						\
+			rbp_red_set(a_type, a_field, rbp_r_t);		\
+			rbp_rotate_left(a_type, a_field, rbp_r_c,	\
+			  rbp_r_t);					\
+		    }							\
+		}							\
+		rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);	\
+		rbp_r_c = rbp_r_t;					\
+	    } else {							\
+		/* Move right.                                        */\
+		rbp_r_p = rbp_r_c;					\
+		rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);	\
+	    }								\
+	}								\
+    }									\
+    if (rbp_r_cmp != 0) {						\
+	while (true) {							\
+	    assert(rbp_r_p != &(a_tree)->rbt_nil);			\
+	    rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);			\
+	    if (rbp_r_cmp < 0) {					\
+		rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);	\
+		if (rbp_r_t == &(a_tree)->rbt_nil) {			\
+		    /* rbp_r_c now refers to the successor node to    */\
+		    /* relocate, and rbp_r_xp/a_node refer to the     */\
+		    /* context for the relocation.                    */\
+		    if (rbp_left_get(a_type, a_field, rbp_r_xp)		\
+		      == (a_node)) {					\
+			rbp_left_set(a_type, a_field, rbp_r_xp,		\
+			  rbp_r_c);					\
+		    } else {						\
+			assert(rbp_right_get(a_type, a_field,		\
+			  rbp_r_xp) == (a_node));			\
+			rbp_right_set(a_type, a_field, rbp_r_xp,	\
+			  rbp_r_c);					\
+		    }							\
+		    rbp_left_set(a_type, a_field, rbp_r_c,		\
+		      rbp_left_get(a_type, a_field, (a_node)));		\
+		    rbp_right_set(a_type, a_field, rbp_r_c,		\
+		      rbp_right_get(a_type, a_field, (a_node)));	\
+		    rbp_color_set(a_type, a_field, rbp_r_c,		\
+		      rbp_red_get(a_type, a_field, (a_node)));		\
+		    if (rbp_left_get(a_type, a_field, rbp_r_p)		\
+		      == rbp_r_c) {					\
+			rbp_left_set(a_type, a_field, rbp_r_p,		\
+			  &(a_tree)->rbt_nil);				\
+		    } else {						\
+			assert(rbp_right_get(a_type, a_field, rbp_r_p)	\
+			  == rbp_r_c);					\
+			rbp_right_set(a_type, a_field, rbp_r_p,		\
+			  &(a_tree)->rbt_nil);				\
+		    }							\
+		    break;						\
+		}							\
+		rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);	\
+		if (rbp_red_get(a_type, a_field, rbp_r_t) == false	\
+		  && rbp_red_get(a_type, a_field, rbp_r_u) == false) {	\
+		    rbp_move_red_left(a_type, a_field, rbp_r_c,		\
+		      rbp_r_t);						\
+		    if (rbp_left_get(a_type, a_field, rbp_r_p)		\
+		      == rbp_r_c) {					\
+			rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
+		    } else {						\
+			rbp_right_set(a_type, a_field, rbp_r_p,		\
+			  rbp_r_t);					\
+		    }							\
+		    rbp_r_c = rbp_r_t;					\
+		} else {						\
+		    rbp_r_p = rbp_r_c;					\
+		    rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);	\
+		}							\
+	    } else {							\
+		/* Check whether to delete this node (it has to be    */\
+		/* the correct node and a leaf node).                 */\
+		if (rbp_r_cmp == 0) {					\
+		    assert((a_node) == rbp_r_c);			\
+		    if (rbp_right_get(a_type, a_field, rbp_r_c)		\
+		      == &(a_tree)->rbt_nil) {				\
+			/* Delete leaf node.                          */\
+			if (rbp_left_get(a_type, a_field, rbp_r_c)	\
+			  != &(a_tree)->rbt_nil) {			\
+			    rbp_lean_right(a_type, a_field, rbp_r_c,	\
+			      rbp_r_t);					\
+			    rbp_right_set(a_type, a_field, rbp_r_t,	\
+			      &(a_tree)->rbt_nil);			\
+			} else {					\
+			    rbp_r_t = &(a_tree)->rbt_nil;		\
+			}						\
+			if (rbp_left_get(a_type, a_field, rbp_r_p)	\
+			  == rbp_r_c) {					\
+			    rbp_left_set(a_type, a_field, rbp_r_p,	\
+			      rbp_r_t);					\
+			} else {					\
+			    rbp_right_set(a_type, a_field, rbp_r_p,	\
+			      rbp_r_t);					\
+			}						\
+			break;						\
+		    } else {						\
+			/* This is the node we want to delete, but we */\
+			/* will instead swap it with its successor    */\
+			/* and delete the successor.  Record enough   */\
+			/* information to do the swap later.          */\
+			/* rbp_r_xp is a_node's parent.               */\
+			rbp_r_xp = rbp_r_p;				\
+		    }							\
+		}							\
+		rbp_r_t = rbp_right_get(a_type, a_field, rbp_r_c);	\
+		rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);	\
+		if (rbp_red_get(a_type, a_field, rbp_r_u) == false) {	\
+		    rbp_move_red_right(a_type, a_field, rbp_r_c,	\
+		      rbp_r_t);						\
+		    if (rbp_left_get(a_type, a_field, rbp_r_p)		\
+		      == rbp_r_c) {					\
+			rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
+		    } else {						\
+			rbp_right_set(a_type, a_field, rbp_r_p,		\
+			  rbp_r_t);					\
+		    }							\
+		    rbp_r_c = rbp_r_t;					\
+		} else {						\
+		    rbp_r_p = rbp_r_c;					\
+		    rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);	\
+		}							\
+	    }								\
+	}								\
+    }									\
+    /* Update root.                                                   */\
+    (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_r_s);	\
+} while (0)
+
+/*
+ * The iterators simulate recursion via an array of pointers that store the
+ * current path.  This is critical to performance, since a series of calls to
+ * rb_{next,prev}() would require time proportional to (n lg n), whereas this
+ * implementation only requires time proportional to (n).
+ */
+
+#define rb_foreach_begin(a_type, a_field, a_tree, a_var)	{	\
+    /* Compute the maximum possible tree depth (3X the black height). */\
+    unsigned rbp_f_height;						\
+    rbp_black_height(a_type, a_field, a_tree, rbp_f_height);		\
+    rbp_f_height *= 3;							\
+    {									\
+	/* Initialize the path to contain the left spine.             */\
+	a_type *rbp_f_path[rbp_f_height];				\
+	a_type *rbp_f_node;						\
+	unsigned rbp_f_depth = 0;					\
+	if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {			\
+	    rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;		\
+	    rbp_f_depth++;						\
+	    while ((rbp_f_node = rbp_left_get(a_type, a_field,		\
+	      rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {	\
+		rbp_f_path[rbp_f_depth] = rbp_f_node;			\
+		rbp_f_depth++;						\
+	    }								\
+	}								\
+	/* While the path is non-empty, iterate.                      */\
+	while (rbp_f_depth > 0) {					\
+	    (a_var) = rbp_f_path[rbp_f_depth-1];
+
+#define rb_foreach_end(a_type, a_field, a_tree, a_var)			\
+	    /* Find the successor.                                    */\
+	    if ((rbp_f_node = rbp_right_get(a_type, a_field,		\
+	      rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {	\
+	        /* The successor is the left-most node in the right   */\
+		/* subtree.                                           */\
+		rbp_f_path[rbp_f_depth] = rbp_f_node;			\
+		rbp_f_depth++;						\
+		while ((rbp_f_node = rbp_left_get(a_type, a_field,	\
+		  rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {	\
+		    rbp_f_path[rbp_f_depth] = rbp_f_node;		\
+		    rbp_f_depth++;					\
+		}							\
+	    } else {							\
+		/* The successor is above the current node.  Unwind   */\
+		/* until a left-leaning edge is removed from the      */\
+		/* path, or the path is empty.                        */\
+		for (rbp_f_depth--; rbp_f_depth > 0; rbp_f_depth--) {	\
+		    if (rbp_left_get(a_type, a_field,			\
+		      rbp_f_path[rbp_f_depth-1])			\
+		      == rbp_f_path[rbp_f_depth]) {			\
+			break;						\
+		    }							\
+		}							\
+	    }								\
+	}								\
+    }									\
+}
+
+#define rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var) {	\
+    /* Compute the maximum possible tree depth (3X the black height). */\
+    unsigned rbp_fr_height;						\
+    rbp_black_height(a_type, a_field, a_tree, rbp_fr_height);		\
+    rbp_fr_height *= 3;							\
+    {									\
+	/* Initialize the path to contain the right spine.            */\
+	a_type *rbp_fr_path[rbp_fr_height];				\
+	a_type *rbp_fr_node;						\
+	unsigned rbp_fr_depth = 0;					\
+	if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {			\
+	    rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;		\
+	    rbp_fr_depth++;						\
+	    while ((rbp_fr_node = rbp_right_get(a_type, a_field,	\
+	      rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {	\
+		rbp_fr_path[rbp_fr_depth] = rbp_fr_node;		\
+		rbp_fr_depth++;						\
+	    }								\
+	}								\
+	/* While the path is non-empty, iterate.                      */\
+	while (rbp_fr_depth > 0) {					\
+	    (a_var) = rbp_fr_path[rbp_fr_depth-1];
+
+#define rb_foreach_reverse_end(a_type, a_field, a_tree, a_var)		\
+	    /* Find the predecessor.                                  */\
+	    if ((rbp_fr_node = rbp_left_get(a_type, a_field,		\
+	      rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {	\
+	        /* The predecessor is the right-most node in the left */\
+		/* subtree.                                           */\
+		rbp_fr_path[rbp_fr_depth] = rbp_fr_node;		\
+		rbp_fr_depth++;						\
+		while ((rbp_fr_node = rbp_right_get(a_type, a_field,	\
+		  rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {\
+		    rbp_fr_path[rbp_fr_depth] = rbp_fr_node;		\
+		    rbp_fr_depth++;					\
+		}							\
+	    } else {							\
+		/* The predecessor is above the current node.  Unwind */\
+		/* until a right-leaning edge is removed from the     */\
+		/* path, or the path is empty.                        */\
+		for (rbp_fr_depth--; rbp_fr_depth > 0; rbp_fr_depth--) {\
+		    if (rbp_right_get(a_type, a_field,			\
+		      rbp_fr_path[rbp_fr_depth-1])			\
+		      == rbp_fr_path[rbp_fr_depth]) {			\
+			break;						\
+		    }							\
+		}							\
+	    }								\
+	}								\
+    }									\
+}