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