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_add (hash_table, 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   g_assert (g_hash_table_contains (hash_table, "2"));
 519   g_assert (g_hash_table_contains (hash_table, "9"));
 520   g_assert (!g_hash_table_contains (hash_table, "a"));
 521
 522   /* this will cause the hash table to loose set nature */
 523   g_hash_table_insert (hash_table, g_strdup ("a"), "b");
 524
 525   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 526   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 527
 528   g_hash_table_destroy (hash_table);
 529 }
 530
 531
 532 static void
 533 test_hash_misc (void)
 534 {
 535   GHashTable *hash_table;
 536   gint i;
 537   gint value = 120;
 538   gint *pvalue;
 539   GList *keys, *values;
 540   gint keys_len, values_len;
 541   GHashTableIter iter;
 542   gpointer ikey, ivalue;
 543   int result_array[10000];
 544   int n_array[1];
 545
 546   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 547   fill_hash_table_and_array (hash_table);
 548   pvalue = g_hash_table_find (hash_table, find_first, &value);
 549   if (!pvalue || *pvalue != value)
 550     g_assert_not_reached();
 551
 552   keys = g_hash_table_get_keys (hash_table);
 553   if (!keys)
 554     g_assert_not_reached ();
 555
 556   values = g_hash_table_get_values (hash_table);
 557   if (!values)
 558     g_assert_not_reached ();
 559
 560   keys_len = g_list_length (keys);
 561   values_len = g_list_length (values);
 562   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 563     g_assert_not_reached ();
 564
 565   g_list_free (keys);
 566   g_list_free (values);
 567
 568   init_result_array (result_array);
 569   g_hash_table_iter_init (&iter, hash_table);
 570   for (i = 0; i < 10000; i++)
 571     {
 572       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 573
 574       handle_pair (ikey, ivalue, result_array);
 575
 576       if (i % 2)
 577         g_hash_table_iter_remove (&iter);
 578     }
 579   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 580   g_assert (g_hash_table_size (hash_table) == 5000);
 581   verify_result_array (result_array);
 582
 583   fill_hash_table_and_array (hash_table);
 584
 585   init_result_array (result_array);
 586   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 587   verify_result_array (result_array);
 588
 589   for (i = 0; i < 10000; i++)
 590     g_hash_table_remove (hash_table, &array[i]);
 591
 592   fill_hash_table_and_array (hash_table);
 593
 594   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 595       g_hash_table_size (hash_table) != 5000)
 596     g_assert_not_reached();
 597
 598   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 599   g_hash_table_destroy (hash_table);
 600
 601   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 602   fill_hash_table_and_array (hash_table);
 603
 604   n_array[0] = 1;
 605
 606   g_hash_table_iter_init (&iter, hash_table);
 607   for (i = 0; i < 10000; i++)
 608     {
 609       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 610       g_hash_table_iter_replace (&iter, &n_array[0]);
 611     }
 612
 613   g_hash_table_iter_init (&iter, hash_table);
 614   for (i = 0; i < 10000; i++)
 615     {
 616       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 617
 618       g_assert (ivalue == &n_array[0]);
 619     }
 620
 621   g_hash_table_destroy (hash_table);
 622 }
 623
 624 static gint destroy_counter;
 625
 626 static void
 627 value_destroy (gpointer value)
 628 {
 629   destroy_counter++;
 630 }
 631
 632 static void
 633 test_hash_ref (void)
 634 {
 635   GHashTable *h;
 636   GHashTableIter iter;
 637   gchar *key, *value;
 638   gboolean abc_seen = FALSE;
 639   gboolean cde_seen = FALSE;
 640   gboolean xyz_seen = FALSE;
 641
 642   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 643   g_hash_table_insert (h, "abc", "ABC");
 644   g_hash_table_insert (h, "cde", "CDE");
 645   g_hash_table_insert (h, "xyz", "XYZ");
 646
 647   g_assert_cmpint (g_hash_table_size (h), == , 3);
 648
 649   g_hash_table_iter_init (&iter, h);
 650
 651   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 652     {
 653       if (strcmp (key, "abc") == 0)
 654         {
 655           g_assert_cmpstr (value, ==, "ABC");
 656           abc_seen = TRUE;
 657           g_hash_table_iter_steal (&iter);
 658         }
 659       else if (strcmp (key, "cde") == 0)
 660         {
 661           g_assert_cmpstr (value, ==, "CDE");
 662           cde_seen = TRUE;
 663         }
 664       else if (strcmp (key, "xyz") == 0)
 665         {
 666           g_assert_cmpstr (value, ==, "XYZ");
 667           xyz_seen = TRUE;
 668         }
 669     }
 670   g_assert_cmpint (destroy_counter, ==, 0);
 671
 672   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 673   g_assert (abc_seen && cde_seen && xyz_seen);
 674   g_assert_cmpint (g_hash_table_size (h), == , 2);
 675
 676   g_hash_table_ref (h);
 677   g_hash_table_destroy (h);
 678   g_assert_cmpint (g_hash_table_size (h), == , 0);
 679   g_assert_cmpint (destroy_counter, ==, 2);
 680   g_hash_table_insert (h, "uvw", "UVW");
 681   g_hash_table_unref (h);
 682   g_assert_cmpint (destroy_counter, ==, 3);
 683 }
 684
 685 static guint
 686 null_safe_str_hash (gconstpointer key)
 687 {
 688   if (key == NULL)
 689     return 0;
 690   else
 691     return g_str_hash (key);
 692 }
 693
 694 static gboolean
 695 null_safe_str_equal (gconstpointer a, gconstpointer b)
 696 {
 697   return g_strcmp0 (a, b) == 0;
 698 }
 699
 700 static void
 701 test_lookup_null_key (void)
 702 {
 703   GHashTable *h;
 704   gboolean res;
 705   gpointer key;
 706   gpointer value;
 707
 708   g_test_bug ("642944");
 709
 710   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 711   g_hash_table_insert (h, "abc", "ABC");
 712
 713   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 714   g_assert (!res);
 715
 716   g_hash_table_insert (h, NULL, "NULL");
 717
 718   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 719   g_assert (res);
 720   g_assert_cmpstr (value, ==, "NULL");
 721
 722   g_hash_table_unref (h);
 723 }
 724
 725 static gint destroy_key_counter;
 726
 727 static void
 728 key_destroy (gpointer key)
 729 {
 730   destroy_key_counter++;
 731 }
 732
 733 static void
 734 test_remove_all (void)
 735 {
 736   GHashTable *h;
 737   gboolean res;
 738
 739   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 740   g_hash_table_insert (h, "abc", "ABC");
 741   g_hash_table_insert (h, "cde", "CDE");
 742   g_hash_table_insert (h, "xyz", "XYZ");
 743
 744   destroy_counter = 0;
 745   destroy_key_counter = 0;
 746
 747   g_hash_table_steal_all (h);
 748   g_assert_cmpint (destroy_counter, ==, 0);
 749   g_assert_cmpint (destroy_key_counter, ==, 0);
 750
 751   g_hash_table_insert (h, "abc", "ABC");
 752   g_hash_table_insert (h, "cde", "CDE");
 753   g_hash_table_insert (h, "xyz", "XYZ");
 754
 755   res = g_hash_table_steal (h, "nosuchkey");
 756   g_assert (!res);
 757   g_assert_cmpint (destroy_counter, ==, 0);
 758   g_assert_cmpint (destroy_key_counter, ==, 0);
 759
 760   res = g_hash_table_steal (h, "xyz");
 761   g_assert (res);
 762   g_assert_cmpint (destroy_counter, ==, 0);
 763   g_assert_cmpint (destroy_key_counter, ==, 0);
 764
 765   g_hash_table_remove_all (h);
 766   g_assert_cmpint (destroy_counter, ==, 2);
 767   g_assert_cmpint (destroy_key_counter, ==, 2);
 768
 769   g_hash_table_unref (h);
 770 }
 771
 772 typedef struct {
 773   gint ref_count;
 774   const gchar *key;
 775 } RefCountedKey;
 776
 777 static guint
 778 hash_func (gconstpointer key)
 779 {
 780   const RefCountedKey *rkey = key;
 781
 782   return g_str_hash (rkey->key);
 783 }
 784
 785 static gboolean
 786 eq_func (gconstpointer a, gconstpointer b)
 787 {
 788   const RefCountedKey *aa = a;
 789   const RefCountedKey *bb = b;
 790
 791   return g_strcmp0 (aa->key, bb->key) == 0;
 792 }
 793
 794 static void
 795 key_unref (gpointer data)
 796 {
 797   RefCountedKey *key = data;
 798
 799   g_assert (key->ref_count > 0);
 800
 801   key->ref_count -= 1;
 802
 803   if (key->ref_count == 0)
 804     g_free (key);
 805 }
 806
 807 static RefCountedKey *
 808 key_ref (RefCountedKey *key)
 809 {
 810   key->ref_count += 1;
 811
 812   return key;
 813 }
 814
 815 static RefCountedKey *
 816 key_new (const gchar *key)
 817 {
 818   RefCountedKey *rkey;
 819
 820   rkey = g_new (RefCountedKey, 1);
 821
 822   rkey->ref_count = 1;
 823   rkey->key = key;
 824
 825   return rkey;
 826 }
 827
 828 static void
 829 set_ref_hash_test (void)
 830 {
 831   GHashTable *h;
 832   RefCountedKey *key1;
 833   RefCountedKey *key2;
 834
 835   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 836
 837   key1 = key_new ("a");
 838   key2 = key_new ("a");
 839
 840   g_assert_cmpint (key1->ref_count, ==, 1);
 841   g_assert_cmpint (key2->ref_count, ==, 1);
 842
 843   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 844
 845   g_assert_cmpint (key1->ref_count, ==, 3);
 846   g_assert_cmpint (key2->ref_count, ==, 1);
 847
 848   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 849
 850   g_assert_cmpint (key1->ref_count, ==, 1);
 851   g_assert_cmpint (key2->ref_count, ==, 3);
 852
 853   g_hash_table_remove (h, key1);
 854
 855   g_assert_cmpint (key1->ref_count, ==, 1);
 856   g_assert_cmpint (key2->ref_count, ==, 1);
 857
 858   g_hash_table_unref (h);
 859
 860   key_unref (key1);
 861   key_unref (key2);
 862 }
 863
 864 GHashTable *h;
 865
 866 typedef struct {
 867     gchar *string;
 868     gboolean freed;
 869 } FakeFreeData;
 870
 871 GPtrArray *fake_free_data;
 872
 873 static void
 874 fake_free (gpointer dead)
 875 {
 876   guint i;
 877
 878   for (i = 0; i < fake_free_data->len; i++)
 879     {
 880       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 881
 882       if (ffd->string == (gchar *) dead)
 883         {
 884           g_assert (!ffd->freed);
 885           ffd->freed = TRUE;
 886           return;
 887         }
 888     }
 889
 890   g_assert_not_reached ();
 891 }
 892
 893 static void
 894 value_destroy_insert (gpointer value)
 895 {
 896   g_hash_table_remove_all (h);
 897 }
 898
 899 static void
 900 test_destroy_modify (void)
 901 {
 902   FakeFreeData *ffd;
 903   guint i;
 904
 905   g_test_bug ("650459");
 906
 907   fake_free_data = g_ptr_array_new ();
 908
 909   h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
 910
 911   ffd = g_new0 (FakeFreeData, 1);
 912   ffd->string = g_strdup ("a");
 913   g_ptr_array_add (fake_free_data, ffd);
 914   g_hash_table_insert (h, ffd->string, "b");
 915
 916   ffd = g_new0 (FakeFreeData, 1);
 917   ffd->string = g_strdup ("c");
 918   g_ptr_array_add (fake_free_data, ffd);
 919   g_hash_table_insert (h, ffd->string, "d");
 920
 921   ffd = g_new0 (FakeFreeData, 1);
 922   ffd->string = g_strdup ("e");
 923   g_ptr_array_add (fake_free_data, ffd);
 924   g_hash_table_insert (h, ffd->string, "f");
 925
 926   ffd = g_new0 (FakeFreeData, 1);
 927   ffd->string = g_strdup ("g");
 928   g_ptr_array_add (fake_free_data, ffd);
 929   g_hash_table_insert (h, ffd->string, "h");
 930
 931   ffd = g_new0 (FakeFreeData, 1);
 932   ffd->string = g_strdup ("h");
 933   g_ptr_array_add (fake_free_data, ffd);
 934   g_hash_table_insert (h, ffd->string, "k");
 935
 936   ffd = g_new0 (FakeFreeData, 1);
 937   ffd->string = g_strdup ("a");
 938   g_ptr_array_add (fake_free_data, ffd);
 939   g_hash_table_insert (h, ffd->string, "c");
 940
 941   g_hash_table_remove (h, "c");
 942
 943   /* that removed everything... */
 944   for (i = 0; i < fake_free_data->len; i++)
 945     {
 946       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 947
 948       g_assert (ffd->freed);
 949       g_free (ffd->string);
 950       g_free (ffd);
 951     }
 952
 953   g_ptr_array_unref (fake_free_data);
 954
 955   /* ... so this is a no-op */
 956   g_hash_table_remove (h, "e");
 957
 958   g_hash_table_unref (h);
 959 }
 960
 961 static gboolean
 962 find_str (gpointer key, gpointer value, gpointer data)
 963 {
 964   return g_str_equal (key, data);
 965 }
 966
 967 static void
 968 test_find (void)
 969 {
 970   GHashTable *hash;
 971   const gchar *value;
 972
 973   hash = g_hash_table_new (g_str_hash, g_str_equal);
 974
 975   g_hash_table_insert (hash, "a", "A");
 976   g_hash_table_insert (hash, "b", "B");
 977   g_hash_table_insert (hash, "c", "C");
 978   g_hash_table_insert (hash, "d", "D");
 979   g_hash_table_insert (hash, "e", "E");
 980   g_hash_table_insert (hash, "f", "F");
 981
 982   value = g_hash_table_find (hash, find_str, "a");
 983   g_assert_cmpstr (value, ==, "A");
 984
 985   value = g_hash_table_find (hash, find_str, "b");
 986   g_assert_cmpstr (value, ==, "B");
 987
 988   value = g_hash_table_find (hash, find_str, "c");
 989   g_assert_cmpstr (value, ==, "C");
 990
 991   value = g_hash_table_find (hash, find_str, "d");
 992   g_assert_cmpstr (value, ==, "D");
 993
 994   value = g_hash_table_find (hash, find_str, "e");
 995   g_assert_cmpstr (value, ==, "E");
 996
 997   value = g_hash_table_find (hash, find_str, "f");
 998   g_assert_cmpstr (value, ==, "F");
 999
1000   value = g_hash_table_find (hash, find_str, "0");
1001   g_assert (value == NULL);
1002
1003   g_hash_table_unref (hash);
1004 }
1005
1006 gboolean seen_key[6];
1007
1008 static void
1009 foreach_func (gpointer key, gpointer value, gpointer data)
1010 {
1011   seen_key[((char*)key)[0] - 'a'] = TRUE;
1012 }
1013
1014 static void
1015 test_foreach (void)
1016 {
1017   GHashTable *hash;
1018   gint i;
1019
1020   hash = g_hash_table_new (g_str_hash, g_str_equal);
1021
1022   g_hash_table_insert (hash, "a", "A");
1023   g_hash_table_insert (hash, "b", "B");
1024   g_hash_table_insert (hash, "c", "C");
1025   g_hash_table_insert (hash, "d", "D");
1026   g_hash_table_insert (hash, "e", "E");
1027   g_hash_table_insert (hash, "f", "F");
1028
1029   for (i = 0; i < 6; i++)
1030     seen_key[i] = FALSE;
1031
1032   g_hash_table_foreach (hash, foreach_func, NULL);
1033
1034   for (i = 0; i < 6; i++)
1035     g_assert (seen_key[i]);
1036
1037   g_hash_table_unref (hash);
1038 }
1039
1040 struct _GHashTable
1041 {
1042   gint             size;
1043   gint             mod;
1044   guint            mask;
1045   gint             nnodes;
1046   gint             noccupied;  /* nnodes + tombstones */
1047
1048   gpointer        *keys;
1049   guint           *hashes;
1050   gpointer        *values;
1051
1052   GHashFunc        hash_func;
1053   GEqualFunc       key_equal_func;
1054   volatile gint    ref_count;
1055
1056 #ifndef G_DISABLE_ASSERT
1057   int              version;
1058 #endif
1059   GDestroyNotify   key_destroy_func;
1060   GDestroyNotify   value_destroy_func;
1061 };
1062
1063 static void
1064 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1065 {
1066   gint i;
1067
1068   *unused = 0;
1069   *occupied = 0;
1070   *tombstones = 0;
1071   for (i = 0; i < h->size; i++)
1072     {
1073       if (h->hashes[i] == 0)
1074         (*unused)++;
1075       else if (h->hashes[i] == 1)
1076         (*tombstones)++;
1077       else
1078         (*occupied)++;
1079     }
1080 }
1081
1082 static void
1083 check_data (GHashTable *h)
1084 {
1085   gint i;
1086
1087   for (i = 0; i < h->size; i++)
1088     {
1089       if (h->hashes[i] < 2)
1090         {
1091           g_assert (h->keys[i] == NULL);
1092           g_assert (h->values[i] == NULL);
1093         }
1094       else
1095         {
1096           g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1097         }
1098     }
1099 }
1100
1101 static void
1102 check_consistency (GHashTable *h)
1103 {
1104   gint unused;
1105   gint occupied;
1106   gint tombstones;
1107
1108   count_keys (h, &unused, &occupied, &tombstones);
1109
1110   g_assert_cmpint (occupied, ==, h->nnodes);
1111   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1112   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1113
1114   check_data (h);
1115 }
1116
1117 static void
1118 check_counts (GHashTable *h, gint occupied, gint tombstones)
1119 {
1120   g_assert_cmpint (occupied, ==, h->nnodes);
1121   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1122 }
1123
1124 static void
1125 trivial_key_destroy (gpointer key)
1126 {
1127 }
1128
1129 static void
1130 test_internal_consistency (void)
1131 {
1132   GHashTable *h;
1133
1134   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1135
1136   check_counts (h, 0, 0);
1137   check_consistency (h);
1138
1139   g_hash_table_insert (h, "a", "A");
1140   g_hash_table_insert (h, "b", "B");
1141   g_hash_table_insert (h, "c", "C");
1142   g_hash_table_insert (h, "d", "D");
1143   g_hash_table_insert (h, "e", "E");
1144   g_hash_table_insert (h, "f", "F");
1145
1146   check_counts (h, 6, 0);
1147   check_consistency (h);
1148
1149   g_hash_table_remove (h, "a");
1150   check_counts (h, 5, 1);
1151   check_consistency (h);
1152
1153   g_hash_table_remove (h, "b");
1154   check_counts (h, 4, 2);
1155   check_consistency (h);
1156
1157   g_hash_table_insert (h, "c", "c");
1158   check_counts (h, 4, 2);
1159   check_consistency (h);
1160
1161   g_hash_table_insert (h, "a", "A");
1162   check_counts (h, 5, 1);
1163   check_consistency (h);
1164
1165   g_hash_table_remove_all (h);
1166   check_counts (h, 0, 0);
1167   check_consistency (h);
1168
1169   g_hash_table_unref (h);
1170 }
1171
1172 static void
1173 my_key_free (gpointer v)
1174 {
1175   gchar *s = v;
1176   g_assert (s[0] != 'x');
1177   s[0] = 'x';
1178   g_free (v);
1179 }
1180
1181 static void
1182 my_value_free (gpointer v)
1183 {
1184   gchar *s = v;
1185   g_assert (s[0] != 'y');
1186   s[0] = 'y';
1187   g_free (v);
1188 }
1189
1190 static void
1191 test_iter_replace (void)
1192 {
1193   GHashTable *h;
1194   GHashTableIter iter;
1195   gpointer k, v;
1196   gchar *s;
1197
1198   g_test_bug ("662544");
1199
1200   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1201
1202   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1203   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1204   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1205
1206   g_hash_table_iter_init (&iter, h);
1207
1208   while (g_hash_table_iter_next (&iter, &k, &v))
1209     {
1210        s = (gchar*)v;
1211        g_assert (g_ascii_islower (s[0]));
1212        g_hash_table_iter_replace (&iter, g_strdup (k));
1213     }
1214
1215   g_hash_table_unref (h);
1216 }
1217
1218 static void
1219 replace_first_character (gchar *string)
1220 {
1221   string[0] = 'b';
1222 }
1223
1224 static void
1225 test_set_insert_corruption (void)
1226 {
1227   GHashTable *hash_table =
1228     g_hash_table_new_full (g_str_hash, g_str_equal,
1229         (GDestroyNotify) replace_first_character, NULL);
1230   GHashTableIter iter;
1231   gchar a[] = "foo";
1232   gchar b[] = "foo";
1233   gpointer key, value;
1234
1235   g_test_bug ("692815");
1236
1237   g_hash_table_insert (hash_table, a, a);
1238   g_assert (g_hash_table_contains (hash_table, "foo"));
1239
1240   g_hash_table_insert (hash_table, b, b);
1241
1242   g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1243   g_hash_table_iter_init (&iter, hash_table);
1244   if (!g_hash_table_iter_next (&iter, &key, &value))
1245     g_assert_not_reached();
1246
1247   /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1248    * and the sole key in 'hash_table' should be 'a'.
1249    */
1250   g_assert (key != b);
1251   g_assert (key == a);
1252
1253   g_assert_cmpstr (b, ==, "boo");
1254
1255   /* g_hash_table_insert() also says that the value should now be 'b',
1256    * which is probably not what the caller intended but is precisely what they
1257    * asked for.
1258    */
1259   g_assert (value == b);
1260
1261   /* even though the hash has now been de-set-ified: */
1262   g_assert (g_hash_table_contains (hash_table, "foo"));
1263
1264   g_hash_table_unref (hash_table);
1265 }
1266
1267 static void
1268 test_set_to_strv (void)
1269 {
1270   GHashTable *set;
1271   gchar **strv;
1272   guint n;
1273
1274   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1275   g_hash_table_add (set, g_strdup ("xyz"));
1276   g_hash_table_add (set, g_strdup ("xyz"));
1277   g_hash_table_add (set, g_strdup ("abc"));
1278   strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1279   g_hash_table_steal_all (set);
1280   g_hash_table_unref (set);
1281   g_assert_cmpint (n, ==, 2);
1282   n = g_strv_length (strv);
1283   g_assert_cmpint (n, ==, 2);
1284   if (g_str_equal (strv[0], "abc"))
1285     g_assert_cmpstr (strv[1], ==, "xyz");
1286   else
1287     {
1288     g_assert_cmpstr (strv[0], ==, "xyz");
1289     g_assert_cmpstr (strv[1], ==, "abc");
1290     }
1291   g_strfreev (strv);
1292 }
1293
1294 int
1295 main (int argc, char *argv[])
1296 {
1297   g_test_init (&argc, &argv, NULL);
1298
1299   g_test_bug_base ("http://bugzilla.gnome.org/");
1300
1301   g_test_add_func ("/hash/misc", test_hash_misc);
1302   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1303   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1304   g_test_add_func ("/hash/direct", direct_hash_test);
1305   g_test_add_func ("/hash/int64", int64_hash_test);
1306   g_test_add_func ("/hash/double", double_hash_test);
1307   g_test_add_func ("/hash/string", string_hash_test);
1308   g_test_add_func ("/hash/set", set_hash_test);
1309   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1310   g_test_add_func ("/hash/ref", test_hash_ref);
1311   g_test_add_func ("/hash/remove-all", test_remove_all);
1312   g_test_add_func ("/hash/find", test_find);
1313   g_test_add_func ("/hash/foreach", test_foreach);
1314
1315   /* tests for individual bugs */
1316   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1317   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1318   g_test_add_func ("/hash/consistency", test_internal_consistency);
1319   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1320   g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1321   g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1322
1323   return g_test_run ();
1324
1325 }