tests/tree-test.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
 102
 103 int
 104 main (int   argc,
 105       char *argv[])
 106 {
 107   gint i;
 108   GTree *tree;
 109   gboolean removed;
 110   char c, d;
 111   char *p;
 112
 113   tree = g_tree_new (my_compare);
 114
 115   for (i = 0; chars[i]; i++)
 116     g_tree_insert (tree, &chars[i], &chars[i]);
 117
 118   g_tree_foreach (tree, my_traverse, NULL);
 119
 120   g_assert (g_tree_nnodes (tree) == strlen (chars));
 121   g_assert (g_tree_height (tree) == 6);
 122
 123   p = chars;
 124   g_tree_foreach (tree, check_order, &p);
 125
 126   for (i = 0; i < 26; i++)
 127     {
 128       removed = g_tree_remove (tree, &chars[i + 10]);
 129       g_assert (removed);
 130     }
 131
 132   c = '\0';
 133   removed = g_tree_remove (tree, &c);
 134   g_assert (removed == FALSE);
 135
 136   g_tree_foreach (tree, my_traverse, NULL);
 137
 138   g_assert (g_tree_nnodes (tree) == strlen (chars2));
 139   g_assert (g_tree_height (tree) == 6);
 140
 141   p = chars2;
 142   g_tree_foreach (tree, check_order, &p);
 143
 144   for (i = 25; i >= 0; i--)
 145     g_tree_insert (tree, &chars[i + 10], &chars[i + 10]);
 146
 147   p = chars;
 148   g_tree_foreach (tree, check_order, &p);
 149
 150   c = '0';
 151   p = g_tree_lookup (tree, &c);
 152   g_assert (p && *p == c);
 153
 154   c = 'A';
 155   p = g_tree_lookup (tree, &c);
 156   g_assert (p && *p == c);
 157
 158   c = 'a';
 159   p = g_tree_lookup (tree, &c);
 160   g_assert (p && *p == c);
 161
 162   c = 'z';
 163   p = g_tree_lookup (tree, &c);
 164   g_assert (p && *p == c);
 165
 166   c = '!';
 167   p = g_tree_lookup (tree, &c);
 168   g_assert (p == NULL);
 169
 170   c = '=';
 171   p = g_tree_lookup (tree, &c);
 172   g_assert (p == NULL);
 173
 174   c = '|';
 175   p = g_tree_lookup (tree, &c);
 176   g_assert (p == NULL);
 177
 178   c = '0';
 179   p = g_tree_search (tree, my_search, &c);
 180   g_assert (p && *p == c);
 181
 182   c = 'A';
 183   p = g_tree_search (tree, my_search, &c);
 184   g_assert (p && *p == c);
 185
 186   c = 'a';
 187   p = g_tree_search (tree, my_search, &c);
 188   g_assert (p &&*p == c);
 189
 190   c = 'z';
 191   p = g_tree_search (tree, my_search, &c);
 192   g_assert (p && *p == c);
 193
 194   c = '!';
 195   p = g_tree_search (tree, my_search, &c);
 196   g_assert (p == NULL);
 197
 198   c = '=';
 199   p = g_tree_search (tree, my_search, &c);
 200   g_assert (p == NULL);
 201
 202   c = '|';
 203   p = g_tree_search (tree, my_search, &c);
 204   g_assert (p == NULL);
 205
 206
 207   g_tree_destroy (tree);
 208
 209   tree = g_tree_new_full (my_compare, NULL,
 210                           my_key_destroy,
 211                           my_value_destroy);
 212
 213   for (i = 0; chars[i]; i++)
 214     g_tree_insert (tree, &chars[i], &chars[i]);
 215
 216   c = '0';
 217   g_tree_insert (tree, &c, &c);
 218   g_assert (destroyed_key == &c);
 219   g_assert (destroyed_value == &chars[0]);
 220   destroyed_key = NULL;
 221   destroyed_value = NULL;
 222
 223   d = '1';
 224   g_tree_replace (tree, &d, &d);
 225   g_assert (destroyed_key == &chars[1]);
 226   g_assert (destroyed_value == &chars[1]);
 227   destroyed_key = NULL;
 228   destroyed_value = NULL;
 229
 230   c = '2';
 231   removed = g_tree_remove (tree, &c);
 232   g_assert (removed);
 233   g_assert (destroyed_key == &chars[2]);
 234   g_assert (destroyed_value == &chars[2]);
 235   destroyed_key = NULL;
 236   destroyed_value = NULL;
 237
 238   c = '3';
 239   removed = g_tree_steal (tree, &c);
 240   g_assert (removed);
 241   g_assert (destroyed_key == NULL);
 242   g_assert (destroyed_value == NULL);
 243
 244   return 0;
 245 }
 246