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, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /*
  21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 #undef G_DISABLE_ASSERT
  28 #undef G_LOG_DOMAIN
  29
  30 /* We are testing some deprecated APIs here */
  31 #define GLIB_DISABLE_DEPRECATION_WARNINGS
  32
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include "glib.h"
  36
  37
  38 static gint
  39 my_compare (gconstpointer a,
  40             gconstpointer b)
  41 {
  42   const char *cha = a;
  43   const char *chb = b;
  44
  45   return *cha - *chb;
  46 }
  47
  48 static gint
  49 my_compare_with_data (gconstpointer a,
  50                       gconstpointer b,
  51                       gpointer      user_data)
  52 {
  53   const char *cha = a;
  54   const char *chb = b;
  55
  56   /* just check that we got the right data */
  57   g_assert (GPOINTER_TO_INT(user_data) == 123);
  58
  59   return *cha - *chb;
  60 }
  61
  62 static gint
  63 my_search (gconstpointer a,
  64            gconstpointer b)
  65 {
  66   return my_compare (b, a);
  67 }
  68
  69 static gpointer destroyed_key = NULL;
  70 static gpointer destroyed_value = NULL;
  71
  72 static void
  73 my_key_destroy (gpointer key)
  74 {
  75   destroyed_key = key;
  76 }
  77
  78 static void
  79 my_value_destroy (gpointer value)
  80 {
  81   destroyed_value = value;
  82 }
  83
  84 static gint
  85 my_traverse (gpointer key,
  86              gpointer value,
  87              gpointer data)
  88 {
  89   char *ch = key;
  90   g_assert ((*ch) > 0);
  91   return FALSE;
  92 }
  93
  94 char chars[] =
  95   "0123456789"
  96   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  97   "abcdefghijklmnopqrstuvwxyz";
  98
  99 char chars2[] =
 100   "0123456789"
 101   "abcdefghijklmnopqrstuvwxyz";
 102
 103 static gint
 104 check_order (gpointer key,
 105              gpointer value,
 106              gpointer data)
 107 {
 108   char **p = data;
 109   char *ch = key;
 110
 111   g_assert (**p == *ch);
 112
 113   (*p)++;
 114
 115   return FALSE;
 116 }
 117
 118 static void
 119 test_tree_search (void)
 120 {
 121   gint i;
 122   GTree *tree;
 123   gboolean removed;
 124   gchar c;
 125   gchar *p, *d;
 126
 127   tree = g_tree_new_with_data (my_compare_with_data, GINT_TO_POINTER(123));
 128
 129   for (i = 0; chars[i]; i++)
 130     g_tree_insert (tree, &chars[i], &chars[i]);
 131
 132   g_tree_foreach (tree, my_traverse, NULL);
 133
 134   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
 135   g_assert_cmpint (g_tree_height (tree), ==, 6);
 136
 137   p = chars;
 138   g_tree_foreach (tree, check_order, &p);
 139
 140   for (i = 0; i < 26; i++)
 141     {
 142       removed = g_tree_remove (tree, &chars[i + 10]);
 143       g_assert (removed);
 144     }
 145
 146   c = '\0';
 147   removed = g_tree_remove (tree, &c);
 148   g_assert (!removed);
 149
 150   g_tree_foreach (tree, my_traverse, NULL);
 151
 152   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars2));
 153   g_assert_cmpint (g_tree_height (tree), ==, 6);
 154
 155   p = chars2;
 156   g_tree_foreach (tree, check_order, &p);
 157
 158   for (i = 25; i >= 0; i--)
 159     g_tree_insert (tree, &chars[i + 10], &chars[i + 10]);
 160
 161   p = chars;
 162   g_tree_foreach (tree, check_order, &p);
 163
 164   c = '0';
 165   p = g_tree_lookup (tree, &c);
 166   g_assert (p && *p == c);
 167   g_assert (g_tree_lookup_extended (tree, &c, (gpointer *)&d, (gpointer *)&p));
 168   g_assert (c == *d && c == *p);
 169
 170   c = 'A';
 171   p = g_tree_lookup (tree, &c);
 172   g_assert (p && *p == c);
 173
 174   c = 'a';
 175   p = g_tree_lookup (tree, &c);
 176   g_assert (p && *p == c);
 177
 178   c = 'z';
 179   p = g_tree_lookup (tree, &c);
 180   g_assert (p && *p == c);
 181
 182   c = '!';
 183   p = g_tree_lookup (tree, &c);
 184   g_assert (p == NULL);
 185
 186   c = '=';
 187   p = g_tree_lookup (tree, &c);
 188   g_assert (p == NULL);
 189
 190   c = '|';
 191   p = g_tree_lookup (tree, &c);
 192   g_assert (p == NULL);
 193
 194   c = '0';
 195   p = g_tree_search (tree, my_search, &c);
 196   g_assert (p && *p == c);
 197
 198   c = 'A';
 199   p = g_tree_search (tree, my_search, &c);
 200   g_assert (p && *p == c);
 201
 202   c = 'a';
 203   p = g_tree_search (tree, my_search, &c);
 204   g_assert (p &&*p == c);
 205
 206   c = 'z';
 207   p = g_tree_search (tree, my_search, &c);
 208   g_assert (p && *p == c);
 209
 210   c = '!';
 211   p = g_tree_search (tree, my_search, &c);
 212   g_assert (p == NULL);
 213
 214   c = '=';
 215   p = g_tree_search (tree, my_search, &c);
 216   g_assert (p == NULL);
 217
 218   c = '|';
 219   p = g_tree_search (tree, my_search, &c);
 220   g_assert (p == NULL);
 221
 222   g_tree_destroy (tree);
 223 }
 224
 225 static void
 226 test_tree_remove (void)
 227 {
 228   GTree *tree;
 229   char c, d;
 230   gint i;
 231   gboolean removed;
 232   gchar *remove;
 233
 234   tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
 235                           my_key_destroy,
 236                           my_value_destroy);
 237
 238   for (i = 0; chars[i]; i++)
 239     g_tree_insert (tree, &chars[i], &chars[i]);
 240
 241   c = '0';
 242   g_tree_insert (tree, &c, &c);
 243   g_assert (destroyed_key == &c);
 244   g_assert (destroyed_value == &chars[0]);
 245   destroyed_key = NULL;
 246   destroyed_value = NULL;
 247
 248   d = '1';
 249   g_tree_replace (tree, &d, &d);
 250   g_assert (destroyed_key == &chars[1]);
 251   g_assert (destroyed_value == &chars[1]);
 252   destroyed_key = NULL;
 253   destroyed_value = NULL;
 254
 255   c = '2';
 256   removed = g_tree_remove (tree, &c);
 257   g_assert (removed);
 258   g_assert (destroyed_key == &chars[2]);
 259   g_assert (destroyed_value == &chars[2]);
 260   destroyed_key = NULL;
 261   destroyed_value = NULL;
 262
 263   c = '3';
 264   removed = g_tree_steal (tree, &c);
 265   g_assert (removed);
 266   g_assert (destroyed_key == NULL);
 267   g_assert (destroyed_value == NULL);
 268
 269   remove = "omkjigfedba";
 270   for (i = 0; remove[i]; i++)
 271     {
 272       removed = g_tree_remove (tree, &remove[i]);
 273       g_assert (removed);
 274     }
 275
 276   g_tree_destroy (tree);
 277 }
 278
 279 static void
 280 test_tree_destroy (void)
 281 {
 282   GTree *tree;
 283   gint i;
 284
 285   tree = g_tree_new (my_compare);
 286
 287   for (i = 0; chars[i]; i++)
 288     g_tree_insert (tree, &chars[i], &chars[i]);
 289
 290   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
 291
 292   g_tree_ref (tree);
 293   g_tree_destroy (tree);
 294
 295   g_assert_cmpint (g_tree_nnodes (tree), ==, 0);
 296
 297   g_tree_unref (tree);
 298 }
 299
 300 static gboolean
 301 traverse_func (gpointer key, gpointer value, gpointer data)
 302 {
 303   gchar *c = value;
 304   gchar **p = data;
 305
 306   **p = *c;
 307   (*p)++;
 308
 309   return FALSE;
 310 }
 311
 312 static void
 313 test_tree_traverse (void)
 314 {
 315   GTree *tree;
 316   gint i;
 317   gchar *p, *result;
 318
 319   tree = g_tree_new (my_compare);
 320
 321   for (i = 0; chars[i]; i++)
 322     g_tree_insert (tree, &chars[i], &chars[i]);
 323
 324   result = g_new0 (gchar, strlen (chars) + 1);
 325
 326   p = result;
 327   g_tree_traverse (tree, traverse_func, G_IN_ORDER, &p);
 328   g_assert_cmpstr (result, ==, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
 329
 330   p = result;
 331   g_tree_traverse (tree, traverse_func, G_PRE_ORDER, &p);
 332   g_assert_cmpstr (result, ==, "VF73102546B98ADCENJHGILKMRPOQTSUldZXWYbachfegjiktpnmorqsxvuwyz");
 333
 334   p = result;
 335   g_tree_traverse (tree, traverse_func, G_POST_ORDER, &p);
 336   g_assert_cmpstr (result, ==, "02146538A9CEDB7GIHKMLJOQPSUTRNFWYXacbZegfikjhdmonqsrpuwvzyxtlV");
 337
 338   g_tree_unref (tree);
 339   g_free (result);
 340 }
 341
 342 int
 343 main (int argc, char *argv[])
 344 {
 345   g_test_init (&argc, &argv, NULL);
 346
 347   g_test_add_func ("/tree/search", test_tree_search);
 348   g_test_add_func ("/tree/remove", test_tree_remove);
 349   g_test_add_func ("/tree/destroy", test_tree_destroy);
 350   g_test_add_func ("/tree/traverse", test_tree_traverse);
 351
 352   return g_test_run ();
 353 }
 354