1 /*
2 * Copyright © 2017 Jason Ekstrand
3 *
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:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
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.
21 */
22
23 #undef NDEBUG
24
25 #include "rb_tree.h"
26
27 #include <assert.h>
28 #include <limits.h>
29
30 /* A list of 100 random numbers from 1 to 100. The number 30 is explicitly
31 * missing from this list.
32 */
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,
44 };
45
46 #define NON_EXISTANT_NUMBER 30
47
48 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
49
50 struct rb_test_node {
51 int key;
52 struct rb_node node;
53 };
54
55 static int
rb_test_node_cmp_void(const struct rb_node * n,const void * v)56 rb_test_node_cmp_void(const struct rb_node *n, const void *v)
57 {
58 struct rb_test_node *tn = rb_node_data(struct rb_test_node, n, node);
59 return *(int *)v - tn->key;
60 }
61
62 static int
rb_test_node_cmp(const struct rb_node * a,const struct rb_node * b)63 rb_test_node_cmp(const struct rb_node *a, const struct rb_node *b)
64 {
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);
67
68 return tb->key - ta->key;
69 }
70
71 static void
validate_tree_order(struct rb_tree * tree,unsigned expected_count)72 validate_tree_order(struct rb_tree *tree, unsigned expected_count)
73 {
74 struct rb_test_node *prev = NULL;
75 int max_val = -1;
76 unsigned count = 0;
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) {
81 max_val = n->key;
82 } else {
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.
86 */
87 assert(prev == NULL || prev < n);
88 }
89
90 prev = n;
91 count++;
92 }
93 assert(count == expected_count);
94
95 prev = NULL;
96 max_val = -1;
97 count = 0;
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) {
102 max_val = n->key;
103 } else {
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.
107 */
108 assert(prev == NULL || prev < n);
109 }
110
111 prev = n;
112 count++;
113 }
114 assert(count == expected_count);
115
116 prev = NULL;
117 int min_val = INT_MAX;
118 count = 0;
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) {
123 min_val = n->key;
124 } else {
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.
128 */
129 assert(prev == NULL || prev > n);
130 }
131
132 prev = n;
133 count++;
134 }
135 assert(count == expected_count);
136
137 prev = NULL;
138 min_val = INT_MAX;
139 count = 0;
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) {
144 min_val = n->key;
145 } else {
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.
149 */
150 assert(prev == NULL || prev > n);
151 }
152
153 prev = n;
154 count++;
155 }
156 assert(count == expected_count);
157 }
158
159 static void
validate_search(struct rb_tree * tree,int first_number,int last_number)160 validate_search(struct rb_tree *tree, int first_number,
161 int last_number)
162 {
163 struct rb_node *n;
164 struct rb_test_node *tn;
165
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]);
171
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]);
176 }
177
178 int missing_key = NON_EXISTANT_NUMBER;
179 n = rb_tree_search(tree, &missing_key, rb_test_node_cmp_void);
180 assert(n == NULL);
181
182 n = rb_tree_search_sloppy(tree, &missing_key, rb_test_node_cmp_void);
183 if (rb_tree_is_empty(tree)) {
184 assert(n == NULL);
185 } else {
186 assert(n != NULL);
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);
191 if (next != NULL) {
192 struct rb_test_node *tnext =
193 rb_node_data(struct rb_test_node, next, node);
194 assert(missing_key < tnext->key);
195 }
196 } else {
197 struct rb_node *prev = rb_node_prev(n);
198 if (prev != NULL) {
199 struct rb_test_node *tprev =
200 rb_node_data(struct rb_test_node, prev, node);
201 assert(missing_key > tprev->key);
202 }
203 }
204 }
205 }
206
207 int
main()208 main()
209 {
210 struct rb_test_node nodes[ARRAY_SIZE(test_numbers)];
211 struct rb_tree tree;
212
213 rb_tree_init(&tree);
214
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);
221 }
222
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);
228 }
229 }
230