1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/ph.h" 4 5 typedef struct node_s node_t; 6 7 struct node_s { 8 #define NODE_MAGIC 0x9823af7e 9 uint32_t magic; 10 phn(node_t) link; 11 uint64_t key; 12 }; 13 14 static int 15 node_cmp(const node_t *a, const node_t *b) { 16 int ret; 17 18 ret = (a->key > b->key) - (a->key < b->key); 19 if (ret == 0) { 20 /* 21 * Duplicates are not allowed in the heap, so force an 22 * arbitrary ordering for non-identical items with equal keys. 23 */ 24 ret = (((uintptr_t)a) > ((uintptr_t)b)) 25 - (((uintptr_t)a) < ((uintptr_t)b)); 26 } 27 return ret; 28 } 29 30 static int 31 node_cmp_magic(const node_t *a, const node_t *b) { 32 33 assert_u32_eq(a->magic, NODE_MAGIC, "Bad magic"); 34 assert_u32_eq(b->magic, NODE_MAGIC, "Bad magic"); 35 36 return node_cmp(a, b); 37 } 38 39 typedef ph(node_t) heap_t; 40 ph_gen(static, heap_, heap_t, node_t, link, node_cmp_magic); 41 42 static void 43 node_print(const node_t *node, unsigned depth) { 44 unsigned i; 45 node_t *leftmost_child, *sibling; 46 47 for (i = 0; i < depth; i++) { 48 malloc_printf("\t"); 49 } 50 malloc_printf("%2"FMTu64"\n", node->key); 51 52 leftmost_child = phn_lchild_get(node_t, link, node); 53 if (leftmost_child == NULL) { 54 return; 55 } 56 node_print(leftmost_child, depth + 1); 57 58 for (sibling = phn_next_get(node_t, link, leftmost_child); sibling != 59 NULL; sibling = phn_next_get(node_t, link, sibling)) { 60 node_print(sibling, depth + 1); 61 } 62 } 63 64 static void 65 heap_print(const heap_t *heap) { 66 node_t *auxelm; 67 68 malloc_printf("vvv heap %p vvv\n", heap); 69 if (heap->ph_root == NULL) { 70 goto label_return; 71 } 72 73 node_print(heap->ph_root, 0); 74 75 for (auxelm = phn_next_get(node_t, link, heap->ph_root); auxelm != NULL; 76 auxelm = phn_next_get(node_t, link, auxelm)) { 77 assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t, 78 link, auxelm)), auxelm, 79 "auxelm's prev doesn't link to auxelm"); 80 node_print(auxelm, 0); 81 } 82 83 label_return: 84 malloc_printf("^^^ heap %p ^^^\n", heap); 85 } 86 87 static unsigned 88 node_validate(const node_t *node, const node_t *parent) { 89 unsigned nnodes = 1; 90 node_t *leftmost_child, *sibling; 91 92 if (parent != NULL) { 93 assert_d_ge(node_cmp_magic(node, parent), 0, 94 "Child is less than parent"); 95 } 96 97 leftmost_child = phn_lchild_get(node_t, link, node); 98 if (leftmost_child == NULL) { 99 return nnodes; 100 } 101 assert_ptr_eq((void *)phn_prev_get(node_t, link, leftmost_child), 102 (void *)node, "Leftmost child does not link to node"); 103 nnodes += node_validate(leftmost_child, node); 104 105 for (sibling = phn_next_get(node_t, link, leftmost_child); sibling != 106 NULL; sibling = phn_next_get(node_t, link, sibling)) { 107 assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t, 108 link, sibling)), sibling, 109 "sibling's prev doesn't link to sibling"); 110 nnodes += node_validate(sibling, node); 111 } 112 return nnodes; 113 } 114 115 static unsigned 116 heap_validate(const heap_t *heap) { 117 unsigned nnodes = 0; 118 node_t *auxelm; 119 120 if (heap->ph_root == NULL) { 121 goto label_return; 122 } 123 124 nnodes += node_validate(heap->ph_root, NULL); 125 126 for (auxelm = phn_next_get(node_t, link, heap->ph_root); auxelm != NULL; 127 auxelm = phn_next_get(node_t, link, auxelm)) { 128 assert_ptr_eq(phn_next_get(node_t, link, phn_prev_get(node_t, 129 link, auxelm)), auxelm, 130 "auxelm's prev doesn't link to auxelm"); 131 nnodes += node_validate(auxelm, NULL); 132 } 133 134 label_return: 135 if (false) { 136 heap_print(heap); 137 } 138 return nnodes; 139 } 140 141 TEST_BEGIN(test_ph_empty) { 142 heap_t heap; 143 144 heap_new(&heap); 145 assert_true(heap_empty(&heap), "Heap should be empty"); 146 assert_ptr_null(heap_first(&heap), "Unexpected node"); 147 assert_ptr_null(heap_any(&heap), "Unexpected node"); 148 } 149 TEST_END 150 151 static void 152 node_remove(heap_t *heap, node_t *node) { 153 heap_remove(heap, node); 154 155 node->magic = 0; 156 } 157 158 static node_t * 159 node_remove_first(heap_t *heap) { 160 node_t *node = heap_remove_first(heap); 161 node->magic = 0; 162 return node; 163 } 164 165 static node_t * 166 node_remove_any(heap_t *heap) { 167 node_t *node = heap_remove_any(heap); 168 node->magic = 0; 169 return node; 170 } 171 172 TEST_BEGIN(test_ph_random) { 173 #define NNODES 25 174 #define NBAGS 250 175 #define SEED 42 176 sfmt_t *sfmt; 177 uint64_t bag[NNODES]; 178 heap_t heap; 179 node_t nodes[NNODES]; 180 unsigned i, j, k; 181 182 sfmt = init_gen_rand(SEED); 183 for (i = 0; i < NBAGS; i++) { 184 switch (i) { 185 case 0: 186 /* Insert in order. */ 187 for (j = 0; j < NNODES; j++) { 188 bag[j] = j; 189 } 190 break; 191 case 1: 192 /* Insert in reverse order. */ 193 for (j = 0; j < NNODES; j++) { 194 bag[j] = NNODES - j - 1; 195 } 196 break; 197 default: 198 for (j = 0; j < NNODES; j++) { 199 bag[j] = gen_rand64_range(sfmt, NNODES); 200 } 201 } 202 203 for (j = 1; j <= NNODES; j++) { 204 /* Initialize heap and nodes. */ 205 heap_new(&heap); 206 assert_u_eq(heap_validate(&heap), 0, 207 "Incorrect node count"); 208 for (k = 0; k < j; k++) { 209 nodes[k].magic = NODE_MAGIC; 210 nodes[k].key = bag[k]; 211 } 212 213 /* Insert nodes. */ 214 for (k = 0; k < j; k++) { 215 heap_insert(&heap, &nodes[k]); 216 if (i % 13 == 12) { 217 assert_ptr_not_null(heap_any(&heap), 218 "Heap should not be empty"); 219 /* Trigger merging. */ 220 assert_ptr_not_null(heap_first(&heap), 221 "Heap should not be empty"); 222 } 223 assert_u_eq(heap_validate(&heap), k + 1, 224 "Incorrect node count"); 225 } 226 227 assert_false(heap_empty(&heap), 228 "Heap should not be empty"); 229 230 /* Remove nodes. */ 231 switch (i % 6) { 232 case 0: 233 for (k = 0; k < j; k++) { 234 assert_u_eq(heap_validate(&heap), j - k, 235 "Incorrect node count"); 236 node_remove(&heap, &nodes[k]); 237 assert_u_eq(heap_validate(&heap), j - k 238 - 1, "Incorrect node count"); 239 } 240 break; 241 case 1: 242 for (k = j; k > 0; k--) { 243 node_remove(&heap, &nodes[k-1]); 244 assert_u_eq(heap_validate(&heap), k - 1, 245 "Incorrect node count"); 246 } 247 break; 248 case 2: { 249 node_t *prev = NULL; 250 for (k = 0; k < j; k++) { 251 node_t *node = node_remove_first(&heap); 252 assert_u_eq(heap_validate(&heap), j - k 253 - 1, "Incorrect node count"); 254 if (prev != NULL) { 255 assert_d_ge(node_cmp(node, 256 prev), 0, 257 "Bad removal order"); 258 } 259 prev = node; 260 } 261 break; 262 } case 3: { 263 node_t *prev = NULL; 264 for (k = 0; k < j; k++) { 265 node_t *node = heap_first(&heap); 266 assert_u_eq(heap_validate(&heap), j - k, 267 "Incorrect node count"); 268 if (prev != NULL) { 269 assert_d_ge(node_cmp(node, 270 prev), 0, 271 "Bad removal order"); 272 } 273 node_remove(&heap, node); 274 assert_u_eq(heap_validate(&heap), j - k 275 - 1, "Incorrect node count"); 276 prev = node; 277 } 278 break; 279 } case 4: { 280 for (k = 0; k < j; k++) { 281 node_remove_any(&heap); 282 assert_u_eq(heap_validate(&heap), j - k 283 - 1, "Incorrect node count"); 284 } 285 break; 286 } case 5: { 287 for (k = 0; k < j; k++) { 288 node_t *node = heap_any(&heap); 289 assert_u_eq(heap_validate(&heap), j - k, 290 "Incorrect node count"); 291 node_remove(&heap, node); 292 assert_u_eq(heap_validate(&heap), j - k 293 - 1, "Incorrect node count"); 294 } 295 break; 296 } default: 297 not_reached(); 298 } 299 300 assert_ptr_null(heap_first(&heap), 301 "Heap should be empty"); 302 assert_ptr_null(heap_any(&heap), 303 "Heap should be empty"); 304 assert_true(heap_empty(&heap), "Heap should be empty"); 305 } 306 } 307 fini_gen_rand(sfmt); 308 #undef NNODES 309 #undef SEED 310 } 311 TEST_END 312 313 int 314 main(void) { 315 return test( 316 test_ph_empty, 317 test_ph_random); 318 } 319
