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
node_cmp(const node_t * a,const node_t * b)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
TEST_BEGIN(test_rb_empty)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
tree_recurse(node_t * node,unsigned black_height,unsigned black_depth)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 *
tree_iterate_cb(tree_t * tree,node_t * node,void * data)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
tree_iterate(tree_t * tree)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
tree_iterate_reverse(tree_t * tree)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
node_remove(tree_t * tree,node_t * node,unsigned nnodes)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 *
remove_iterate_cb(tree_t * tree,node_t * node,void * data)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 *
remove_reverse_iterate_cb(tree_t * tree,node_t * node,void * data)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
destroy_cb(node_t * node,void * data)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
TEST_BEGIN(test_rb_random)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
main(void)351 main(void) {
352 return test(
353 test_rb_empty,
354 test_rb_random);
355 }
356