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