1#include "test/jemalloc_test.h"
2
3typedef struct node_s node_t;
4
5struct node_s {
6#define	NODE_MAGIC 0x9823af7e
7	uint32_t magic;
8	phn(node_t) link;
9	uint64_t key;
10};
11
12static int
13node_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
29static int
30node_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
38typedef ph(node_t) heap_t;
39ph_gen(static, heap_, heap_t, node_t, link, node_cmp_magic);
40
41static void
42node_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
62static void
63heap_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
81label_return:
82	malloc_printf("^^^ heap %p ^^^\n", heap);
83}
84
85static unsigned
86node_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
113static unsigned
114heap_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
132label_return:
133	if (false)
134		heap_print(heap);
135	return (nnodes);
136}
137
138TEST_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}
146TEST_END
147
148static void
149node_remove(heap_t *heap, node_t *node)
150{
151	heap_remove(heap, node);
152
153	node->magic = 0;
154}
155
156static node_t *
157node_remove_first(heap_t *heap)
158{
159	node_t *node = heap_remove_first(heap);
160	node->magic = 0;
161	return (node);
162}
163
164TEST_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}
280TEST_END
281
282int
283main(void)
284{
285	return (test(
286	    test_ph_empty,
287	    test_ph_random));
288}
289