2 * SPDX-License-Identifier: LGPL-2.1-or-later
5 * Original source: glib
6 * https://gitlab.gnome.org/GNOME/glib/-/blob/main/glib/tests/tree.c
8 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
11 #include "qemu/osdep.h"
12 #include "qemu/qtree.h"
14 static gint
my_compare(gconstpointer a
, gconstpointer b
)
22 static gint
my_compare_with_data(gconstpointer a
,
29 /* just check that we got the right data */
30 g_assert(GPOINTER_TO_INT(user_data
) == 123);
35 static gint
my_search(gconstpointer a
, gconstpointer b
)
37 return my_compare(b
, a
);
40 static gpointer destroyed_key
;
41 static gpointer destroyed_value
;
42 static guint destroyed_key_count
;
43 static guint destroyed_value_count
;
45 static void my_key_destroy(gpointer key
)
48 destroyed_key_count
++;
51 static void my_value_destroy(gpointer value
)
53 destroyed_value
= value
;
54 destroyed_value_count
++;
57 static gint
my_traverse(gpointer key
, gpointer value
, gpointer data
)
72 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
73 "abcdefghijklmnopqrstuvwxyz";
77 "abcdefghijklmnopqrstuvwxyz";
79 static gint
check_order(gpointer key
, gpointer value
, gpointer data
)
91 static void test_tree_search(void)
99 tree
= q_tree_new_with_data(my_compare_with_data
, GINT_TO_POINTER(123));
101 for (i
= 0; chars
[i
]; i
++) {
102 q_tree_insert(tree
, &chars
[i
], &chars
[i
]);
105 q_tree_foreach(tree
, my_traverse
, NULL
);
107 g_assert(q_tree_nnodes(tree
) == strlen(chars
));
108 g_assert(q_tree_height(tree
) == 6);
111 q_tree_foreach(tree
, check_order
, &p
);
113 for (i
= 0; i
< 26; i
++) {
114 removed
= q_tree_remove(tree
, &chars
[i
+ 10]);
119 removed
= q_tree_remove(tree
, &c
);
122 q_tree_foreach(tree
, my_traverse
, NULL
);
124 g_assert(q_tree_nnodes(tree
) == strlen(chars2
));
125 g_assert(q_tree_height(tree
) == 6);
128 q_tree_foreach(tree
, check_order
, &p
);
130 for (i
= 25; i
>= 0; i
--) {
131 q_tree_insert(tree
, &chars
[i
+ 10], &chars
[i
+ 10]);
135 q_tree_foreach(tree
, check_order
, &p
);
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
);
144 p
= q_tree_lookup(tree
, &c
);
145 g_assert(p
&& *p
== c
);
148 p
= q_tree_lookup(tree
, &c
);
149 g_assert(p
&& *p
== c
);
152 p
= q_tree_lookup(tree
, &c
);
153 g_assert(p
&& *p
== c
);
156 p
= q_tree_lookup(tree
, &c
);
160 p
= q_tree_lookup(tree
, &c
);
164 p
= q_tree_lookup(tree
, &c
);
168 p
= q_tree_search(tree
, my_search
, &c
);
169 g_assert(p
&& *p
== c
);
172 p
= q_tree_search(tree
, my_search
, &c
);
173 g_assert(p
&& *p
== c
);
176 p
= q_tree_search(tree
, my_search
, &c
);
177 g_assert(p
&& *p
== c
);
180 p
= q_tree_search(tree
, my_search
, &c
);
181 g_assert(p
&& *p
== c
);
184 p
= q_tree_search(tree
, my_search
, &c
);
188 p
= q_tree_search(tree
, my_search
, &c
);
192 p
= q_tree_search(tree
, my_search
, &c
);
195 q_tree_destroy(tree
);
198 static void test_tree_remove(void)
205 tree
= q_tree_new_full((GCompareDataFunc
)my_compare
, NULL
,
209 for (i
= 0; chars
[i
]; i
++) {
210 q_tree_insert(tree
, &chars
[i
], &chars
[i
]);
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
;
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
;
228 removed
= q_tree_remove(tree
, &c
);
230 g_assert(destroyed_key
== &chars
[2]);
231 g_assert(destroyed_value
== &chars
[2]);
232 destroyed_key
= NULL
;
233 destroyed_value
= NULL
;
236 removed
= q_tree_steal(tree
, &c
);
238 g_assert(destroyed_key
== NULL
);
239 g_assert(destroyed_value
== NULL
);
241 const gchar
*remove
= "omkjigfedba";
242 for (i
= 0; remove
[i
]; i
++) {
243 removed
= q_tree_remove(tree
, &remove
[i
]);
247 q_tree_destroy(tree
);
250 static void test_tree_destroy(void)
255 tree
= q_tree_new(my_compare
);
257 for (i
= 0; chars
[i
]; i
++) {
258 q_tree_insert(tree
, &chars
[i
], &chars
[i
]);
261 g_assert(q_tree_nnodes(tree
) == strlen(chars
));
263 g_test_message("nnodes: %d", q_tree_nnodes(tree
));
265 q_tree_destroy(tree
);
267 g_test_message("nnodes: %d", q_tree_nnodes(tree
));
268 g_assert(q_tree_nnodes(tree
) == 0);
273 static void test_tree_insert(void)
280 tree
= q_tree_new(my_compare
);
282 for (i
= 0; chars
[i
]; i
++) {
283 q_tree_insert(tree
, &chars
[i
], &chars
[i
]);
286 q_tree_foreach(tree
, check_order
, &p
);
289 tree
= q_tree_new(my_compare
);
291 for (i
= strlen(chars
) - 1; i
>= 0; i
--) {
292 q_tree_insert(tree
, &chars
[i
], &chars
[i
]);
295 q_tree_foreach(tree
, check_order
, &p
);
298 tree
= q_tree_new(my_compare
);
300 scrambled
= g_strdup(chars
);
302 for (i
= 0; i
< 30; i
++) {
306 a
= g_random_int_range(0, strlen(scrambled
));
307 b
= g_random_int_range(0, strlen(scrambled
));
309 scrambled
[a
] = scrambled
[b
];
313 for (i
= 0; scrambled
[i
]; i
++) {
314 q_tree_insert(tree
, &scrambled
[i
], &scrambled
[i
]);
317 q_tree_foreach(tree
, check_order
, &p
);
323 int main(int argc
, char *argv
[])
325 g_test_init(&argc
, &argv
, NULL
);
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
);