diff options
Diffstat (limited to 'examples/redis-unstable/deps/jemalloc/test/unit/rb.c')
| -rw-r--r-- | examples/redis-unstable/deps/jemalloc/test/unit/rb.c | 1019 |
1 files changed, 0 insertions, 1019 deletions
diff --git a/examples/redis-unstable/deps/jemalloc/test/unit/rb.c b/examples/redis-unstable/deps/jemalloc/test/unit/rb.c deleted file mode 100644 index 827ec51..0000000 --- a/examples/redis-unstable/deps/jemalloc/test/unit/rb.c +++ /dev/null @@ -1,1019 +0,0 @@ -#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); -} |