glib/tests/hash.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 static void
  48 fill_hash_table_and_array (GHashTable *hash_table)
  49 {
  50   int i;
  51
  52   for (i = 0; i < 10000; i++)
  53     {
  54       array[i] = i;
  55       g_hash_table_insert (hash_table, &array[i], &array[i]);
  56     }
  57 }
  58
  59 static void
  60 init_result_array (int result_array[10000])
  61 {
  62   int i;
  63
  64   for (i = 0; i < 10000; i++)
  65     result_array[i] = -1;
  66 }
  67
  68 static void
  69 verify_result_array (int array[10000])
  70 {
  71   int i;
  72
  73   for (i = 0; i < 10000; i++)
  74     g_assert (array[i] == i);
  75 }
  76
  77 static void
  78 handle_pair (gpointer key, gpointer value, int result_array[10000])
  79 {
  80   int n;
  81
  82   g_assert (key == value);
  83
  84   n = *((int *) value);
  85
  86   g_assert (n >= 0 && n < 10000);
  87   g_assert (result_array[n] == -1);
  88
  89   result_array[n] = n;
  90 }
  91
  92 static gboolean
  93 my_hash_callback_remove (gpointer key,
  94                          gpointer value,
  95                          gpointer user_data)
  96 {
  97   int *d = value;
  98
  99   if ((*d) % 2)
 100     return TRUE;
 101
 102   return FALSE;
 103 }
 104
 105 static void
 106 my_hash_callback_remove_test (gpointer key,
 107                               gpointer value,
 108                               gpointer user_data)
 109 {
 110   int *d = value;
 111
 112   if ((*d) % 2)
 113     g_assert_not_reached ();
 114 }
 115
 116 static void
 117 my_hash_callback (gpointer key,
 118                   gpointer value,
 119                   gpointer user_data)
 120 {
 121   handle_pair (key, value, user_data);
 122 }
 123
 124 static guint
 125 my_hash (gconstpointer key)
 126 {
 127   return (guint) *((const gint*) key);
 128 }
 129
 130 static gboolean
 131 my_hash_equal (gconstpointer a,
 132                gconstpointer b)
 133 {
 134   return *((const gint*) a) == *((const gint*) b);
 135 }
 136
 137
 138
 139 /*
 140  * This is a simplified version of the pathalias hashing function.
 141  * Thanks to Steve Belovin and Peter Honeyman
 142  *
 143  * hash a string into a long int.  31 bit crc (from andrew appel).
 144  * the crc table is computed at run time by crcinit() -- we could
 145  * precompute, but it takes 1 clock tick on a 750.
 146  *
 147  * This fast table calculation works only if POLY is a prime polynomial
 148  * in the field of integers modulo 2.  Since the coefficients of a
 149  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 150  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 151  * 31 down to 25 are zero.  Happily, we have candidates, from
 152  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 153  *      x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 154  *      x^31 + x^3 + x^0
 155  *
 156  * We reverse the bits to get:
 157  *      111101010000000000000000000000001 but drop the last 1
 158  *         f   5   0   0   0   0   0   0
 159  *      010010000000000000000000000000001 ditto, for 31-bit crc
 160  *         4   8   0   0   0   0   0   0
 161  */
 162
 163 #define POLY 0x48000000L        /* 31-bit polynomial (avoids sign problems) */
 164
 165 static guint CrcTable[128];
 166
 167 /*
 168  - crcinit - initialize tables for hash function
 169  */
 170 static void crcinit(void)
 171 {
 172         int i, j;
 173         guint sum;
 174
 175         for (i = 0; i < 128; ++i) {
 176                 sum = 0L;
 177                 for (j = 7 - 1; j >= 0; --j)
 178                         if (i & (1 << j))
 179                                 sum ^= POLY >> j;
 180                 CrcTable[i] = sum;
 181         }
 182 }
 183
 184 /*
 185  - hash - Honeyman's nice hashing function
 186  */
 187 static guint honeyman_hash(gconstpointer key)
 188 {
 189         const gchar *name = (const gchar *) key;
 190         gint size;
 191         guint sum = 0;
 192
 193         g_assert (name != NULL);
 194         g_assert (*name != 0);
 195
 196         size = strlen(name);
 197
 198         while (size--) {
 199                 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
 200         }
 201
 202         return(sum);
 203 }
 204
 205
 206 static gboolean second_hash_cmp (gconstpointer a, gconstpointer b)
 207 {
 208   return (strcmp (a, b) == 0);
 209 }
 210
 211
 212
 213 static guint one_hash(gconstpointer key)
 214 {
 215   return 1;
 216 }
 217
 218
 219 static void not_even_foreach (gpointer       key,
 220                                  gpointer       value,
 221                                  gpointer       user_data)
 222 {
 223   const char *_key = (const char *) key;
 224   const char *_value = (const char *) value;
 225   int i;
 226   char val [20];
 227
 228   g_assert (_key != NULL);
 229   g_assert (*_key != 0);
 230   g_assert (_value != NULL);
 231   g_assert (*_value != 0);
 232
 233   i = atoi (_key);
 234
 235   sprintf (val, "%d value", i);
 236   g_assert (strcmp (_value, val) == 0);
 237
 238   g_assert ((i % 2) != 0);
 239   g_assert (i != 3);
 240 }
 241
 242
 243 static gboolean remove_even_foreach (gpointer       key,
 244                                  gpointer       value,
 245                                  gpointer       user_data)
 246 {
 247   const char *_key = (const char *) key;
 248   const char *_value = (const char *) value;
 249   int i;
 250   char val [20];
 251
 252   g_assert (_key != NULL);
 253   g_assert (*_key != 0);
 254   g_assert (_value != NULL);
 255   g_assert (*_value != 0);
 256
 257   i = atoi (_key);
 258
 259   sprintf (val, "%d value", i);
 260   g_assert (strcmp (_value, val) == 0);
 261
 262   return ((i % 2) == 0) ? TRUE : FALSE;
 263 }
 264
 265
 266
 267
 268 static void second_hash_test (gconstpointer d)
 269 {
 270      gboolean simple_hash = GPOINTER_TO_INT (d);
 271
 272      int       i;
 273      char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 274      GHashTable     *h;
 275      gboolean found;
 276
 277      crcinit ();
 278
 279      h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
 280                                 second_hash_cmp,
 281                                 g_free, g_free);
 282      g_assert (h != NULL);
 283      for (i=0; i<20; i++)
 284           {
 285           sprintf (key, "%d", i);
 286           g_assert (atoi (key) == i);
 287
 288           sprintf (val, "%d value", i);
 289           g_assert (atoi (val) == i);
 290
 291           g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 292           }
 293
 294      g_assert (g_hash_table_size (h) == 20);
 295
 296      for (i=0; i<20; i++)
 297           {
 298           sprintf (key, "%d", i);
 299           g_assert (atoi(key) == i);
 300
 301           v = (char *) g_hash_table_lookup (h, key);
 302
 303           g_assert (v != NULL);
 304           g_assert (*v != 0);
 305           g_assert (atoi (v) == i);
 306           }
 307
 308      sprintf (key, "%d", 3);
 309      g_hash_table_remove (h, key);
 310      g_assert (g_hash_table_size (h) == 19);
 311      g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 312      g_assert (g_hash_table_size (h) == 9);
 313      g_hash_table_foreach (h, not_even_foreach, NULL);
 314
 315      for (i=0; i<20; i++)
 316           {
 317           sprintf (key, "%d", i);
 318           g_assert (atoi(key) == i);
 319
 320           sprintf (val, "%d value", i);
 321           g_assert (atoi (val) == i);
 322
 323           orig_key = orig_val = NULL;
 324           found = g_hash_table_lookup_extended (h, key,
 325                                                 (gpointer)&orig_key,
 326                                                 (gpointer)&orig_val);
 327           if ((i % 2) == 0 || i == 3)
 328             {
 329               g_assert (!found);
 330               continue;
 331             }
 332
 333           g_assert (found);
 334
 335           g_assert (orig_key != NULL);
 336           g_assert (strcmp (key, orig_key) == 0);
 337
 338           g_assert (orig_val != NULL);
 339           g_assert (strcmp (val, orig_val) == 0);
 340           }
 341
 342     g_hash_table_destroy (h);
 343 }
 344
 345 static gboolean find_first     (gpointer key,
 346                                 gpointer value,
 347                                 gpointer user_data)
 348 {
 349   gint *v = value;
 350   gint *test = user_data;
 351   return (*v == *test);
 352 }
 353
 354
 355 static void direct_hash_test (void)
 356 {
 357      gint       i, rc;
 358      GHashTable     *h;
 359
 360      h = g_hash_table_new (NULL, NULL);
 361      g_assert (h != NULL);
 362      for (i=1; i<=20; i++)
 363           {
 364           g_hash_table_insert (h, GINT_TO_POINTER (i),
 365                                GINT_TO_POINTER (i + 42));
 366           }
 367
 368      g_assert (g_hash_table_size (h) == 20);
 369
 370      for (i=1; i<=20; i++)
 371           {
 372           rc = GPOINTER_TO_INT (
 373                 g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 374
 375           g_assert (rc != 0);
 376           g_assert ((rc - 42) == i);
 377           }
 378
 379     g_hash_table_destroy (h);
 380 }
 381
 382 static void int64_hash_test (void)
 383 {
 384      gint       i, rc;
 385      GHashTable     *h;
 386      gint64     values[20];
 387      gint64 key;
 388
 389      h = g_hash_table_new (g_int64_hash, g_int64_equal);
 390      g_assert (h != NULL);
 391      for (i=0; i<20; i++)
 392           {
 393           values[i] = i + 42;
 394           g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 395           }
 396
 397      g_assert (g_hash_table_size (h) == 20);
 398
 399      for (i=0; i<20; i++)
 400           {
 401           key = i + 42;
 402           rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 403
 404           g_assert_cmpint (rc, ==, i + 42);
 405           }
 406
 407     g_hash_table_destroy (h);
 408 }
 409
 410 static void double_hash_test (void)
 411 {
 412      gint       i, rc;
 413      GHashTable     *h;
 414      gdouble values[20];
 415      gdouble key;
 416
 417      h = g_hash_table_new (g_double_hash, g_double_equal);
 418      g_assert (h != NULL);
 419      for (i=0; i<20; i++)
 420           {
 421           values[i] = i + 42.5;
 422           g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 423           }
 424
 425      g_assert (g_hash_table_size (h) == 20);
 426
 427      for (i=0; i<20; i++)
 428           {
 429           key = i + 42.5;
 430           rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 431
 432           g_assert_cmpint (rc, ==, i + 42);
 433           }
 434
 435     g_hash_table_destroy (h);
 436 }
 437
 438 static void
 439 string_free (gpointer data)
 440 {
 441   GString *s = data;
 442
 443   g_string_free (s, TRUE);
 444 }
 445
 446 static void string_hash_test (void)
 447 {
 448      gint       i, rc;
 449      GHashTable     *h;
 450      GString *s;
 451
 452      h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 453      g_assert (h != NULL);
 454      for (i=0; i<20; i++)
 455           {
 456           s = g_string_new ("");
 457           g_string_append_printf (s, "%d", i + 42);
 458           g_string_append_c (s, '.');
 459           g_string_prepend_unichar (s, 0x2301);
 460           g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 461           }
 462
 463      g_assert (g_hash_table_size (h) == 20);
 464
 465      s = g_string_new ("");
 466      for (i=0; i<20; i++)
 467           {
 468           g_string_assign (s, "");
 469           g_string_append_printf (s, "%d", i + 42);
 470           g_string_append_c (s, '.');
 471           g_string_prepend_unichar (s, 0x2301);
 472           rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 473
 474           g_assert_cmpint (rc, ==, i + 42);
 475           }
 476
 477     g_string_free (s, TRUE);
 478     g_hash_table_destroy (h);
 479 }
 480
 481 static void
 482 test_hash_misc (void)
 483 {
 484   GHashTable *hash_table;
 485   gint i;
 486   gint value = 120;
 487   gint *pvalue;
 488   GList *keys, *values;
 489   gint keys_len, values_len;
 490   GHashTableIter iter;
 491   gpointer ikey, ivalue;
 492   int result_array[10000];
 493
 494   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 495   fill_hash_table_and_array (hash_table);
 496   pvalue = g_hash_table_find (hash_table, find_first, &value);
 497   if (!pvalue || *pvalue != value)
 498     g_assert_not_reached();
 499
 500   keys = g_hash_table_get_keys (hash_table);
 501   if (!keys)
 502     g_assert_not_reached ();
 503
 504   values = g_hash_table_get_values (hash_table);
 505   if (!values)
 506     g_assert_not_reached ();
 507
 508   keys_len = g_list_length (keys);
 509   values_len = g_list_length (values);
 510   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 511     g_assert_not_reached ();
 512
 513   g_list_free (keys);
 514   g_list_free (values);
 515
 516   init_result_array (result_array);
 517   g_hash_table_iter_init (&iter, hash_table);
 518   for (i = 0; i < 10000; i++)
 519     {
 520       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 521
 522       handle_pair (ikey, ivalue, result_array);
 523
 524       if (i % 2)
 525         g_hash_table_iter_remove (&iter);
 526     }
 527   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 528   g_assert (g_hash_table_size (hash_table) == 5000);
 529   verify_result_array (result_array);
 530
 531   fill_hash_table_and_array (hash_table);
 532
 533   init_result_array (result_array);
 534   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 535   verify_result_array (result_array);
 536
 537   for (i = 0; i < 10000; i++)
 538     g_hash_table_remove (hash_table, &array[i]);
 539
 540   fill_hash_table_and_array (hash_table);
 541
 542   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 543       g_hash_table_size (hash_table) != 5000)
 544     g_assert_not_reached();
 545
 546   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 547   g_hash_table_destroy (hash_table);
 548 }
 549
 550 static gint destroy_counter;
 551
 552 static void
 553 value_destroy (gpointer value)
 554 {
 555   destroy_counter++;
 556 }
 557
 558 static void
 559 test_hash_ref (void)
 560 {
 561   GHashTable *h;
 562   GHashTableIter iter;
 563   gchar *key, *value;
 564   gboolean abc_seen = FALSE;
 565   gboolean cde_seen = FALSE;
 566   gboolean xyz_seen = FALSE;
 567
 568   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 569   g_hash_table_insert (h, "abc", "ABC");
 570   g_hash_table_insert (h, "cde", "CDE");
 571   g_hash_table_insert (h, "xyz", "XYZ");
 572
 573   g_assert_cmpint (g_hash_table_size (h), == , 3);
 574
 575   g_hash_table_iter_init (&iter, h);
 576
 577   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 578     {
 579       if (strcmp (key, "abc") == 0)
 580         {
 581           g_assert_cmpstr (value, ==, "ABC");
 582           abc_seen = TRUE;
 583           g_hash_table_iter_steal (&iter);
 584         }
 585       else if (strcmp (key, "cde") == 0)
 586         {
 587           g_assert_cmpstr (value, ==, "CDE");
 588           cde_seen = TRUE;
 589         }
 590       else if (strcmp (key, "xyz") == 0)
 591         {
 592           g_assert_cmpstr (value, ==, "XYZ");
 593           xyz_seen = TRUE;
 594         }
 595     }
 596   g_assert_cmpint (destroy_counter, ==, 0);
 597
 598   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 599   g_assert (abc_seen && cde_seen && xyz_seen);
 600   g_assert_cmpint (g_hash_table_size (h), == , 2);
 601
 602   g_hash_table_ref (h);
 603   g_hash_table_destroy (h);
 604   g_assert_cmpint (g_hash_table_size (h), == , 0);
 605   g_assert_cmpint (destroy_counter, ==, 2);
 606   g_hash_table_insert (h, "uvw", "UVW");
 607   g_hash_table_unref (h);
 608   g_assert_cmpint (destroy_counter, ==, 3);
 609 }
 610
 611 static guint
 612 null_safe_str_hash (gconstpointer key)
 613 {
 614   if (key == NULL)
 615     return 0;
 616   else
 617     return g_str_hash (key);
 618 }
 619
 620 static gboolean
 621 null_safe_str_equal (gconstpointer a, gconstpointer b)
 622 {
 623   return g_strcmp0 (a, b) == 0;
 624 }
 625
 626 static void
 627 test_lookup_null_key (void)
 628 {
 629   GHashTable *h;
 630   gboolean res;
 631   gpointer key;
 632   gpointer value;
 633
 634   g_test_bug ("642944");
 635
 636   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 637   g_hash_table_insert (h, "abc", "ABC");
 638
 639   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 640   g_assert (!res);
 641
 642   g_hash_table_insert (h, NULL, "NULL");
 643
 644   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 645   g_assert (res);
 646   g_assert_cmpstr (value, ==, "NULL");
 647
 648   g_hash_table_unref (h);
 649 }
 650
 651 int
 652 main (int argc, char *argv[])
 653 {
 654   g_test_init (&argc, &argv, NULL);
 655
 656   g_test_bug_base ("http://bugzilla.gnome.org/");
 657
 658   g_test_add_func ("/hash/misc", test_hash_misc);
 659   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
 660   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
 661   g_test_add_func ("/hash/direct", direct_hash_test);
 662   g_test_add_func ("/hash/int64", int64_hash_test);
 663   g_test_add_func ("/hash/double", double_hash_test);
 664   g_test_add_func ("/hash/string", string_hash_test);
 665   g_test_add_func ("/hash/ref", test_hash_ref);
 666
 667   /* tests for individual bugs */
 668   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
 669
 670   return g_test_run ();
 671
 672 }