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