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     {
 177       sum = 0L;
 178       for (j = 7 - 1; j >= 0; --j)
 179         if (i & (1 << j))
 180           sum ^= POLY >> j;
 181       CrcTable[i] = sum;
 182     }
 183 }
 184
 185 /*
 186  - hash - Honeyman's nice hashing function
 187  */
 188 static guint
 189 honeyman_hash (gconstpointer key)
 190 {
 191   const gchar *name = (const gchar *) key;
 192   gint size;
 193   guint sum = 0;
 194
 195   g_assert (name != NULL);
 196   g_assert (*name != 0);
 197
 198   size = strlen (name);
 199
 200   while (size--)
 201     sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
 202
 203   return sum;
 204 }
 205
 206
 207 static gboolean
 208 second_hash_cmp (gconstpointer a, gconstpointer b)
 209 {
 210   return strcmp (a, b) == 0;
 211 }
 212
 213
 214
 215 static guint
 216 one_hash (gconstpointer key)
 217 {
 218   return 1;
 219 }
 220
 221
 222 static void
 223 not_even_foreach (gpointer key,
 224                   gpointer value,
 225                   gpointer user_data)
 226 {
 227   const char *_key = (const char *) key;
 228   const char *_value = (const char *) value;
 229   int i;
 230   char val [20];
 231
 232   g_assert (_key != NULL);
 233   g_assert (*_key != 0);
 234   g_assert (_value != NULL);
 235   g_assert (*_value != 0);
 236
 237   i = atoi (_key);
 238
 239   sprintf (val, "%d value", i);
 240   g_assert (strcmp (_value, val) == 0);
 241
 242   g_assert ((i % 2) != 0);
 243   g_assert (i != 3);
 244 }
 245
 246
 247 static gboolean
 248 remove_even_foreach (gpointer key,
 249                      gpointer value,
 250                      gpointer user_data)
 251 {
 252   const char *_key = (const char *) key;
 253   const char *_value = (const char *) value;
 254   int i;
 255   char val [20];
 256
 257   g_assert (_key != NULL);
 258   g_assert (*_key != 0);
 259   g_assert (_value != NULL);
 260   g_assert (*_value != 0);
 261
 262   i = atoi (_key);
 263
 264   sprintf (val, "%d value", i);
 265   g_assert (strcmp (_value, val) == 0);
 266
 267   return ((i % 2) == 0) ? TRUE : FALSE;
 268 }
 269
 270
 271
 272
 273 static void
 274 second_hash_test (gconstpointer d)
 275 {
 276   gboolean simple_hash = GPOINTER_TO_INT (d);
 277
 278   int       i;
 279   char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 280   GHashTable     *h;
 281   gboolean found;
 282
 283   crcinit ();
 284
 285   h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
 286                              second_hash_cmp,
 287                              g_free, g_free);
 288   g_assert (h != NULL);
 289   for (i = 0; i < 20; i++)
 290     {
 291       sprintf (key, "%d", i);
 292       g_assert (atoi (key) == i);
 293
 294       sprintf (val, "%d value", i);
 295       g_assert (atoi (val) == i);
 296
 297       g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 298     }
 299
 300   g_assert (g_hash_table_size (h) == 20);
 301
 302   for (i = 0; i < 20; i++)
 303     {
 304       sprintf (key, "%d", i);
 305       g_assert (atoi(key) == i);
 306
 307       v = (char *) g_hash_table_lookup (h, key);
 308
 309       g_assert (v != NULL);
 310       g_assert (*v != 0);
 311       g_assert (atoi (v) == i);
 312     }
 313
 314   sprintf (key, "%d", 3);
 315   g_hash_table_remove (h, key);
 316   g_assert (g_hash_table_size (h) == 19);
 317   g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 318   g_assert (g_hash_table_size (h) == 9);
 319   g_hash_table_foreach (h, not_even_foreach, NULL);
 320
 321   for (i = 0; i < 20; i++)
 322     {
 323       sprintf (key, "%d", i);
 324       g_assert (atoi(key) == i);
 325
 326       sprintf (val, "%d value", i);
 327       g_assert (atoi (val) == i);
 328
 329       orig_key = orig_val = NULL;
 330       found = g_hash_table_lookup_extended (h, key,
 331                                             (gpointer)&orig_key,
 332                                             (gpointer)&orig_val);
 333       if ((i % 2) == 0 || i == 3)
 334         {
 335           g_assert (!found);
 336           continue;
 337         }
 338
 339       g_assert (found);
 340
 341       g_assert (orig_key != NULL);
 342       g_assert (strcmp (key, orig_key) == 0);
 343
 344       g_assert (orig_val != NULL);
 345       g_assert (strcmp (val, orig_val) == 0);
 346     }
 347
 348   g_hash_table_destroy (h);
 349 }
 350
 351 static gboolean
 352 find_first (gpointer key,
 353             gpointer value,
 354             gpointer user_data)
 355 {
 356   gint *v = value;
 357   gint *test = user_data;
 358   return (*v == *test);
 359 }
 360
 361
 362 static void
 363 direct_hash_test (void)
 364 {
 365   gint       i, rc;
 366   GHashTable     *h;
 367
 368   h = g_hash_table_new (NULL, NULL);
 369   g_assert (h != NULL);
 370   for (i = 1; i <= 20; i++)
 371     g_hash_table_insert (h, GINT_TO_POINTER (i),
 372                          GINT_TO_POINTER (i + 42));
 373
 374   g_assert (g_hash_table_size (h) == 20);
 375
 376   for (i = 1; i <= 20; i++)
 377     {
 378       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 379
 380       g_assert (rc != 0);
 381       g_assert ((rc - 42) == i);
 382     }
 383
 384   g_hash_table_destroy (h);
 385 }
 386
 387 static void
 388 int64_hash_test (void)
 389 {
 390   gint       i, rc;
 391   GHashTable     *h;
 392   gint64     values[20];
 393   gint64 key;
 394
 395   h = g_hash_table_new (g_int64_hash, g_int64_equal);
 396   g_assert (h != NULL);
 397   for (i = 0; i < 20; i++)
 398     {
 399       values[i] = i + 42;
 400       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 401     }
 402
 403   g_assert (g_hash_table_size (h) == 20);
 404
 405   for (i = 0; i < 20; i++)
 406     {
 407       key = i + 42;
 408       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 409
 410       g_assert_cmpint (rc, ==, i + 42);
 411     }
 412
 413   g_hash_table_destroy (h);
 414 }
 415
 416 static void
 417 double_hash_test (void)
 418 {
 419   gint       i, rc;
 420   GHashTable     *h;
 421   gdouble values[20];
 422   gdouble key;
 423
 424   h = g_hash_table_new (g_double_hash, g_double_equal);
 425   g_assert (h != NULL);
 426   for (i = 0; i < 20; i++)
 427     {
 428       values[i] = i + 42.5;
 429       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 430     }
 431
 432   g_assert (g_hash_table_size (h) == 20);
 433
 434   for (i = 0; i < 20; i++)
 435     {
 436       key = i + 42.5;
 437       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 438
 439       g_assert_cmpint (rc, ==, i + 42);
 440     }
 441
 442   g_hash_table_destroy (h);
 443 }
 444
 445 static void
 446 string_free (gpointer data)
 447 {
 448   GString *s = data;
 449
 450   g_string_free (s, TRUE);
 451 }
 452
 453 static void
 454 string_hash_test (void)
 455 {
 456   gint       i, rc;
 457   GHashTable     *h;
 458   GString *s;
 459
 460   h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 461   g_assert (h != NULL);
 462   for (i = 0; i < 20; i++)
 463     {
 464       s = g_string_new ("");
 465       g_string_append_printf (s, "%d", i + 42);
 466       g_string_append_c (s, '.');
 467       g_string_prepend_unichar (s, 0x2301);
 468       g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 469     }
 470
 471   g_assert (g_hash_table_size (h) == 20);
 472
 473   s = g_string_new ("");
 474   for (i = 0; i < 20; i++)
 475     {
 476       g_string_assign (s, "");
 477       g_string_append_printf (s, "%d", i + 42);
 478       g_string_append_c (s, '.');
 479       g_string_prepend_unichar (s, 0x2301);
 480       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 481
 482       g_assert_cmpint (rc, ==, i + 42);
 483     }
 484
 485   g_string_free (s, TRUE);
 486   g_hash_table_destroy (h);
 487 }
 488
 489 static void
 490 set_check (gpointer key,
 491            gpointer value,
 492            gpointer user_data)
 493 {
 494   int *pi = user_data;
 495   if (key != value)
 496     g_assert_not_reached ();
 497
 498   g_assert_cmpint (atoi (key) % 7, ==, 2);
 499
 500   (*pi)++;
 501 }
 502
 503 static void
 504 set_hash_test (void)
 505 {
 506   GHashTable *hash_table =
 507     g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 508   int i;
 509
 510   for (i = 2; i < 5000; i += 7)
 511     {
 512       char *s = g_strdup_printf ("%d", i);
 513       g_hash_table_insert (hash_table, s, s);
 514     }
 515
 516   i = 0;
 517   g_hash_table_foreach (hash_table, set_check, &i);
 518   g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
 519
 520   /* this will cause the hash table to loose set nature */
 521   g_hash_table_insert (hash_table, g_strdup ("a"), "b");
 522
 523   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 524   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 525
 526   g_hash_table_destroy (hash_table);
 527 }
 528
 529
 530 static void
 531 test_hash_misc (void)
 532 {
 533   GHashTable *hash_table;
 534   gint i;
 535   gint value = 120;
 536   gint *pvalue;
 537   GList *keys, *values;
 538   gint keys_len, values_len;
 539   GHashTableIter iter;
 540   gpointer ikey, ivalue;
 541   int result_array[10000];
 542   int n_array[1];
 543
 544   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 545   fill_hash_table_and_array (hash_table);
 546   pvalue = g_hash_table_find (hash_table, find_first, &value);
 547   if (!pvalue || *pvalue != value)
 548     g_assert_not_reached();
 549
 550   keys = g_hash_table_get_keys (hash_table);
 551   if (!keys)
 552     g_assert_not_reached ();
 553
 554   values = g_hash_table_get_values (hash_table);
 555   if (!values)
 556     g_assert_not_reached ();
 557
 558   keys_len = g_list_length (keys);
 559   values_len = g_list_length (values);
 560   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 561     g_assert_not_reached ();
 562
 563   g_list_free (keys);
 564   g_list_free (values);
 565
 566   init_result_array (result_array);
 567   g_hash_table_iter_init (&iter, hash_table);
 568   for (i = 0; i < 10000; i++)
 569     {
 570       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 571
 572       handle_pair (ikey, ivalue, result_array);
 573
 574       if (i % 2)
 575         g_hash_table_iter_remove (&iter);
 576     }
 577   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 578   g_assert (g_hash_table_size (hash_table) == 5000);
 579   verify_result_array (result_array);
 580
 581   fill_hash_table_and_array (hash_table);
 582
 583   init_result_array (result_array);
 584   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 585   verify_result_array (result_array);
 586
 587   for (i = 0; i < 10000; i++)
 588     g_hash_table_remove (hash_table, &array[i]);
 589
 590   fill_hash_table_and_array (hash_table);
 591
 592   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 593       g_hash_table_size (hash_table) != 5000)
 594     g_assert_not_reached();
 595
 596   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 597   g_hash_table_destroy (hash_table);
 598
 599   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 600   fill_hash_table_and_array (hash_table);
 601
 602   n_array[0] = 1;
 603
 604   g_hash_table_iter_init (&iter, hash_table);
 605   for (i = 0; i < 10000; i++)
 606     {
 607       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 608       g_hash_table_iter_replace (&iter, &n_array[0]);
 609     }
 610
 611   g_hash_table_iter_init (&iter, hash_table);
 612   for (i = 0; i < 10000; i++)
 613     {
 614       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 615
 616       g_assert (ivalue == &n_array[0]);
 617     }
 618
 619   g_hash_table_destroy (hash_table);
 620 }
 621
 622 static gint destroy_counter;
 623
 624 static void
 625 value_destroy (gpointer value)
 626 {
 627   destroy_counter++;
 628 }
 629
 630 static void
 631 test_hash_ref (void)
 632 {
 633   GHashTable *h;
 634   GHashTableIter iter;
 635   gchar *key, *value;
 636   gboolean abc_seen = FALSE;
 637   gboolean cde_seen = FALSE;
 638   gboolean xyz_seen = FALSE;
 639
 640   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 641   g_hash_table_insert (h, "abc", "ABC");
 642   g_hash_table_insert (h, "cde", "CDE");
 643   g_hash_table_insert (h, "xyz", "XYZ");
 644
 645   g_assert_cmpint (g_hash_table_size (h), == , 3);
 646
 647   g_hash_table_iter_init (&iter, h);
 648
 649   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 650     {
 651       if (strcmp (key, "abc") == 0)
 652         {
 653           g_assert_cmpstr (value, ==, "ABC");
 654           abc_seen = TRUE;
 655           g_hash_table_iter_steal (&iter);
 656         }
 657       else if (strcmp (key, "cde") == 0)
 658         {
 659           g_assert_cmpstr (value, ==, "CDE");
 660           cde_seen = TRUE;
 661         }
 662       else if (strcmp (key, "xyz") == 0)
 663         {
 664           g_assert_cmpstr (value, ==, "XYZ");
 665           xyz_seen = TRUE;
 666         }
 667     }
 668   g_assert_cmpint (destroy_counter, ==, 0);
 669
 670   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 671   g_assert (abc_seen && cde_seen && xyz_seen);
 672   g_assert_cmpint (g_hash_table_size (h), == , 2);
 673
 674   g_hash_table_ref (h);
 675   g_hash_table_destroy (h);
 676   g_assert_cmpint (g_hash_table_size (h), == , 0);
 677   g_assert_cmpint (destroy_counter, ==, 2);
 678   g_hash_table_insert (h, "uvw", "UVW");
 679   g_hash_table_unref (h);
 680   g_assert_cmpint (destroy_counter, ==, 3);
 681 }
 682
 683 static guint
 684 null_safe_str_hash (gconstpointer key)
 685 {
 686   if (key == NULL)
 687     return 0;
 688   else
 689     return g_str_hash (key);
 690 }
 691
 692 static gboolean
 693 null_safe_str_equal (gconstpointer a, gconstpointer b)
 694 {
 695   return g_strcmp0 (a, b) == 0;
 696 }
 697
 698 static void
 699 test_lookup_null_key (void)
 700 {
 701   GHashTable *h;
 702   gboolean res;
 703   gpointer key;
 704   gpointer value;
 705
 706   g_test_bug ("642944");
 707
 708   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 709   g_hash_table_insert (h, "abc", "ABC");
 710
 711   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 712   g_assert (!res);
 713
 714   g_hash_table_insert (h, NULL, "NULL");
 715
 716   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 717   g_assert (res);
 718   g_assert_cmpstr (value, ==, "NULL");
 719
 720   g_hash_table_unref (h);
 721 }
 722
 723 static gint destroy_key_counter;
 724
 725 static void
 726 key_destroy (gpointer key)
 727 {
 728   destroy_key_counter++;
 729 }
 730
 731 static void
 732 test_remove_all (void)
 733 {
 734   GHashTable *h;
 735   gboolean res;
 736
 737   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 738   g_hash_table_insert (h, "abc", "ABC");
 739   g_hash_table_insert (h, "cde", "CDE");
 740   g_hash_table_insert (h, "xyz", "XYZ");
 741
 742   destroy_counter = 0;
 743   destroy_key_counter = 0;
 744
 745   g_hash_table_steal_all (h);
 746   g_assert_cmpint (destroy_counter, ==, 0);
 747   g_assert_cmpint (destroy_key_counter, ==, 0);
 748
 749   g_hash_table_insert (h, "abc", "ABC");
 750   g_hash_table_insert (h, "cde", "CDE");
 751   g_hash_table_insert (h, "xyz", "XYZ");
 752
 753   res = g_hash_table_steal (h, "nosuchkey");
 754   g_assert (!res);
 755   g_assert_cmpint (destroy_counter, ==, 0);
 756   g_assert_cmpint (destroy_key_counter, ==, 0);
 757
 758   res = g_hash_table_steal (h, "xyz");
 759   g_assert (res);
 760   g_assert_cmpint (destroy_counter, ==, 0);
 761   g_assert_cmpint (destroy_key_counter, ==, 0);
 762
 763   g_hash_table_remove_all (h);
 764   g_assert_cmpint (destroy_counter, ==, 2);
 765   g_assert_cmpint (destroy_key_counter, ==, 2);
 766
 767   g_hash_table_unref (h);
 768 }
 769
 770 typedef struct {
 771   gint ref_count;
 772   const gchar *key;
 773 } RefCountedKey;
 774
 775 static guint
 776 hash_func (gconstpointer key)
 777 {
 778   const RefCountedKey *rkey = key;
 779
 780   return g_str_hash (rkey->key);
 781 }
 782
 783 static gboolean
 784 eq_func (gconstpointer a, gconstpointer b)
 785 {
 786   const RefCountedKey *aa = a;
 787   const RefCountedKey *bb = b;
 788
 789   return g_strcmp0 (aa->key, bb->key) == 0;
 790 }
 791
 792 static void
 793 key_unref (gpointer data)
 794 {
 795   RefCountedKey *key = data;
 796
 797   g_assert (key->ref_count > 0);
 798
 799   key->ref_count -= 1;
 800
 801   if (key->ref_count == 0)
 802     g_free (key);
 803 }
 804
 805 static RefCountedKey *
 806 key_ref (RefCountedKey *key)
 807 {
 808   key->ref_count += 1;
 809
 810   return key;
 811 }
 812
 813 static RefCountedKey *
 814 key_new (const gchar *key)
 815 {
 816   RefCountedKey *rkey;
 817
 818   rkey = g_new (RefCountedKey, 1);
 819
 820   rkey->ref_count = 1;
 821   rkey->key = key;
 822
 823   return rkey;
 824 }
 825
 826 static void
 827 set_ref_hash_test (void)
 828 {
 829   GHashTable *h;
 830   RefCountedKey *key1;
 831   RefCountedKey *key2;
 832
 833   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 834
 835   key1 = key_new ("a");
 836   key2 = key_new ("a");
 837
 838   g_assert_cmpint (key1->ref_count, ==, 1);
 839   g_assert_cmpint (key2->ref_count, ==, 1);
 840
 841   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 842
 843   g_assert_cmpint (key1->ref_count, ==, 3);
 844   g_assert_cmpint (key2->ref_count, ==, 1);
 845
 846   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 847
 848   g_assert_cmpint (key1->ref_count, ==, 1);
 849   g_assert_cmpint (key2->ref_count, ==, 3);
 850
 851   g_hash_table_remove (h, key1);
 852
 853   g_assert_cmpint (key1->ref_count, ==, 1);
 854   g_assert_cmpint (key2->ref_count, ==, 1);
 855
 856   g_hash_table_unref (h);
 857
 858   key_unref (key1);
 859   key_unref (key2);
 860 }
 861
 862 GHashTable *h;
 863
 864 static void
 865 value_destroy_insert (gpointer value)
 866 {
 867   g_hash_table_remove_all (h);
 868 }
 869
 870 static void
 871 test_destroy_modify (void)
 872 {
 873   g_test_bug ("650459");
 874
 875   h = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, value_destroy_insert);
 876
 877   g_hash_table_insert (h, g_strdup ("a"), g_strdup ("b"));
 878   g_hash_table_insert (h, g_strdup ("c"), g_strdup ("d"));
 879   g_hash_table_insert (h, g_strdup ("e"), g_strdup ("f"));
 880   g_hash_table_insert (h, g_strdup ("g"), g_strdup ("h"));
 881   g_hash_table_insert (h, g_strdup ("h"), g_strdup ("k"));
 882   g_hash_table_insert (h, g_strdup ("a"), g_strdup ("c"));
 883
 884   g_hash_table_remove (h, "c");
 885   g_hash_table_remove (h, "e");
 886
 887   g_hash_table_unref (h);
 888 }
 889
 890 static gboolean
 891 find_str (gpointer key, gpointer value, gpointer data)
 892 {
 893   return g_str_equal (key, data);
 894 }
 895
 896 static void
 897 test_find (void)
 898 {
 899   GHashTable *hash;
 900   const gchar *value;
 901
 902   hash = g_hash_table_new (g_str_hash, g_str_equal);
 903
 904   g_hash_table_insert (hash, "a", "A");
 905   g_hash_table_insert (hash, "b", "B");
 906   g_hash_table_insert (hash, "c", "C");
 907   g_hash_table_insert (hash, "d", "D");
 908   g_hash_table_insert (hash, "e", "E");
 909   g_hash_table_insert (hash, "f", "F");
 910
 911   value = g_hash_table_find (hash, find_str, "a");
 912   g_assert_cmpstr (value, ==, "A");
 913
 914   value = g_hash_table_find (hash, find_str, "b");
 915   g_assert_cmpstr (value, ==, "B");
 916
 917   value = g_hash_table_find (hash, find_str, "c");
 918   g_assert_cmpstr (value, ==, "C");
 919
 920   value = g_hash_table_find (hash, find_str, "d");
 921   g_assert_cmpstr (value, ==, "D");
 922
 923   value = g_hash_table_find (hash, find_str, "e");
 924   g_assert_cmpstr (value, ==, "E");
 925
 926   value = g_hash_table_find (hash, find_str, "f");
 927   g_assert_cmpstr (value, ==, "F");
 928
 929   value = g_hash_table_find (hash, find_str, "0");
 930   g_assert (value == NULL);
 931
 932   g_hash_table_unref (hash);
 933 }
 934
 935 gboolean seen_key[6];
 936
 937 static void
 938 foreach_func (gpointer key, gpointer value, gpointer data)
 939 {
 940   seen_key[((char*)key)[0] - 'a'] = TRUE;
 941 }
 942
 943 static void
 944 test_foreach (void)
 945 {
 946   GHashTable *hash;
 947   gint i;
 948
 949   hash = g_hash_table_new (g_str_hash, g_str_equal);
 950
 951   g_hash_table_insert (hash, "a", "A");
 952   g_hash_table_insert (hash, "b", "B");
 953   g_hash_table_insert (hash, "c", "C");
 954   g_hash_table_insert (hash, "d", "D");
 955   g_hash_table_insert (hash, "e", "E");
 956   g_hash_table_insert (hash, "f", "F");
 957
 958   for (i = 0; i < 6; i++)
 959     seen_key[i] = FALSE;
 960
 961   g_hash_table_foreach (hash, foreach_func, NULL);
 962
 963   for (i = 0; i < 6; i++)
 964     g_assert (seen_key[i]);
 965
 966   g_hash_table_unref (hash);
 967 }
 968
 969 struct _GHashTable
 970 {
 971   gint             size;
 972   gint             mod;
 973   guint            mask;
 974   gint             nnodes;
 975   gint             noccupied;  /* nnodes + tombstones */
 976
 977   gpointer        *keys;
 978   guint           *hashes;
 979   gpointer        *values;
 980
 981   GHashFunc        hash_func;
 982   GEqualFunc       key_equal_func;
 983   volatile gint    ref_count;
 984
 985 #ifndef G_DISABLE_ASSERT
 986   int              version;
 987 #endif
 988   GDestroyNotify   key_destroy_func;
 989   GDestroyNotify   value_destroy_func;
 990 };
 991
 992 static void
 993 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
 994 {
 995   gint i;
 996
 997   *unused = 0;
 998   *occupied = 0;
 999   *tombstones = 0;
1000   for (i = 0; i < h->size; i++)
1001     {
1002       if (h->hashes[i] == 0)
1003         (*unused)++;
1004       else if (h->hashes[i] == 1)
1005         (*tombstones)++;
1006       else
1007         (*occupied)++;
1008     }
1009 }
1010
1011 static void
1012 check_data (GHashTable *h)
1013 {
1014   gint i;
1015
1016   for (i = 0; i < h->size; i++)
1017     {
1018       if (h->hashes[i] < 2)
1019         {
1020           g_assert (h->keys[i] == NULL);
1021           g_assert (h->values[i] == NULL);
1022         }
1023       else
1024         {
1025           g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1026         }
1027     }
1028 }
1029
1030 static void
1031 check_consistency (GHashTable *h)
1032 {
1033   gint unused;
1034   gint occupied;
1035   gint tombstones;
1036
1037   count_keys (h, &unused, &occupied, &tombstones);
1038
1039   g_assert_cmpint (occupied, ==, h->nnodes);
1040   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1041   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1042
1043   check_data (h);
1044 }
1045
1046 static void
1047 check_counts (GHashTable *h, gint occupied, gint tombstones)
1048 {
1049   g_assert_cmpint (occupied, ==, h->nnodes);
1050   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1051 }
1052
1053 static void
1054 trivial_key_destroy (gpointer key)
1055 {
1056 }
1057
1058 static void
1059 test_internal_consistency (void)
1060 {
1061   GHashTable *h;
1062
1063   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1064
1065   check_counts (h, 0, 0);
1066   check_consistency (h);
1067
1068   g_hash_table_insert (h, "a", "A");
1069   g_hash_table_insert (h, "b", "B");
1070   g_hash_table_insert (h, "c", "C");
1071   g_hash_table_insert (h, "d", "D");
1072   g_hash_table_insert (h, "e", "E");
1073   g_hash_table_insert (h, "f", "F");
1074
1075   check_counts (h, 6, 0);
1076   check_consistency (h);
1077
1078   g_hash_table_remove (h, "a");
1079   check_counts (h, 5, 1);
1080   check_consistency (h);
1081
1082   g_hash_table_remove (h, "b");
1083   check_counts (h, 4, 2);
1084   check_consistency (h);
1085
1086   g_hash_table_insert (h, "c", "c");
1087   check_counts (h, 4, 2);
1088   check_consistency (h);
1089
1090   g_hash_table_insert (h, "a", "A");
1091   check_counts (h, 5, 1);
1092   check_consistency (h);
1093
1094   g_hash_table_remove_all (h);
1095   check_counts (h, 0, 0);
1096   check_consistency (h);
1097
1098   g_hash_table_unref (h);
1099 }
1100
1101 static void
1102 my_key_free (gpointer v)
1103 {
1104   gchar *s = v;
1105   g_assert (s[0] != 'x');
1106   s[0] = 'x';
1107   g_free (v);
1108 }
1109
1110 static void
1111 my_value_free (gpointer v)
1112 {
1113   gchar *s = v;
1114   g_assert (s[0] != 'y');
1115   s[0] = 'y';
1116   g_free (v);
1117 }
1118
1119 static void
1120 test_iter_replace (void)
1121 {
1122   GHashTable *h;
1123   GHashTableIter iter;
1124   gpointer k, v;
1125   gchar *s;
1126
1127   g_test_bug ("662544");
1128
1129   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1130
1131   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1132   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1133   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1134
1135   g_hash_table_iter_init (&iter, h);
1136
1137   while (g_hash_table_iter_next (&iter, &k, &v))
1138     {
1139        s = (gchar*)v;
1140        g_assert (g_ascii_islower (s[0]));
1141        g_hash_table_iter_replace (&iter, g_strdup (k));
1142     }
1143
1144   g_hash_table_unref (h);
1145 }
1146
1147 int
1148 main (int argc, char *argv[])
1149 {
1150   g_test_init (&argc, &argv, NULL);
1151
1152   g_test_bug_base ("http://bugzilla.gnome.org/");
1153
1154   g_test_add_func ("/hash/misc", test_hash_misc);
1155   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1156   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1157   g_test_add_func ("/hash/direct", direct_hash_test);
1158   g_test_add_func ("/hash/int64", int64_hash_test);
1159   g_test_add_func ("/hash/double", double_hash_test);
1160   g_test_add_func ("/hash/string", string_hash_test);
1161   g_test_add_func ("/hash/set", set_hash_test);
1162   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1163   g_test_add_func ("/hash/ref", test_hash_ref);
1164   g_test_add_func ("/hash/remove-all", test_remove_all);
1165   g_test_add_func ("/hash/find", test_find);
1166   g_test_add_func ("/hash/foreach", test_foreach);
1167
1168   /* tests for individual bugs */
1169   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1170   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1171   g_test_add_func ("/hash/consistency", test_internal_consistency);
1172   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1173
1174   return g_test_run ();
1175
1176 }