tests/hash-test.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  * Copyright (C) 1999 The Free Software Foundation
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21 /*
  22  * Modified by the GLib Team and others 1997-1999.  See the AUTHORS
  23  * file for a list of people on the GLib Team.  See the ChangeLog
  24  * files for a list of changes.  These files are distributed with
  25  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  26  */
  27
  28 #undef G_LOG_DOMAIN
  29
  30 #ifdef HAVE_CONFIG_H
  31 #  include <config.h>
  32 #endif
  33
  34 #if STDC_HEADERS
  35 #include <stdio.h>
  36 #include <string.h>
  37 #include <stdlib.h>
  38 #endif
  39
  40 #include <glib.h>
  41
  42
  43
  44 int array[10000];
  45
  46
  47
  48 static gboolean
  49 my_hash_callback_remove (gpointer key,
  50                          gpointer value,
  51                          gpointer user_data)
  52 {
  53   int *d = value;
  54
  55   if ((*d) % 2)
  56     return TRUE;
  57
  58   return FALSE;
  59 }
  60
  61 static void
  62 my_hash_callback_remove_test (gpointer key,
  63                               gpointer value,
  64                               gpointer user_data)
  65 {
  66   int *d = value;
  67
  68   if ((*d) % 2)
  69     g_assert_not_reached ();
  70 }
  71
  72 static void
  73 my_hash_callback (gpointer key,
  74                   gpointer value,
  75                   gpointer user_data)
  76 {
  77   int *d = value;
  78   *d = 1;
  79 }
  80
  81 static guint
  82 my_hash (gconstpointer key)
  83 {
  84   return (guint) *((const gint*) key);
  85 }
  86
  87 static gint
  88 my_hash_compare (gconstpointer a,
  89                  gconstpointer b)
  90 {
  91   return *((const gint*) a) == *((const gint*) b);
  92 }
  93
  94
  95
  96 /*
  97  * This is a simplified version of the pathalias hashing function.
  98  * Thanks to Steve Belovin and Peter Honeyman
  99  *
 100  * hash a string into a long int.  31 bit crc (from andrew appel).
 101  * the crc table is computed at run time by crcinit() -- we could
 102  * precompute, but it takes 1 clock tick on a 750.
 103  *
 104  * This fast table calculation works only if POLY is a prime polynomial
 105  * in the field of integers modulo 2.  Since the coefficients of a
 106  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 107  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 108  * 31 down to 25 are zero.  Happily, we have candidates, from
 109  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 110  *      x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 111  *      x^31 + x^3 + x^0
 112  *
 113  * We reverse the bits to get:
 114  *      111101010000000000000000000000001 but drop the last 1
 115  *         f   5   0   0   0   0   0   0
 116  *      010010000000000000000000000000001 ditto, for 31-bit crc
 117  *         4   8   0   0   0   0   0   0
 118  */
 119
 120 #define POLY 0x48000000L        /* 31-bit polynomial (avoids sign problems) */
 121
 122 static guint CrcTable[128];
 123
 124 /*
 125  - crcinit - initialize tables for hash function
 126  */
 127 static void crcinit(void)
 128 {
 129         int i, j;
 130         guint sum;
 131
 132         for (i = 0; i < 128; ++i) {
 133                 sum = 0L;
 134                 for (j = 7 - 1; j >= 0; --j)
 135                         if (i & (1 << j))
 136                                 sum ^= POLY >> j;
 137                 CrcTable[i] = sum;
 138         }
 139 }
 140
 141 /*
 142  - hash - Honeyman's nice hashing function
 143  */
 144 static guint honeyman_hash(gconstpointer key)
 145 {
 146         const gchar *name = (const gchar *) key;
 147         gint size;
 148         guint sum = 0;
 149
 150         g_assert (name != NULL);
 151         g_assert (*name != 0);
 152
 153         size = strlen(name);
 154
 155         while (size--) {
 156                 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
 157         }
 158
 159         return(sum);
 160 }
 161
 162
 163 static gint second_hash_cmp (gconstpointer a, gconstpointer b)
 164 {
 165   gint rc = (strcmp (a, b) == 0);
 166
 167   return rc;
 168 }
 169
 170
 171
 172 static guint one_hash(gconstpointer key)
 173 {
 174   return 1;
 175 }
 176
 177
 178 static void not_even_foreach (gpointer       key,
 179                                  gpointer       value,
 180                                  gpointer       user_data)
 181 {
 182   const char *_key = (const char *) key;
 183   const char *_value = (const char *) value;
 184   int i;
 185   char val [20];
 186
 187   g_assert (_key != NULL);
 188   g_assert (*_key != 0);
 189   g_assert (_value != NULL);
 190   g_assert (*_value != 0);
 191
 192   i = atoi (_key);
 193   g_assert (atoi (_key) > 0);
 194
 195   sprintf (val, "%d value", i);
 196   g_assert (strcmp (_value, val) == 0);
 197
 198   g_assert ((i % 2) != 0);
 199   g_assert (i != 3);
 200 }
 201
 202
 203 static gboolean remove_even_foreach (gpointer       key,
 204                                  gpointer       value,
 205                                  gpointer       user_data)
 206 {
 207   const char *_key = (const char *) key;
 208   const char *_value = (const char *) value;
 209   int i;
 210   char val [20];
 211
 212   g_assert (_key != NULL);
 213   g_assert (*_key != 0);
 214   g_assert (_value != NULL);
 215   g_assert (*_value != 0);
 216
 217   i = atoi (_key);
 218   g_assert (i > 0);
 219
 220   sprintf (val, "%d value", i);
 221   g_assert (strcmp (_value, val) == 0);
 222
 223   return ((i % 2) == 0) ? TRUE : FALSE;
 224 }
 225
 226
 227
 228
 229 static void second_hash_test (gboolean simple_hash)
 230 {
 231      int       i;
 232      char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 233      GHashTable     *h;
 234      gboolean found;
 235
 236      crcinit ();
 237
 238      h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash,
 239                            second_hash_cmp);
 240      g_assert (h != NULL);
 241      for (i=0; i<20; i++)
 242           {
 243           sprintf (key, "%d", i);
 244           g_assert (atoi (key) == i);
 245
 246           sprintf (val, "%d value", i);
 247           g_assert (atoi (val) == i);
 248
 249           g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 250           }
 251
 252      g_assert (g_hash_table_size (h) == 20);
 253
 254      for (i=0; i<20; i++)
 255           {
 256           sprintf (key, "%d", i);
 257           g_assert (atoi(key) == i);
 258
 259           v = (char *) g_hash_table_lookup (h, key);
 260
 261           g_assert (v != NULL);
 262           g_assert (*v != 0);
 263           g_assert (atoi (v) == i);
 264           }
 265
 266      /**** future test stuff, yet to be debugged
 267      sprintf (key, "%d", 3);
 268      g_hash_table_remove (h, key);
 269      g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 270      g_hash_table_foreach (h, not_even_foreach, NULL);
 271      */
 272
 273      for (i=0; i<20; i++)
 274           {
 275           if (((i % 2) == 0) || (i == 3))
 276             i++;
 277
 278           sprintf (key, "%d", i);
 279           g_assert (atoi(key) == i);
 280
 281           sprintf (val, "%d value", i);
 282           g_assert (atoi (val) == i);
 283
 284           orig_key = orig_val = NULL;
 285           found = g_hash_table_lookup_extended (h, key,
 286                                                 (gpointer)&orig_key,
 287                                                 (gpointer)&orig_val);
 288           g_assert (found);
 289
 290           g_assert (orig_key != NULL);
 291           g_assert (strcmp (key, orig_key) == 0);
 292           g_free (orig_key);
 293
 294           g_assert (orig_val != NULL);
 295           g_assert (strcmp (val, orig_val) == 0);
 296           g_free (orig_val);
 297           }
 298
 299     g_hash_table_destroy (h);
 300 }
 301
 302
 303 static void direct_hash_test (void)
 304 {
 305      gint       i, rc;
 306      GHashTable     *h;
 307
 308      h = g_hash_table_new (NULL, NULL);
 309      g_assert (h != NULL);
 310      for (i=1; i<=20; i++)
 311           {
 312           g_hash_table_insert (h, GINT_TO_POINTER (i),
 313                                GINT_TO_POINTER (i + 42));
 314           }
 315
 316      g_assert (g_hash_table_size (h) == 20);
 317
 318      for (i=1; i<=20; i++)
 319           {
 320           rc = GPOINTER_TO_INT (
 321                 g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 322
 323           g_assert (rc != 0);
 324           g_assert ((rc - 42) == i);
 325           }
 326
 327     g_hash_table_destroy (h);
 328 }
 329
 330
 331
 332 int
 333 main (int   argc,
 334       char *argv[])
 335 {
 336   GHashTable *hash_table;
 337   gint i;
 338
 339   hash_table = g_hash_table_new (my_hash, my_hash_compare);
 340   for (i = 0; i < 10000; i++)
 341     {
 342       array[i] = i;
 343       g_hash_table_insert (hash_table, &array[i], &array[i]);
 344     }
 345   g_hash_table_foreach (hash_table, my_hash_callback, NULL);
 346
 347   for (i = 0; i < 10000; i++)
 348     if (array[i] == 0)
 349       g_assert_not_reached();
 350
 351   for (i = 0; i < 10000; i++)
 352     g_hash_table_remove (hash_table, &array[i]);
 353
 354   for (i = 0; i < 10000; i++)
 355     {
 356       array[i] = i;
 357       g_hash_table_insert (hash_table, &array[i], &array[i]);
 358     }
 359
 360   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 361       g_hash_table_size (hash_table) != 5000)
 362     g_assert_not_reached();
 363
 364   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 365
 366
 367   g_hash_table_destroy (hash_table);
 368
 369   second_hash_test (TRUE);
 370   second_hash_test (FALSE);
 371   direct_hash_test ();
 372
 373   return 0;
 374
 375 }