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);