--- a/CMakeLists.txt	Wed Jul 25 12:16:02 2018 -0400
+++ b/CMakeLists.txt	Wed Jul 25 14:19:27 2018 -0400
@@ -102,6 +102,7 @@
 	padding.c
 	qstring.c
 	rand.c
+	rbtree.c
 	scgisvc.c
 	sexpr.c
 	sexpr_dump.c
@@ -156,6 +157,7 @@
 		include/jeffpc/padding.h
 		include/jeffpc/qstring.h
 		include/jeffpc/rand.h
+		include/jeffpc/rbtree.h
 		include/jeffpc/refcnt.h
 		include/jeffpc/scgi.h
 		include/jeffpc/scgisvc.h

--- a/bst.c	Wed Jul 25 12:16:02 2018 -0400
+++ b/bst.c	Wed Jul 25 14:19:27 2018 -0400
@@ -62,150 +62,9 @@
 	return tree_insert_here(&tree->tree, newitem, &cookie->cookie);
 }
 
-static inline void __bst_swap_nodes(struct tree_tree *tree,
-				    struct tree_node *x,
-				    struct tree_node *y,
-				    const enum tree_dir left)
+void bst_remove(struct bst_tree *tree, void *item)
 {
-	const enum tree_dir right = 1 - left;
-	const bool root = tree->root == x;
-	enum tree_dir dir_to_orig_x;
-
-	ASSERT3P(x, !=, y);
-	ASSERT3P(y->children[left], ==, NULL);
-
-	if (!root)
-		dir_to_orig_x = which_dir(x->parent, x);
-
-	if (x->children[right] == y) {
-		/*
-		 *  A                 A
-		 *   \                 \
-		 *    \                 \
-		 *     x                 y
-		 *    / \               / \
-		 *   /   \       =>    /   \
-		 *  B     y           B     x
-		 *         \                 \
-		 *          \                 \
-		 *           E                 E
-		 */
-		struct tree_node *A, *B, *E;
-
-		A = x->parent;
-		B = x->children[left];
-		E = y->children[right];
-
-		x->parent = y;
-		y->parent = A;
-		B->parent = y;
-		if (E)
-			E->parent = x;
-
-		x->children[left] = NULL;
-		x->children[right] = E;
-		y->children[left] = B;
-		y->children[right] = x;
-		if (!root)
-			A->children[dir_to_orig_x] = y;
-		else
-			tree->root = y;
-	} else {
-		/*
-		 *    A                 A
-		 *     \                 \
-		 *      \                 \
-		 *       x                 y
-		 *      / \               / \
-		 *     /   \       =>    /   \
-		 *    B     C           B     C
-		 *         /                 /
-		 *        .                 .
-		 *       .                 .
-		 *      /                 /
-		 *     D                 D
-		 *    /                 /
-		 *   /                 /
-		 *  y                 x
-		 *   \                 \
-		 *    \                 \
-		 *     E                 E
-		 */
-		struct tree_node *A, *B, *C, *D, *E;
+	struct tree_node *p, *c;
 
-		A = x->parent;
-		B = x->children[left];
-		C = x->children[right];
-		D = y->parent;
-		E = y->children[right];
-
-		x->parent = D;
-		y->parent = A;
-		B->parent = y;
-		C->parent = y;
-		if (E)
-			E->parent = x;
-
-		x->children[left] = NULL;
-		x->children[right] = E;
-		y->children[left] = B;
-		y->children[right] = C;
-		if (!root)
-			A->children[dir_to_orig_x] = y;
-		else
-			tree->root = y;
-		D->children[left] = x;
-	}
-}
-
-static inline void __bst_remove_node(struct tree_tree *tree,
-				     struct tree_node *parent,
-				     struct tree_node *tgt,
-				     struct tree_node *child)
-{
-	if (parent)
-		parent->children[which_dir(parent, tgt)] = child;
-	else
-		tree->root = child;
-
-	if (child)
-		child->parent = parent;
+	tree_remove(&tree->tree, item, &p, &c);
 }
-
-void bst_remove(struct bst_tree *_tree, void *item)
-{
-	struct tree_tree *tree = &_tree->tree;
-	struct tree_node *node;
-
-	ASSERT3P(tree->root, !=, NULL);
-	ASSERT3P(item, !=, NULL);
-
-	node = obj2node(tree, item);
-
-	if (node->children[TREE_LEFT] && node->children[TREE_RIGHT])
-		/*
-		 * Two children: exchange it with a leaf-ish node greater
-		 * than this node.
-		 */
-		__bst_swap_nodes(tree, node,
-				 firstlast(node->children[TREE_RIGHT], TREE_LEFT),
-				 TREE_LEFT);
-
-	/* now, we have zero or one child */
-	ASSERT(!node->children[TREE_LEFT] || !node->children[TREE_RIGHT]);
-
-	if (node->children[TREE_LEFT])
-		__bst_remove_node(tree, node->parent, node,
-				  node->children[TREE_LEFT]);
-	else if (node->children[TREE_RIGHT])
-		__bst_remove_node(tree, node->parent, node,
-				  node->children[TREE_RIGHT]);
-	else
-		__bst_remove_node(tree, node->parent, node, NULL);
-
-	node->parent = NULL;
-	node->children[TREE_LEFT] = NULL;
-	node->children[TREE_RIGHT] = NULL;
-
-	tree->num_nodes--;
-}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/include/jeffpc/rbtree.h	Wed Jul 25 14:19:27 2018 -0400
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#ifndef __JEFFPC_RBTREE_H
+#define __JEFFPC_RBTREE_H
+
+#include <stdbool.h>
+
+#include <jeffpc/tree_private.h>
+
+struct rb_node {
+	struct tree_node node;
+};
+
+struct rb_tree {
+	struct tree_tree tree;
+};
+
+struct rb_cookie {
+	struct tree_cookie cookie;
+};
+
+#define rb_for_each(tree, pos) \
+	for (pos = rb_first(tree); pos; pos = rb_next(tree, pos))
+
+extern void rb_create(struct rb_tree *tree,
+		      int (*cmp)(const void *, const void *),
+		      size_t size, size_t off);
+extern void rb_destroy(struct rb_tree *tree);
+
+extern void rb_add(struct rb_tree *tree, void *item);
+extern void *rb_insert_here(struct rb_tree *tree, void *item,
+			    struct rb_cookie *cookie);
+#define rb_insert(tree, item)	rb_insert_here((tree), (item), NULL)
+extern void rb_remove(struct rb_tree *tree, void *item);
+
+static inline bool rb_is_empty(struct rb_tree *tree)
+{
+	return tree_is_empty(&tree->tree);
+}
+
+static inline size_t rb_numnodes(struct rb_tree *tree)
+{
+	return tree_numnodes(&tree->tree);
+}
+
+/*
+ * Search, iteration, and swapping are completely generic
+ */
+static inline void *rb_find(struct rb_tree *tree, const void *key,
+			    struct rb_cookie *cookie)
+{
+	return tree_find(&tree->tree, key, &cookie->cookie);
+}
+
+static inline void *rb_first(struct rb_tree *tree)
+{
+	return tree_first(&tree->tree);
+}
+
+static inline void *rb_last(struct rb_tree *tree)
+{
+	return tree_last(&tree->tree);
+}
+
+static inline void *rb_next(struct rb_tree *tree, void *item)
+{
+	return tree_next(&tree->tree, item);
+}
+
+static inline void *rb_prev(struct rb_tree *tree, void *item)
+{
+	return tree_prev(&tree->tree, item);
+}
+
+static inline void *rb_destroy_nodes(struct rb_tree *tree,
+				     struct rb_cookie *cookie)
+{
+	return tree_destroy_nodes(&tree->tree, &cookie->cookie);
+}
+
+static inline void rb_swap(struct rb_tree *tree1, struct rb_tree *tree2)
+{
+	tree_swap(&tree1->tree, &tree2->tree);
+}
+
+#endif

--- a/include/jeffpc/tree_private.h	Wed Jul 25 12:16:02 2018 -0400
+++ b/include/jeffpc/tree_private.h	Wed Jul 25 14:19:27 2018 -0400
@@ -30,6 +30,7 @@
 struct tree_node {
 	struct tree_node *children[2];
 	struct tree_node *parent;
+	bool red;
 };
 
 struct tree_tree {
@@ -40,6 +41,7 @@
 	size_t num_nodes;
 	enum {
 		TREE_FLAVOR_UNBALANCED,
+		TREE_FLAVOR_RED_BLACK,
 	} flavor;
 };
 

--- a/mapfile-vers	Wed Jul 25 12:16:02 2018 -0400
+++ b/mapfile-vers	Wed Jul 25 14:19:27 2018 -0400
@@ -153,6 +153,13 @@
 		rand64;
 		rand_buf;
 
+		# rbtree
+		rb_add;
+		rb_create;
+		rb_destroy;
+		rb_insert_here;
+		rb_remove;
+
 		# scgisvc
 		scgisvc;
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rbtree.c	Wed Jul 25 14:19:27 2018 -0400
@@ -0,0 +1,240 @@
+/*
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <string.h>
+
+#include <jeffpc/rbtree.h>
+#include <jeffpc/error.h>
+
+#include "tree_impl.h"
+
+static inline void set_red(struct tree_node *node, bool red)
+{
+	if (node)
+		node->red = red;
+}
+
+static inline bool is_red(struct tree_node *node)
+{
+	/* NB: NULLs are black by definition */
+	return node && node->red;
+}
+
+void rb_create(struct rb_tree *tree,
+	       int (*cmp)(const void *, const void *),
+	       size_t size, size_t off)
+{
+	ASSERT3U(off + sizeof(struct rb_node), <=, size);
+
+	tree->tree.cmp = cmp;
+	tree->tree.root = NULL;
+	tree->tree.node_size = size;
+	tree->tree.node_off = off;
+	tree->tree.num_nodes = 0;
+	tree->tree.flavor = TREE_FLAVOR_RED_BLACK;
+}
+
+void rb_destroy(struct rb_tree *tree)
+{
+	memset(tree, 0, sizeof(struct rb_tree));
+}
+
+void rb_add(struct rb_tree *tree, void *item)
+{
+	struct rb_node *orig;
+
+	orig = rb_insert(tree, item);
+	if (orig)
+		panic("%s(%p, %p) failed: tree already contains desired key",
+		      __func__, tree, item);
+}
+
+static void rb_rotate(struct tree_tree *tree, struct tree_node *node,
+		      enum tree_dir left)
+{
+	const enum tree_dir right = 1 - left;
+	struct tree_node *tmp;
+
+	ASSERT3P(node->children[right], !=, NULL);
+
+	tmp = node->children[right];
+	node->children[right] = tmp->children[left];
+
+	if (tmp->children[left])
+		tmp->children[left]->parent = node;
+
+	tmp->parent = node->parent;
+	if (!node->parent) {
+		tree->root = tmp;
+	} else {
+		node->parent->children[which_dir(node->parent, node)] = tmp;
+	}
+
+	tmp->children[left] = node;
+	node->parent = tmp;
+}
+
+void *rb_insert_here(struct rb_tree *tree, void *newitem,
+		     struct rb_cookie *cookie)
+{
+	struct tree_node *node;
+	void *tmp;
+
+	node = obj2node(&tree->tree, newitem);
+
+	/*
+	 * First, insert as if it were an unbalanced binary search tree but
+	 * with the new node marked as red.
+	 */
+	tmp = tree_insert_here(&tree->tree, newitem, &cookie->cookie);
+	if (tmp)
+		return tmp;
+
+	set_red(node, true);
+
+	/*
+	 * Second, restore red-black tree invariants.
+	 *
+	 * Based on algorithm in CLRS.
+	 */
+	while (node && is_red(node)) {
+		struct tree_node *gparent;
+		struct tree_node *parent;
+		struct tree_node *uncle;
+
+		parent  = node->parent;
+		gparent = parent ? parent->parent : NULL;
+		uncle   = gparent ?
+			gparent->children[1 - which_dir(gparent, parent)] : NULL;
+
+		if (!is_red(parent)) {
+			break;
+		} else if (is_red(uncle)) {
+			set_red(parent, false);
+			set_red(uncle, false);
+			set_red(gparent, true);
+			node = gparent;
+		} else {
+			if (which_dir(parent, node) != which_dir(gparent, parent)) {
+				/*
+				 *        G                G
+				 *       / \              / \
+				 *      /   \            /   \
+				 *     P     U  ==>     N     U
+				 *      \              /
+				 *       \            /
+				 *        N          P
+				 *
+				 * This doesn't fix anything, but it sets up
+				 * the tree for the rotation that follows.
+				 */
+				rb_rotate(&tree->tree, parent,
+					  1 - which_dir(parent, node));
+
+				node = parent;
+				parent  = node->parent;
+				gparent = parent ? parent->parent : NULL;
+			}
+
+			if (which_dir(parent, node) == which_dir(gparent, parent)) {
+				/*
+				 *        G             P
+				 *       / \           / \
+				 *      /   \         /   \
+				 *     P     U  ==>  N     G
+				 *    /                     \
+				 *   /                       \
+				 *  N                         U
+				 */
+				rb_rotate(&tree->tree, gparent,
+					  1 - which_dir(parent, node));
+			}
+
+			set_red(parent, false);
+			set_red(gparent, true);
+		}
+	}
+
+	set_red(tree->tree.root, false);
+
+	return NULL; /* no previous node */
+}
+
+void rb_remove(struct rb_tree *_tree, void *item)
+{
+	struct tree_tree *tree = &_tree->tree;
+	struct tree_node *parent;
+	struct tree_node *child;
+	struct tree_node *node;
+
+	node = obj2node(tree, item);
+
+	tree_remove(tree, item, &parent, &child);
+
+	/* we emptied the tree - no reason to bother fixing up */
+	if (!tree->root)
+		return;
+
+	/* removing a red node cannot violate red-black tree invariants */
+	if (is_red(node))
+		return;
+
+	node = child;
+
+	while (node != tree->root && !is_red(node)) {
+		const enum tree_dir left = which_dir(parent, node);
+		const enum tree_dir right = 1 - left;
+		struct tree_node *sibling;
+
+		sibling = parent->children[right];
+
+		if (is_red(sibling)) {
+			set_red(sibling, false);
+			set_red(parent, true);
+			rb_rotate(tree, parent, left);
+			sibling = parent->children[right];
+		}
+
+		if (!is_red(sibling->children[left]) &&
+		    !is_red(sibling->children[right])) {
+			set_red(sibling, true);
+			node = parent;
+		} else {
+			if (!is_red(sibling->children[right])) {
+				set_red(sibling->children[left], false);
+				set_red(sibling, true);
+				rb_rotate(tree, sibling, right);
+				sibling = parent->children[right];
+			}
+
+			set_red(sibling, is_red(parent));
+			set_red(parent, false);
+			set_red(sibling->children[right], false);
+			rb_rotate(tree, parent, left);
+			node = tree->root;
+		}
+
+		parent = node->parent;
+	}
+
+	set_red(node, false);
+}

--- a/tests/.hgignore	Wed Jul 25 12:16:02 2018 -0400
+++ b/tests/.hgignore	Wed Jul 25 14:19:27 2018 -0400
@@ -18,7 +18,8 @@
 test_sexpr_parser
 test_sexpr_eval
 test_sexpr_iter
-test_tree_destroy_nodes
+test_tree_bst
+test_tree_rb
 test_urldecode
 test_utf32-to-utf8
 test_utf8-to-utf32

--- a/tests/CMakeLists.txt	Wed Jul 25 12:16:02 2018 -0400
+++ b/tests/CMakeLists.txt	Wed Jul 25 14:19:27 2018 -0400
@@ -40,7 +40,8 @@
 build_test_bin_and_run(padding)
 build_test_bin_and_run(sexpr_eval)
 build_test_bin_and_run(sexpr_iter)
-build_test_bin_and_run(tree_destroy_nodes)
+build_test_bin_and_run(tree_bst)
+build_test_bin_and_run(tree_rb)
 build_test_bin_and_run(urldecode)
 build_test_bin_and_run(utf32-to-utf8)
 build_test_bin_and_run(utf8-to-utf32)

--- a/tests/perf_tree.c	Wed Jul 25 12:16:02 2018 -0400
+++ b/tests/perf_tree.c	Wed Jul 25 14:19:27 2018 -0400
@@ -23,13 +23,50 @@
 #include <jeffpc/jeffpc.h>
 #include <jeffpc/error.h>
 #include <jeffpc/bst.h>
+#include <jeffpc/rbtree.h>
 #include <jeffpc/rand.h>
 #include <jeffpc/time.h>
 
-#define NITERS		100000
+#define NITERS		1000000
+
+#define PERF_TREE_RB
+
+#if defined(PERF_TREE_BST)
+/*
+ * Use fewer iterations to avoid pathological behavior with sequential
+ * insertions taking O(n^2) with a large n.
+ */
+#undef NITERS
+#define NITERS			100000
+#define TREE_TREE		bst_tree
+#define TREE_NODE		bst_node
+#define TREE_COOKIE		bst_cookie
+#define TREE_CREATE		bst_create
+#define TREE_DESTROY		bst_destroy
+#define TREE_FIND		bst_find
+#define TREE_INSERT		bst_insert
+#define TREE_REMOVE		bst_remove
+#define TREE_FOR_EACH		bst_for_each
+#define TREE_NUMNODES		bst_numnodes
+#define TREE_DESTROY_NODES	bst_destroy_nodes
+#elif defined(PERF_TREE_RB)
+#define TREE_TREE		rb_tree
+#define TREE_NODE		rb_node
+#define TREE_COOKIE		rb_cookie
+#define TREE_CREATE		rb_create
+#define TREE_DESTROY		rb_destroy
+#define TREE_FIND		rb_find
+#define TREE_INSERT		rb_insert
+#define TREE_REMOVE		rb_remove
+#define TREE_FOR_EACH		rb_for_each
+#define TREE_NUMNODES		rb_numnodes
+#define TREE_DESTROY_NODES	rb_destroy_nodes
+#else
+#error "Unspecified test type"
+#endif
 
 struct node {
-	struct bst_node node;
+	struct TREE_NODE node;
 	uint32_t v;
 };
 
@@ -68,37 +105,37 @@
 	seq_v = 0;
 }
 
-static void insert(struct bst_tree *tree, struct node *nodes,
+static void insert(struct TREE_TREE *tree, struct node *nodes,
 		   uint32_t (*f)(void))
 {
 	uint64_t start, end;
 	size_t i, ok;
 
-	ASSERT3U(bst_numnodes(tree), ==, 0);
+	ASSERT3U(TREE_NUMNODES(tree), ==, 0);
 
 	start = gettick();
 	for (i = 0, ok = 0; i < NITERS; i++) {
 		nodes[i].v = f();
 
-		if (!bst_insert(tree, &nodes[i]))
+		if (!TREE_INSERT(tree, &nodes[i]))
 			ok++;
 	}
 	end = gettick();
 
-	ASSERT3U(bst_numnodes(tree), ==, ok);
+	ASSERT3U(TREE_NUMNODES(tree), ==, ok);
 
 	cmn_err(CE_INFO, "%zu/%zu insertions in %"PRIu64" ns", ok, NITERS,
 		end - start);
 }
 
-static void find_or_delete(struct bst_tree *tree, struct node *nodes,
+static void find_or_delete(struct TREE_TREE *tree, struct node *nodes,
 			   uint32_t (*f)(void), bool find_only)
 {
 	uint64_t start, end;
 	size_t orig_numnodes;
 	size_t i, ok;
 
-	orig_numnodes = bst_numnodes(tree);
+	orig_numnodes = TREE_NUMNODES(tree);
 
 	start = gettick();
 	for (i = 0, ok = 0; i < NITERS * 10; i++) {
@@ -107,19 +144,19 @@
 		};
 		struct node *node;
 
-		node = bst_find(tree, &key, NULL);
+		node = TREE_FIND(tree, &key, NULL);
 		if (node) {
 			if (!find_only)
-				bst_remove(tree, node);
+				TREE_REMOVE(tree, node);
 			ok++;
 		}
 	}
 	end = gettick();
 
 	if (find_only)
-		ASSERT3U(bst_numnodes(tree), ==, orig_numnodes);
+		ASSERT3U(TREE_NUMNODES(tree), ==, orig_numnodes);
 	else
-		ASSERT3U(bst_numnodes(tree), ==, orig_numnodes - ok);
+		ASSERT3U(TREE_NUMNODES(tree), ==, orig_numnodes - ok);
 
 	cmn_err(CE_INFO, "%zu/%zu %s in %"PRIu64" ns", ok, NITERS,
 		find_only ? "finds" : "deletions", end - start);
@@ -127,11 +164,11 @@
 
 static void test(uint32_t (*f)(void), void (*reset)(void))
 {
-	struct bst_tree tree;
+	struct TREE_TREE tree;
 	struct node *nodes;
 
-	bst_create(&tree, cmp, sizeof(struct node),
-		   offsetof(struct node, node));
+	TREE_CREATE(&tree, cmp, sizeof(struct node),
+		    offsetof(struct node, node));
 
 	nodes = calloc(NITERS, sizeof(struct node));
 	if (!nodes)
@@ -146,7 +183,7 @@
 
 	free(nodes);
 
-	bst_destroy(&tree);
+	TREE_DESTROY(&tree);
 }
 
 static void usage(const char *prog)
@@ -173,6 +210,9 @@
 
 	jeffpc_init(&init_ops);
 
+	if (argc < 2)
+		usage(argv[0]);
+
 	for (i = 1; i < argc; i++) {
 		test_name = argv[i];
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test_tree_bst.c	Wed Jul 25 14:19:27 2018 -0400
@@ -0,0 +1,610 @@
+/*
+ * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#define TEST_TREE_BST
+
+#include "test_tree_common.c"
+
+static struct test2 checks2[2] = {
+	[true]  = {
+		"ascending",
+		{ &a, NULL, &b },
+		{
+			{ &a, { &b } },
+			{ &b, { &a } },
+		},
+	},
+	[false] = {
+		"descending",
+		{ &b, &a, NULL },
+		{
+			{ &a, { &b } },
+			{ &b, { &a } },
+		},
+	},
+};
+
+static struct test3 checks3[6] = {
+	[0] = {
+		.pre = { &a,
+			 NULL, &b,
+			 NULL, NULL, NULL, &c },
+		.sub = {
+			[0] = { &a, { &b, NULL, &c }, },
+			[1] = { &b, { &a, NULL, &c }, },
+			[2] = { &c, { &a, NULL, &b }, },
+		},
+	},
+	[1] = {
+		.pre = { &a,
+			 NULL, &c,
+			 NULL, NULL, &b, NULL },
+		.sub = {
+			[0] = { &a, { &c, &b, NULL }, },
+			[1] = { &b, { &a, NULL, &c }, },
+			[2] = { &c, { &a, NULL, &b }, },
+		},
+	},
+	[2] = {
+		.pre = { &b,
+			 &a, &c },
+		.sub = {
+			[0] = { &a, { &b, NULL, &c }, },
+			[1] = { &b, { &c, &a, NULL }, },
+			[2] = { &c, { &b, &a, NULL }, },
+		},
+	},
+	[3] = {
+		.pre = { &b,
+			 &a, &c },
+		.sub = {
+			[0] = { &a, { &b, NULL, &c }, },
+			[1] = { &b, { &c, &a, NULL }, },
+			[2] = { &c, { &b, &a, NULL }, },
+		},
+	},
+	[4] = {
+		.pre = { &c,
+			 &a, NULL,
+			 NULL, &b, NULL, NULL },
+		.sub = {
+			[0] = { &a, { &c, &b, NULL }, },
+			[1] = { &b, { &c, &a, NULL }, },
+			[2] = { &c, { &a, NULL, &b }, },
+		},
+	},
+	[5] = {
+		.pre = { &c,
+			 &b, NULL,
+			 &a, NULL, NULL, NULL },
+		.sub = {
+			[0] = { &a, { &c, &b, NULL }, },
+			[1] = { &b, { &c, &a, NULL }, },
+			[2] = { &c, { &b, &a, NULL }, },
+		},
+	},
+};
+
+static struct test4 checks4[24] = {
+	[0]  = {
+		.pre = { &a,
+			 NULL, &b,
+			 NULL, NULL, NULL, &c,
+			 NULL, NULL, NULL, NULL, NULL, NULL, NULL, &d },
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[1] = { &b,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[2] = { &c,
+				{ &a,
+				  NULL, &b,
+				  NULL, NULL, NULL, &d },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &b,
+				  NULL, NULL, NULL, &c },
+			},
+		},
+	},
+	[1]  = {
+		.pre = { &a,
+			 NULL, &c,
+			 NULL, NULL, &b, &d },
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[2] = { &c,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &b, NULL },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, &b, NULL },
+			},
+		},
+	},
+	[2]  = {
+		.pre = TEST4_BACD,
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c, TEST3_BAD },
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[3]  = {
+		.pre = TEST4_BACD,
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c, TEST3_BAD },
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[4]  = {
+		.pre = TEST4_CADB,
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c,
+				{ &d,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+		},
+	},
+	[5]  = {
+		.pre = TEST4_CBDA,
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c,
+				{ &d,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+		},
+	},
+
+	[6]  = {
+		.pre = { &a,
+			 NULL, &b,
+			 NULL, NULL, NULL, &d,
+			 NULL, NULL, NULL, NULL, NULL, NULL, &c, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[1] = { &b,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[2] = { &c,
+				{ &a,
+				  NULL, &b,
+				  NULL, NULL, NULL, &d },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &b,
+				  NULL, NULL, NULL, &c },
+			},
+		},
+	},
+	[7]  = {
+		.pre = { &a,
+			 NULL, &c,
+			 NULL, NULL, &b, &d },
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[2] = { &c,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &b, NULL },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, &b, NULL },
+			},
+		},
+	},
+	[8]  = {
+		.pre = TEST4_BADC,
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c, TEST3_BAD },
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[9]  = {
+		.pre = TEST4_BACD,
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &c,
+				  NULL, NULL, NULL, &d },
+			},
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c, TEST3_BAD },
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[10] = {
+		.pre = TEST4_CADB,
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c,
+				{ &d,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+		},
+	},
+	[11] = {
+		.pre = TEST4_CBDA,
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c,
+				{ &d,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+		},
+	},
+
+	[12] = {
+		.pre = { &a,
+			 NULL, &d,
+			 NULL, NULL, &b, NULL,
+			 NULL, NULL, NULL, NULL, NULL, &c, NULL, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &b, NULL,
+				  NULL, &c, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[2] = { &c,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &b, NULL },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &b,
+				  NULL, NULL, NULL, &c },
+			},
+		},
+	},
+	[13] = {
+		.pre = { &a,
+			 NULL, &d,
+			 NULL, NULL, &c, NULL,
+			 NULL, NULL, NULL, NULL, &b, NULL, NULL, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &c, NULL,
+				  &b, NULL, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[2] = { &c,
+				{ &a,
+				  NULL, &d,
+				  NULL, NULL, &b, NULL },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, &b, NULL },
+			},
+		},
+	},
+	[14] = {
+		.pre = TEST4_BADC,
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c, TEST3_BAD },
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[15] = {
+		.pre = TEST4_BADC,
+		.sub = {
+			[0] = { &a,
+				{ &b,
+				  NULL, &d,
+				  NULL, NULL, &c, NULL },
+			},
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c, TEST3_BAD },
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[16] = {
+		.pre = TEST4_CADB,
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c,
+				{ &d,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+		},
+	},
+	[17] = {
+		.pre = TEST4_CBDA,
+		.sub = {
+			[0] = { &a, TEST3_CBD },
+			[1] = { &b, TEST3_CAD },
+			[2] = { &c,
+				{ &d,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+		},
+	},
+
+	[18] = {
+		.pre = { &d,
+			 &a, NULL,
+			 NULL, &b, NULL, NULL,
+			 NULL, NULL, NULL, &c, NULL, NULL, NULL, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &b, NULL,
+				  NULL, &c, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &d,
+				  &a, NULL,
+				  NULL, &c, NULL, NULL },
+			},
+			[2] = { &c,
+				{ &d,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &b,
+				  NULL, NULL, NULL, &c },
+			},
+		},
+	},
+	[19] = {
+		.pre = { &d,
+			 &a, NULL,
+			 NULL, &c, NULL, NULL,
+			 NULL, NULL, &b, NULL, NULL, NULL, NULL, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &c, NULL,
+				  &b, NULL, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &d,
+				  &a, NULL,
+				  NULL, &c, NULL, NULL },
+			},
+			[2] = { &c,
+				{ &d,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &a,
+				  NULL, &c,
+				  NULL, NULL, &b, NULL },
+			},
+		},
+	},
+	[20] = {
+		.pre = { &d,
+			 &b, NULL,
+			 &a, &c, NULL, NULL},
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &b, NULL,
+				  NULL, &c, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &d,
+				  &c, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[2] = { &c,
+				{ &d,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &b,
+				  &a, &c },
+			},
+		},
+	},
+	[21] = {
+		.pre = { &d,
+			 &b, NULL,
+			 &a, &c, NULL, NULL},
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &b, NULL,
+				  NULL, &c, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &d,
+				  &c, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[2] = { &c,
+				{ &d,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[3] = { &d, TEST3_BAC },
+		},
+	},
+	[22] = {
+		.pre = { &d,
+			 &c, NULL,
+			 &a, NULL, NULL, NULL,
+			 NULL, &b, NULL, NULL, NULL, NULL, NULL, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &c, NULL,
+				  &b, NULL, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &d,
+				  &c, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[2] = { &c,
+				{ &d,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &a, NULL,
+				  NULL, &b, NULL, NULL },
+			},
+		},
+	},
+	[23] = {
+		.pre = { &d,
+			 &c, NULL,
+			 &b, NULL, NULL, NULL,
+			 &a, NULL, NULL, NULL, NULL, NULL, NULL, NULL },
+		.sub = {
+			[0] = { &a,
+				{ &d,
+				  &c, NULL,
+				  &b, NULL, NULL, NULL },
+			},
+			[1] = { &b,
+				{ &d,
+				  &c, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[2] = { &c,
+				{ &d,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+			[3] = { &d,
+				{ &c,
+				  &b, NULL,
+				  &a, NULL, NULL, NULL },
+			},
+		},
+	},
+};

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test_tree_common.c	Wed Jul 25 14:19:27 2018 -0400
@@ -0,0 +1,392 @@
+/*
+ * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <jeffpc/types.h>
+#include <jeffpc/bst.h>
+#include <jeffpc/rbtree.h>
+
+#include "test.c"
+
+#if defined(TEST_TREE_BST)
+#define TREE_TREE		bst_tree
+#define TREE_NODE		bst_node
+#define TREE_COOKIE		bst_cookie
+#define TREE_CREATE		bst_create
+#define TREE_DESTROY		bst_destroy
+#define TREE_ADD		bst_add
+#define TREE_REMOVE		bst_remove
+#define TREE_FOR_EACH		bst_for_each
+#define TREE_NUMNODES		bst_numnodes
+#define TREE_DESTROY_NODES	bst_destroy_nodes
+#elif defined(TEST_TREE_RB)
+#define TREE_TREE		rb_tree
+#define TREE_NODE		rb_node
+#define TREE_COOKIE		rb_cookie
+#define TREE_CREATE		rb_create
+#define TREE_DESTROY		rb_destroy
+#define TREE_ADD		rb_add
+#define TREE_REMOVE		rb_remove
+#define TREE_FOR_EACH		rb_for_each
+#define TREE_NUMNODES		rb_numnodes
+#define TREE_DESTROY_NODES	rb_destroy_nodes
+#else
+#error "Unspecified test type"
+#endif
+
+struct node {
+	struct TREE_NODE node;
+	const char *name;
+	int v;
+};
+
+/* various balanced orderings */
+#define TEST3_BAC	{ &b, \
+			  &a, &c }
+#define TEST3_BAD	{ &b, \
+			  &a, &d }
+#define TEST3_CAD	{ &c, \
+			  &a, &d }
+#define TEST3_CBD	{ &c, \
+			  &b, &d }
+
+#define TEST4_BACD	{ &b, \
+			  &a, &c, \
+			  NULL, NULL, NULL, &d }
+#define TEST4_BADC	{ &b, \
+			  &a, &d, \
+			  NULL, NULL, &c, NULL }
+#define TEST4_CADB	{ &c, \
+			  &a, &d, \
+			  NULL, &b, NULL, NULL }
+#define TEST4_CBDA	{ &c, \
+			  &b, &d, \
+			  &a, NULL, NULL, NULL }
+
+static struct node a = { .name = "a", .v = 10 };
+static struct node b = { .name = "b", .v = 20 };
+static struct node c = { .name = "c", .v = 30 };
+static struct node d = { .name = "d", .v = 40 };
+
+struct test2 {
+	const char *name;
+	struct node *pre[3];
+	struct subtest {
+		struct node *remove;
+		struct node *post[1];
+	} sub[2];
+};
+
+struct test3 {
+	struct node *pre[7];
+	struct {
+		struct node *remove;
+		struct node *nodes[3];
+	} sub[3];
+};
+
+struct test4 {
+	struct node *pre[15];
+	struct {
+		struct node *remove;
+		struct node *nodes[7];
+	} sub[4];
+};
+
+static struct test2 checks2[2];
+static struct test3 checks3[6];
+static struct test4 checks4[24];
+
+static int cmp(const void *va, const void *vb)
+{
+	const struct node *a = va;
+	const struct node *b = vb;
+
+	if (a->v < b->v)
+		return -1;
+	if (a->v > b->v)
+		return 1;
+	return 0;
+}
+
+static void init(struct TREE_TREE *tree, const char *testname, const char *nodename,
+		 size_t numnodes, struct node **nodes, bool begin)
+{
+	size_t i;
+
+	if (begin)
+		fprintf(stderr, "%zu nodes: %s - %s...", numnodes, testname,
+			nodename);
+
+	TREE_CREATE(tree, cmp, sizeof(struct node),
+		    offsetof(struct node, node));
+
+	/* insert the first set of pointers */
+	for (i = 0; i < numnodes; i++)
+		TREE_ADD(tree, nodes[i]);
+
+}
+
+static size_t __destroy_destroy(struct TREE_TREE *tree)
+{
+	struct TREE_COOKIE cookie;
+	struct node *node;
+	size_t removed_nodes;
+
+	fprintf(stderr, "destroy...");
+	memset(&cookie, 0, sizeof(cookie));
+	removed_nodes = 0;
+
+	while ((node = TREE_DESTROY_NODES(tree, &cookie)))
+		removed_nodes++;
+
+	return removed_nodes;
+}
+
+static void destroy(struct TREE_TREE *tree, size_t expected_numnodes,
+		    bool done)
+{
+	size_t remaining_nodes;
+
+	remaining_nodes = TREE_NUMNODES(tree);
+
+	VERIFY3U(remaining_nodes, ==, expected_numnodes);
+
+	/* test destruction */
+	remaining_nodes -= __destroy_destroy(tree);
+
+	VERIFY0(remaining_nodes);
+	VERIFY0(TREE_NUMNODES(tree));
+
+	TREE_DESTROY(tree);
+
+	if (done)
+		fprintf(stderr, "ok.\n");
+}
+
+static void __verify_nodes(struct tree_node *node, size_t numnodes,
+			   struct node **exp, size_t level,
+			   size_t leveloff)
+{
+	size_t idx = (1 << level) - 1 + leveloff;
+
+	if ((idx >= numnodes) || !exp[idx]) {
+		VERIFY3P(node, ==, NULL);
+		return;
+	}
+
+	if (node != &exp[idx]->node.node) {
+		panic("node (%p) != expected (%p) at index %zu",
+		      node, &exp[idx]->node.node, idx);
+	}
+
+	__verify_nodes(node->children[TREE_LEFT], numnodes, exp,
+		       level + 1, leveloff * 2);
+	__verify_nodes(node->children[TREE_RIGHT], numnodes, exp,
+		       level + 1, leveloff * 2 + 1);
+}
+
+static void verify_nodes(struct TREE_TREE *tree, size_t numnodes,
+			 struct node **exp)
+{
+	fprintf(stderr, "verify...");
+	__verify_nodes(tree->tree.root, numnodes, exp, 0, 0);
+}
+
+static void verify_iter(struct TREE_TREE *tree, size_t expected_numnodes)
+{
+	struct node *max_node;
+	struct node *node;
+	size_t found_nodes;
+	int max_so_far;
+
+	fprintf(stderr, "iter...");
+	VERIFY3U(TREE_NUMNODES(tree), ==, expected_numnodes);
+
+	found_nodes = 0;
+	max_so_far = INT_MIN;
+	max_node = NULL;
+	TREE_FOR_EACH(tree, node) {
+		found_nodes++;
+
+		if (max_so_far >= node->v)
+			panic("found node with value preceding previous "
+			      "(current: %d @ %p, previous: %d @ %p)",
+			      node->v, node, max_so_far, max_node);
+
+		max_so_far = node->v;
+		max_node = node;
+	}
+
+	VERIFY3U(TREE_NUMNODES(tree), ==, found_nodes);
+	VERIFY3U(TREE_NUMNODES(tree), ==, expected_numnodes);
+}
+
+static void test_nodes(const char *testname, struct node *remove,
+		       size_t numinsert, struct node **inserts,
+		       size_t npre, struct node **pre,
+		       size_t npost, struct node **post)
+{
+	struct TREE_TREE tree;
+
+	init(&tree, testname, remove ? remove->name : "(none)", numinsert, inserts, true);
+#if 0
+	fprintf(stderr, "   node dump:\n");
+	for (size_t i = 0; i < numinsert; i++)
+		fprintf(stderr, "       [%zu] = %p\n", i, inserts[i]);
+#endif
+	verify_nodes(&tree, npre, pre);
+	verify_iter(&tree, numinsert);
+	destroy(&tree, numinsert, !remove);
+
+	if (!remove)
+		return;
+
+	init(&tree, NULL, NULL, numinsert, inserts, false);
+	verify_nodes(&tree, npre, pre);
+	verify_iter(&tree, numinsert);
+	fprintf(stderr, "remove...");
+	TREE_REMOVE(&tree, remove);
+	verify_nodes(&tree, npost, post);
+	verify_iter(&tree, numinsert - 1);
+	destroy(&tree, numinsert - 1, true);
+}
+
+static void test_empty(void)
+{
+	test_nodes("empty", NULL,
+		   0, NULL, 0, NULL, 0, NULL);
+}
+
+static void test_one(void)
+{
+	struct node *inserts[1] = { &a };
+	struct node *checks[1] = { &a };
+
+	test_nodes("root only", &a,
+		   ARRAY_LEN(inserts), inserts,
+		   ARRAY_LEN(checks), checks,
+		   0, NULL);
+}
+
+static void test_two(bool asc)
+{
+	size_t i;
+	struct node *inserts[2][2] = {
+		[true]  = { &a, &b },
+		[false] = { &b, &a },
+	};
+
+	for (i = 0; i < 2; i++)
+		test_nodes(checks2[asc].name,
+			   checks2[asc].sub[i].remove,
+			   ARRAY_LEN(inserts[asc]), inserts[asc],
+			   ARRAY_LEN(checks2[asc].pre), checks2[asc].pre,
+			   ARRAY_LEN(checks2[asc].sub[i].post), checks2[asc].sub[i].post);
+}
+
+static void test_three(int perm)
+{
+	size_t i;
+	struct node *inserts[6][3] = {
+		[0] = { &a, &b, &c },
+		[1] = { &a, &c, &b },
+		[2] = { &b, &a, &c },
+		[3] = { &b, &c, &a },
+		[4] = { &c, &a, &b },
+		[5] = { &c, &b, &a },
+	};
+
+	for (i = 0; i < 3 ; i++) {
+		char name[64];
+
+		snprintf(name, sizeof(name), "permutation: %d", perm);
+
+		test_nodes(name, checks3[perm].sub[i].remove,
+			   ARRAY_LEN(inserts[perm]), inserts[perm],
+			   ARRAY_LEN(checks3[perm].pre), checks3[perm].pre,
+			   ARRAY_LEN(checks3[perm].sub[i].nodes), checks3[perm].sub[i].nodes);
+	}
+}
+
+static void test_four(int perm)
+{
+	size_t i;
+	struct node *inserts[24][4] = {
+		[0]  = { &a, &b, &c, &d },
+		[1]  = { &a, &c, &b, &d },
+		[2]  = { &b, &a, &c, &d },
+		[3]  = { &b, &c, &a, &d },
+		[4]  = { &c, &a, &b, &d },
+		[5]  = { &c, &b, &a, &d },
+
+		[6]  = { &a, &b, &d, &c },
+		[7]  = { &a, &c, &d, &b },
+		[8]  = { &b, &a, &d, &c },
+		[9]  = { &b, &c, &d, &a },
+		[10] = { &c, &a, &d, &b },
+		[11] = { &c, &b, &d, &a },
+
+		[12] = { &a, &d, &b, &c },
+		[13] = { &a, &d, &c, &b },
+		[14] = { &b, &d, &a, &c },
+		[15] = { &b, &d, &c, &a },
+		[16] = { &c, &d, &a, &b },
+		[17] = { &c, &d, &b, &a },
+
+		[18] = { &d, &a, &b, &c },
+		[19] = { &d, &a, &c, &b },
+		[20] = { &d, &b, &a, &c },
+		[21] = { &d, &b, &c, &a },
+		[22] = { &d, &c, &a, &b },
+		[23] = { &d, &c, &b, &a },
+	};
+
+	for (i = 0; i < 4 ; i++) {
+		char name[64];
+
+		snprintf(name, sizeof(name), "permutation: %d", perm);
+
+		test_nodes(name, checks4[perm].sub[i].remove,
+			   ARRAY_LEN(inserts[perm]), inserts[perm],
+			   ARRAY_LEN(checks4[perm].pre), checks4[perm].pre,
+			   ARRAY_LEN(checks4[perm].sub[i].nodes), checks4[perm].sub[i].nodes);
+	}
+}
+
+static void test_insert(void)
+{
+	int i;
+
+	test_empty();
+	test_one();
+	test_two(true);
+	test_two(false);
+	for (i = 0; i < 6; i++)
+		test_three(i);
+	for (i = 0; i < 24; i++)
+		test_four(i);
+}
+
+void test(void)
+{
+	test_insert();
+}

--- a/tests/test_tree_destroy_nodes.c	Wed Jul 25 12:16:02 2018 -0400
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,168 +0,0 @@
-/*
- * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-
-#include <jeffpc/types.h>
-#include <jeffpc/bst.h>
-
-#include "test.c"
-
-struct node {
-	struct bst_node node;
-	int v;
-};
-
-static int cmp(const void *va, const void *vb)
-{
-	const struct node *a = va;
-	const struct node *b = vb;
-
-	if (a->v < b->v)
-		return -1;
-	if (a->v > b->v)
-		return 1;
-	return 0;
-}
-
-static void init(struct bst_tree *tree, const char *testname,
-		 size_t numnodes)
-{
-	fprintf(stderr, "Testing %zu (%s)...", numnodes, testname);
-
-	bst_create(tree, cmp, sizeof(struct node),
-		   offsetof(struct node, node));
-}
-
-static void insert(struct bst_tree *tree, int val)
-{
-	struct node *node;
-
-	node = malloc(sizeof(struct node));
-	ASSERT3P(node, !=, NULL);
-
-	node->v = val;
-
-	bst_add(tree, node);
-}
-
-static void __destroy_iter(struct bst_tree *tree, size_t expected_numnodes)
-{
-	struct node *node;
-	size_t found_nodes;
-
-	VERIFY3U(bst_numnodes(tree), ==, expected_numnodes);
-
-	found_nodes = 0;
-	bst_for_each(tree, node)
-		found_nodes++;
-
-	VERIFY3U(bst_numnodes(tree), ==, found_nodes);
-	VERIFY3U(bst_numnodes(tree), ==, expected_numnodes);
-}
-
-static size_t __destroy_destroy(struct bst_tree *tree)
-{
-	struct bst_cookie cookie;
-	struct bst_node *node;
-	size_t removed_nodes;
-
-	memset(&cookie, 0, sizeof(cookie));
-	removed_nodes = 0;
-
-	while ((node = bst_destroy_nodes(tree, &cookie))) {
-		memset(node, 0xba, sizeof(struct node));
-		removed_nodes++;
-	}
-
-	return removed_nodes;
-}
-
-static void destroy(struct bst_tree *tree, size_t expected_numnodes)
-{
-	size_t remaining_nodes;
-
-	remaining_nodes = bst_numnodes(tree);
-
-	VERIFY3U(remaining_nodes, ==, expected_numnodes);
-
-	/* test iteration */
-	__destroy_iter(tree, expected_numnodes);
-
-	/* test destruction */
-	remaining_nodes -= __destroy_destroy(tree);
-
-	VERIFY0(remaining_nodes);
-	VERIFY0(bst_numnodes(tree));
-
-	bst_destroy(tree);
-
-	fprintf(stderr, "ok.\n");
-}
-
-static void test_nodes(const char *testname, size_t numnodes, ...)
-{
-	struct bst_tree tree;
-	va_list ap;
-	size_t i;
-
-	init(&tree, testname, numnodes);
-	va_start(ap, numnodes);
-	for (i = 0; i < numnodes; i++)
-		insert(&tree, va_arg(ap, int));
-	va_end(ap);
-	destroy(&tree, numnodes);
-}
-
-void test(void)
-{
-	test_nodes("empty",		0);
-	test_nodes("root",		1, 5);
-	test_nodes("left-lean",		2, 2, 1);
-	test_nodes("right-lean",	2, 1, 2);
-	test_nodes("balanced",		3, 2, 1, 3);
-	test_nodes("L-L",		3, 3, 2, 1);
-	test_nodes("L-R",		3, 3, 1, 2);
-	test_nodes("R-R",		3, 1, 2, 3);
-	test_nodes("R-L",		3, 1, 3, 2);
-	test_nodes("L-R-L-R",		5, 5, 1, 4, 2, 3);
-	test_nodes("R-L-R-L",		5, 1, 5, 2, 4, 3);
-
-	test_nodes("complex A", 6,
-		   /* row 1 */ 5,
-		   /* row 2 */ 3, 6,
-		   /* row 3 */ 1, 4,
-		   /* row 4 */ 2);
-	test_nodes("complex B", 6,
-		   /* row 1 */ 5,
-		   /* row 2 */ 3, 6,
-		   /* row 3 */ 2, 4,
-		   /* row 4 */ 1);
-	test_nodes("complex C", 11,
-		   /* row 1 */ 4,
-		   /* row 2 */ 2, 8,
-		   /* row 3 */ 1, 3, 6, 10,
-		   /* row 4 */ 5, 7, 9, 11);
-	test_nodes("complex D", 10,
-		   /* row 1 */ 4,
-		   /* row 2 */ 2, 8,
-		   /* row 3 */ 1, 3, 6, 9,
-		   /* row 4 */ 5, 7, 10);
-}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test_tree_rb.c	Wed Jul 25 14:19:27 2018 -0400
@@ -0,0 +1,180 @@
+/*
+ * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#define TEST_TREE_RB
+
+#include "test_tree_common.c"
+
+static struct test2 checks2[2] = {
+	[true]  = {
+		"ascending",
+		{ &a, NULL, &b },
+		{
+			{ &a, { &b } },
+			{ &b, { &a } },
+		},
+	},
+	[false] = {
+		"descending",
+		{ &b, &a, NULL },
+		{
+			{ &a, { &b } },
+			{ &b, { &a } },
+		},
+	},
+};
+
+/*
+ * Since all permutations create the same tree, we test removal only for one
+ * of them
+ */
+static struct test3 checks3[6] = {
+	[0] = {
+		.pre = { &b, &a, &c },
+		.sub = {
+			[0] = { &a, { &b, NULL, &c }, },
+			[1] = { &b, { &c, &a, NULL }, },
+			[2] = { &c, { &b, &a, NULL }, },
+		},
+	},
+	[1] = {
+		.pre = { &b, &a, &c },
+	},
+	[2] = {
+		.pre = { &b, &a, &c },
+	},
+	[3] = {
+		.pre = { &b, &a, &c },
+	},
+	[4] = {
+		.pre = { &b, &a, &c },
+	},
+	[5] = {
+		.pre = { &b, &a, &c },
+	},
+};
+
+/*
+ * Since all permutations create only four different trees, we test removal
+ * only once for each of them.
+ */
+static struct test4 checks4[24] = {
+	[0]  = {
+		.pre = TEST4_BACD,
+		.sub = {
+			[0] = { &a, { &c, &b, &d }, },
+			[1] = { &b, { &c, &a, &d }, },
+			[2] = { &c, { &b, &a, &d }, },
+			[3] = { &d, { &b, &a, &c }, },
+		},
+	},
+	[1]  = {
+		.pre = TEST4_BACD,
+	},
+	[2]  = {
+		.pre = TEST4_BACD,
+	},
+	[3]  = {
+		.pre = TEST4_BACD,
+	},
+	[4]  = {
+		.pre = TEST4_BACD,
+	},
+	[5]  = {
+		.pre = TEST4_BACD,
+	},
+
+	[6]  = {
+		.pre = TEST4_BADC,
+		.sub = {
+			[0] = { &a, { &c, &b, &d }, },
+			[1] = { &b, { &c, &a, &d }, },
+			[2] = { &c, { &b, &a, &d }, },
+			[3] = { &d, { &b, &a, &c }, },
+		},
+	},
+	[7]  = {
+		.pre = TEST4_CADB,
+		.sub = {
+			[0] = { &a, { &c, &b, &d }, },
+			[1] = { &b, { &c, &a, &d }, },
+			[2] = { &c, { &b, &a, &d }, },
+			[3] = { &d, { &b, &a, &c }, },
+		},
+	},
+	[8]  = {
+		.pre = TEST4_BADC,
+	},
+	[9]  = {
+		.pre = TEST4_CBDA,
+		.sub = {
+			[0] = { &a, { &c, &b, &d }, },
+			[1] = { &b, { &c, &a, &d }, },
+			[2] = { &c, { &b, &a, &d }, },
+			[3] = { &d, { &b, &a, &c }, },
+		},
+	},
+	[10] = {
+		.pre = TEST4_CADB,
+	},
+	[11] = {
+		.pre = TEST4_CBDA,
+	},
+
+	[12] = {
+		.pre = TEST4_BADC,
+	},
+	[13] = {
+		.pre = TEST4_CADB,
+	},
+	[14] = {
+		.pre = TEST4_BADC,
+	},
+	[15] = {
+		.pre = TEST4_CBDA,
+	},
+	[16] = {
+		.pre = TEST4_CADB,
+	},
+	[17] = {
+		.pre = TEST4_CBDA,
+	},
+
+	[18] = {
+		.pre = TEST4_BADC,
+	},
+	[19] = {
+		.pre = TEST4_CADB,
+	},
+	[20] = {
+		.pre = TEST4_BADC,
+	},
+	[21] = {
+		.pre = TEST4_CBDA,
+	},
+	[22] = {
+		.pre = TEST4_CADB,
+	},
+	[23] = {
+		.pre = TEST4_CBDA,
+	},
+};

--- a/tree.c	Wed Jul 25 12:16:02 2018 -0400
+++ b/tree.c	Wed Jul 25 14:19:27 2018 -0400
@@ -88,6 +88,174 @@
 	return NULL;
 }
 
+static inline void __swap_nodes(struct tree_tree *tree,
+				struct tree_node *x,
+				struct tree_node *y,
+				const enum tree_dir left)
+{
+	const enum tree_dir right = 1 - left;
+	const bool root = tree->root == x;
+	enum tree_dir dir_to_orig_x;
+	bool tmp;
+
+	ASSERT3P(x, !=, y);
+	ASSERT3P(y->children[left], ==, NULL);
+
+	if (!root)
+		dir_to_orig_x = which_dir(x->parent, x);
+
+	if (x->children[right] == y) {
+		/*
+		 *  A                 A
+		 *   \                 \
+		 *    \                 \
+		 *     x                 y
+		 *    / \               / \
+		 *   /   \       =>    /   \
+		 *  B     y           B     x
+		 *         \                 \
+		 *          \                 \
+		 *           E                 E
+		 */
+		struct tree_node *A, *B, *E;
+
+		A = x->parent;
+		B = x->children[left];
+		E = y->children[right];
+
+		x->parent = y;
+		y->parent = A;
+		B->parent = y;
+		if (E)
+			E->parent = x;
+
+		x->children[left] = NULL;
+		x->children[right] = E;
+		y->children[left] = B;
+		y->children[right] = x;
+		if (!root)
+			A->children[dir_to_orig_x] = y;
+		else
+			tree->root = y;
+	} else {
+		/*
+		 *    A                 A
+		 *     \                 \
+		 *      \                 \
+		 *       x                 y
+		 *      / \               / \
+		 *     /   \       =>    /   \
+		 *    B     C           B     C
+		 *         /                 /
+		 *        .                 .
+		 *       .                 .
+		 *      /                 /
+		 *     D                 D
+		 *    /                 /
+		 *   /                 /
+		 *  y                 x
+		 *   \                 \
+		 *    \                 \
+		 *     E                 E
+		 */
+		struct tree_node *A, *B, *C, *D, *E;
+
+		A = x->parent;
+		B = x->children[left];
+		C = x->children[right];
+		D = y->parent;
+		E = y->children[right];
+
+		x->parent = D;
+		y->parent = A;
+		B->parent = y;
+		C->parent = y;
+		if (E)
+			E->parent = x;
+
+		x->children[left] = NULL;
+		x->children[right] = E;
+		y->children[left] = B;
+		y->children[right] = C;
+		if (!root)
+			A->children[dir_to_orig_x] = y;
+		else
+			tree->root = y;
+		D->children[left] = x;
+	}
+
+	/* swap the colors */
+	tmp = x->red;
+	x->red = y->red;
+	y->red = tmp;
+}
+
+static inline void __promote_node_child(struct tree_tree *tree,
+					struct tree_node *parent,
+					struct tree_node *node,
+					struct tree_node *child)
+{
+	if (parent)
+		parent->children[which_dir(parent, node)] = child;
+	else
+		tree->root = child;
+
+	if (child)
+		child->parent = parent;
+}
+
+/*
+ * Remove @item from @tree.
+ *
+ * @parent_r: the parent node of @child_r (may be NULL)
+ * @child_r: the node that ultimately took @item's new place in the tree
+ *	(may be NULL)
+ */
+void tree_remove(struct tree_tree *tree, void *item,
+		 struct tree_node **parent_r,
+		 struct tree_node **child_r)
+{
+	struct tree_node *parent;
+	struct tree_node *child;
+	struct tree_node *node;
+
+	ASSERT3P(tree, !=, NULL);
+	ASSERT3P(item, !=, NULL);
+
+	node = obj2node(tree, item);
+
+	/*
+	 * Two children: exchange it with a leaf-ish node greater than this
+	 * node.
+	 */
+	if (node->children[TREE_LEFT] && node->children[TREE_RIGHT])
+		__swap_nodes(tree, node,
+			     firstlast(node->children[TREE_RIGHT], TREE_LEFT),
+			     TREE_LEFT);
+
+	/* now, we have zero or one child */
+	ASSERT(!node->children[TREE_LEFT] || !node->children[TREE_RIGHT]);
+
+	parent = node->parent;
+	if (node->children[TREE_LEFT])
+		child = node->children[TREE_LEFT];
+	else
+		child = node->children[TREE_RIGHT];
+
+	__promote_node_child(tree, parent, node, child);
+
+	/* clear out the removed node */
+	node->parent = NULL;
+	node->children[TREE_LEFT] = NULL;
+	node->children[TREE_RIGHT] = NULL;
+
+	tree->num_nodes--;
+
+	/* return various info */
+	*parent_r = parent;
+	*child_r = child;
+}
+
 void *tree_first(struct tree_tree *tree)
 {
 	return firstlast_obj(tree, TREE_LEFT);

--- a/tree_impl.h	Wed Jul 25 12:16:02 2018 -0400
+++ b/tree_impl.h	Wed Jul 25 14:19:27 2018 -0400
@@ -27,6 +27,9 @@
 
 extern void *tree_insert_here(struct tree_tree *tree, void *newitem,
 			      struct tree_cookie *cookie);
+extern void tree_remove(struct tree_tree *tree, void *item,
+			struct tree_node **parent_r,
+			struct tree_node **child_r);
 
 static inline void *node2obj(struct tree_tree *tree, struct tree_node *node)
 {