]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/test/test-rbtree.c
2 This file is part of systemd. See COPYING for details.
4 systemd is free software; you can redistribute it and/or modify it
5 under the terms of the GNU Lesser General Public License as published by
6 the Free Software Foundation; either version 2.1 of the License, or
7 (at your option) any later version.
9 systemd is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
14 You should have received a copy of the GNU Lesser General Public License
15 along with systemd; If not, see <http://www.gnu.org/licenses/>.
28 /* verify that all API calls are exported */
29 static void test_api(void) {
31 CRBNode n
= C_RBNODE_INIT(n
);
33 assert(!c_rbnode_is_linked(&n
));
35 /* init, is_linked, add, remove, remove_init */
37 c_rbtree_add(&t
, NULL
, &t
.root
, &n
);
38 assert(c_rbnode_is_linked(&n
));
40 c_rbtree_remove_init(&t
, &n
);
41 assert(!c_rbnode_is_linked(&n
));
43 c_rbtree_add(&t
, NULL
, &t
.root
, &n
);
44 assert(c_rbnode_is_linked(&n
));
46 c_rbtree_remove(&t
, &n
);
47 assert(c_rbnode_is_linked(&n
)); /* @n wasn't touched */
50 assert(!c_rbnode_is_linked(&n
));
52 /* first, last, leftmost, rightmost, next, prev */
54 assert(!c_rbtree_first(&t
));
55 assert(!c_rbtree_last(&t
));
56 assert(&n
== c_rbnode_leftmost(&n
));
57 assert(&n
== c_rbnode_rightmost(&n
));
58 assert(!c_rbnode_next(&n
));
59 assert(!c_rbnode_prev(&n
));
62 /* copied from c-rbtree.c, relies on internal representation */
63 static inline _Bool
c_rbnode_is_red(CRBNode
*n
) {
64 return !((unsigned long)n
->__parent_and_color
& 1UL);
67 /* copied from c-rbtree.c, relies on internal representation */
68 static inline _Bool
c_rbnode_is_black(CRBNode
*n
) {
69 return !!((unsigned long)n
->__parent_and_color
& 1UL);
72 static size_t validate(CRBTree
*t
) {
73 unsigned int i_black
, n_black
;
78 assert(!t
->root
|| c_rbnode_is_black(t
->root
));
80 /* traverse to left-most child, count black nodes */
83 while (n
&& n
->left
) {
84 if (c_rbnode_is_black(n
))
91 * Traverse tree and verify correctness:
92 * 1) A node is either red or black
93 * 2) The root is black
94 * 3) All leaves are black
95 * 4) Every red node must have two black child nodes
96 * 5) Every path to a leaf contains the same number of black nodes
98 * Note that NULL nodes are considered black, which is why we don't
105 /* verify natural order */
109 /* verify consistency */
110 assert(!n
->right
|| c_rbnode_parent(n
->right
) == n
);
111 assert(!n
->left
|| c_rbnode_parent(n
->left
) == n
);
114 if (!c_rbnode_parent(n
))
115 assert(c_rbnode_is_black(n
));
117 if (c_rbnode_is_red(n
)) {
119 assert(!n
->left
|| c_rbnode_is_black(n
->left
));
120 assert(!n
->right
|| c_rbnode_is_black(n
->right
));
123 assert(c_rbnode_is_black(n
));
127 if (!n
->left
&& !n
->right
)
128 assert(i_black
== n_black
);
133 if (c_rbnode_is_black(n
))
138 if (c_rbnode_is_black(n
))
142 while ((p
= c_rbnode_parent(n
)) && n
== p
->right
) {
144 if (c_rbnode_is_black(p
->right
))
149 if (p
&& c_rbnode_is_black(p
->left
))
157 static void insert(CRBTree
*t
, CRBNode
*n
) {
162 assert(!c_rbnode_is_linked(n
));
176 c_rbtree_add(t
, p
, i
, n
);
179 static void shuffle(void **nodes
, size_t n_memb
) {
183 for (i
= 0; i
< n_memb
; ++i
) {
191 /* run some pseudo-random tests on the tree */
192 static void test_shuffle(void) {
198 /* allocate and initialize all nodes */
199 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
200 nodes
[i
] = malloc(sizeof(*nodes
[i
]));
202 c_rbnode_init(nodes
[i
]);
205 /* shuffle nodes and validate *empty* tree */
206 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
210 /* add all nodes and validate after each insertion */
211 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
212 insert(&t
, nodes
[i
]);
217 /* shuffle nodes again */
218 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
220 /* remove all nodes (in different order) and validate on each round */
221 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
222 c_rbtree_remove(&t
, nodes
[i
]);
224 assert(n
== sizeof(nodes
) / sizeof(*nodes
) - i
- 1);
225 c_rbnode_init(nodes
[i
]);
228 /* shuffle nodes and validate *empty* tree again */
229 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
233 /* add all nodes again */
234 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
235 insert(&t
, nodes
[i
]);
240 /* 4 times, remove half of the nodes and add them again */
241 for (j
= 0; j
< 4; ++j
) {
242 /* shuffle nodes again */
243 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
245 /* remove half of the nodes */
246 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
) / 2; ++i
) {
247 c_rbtree_remove(&t
, nodes
[i
]);
249 assert(n
== sizeof(nodes
) / sizeof(*nodes
) - i
- 1);
250 c_rbnode_init(nodes
[i
]);
253 /* shuffle the removed half */
254 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
) / 2);
256 /* add the removed half again */
257 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
) / 2; ++i
) {
258 insert(&t
, nodes
[i
]);
260 assert(n
== sizeof(nodes
) / sizeof(*nodes
) / 2 + i
+ 1);
264 /* shuffle nodes again */
265 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
268 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
269 c_rbtree_remove(&t
, nodes
[i
]);
271 assert(n
== sizeof(nodes
) / sizeof(*nodes
) - i
- 1);
272 c_rbnode_init(nodes
[i
]);
275 /* free nodes again */
276 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
)
285 #define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb)))
287 static int compare(CRBTree
*t
, void *k
, CRBNode
*n
) {
288 unsigned long key
= (unsigned long)k
;
289 Node
*node
= node_from_rb(n
);
291 return (key
< node
->key
) ? -1 : (key
> node
->key
) ? 1 : 0;
294 /* run tests against the c_rbtree_find*() helpers */
295 static void test_map(void) {
301 /* allocate and initialize all nodes */
302 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
303 nodes
[i
] = malloc(sizeof(*nodes
[i
]));
306 c_rbnode_init(&nodes
[i
]->rb
);
310 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
312 /* add all nodes, and verify that each node is linked */
313 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
314 assert(!c_rbnode_is_linked(&nodes
[i
]->rb
));
315 assert(!c_rbtree_find_entry(&t
, compare
, (void *)nodes
[i
]->key
, Node
, rb
));
317 slot
= c_rbtree_find_slot(&t
, compare
, (void *)nodes
[i
]->key
, &p
);
319 c_rbtree_add(&t
, p
, slot
, &nodes
[i
]->rb
);
321 assert(c_rbnode_is_linked(&nodes
[i
]->rb
));
322 assert(nodes
[i
] == c_rbtree_find_entry(&t
, compare
, (void *)nodes
[i
]->key
, Node
, rb
));
325 /* shuffle nodes again */
326 shuffle((void **)nodes
, sizeof(nodes
) / sizeof(*nodes
));
328 /* remove all nodes (in different order) */
329 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
) {
330 assert(c_rbnode_is_linked(&nodes
[i
]->rb
));
331 assert(nodes
[i
] == c_rbtree_find_entry(&t
, compare
, (void *)nodes
[i
]->key
, Node
, rb
));
333 c_rbtree_remove_init(&t
, &nodes
[i
]->rb
);
335 assert(!c_rbnode_is_linked(&nodes
[i
]->rb
));
336 assert(!c_rbtree_find_entry(&t
, compare
, (void *)nodes
[i
]->key
, Node
, rb
));
339 /* free nodes again */
340 for (i
= 0; i
< sizeof(nodes
) / sizeof(*nodes
); ++i
)
344 int main(int argc
, char **argv
) {
347 /* we want stable tests, so use fixed seed */
353 * The tests are pseudo random; run them multiple times, each run will
354 * have different orders and thus different results.
356 for (i
= 0; i
< 4; ++i
) {