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