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 heap_remove(heap, node);
152
153 node->magic = 0;
154 }
155
156 static node_t *
node_remove_first(heap_t * heap)157 node_remove_first(heap_t *heap)
158 {
159 node_t *node = heap_remove_first(heap);
160 node->magic = 0;
161 return (node);
162 }
163
TEST_BEGIN(test_ph_random)164 TEST_BEGIN(test_ph_random)
165 {
166 #define NNODES 25
167 #define NBAGS 250
168 #define SEED 42
169 sfmt_t *sfmt;
170 uint64_t bag[NNODES];
171 heap_t heap;
172 node_t nodes[NNODES];
173 unsigned i, j, k;
174
175 sfmt = init_gen_rand(SEED);
176 for (i = 0; i < NBAGS; i++) {
177 switch (i) {
178 case 0:
179 /* Insert in order. */
180 for (j = 0; j < NNODES; j++)
181 bag[j] = j;
182 break;
183 case 1:
184 /* Insert in reverse order. */
185 for (j = 0; j < NNODES; j++)
186 bag[j] = NNODES - j - 1;
187 break;
188 default:
189 for (j = 0; j < NNODES; j++)
190 bag[j] = gen_rand64_range(sfmt, NNODES);
191 }
192
193 for (j = 1; j <= NNODES; j++) {
194 /* Initialize heap and nodes. */
195 heap_new(&heap);
196 assert_u_eq(heap_validate(&heap), 0,
197 "Incorrect node count");
198 for (k = 0; k < j; k++) {
199 nodes[k].magic = NODE_MAGIC;
200 nodes[k].key = bag[k];
201 }
202
203 /* Insert nodes. */
204 for (k = 0; k < j; k++) {
205 heap_insert(&heap, &nodes[k]);
206 if (i % 13 == 12) {
207 /* Trigger merging. */
208 assert_ptr_not_null(heap_first(&heap),
209 "Heap should not be empty");
210 }
211 assert_u_eq(heap_validate(&heap), k + 1,
212 "Incorrect node count");
213 }
214
215 assert_false(heap_empty(&heap),
216 "Heap should not be empty");
217
218 /* Remove nodes. */
219 switch (i % 4) {
220 case 0:
221 for (k = 0; k < j; k++) {
222 assert_u_eq(heap_validate(&heap), j - k,
223 "Incorrect node count");
224 node_remove(&heap, &nodes[k]);
225 assert_u_eq(heap_validate(&heap), j - k
226 - 1, "Incorrect node count");
227 }
228 break;
229 case 1:
230 for (k = j; k > 0; k--) {
231 node_remove(&heap, &nodes[k-1]);
232 assert_u_eq(heap_validate(&heap), k - 1,
233 "Incorrect node count");
234 }
235 break;
236 case 2: {
237 node_t *prev = NULL;
238 for (k = 0; k < j; k++) {
239 node_t *node = node_remove_first(&heap);
240 assert_u_eq(heap_validate(&heap), j - k
241 - 1, "Incorrect node count");
242 if (prev != NULL) {
243 assert_d_ge(node_cmp(node,
244 prev), 0,
245 "Bad removal order");
246 }
247 prev = node;
248 }
249 break;
250 } case 3: {
251 node_t *prev = NULL;
252 for (k = 0; k < j; k++) {
253 node_t *node = heap_first(&heap);
254 assert_u_eq(heap_validate(&heap), j - k,
255 "Incorrect node count");
256 if (prev != NULL) {
257 assert_d_ge(node_cmp(node,
258 prev), 0,
259 "Bad removal order");
260 }
261 node_remove(&heap, node);
262 assert_u_eq(heap_validate(&heap), j - k
263 - 1, "Incorrect node count");
264 prev = node;
265 }
266 break;
267 } default:
268 not_reached();
269 }
270
271 assert_ptr_null(heap_first(&heap),
272 "Heap should be empty");
273 assert_true(heap_empty(&heap), "Heap should be empty");
274 }
275 }
276 fini_gen_rand(sfmt);
277 #undef NNODES
278 #undef SEED
279 }
280 TEST_END
281
282 int
main(void)283 main(void)
284 {
285 return (test(
286 test_ph_empty,
287 test_ph_random));
288 }
289