xref: /netbsd-src/external/bsd/jemalloc/dist/test/unit/rb.c (revision 7bdf38e5b7a28439665f2fdeff81e36913eef7dd)

#include "test/jemalloc_test.h"

#include <stdlib.h>

#include "jemalloc/internal/rb.h"

#define rbtn_black_height(a_type, a_field, a_rbt, r_height) do {	\
	a_type *rbp_bh_t;						\
	for (rbp_bh_t = (a_rbt)->rbt_root, (r_height) = 0; rbp_bh_t !=	\
	    NULL; rbp_bh_t = rbtn_left_get(a_type, a_field,		\
	    rbp_bh_t)) {						\
		if (!rbtn_red_get(a_type, a_field, rbp_bh_t)) {		\
		(r_height)++;						\
		}							\
	}								\
} while (0)

static bool summarize_always_returns_true = false;

typedef struct node_s node_t;
struct node_s {
#define NODE_MAGIC 0x9823af7e
	uint32_t magic;
	rb_node(node_t) link;
	/* Order used by nodes. */
	uint64_t key;
	/*
	 * Our made-up summary property is "specialness", with summarization
	 * taking the max.
	 */
	uint64_t specialness;

	/*
	 * Used by some of the test randomization to avoid double-removing
	 * nodes.
	 */
	bool mid_remove;

	/*
	 * To test searching functionality, we want to temporarily weaken the
	 * ordering to allow non-equal nodes that nevertheless compare equal.
	 */
	bool allow_duplicates;

	/*
	 * In check_consistency, it's handy to know a node's rank in the tree;
	 * this tracks it (but only there; not all tests use this).
	 */
	int rank;
	int filtered_rank;

	/*
	 * Replicate the internal structure of the tree, to make sure the
	 * implementation doesn't miss any updates.
	 */
	const node_t *summary_lchild;
	const node_t *summary_rchild;
	uint64_t summary_max_specialness;
};

static int
node_cmp(const node_t *a, const node_t *b) {
	int ret;

	expect_u32_eq(a->magic, NODE_MAGIC, "Bad magic");
	expect_u32_eq(b->magic, NODE_MAGIC, "Bad magic");

	ret = (a->key > b->key) - (a->key < b->key);
	if (ret == 0 && !a->allow_duplicates) {
		/*
		 * Duplicates are not allowed in the tree, so force an
		 * arbitrary ordering for non-identical items with equal keys,
		 * unless the user is searching and wants to allow the
		 * duplicate.
		 */
		ret = (((uintptr_t)a) > ((uintptr_t)b))
		    - (((uintptr_t)a) < ((uintptr_t)b));
	}
	return ret;
}

static uint64_t
node_subtree_specialness(node_t *n, const node_t *lchild,
    const node_t *rchild) {
	uint64_t subtree_specialness = n->specialness;
	if (lchild != NULL
	    && lchild->summary_max_specialness > subtree_specialness) {
		subtree_specialness = lchild->summary_max_specialness;
	}
	if (rchild != NULL
	    && rchild->summary_max_specialness > subtree_specialness) {
		subtree_specialness = rchild->summary_max_specialness;
	}
	return subtree_specialness;
}

static bool
node_summarize(node_t *a, const node_t *lchild, const node_t *rchild) {
	uint64_t new_summary_max_specialness = node_subtree_specialness(
	    a, lchild, rchild);
	bool changed = (a->summary_lchild != lchild)
	    || (a->summary_rchild != rchild)
	    || (new_summary_max_specialness != a->summary_max_specialness);
	a->summary_max_specialness = new_summary_max_specialness;
	a->summary_lchild = lchild;
	a->summary_rchild = rchild;
	return changed || summarize_always_returns_true;
}

typedef rb_tree(node_t) tree_t;
rb_summarized_proto(static, tree_, tree_t, node_t);
rb_summarized_gen(static, tree_, tree_t, node_t, link, node_cmp,
    node_summarize);

static bool
specialness_filter_node(void *ctx, node_t *node) {
	uint64_t specialness = *(uint64_t *)ctx;
	return node->specialness >= specialness;
}

static bool
specialness_filter_subtree(void *ctx, node_t *node) {
	uint64_t specialness = *(uint64_t *)ctx;
	return node->summary_max_specialness >= specialness;
}

static node_t *
tree_iterate_cb(tree_t *tree, node_t *node, void *data) {
	unsigned *i = (unsigned *)data;
	node_t *search_node;

	expect_u32_eq(node->magic, NODE_MAGIC, "Bad magic");

	/* Test rb_search(). */
	search_node = tree_search(tree, node);
	expect_ptr_eq(search_node, node,
	    "tree_search() returned unexpected node");

	/* Test rb_nsearch(). */
	search_node = tree_nsearch(tree, node);
	expect_ptr_eq(search_node, node,
	    "tree_nsearch() returned unexpected node");

	/* Test rb_psearch(). */
	search_node = tree_psearch(tree, node);
	expect_ptr_eq(search_node, node,
	    "tree_psearch() returned unexpected node");

	(*i)++;

	return NULL;
}

TEST_BEGIN(test_rb_empty) {
	tree_t tree;
	node_t key;

	tree_new(&tree);

	expect_true(tree_empty(&tree), "Tree should be empty");
	expect_ptr_null(tree_first(&tree), "Unexpected node");
	expect_ptr_null(tree_last(&tree), "Unexpected node");

	key.key = 0;
	key.magic = NODE_MAGIC;
	expect_ptr_null(tree_search(&tree, &key), "Unexpected node");

	key.key = 0;
	key.magic = NODE_MAGIC;
	expect_ptr_null(tree_nsearch(&tree, &key), "Unexpected node");

	key.key = 0;
	key.magic = NODE_MAGIC;
	expect_ptr_null(tree_psearch(&tree, &key), "Unexpected node");

	unsigned nodes = 0;
	tree_iter_filtered(&tree, NULL, &tree_iterate_cb,
	    &nodes, &specialness_filter_node, &specialness_filter_subtree,
	    NULL);
	expect_u_eq(0, nodes, "");

	nodes = 0;
	tree_reverse_iter_filtered(&tree, NULL, &tree_iterate_cb,
	    &nodes, &specialness_filter_node, &specialness_filter_subtree,
	    NULL);
	expect_u_eq(0, nodes, "");

	expect_ptr_null(tree_first_filtered(&tree, &specialness_filter_node,
	    &specialness_filter_subtree, NULL), "");
	expect_ptr_null(tree_last_filtered(&tree, &specialness_filter_node,
	    &specialness_filter_subtree, NULL), "");

	key.key = 0;
	key.magic = NODE_MAGIC;
	expect_ptr_null(tree_search_filtered(&tree, &key,
	    &specialness_filter_node, &specialness_filter_subtree, NULL), "");
	expect_ptr_null(tree_nsearch_filtered(&tree, &key,
	    &specialness_filter_node, &specialness_filter_subtree, NULL), "");
	expect_ptr_null(tree_psearch_filtered(&tree, &key,
	    &specialness_filter_node, &specialness_filter_subtree, NULL), "");
}
TEST_END

static unsigned
tree_recurse(node_t *node, unsigned black_height, unsigned black_depth) {
	unsigned ret = 0;
	node_t *left_node;
	node_t *right_node;

	if (node == NULL) {
		return ret;
	}

	left_node = rbtn_left_get(node_t, link, node);
	right_node = rbtn_right_get(node_t, link, node);

	expect_ptr_eq(left_node, node->summary_lchild,
	    "summary missed a tree update");
	expect_ptr_eq(right_node, node->summary_rchild,
	    "summary missed a tree update");

	uint64_t expected_subtree_specialness = node_subtree_specialness(node,
	    left_node, right_node);
	expect_u64_eq(expected_subtree_specialness,
	    node->summary_max_specialness, "Incorrect summary");

	if (!rbtn_red_get(node_t, link, node)) {
		black_depth++;
	}

	/* Red nodes must be interleaved with black nodes. */
	if (rbtn_red_get(node_t, link, node)) {
		if (left_node != NULL) {
			expect_false(rbtn_red_get(node_t, link, left_node),
				"Node should be black");
		}
		if (right_node != NULL) {
			expect_false(rbtn_red_get(node_t, link, right_node),
			    "Node should be black");
		}
	}

	/* Self. */
	expect_u32_eq(node->magic, NODE_MAGIC, "Bad magic");

	/* Left subtree. */
	if (left_node != NULL) {
		ret += tree_recurse(left_node, black_height, black_depth);
	} else {
		ret += (black_depth != black_height);
	}

	/* Right subtree. */
	if (right_node != NULL) {
		ret += tree_recurse(right_node, black_height, black_depth);
	} else {
		ret += (black_depth != black_height);
	}

	return ret;
}

static unsigned
tree_iterate(tree_t *tree) {
	unsigned i;

	i = 0;
	tree_iter(tree, NULL, tree_iterate_cb, (void *)&i);

	return i;
}

static unsigned
tree_iterate_reverse(tree_t *tree) {
	unsigned i;

	i = 0;
	tree_reverse_iter(tree, NULL, tree_iterate_cb, (void *)&i);

	return i;
}

static void
node_remove(tree_t *tree, node_t *node, unsigned nnodes) {
	node_t *search_node;
	unsigned black_height, imbalances;

	tree_remove(tree, node);

	/* Test rb_nsearch(). */
	search_node = tree_nsearch(tree, node);
	if (search_node != NULL) {
		expect_u64_ge(search_node->key, node->key,
		    "Key ordering error");
	}

	/* Test rb_psearch(). */
	search_node = tree_psearch(tree, node);
	if (search_node != NULL) {
		expect_u64_le(search_node->key, node->key,
		    "Key ordering error");
	}

	node->magic = 0;

	rbtn_black_height(node_t, link, tree, black_height);
	imbalances = tree_recurse(tree->rbt_root, black_height, 0);
	expect_u_eq(imbalances, 0, "Tree is unbalanced");
	expect_u_eq(tree_iterate(tree), nnodes-1,
	    "Unexpected node iteration count");
	expect_u_eq(tree_iterate_reverse(tree), nnodes-1,
	    "Unexpected node iteration count");
}

static node_t *
remove_iterate_cb(tree_t *tree, node_t *node, void *data) {
	unsigned *nnodes = (unsigned *)data;
	node_t *ret = tree_next(tree, node);

	node_remove(tree, node, *nnodes);

	return ret;
}

static node_t *
remove_reverse_iterate_cb(tree_t *tree, node_t *node, void *data) {
	unsigned *nnodes = (unsigned *)data;
	node_t *ret = tree_prev(tree, node);

	node_remove(tree, node, *nnodes);

	return ret;
}

static void
destroy_cb(node_t *node, void *data) {
	unsigned *nnodes = (unsigned *)data;

	expect_u_gt(*nnodes, 0, "Destruction removed too many nodes");
	(*nnodes)--;
}

TEST_BEGIN(test_rb_random) {
	enum {
		NNODES = 25,
		NBAGS = 500,
		SEED = 42
	};
	sfmt_t *sfmt;
	uint64_t bag[NNODES];
	tree_t tree;
	node_t nodes[NNODES];
	unsigned i, j, k, black_height, imbalances;

	sfmt = init_gen_rand(SEED);
	for (i = 0; i < NBAGS; i++) {
		switch (i) {
		case 0:
			/* Insert in order. */
			for (j = 0; j < NNODES; j++) {
				bag[j] = j;
			}
			break;
		case 1:
			/* Insert in reverse order. */
			for (j = 0; j < NNODES; j++) {
				bag[j] = NNODES - j - 1;
			}
			break;
		default:
			for (j = 0; j < NNODES; j++) {
				bag[j] = gen_rand64_range(sfmt, NNODES);
			}
		}

		/*
		 * We alternate test behavior with a period of 2 here, and a
		 * period of 5 down below, so there's no cycle in which certain
		 * combinations get omitted.
		 */
		summarize_always_returns_true = (i % 2 == 0);

		for (j = 1; j <= NNODES; j++) {
			/* Initialize tree and nodes. */
			tree_new(&tree);
			for (k = 0; k < j; k++) {
				nodes[k].magic = NODE_MAGIC;
				nodes[k].key = bag[k];
				nodes[k].specialness = gen_rand64_range(sfmt,
				    NNODES);
				nodes[k].mid_remove = false;
				nodes[k].allow_duplicates = false;
				nodes[k].summary_lchild = NULL;
				nodes[k].summary_rchild = NULL;
				nodes[k].summary_max_specialness = 0;
			}

			/* Insert nodes. */
			for (k = 0; k < j; k++) {
				tree_insert(&tree, &nodes[k]);

				rbtn_black_height(node_t, link, &tree,
				    black_height);
				imbalances = tree_recurse(tree.rbt_root,
				    black_height, 0);
				expect_u_eq(imbalances, 0,
				    "Tree is unbalanced");

				expect_u_eq(tree_iterate(&tree), k+1,
				    "Unexpected node iteration count");
				expect_u_eq(tree_iterate_reverse(&tree), k+1,
				    "Unexpected node iteration count");

				expect_false(tree_empty(&tree),
				    "Tree should not be empty");
				expect_ptr_not_null(tree_first(&tree),
				    "Tree should not be empty");
				expect_ptr_not_null(tree_last(&tree),
				    "Tree should not be empty");

				tree_next(&tree, &nodes[k]);
				tree_prev(&tree, &nodes[k]);
			}

			/* Remove nodes. */
			switch (i % 5) {
			case 0:
				for (k = 0; k < j; k++) {
					node_remove(&tree, &nodes[k], j - k);
				}
				break;
			case 1:
				for (k = j; k > 0; k--) {
					node_remove(&tree, &nodes[k-1], k);
				}
				break;
			case 2: {
				node_t *start;
				unsigned nnodes = j;

				start = NULL;
				do {
					start = tree_iter(&tree, start,
					    remove_iterate_cb, (void *)&nnodes);
					nnodes--;
				} while (start != NULL);
				expect_u_eq(nnodes, 0,
				    "Removal terminated early");
				break;
			} case 3: {
				node_t *start;
				unsigned nnodes = j;

				start = NULL;
				do {
					start = tree_reverse_iter(&tree, start,
					    remove_reverse_iterate_cb,
					    (void *)&nnodes);
					nnodes--;
				} while (start != NULL);
				expect_u_eq(nnodes, 0,
				    "Removal terminated early");
				break;
			} case 4: {
				unsigned nnodes = j;
				tree_destroy(&tree, destroy_cb, &nnodes);
				expect_u_eq(nnodes, 0,
				    "Destruction terminated early");
				break;
			} default:
				not_reached();
			}
		}
	}
	fini_gen_rand(sfmt);
}
TEST_END

static void
expect_simple_consistency(tree_t *tree, uint64_t specialness,
    bool expected_empty, node_t *expected_first, node_t *expected_last) {
	bool empty;
	node_t *first;
	node_t *last;

	empty = tree_empty_filtered(tree, &specialness_filter_node,
	    &specialness_filter_subtree, &specialness);
	expect_b_eq(expected_empty, empty, "");

	first = tree_first_filtered(tree,
	    &specialness_filter_node, &specialness_filter_subtree,
	    (void *)&specialness);
	expect_ptr_eq(expected_first, first, "");

	last = tree_last_filtered(tree,
	    &specialness_filter_node, &specialness_filter_subtree,
	    (void *)&specialness);
	expect_ptr_eq(expected_last, last, "");
}

TEST_BEGIN(test_rb_filter_simple) {
	enum {FILTER_NODES = 10};
	node_t nodes[FILTER_NODES];
	for (unsigned i = 0; i < FILTER_NODES; i++) {
		nodes[i].magic = NODE_MAGIC;
		nodes[i].key = i;
		if (i == 0) {
			nodes[i].specialness = 0;
		} else {
			nodes[i].specialness = ffs_u(i);
		}
		nodes[i].mid_remove = false;
		nodes[i].allow_duplicates = false;
		nodes[i].summary_lchild = NULL;
		nodes[i].summary_rchild = NULL;
		nodes[i].summary_max_specialness = 0;
	}

	summarize_always_returns_true = false;

	tree_t tree;
	tree_new(&tree);

	/* Should be empty */
	expect_simple_consistency(&tree, /* specialness */ 0, /* empty */ true,
	    /* first */ NULL, /* last */ NULL);

	/* Fill in just the odd nodes. */
	for (int i = 1; i < FILTER_NODES; i += 2) {
		tree_insert(&tree, &nodes[i]);
	}

	/* A search for an odd node should succeed. */
	expect_simple_consistency(&tree, /* specialness */ 0, /* empty */ false,
	    /* first */ &nodes[1], /* last */ &nodes[9]);

	/* But a search for an even one should fail. */
	expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ true,
	    /* first */ NULL, /* last */ NULL);

	/* Now we add an even. */
	tree_insert(&tree, &nodes[4]);
	expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false,
	    /* first */ &nodes[4], /* last */ &nodes[4]);

	/* A smaller even, and a larger even. */
	tree_insert(&tree, &nodes[2]);
	tree_insert(&tree, &nodes[8]);

	/*
	 * A first-search (resp. last-search) for an even should switch to the
	 * lower (higher) one, now that it's been added.
	 */
	expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false,
	    /* first */ &nodes[2], /* last */ &nodes[8]);

	/*
	 * If we remove 2, a first-search we should go back to 4, while a
	 * last-search should remain unchanged.
	 */
	tree_remove(&tree, &nodes[2]);
	expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false,
	    /* first */ &nodes[4], /* last */ &nodes[8]);

	/* Reinsert 2, then find it again. */
	tree_insert(&tree, &nodes[2]);
	expect_simple_consistency(&tree, /* specialness */ 1, /* empty */ false,
	    /* first */ &nodes[2], /* last */ &nodes[8]);

	/* Searching for a multiple of 4 should not have changed. */
	expect_simple_consistency(&tree, /* specialness */ 2, /* empty */ false,
	    /* first */ &nodes[4], /* last */ &nodes[8]);

	/* And a multiple of 8 */
	expect_simple_consistency(&tree, /* specialness */ 3, /* empty */ false,
	    /* first */ &nodes[8], /* last */ &nodes[8]);

	/* But not a multiple of 16 */
	expect_simple_consistency(&tree, /* specialness */ 4, /* empty */ true,
	    /* first */ NULL, /* last */ NULL);
}
TEST_END

typedef struct iter_ctx_s iter_ctx_t;
struct iter_ctx_s {
	int ncalls;
	node_t *last_node;

	int ncalls_max;
	bool forward;
};

static node_t *
tree_iterate_filtered_cb(tree_t *tree, node_t *node, void *arg) {
	iter_ctx_t *ctx = (iter_ctx_t *)arg;
	ctx->ncalls++;
	expect_u64_ge(node->specialness, 1,
	    "Should only invoke cb on nodes that pass the filter");
	if (ctx->last_node != NULL) {
		if (ctx->forward) {
			expect_d_lt(node_cmp(ctx->last_node, node), 0,
			    "Incorrect iteration order");
		} else {
			expect_d_gt(node_cmp(ctx->last_node, node), 0,
			    "Incorrect iteration order");
		}
	}
	ctx->last_node = node;
	if (ctx->ncalls == ctx->ncalls_max) {
		return node;
	}
	return NULL;
}

static int
qsort_node_cmp(const void *ap, const void *bp) {
	node_t *a = *(node_t **)ap;
	node_t *b = *(node_t **)bp;
	return node_cmp(a, b);
}

#define UPDATE_TEST_MAX 100
static void
check_consistency(tree_t *tree, node_t nodes[UPDATE_TEST_MAX], int nnodes) {
	uint64_t specialness = 1;

	bool empty;
	bool real_empty = true;
	node_t *first;
	node_t *real_first = NULL;
	node_t *last;
	node_t *real_last = NULL;
	for (int i = 0; i < nnodes; i++) {
		if (nodes[i].specialness >= specialness) {
			real_empty = false;
			if (real_first == NULL
			    || node_cmp(&nodes[i], real_first) < 0) {
				real_first = &nodes[i];
			}
			if (real_last == NULL
			    || node_cmp(&nodes[i], real_last) > 0) {
				real_last = &nodes[i];
			}
		}
	}

	empty = tree_empty_filtered(tree, &specialness_filter_node,
	    &specialness_filter_subtree, &specialness);
	expect_b_eq(real_empty, empty, "");

	first = tree_first_filtered(tree, &specialness_filter_node,
	    &specialness_filter_subtree, &specialness);
	expect_ptr_eq(real_first, first, "");

	last = tree_last_filtered(tree, &specialness_filter_node,
	    &specialness_filter_subtree, &specialness);
	expect_ptr_eq(real_last, last, "");

	for (int i = 0; i < nnodes; i++) {
		node_t *next_filtered;
		node_t *real_next_filtered = NULL;
		node_t *prev_filtered;
		node_t *real_prev_filtered = NULL;
		for (int j = 0; j < nnodes; j++) {
			if (nodes[j].specialness < specialness) {
				continue;
			}
			if (node_cmp(&nodes[j], &nodes[i]) < 0
			    && (real_prev_filtered == NULL
			    || node_cmp(&nodes[j], real_prev_filtered) > 0)) {
				real_prev_filtered = &nodes[j];
			}
			if (node_cmp(&nodes[j], &nodes[i]) > 0
			    && (real_next_filtered == NULL
			    || node_cmp(&nodes[j], real_next_filtered) < 0)) {
				real_next_filtered = &nodes[j];
			}
		}
		next_filtered = tree_next_filtered(tree, &nodes[i],
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_next_filtered, next_filtered, "");

		prev_filtered = tree_prev_filtered(tree, &nodes[i],
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_prev_filtered, prev_filtered, "");

		node_t *search_filtered;
		node_t *real_search_filtered;
		node_t *nsearch_filtered;
		node_t *real_nsearch_filtered;
		node_t *psearch_filtered;
		node_t *real_psearch_filtered;

		/*
		 * search, nsearch, psearch from a node before nodes[i] in the
		 * ordering.
		 */
		node_t before;
		before.magic = NODE_MAGIC;
		before.key = nodes[i].key - 1;
		before.allow_duplicates = false;
		real_search_filtered = NULL;
		search_filtered = tree_search_filtered(tree, &before,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_search_filtered, search_filtered, "");

		real_nsearch_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : real_next_filtered);
		nsearch_filtered = tree_nsearch_filtered(tree, &before,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, "");

		real_psearch_filtered = real_prev_filtered;
		psearch_filtered = tree_psearch_filtered(tree, &before,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_psearch_filtered, psearch_filtered, "");

		/* search, nsearch, psearch from nodes[i] */
		real_search_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : NULL);
		search_filtered = tree_search_filtered(tree, &nodes[i],
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_search_filtered, search_filtered, "");

		real_nsearch_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : real_next_filtered);
		nsearch_filtered = tree_nsearch_filtered(tree, &nodes[i],
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, "");

		real_psearch_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : real_prev_filtered);
		psearch_filtered = tree_psearch_filtered(tree, &nodes[i],
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_psearch_filtered, psearch_filtered, "");

		/*
		 * search, nsearch, psearch from a node equivalent to but
		 * distinct from nodes[i].
		 */
		node_t equiv;
		equiv.magic = NODE_MAGIC;
		equiv.key = nodes[i].key;
		equiv.allow_duplicates = true;
		real_search_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : NULL);
		search_filtered = tree_search_filtered(tree, &equiv,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_search_filtered, search_filtered, "");

		real_nsearch_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : real_next_filtered);
		nsearch_filtered = tree_nsearch_filtered(tree, &equiv,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, "");

		real_psearch_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : real_prev_filtered);
		psearch_filtered = tree_psearch_filtered(tree, &equiv,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_psearch_filtered, psearch_filtered, "");

		/*
		 * search, nsearch, psearch from a node after nodes[i] in the
		 * ordering.
		 */
		node_t after;
		after.magic = NODE_MAGIC;
		after.key = nodes[i].key + 1;
		after.allow_duplicates = false;
		real_search_filtered = NULL;
		search_filtered = tree_search_filtered(tree, &after,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_search_filtered, search_filtered, "");

		real_nsearch_filtered = real_next_filtered;
		nsearch_filtered = tree_nsearch_filtered(tree, &after,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_nsearch_filtered, nsearch_filtered, "");

		real_psearch_filtered = (nodes[i].specialness >= specialness ?
		    &nodes[i] : real_prev_filtered);
		psearch_filtered = tree_psearch_filtered(tree, &after,
		    &specialness_filter_node, &specialness_filter_subtree,
		    &specialness);
		expect_ptr_eq(real_psearch_filtered, psearch_filtered, "");
	}

	/* Filtered iteration test setup. */
	int nspecial = 0;
	node_t *sorted_nodes[UPDATE_TEST_MAX];
	node_t *sorted_filtered_nodes[UPDATE_TEST_MAX];
	for (int i = 0; i < nnodes; i++) {
		sorted_nodes[i] = &nodes[i];
	}
	qsort(sorted_nodes, nnodes, sizeof(node_t *), &qsort_node_cmp);
	for (int i = 0; i < nnodes; i++) {
		sorted_nodes[i]->rank = i;
		sorted_nodes[i]->filtered_rank = nspecial;
		if (sorted_nodes[i]->specialness >= 1) {
			sorted_filtered_nodes[nspecial] = sorted_nodes[i];
			nspecial++;
		}
	}

	node_t *iter_result;

	iter_ctx_t ctx;
	ctx.ncalls = 0;
	ctx.last_node = NULL;
	ctx.ncalls_max = INT_MAX;
	ctx.forward = true;

	/* Filtered forward iteration from the beginning. */
	iter_result = tree_iter_filtered(tree, NULL, &tree_iterate_filtered_cb,
	    &ctx, &specialness_filter_node, &specialness_filter_subtree,
	    &specialness);
	expect_ptr_null(iter_result, "");
	expect_d_eq(nspecial, ctx.ncalls, "");
	/* Filtered forward iteration from a starting point. */
	for (int i = 0; i < nnodes; i++) {
		ctx.ncalls = 0;
		ctx.last_node = NULL;
		iter_result = tree_iter_filtered(tree, &nodes[i],
		    &tree_iterate_filtered_cb, &ctx, &specialness_filter_node,
		    &specialness_filter_subtree, &specialness);
		expect_ptr_null(iter_result, "");
		expect_d_eq(nspecial - nodes[i].filtered_rank, ctx.ncalls, "");
	}
	/* Filtered forward iteration from the beginning, with stopping */
	for (int i = 0; i < nspecial; i++) {
		ctx.ncalls = 0;
		ctx.last_node = NULL;
		ctx.ncalls_max = i + 1;
		iter_result = tree_iter_filtered(tree, NULL,
		    &tree_iterate_filtered_cb, &ctx, &specialness_filter_node,
		    &specialness_filter_subtree, &specialness);
		expect_ptr_eq(sorted_filtered_nodes[i], iter_result, "");
		expect_d_eq(ctx.ncalls, i + 1, "");
	}
	/* Filtered forward iteration from a starting point, with stopping. */
	for (int i = 0; i < nnodes; i++) {
		for (int j = 0; j < nspecial - nodes[i].filtered_rank; j++) {
			ctx.ncalls = 0;
			ctx.last_node = NULL;
			ctx.ncalls_max = j + 1;
			iter_result = tree_iter_filtered(tree, &nodes[i],
			    &tree_iterate_filtered_cb, &ctx,
			    &specialness_filter_node,
			    &specialness_filter_subtree, &specialness);
			expect_d_eq(j + 1, ctx.ncalls, "");
			expect_ptr_eq(sorted_filtered_nodes[
			    nodes[i].filtered_rank + j], iter_result, "");
		}
	}

	/* Backwards iteration. */
	ctx.ncalls = 0;
	ctx.last_node = NULL;
	ctx.ncalls_max = INT_MAX;
	ctx.forward = false;

	/* Filtered backward iteration from the end. */
	iter_result = tree_reverse_iter_filtered(tree, NULL,
	    &tree_iterate_filtered_cb, &ctx, &specialness_filter_node,
	    &specialness_filter_subtree, &specialness);
	expect_ptr_null(iter_result, "");
	expect_d_eq(nspecial, ctx.ncalls, "");
	/* Filtered backward iteration from a starting point. */
	for (int i = 0; i < nnodes; i++) {
		ctx.ncalls = 0;
		ctx.last_node = NULL;
		iter_result = tree_reverse_iter_filtered(tree, &nodes[i],
		    &tree_iterate_filtered_cb, &ctx, &specialness_filter_node,
		    &specialness_filter_subtree, &specialness);
		expect_ptr_null(iter_result, "");
		int surplus_rank = (nodes[i].specialness >= 1 ? 1 : 0);
		expect_d_eq(nodes[i].filtered_rank + surplus_rank, ctx.ncalls,
		    "");
	}
	/* Filtered backward iteration from the end, with stopping */
	for (int i = 0; i < nspecial; i++) {
		ctx.ncalls = 0;
		ctx.last_node = NULL;
		ctx.ncalls_max = i + 1;
		iter_result = tree_reverse_iter_filtered(tree, NULL,
		    &tree_iterate_filtered_cb, &ctx, &specialness_filter_node,
		    &specialness_filter_subtree, &specialness);
		expect_ptr_eq(sorted_filtered_nodes[nspecial - i - 1],
		    iter_result, "");
		expect_d_eq(ctx.ncalls, i + 1, "");
	}
	/* Filtered backward iteration from a starting point, with stopping. */
	for (int i = 0; i < nnodes; i++) {
		int surplus_rank = (nodes[i].specialness >= 1 ? 1 : 0);
		for (int j = 0; j < nodes[i].filtered_rank + surplus_rank;
		    j++) {
			ctx.ncalls = 0;
			ctx.last_node = NULL;
			ctx.ncalls_max = j + 1;
			iter_result = tree_reverse_iter_filtered(tree,
			    &nodes[i], &tree_iterate_filtered_cb, &ctx,
			    &specialness_filter_node,
			    &specialness_filter_subtree, &specialness);
			expect_d_eq(j + 1, ctx.ncalls, "");
			expect_ptr_eq(sorted_filtered_nodes[
			    nodes[i].filtered_rank - j - 1 + surplus_rank],
			    iter_result, "");
		}
	}
}

static void
do_update_search_test(int nnodes, int ntrees, int nremovals,
    int nupdates) {
	node_t nodes[UPDATE_TEST_MAX];
	assert(nnodes <= UPDATE_TEST_MAX);

	sfmt_t *sfmt = init_gen_rand(12345);
	for (int i = 0; i < ntrees; i++) {
		tree_t tree;
		tree_new(&tree);
		for (int j = 0; j < nnodes; j++) {
			nodes[j].magic = NODE_MAGIC;
			/*
			 * In consistency checking, we increment or decrement a
			 * key and assume that the result is not a key in the
			 * tree.  This isn't a *real* concern with 64-bit keys
			 * and a good PRNG, but why not be correct anyways?
			 */
			nodes[j].key = 2 * gen_rand64(sfmt);
			nodes[j].specialness = 0;
			nodes[j].mid_remove = false;
			nodes[j].allow_duplicates = false;
			nodes[j].summary_lchild = NULL;
			nodes[j].summary_rchild = NULL;
			nodes[j].summary_max_specialness = 0;
			tree_insert(&tree, &nodes[j]);
		}
		for (int j = 0; j < nremovals; j++) {
			int victim = (int)gen_rand64_range(sfmt, nnodes);
			if (!nodes[victim].mid_remove) {
				tree_remove(&tree, &nodes[victim]);
				nodes[victim].mid_remove = true;
			}
		}
		for (int j = 0; j < nnodes; j++) {
			if (nodes[j].mid_remove) {
				nodes[j].mid_remove = false;
				nodes[j].key = 2 * gen_rand64(sfmt);
				tree_insert(&tree, &nodes[j]);
			}
		}
		for (int j = 0; j < nupdates; j++) {
			uint32_t ind = gen_rand32_range(sfmt, nnodes);
			nodes[ind].specialness = 1 - nodes[ind].specialness;
			tree_update_summaries(&tree, &nodes[ind]);
			check_consistency(&tree, nodes, nnodes);
		}
	}
}

TEST_BEGIN(test_rb_update_search) {
	summarize_always_returns_true = false;
	do_update_search_test(2, 100, 3, 50);
	do_update_search_test(5, 100, 3, 50);
	do_update_search_test(12, 100, 5, 1000);
	do_update_search_test(100, 1, 50, 500);
}
TEST_END

typedef rb_tree(node_t) unsummarized_tree_t;
rb_gen(static UNUSED, unsummarized_tree_, unsummarized_tree_t, node_t, link,
    node_cmp);

static node_t *
unsummarized_tree_iterate_cb(unsummarized_tree_t *tree, node_t *node,
    void *data) {
	unsigned *i = (unsigned *)data;
	(*i)++;
	return NULL;
}
/*
 * The unsummarized and summarized funtionality is implemented via the same
 * functions; we don't really need to do much more than test that we can exclude
 * the filtered functionality without anything breaking.
 */
TEST_BEGIN(test_rb_unsummarized) {
	unsummarized_tree_t tree;
	unsummarized_tree_new(&tree);
	unsigned nnodes = 0;
	unsummarized_tree_iter(&tree, NULL, &unsummarized_tree_iterate_cb,
	    &nnodes);
	expect_u_eq(0, nnodes, "");
}
TEST_END

int
main(void) {
	return test_no_reentrancy(
	    test_rb_empty,
	    test_rb_random,
	    test_rb_filter_simple,
	    test_rb_update_search,
	    test_rb_unsummarized);
}