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