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 Lesser 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  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser 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-2000.  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 gboolean
  88 my_hash_equal (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 gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
 164 {
 165   return (strcmp (a, b) == 0);
 166 }
 167
 168
 169
 170 static guint one_hash(gconstpointer key)
 171 {
 172   return 1;
 173 }
 174
 175
 176 static void not_even_foreach (gpointer       key,
 177                                  gpointer       value,
 178                                  gpointer       user_data)
 179 {
 180   const char *_key = (const char *) key;
 181   const char *_value = (const char *) value;
 182   int i;
 183   char val [20];
 184
 185   g_assert (_key != NULL);
 186   g_assert (*_key != 0);
 187   g_assert (_value != NULL);
 188   g_assert (*_value != 0);
 189
 190   i = atoi (_key);
 191   g_assert (atoi (_key) > 0);
 192
 193   sprintf (val, "%d value", i);
 194   g_assert (strcmp (_value, val) == 0);
 195
 196   g_assert ((i % 2) != 0);
 197   g_assert (i != 3);
 198 }
 199
 200
 201 static gboolean remove_even_foreach (gpointer       key,
 202                                  gpointer       value,
 203                                  gpointer       user_data)
 204 {
 205   const char *_key = (const char *) key;
 206   const char *_value = (const char *) value;
 207   int i;
 208   char val [20];
 209
 210   g_assert (_key != NULL);
 211   g_assert (*_key != 0);
 212   g_assert (_value != NULL);
 213   g_assert (*_value != 0);
 214
 215   i = atoi (_key);
 216   g_assert (i > 0);
 217
 218   sprintf (val, "%d value", i);
 219   g_assert (strcmp (_value, val) == 0);
 220
 221   return ((i % 2) == 0) ? TRUE : FALSE;
 222 }
 223
 224
 225
 226
 227 static void second_hash_test (gboolean simple_hash)
 228 {
 229      int       i;
 230      char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 231      GHashTable     *h;
 232      gboolean found;
 233
 234      crcinit ();
 235
 236      h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash,
 237                            second_hash_cmp);
 238      g_assert (h != NULL);
 239      for (i=0; i<20; i++)
 240           {
 241           sprintf (key, "%d", i);
 242           g_assert (atoi (key) == i);
 243
 244           sprintf (val, "%d value", i);
 245           g_assert (atoi (val) == i);
 246
 247           g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 248           }
 249
 250      g_assert (g_hash_table_size (h) == 20);
 251
 252      for (i=0; i<20; i++)
 253           {
 254           sprintf (key, "%d", i);
 255           g_assert (atoi(key) == i);
 256
 257           v = (char *) g_hash_table_lookup (h, key);
 258
 259           g_assert (v != NULL);
 260           g_assert (*v != 0);
 261           g_assert (atoi (v) == i);
 262           }
 263
 264      /**** future test stuff, yet to be debugged
 265      sprintf (key, "%d", 3);
 266      g_hash_table_remove (h, key);
 267      g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 268      g_hash_table_foreach (h, not_even_foreach, NULL);
 269      */
 270
 271      for (i=0; i<20; i++)
 272           {
 273           if (((i % 2) == 0) || (i == 3))
 274             i++;
 275
 276           sprintf (key, "%d", i);
 277           g_assert (atoi(key) == i);
 278
 279           sprintf (val, "%d value", i);
 280           g_assert (atoi (val) == i);
 281
 282           orig_key = orig_val = NULL;
 283           found = g_hash_table_lookup_extended (h, key,
 284                                                 (gpointer)&orig_key,
 285                                                 (gpointer)&orig_val);
 286           g_assert (found);
 287
 288           g_assert (orig_key != NULL);
 289           g_assert (strcmp (key, orig_key) == 0);
 290           g_free (orig_key);
 291
 292           g_assert (orig_val != NULL);
 293           g_assert (strcmp (val, orig_val) == 0);
 294           g_free (orig_val);
 295           }
 296
 297     g_hash_table_destroy (h);
 298 }
 299
 300
 301 static void direct_hash_test (void)
 302 {
 303      gint       i, rc;
 304      GHashTable     *h;
 305
 306      h = g_hash_table_new (NULL, NULL);
 307      g_assert (h != NULL);
 308      for (i=1; i<=20; i++)
 309           {
 310           g_hash_table_insert (h, GINT_TO_POINTER (i),
 311                                GINT_TO_POINTER (i + 42));
 312           }
 313
 314      g_assert (g_hash_table_size (h) == 20);
 315
 316      for (i=1; i<=20; i++)
 317           {
 318           rc = GPOINTER_TO_INT (
 319                 g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 320
 321           g_assert (rc != 0);
 322           g_assert ((rc - 42) == i);
 323           }
 324
 325     g_hash_table_destroy (h);
 326 }
 327
 328
 329
 330 int
 331 main (int   argc,
 332       char *argv[])
 333 {
 334   GHashTable *hash_table;
 335   gint i;
 336
 337   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 338   for (i = 0; i < 10000; i++)
 339     {
 340       array[i] = i;
 341       g_hash_table_insert (hash_table, &array[i], &array[i]);
 342     }
 343   g_hash_table_foreach (hash_table, my_hash_callback, NULL);
 344
 345   for (i = 0; i < 10000; i++)
 346     if (array[i] == 0)
 347       g_assert_not_reached();
 348
 349   for (i = 0; i < 10000; i++)
 350     g_hash_table_remove (hash_table, &array[i]);
 351
 352   for (i = 0; i < 10000; i++)
 353     {
 354       array[i] = i;
 355       g_hash_table_insert (hash_table, &array[i], &array[i]);
 356     }
 357
 358   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 359       g_hash_table_size (hash_table) != 5000)
 360     g_assert_not_reached();
 361
 362   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 363
 364
 365   g_hash_table_destroy (hash_table);
 366
 367   second_hash_test (TRUE);
 368   second_hash_test (FALSE);
 369   direct_hash_test ();
 370
 371   return 0;
 372
 373 }