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