tests/unit/test-qtree.c

   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 }