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