From 317c0644ccf108aa23ef3fd8358bd66c2840bfc0 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 14 Apr 2024 15:40:54 +0200 Subject: Adding upstream version 5:7.2.4. Signed-off-by: Daniel Baumann --- deps/jemalloc/test/unit/ph.c | 330 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 330 insertions(+) create mode 100644 deps/jemalloc/test/unit/ph.c (limited to 'deps/jemalloc/test/unit/ph.c') diff --git a/deps/jemalloc/test/unit/ph.c b/deps/jemalloc/test/unit/ph.c new file mode 100644 index 0000000..28f5e48 --- /dev/null +++ b/deps/jemalloc/test/unit/ph.c @@ -0,0 +1,330 @@ +#include "test/jemalloc_test.h" + +#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; + heap_link_t link; + uint64_t key; +}; + +static int +node_cmp(const node_t *a, const node_t *b) { + int ret; + + ret = (a->key > b->key) - (a->key < b->key); + if (ret == 0) { + /* + * Duplicates are not allowed in the heap, so force an + * arbitrary ordering for non-identical items with equal keys. + */ + ret = (((uintptr_t)a) > ((uintptr_t)b)) + - (((uintptr_t)a) < ((uintptr_t)b)); + } + return ret; +} + +static int +node_cmp_magic(const node_t *a, const node_t *b) { + + expect_u32_eq(a->magic, NODE_MAGIC, "Bad magic"); + expect_u32_eq(b->magic, NODE_MAGIC, "Bad magic"); + + return node_cmp(a, b); +} + +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) { + unsigned i; + node_t *leftmost_child, *sibling; + + for (i = 0; i < depth; i++) { + malloc_printf("\t"); + } + malloc_printf("%2"FMTu64"\n", node->key); + + leftmost_child = node_lchild_get(node); + if (leftmost_child == NULL) { + return; + } + node_print(leftmost_child, depth + 1); + + for (sibling = node_next_get(leftmost_child); sibling != + NULL; sibling = node_next_get(sibling)) { + node_print(sibling, depth + 1); + } +} + +static void +heap_print(const heap_t *heap) { + node_t *auxelm; + + malloc_printf("vvv heap %p vvv\n", heap); + if (heap->ph.root == NULL) { + goto label_return; + } + + node_print(heap->ph.root, 0); + + 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); + } + +label_return: + malloc_printf("^^^ heap %p ^^^\n", heap); +} + +static unsigned +node_validate(const node_t *node, const node_t *parent) { + unsigned nnodes = 1; + node_t *leftmost_child, *sibling; + + if (parent != NULL) { + expect_d_ge(node_cmp_magic(node, parent), 0, + "Child is less than parent"); + } + + leftmost_child = node_lchild_get(node); + if (leftmost_child == NULL) { + return nnodes; + } + 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 = 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); + } + return nnodes; +} + +static unsigned +heap_validate(const heap_t *heap) { + unsigned nnodes = 0; + node_t *auxelm; + + if (heap->ph.root == NULL) { + goto label_return; + } + + nnodes += node_validate(heap->ph.root, NULL); + + 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); + } + +label_return: + if (false) { + heap_print(heap); + } + return nnodes; +} + +TEST_BEGIN(test_ph_empty) { + heap_t heap; + + heap_new(&heap); + 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 + +static void +node_remove(heap_t *heap, node_t *node) { + heap_remove(heap, node); + + node->magic = 0; +} + +static node_t * +node_remove_first(heap_t *heap) { + node_t *node = heap_remove_first(heap); + node->magic = 0; + return node; +} + +static node_t * +node_remove_any(heap_t *heap) { + node_t *node = heap_remove_any(heap); + node->magic = 0; + return node; +} + +TEST_BEGIN(test_ph_random) { +#define NNODES 25 +#define NBAGS 250 +#define SEED 42 + sfmt_t *sfmt; + uint64_t bag[NNODES]; + heap_t heap; + node_t nodes[NNODES]; + unsigned i, j, k; + + 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); + } + } + + for (j = 1; j <= NNODES; j++) { + /* Initialize heap and nodes. */ + heap_new(&heap); + expect_u_eq(heap_validate(&heap), 0, + "Incorrect node count"); + for (k = 0; k < j; k++) { + nodes[k].magic = NODE_MAGIC; + nodes[k].key = bag[k]; + } + + /* Insert nodes. */ + for (k = 0; k < j; k++) { + heap_insert(&heap, &nodes[k]); + if (i % 13 == 12) { + expect_ptr_not_null(heap_any(&heap), + "Heap should not be empty"); + /* Trigger merging. */ + expect_ptr_not_null(heap_first(&heap), + "Heap should not be empty"); + } + expect_u_eq(heap_validate(&heap), k + 1, + "Incorrect node count"); + } + + expect_false(heap_empty(&heap), + "Heap should not be empty"); + + /* Remove nodes. */ + switch (i % 6) { + case 0: + for (k = 0; k < j; k++) { + expect_u_eq(heap_validate(&heap), j - k, + "Incorrect node count"); + node_remove(&heap, &nodes[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]); + expect_u_eq(heap_validate(&heap), k - 1, + "Incorrect node count"); + } + break; + case 2: { + node_t *prev = NULL; + for (k = 0; k < j; k++) { + node_t *node = node_remove_first(&heap); + expect_u_eq(heap_validate(&heap), j - k + - 1, "Incorrect node count"); + if (prev != NULL) { + expect_d_ge(node_cmp(node, + prev), 0, + "Bad removal order"); + } + prev = node; + } + break; + } case 3: { + node_t *prev = NULL; + for (k = 0; k < j; k++) { + node_t *node = heap_first(&heap); + expect_u_eq(heap_validate(&heap), j - k, + "Incorrect node count"); + if (prev != NULL) { + expect_d_ge(node_cmp(node, + prev), 0, + "Bad removal order"); + } + node_remove(&heap, node); + expect_u_eq(heap_validate(&heap), j - k + - 1, "Incorrect node count"); + prev = node; + } + break; + } case 4: { + for (k = 0; k < j; k++) { + node_remove_any(&heap); + 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); + expect_u_eq(heap_validate(&heap), j - k, + "Incorrect node count"); + node_remove(&heap, node); + expect_u_eq(heap_validate(&heap), j - k + - 1, "Incorrect node count"); + } + break; + } default: + not_reached(); + } + + expect_ptr_null(heap_first(&heap), + "Heap should be empty"); + expect_ptr_null(heap_any(&heap), + "Heap should be empty"); + expect_true(heap_empty(&heap), "Heap should be empty"); + } + } + fini_gen_rand(sfmt); +#undef NNODES +#undef SEED +} +TEST_END + +int +main(void) { + return test( + test_ph_empty, + test_ph_random); +} -- cgit v1.2.3