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