glib/tests/tree.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 /*
  19  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  20  * file for a list of people on the GLib Team.  See the ChangeLog
  21  * files for a list of changes.  These files are distributed with
  22  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  23  */
  24
  25 #undef G_DISABLE_ASSERT
  26 #undef G_LOG_DOMAIN
  27
  28 /* We are testing some deprecated APIs here */
  29 #define GLIB_DISABLE_DEPRECATION_WARNINGS
  30
  31 #include <stdio.h>
  32 #include <string.h>
  33 #include "glib.h"
  34
  35
  36 static gint
  37 my_compare (gconstpointer a,
  38             gconstpointer b)
  39 {
  40   const char *cha = a;
  41   const char *chb = b;
  42
  43   return *cha - *chb;
  44 }
  45
  46 static gint
  47 my_compare_with_data (gconstpointer a,
  48                       gconstpointer b,
  49                       gpointer      user_data)
  50 {
  51   const char *cha = a;
  52   const char *chb = b;
  53
  54   /* just check that we got the right data */
  55   g_assert (GPOINTER_TO_INT(user_data) == 123);
  56
  57   return *cha - *chb;
  58 }
  59
  60 static gint
  61 my_search (gconstpointer a,
  62            gconstpointer b)
  63 {
  64   return my_compare (b, a);
  65 }
  66
  67 static gpointer destroyed_key = NULL;
  68 static gpointer destroyed_value = NULL;
  69
  70 static void
  71 my_key_destroy (gpointer key)
  72 {
  73   destroyed_key = key;
  74 }
  75
  76 static void
  77 my_value_destroy (gpointer value)
  78 {
  79   destroyed_value = value;
  80 }
  81
  82 static gint
  83 my_traverse (gpointer key,
  84              gpointer value,
  85              gpointer data)
  86 {
  87   char *ch = key;
  88
  89   g_assert ((*ch) > 0);
  90
  91   if (*ch == 'd')
  92     return TRUE;
  93
  94   return FALSE;
  95 }
  96
  97 char chars[] =
  98   "0123456789"
  99   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 100   "abcdefghijklmnopqrstuvwxyz";
 101
 102 char chars2[] =
 103   "0123456789"
 104   "abcdefghijklmnopqrstuvwxyz";
 105
 106 static gint
 107 check_order (gpointer key,
 108              gpointer value,
 109              gpointer data)
 110 {
 111   char **p = data;
 112   char *ch = key;
 113
 114   g_assert (**p == *ch);
 115
 116   (*p)++;
 117
 118   return FALSE;
 119 }
 120
 121 static void
 122 test_tree_search (void)
 123 {
 124   gint i;
 125   GTree *tree;
 126   gboolean removed;
 127   gchar c;
 128   gchar *p, *d;
 129
 130   tree = g_tree_new_with_data (my_compare_with_data, GINT_TO_POINTER(123));
 131
 132   for (i = 0; chars[i]; i++)
 133     g_tree_insert (tree, &chars[i], &chars[i]);
 134
 135   g_tree_foreach (tree, my_traverse, NULL);
 136
 137   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
 138   g_assert_cmpint (g_tree_height (tree), ==, 6);
 139
 140   p = chars;
 141   g_tree_foreach (tree, check_order, &p);
 142
 143   for (i = 0; i < 26; i++)
 144     {
 145       removed = g_tree_remove (tree, &chars[i + 10]);
 146       g_assert (removed);
 147     }
 148
 149   c = '\0';
 150   removed = g_tree_remove (tree, &c);
 151   g_assert (!removed);
 152
 153   g_tree_foreach (tree, my_traverse, NULL);
 154
 155   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars2));
 156   g_assert_cmpint (g_tree_height (tree), ==, 6);
 157
 158   p = chars2;
 159   g_tree_foreach (tree, check_order, &p);
 160
 161   for (i = 25; i >= 0; i--)
 162     g_tree_insert (tree, &chars[i + 10], &chars[i + 10]);
 163
 164   p = chars;
 165   g_tree_foreach (tree, check_order, &p);
 166
 167   c = '0';
 168   p = g_tree_lookup (tree, &c);
 169   g_assert (p && *p == c);
 170   g_assert (g_tree_lookup_extended (tree, &c, (gpointer *)&d, (gpointer *)&p));
 171   g_assert (c == *d && c == *p);
 172
 173   c = 'A';
 174   p = g_tree_lookup (tree, &c);
 175   g_assert (p && *p == c);
 176
 177   c = 'a';
 178   p = g_tree_lookup (tree, &c);
 179   g_assert (p && *p == c);
 180
 181   c = 'z';
 182   p = g_tree_lookup (tree, &c);
 183   g_assert (p && *p == c);
 184
 185   c = '!';
 186   p = g_tree_lookup (tree, &c);
 187   g_assert (p == NULL);
 188
 189   c = '=';
 190   p = g_tree_lookup (tree, &c);
 191   g_assert (p == NULL);
 192
 193   c = '|';
 194   p = g_tree_lookup (tree, &c);
 195   g_assert (p == NULL);
 196
 197   c = '0';
 198   p = g_tree_search (tree, my_search, &c);
 199   g_assert (p && *p == c);
 200
 201   c = 'A';
 202   p = g_tree_search (tree, my_search, &c);
 203   g_assert (p && *p == c);
 204
 205   c = 'a';
 206   p = g_tree_search (tree, my_search, &c);
 207   g_assert (p &&*p == c);
 208
 209   c = 'z';
 210   p = g_tree_search (tree, my_search, &c);
 211   g_assert (p && *p == c);
 212
 213   c = '!';
 214   p = g_tree_search (tree, my_search, &c);
 215   g_assert (p == NULL);
 216
 217   c = '=';
 218   p = g_tree_search (tree, my_search, &c);
 219   g_assert (p == NULL);
 220
 221   c = '|';
 222   p = g_tree_search (tree, my_search, &c);
 223   g_assert (p == NULL);
 224
 225   g_tree_destroy (tree);
 226 }
 227
 228 static void
 229 test_tree_remove (void)
 230 {
 231   GTree *tree;
 232   char c, d;
 233   gint i;
 234   gboolean removed;
 235   gchar *remove;
 236
 237   tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
 238                           my_key_destroy,
 239                           my_value_destroy);
 240
 241   for (i = 0; chars[i]; i++)
 242     g_tree_insert (tree, &chars[i], &chars[i]);
 243
 244   c = '0';
 245   g_tree_insert (tree, &c, &c);
 246   g_assert (destroyed_key == &c);
 247   g_assert (destroyed_value == &chars[0]);
 248   destroyed_key = NULL;
 249   destroyed_value = NULL;
 250
 251   d = '1';
 252   g_tree_replace (tree, &d, &d);
 253   g_assert (destroyed_key == &chars[1]);
 254   g_assert (destroyed_value == &chars[1]);
 255   destroyed_key = NULL;
 256   destroyed_value = NULL;
 257
 258   c = '2';
 259   removed = g_tree_remove (tree, &c);
 260   g_assert (removed);
 261   g_assert (destroyed_key == &chars[2]);
 262   g_assert (destroyed_value == &chars[2]);
 263   destroyed_key = NULL;
 264   destroyed_value = NULL;
 265
 266   c = '3';
 267   removed = g_tree_steal (tree, &c);
 268   g_assert (removed);
 269   g_assert (destroyed_key == NULL);
 270   g_assert (destroyed_value == NULL);
 271
 272   remove = "omkjigfedba";
 273   for (i = 0; remove[i]; i++)
 274     {
 275       removed = g_tree_remove (tree, &remove[i]);
 276       g_assert (removed);
 277     }
 278
 279   g_tree_destroy (tree);
 280 }
 281
 282 static void
 283 test_tree_destroy (void)
 284 {
 285   GTree *tree;
 286   gint i;
 287
 288   tree = g_tree_new (my_compare);
 289
 290   for (i = 0; chars[i]; i++)
 291     g_tree_insert (tree, &chars[i], &chars[i]);
 292
 293   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
 294
 295   g_tree_ref (tree);
 296   g_tree_destroy (tree);
 297
 298   g_assert_cmpint (g_tree_nnodes (tree), ==, 0);
 299
 300   g_tree_unref (tree);
 301 }
 302
 303 typedef struct {
 304   GString *s;
 305   gint count;
 306 } CallbackData;
 307
 308 static gboolean
 309 traverse_func (gpointer key, gpointer value, gpointer data)
 310 {
 311   CallbackData *d = data;
 312
 313   gchar *c = value;
 314   g_string_append_c (d->s, *c);
 315
 316   d->count--;
 317
 318   if (d->count == 0)
 319     return TRUE;
 320
 321   return FALSE;
 322 }
 323
 324 typedef struct {
 325   GTraverseType  traverse;
 326   gint           limit;
 327   const gchar   *expected;
 328 } TraverseData;
 329
 330 static void
 331 test_tree_traverse (void)
 332 {
 333   GTree *tree;
 334   gint i;
 335   TraverseData orders[] = {
 336     { G_IN_ORDER,   -1, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" },
 337     { G_IN_ORDER,    1, "0" },
 338     { G_IN_ORDER,    2, "01" },
 339     { G_IN_ORDER,    3, "012" },
 340     { G_IN_ORDER,    4, "0123" },
 341     { G_IN_ORDER,    5, "01234" },
 342     { G_IN_ORDER,    6, "012345" },
 343     { G_IN_ORDER,    7, "0123456" },
 344     { G_IN_ORDER,    8, "01234567" },
 345     { G_IN_ORDER,    9, "012345678" },
 346     { G_IN_ORDER,   10, "0123456789" },
 347     { G_IN_ORDER,   11, "0123456789A" },
 348     { G_IN_ORDER,   12, "0123456789AB" },
 349     { G_IN_ORDER,   13, "0123456789ABC" },
 350     { G_IN_ORDER,   14, "0123456789ABCD" },
 351
 352     { G_PRE_ORDER,  -1, "VF73102546B98ADCENJHGILKMRPOQTSUldZXWYbachfegjiktpnmorqsxvuwyz" },
 353     { G_PRE_ORDER,   1, "V" },
 354     { G_PRE_ORDER,   2, "VF" },
 355     { G_PRE_ORDER,   3, "VF7" },
 356     { G_PRE_ORDER,   4, "VF73" },
 357     { G_PRE_ORDER,   5, "VF731" },
 358     { G_PRE_ORDER,   6, "VF7310" },
 359     { G_PRE_ORDER,   7, "VF73102" },
 360     { G_PRE_ORDER,   8, "VF731025" },
 361     { G_PRE_ORDER,   9, "VF7310254" },
 362     { G_PRE_ORDER,  10, "VF73102546" },
 363     { G_PRE_ORDER,  11, "VF73102546B" },
 364     { G_PRE_ORDER,  12, "VF73102546B9" },
 365     { G_PRE_ORDER,  13, "VF73102546B98" },
 366     { G_PRE_ORDER,  14, "VF73102546B98A" },
 367
 368     { G_POST_ORDER, -1, "02146538A9CEDB7GIHKMLJOQPSUTRNFWYXacbZegfikjhdmonqsrpuwvzyxtlV" },
 369     { G_POST_ORDER,  1, "0" },
 370     { G_POST_ORDER,  2, "02" },
 371     { G_POST_ORDER,  3, "021" },
 372     { G_POST_ORDER,  4, "0214" },
 373     { G_POST_ORDER,  5, "02146" },
 374     { G_POST_ORDER,  6, "021465" },
 375     { G_POST_ORDER,  7, "0214653" },
 376     { G_POST_ORDER,  8, "02146538" },
 377     { G_POST_ORDER,  9, "02146538A" },
 378     { G_POST_ORDER, 10, "02146538A9" },
 379     { G_POST_ORDER, 11, "02146538A9C" },
 380     { G_POST_ORDER, 12, "02146538A9CE" },
 381     { G_POST_ORDER, 13, "02146538A9CED" },
 382     { G_POST_ORDER, 14, "02146538A9CEDB" }
 383   };
 384   CallbackData data;
 385
 386   tree = g_tree_new (my_compare);
 387
 388   for (i = 0; chars[i]; i++)
 389     g_tree_insert (tree, &chars[i], &chars[i]);
 390
 391   data.s = g_string_new ("");
 392   for (i = 0; i < G_N_ELEMENTS (orders); i++)
 393     {
 394       g_string_set_size (data.s, 0);
 395       data.count = orders[i].limit;
 396       g_tree_traverse (tree, traverse_func, orders[i].traverse, &data);
 397       g_assert_cmpstr (data.s->str, ==, orders[i].expected);
 398     }
 399
 400   g_tree_unref (tree);
 401   g_string_free (data.s, TRUE);
 402 }
 403
 404 static void
 405 test_tree_insert (void)
 406 {
 407   GTree *tree;
 408   gchar *p;
 409   gint i;
 410   gchar *scrambled;
 411
 412   tree = g_tree_new (my_compare);
 413
 414   for (i = 0; chars[i]; i++)
 415     g_tree_insert (tree, &chars[i], &chars[i]);
 416   p = chars;
 417   g_tree_foreach (tree, check_order, &p);
 418
 419   g_tree_unref (tree);
 420   tree = g_tree_new (my_compare);
 421
 422   for (i = strlen (chars) - 1; i >= 0; i--)
 423     g_tree_insert (tree, &chars[i], &chars[i]);
 424   p = chars;
 425   g_tree_foreach (tree, check_order, &p);
 426
 427   g_tree_unref (tree);
 428   tree = g_tree_new (my_compare);
 429
 430   scrambled = g_strdup (chars);
 431
 432   for (i = 0; i < 30; i++)
 433     {
 434       gchar tmp;
 435       gint a, b;
 436
 437       a = g_random_int_range (0, strlen (scrambled));
 438       b = g_random_int_range (0, strlen (scrambled));
 439       tmp = scrambled[a];
 440       scrambled[a] = scrambled[b];
 441       scrambled[b] = tmp;
 442     }
 443
 444   for (i = 0; scrambled[i]; i++)
 445     g_tree_insert (tree, &scrambled[i], &scrambled[i]);
 446   p = chars;
 447   g_tree_foreach (tree, check_order, &p);
 448
 449   g_free (scrambled);
 450   g_tree_unref (tree);
 451 }
 452
 453 int
 454 main (int argc, char *argv[])
 455 {
 456   g_test_init (&argc, &argv, NULL);
 457
 458   g_test_add_func ("/tree/search", test_tree_search);
 459   g_test_add_func ("/tree/remove", test_tree_remove);
 460   g_test_add_func ("/tree/destroy", test_tree_destroy);
 461   g_test_add_func ("/tree/traverse", test_tree_traverse);
 462   g_test_add_func ("/tree/insert", test_tree_insert);
 463
 464   return g_test_run ();
 465 }
 466