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 #include <stdio.h>
  36 #include <string.h>
  37 #include <stdlib.h>
  38
  39 #include <glib.h>
  40
  41
  42
  43 int array[10000];
  44
  45 static void
  46 fill_hash_table_and_array (GHashTable *hash_table)
  47 {
  48   int i;
  49
  50   for (i = 0; i < 10000; i++)
  51     {
  52       array[i] = i;
  53       g_hash_table_insert (hash_table, &array[i], &array[i]);
  54     }
  55 }
  56
  57 static void
  58 init_result_array (int result_array[10000])
  59 {
  60   int i;
  61
  62   for (i = 0; i < 10000; i++)
  63     result_array[i] = -1;
  64 }
  65
  66 static void
  67 verify_result_array (int array[10000])
  68 {
  69   int i;
  70
  71   for (i = 0; i < 10000; i++)
  72     g_assert (array[i] == i);
  73 }
  74
  75 static void
  76 handle_pair (gpointer key, gpointer value, int result_array[10000])
  77 {
  78   int n;
  79
  80   g_assert (key == value);
  81
  82   n = *((int *) value);
  83
  84   g_assert (n >= 0 && n < 10000);
  85   g_assert (result_array[n] == -1);
  86
  87   result_array[n] = n;
  88 }
  89
  90 static gboolean
  91 my_hash_callback_remove (gpointer key,
  92                          gpointer value,
  93                          gpointer user_data)
  94 {
  95   int *d = value;
  96
  97   if ((*d) % 2)
  98     return TRUE;
  99
 100   return FALSE;
 101 }
 102
 103 static void
 104 my_hash_callback_remove_test (gpointer key,
 105                               gpointer value,
 106                               gpointer user_data)
 107 {
 108   int *d = value;
 109
 110   if ((*d) % 2)
 111     g_assert_not_reached ();
 112 }
 113
 114 static void
 115 my_hash_callback (gpointer key,
 116                   gpointer value,
 117                   gpointer user_data)
 118 {
 119   handle_pair (key, value, user_data);
 120 }
 121
 122 static guint
 123 my_hash (gconstpointer key)
 124 {
 125   return (guint) *((const gint*) key);
 126 }
 127
 128 static gboolean
 129 my_hash_equal (gconstpointer a,
 130                gconstpointer b)
 131 {
 132   return *((const gint*) a) == *((const gint*) b);
 133 }
 134
 135
 136
 137 /*
 138  * This is a simplified version of the pathalias hashing function.
 139  * Thanks to Steve Belovin and Peter Honeyman
 140  *
 141  * hash a string into a long int.  31 bit crc (from andrew appel).
 142  * the crc table is computed at run time by crcinit() -- we could
 143  * precompute, but it takes 1 clock tick on a 750.
 144  *
 145  * This fast table calculation works only if POLY is a prime polynomial
 146  * in the field of integers modulo 2.  Since the coefficients of a
 147  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 148  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 149  * 31 down to 25 are zero.  Happily, we have candidates, from
 150  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 151  *      x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 152  *      x^31 + x^3 + x^0
 153  *
 154  * We reverse the bits to get:
 155  *      111101010000000000000000000000001 but drop the last 1
 156  *         f   5   0   0   0   0   0   0
 157  *      010010000000000000000000000000001 ditto, for 31-bit crc
 158  *         4   8   0   0   0   0   0   0
 159  */
 160
 161 #define POLY 0x48000000L        /* 31-bit polynomial (avoids sign problems) */
 162
 163 static guint CrcTable[128];
 164
 165 /*
 166  - crcinit - initialize tables for hash function
 167  */
 168 static void crcinit(void)
 169 {
 170   int i, j;
 171   guint sum;
 172
 173   for (i = 0; i < 128; ++i)
 174     {
 175       sum = 0L;
 176       for (j = 7 - 1; j >= 0; --j)
 177         if (i & (1 << j))
 178           sum ^= POLY >> j;
 179       CrcTable[i] = sum;
 180     }
 181 }
 182
 183 /*
 184  - hash - Honeyman's nice hashing function
 185  */
 186 static guint
 187 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   return sum;
 202 }
 203
 204
 205 static gboolean
 206 second_hash_cmp (gconstpointer a, gconstpointer b)
 207 {
 208   return strcmp (a, b) == 0;
 209 }
 210
 211
 212
 213 static guint
 214 one_hash (gconstpointer key)
 215 {
 216   return 1;
 217 }
 218
 219
 220 static void
 221 not_even_foreach (gpointer key,
 222                   gpointer value,
 223                   gpointer user_data)
 224 {
 225   const char *_key = (const char *) key;
 226   const char *_value = (const char *) value;
 227   int i;
 228   char val [20];
 229
 230   g_assert (_key != NULL);
 231   g_assert (*_key != 0);
 232   g_assert (_value != NULL);
 233   g_assert (*_value != 0);
 234
 235   i = atoi (_key);
 236
 237   sprintf (val, "%d value", i);
 238   g_assert (strcmp (_value, val) == 0);
 239
 240   g_assert ((i % 2) != 0);
 241   g_assert (i != 3);
 242 }
 243
 244
 245 static gboolean
 246 remove_even_foreach (gpointer key,
 247                      gpointer value,
 248                      gpointer user_data)
 249 {
 250   const char *_key = (const char *) key;
 251   const char *_value = (const char *) value;
 252   int i;
 253   char val [20];
 254
 255   g_assert (_key != NULL);
 256   g_assert (*_key != 0);
 257   g_assert (_value != NULL);
 258   g_assert (*_value != 0);
 259
 260   i = atoi (_key);
 261
 262   sprintf (val, "%d value", i);
 263   g_assert (strcmp (_value, val) == 0);
 264
 265   return ((i % 2) == 0) ? TRUE : FALSE;
 266 }
 267
 268
 269
 270
 271 static void
 272 second_hash_test (gconstpointer d)
 273 {
 274   gboolean simple_hash = GPOINTER_TO_INT (d);
 275
 276   int       i;
 277   char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 278   GHashTable     *h;
 279   gboolean found;
 280
 281   crcinit ();
 282
 283   h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
 284                              second_hash_cmp,
 285                              g_free, g_free);
 286   g_assert (h != NULL);
 287   for (i = 0; i < 20; i++)
 288     {
 289       sprintf (key, "%d", i);
 290       g_assert (atoi (key) == i);
 291
 292       sprintf (val, "%d value", i);
 293       g_assert (atoi (val) == i);
 294
 295       g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 296     }
 297
 298   g_assert (g_hash_table_size (h) == 20);
 299
 300   for (i = 0; i < 20; i++)
 301     {
 302       sprintf (key, "%d", i);
 303       g_assert (atoi(key) == i);
 304
 305       v = (char *) g_hash_table_lookup (h, key);
 306
 307       g_assert (v != NULL);
 308       g_assert (*v != 0);
 309       g_assert (atoi (v) == i);
 310     }
 311
 312   sprintf (key, "%d", 3);
 313   g_hash_table_remove (h, key);
 314   g_assert (g_hash_table_size (h) == 19);
 315   g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 316   g_assert (g_hash_table_size (h) == 9);
 317   g_hash_table_foreach (h, not_even_foreach, NULL);
 318
 319   for (i = 0; i < 20; i++)
 320     {
 321       sprintf (key, "%d", i);
 322       g_assert (atoi(key) == i);
 323
 324       sprintf (val, "%d value", i);
 325       g_assert (atoi (val) == i);
 326
 327       orig_key = orig_val = NULL;
 328       found = g_hash_table_lookup_extended (h, key,
 329                                             (gpointer)&orig_key,
 330                                             (gpointer)&orig_val);
 331       if ((i % 2) == 0 || i == 3)
 332         {
 333           g_assert (!found);
 334           continue;
 335         }
 336
 337       g_assert (found);
 338
 339       g_assert (orig_key != NULL);
 340       g_assert (strcmp (key, orig_key) == 0);
 341
 342       g_assert (orig_val != NULL);
 343       g_assert (strcmp (val, orig_val) == 0);
 344     }
 345
 346   g_hash_table_destroy (h);
 347 }
 348
 349 static gboolean
 350 find_first (gpointer key,
 351             gpointer value,
 352             gpointer user_data)
 353 {
 354   gint *v = value;
 355   gint *test = user_data;
 356   return (*v == *test);
 357 }
 358
 359
 360 static void
 361 direct_hash_test (void)
 362 {
 363   gint       i, rc;
 364   GHashTable     *h;
 365
 366   h = g_hash_table_new (NULL, NULL);
 367   g_assert (h != NULL);
 368   for (i = 1; i <= 20; i++)
 369     g_hash_table_insert (h, GINT_TO_POINTER (i),
 370                          GINT_TO_POINTER (i + 42));
 371
 372   g_assert (g_hash_table_size (h) == 20);
 373
 374   for (i = 1; i <= 20; i++)
 375     {
 376       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 377
 378       g_assert (rc != 0);
 379       g_assert ((rc - 42) == i);
 380     }
 381
 382   g_hash_table_destroy (h);
 383 }
 384
 385 static void
 386 int64_hash_test (void)
 387 {
 388   gint       i, rc;
 389   GHashTable     *h;
 390   gint64     values[20];
 391   gint64 key;
 392
 393   h = g_hash_table_new (g_int64_hash, g_int64_equal);
 394   g_assert (h != NULL);
 395   for (i = 0; i < 20; i++)
 396     {
 397       values[i] = i + 42;
 398       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 399     }
 400
 401   g_assert (g_hash_table_size (h) == 20);
 402
 403   for (i = 0; i < 20; i++)
 404     {
 405       key = i + 42;
 406       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 407
 408       g_assert_cmpint (rc, ==, i + 42);
 409     }
 410
 411   g_hash_table_destroy (h);
 412 }
 413
 414 static void
 415 double_hash_test (void)
 416 {
 417   gint       i, rc;
 418   GHashTable     *h;
 419   gdouble values[20];
 420   gdouble key;
 421
 422   h = g_hash_table_new (g_double_hash, g_double_equal);
 423   g_assert (h != NULL);
 424   for (i = 0; i < 20; i++)
 425     {
 426       values[i] = i + 42.5;
 427       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 428     }
 429
 430   g_assert (g_hash_table_size (h) == 20);
 431
 432   for (i = 0; i < 20; i++)
 433     {
 434       key = i + 42.5;
 435       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 436
 437       g_assert_cmpint (rc, ==, i + 42);
 438     }
 439
 440   g_hash_table_destroy (h);
 441 }
 442
 443 static void
 444 string_free (gpointer data)
 445 {
 446   GString *s = data;
 447
 448   g_string_free (s, TRUE);
 449 }
 450
 451 static void
 452 string_hash_test (void)
 453 {
 454   gint       i, rc;
 455   GHashTable     *h;
 456   GString *s;
 457
 458   h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 459   g_assert (h != NULL);
 460   for (i = 0; i < 20; i++)
 461     {
 462       s = g_string_new ("");
 463       g_string_append_printf (s, "%d", i + 42);
 464       g_string_append_c (s, '.');
 465       g_string_prepend_unichar (s, 0x2301);
 466       g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 467     }
 468
 469   g_assert (g_hash_table_size (h) == 20);
 470
 471   s = g_string_new ("");
 472   for (i = 0; i < 20; i++)
 473     {
 474       g_string_assign (s, "");
 475       g_string_append_printf (s, "%d", i + 42);
 476       g_string_append_c (s, '.');
 477       g_string_prepend_unichar (s, 0x2301);
 478       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 479
 480       g_assert_cmpint (rc, ==, i + 42);
 481     }
 482
 483   g_string_free (s, TRUE);
 484   g_hash_table_destroy (h);
 485 }
 486
 487 static void
 488 set_check (gpointer key,
 489            gpointer value,
 490            gpointer user_data)
 491 {
 492   int *pi = user_data;
 493   if (key != value)
 494     g_assert_not_reached ();
 495
 496   g_assert_cmpint (atoi (key) % 7, ==, 2);
 497
 498   (*pi)++;
 499 }
 500
 501 static void
 502 set_hash_test (void)
 503 {
 504   GHashTable *hash_table =
 505     g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 506   int i;
 507
 508   for (i = 2; i < 5000; i += 7)
 509     {
 510       char *s = g_strdup_printf ("%d", i);
 511       g_hash_table_insert (hash_table, s, s);
 512     }
 513
 514   i = 0;
 515   g_hash_table_foreach (hash_table, set_check, &i);
 516   g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
 517
 518   /* this will cause the hash table to loose set nature */
 519   g_hash_table_insert (hash_table, g_strdup ("a"), "b");
 520
 521   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 522   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 523
 524   g_hash_table_destroy (hash_table);
 525 }
 526
 527
 528 static void
 529 test_hash_misc (void)
 530 {
 531   GHashTable *hash_table;
 532   gint i;
 533   gint value = 120;
 534   gint *pvalue;
 535   GList *keys, *values;
 536   gint keys_len, values_len;
 537   GHashTableIter iter;
 538   gpointer ikey, ivalue;
 539   int result_array[10000];
 540   int n_array[1];
 541
 542   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 543   fill_hash_table_and_array (hash_table);
 544   pvalue = g_hash_table_find (hash_table, find_first, &value);
 545   if (!pvalue || *pvalue != value)
 546     g_assert_not_reached();
 547
 548   keys = g_hash_table_get_keys (hash_table);
 549   if (!keys)
 550     g_assert_not_reached ();
 551
 552   values = g_hash_table_get_values (hash_table);
 553   if (!values)
 554     g_assert_not_reached ();
 555
 556   keys_len = g_list_length (keys);
 557   values_len = g_list_length (values);
 558   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 559     g_assert_not_reached ();
 560
 561   g_list_free (keys);
 562   g_list_free (values);
 563
 564   init_result_array (result_array);
 565   g_hash_table_iter_init (&iter, hash_table);
 566   for (i = 0; i < 10000; i++)
 567     {
 568       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 569
 570       handle_pair (ikey, ivalue, result_array);
 571
 572       if (i % 2)
 573         g_hash_table_iter_remove (&iter);
 574     }
 575   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 576   g_assert (g_hash_table_size (hash_table) == 5000);
 577   verify_result_array (result_array);
 578
 579   fill_hash_table_and_array (hash_table);
 580
 581   init_result_array (result_array);
 582   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 583   verify_result_array (result_array);
 584
 585   for (i = 0; i < 10000; i++)
 586     g_hash_table_remove (hash_table, &array[i]);
 587
 588   fill_hash_table_and_array (hash_table);
 589
 590   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 591       g_hash_table_size (hash_table) != 5000)
 592     g_assert_not_reached();
 593
 594   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 595   g_hash_table_destroy (hash_table);
 596
 597   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 598   fill_hash_table_and_array (hash_table);
 599
 600   n_array[0] = 1;
 601
 602   g_hash_table_iter_init (&iter, hash_table);
 603   for (i = 0; i < 10000; i++)
 604     {
 605       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 606       g_hash_table_iter_replace (&iter, &n_array[0]);
 607     }
 608
 609   g_hash_table_iter_init (&iter, hash_table);
 610   for (i = 0; i < 10000; i++)
 611     {
 612       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 613
 614       g_assert (ivalue == &n_array[0]);
 615     }
 616
 617   g_hash_table_destroy (hash_table);
 618 }
 619
 620 static gint destroy_counter;
 621
 622 static void
 623 value_destroy (gpointer value)
 624 {
 625   destroy_counter++;
 626 }
 627
 628 static void
 629 test_hash_ref (void)
 630 {
 631   GHashTable *h;
 632   GHashTableIter iter;
 633   gchar *key, *value;
 634   gboolean abc_seen = FALSE;
 635   gboolean cde_seen = FALSE;
 636   gboolean xyz_seen = FALSE;
 637
 638   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 639   g_hash_table_insert (h, "abc", "ABC");
 640   g_hash_table_insert (h, "cde", "CDE");
 641   g_hash_table_insert (h, "xyz", "XYZ");
 642
 643   g_assert_cmpint (g_hash_table_size (h), == , 3);
 644
 645   g_hash_table_iter_init (&iter, h);
 646
 647   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 648     {
 649       if (strcmp (key, "abc") == 0)
 650         {
 651           g_assert_cmpstr (value, ==, "ABC");
 652           abc_seen = TRUE;
 653           g_hash_table_iter_steal (&iter);
 654         }
 655       else if (strcmp (key, "cde") == 0)
 656         {
 657           g_assert_cmpstr (value, ==, "CDE");
 658           cde_seen = TRUE;
 659         }
 660       else if (strcmp (key, "xyz") == 0)
 661         {
 662           g_assert_cmpstr (value, ==, "XYZ");
 663           xyz_seen = TRUE;
 664         }
 665     }
 666   g_assert_cmpint (destroy_counter, ==, 0);
 667
 668   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 669   g_assert (abc_seen && cde_seen && xyz_seen);
 670   g_assert_cmpint (g_hash_table_size (h), == , 2);
 671
 672   g_hash_table_ref (h);
 673   g_hash_table_destroy (h);
 674   g_assert_cmpint (g_hash_table_size (h), == , 0);
 675   g_assert_cmpint (destroy_counter, ==, 2);
 676   g_hash_table_insert (h, "uvw", "UVW");
 677   g_hash_table_unref (h);
 678   g_assert_cmpint (destroy_counter, ==, 3);
 679 }
 680
 681 static guint
 682 null_safe_str_hash (gconstpointer key)
 683 {
 684   if (key == NULL)
 685     return 0;
 686   else
 687     return g_str_hash (key);
 688 }
 689
 690 static gboolean
 691 null_safe_str_equal (gconstpointer a, gconstpointer b)
 692 {
 693   return g_strcmp0 (a, b) == 0;
 694 }
 695
 696 static void
 697 test_lookup_null_key (void)
 698 {
 699   GHashTable *h;
 700   gboolean res;
 701   gpointer key;
 702   gpointer value;
 703
 704   g_test_bug ("642944");
 705
 706   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 707   g_hash_table_insert (h, "abc", "ABC");
 708
 709   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 710   g_assert (!res);
 711
 712   g_hash_table_insert (h, NULL, "NULL");
 713
 714   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 715   g_assert (res);
 716   g_assert_cmpstr (value, ==, "NULL");
 717
 718   g_hash_table_unref (h);
 719 }
 720
 721 static gint destroy_key_counter;
 722
 723 static void
 724 key_destroy (gpointer key)
 725 {
 726   destroy_key_counter++;
 727 }
 728
 729 static void
 730 test_remove_all (void)
 731 {
 732   GHashTable *h;
 733   gboolean res;
 734
 735   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 736   g_hash_table_insert (h, "abc", "ABC");
 737   g_hash_table_insert (h, "cde", "CDE");
 738   g_hash_table_insert (h, "xyz", "XYZ");
 739
 740   destroy_counter = 0;
 741   destroy_key_counter = 0;
 742
 743   g_hash_table_steal_all (h);
 744   g_assert_cmpint (destroy_counter, ==, 0);
 745   g_assert_cmpint (destroy_key_counter, ==, 0);
 746
 747   g_hash_table_insert (h, "abc", "ABC");
 748   g_hash_table_insert (h, "cde", "CDE");
 749   g_hash_table_insert (h, "xyz", "XYZ");
 750
 751   res = g_hash_table_steal (h, "nosuchkey");
 752   g_assert (!res);
 753   g_assert_cmpint (destroy_counter, ==, 0);
 754   g_assert_cmpint (destroy_key_counter, ==, 0);
 755
 756   res = g_hash_table_steal (h, "xyz");
 757   g_assert (res);
 758   g_assert_cmpint (destroy_counter, ==, 0);
 759   g_assert_cmpint (destroy_key_counter, ==, 0);
 760
 761   g_hash_table_remove_all (h);
 762   g_assert_cmpint (destroy_counter, ==, 2);
 763   g_assert_cmpint (destroy_key_counter, ==, 2);
 764
 765   g_hash_table_unref (h);
 766 }
 767
 768 typedef struct {
 769   gint ref_count;
 770   const gchar *key;
 771 } RefCountedKey;
 772
 773 static guint
 774 hash_func (gconstpointer key)
 775 {
 776   const RefCountedKey *rkey = key;
 777
 778   return g_str_hash (rkey->key);
 779 }
 780
 781 static gboolean
 782 eq_func (gconstpointer a, gconstpointer b)
 783 {
 784   const RefCountedKey *aa = a;
 785   const RefCountedKey *bb = b;
 786
 787   return g_strcmp0 (aa->key, bb->key) == 0;
 788 }
 789
 790 static void
 791 key_unref (gpointer data)
 792 {
 793   RefCountedKey *key = data;
 794
 795   g_assert (key->ref_count > 0);
 796
 797   key->ref_count -= 1;
 798
 799   if (key->ref_count == 0)
 800     g_free (key);
 801 }
 802
 803 static RefCountedKey *
 804 key_ref (RefCountedKey *key)
 805 {
 806   key->ref_count += 1;
 807
 808   return key;
 809 }
 810
 811 static RefCountedKey *
 812 key_new (const gchar *key)
 813 {
 814   RefCountedKey *rkey;
 815
 816   rkey = g_new (RefCountedKey, 1);
 817
 818   rkey->ref_count = 1;
 819   rkey->key = key;
 820
 821   return rkey;
 822 }
 823
 824 static void
 825 set_ref_hash_test (void)
 826 {
 827   GHashTable *h;
 828   RefCountedKey *key1;
 829   RefCountedKey *key2;
 830
 831   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 832
 833   key1 = key_new ("a");
 834   key2 = key_new ("a");
 835
 836   g_assert_cmpint (key1->ref_count, ==, 1);
 837   g_assert_cmpint (key2->ref_count, ==, 1);
 838
 839   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 840
 841   g_assert_cmpint (key1->ref_count, ==, 3);
 842   g_assert_cmpint (key2->ref_count, ==, 1);
 843
 844   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 845
 846   g_assert_cmpint (key1->ref_count, ==, 1);
 847   g_assert_cmpint (key2->ref_count, ==, 3);
 848
 849   g_hash_table_remove (h, key1);
 850
 851   g_assert_cmpint (key1->ref_count, ==, 1);
 852   g_assert_cmpint (key2->ref_count, ==, 1);
 853
 854   g_hash_table_unref (h);
 855
 856   key_unref (key1);
 857   key_unref (key2);
 858 }
 859
 860 GHashTable *h;
 861
 862 typedef struct {
 863     gchar *string;
 864     gboolean freed;
 865 } FakeFreeData;
 866
 867 GPtrArray *fake_free_data;
 868
 869 static void
 870 fake_free (gpointer dead)
 871 {
 872   guint i;
 873
 874   for (i = 0; i < fake_free_data->len; i++)
 875     {
 876       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 877
 878       if (ffd->string == (gchar *) dead)
 879         {
 880           g_assert (!ffd->freed);
 881           ffd->freed = TRUE;
 882           return;
 883         }
 884     }
 885
 886   g_assert_not_reached ();
 887 }
 888
 889 static void
 890 value_destroy_insert (gpointer value)
 891 {
 892   g_hash_table_remove_all (h);
 893 }
 894
 895 static void
 896 test_destroy_modify (void)
 897 {
 898   FakeFreeData *ffd;
 899   guint i;
 900
 901   g_test_bug ("650459");
 902
 903   fake_free_data = g_ptr_array_new ();
 904
 905   h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
 906
 907   ffd = g_new0 (FakeFreeData, 1);
 908   ffd->string = g_strdup ("a");
 909   g_ptr_array_add (fake_free_data, ffd);
 910   g_hash_table_insert (h, ffd->string, "b");
 911
 912   ffd = g_new0 (FakeFreeData, 1);
 913   ffd->string = g_strdup ("c");
 914   g_ptr_array_add (fake_free_data, ffd);
 915   g_hash_table_insert (h, ffd->string, "d");
 916
 917   ffd = g_new0 (FakeFreeData, 1);
 918   ffd->string = g_strdup ("e");
 919   g_ptr_array_add (fake_free_data, ffd);
 920   g_hash_table_insert (h, ffd->string, "f");
 921
 922   ffd = g_new0 (FakeFreeData, 1);
 923   ffd->string = g_strdup ("g");
 924   g_ptr_array_add (fake_free_data, ffd);
 925   g_hash_table_insert (h, ffd->string, "h");
 926
 927   ffd = g_new0 (FakeFreeData, 1);
 928   ffd->string = g_strdup ("h");
 929   g_ptr_array_add (fake_free_data, ffd);
 930   g_hash_table_insert (h, ffd->string, "k");
 931
 932   ffd = g_new0 (FakeFreeData, 1);
 933   ffd->string = g_strdup ("a");
 934   g_ptr_array_add (fake_free_data, ffd);
 935   g_hash_table_insert (h, ffd->string, "c");
 936
 937   g_hash_table_remove (h, "c");
 938
 939   /* that removed everything... */
 940   for (i = 0; i < fake_free_data->len; i++)
 941     {
 942       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 943
 944       g_assert (ffd->freed);
 945       g_free (ffd);
 946     }
 947
 948   g_ptr_array_unref (fake_free_data);
 949
 950   /* ... so this is a no-op */
 951   g_hash_table_remove (h, "e");
 952
 953   g_hash_table_unref (h);
 954 }
 955
 956 static gboolean
 957 find_str (gpointer key, gpointer value, gpointer data)
 958 {
 959   return g_str_equal (key, data);
 960 }
 961
 962 static void
 963 test_find (void)
 964 {
 965   GHashTable *hash;
 966   const gchar *value;
 967
 968   hash = g_hash_table_new (g_str_hash, g_str_equal);
 969
 970   g_hash_table_insert (hash, "a", "A");
 971   g_hash_table_insert (hash, "b", "B");
 972   g_hash_table_insert (hash, "c", "C");
 973   g_hash_table_insert (hash, "d", "D");
 974   g_hash_table_insert (hash, "e", "E");
 975   g_hash_table_insert (hash, "f", "F");
 976
 977   value = g_hash_table_find (hash, find_str, "a");
 978   g_assert_cmpstr (value, ==, "A");
 979
 980   value = g_hash_table_find (hash, find_str, "b");
 981   g_assert_cmpstr (value, ==, "B");
 982
 983   value = g_hash_table_find (hash, find_str, "c");
 984   g_assert_cmpstr (value, ==, "C");
 985
 986   value = g_hash_table_find (hash, find_str, "d");
 987   g_assert_cmpstr (value, ==, "D");
 988
 989   value = g_hash_table_find (hash, find_str, "e");
 990   g_assert_cmpstr (value, ==, "E");
 991
 992   value = g_hash_table_find (hash, find_str, "f");
 993   g_assert_cmpstr (value, ==, "F");
 994
 995   value = g_hash_table_find (hash, find_str, "0");
 996   g_assert (value == NULL);
 997
 998   g_hash_table_unref (hash);
 999 }
1000
1001 gboolean seen_key[6];
1002
1003 static void
1004 foreach_func (gpointer key, gpointer value, gpointer data)
1005 {
1006   seen_key[((char*)key)[0] - 'a'] = TRUE;
1007 }
1008
1009 static void
1010 test_foreach (void)
1011 {
1012   GHashTable *hash;
1013   gint i;
1014
1015   hash = g_hash_table_new (g_str_hash, g_str_equal);
1016
1017   g_hash_table_insert (hash, "a", "A");
1018   g_hash_table_insert (hash, "b", "B");
1019   g_hash_table_insert (hash, "c", "C");
1020   g_hash_table_insert (hash, "d", "D");
1021   g_hash_table_insert (hash, "e", "E");
1022   g_hash_table_insert (hash, "f", "F");
1023
1024   for (i = 0; i < 6; i++)
1025     seen_key[i] = FALSE;
1026
1027   g_hash_table_foreach (hash, foreach_func, NULL);
1028
1029   for (i = 0; i < 6; i++)
1030     g_assert (seen_key[i]);
1031
1032   g_hash_table_unref (hash);
1033 }
1034
1035 struct _GHashTable
1036 {
1037   gint             size;
1038   gint             mod;
1039   guint            mask;
1040   gint             nnodes;
1041   gint             noccupied;  /* nnodes + tombstones */
1042
1043   gpointer        *keys;
1044   guint           *hashes;
1045   gpointer        *values;
1046
1047   GHashFunc        hash_func;
1048   GEqualFunc       key_equal_func;
1049   volatile gint    ref_count;
1050
1051 #ifndef G_DISABLE_ASSERT
1052   int              version;
1053 #endif
1054   GDestroyNotify   key_destroy_func;
1055   GDestroyNotify   value_destroy_func;
1056 };
1057
1058 static void
1059 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1060 {
1061   gint i;
1062
1063   *unused = 0;
1064   *occupied = 0;
1065   *tombstones = 0;
1066   for (i = 0; i < h->size; i++)
1067     {
1068       if (h->hashes[i] == 0)
1069         (*unused)++;
1070       else if (h->hashes[i] == 1)
1071         (*tombstones)++;
1072       else
1073         (*occupied)++;
1074     }
1075 }
1076
1077 static void
1078 check_data (GHashTable *h)
1079 {
1080   gint i;
1081
1082   for (i = 0; i < h->size; i++)
1083     {
1084       if (h->hashes[i] < 2)
1085         {
1086           g_assert (h->keys[i] == NULL);
1087           g_assert (h->values[i] == NULL);
1088         }
1089       else
1090         {
1091           g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1092         }
1093     }
1094 }
1095
1096 static void
1097 check_consistency (GHashTable *h)
1098 {
1099   gint unused;
1100   gint occupied;
1101   gint tombstones;
1102
1103   count_keys (h, &unused, &occupied, &tombstones);
1104
1105   g_assert_cmpint (occupied, ==, h->nnodes);
1106   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1107   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1108
1109   check_data (h);
1110 }
1111
1112 static void
1113 check_counts (GHashTable *h, gint occupied, gint tombstones)
1114 {
1115   g_assert_cmpint (occupied, ==, h->nnodes);
1116   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1117 }
1118
1119 static void
1120 trivial_key_destroy (gpointer key)
1121 {
1122 }
1123
1124 static void
1125 test_internal_consistency (void)
1126 {
1127   GHashTable *h;
1128
1129   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1130
1131   check_counts (h, 0, 0);
1132   check_consistency (h);
1133
1134   g_hash_table_insert (h, "a", "A");
1135   g_hash_table_insert (h, "b", "B");
1136   g_hash_table_insert (h, "c", "C");
1137   g_hash_table_insert (h, "d", "D");
1138   g_hash_table_insert (h, "e", "E");
1139   g_hash_table_insert (h, "f", "F");
1140
1141   check_counts (h, 6, 0);
1142   check_consistency (h);
1143
1144   g_hash_table_remove (h, "a");
1145   check_counts (h, 5, 1);
1146   check_consistency (h);
1147
1148   g_hash_table_remove (h, "b");
1149   check_counts (h, 4, 2);
1150   check_consistency (h);
1151
1152   g_hash_table_insert (h, "c", "c");
1153   check_counts (h, 4, 2);
1154   check_consistency (h);
1155
1156   g_hash_table_insert (h, "a", "A");
1157   check_counts (h, 5, 1);
1158   check_consistency (h);
1159
1160   g_hash_table_remove_all (h);
1161   check_counts (h, 0, 0);
1162   check_consistency (h);
1163
1164   g_hash_table_unref (h);
1165 }
1166
1167 static void
1168 my_key_free (gpointer v)
1169 {
1170   gchar *s = v;
1171   g_assert (s[0] != 'x');
1172   s[0] = 'x';
1173   g_free (v);
1174 }
1175
1176 static void
1177 my_value_free (gpointer v)
1178 {
1179   gchar *s = v;
1180   g_assert (s[0] != 'y');
1181   s[0] = 'y';
1182   g_free (v);
1183 }
1184
1185 static void
1186 test_iter_replace (void)
1187 {
1188   GHashTable *h;
1189   GHashTableIter iter;
1190   gpointer k, v;
1191   gchar *s;
1192
1193   g_test_bug ("662544");
1194
1195   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1196
1197   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1198   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1199   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1200
1201   g_hash_table_iter_init (&iter, h);
1202
1203   while (g_hash_table_iter_next (&iter, &k, &v))
1204     {
1205        s = (gchar*)v;
1206        g_assert (g_ascii_islower (s[0]));
1207        g_hash_table_iter_replace (&iter, g_strdup (k));
1208     }
1209
1210   g_hash_table_unref (h);
1211 }
1212
1213 int
1214 main (int argc, char *argv[])
1215 {
1216   g_test_init (&argc, &argv, NULL);
1217
1218   g_test_bug_base ("http://bugzilla.gnome.org/");
1219
1220   g_test_add_func ("/hash/misc", test_hash_misc);
1221   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1222   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1223   g_test_add_func ("/hash/direct", direct_hash_test);
1224   g_test_add_func ("/hash/int64", int64_hash_test);
1225   g_test_add_func ("/hash/double", double_hash_test);
1226   g_test_add_func ("/hash/string", string_hash_test);
1227   g_test_add_func ("/hash/set", set_hash_test);
1228   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1229   g_test_add_func ("/hash/ref", test_hash_ref);
1230   g_test_add_func ("/hash/remove-all", test_remove_all);
1231   g_test_add_func ("/hash/find", test_find);
1232   g_test_add_func ("/hash/foreach", test_foreach);
1233
1234   /* tests for individual bugs */
1235   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1236   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1237   g_test_add_func ("/hash/consistency", test_internal_consistency);
1238   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1239
1240   return g_test_run ();
1241
1242 }