1 #include "test/jemalloc_test.h"
3 #define rbtn_black_height(a_type, a_field, a_rbt, r_height) do { \
5 for (rbp_bh_t = (a_rbt)->rbt_root, (r_height) = 0; \
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)) { \
14 typedef struct node_s node_t
;
17 #define NODE_MAGIC 0x9823af7e
24 node_cmp(const node_t
*a
, const node_t
*b
) {
27 assert_u32_eq(a
->magic
, NODE_MAGIC
, "Bad magic");
28 assert_u32_eq(b
->magic
, NODE_MAGIC
, "Bad magic");
30 ret
= (a
->key
> b
->key
) - (a
->key
< b
->key
);
33 * Duplicates are not allowed in the tree, so force an
34 * arbitrary ordering for non-identical items with equal keys.
36 ret
= (((uintptr_t)a
) > ((uintptr_t)b
))
37 - (((uintptr_t)a
) < ((uintptr_t)b
));
42 typedef rb_tree(node_t
) tree_t
;
43 rb_gen(static, tree_
, tree_t
, node_t
, link
, node_cmp
);
45 TEST_BEGIN(test_rb_empty
)
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");
57 key
.magic
= NODE_MAGIC
;
58 assert_ptr_null(tree_search(&tree
, &key
), "Unexpected node");
61 key
.magic
= NODE_MAGIC
;
62 assert_ptr_null(tree_nsearch(&tree
, &key
), "Unexpected node");
65 key
.magic
= NODE_MAGIC
;
66 assert_ptr_null(tree_psearch(&tree
, &key
), "Unexpected node");
71 tree_recurse(node_t
*node
, unsigned black_height
, unsigned black_depth
)
80 left_node
= rbtn_left_get(node_t
, link
, node
);
81 right_node
= rbtn_right_get(node_t
, link
, node
);
83 if (!rbtn_red_get(node_t
, link
, node
))
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");
97 assert_u32_eq(node
->magic
, NODE_MAGIC
, "Bad magic");
100 if (left_node
!= NULL
)
101 ret
+= tree_recurse(left_node
, black_height
, black_depth
);
103 ret
+= (black_depth
!= black_height
);
106 if (right_node
!= NULL
)
107 ret
+= tree_recurse(right_node
, black_height
, black_depth
);
109 ret
+= (black_depth
!= black_height
);
115 tree_iterate_cb(tree_t
*tree
, node_t
*node
, void *data
)
117 unsigned *i
= (unsigned *)data
;
120 assert_u32_eq(node
->magic
, NODE_MAGIC
, "Bad magic");
122 /* Test rb_search(). */
123 search_node
= tree_search(tree
, node
);
124 assert_ptr_eq(search_node
, node
,
125 "tree_search() returned unexpected node");
127 /* Test rb_nsearch(). */
128 search_node
= tree_nsearch(tree
, node
);
129 assert_ptr_eq(search_node
, node
,
130 "tree_nsearch() returned unexpected node");
132 /* Test rb_psearch(). */
133 search_node
= tree_psearch(tree
, node
);
134 assert_ptr_eq(search_node
, node
,
135 "tree_psearch() returned unexpected node");
143 tree_iterate(tree_t
*tree
)
148 tree_iter(tree
, NULL
, tree_iterate_cb
, (void *)&i
);
154 tree_iterate_reverse(tree_t
*tree
)
159 tree_reverse_iter(tree
, NULL
, tree_iterate_cb
, (void *)&i
);
165 node_remove(tree_t
*tree
, node_t
*node
, unsigned nnodes
)
168 unsigned black_height
, imbalances
;
170 tree_remove(tree
, node
);
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");
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");
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");
198 remove_iterate_cb(tree_t
*tree
, node_t
*node
, void *data
)
200 unsigned *nnodes
= (unsigned *)data
;
201 node_t
*ret
= tree_next(tree
, node
);
203 node_remove(tree
, node
, *nnodes
);
209 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
);
214 node_remove(tree
, node
, *nnodes
);
220 destroy_cb(node_t
*node
, void *data
)
222 unsigned *nnodes
= (unsigned *)data
;
224 assert_u_gt(*nnodes
, 0, "Destruction removed too many nodes");
228 TEST_BEGIN(test_rb_random
)
234 uint64_t bag
[NNODES
];
236 node_t nodes
[NNODES
];
237 unsigned i
, j
, k
, black_height
, imbalances
;
239 sfmt
= init_gen_rand(SEED
);
240 for (i
= 0; i
< NBAGS
; i
++) {
243 /* Insert in order. */
244 for (j
= 0; j
< NNODES
; j
++)
248 /* Insert in reverse order. */
249 for (j
= 0; j
< NNODES
; j
++)
250 bag
[j
] = NNODES
- j
- 1;
253 for (j
= 0; j
< NNODES
; j
++)
254 bag
[j
] = gen_rand64_range(sfmt
, NNODES
);
257 for (j
= 1; j
<= NNODES
; j
++) {
258 /* Initialize tree and nodes. */
260 for (k
= 0; k
< j
; k
++) {
261 nodes
[k
].magic
= NODE_MAGIC
;
262 nodes
[k
].key
= bag
[k
];
266 for (k
= 0; k
< j
; k
++) {
267 tree_insert(&tree
, &nodes
[k
]);
269 rbtn_black_height(node_t
, link
, &tree
,
271 imbalances
= tree_recurse(tree
.rbt_root
,
273 assert_u_eq(imbalances
, 0,
274 "Tree is unbalanced");
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");
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");
288 tree_next(&tree
, &nodes
[k
]);
289 tree_prev(&tree
, &nodes
[k
]);
295 for (k
= 0; k
< j
; k
++)
296 node_remove(&tree
, &nodes
[k
], j
- k
);
299 for (k
= j
; k
> 0; k
--)
300 node_remove(&tree
, &nodes
[k
-1], k
);
308 start
= tree_iter(&tree
, start
,
309 remove_iterate_cb
, (void *)&nnodes
);
311 } while (start
!= NULL
);
312 assert_u_eq(nnodes
, 0,
313 "Removal terminated early");
321 start
= tree_reverse_iter(&tree
, start
,
322 remove_reverse_iterate_cb
,
325 } while (start
!= NULL
);
326 assert_u_eq(nnodes
, 0,
327 "Removal terminated early");
331 tree_destroy(&tree
, destroy_cb
, &nnodes
);
332 assert_u_eq(nnodes
, 0,
333 "Destruction terminated early");