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