1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DEFINE(minheap, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "nodes",
6 });
7
8static void mhtest_do_inserts(struct minheap *mh, struct minheap_node **nodes,
9 size_t count) {
10 for (size_t i = 0; i < count; i++) {
11 struct minheap_node *mhn = vnew(mhn, ALLOC_ZERO);
12 MINHEAP_NODE_SET_KEY(mhn, count - i);
13 nodes[i] = mhn;
14 minheap_insert(heap: mh, node: mhn, MINHEAP_NODE_KEY(mhn));
15 }
16}
17
18TEST_DEFINE_UNIT(minheap, insert_remove_pop_order,
19 TEST_INTENSITY(10, 50, 1024)) {
20 size_t count = ctx->intensity_val ? ctx->intensity_val : 50;
21 struct minheap_node **nodes = vnews(nodes, count, ALLOC_ZERO);
22 TEST_ASSERT_NONNULL(nodes);
23
24 struct minheap *mh = minheap_create();
25 TEST_ASSERT_NONNULL(mh);
26 mhtest_do_inserts(mh, nodes, count);
27 TEST_ASSERT_EQ(MINHEAP_SIZE(mh), count);
28
29 for (size_t i = 0; i < count; i++) {
30 struct minheap_node *mhn = nodes[i];
31 minheap_remove(heap: mh, node: mhn);
32 vfree(mhn);
33 nodes[i] = NULL;
34 }
35
36 TEST_ASSERT_EQ(MINHEAP_SIZE(mh), 0);
37 mhtest_do_inserts(mh, nodes, count);
38
39 TEST_ASSERT_EQ(MINHEAP_NODE_KEY(minheap_peek(mh)), 1);
40 struct minheap_node *popped = minheap_pop(heap: mh);
41 TEST_ASSERT_EQ(MINHEAP_NODE_KEY(popped), 1);
42
43 vfree(nodes);
44 return TEST_SUCCESS;
45}
46