1 #include "test/jemalloc_test.h"
2
3 typedef struct node_s node_t;
4
5 struct node_s {
6 #define NODE_MAGIC 0x9823af7e
7 uint32_t magic;
8 phn(node_t) link;
9 uint64_t key;
10 };
11
12 static int
node_cmp(const node_t * a,const node_t * b)13 node_cmp(const node_t *a, const node_t *b)
14 {
15 int ret;
16
17 ret = (a->key > b->key) - (a->key < b->key);
18 if (ret == 0) {
19 /*
20 * Duplicates are not allowed in the heap, so force an
21 * arbitrary ordering for non-identical items with equal keys.
22 */
23 ret = (((uintptr_t)a) > ((uintptr_t)b))
24 - (((uintptr_t)a) < ((uintptr_t)b));
25 }
26 return (ret);
27 }
28
29 static int
node_cmp_magic(const node_t * a,const node_t * b)30 node_cmp_magic(const node_t *a, const node_t *b) {
31
32 assert_u32_eq(a->magic, NODE_MAGIC, "Bad magic");
33 assert_u32_eq(b->magic, NODE_MAGIC, "Bad magic");
34
35 return (node_cmp(a, b));
36 }
37
38 typedef ph(node_t) heap_t;
39 ph_gen(static, heap_, heap_t, node_t, link, node_cmp_magic);
40
41 static void
node_print(const node_t * node,unsigned depth)42 node_print(const node_t *node, unsigned depth)
43 {
44 unsigned i;
45 node_t *leftmost_child, *sibling;
46
47 for (i = 0; i < depth; i++)
48 malloc_printf("\t");
49 malloc_printf("%2"FMTu64"\n", node->key);
50
51 leftmost_child = phn_lchild_get(node_t, link, node);
52 if (leftmost_child == NULL)
53 return;
54 node_print(leftmost_child, depth + 1);
55
56 for (sibling = phn_next_get(node_t, link, leftmost_child); sibling !=
57 NULL; sibling = phn_next_get(node_t, link, sibling)) {
58 node_print(sibling, depth + 1);
59 }
60 }
61
62 static void
heap_print(const heap_t * heap)63 heap_print(const heap_t *heap)
64 {
65 node_t *auxelm;
66
67 malloc_printf("vvv heap %p vvv\n", heap);
68 if (heap->ph_root == NULL)
69 goto label_return;
70
71 node_print(heap->ph_root, 0);
72
73 for (auxelm = phn_next_get(node_t, link, heap->ph_root); auxelm != NULL;
74 auxelm = phn_next_get(node_t, link, auxelm)) {
75 assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t,
76 link, auxelm)), auxelm,
77 "auxelm's prev doesn't link to auxelm");
78 node_print(auxelm, 0);
79 }
80
81 label_return:
82 malloc_printf("^^^ heap %p ^^^\n", heap);
83 }
84
85 static unsigned
node_validate(const node_t * node,const node_t * parent)86 node_validate(const node_t *node, const node_t *parent)
87 {
88 unsigned nnodes = 1;
89 node_t *leftmost_child, *sibling;
90
91 if (parent != NULL) {
92 assert_d_ge(node_cmp_magic(node, parent), 0,
93 "Child is less than parent");
94 }
95
96 leftmost_child = phn_lchild_get(node_t, link, node);
97 if (leftmost_child == NULL)
98 return (nnodes);
99 assert_ptr_eq((void *)phn_prev_get(node_t, link, leftmost_child),
100 (void *)node, "Leftmost child does not link to node");
101 nnodes += node_validate(leftmost_child, node);
102
103 for (sibling = phn_next_get(node_t, link, leftmost_child); sibling !=
104 NULL; sibling = phn_next_get(node_t, link, sibling)) {
105 assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t,
106 link, sibling)), sibling,
107 "sibling's prev doesn't link to sibling");
108 nnodes += node_validate(sibling, node);
109 }
110 return (nnodes);
111 }
112
113 static unsigned
heap_validate(const heap_t * heap)114 heap_validate(const heap_t *heap)
115 {
116 unsigned nnodes = 0;
117 node_t *auxelm;
118
119 if (heap->ph_root == NULL)
120 goto label_return;
121
122 nnodes += node_validate(heap->ph_root, NULL);
123
124 for (auxelm = phn_next_get(node_t, link, heap->ph_root); auxelm != NULL;
125 auxelm = phn_next_get(node_t, link, auxelm)) {
126 assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t,
127 link, auxelm)), auxelm,
128 "auxelm's prev doesn't link to auxelm");
129 nnodes += node_validate(auxelm, NULL);
130 }
131
132 label_return:
133 if (false)
134 heap_print(heap);
135 return (nnodes);
136 }
137
TEST_BEGIN(test_ph_empty)138 TEST_BEGIN(test_ph_empty)
139 {
140 heap_t heap;
141
142 heap_new(&heap);
143 assert_true(heap_empty(&heap), "Heap should be empty");
144 assert_ptr_null(heap_first(&heap), "Unexpected node");
145 }
146 TEST_END
147
148 static void
node_remove(heap_t * heap,node_t * node)149 node_remove(heap_t *heap, node_t *node)
150 {
151
152 heap_remove(heap, node);
153
154 node->magic = 0;
155 }
156
157 static node_t *
node_remove_first(heap_t * heap)158 node_remove_first(heap_t *heap)
159 {
160 node_t *node = heap_remove_first(heap);
161 node->magic = 0;
162 return (node);
163 }
164
TEST_BEGIN(test_ph_random)165 TEST_BEGIN(test_ph_random)
166 {
167 #define NNODES 25
168 #define NBAGS 250
169 #define SEED 42
170 sfmt_t *sfmt;
171 uint64_t bag[NNODES];
172 heap_t heap;
173 node_t nodes[NNODES];
174 unsigned i, j, k;
175
176 sfmt = init_gen_rand(SEED);
177 for (i = 0; i < NBAGS; i++) {
178 switch (i) {
179 case 0:
180 /* Insert in order. */
181 for (j = 0; j < NNODES; j++)
182 bag[j] = j;
183 break;
184 case 1:
185 /* Insert in reverse order. */
186 for (j = 0; j < NNODES; j++)
187 bag[j] = NNODES - j - 1;
188 break;
189 default:
190 for (j = 0; j < NNODES; j++)
191 bag[j] = gen_rand64_range(sfmt, NNODES);
192 }
193
194 for (j = 1; j <= NNODES; j++) {
195 /* Initialize heap and nodes. */
196 heap_new(&heap);
197 assert_u_eq(heap_validate(&heap), 0,
198 "Incorrect node count");
199 for (k = 0; k < j; k++) {
200 nodes[k].magic = NODE_MAGIC;
201 nodes[k].key = bag[k];
202 }
203
204 /* Insert nodes. */
205 for (k = 0; k < j; k++) {
206 heap_insert(&heap, &nodes[k]);
207 if (i % 13 == 12) {
208 /* Trigger merging. */
209 assert_ptr_not_null(heap_first(&heap),
210 "Heap should not be empty");
211 }
212 assert_u_eq(heap_validate(&heap), k + 1,
213 "Incorrect node count");
214 }
215
216 assert_false(heap_empty(&heap),
217 "Heap should not be empty");
218
219 /* Remove nodes. */
220 switch (i % 4) {
221 case 0:
222 for (k = 0; k < j; k++) {
223 assert_u_eq(heap_validate(&heap), j - k,
224 "Incorrect node count");
225 node_remove(&heap, &nodes[k]);
226 assert_u_eq(heap_validate(&heap), j - k
227 - 1, "Incorrect node count");
228 }
229 break;
230 case 1:
231 for (k = j; k > 0; k--) {
232 node_remove(&heap, &nodes[k-1]);
233 assert_u_eq(heap_validate(&heap), k - 1,
234 "Incorrect node count");
235 }
236 break;
237 case 2: {
238 node_t *prev = NULL;
239 for (k = 0; k < j; k++) {
240 node_t *node = node_remove_first(&heap);
241 assert_u_eq(heap_validate(&heap), j - k
242 - 1, "Incorrect node count");
243 if (prev != NULL) {
244 assert_d_ge(node_cmp(node,
245 prev), 0,
246 "Bad removal order");
247 }
248 prev = node;
249 }
250 break;
251 } case 3: {
252 node_t *prev = NULL;
253 for (k = 0; k < j; k++) {
254 node_t *node = heap_first(&heap);
255 assert_u_eq(heap_validate(&heap), j - k,
256 "Incorrect node count");
257 if (prev != NULL) {
258 assert_d_ge(node_cmp(node,
259 prev), 0,
260 "Bad removal order");
261 }
262 node_remove(&heap, node);
263 assert_u_eq(heap_validate(&heap), j - k
264 - 1, "Incorrect node count");
265 prev = node;
266 }
267 break;
268 } default:
269 not_reached();
270 }
271
272 assert_ptr_null(heap_first(&heap),
273 "Heap should be empty");
274 assert_true(heap_empty(&heap), "Heap should be empty");
275 }
276 }
277 fini_gen_rand(sfmt);
278 #undef NNODES
279 #undef SEED
280 }
281 TEST_END
282
283 int
main(void)284 main(void)
285 {
286
287 return (test(
288 test_ph_empty,
289 test_ph_random));
290 }
291