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
152	heap_remove(heap, node);
153
154	node->magic = 0;
155}
156
157static node_t *
158node_remove_first(heap_t *heap)
159{
160	node_t *node = heap_remove_first(heap);
161	node->magic = 0;
162	return (node);
163}
164
165TEST_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}
281TEST_END
282
283int
284main(void)
285{
286
287	return (test(
288	    test_ph_empty,
289	    test_ph_random));
290}
291