1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/rb.h" 4 5 #define rbtn_black_height(a_type, a_field, a_rbt, r_height) do { \ 6 a_type *rbp_bh_t; \ 7 for (rbp_bh_t = (a_rbt)->rbt_root, (r_height) = 0; rbp_bh_t != \ 8 NULL; rbp_bh_t = rbtn_left_get(a_type, a_field, \ 9 rbp_bh_t)) { \ 10 if (!rbtn_red_get(a_type, a_field, rbp_bh_t)) { \ 11 (r_height)++; \ 12 } \ 13 } \ 14 } while (0) 15 16 typedef struct node_s node_t; 17 18 struct node_s { 19 #define NODE_MAGIC 0x9823af7e 20 uint32_t magic; 21 rb_node(node_t) link; 22 uint64_t key; 23 }; 24 25 static int 26 node_cmp(const node_t *a, const node_t *b) { 27 int ret; 28 29 assert_u32_eq(a->magic, NODE_MAGIC, "Bad magic"); 30 assert_u32_eq(b->magic, NODE_MAGIC, "Bad magic"); 31 32 ret = (a->key > b->key) - (a->key < b->key); 33 if (ret == 0) { 34 /* 35 * Duplicates are not allowed in the tree, so force an 36 * arbitrary ordering for non-identical items with equal keys. 37 */ 38 ret = (((uintptr_t)a) > ((uintptr_t)b)) 39 - (((uintptr_t)a) < ((uintptr_t)b)); 40 } 41 return ret; 42 } 43 44 typedef rb_tree(node_t) tree_t; 45 rb_gen(static, tree_, tree_t, node_t, link, node_cmp); 46 47 TEST_BEGIN(test_rb_empty) { 48 tree_t tree; 49 node_t key; 50 51 tree_new(&tree); 52 53 assert_true(tree_empty(&tree), "Tree should be empty"); 54 assert_ptr_null(tree_first(&tree), "Unexpected node"); 55 assert_ptr_null(tree_last(&tree), "Unexpected node"); 56 57 key.key = 0; 58 key.magic = NODE_MAGIC; 59 assert_ptr_null(tree_search(&tree, &key), "Unexpected node"); 60 61 key.key = 0; 62 key.magic = NODE_MAGIC; 63 assert_ptr_null(tree_nsearch(&tree, &key), "Unexpected node"); 64 65 key.key = 0; 66 key.magic = NODE_MAGIC; 67 assert_ptr_null(tree_psearch(&tree, &key), "Unexpected node"); 68 } 69 TEST_END 70 71 static unsigned 72 tree_recurse(node_t *node, unsigned black_height, unsigned black_depth) { 73 unsigned ret = 0; 74 node_t *left_node; 75 node_t *right_node; 76 77 if (node == NULL) { 78 return ret; 79 } 80 81 left_node = rbtn_left_get(node_t, link, node); 82 right_node = rbtn_right_get(node_t, link, node); 83 84 if (!rbtn_red_get(node_t, link, node)) { 85 black_depth++; 86 } 87 88 /* Red nodes must be interleaved with black nodes. */ 89 if (rbtn_red_get(node_t, link, node)) { 90 if (left_node != NULL) { 91 assert_false(rbtn_red_get(node_t, link, left_node), 92 "Node should be black"); 93 } 94 if (right_node != NULL) { 95 assert_false(rbtn_red_get(node_t, link, right_node), 96 "Node should be black"); 97 } 98 } 99 100 /* Self. */ 101 assert_u32_eq(node->magic, NODE_MAGIC, "Bad magic"); 102 103 /* Left subtree. */ 104 if (left_node != NULL) { 105 ret += tree_recurse(left_node, black_height, black_depth); 106 } else { 107 ret += (black_depth != black_height); 108 } 109 110 /* Right subtree. */ 111 if (right_node != NULL) { 112 ret += tree_recurse(right_node, black_height, black_depth); 113 } else { 114 ret += (black_depth != black_height); 115 } 116 117 return ret; 118 } 119 120 static node_t * 121 tree_iterate_cb(tree_t *tree, node_t *node, void *data) { 122 unsigned *i = (unsigned *)data; 123 node_t *search_node; 124 125 assert_u32_eq(node->magic, NODE_MAGIC, "Bad magic"); 126 127 /* Test rb_search(). */ 128 search_node = tree_search(tree, node); 129 assert_ptr_eq(search_node, node, 130 "tree_search() returned unexpected node"); 131 132 /* Test rb_nsearch(). */ 133 search_node = tree_nsearch(tree, node); 134 assert_ptr_eq(search_node, node, 135 "tree_nsearch() returned unexpected node"); 136 137 /* Test rb_psearch(). */ 138 search_node = tree_psearch(tree, node); 139 assert_ptr_eq(search_node, node, 140 "tree_psearch() returned unexpected node"); 141 142 (*i)++; 143 144 return NULL; 145 } 146 147 static unsigned 148 tree_iterate(tree_t *tree) { 149 unsigned i; 150 151 i = 0; 152 tree_iter(tree, NULL, tree_iterate_cb, (void *)&i); 153 154 return i; 155 } 156 157 static unsigned 158 tree_iterate_reverse(tree_t *tree) { 159 unsigned i; 160 161 i = 0; 162 tree_reverse_iter(tree, NULL, tree_iterate_cb, (void *)&i); 163 164 return i; 165 } 166 167 static void 168 node_remove(tree_t *tree, node_t *node, unsigned nnodes) { 169 node_t *search_node; 170 unsigned black_height, imbalances; 171 172 tree_remove(tree, node); 173 174 /* Test rb_nsearch(). */ 175 search_node = tree_nsearch(tree, node); 176 if (search_node != NULL) { 177 assert_u64_ge(search_node->key, node->key, 178 "Key ordering error"); 179 } 180 181 /* Test rb_psearch(). */ 182 search_node = tree_psearch(tree, node); 183 if (search_node != NULL) { 184 assert_u64_le(search_node->key, node->key, 185 "Key ordering error"); 186 } 187 188 node->magic = 0; 189 190 rbtn_black_height(node_t, link, tree, black_height); 191 imbalances = tree_recurse(tree->rbt_root, black_height, 0); 192 assert_u_eq(imbalances, 0, "Tree is unbalanced"); 193 assert_u_eq(tree_iterate(tree), nnodes-1, 194 "Unexpected node iteration count"); 195 assert_u_eq(tree_iterate_reverse(tree), nnodes-1, 196 "Unexpected node iteration count"); 197 } 198 199 static node_t * 200 remove_iterate_cb(tree_t *tree, node_t *node, void *data) { 201 unsigned *nnodes = (unsigned *)data; 202 node_t *ret = tree_next(tree, node); 203 204 node_remove(tree, node, *nnodes); 205 206 return ret; 207 } 208 209 static node_t * 210 remove_reverse_iterate_cb(tree_t *tree, node_t *node, void *data) { 211 unsigned *nnodes = (unsigned *)data; 212 node_t *ret = tree_prev(tree, node); 213 214 node_remove(tree, node, *nnodes); 215 216 return ret; 217 } 218 219 static void 220 destroy_cb(node_t *node, void *data) { 221 unsigned *nnodes = (unsigned *)data; 222 223 assert_u_gt(*nnodes, 0, "Destruction removed too many nodes"); 224 (*nnodes)--; 225 } 226 227 TEST_BEGIN(test_rb_random) { 228 #define NNODES 25 229 #define NBAGS 250 230 #define SEED 42 231 sfmt_t *sfmt; 232 uint64_t bag[NNODES]; 233 tree_t tree; 234 node_t nodes[NNODES]; 235 unsigned i, j, k, black_height, imbalances; 236 237 sfmt = init_gen_rand(SEED); 238 for (i = 0; i < NBAGS; i++) { 239 switch (i) { 240 case 0: 241 /* Insert in order. */ 242 for (j = 0; j < NNODES; j++) { 243 bag[j] = j; 244 } 245 break; 246 case 1: 247 /* Insert in reverse order. */ 248 for (j = 0; j < NNODES; j++) { 249 bag[j] = NNODES - j - 1; 250 } 251 break; 252 default: 253 for (j = 0; j < NNODES; j++) { 254 bag[j] = gen_rand64_range(sfmt, NNODES); 255 } 256 } 257 258 for (j = 1; j <= NNODES; j++) { 259 /* Initialize tree and nodes. */ 260 tree_new(&tree); 261 for (k = 0; k < j; k++) { 262 nodes[k].magic = NODE_MAGIC; 263 nodes[k].key = bag[k]; 264 } 265 266 /* Insert nodes. */ 267 for (k = 0; k < j; k++) { 268 tree_insert(&tree, &nodes[k]); 269 270 rbtn_black_height(node_t, link, &tree, 271 black_height); 272 imbalances = tree_recurse(tree.rbt_root, 273 black_height, 0); 274 assert_u_eq(imbalances, 0, 275 "Tree is unbalanced"); 276 277 assert_u_eq(tree_iterate(&tree), k+1, 278 "Unexpected node iteration count"); 279 assert_u_eq(tree_iterate_reverse(&tree), k+1, 280 "Unexpected node iteration count"); 281 282 assert_false(tree_empty(&tree), 283 "Tree should not be empty"); 284 assert_ptr_not_null(tree_first(&tree), 285 "Tree should not be empty"); 286 assert_ptr_not_null(tree_last(&tree), 287 "Tree should not be empty"); 288 289 tree_next(&tree, &nodes[k]); 290 tree_prev(&tree, &nodes[k]); 291 } 292 293 /* Remove nodes. */ 294 switch (i % 5) { 295 case 0: 296 for (k = 0; k < j; k++) { 297 node_remove(&tree, &nodes[k], j - k); 298 } 299 break; 300 case 1: 301 for (k = j; k > 0; k--) { 302 node_remove(&tree, &nodes[k-1], k); 303 } 304 break; 305 case 2: { 306 node_t *start; 307 unsigned nnodes = j; 308 309 start = NULL; 310 do { 311 start = tree_iter(&tree, start, 312 remove_iterate_cb, (void *)&nnodes); 313 nnodes--; 314 } while (start != NULL); 315 assert_u_eq(nnodes, 0, 316 "Removal terminated early"); 317 break; 318 } case 3: { 319 node_t *start; 320 unsigned nnodes = j; 321 322 start = NULL; 323 do { 324 start = tree_reverse_iter(&tree, start, 325 remove_reverse_iterate_cb, 326 (void *)&nnodes); 327 nnodes--; 328 } while (start != NULL); 329 assert_u_eq(nnodes, 0, 330 "Removal terminated early"); 331 break; 332 } case 4: { 333 unsigned nnodes = j; 334 tree_destroy(&tree, destroy_cb, &nnodes); 335 assert_u_eq(nnodes, 0, 336 "Destruction terminated early"); 337 break; 338 } default: 339 not_reached(); 340 } 341 } 342 } 343 fini_gen_rand(sfmt); 344 #undef NNODES 345 #undef NBAGS 346 #undef SEED 347 } 348 TEST_END 349 350 int 351 main(void) { 352 return test( 353 test_rb_empty, 354 test_rb_random); 355 } 356
