diff options
Diffstat (limited to 'deps/jemalloc/test/unit/ph.c')
-rw-r--r-- | deps/jemalloc/test/unit/ph.c | 110 |
1 files changed, 61 insertions, 49 deletions
diff --git a/deps/jemalloc/test/unit/ph.c b/deps/jemalloc/test/unit/ph.c index 88bf56f88..28f5e488e 100644 --- a/deps/jemalloc/test/unit/ph.c +++ b/deps/jemalloc/test/unit/ph.c @@ -3,11 +3,12 @@ #include "jemalloc/internal/ph.h" typedef struct node_s node_t; +ph_structs(heap, node_t); struct node_s { #define NODE_MAGIC 0x9823af7e uint32_t magic; - phn(node_t) link; + heap_link_t link; uint64_t key; }; @@ -30,14 +31,28 @@ node_cmp(const node_t *a, const node_t *b) { static int node_cmp_magic(const node_t *a, const node_t *b) { - assert_u32_eq(a->magic, NODE_MAGIC, "Bad magic"); - assert_u32_eq(b->magic, NODE_MAGIC, "Bad magic"); + expect_u32_eq(a->magic, NODE_MAGIC, "Bad magic"); + expect_u32_eq(b->magic, NODE_MAGIC, "Bad magic"); return node_cmp(a, b); } -typedef ph(node_t) heap_t; -ph_gen(static, heap_, heap_t, node_t, link, node_cmp_magic); +ph_gen(static, heap, node_t, link, node_cmp_magic); + +static node_t * +node_next_get(const node_t *node) { + return phn_next_get((node_t *)node, offsetof(node_t, link)); +} + +static node_t * +node_prev_get(const node_t *node) { + return phn_prev_get((node_t *)node, offsetof(node_t, link)); +} + +static node_t * +node_lchild_get(const node_t *node) { + return phn_lchild_get((node_t *)node, offsetof(node_t, link)); +} static void node_print(const node_t *node, unsigned depth) { @@ -49,14 +64,14 @@ node_print(const node_t *node, unsigned depth) { } malloc_printf("%2"FMTu64"\n", node->key); - leftmost_child = phn_lchild_get(node_t, link, node); + leftmost_child = node_lchild_get(node); if (leftmost_child == NULL) { return; } node_print(leftmost_child, depth + 1); - for (sibling = phn_next_get(node_t, link, leftmost_child); sibling != - NULL; sibling = phn_next_get(node_t, link, sibling)) { + for (sibling = node_next_get(leftmost_child); sibling != + NULL; sibling = node_next_get(sibling)) { node_print(sibling, depth + 1); } } @@ -66,16 +81,15 @@ heap_print(const heap_t *heap) { node_t *auxelm; malloc_printf("vvv heap %p vvv\n", heap); - if (heap->ph_root == NULL) { + if (heap->ph.root == NULL) { goto label_return; } - node_print(heap->ph_root, 0); + node_print(heap->ph.root, 0); - for (auxelm = phn_next_get(node_t, link, heap->ph_root); auxelm != NULL; - auxelm = phn_next_get(node_t, link, auxelm)) { - assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t, - link, auxelm)), auxelm, + for (auxelm = node_next_get(heap->ph.root); auxelm != NULL; + auxelm = node_next_get(auxelm)) { + expect_ptr_eq(node_next_get(node_prev_get(auxelm)), auxelm, "auxelm's prev doesn't link to auxelm"); node_print(auxelm, 0); } @@ -90,22 +104,21 @@ node_validate(const node_t *node, const node_t *parent) { node_t *leftmost_child, *sibling; if (parent != NULL) { - assert_d_ge(node_cmp_magic(node, parent), 0, + expect_d_ge(node_cmp_magic(node, parent), 0, "Child is less than parent"); } - leftmost_child = phn_lchild_get(node_t, link, node); + leftmost_child = node_lchild_get(node); if (leftmost_child == NULL) { return nnodes; } - assert_ptr_eq((void *)phn_prev_get(node_t, link, leftmost_child), + expect_ptr_eq(node_prev_get(leftmost_child), (void *)node, "Leftmost child does not link to node"); nnodes += node_validate(leftmost_child, node); - for (sibling = phn_next_get(node_t, link, leftmost_child); sibling != - NULL; sibling = phn_next_get(node_t, link, sibling)) { - assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t, - link, sibling)), sibling, + for (sibling = node_next_get(leftmost_child); sibling != + NULL; sibling = node_next_get(sibling)) { + expect_ptr_eq(node_next_get(node_prev_get(sibling)), sibling, "sibling's prev doesn't link to sibling"); nnodes += node_validate(sibling, node); } @@ -117,16 +130,15 @@ heap_validate(const heap_t *heap) { unsigned nnodes = 0; node_t *auxelm; - if (heap->ph_root == NULL) { + if (heap->ph.root == NULL) { goto label_return; } - nnodes += node_validate(heap->ph_root, NULL); + nnodes += node_validate(heap->ph.root, NULL); - for (auxelm = phn_next_get(node_t, link, heap->ph_root); auxelm != NULL; - auxelm = phn_next_get(node_t, link, auxelm)) { - assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t, - link, auxelm)), auxelm, + for (auxelm = node_next_get(heap->ph.root); auxelm != NULL; + auxelm = node_next_get(auxelm)) { + expect_ptr_eq(node_next_get(node_prev_get(auxelm)), auxelm, "auxelm's prev doesn't link to auxelm"); nnodes += node_validate(auxelm, NULL); } @@ -142,9 +154,9 @@ TEST_BEGIN(test_ph_empty) { heap_t heap; heap_new(&heap); - assert_true(heap_empty(&heap), "Heap should be empty"); - assert_ptr_null(heap_first(&heap), "Unexpected node"); - assert_ptr_null(heap_any(&heap), "Unexpected node"); + expect_true(heap_empty(&heap), "Heap should be empty"); + expect_ptr_null(heap_first(&heap), "Unexpected node"); + expect_ptr_null(heap_any(&heap), "Unexpected node"); } TEST_END @@ -203,7 +215,7 @@ TEST_BEGIN(test_ph_random) { for (j = 1; j <= NNODES; j++) { /* Initialize heap and nodes. */ heap_new(&heap); - assert_u_eq(heap_validate(&heap), 0, + expect_u_eq(heap_validate(&heap), 0, "Incorrect node count"); for (k = 0; k < j; k++) { nodes[k].magic = NODE_MAGIC; @@ -214,34 +226,34 @@ TEST_BEGIN(test_ph_random) { for (k = 0; k < j; k++) { heap_insert(&heap, &nodes[k]); if (i % 13 == 12) { - assert_ptr_not_null(heap_any(&heap), + expect_ptr_not_null(heap_any(&heap), "Heap should not be empty"); /* Trigger merging. */ - assert_ptr_not_null(heap_first(&heap), + expect_ptr_not_null(heap_first(&heap), "Heap should not be empty"); } - assert_u_eq(heap_validate(&heap), k + 1, + expect_u_eq(heap_validate(&heap), k + 1, "Incorrect node count"); } - assert_false(heap_empty(&heap), + expect_false(heap_empty(&heap), "Heap should not be empty"); /* Remove nodes. */ switch (i % 6) { case 0: for (k = 0; k < j; k++) { - assert_u_eq(heap_validate(&heap), j - k, + expect_u_eq(heap_validate(&heap), j - k, "Incorrect node count"); node_remove(&heap, &nodes[k]); - assert_u_eq(heap_validate(&heap), j - k + expect_u_eq(heap_validate(&heap), j - k - 1, "Incorrect node count"); } break; case 1: for (k = j; k > 0; k--) { node_remove(&heap, &nodes[k-1]); - assert_u_eq(heap_validate(&heap), k - 1, + expect_u_eq(heap_validate(&heap), k - 1, "Incorrect node count"); } break; @@ -249,10 +261,10 @@ TEST_BEGIN(test_ph_random) { node_t *prev = NULL; for (k = 0; k < j; k++) { node_t *node = node_remove_first(&heap); - assert_u_eq(heap_validate(&heap), j - k + expect_u_eq(heap_validate(&heap), j - k - 1, "Incorrect node count"); if (prev != NULL) { - assert_d_ge(node_cmp(node, + expect_d_ge(node_cmp(node, prev), 0, "Bad removal order"); } @@ -263,15 +275,15 @@ TEST_BEGIN(test_ph_random) { node_t *prev = NULL; for (k = 0; k < j; k++) { node_t *node = heap_first(&heap); - assert_u_eq(heap_validate(&heap), j - k, + expect_u_eq(heap_validate(&heap), j - k, "Incorrect node count"); if (prev != NULL) { - assert_d_ge(node_cmp(node, + expect_d_ge(node_cmp(node, prev), 0, "Bad removal order"); } node_remove(&heap, node); - assert_u_eq(heap_validate(&heap), j - k + expect_u_eq(heap_validate(&heap), j - k - 1, "Incorrect node count"); prev = node; } @@ -279,17 +291,17 @@ TEST_BEGIN(test_ph_random) { } case 4: { for (k = 0; k < j; k++) { node_remove_any(&heap); - assert_u_eq(heap_validate(&heap), j - k + expect_u_eq(heap_validate(&heap), j - k - 1, "Incorrect node count"); } break; } case 5: { for (k = 0; k < j; k++) { node_t *node = heap_any(&heap); - assert_u_eq(heap_validate(&heap), j - k, + expect_u_eq(heap_validate(&heap), j - k, "Incorrect node count"); node_remove(&heap, node); - assert_u_eq(heap_validate(&heap), j - k + expect_u_eq(heap_validate(&heap), j - k - 1, "Incorrect node count"); } break; @@ -297,11 +309,11 @@ TEST_BEGIN(test_ph_random) { not_reached(); } - assert_ptr_null(heap_first(&heap), + expect_ptr_null(heap_first(&heap), "Heap should be empty"); - assert_ptr_null(heap_any(&heap), + expect_ptr_null(heap_any(&heap), "Heap should be empty"); - assert_true(heap_empty(&heap), "Heap should be empty"); + expect_true(heap_empty(&heap), "Heap should be empty"); } } fini_gen_rand(sfmt); |