2 * Copyright © 2017 Jason Ekstrand
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
30 /* A list of 100 random numbers from 1 to 100. The number 30 is explicitly
31 * missing from this list.
33 int test_numbers
[] = {
34 26, 12, 35, 15, 48, 11, 39, 23, 40, 18,
35 39, 15, 40, 11, 42, 2, 5, 2, 28, 8,
36 10, 22, 23, 38, 47, 12, 31, 22, 26, 39,
37 9, 42, 32, 18, 36, 8, 32, 29, 9, 3,
38 32, 49, 23, 11, 43, 41, 22, 42, 6, 35,
39 38, 48, 5, 35, 39, 44, 22, 16, 16, 32,
40 31, 50, 48, 5, 50, 8, 2, 32, 27, 34,
41 42, 48, 22, 47, 10, 48, 39, 36, 28, 40,
42 32, 33, 21, 17, 14, 38, 27, 6, 25, 18,
43 32, 38, 19, 22, 20, 47, 50, 41, 29, 50,
46 #define NON_EXISTANT_NUMBER 30
48 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
56 rb_test_node_cmp_void(const struct rb_node
*n
, const void *v
)
58 struct rb_test_node
*tn
= rb_node_data(struct rb_test_node
, n
, node
);
59 return *(int *)v
- tn
->key
;
63 rb_test_node_cmp(const struct rb_node
*a
, const struct rb_node
*b
)
65 struct rb_test_node
*ta
= rb_node_data(struct rb_test_node
, a
, node
);
66 struct rb_test_node
*tb
= rb_node_data(struct rb_test_node
, b
, node
);
68 return tb
->key
- ta
->key
;
72 validate_tree_order(struct rb_tree
*tree
, unsigned expected_count
)
74 struct rb_test_node
*prev
= NULL
;
77 rb_tree_foreach(struct rb_test_node
, n
, tree
, node
) {
78 /* Everything should be in increasing order */
79 assert(n
->key
>= max_val
);
80 if (n
->key
> max_val
) {
83 /* Things should be stable, i.e., given equal keys, they should
84 * show up in the list in order of insertion. We insert them
85 * in the order they are in in the array.
87 assert(prev
== NULL
|| prev
< n
);
93 assert(count
== expected_count
);
98 rb_tree_foreach_safe(struct rb_test_node
, n
, tree
, node
) {
99 /* Everything should be in increasing order */
100 assert(n
->key
>= max_val
);
101 if (n
->key
> max_val
) {
104 /* Things should be stable, i.e., given equal keys, they should
105 * show up in the list in order of insertion. We insert them
106 * in the order they are in in the array.
108 assert(prev
== NULL
|| prev
< n
);
114 assert(count
== expected_count
);
117 int min_val
= INT_MAX
;
119 rb_tree_foreach_rev(struct rb_test_node
, n
, tree
, node
) {
120 /* Everything should be in increasing order */
121 assert(n
->key
<= min_val
);
122 if (n
->key
< min_val
) {
125 /* Things should be stable, i.e., given equal keys, they should
126 * show up in the list in order of insertion. We insert them
127 * in the order they are in in the array.
129 assert(prev
== NULL
|| prev
> n
);
135 assert(count
== expected_count
);
140 rb_tree_foreach_rev_safe(struct rb_test_node
, n
, tree
, node
) {
141 /* Everything should be in increasing order */
142 assert(n
->key
<= min_val
);
143 if (n
->key
< min_val
) {
146 /* Things should be stable, i.e., given equal keys, they should
147 * show up in the list in order of insertion. We insert them
148 * in the order they are in in the array.
150 assert(prev
== NULL
|| prev
> n
);
156 assert(count
== expected_count
);
160 validate_search(struct rb_tree
*tree
, int first_number
,
164 struct rb_test_node
*tn
;
166 /* Search for all of the values */
167 for (int i
= first_number
; i
<= last_number
; i
++) {
168 n
= rb_tree_search(tree
, &test_numbers
[i
], rb_test_node_cmp_void
);
169 tn
= rb_node_data(struct rb_test_node
, n
, node
);
170 assert(tn
->key
== test_numbers
[i
]);
172 n
= rb_tree_search_sloppy(tree
, &test_numbers
[i
],
173 rb_test_node_cmp_void
);
174 tn
= rb_node_data(struct rb_test_node
, n
, node
);
175 assert(tn
->key
== test_numbers
[i
]);
178 int missing_key
= NON_EXISTANT_NUMBER
;
179 n
= rb_tree_search(tree
, &missing_key
, rb_test_node_cmp_void
);
182 n
= rb_tree_search_sloppy(tree
, &missing_key
, rb_test_node_cmp_void
);
183 if (rb_tree_is_empty(tree
)) {
187 tn
= rb_node_data(struct rb_test_node
, n
, node
);
188 assert(tn
->key
!= missing_key
);
189 if (tn
->key
< missing_key
) {
190 struct rb_node
*next
= rb_node_next(n
);
192 struct rb_test_node
*tnext
=
193 rb_node_data(struct rb_test_node
, next
, node
);
194 assert(missing_key
< tnext
->key
);
197 struct rb_node
*prev
= rb_node_prev(n
);
199 struct rb_test_node
*tprev
=
200 rb_node_data(struct rb_test_node
, prev
, node
);
201 assert(missing_key
> tprev
->key
);
210 struct rb_test_node nodes
[ARRAY_SIZE(test_numbers
)];
215 for (unsigned i
= 0; i
< ARRAY_SIZE(test_numbers
); i
++) {
216 nodes
[i
].key
= test_numbers
[i
];
217 rb_tree_insert(&tree
, &nodes
[i
].node
, rb_test_node_cmp
);
218 rb_tree_validate(&tree
);
219 validate_tree_order(&tree
, i
+ 1);
220 validate_search(&tree
, 0, i
);
223 for (unsigned i
= 0; i
< ARRAY_SIZE(test_numbers
); i
++) {
224 rb_tree_remove(&tree
, &nodes
[i
].node
);
225 rb_tree_validate(&tree
);
226 validate_tree_order(&tree
, ARRAY_SIZE(test_numbers
) - i
- 1);
227 validate_search(&tree
, i
+ 1, ARRAY_SIZE(test_numbers
) - 1);