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 #include <stdio.h>
  31 #include <string.h>
  32 #include "glib.h"
  33
  34
  35 static gint
  36 my_compare (gconstpointer a,
  37             gconstpointer b)
  38 {
  39   const char *cha = a;
  40   const char *chb = b;
  41
  42   return *cha - *chb;
  43 }
  44
  45 static gint
  46 my_search (gconstpointer a,
  47            gconstpointer b)
  48 {
  49   return my_compare (b, a);
  50 }
  51
  52 static gpointer destroyed_key = NULL;
  53 static gpointer destroyed_value = NULL;
  54
  55 static void
  56 my_key_destroy (gpointer key)
  57 {
  58   destroyed_key = key;
  59 }
  60
  61 static void
  62 my_value_destroy (gpointer value)
  63 {
  64   destroyed_value = value;
  65 }
  66
  67 static gint
  68 my_traverse (gpointer key,
  69              gpointer value,
  70              gpointer data)
  71 {
  72   char *ch = key;
  73   g_assert ((*ch) > 0);
  74   return FALSE;
  75 }
  76
  77 char chars[] =
  78   "0123456789"
  79   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  80   "abcdefghijklmnopqrstuvwxyz";
  81
  82 char chars2[] =
  83   "0123456789"
  84   "abcdefghijklmnopqrstuvwxyz";
  85
  86 static gint
  87 check_order (gpointer key,
  88              gpointer value,
  89              gpointer data)
  90 {
  91   char **p = data;
  92   char *ch = key;
  93
  94   g_assert (**p == *ch);
  95
  96   (*p)++;
  97
  98   return FALSE;
  99 }
 100
 101 static void
 102 test_tree_search (void)
 103 {
 104   gint i;
 105   GTree *tree;
 106   gboolean removed;
 107   gchar c;
 108   gchar *p, *d;
 109
 110   tree = g_tree_new (my_compare);
 111
 112   for (i = 0; chars[i]; i++)
 113     g_tree_insert (tree, &chars[i], &chars[i]);
 114
 115   g_tree_foreach (tree, my_traverse, NULL);
 116
 117   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
 118   g_assert_cmpint (g_tree_height (tree), ==, 6);
 119
 120   p = chars;
 121   g_tree_foreach (tree, check_order, &p);
 122
 123   for (i = 0; i < 26; i++)
 124     {
 125       removed = g_tree_remove (tree, &chars[i + 10]);
 126       g_assert (removed);
 127     }
 128
 129   c = '\0';
 130   removed = g_tree_remove (tree, &c);
 131   g_assert (!removed);
 132
 133   g_tree_foreach (tree, my_traverse, NULL);
 134
 135   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars2));
 136   g_assert_cmpint (g_tree_height (tree), ==, 6);
 137
 138   p = chars2;
 139   g_tree_foreach (tree, check_order, &p);
 140
 141   for (i = 25; i >= 0; i--)
 142     g_tree_insert (tree, &chars[i + 10], &chars[i + 10]);
 143
 144   p = chars;
 145   g_tree_foreach (tree, check_order, &p);
 146
 147   c = '0';
 148   p = g_tree_lookup (tree, &c);
 149   g_assert (p && *p == c);
 150   g_assert (g_tree_lookup_extended (tree, &c, (gpointer *)&d, (gpointer *)&p));
 151   g_assert (c == *d && c == *p);
 152
 153   c = 'A';
 154   p = g_tree_lookup (tree, &c);
 155   g_assert (p && *p == c);
 156
 157   c = 'a';
 158   p = g_tree_lookup (tree, &c);
 159   g_assert (p && *p == c);
 160
 161   c = 'z';
 162   p = g_tree_lookup (tree, &c);
 163   g_assert (p && *p == c);
 164
 165   c = '!';
 166   p = g_tree_lookup (tree, &c);
 167   g_assert (p == NULL);
 168
 169   c = '=';
 170   p = g_tree_lookup (tree, &c);
 171   g_assert (p == NULL);
 172
 173   c = '|';
 174   p = g_tree_lookup (tree, &c);
 175   g_assert (p == NULL);
 176
 177   c = '0';
 178   p = g_tree_search (tree, my_search, &c);
 179   g_assert (p && *p == c);
 180
 181   c = 'A';
 182   p = g_tree_search (tree, my_search, &c);
 183   g_assert (p && *p == c);
 184
 185   c = 'a';
 186   p = g_tree_search (tree, my_search, &c);
 187   g_assert (p &&*p == c);
 188
 189   c = 'z';
 190   p = g_tree_search (tree, my_search, &c);
 191   g_assert (p && *p == c);
 192
 193   c = '!';
 194   p = g_tree_search (tree, my_search, &c);
 195   g_assert (p == NULL);
 196
 197   c = '=';
 198   p = g_tree_search (tree, my_search, &c);
 199   g_assert (p == NULL);
 200
 201   c = '|';
 202   p = g_tree_search (tree, my_search, &c);
 203   g_assert (p == NULL);
 204
 205   g_tree_destroy (tree);
 206 }
 207
 208 static void
 209 test_tree_remove (void)
 210 {
 211   GTree *tree;
 212   char c, d;
 213   gint i;
 214   gboolean removed;
 215
 216   tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
 217                           my_key_destroy,
 218                           my_value_destroy);
 219
 220   for (i = 0; chars[i]; i++)
 221     g_tree_insert (tree, &chars[i], &chars[i]);
 222
 223   c = '0';
 224   g_tree_insert (tree, &c, &c);
 225   g_assert (destroyed_key == &c);
 226   g_assert (destroyed_value == &chars[0]);
 227   destroyed_key = NULL;
 228   destroyed_value = NULL;
 229
 230   d = '1';
 231   g_tree_replace (tree, &d, &d);
 232   g_assert (destroyed_key == &chars[1]);
 233   g_assert (destroyed_value == &chars[1]);
 234   destroyed_key = NULL;
 235   destroyed_value = NULL;
 236
 237   c = '2';
 238   removed = g_tree_remove (tree, &c);
 239   g_assert (removed);
 240   g_assert (destroyed_key == &chars[2]);
 241   g_assert (destroyed_value == &chars[2]);
 242   destroyed_key = NULL;
 243   destroyed_value = NULL;
 244
 245   c = '3';
 246   removed = g_tree_steal (tree, &c);
 247   g_assert (removed);
 248   g_assert (destroyed_key == NULL);
 249   g_assert (destroyed_value == NULL);
 250
 251   g_tree_destroy (tree);
 252 }
 253
 254 static void
 255 test_tree_destroy (void)
 256 {
 257   GTree *tree;
 258   gint i;
 259
 260   tree = g_tree_new (my_compare);
 261
 262   for (i = 0; chars[i]; i++)
 263     g_tree_insert (tree, &chars[i], &chars[i]);
 264
 265   g_assert_cmpint (g_tree_nnodes (tree), ==, strlen (chars));
 266
 267   g_tree_ref (tree);
 268   g_tree_destroy (tree);
 269
 270   g_assert_cmpint (g_tree_nnodes (tree), ==, 0);
 271
 272   g_tree_unref (tree);
 273 }
 274
 275 int
 276 main (int argc, char *argv[])
 277 {
 278   g_test_init (&argc, &argv, NULL);
 279
 280   g_test_add_func ("/tree/search", test_tree_search);
 281   g_test_add_func ("/tree/remove", test_tree_remove);
 282   g_test_add_func ("/tree/destroy", test_tree_destroy);
 283
 284   return g_test_run ();
 285 }
 286