xref: /qemu/tests/unit/test-qtree.c (revision 7bdd67a5) 
1 /*
2  * SPDX-License-Identifier: LGPL-2.1-or-later
3  *
4  * Tests for QTree.
5  * Original source: glib
6  *   https://gitlab.gnome.org/GNOME/glib/-/blob/main/glib/tests/tree.c
7  *   LGPL license.
8  *   Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
9  */
10 
11 #include "qemu/osdep.h"
12 #include "qemu/qtree.h"
13 
14 static 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 
22 static 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     /* just check that we got the right data */
30     g_assert(GPOINTER_TO_INT(user_data) == 123);
31 
32     return *cha - *chb;
33 }
34 
35 static gint my_search(gconstpointer a, gconstpointer b)
36 {
37     return my_compare(b, a);
38 }
39 
40 static gpointer destroyed_key;
41 static gpointer destroyed_value;
42 static guint destroyed_key_count;
43 static guint destroyed_value_count;
44 
45 static void my_key_destroy(gpointer key)
46 {
47     destroyed_key = key;
48     destroyed_key_count++;
49 }
50 
51 static void my_value_destroy(gpointer value)
52 {
53     destroyed_value = value;
54     destroyed_value_count++;
55 }
56 
57 static 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 
70 char chars[] =
71     "0123456789"
72     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
73     "abcdefghijklmnopqrstuvwxyz";
74 
75 char chars2[] =
76     "0123456789"
77     "abcdefghijklmnopqrstuvwxyz";
78 
79 static 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 
91 static 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 
198 static 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 
250 static 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 
273 static 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 
323 int 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