1
2
3
4
5
6
7
8
9
10
11#include "qemu/osdep.h"
12#include "qemu/qtree.h"
13
14static gint my_compare(gconstpointer a, gconstpointer b)
15{
16 const char *cha = a;
17 const char *chb = b;
18
19 return *cha - *chb;
20}
21
22static gint my_compare_with_data(gconstpointer a,
23 gconstpointer b,
24 gpointer user_data)
25{
26 const char *cha = a;
27 const char *chb = b;
28
29
30 g_assert(GPOINTER_TO_INT(user_data) == 123);
31
32 return *cha - *chb;
33}
34
35static gint my_search(gconstpointer a, gconstpointer b)
36{
37 return my_compare(b, a);
38}
39
40static gpointer destroyed_key;
41static gpointer destroyed_value;
42static guint destroyed_key_count;
43static guint destroyed_value_count;
44
45static void my_key_destroy(gpointer key)
46{
47 destroyed_key = key;
48 destroyed_key_count++;
49}
50
51static void my_value_destroy(gpointer value)
52{
53 destroyed_value = value;
54 destroyed_value_count++;
55}
56
57static gint my_traverse(gpointer key, gpointer value, gpointer data)
58{
59 char *ch = key;
60
61 g_assert((*ch) > 0);
62
63 if (*ch == 'd') {
64 return TRUE;
65 }
66
67 return FALSE;
68}
69
70char chars[] =
71 "0123456789"
72 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
73 "abcdefghijklmnopqrstuvwxyz";
74
75char chars2[] =
76 "0123456789"
77 "abcdefghijklmnopqrstuvwxyz";
78
79static gint check_order(gpointer key, gpointer value, gpointer data)
80{
81 char **p = data;
82 char *ch = key;
83
84 g_assert(**p == *ch);
85
86 (*p)++;
87
88 return FALSE;
89}
90
91static void test_tree_search(void)
92{
93 gint i;
94 QTree *tree;
95 gboolean removed;
96 gchar c;
97 gchar *p, *d;
98
99 tree = q_tree_new_with_data(my_compare_with_data, GINT_TO_POINTER(123));
100
101 for (i = 0; chars[i]; i++) {
102 q_tree_insert(tree, &chars[i], &chars[i]);
103 }
104
105 q_tree_foreach(tree, my_traverse, NULL);
106
107 g_assert(q_tree_nnodes(tree) == strlen(chars));
108 g_assert(q_tree_height(tree) == 6);
109
110 p = chars;
111 q_tree_foreach(tree, check_order, &p);
112
113 for (i = 0; i < 26; i++) {
114 removed = q_tree_remove(tree, &chars[i + 10]);
115 g_assert(removed);
116 }
117
118 c = '\0';
119 removed = q_tree_remove(tree, &c);
120 g_assert(!removed);
121
122 q_tree_foreach(tree, my_traverse, NULL);
123
124 g_assert(q_tree_nnodes(tree) == strlen(chars2));
125 g_assert(q_tree_height(tree) == 6);
126
127 p = chars2;
128 q_tree_foreach(tree, check_order, &p);
129
130 for (i = 25; i >= 0; i--) {
131 q_tree_insert(tree, &chars[i + 10], &chars[i + 10]);
132 }
133
134 p = chars;
135 q_tree_foreach(tree, check_order, &p);
136
137 c = '0';
138 p = q_tree_lookup(tree, &c);
139 g_assert(p && *p == c);
140 g_assert(q_tree_lookup_extended(tree, &c, (gpointer *)&d, (gpointer *)&p));
141 g_assert(c == *d && c == *p);
142
143 c = 'A';
144 p = q_tree_lookup(tree, &c);
145 g_assert(p && *p == c);
146
147 c = 'a';
148 p = q_tree_lookup(tree, &c);
149 g_assert(p && *p == c);
150
151 c = 'z';
152 p = q_tree_lookup(tree, &c);
153 g_assert(p && *p == c);
154
155 c = '!';
156 p = q_tree_lookup(tree, &c);
157 g_assert(p == NULL);
158
159 c = '=';
160 p = q_tree_lookup(tree, &c);
161 g_assert(p == NULL);
162
163 c = '|';
164 p = q_tree_lookup(tree, &c);
165 g_assert(p == NULL);
166
167 c = '0';
168 p = q_tree_search(tree, my_search, &c);
169 g_assert(p && *p == c);
170
171 c = 'A';
172 p = q_tree_search(tree, my_search, &c);
173 g_assert(p && *p == c);
174
175 c = 'a';
176 p = q_tree_search(tree, my_search, &c);
177 g_assert(p && *p == c);
178
179 c = 'z';
180 p = q_tree_search(tree, my_search, &c);
181 g_assert(p && *p == c);
182
183 c = '!';
184 p = q_tree_search(tree, my_search, &c);
185 g_assert(p == NULL);
186
187 c = '=';
188 p = q_tree_search(tree, my_search, &c);
189 g_assert(p == NULL);
190
191 c = '|';
192 p = q_tree_search(tree, my_search, &c);
193 g_assert(p == NULL);
194
195 q_tree_destroy(tree);
196}
197
198static void test_tree_remove(void)
199{
200 QTree *tree;
201 char c, d;
202 gint i;
203 gboolean removed;
204
205 tree = q_tree_new_full((GCompareDataFunc)my_compare, NULL,
206 my_key_destroy,
207 my_value_destroy);
208
209 for (i = 0; chars[i]; i++) {
210 q_tree_insert(tree, &chars[i], &chars[i]);
211 }
212
213 c = '0';
214 q_tree_insert(tree, &c, &c);
215 g_assert(destroyed_key == &c);
216 g_assert(destroyed_value == &chars[0]);
217 destroyed_key = NULL;
218 destroyed_value = NULL;
219
220 d = '1';
221 q_tree_replace(tree, &d, &d);
222 g_assert(destroyed_key == &chars[1]);
223 g_assert(destroyed_value == &chars[1]);
224 destroyed_key = NULL;
225 destroyed_value = NULL;
226
227 c = '2';
228 removed = q_tree_remove(tree, &c);
229 g_assert(removed);
230 g_assert(destroyed_key == &chars[2]);
231 g_assert(destroyed_value == &chars[2]);
232 destroyed_key = NULL;
233 destroyed_value = NULL;
234
235 c = '3';
236 removed = q_tree_steal(tree, &c);
237 g_assert(removed);
238 g_assert(destroyed_key == NULL);
239 g_assert(destroyed_value == NULL);
240
241 const gchar *remove = "omkjigfedba";
242 for (i = 0; remove[i]; i++) {
243 removed = q_tree_remove(tree, &remove[i]);
244 g_assert(removed);
245 }
246
247 q_tree_destroy(tree);
248}
249
250static void test_tree_destroy(void)
251{
252 QTree *tree;
253 gint i;
254
255 tree = q_tree_new(my_compare);
256
257 for (i = 0; chars[i]; i++) {
258 q_tree_insert(tree, &chars[i], &chars[i]);
259 }
260
261 g_assert(q_tree_nnodes(tree) == strlen(chars));
262
263 g_test_message("nnodes: %d", q_tree_nnodes(tree));
264 q_tree_ref(tree);
265 q_tree_destroy(tree);
266
267 g_test_message("nnodes: %d", q_tree_nnodes(tree));
268 g_assert(q_tree_nnodes(tree) == 0);
269
270 q_tree_unref(tree);
271}
272
273static void test_tree_insert(void)
274{
275 QTree *tree;
276 gchar *p;
277 gint i;
278 gchar *scrambled;
279
280 tree = q_tree_new(my_compare);
281
282 for (i = 0; chars[i]; i++) {
283 q_tree_insert(tree, &chars[i], &chars[i]);
284 }
285 p = chars;
286 q_tree_foreach(tree, check_order, &p);
287
288 q_tree_unref(tree);
289 tree = q_tree_new(my_compare);
290
291 for (i = strlen(chars) - 1; i >= 0; i--) {
292 q_tree_insert(tree, &chars[i], &chars[i]);
293 }
294 p = chars;
295 q_tree_foreach(tree, check_order, &p);
296
297 q_tree_unref(tree);
298 tree = q_tree_new(my_compare);
299
300 scrambled = g_strdup(chars);
301
302 for (i = 0; i < 30; i++) {
303 gchar tmp;
304 gint a, b;
305
306 a = g_random_int_range(0, strlen(scrambled));
307 b = g_random_int_range(0, strlen(scrambled));
308 tmp = scrambled[a];
309 scrambled[a] = scrambled[b];
310 scrambled[b] = tmp;
311 }
312
313 for (i = 0; scrambled[i]; i++) {
314 q_tree_insert(tree, &scrambled[i], &scrambled[i]);
315 }
316 p = chars;
317 q_tree_foreach(tree, check_order, &p);
318
319 g_free(scrambled);
320 q_tree_unref(tree);
321}
322
323int main(int argc, char *argv[])
324{
325 g_test_init(&argc, &argv, NULL);
326
327 g_test_add_func("/qtree/search", test_tree_search);
328 g_test_add_func("/qtree/remove", test_tree_remove);
329 g_test_add_func("/qtree/destroy", test_tree_destroy);
330 g_test_add_func("/qtree/insert", test_tree_insert);
331
332 return g_test_run();
333}
334
