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 static gboolean
 245 remove_even_foreach (gpointer key,
 246                      gpointer value,
 247                      gpointer user_data)
 248 {
 249   const char *_key = (const char *) key;
 250   const char *_value = (const char *) value;
 251   int i;
 252   char val [20];
 253
 254   g_assert (_key != NULL);
 255   g_assert (*_key != 0);
 256   g_assert (_value != NULL);
 257   g_assert (*_value != 0);
 258
 259   i = atoi (_key);
 260
 261   sprintf (val, "%d value", i);
 262   g_assert (strcmp (_value, val) == 0);
 263
 264   return ((i % 2) == 0) ? TRUE : FALSE;
 265 }
 266
 267
 268
 269
 270 static void
 271 second_hash_test (gconstpointer d)
 272 {
 273   gboolean simple_hash = GPOINTER_TO_INT (d);
 274
 275   int       i;
 276   char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 277   GHashTable     *h;
 278   gboolean found;
 279
 280   crcinit ();
 281
 282   h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
 283                              second_hash_cmp,
 284                              g_free, g_free);
 285   g_assert (h != NULL);
 286   for (i = 0; i < 20; i++)
 287     {
 288       sprintf (key, "%d", i);
 289       g_assert (atoi (key) == i);
 290
 291       sprintf (val, "%d value", i);
 292       g_assert (atoi (val) == i);
 293
 294       g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 295     }
 296
 297   g_assert (g_hash_table_size (h) == 20);
 298
 299   for (i = 0; i < 20; i++)
 300     {
 301       sprintf (key, "%d", i);
 302       g_assert (atoi(key) == i);
 303
 304       v = (char *) g_hash_table_lookup (h, key);
 305
 306       g_assert (v != NULL);
 307       g_assert (*v != 0);
 308       g_assert (atoi (v) == i);
 309     }
 310
 311   sprintf (key, "%d", 3);
 312   g_hash_table_remove (h, key);
 313   g_assert (g_hash_table_size (h) == 19);
 314   g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 315   g_assert (g_hash_table_size (h) == 9);
 316   g_hash_table_foreach (h, not_even_foreach, NULL);
 317
 318   for (i = 0; i < 20; i++)
 319     {
 320       sprintf (key, "%d", i);
 321       g_assert (atoi(key) == i);
 322
 323       sprintf (val, "%d value", i);
 324       g_assert (atoi (val) == i);
 325
 326       orig_key = orig_val = NULL;
 327       found = g_hash_table_lookup_extended (h, key,
 328                                             (gpointer)&orig_key,
 329                                             (gpointer)&orig_val);
 330       if ((i % 2) == 0 || i == 3)
 331         {
 332           g_assert (!found);
 333           continue;
 334         }
 335
 336       g_assert (found);
 337
 338       g_assert (orig_key != NULL);
 339       g_assert (strcmp (key, orig_key) == 0);
 340
 341       g_assert (orig_val != NULL);
 342       g_assert (strcmp (val, orig_val) == 0);
 343     }
 344
 345   g_hash_table_destroy (h);
 346 }
 347
 348 static gboolean
 349 find_first (gpointer key,
 350             gpointer value,
 351             gpointer user_data)
 352 {
 353   gint *v = value;
 354   gint *test = user_data;
 355   return (*v == *test);
 356 }
 357
 358
 359 static void
 360 direct_hash_test (void)
 361 {
 362   gint       i, rc;
 363   GHashTable     *h;
 364
 365   h = g_hash_table_new (NULL, NULL);
 366   g_assert (h != NULL);
 367   for (i = 1; i <= 20; i++)
 368     g_hash_table_insert (h, GINT_TO_POINTER (i),
 369                          GINT_TO_POINTER (i + 42));
 370
 371   g_assert (g_hash_table_size (h) == 20);
 372
 373   for (i = 1; i <= 20; i++)
 374     {
 375       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 376
 377       g_assert (rc != 0);
 378       g_assert ((rc - 42) == i);
 379     }
 380
 381   g_hash_table_destroy (h);
 382 }
 383
 384 static void
 385 int_hash_test (void)
 386 {
 387   gint       i, rc;
 388   GHashTable     *h;
 389   gint     values[20];
 390   gint key;
 391
 392   h = g_hash_table_new (g_int_hash, g_int_equal);
 393   g_assert (h != NULL);
 394   for (i = 0; i < 20; i++)
 395     {
 396       values[i] = i + 42;
 397       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 398     }
 399
 400   g_assert (g_hash_table_size (h) == 20);
 401
 402   for (i = 0; i < 20; i++)
 403     {
 404       key = i + 42;
 405       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 406
 407       g_assert_cmpint (rc, ==, i + 42);
 408     }
 409
 410   g_hash_table_destroy (h);
 411 }
 412
 413 static void
 414 int64_hash_test (void)
 415 {
 416   gint       i, rc;
 417   GHashTable     *h;
 418   gint64     values[20];
 419   gint64 key;
 420
 421   h = g_hash_table_new (g_int64_hash, g_int64_equal);
 422   g_assert (h != NULL);
 423   for (i = 0; i < 20; i++)
 424     {
 425       values[i] = i + 42;
 426       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 427     }
 428
 429   g_assert (g_hash_table_size (h) == 20);
 430
 431   for (i = 0; i < 20; i++)
 432     {
 433       key = i + 42;
 434       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 435
 436       g_assert_cmpint (rc, ==, i + 42);
 437     }
 438
 439   g_hash_table_destroy (h);
 440 }
 441
 442 static void
 443 double_hash_test (void)
 444 {
 445   gint       i, rc;
 446   GHashTable     *h;
 447   gdouble values[20];
 448   gdouble key;
 449
 450   h = g_hash_table_new (g_double_hash, g_double_equal);
 451   g_assert (h != NULL);
 452   for (i = 0; i < 20; i++)
 453     {
 454       values[i] = i + 42.5;
 455       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 456     }
 457
 458   g_assert (g_hash_table_size (h) == 20);
 459
 460   for (i = 0; i < 20; i++)
 461     {
 462       key = i + 42.5;
 463       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 464
 465       g_assert_cmpint (rc, ==, i + 42);
 466     }
 467
 468   g_hash_table_destroy (h);
 469 }
 470
 471 static void
 472 string_free (gpointer data)
 473 {
 474   GString *s = data;
 475
 476   g_string_free (s, TRUE);
 477 }
 478
 479 static void
 480 string_hash_test (void)
 481 {
 482   gint       i, rc;
 483   GHashTable     *h;
 484   GString *s;
 485
 486   h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 487   g_assert (h != NULL);
 488   for (i = 0; i < 20; i++)
 489     {
 490       s = g_string_new ("");
 491       g_string_append_printf (s, "%d", i + 42);
 492       g_string_append_c (s, '.');
 493       g_string_prepend_unichar (s, 0x2301);
 494       g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 495     }
 496
 497   g_assert (g_hash_table_size (h) == 20);
 498
 499   s = g_string_new ("");
 500   for (i = 0; i < 20; i++)
 501     {
 502       g_string_assign (s, "");
 503       g_string_append_printf (s, "%d", i + 42);
 504       g_string_append_c (s, '.');
 505       g_string_prepend_unichar (s, 0x2301);
 506       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 507
 508       g_assert_cmpint (rc, ==, i + 42);
 509     }
 510
 511   g_string_free (s, TRUE);
 512   g_hash_table_destroy (h);
 513 }
 514
 515 static void
 516 set_check (gpointer key,
 517            gpointer value,
 518            gpointer user_data)
 519 {
 520   int *pi = user_data;
 521   if (key != value)
 522     g_assert_not_reached ();
 523
 524   g_assert_cmpint (atoi (key) % 7, ==, 2);
 525
 526   (*pi)++;
 527 }
 528
 529 static void
 530 set_hash_test (void)
 531 {
 532   GHashTable *hash_table =
 533     g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 534   int i;
 535
 536   for (i = 2; i < 5000; i += 7)
 537     {
 538       char *s = g_strdup_printf ("%d", i);
 539       g_assert (g_hash_table_add (hash_table, s));
 540     }
 541
 542   g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
 543
 544   i = 0;
 545   g_hash_table_foreach (hash_table, set_check, &i);
 546   g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
 547
 548   g_assert (g_hash_table_contains (hash_table, "2"));
 549   g_assert (g_hash_table_contains (hash_table, "9"));
 550   g_assert (!g_hash_table_contains (hash_table, "a"));
 551
 552   /* this will cause the hash table to loose set nature */
 553   g_assert (g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 554   g_assert (!g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 555
 556   g_assert (g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 557   g_assert (!g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 558
 559   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 560   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 561
 562   g_hash_table_destroy (hash_table);
 563 }
 564
 565
 566 static void
 567 test_hash_misc (void)
 568 {
 569   GHashTable *hash_table;
 570   gint i;
 571   gint value = 120;
 572   gint *pvalue;
 573   GList *keys, *values;
 574   gint keys_len, values_len;
 575   GHashTableIter iter;
 576   gpointer ikey, ivalue;
 577   int result_array[10000];
 578   int n_array[1];
 579
 580   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 581   fill_hash_table_and_array (hash_table);
 582   pvalue = g_hash_table_find (hash_table, find_first, &value);
 583   if (!pvalue || *pvalue != value)
 584     g_assert_not_reached();
 585
 586   keys = g_hash_table_get_keys (hash_table);
 587   if (!keys)
 588     g_assert_not_reached ();
 589
 590   values = g_hash_table_get_values (hash_table);
 591   if (!values)
 592     g_assert_not_reached ();
 593
 594   keys_len = g_list_length (keys);
 595   values_len = g_list_length (values);
 596   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 597     g_assert_not_reached ();
 598
 599   g_list_free (keys);
 600   g_list_free (values);
 601
 602   init_result_array (result_array);
 603   g_hash_table_iter_init (&iter, hash_table);
 604   for (i = 0; i < 10000; i++)
 605     {
 606       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 607
 608       handle_pair (ikey, ivalue, result_array);
 609
 610       if (i % 2)
 611         g_hash_table_iter_remove (&iter);
 612     }
 613   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 614   g_assert (g_hash_table_size (hash_table) == 5000);
 615   verify_result_array (result_array);
 616
 617   fill_hash_table_and_array (hash_table);
 618
 619   init_result_array (result_array);
 620   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 621   verify_result_array (result_array);
 622
 623   for (i = 0; i < 10000; i++)
 624     g_hash_table_remove (hash_table, &array[i]);
 625
 626   fill_hash_table_and_array (hash_table);
 627
 628   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 629       g_hash_table_size (hash_table) != 5000)
 630     g_assert_not_reached();
 631
 632   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 633   g_hash_table_destroy (hash_table);
 634
 635   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 636   fill_hash_table_and_array (hash_table);
 637
 638   n_array[0] = 1;
 639
 640   g_hash_table_iter_init (&iter, hash_table);
 641   for (i = 0; i < 10000; i++)
 642     {
 643       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 644       g_hash_table_iter_replace (&iter, &n_array[0]);
 645     }
 646
 647   g_hash_table_iter_init (&iter, hash_table);
 648   for (i = 0; i < 10000; i++)
 649     {
 650       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 651
 652       g_assert (ivalue == &n_array[0]);
 653     }
 654
 655   g_hash_table_destroy (hash_table);
 656 }
 657
 658 static gint destroy_counter;
 659
 660 static void
 661 value_destroy (gpointer value)
 662 {
 663   destroy_counter++;
 664 }
 665
 666 static void
 667 test_hash_ref (void)
 668 {
 669   GHashTable *h;
 670   GHashTableIter iter;
 671   gchar *key, *value;
 672   gboolean abc_seen = FALSE;
 673   gboolean cde_seen = FALSE;
 674   gboolean xyz_seen = FALSE;
 675
 676   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 677   g_hash_table_insert (h, "abc", "ABC");
 678   g_hash_table_insert (h, "cde", "CDE");
 679   g_hash_table_insert (h, "xyz", "XYZ");
 680
 681   g_assert_cmpint (g_hash_table_size (h), == , 3);
 682
 683   g_hash_table_iter_init (&iter, h);
 684
 685   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 686     {
 687       if (strcmp (key, "abc") == 0)
 688         {
 689           g_assert_cmpstr (value, ==, "ABC");
 690           abc_seen = TRUE;
 691           g_hash_table_iter_steal (&iter);
 692         }
 693       else if (strcmp (key, "cde") == 0)
 694         {
 695           g_assert_cmpstr (value, ==, "CDE");
 696           cde_seen = TRUE;
 697         }
 698       else if (strcmp (key, "xyz") == 0)
 699         {
 700           g_assert_cmpstr (value, ==, "XYZ");
 701           xyz_seen = TRUE;
 702         }
 703     }
 704   g_assert_cmpint (destroy_counter, ==, 0);
 705
 706   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 707   g_assert (abc_seen && cde_seen && xyz_seen);
 708   g_assert_cmpint (g_hash_table_size (h), == , 2);
 709
 710   g_hash_table_ref (h);
 711   g_hash_table_destroy (h);
 712   g_assert_cmpint (g_hash_table_size (h), == , 0);
 713   g_assert_cmpint (destroy_counter, ==, 2);
 714   g_hash_table_insert (h, "uvw", "UVW");
 715   g_hash_table_unref (h);
 716   g_assert_cmpint (destroy_counter, ==, 3);
 717 }
 718
 719 static guint
 720 null_safe_str_hash (gconstpointer key)
 721 {
 722   if (key == NULL)
 723     return 0;
 724   else
 725     return g_str_hash (key);
 726 }
 727
 728 static gboolean
 729 null_safe_str_equal (gconstpointer a, gconstpointer b)
 730 {
 731   return g_strcmp0 (a, b) == 0;
 732 }
 733
 734 static void
 735 test_lookup_null_key (void)
 736 {
 737   GHashTable *h;
 738   gboolean res;
 739   gpointer key;
 740   gpointer value;
 741
 742   g_test_bug ("642944");
 743
 744   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 745   g_hash_table_insert (h, "abc", "ABC");
 746
 747   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 748   g_assert (!res);
 749
 750   g_hash_table_insert (h, NULL, "NULL");
 751
 752   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 753   g_assert (res);
 754   g_assert_cmpstr (value, ==, "NULL");
 755
 756   g_hash_table_unref (h);
 757 }
 758
 759 static gint destroy_key_counter;
 760
 761 static void
 762 key_destroy (gpointer key)
 763 {
 764   destroy_key_counter++;
 765 }
 766
 767 static void
 768 test_remove_all (void)
 769 {
 770   GHashTable *h;
 771   gboolean res;
 772
 773   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 774   g_hash_table_insert (h, "abc", "ABC");
 775   g_hash_table_insert (h, "cde", "CDE");
 776   g_hash_table_insert (h, "xyz", "XYZ");
 777
 778   destroy_counter = 0;
 779   destroy_key_counter = 0;
 780
 781   g_hash_table_steal_all (h);
 782   g_assert_cmpint (destroy_counter, ==, 0);
 783   g_assert_cmpint (destroy_key_counter, ==, 0);
 784
 785   g_hash_table_insert (h, "abc", "ABC");
 786   g_hash_table_insert (h, "cde", "CDE");
 787   g_hash_table_insert (h, "xyz", "XYZ");
 788
 789   res = g_hash_table_steal (h, "nosuchkey");
 790   g_assert (!res);
 791   g_assert_cmpint (destroy_counter, ==, 0);
 792   g_assert_cmpint (destroy_key_counter, ==, 0);
 793
 794   res = g_hash_table_steal (h, "xyz");
 795   g_assert (res);
 796   g_assert_cmpint (destroy_counter, ==, 0);
 797   g_assert_cmpint (destroy_key_counter, ==, 0);
 798
 799   g_hash_table_remove_all (h);
 800   g_assert_cmpint (destroy_counter, ==, 2);
 801   g_assert_cmpint (destroy_key_counter, ==, 2);
 802
 803   g_hash_table_unref (h);
 804 }
 805
 806 typedef struct {
 807   gint ref_count;
 808   const gchar *key;
 809 } RefCountedKey;
 810
 811 static guint
 812 hash_func (gconstpointer key)
 813 {
 814   const RefCountedKey *rkey = key;
 815
 816   return g_str_hash (rkey->key);
 817 }
 818
 819 static gboolean
 820 eq_func (gconstpointer a, gconstpointer b)
 821 {
 822   const RefCountedKey *aa = a;
 823   const RefCountedKey *bb = b;
 824
 825   return g_strcmp0 (aa->key, bb->key) == 0;
 826 }
 827
 828 static void
 829 key_unref (gpointer data)
 830 {
 831   RefCountedKey *key = data;
 832
 833   g_assert (key->ref_count > 0);
 834
 835   key->ref_count -= 1;
 836
 837   if (key->ref_count == 0)
 838     g_free (key);
 839 }
 840
 841 static RefCountedKey *
 842 key_ref (RefCountedKey *key)
 843 {
 844   key->ref_count += 1;
 845
 846   return key;
 847 }
 848
 849 static RefCountedKey *
 850 key_new (const gchar *key)
 851 {
 852   RefCountedKey *rkey;
 853
 854   rkey = g_new (RefCountedKey, 1);
 855
 856   rkey->ref_count = 1;
 857   rkey->key = key;
 858
 859   return rkey;
 860 }
 861
 862 static void
 863 set_ref_hash_test (void)
 864 {
 865   GHashTable *h;
 866   RefCountedKey *key1;
 867   RefCountedKey *key2;
 868
 869   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 870
 871   key1 = key_new ("a");
 872   key2 = key_new ("a");
 873
 874   g_assert_cmpint (key1->ref_count, ==, 1);
 875   g_assert_cmpint (key2->ref_count, ==, 1);
 876
 877   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 878
 879   g_assert_cmpint (key1->ref_count, ==, 3);
 880   g_assert_cmpint (key2->ref_count, ==, 1);
 881
 882   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 883
 884   g_assert_cmpint (key1->ref_count, ==, 1);
 885   g_assert_cmpint (key2->ref_count, ==, 3);
 886
 887   g_hash_table_remove (h, key1);
 888
 889   g_assert_cmpint (key1->ref_count, ==, 1);
 890   g_assert_cmpint (key2->ref_count, ==, 1);
 891
 892   g_hash_table_unref (h);
 893
 894   key_unref (key1);
 895   key_unref (key2);
 896 }
 897
 898 GHashTable *h;
 899
 900 typedef struct {
 901     gchar *string;
 902     gboolean freed;
 903 } FakeFreeData;
 904
 905 GPtrArray *fake_free_data;
 906
 907 static void
 908 fake_free (gpointer dead)
 909 {
 910   guint i;
 911
 912   for (i = 0; i < fake_free_data->len; i++)
 913     {
 914       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 915
 916       if (ffd->string == (gchar *) dead)
 917         {
 918           g_assert (!ffd->freed);
 919           ffd->freed = TRUE;
 920           return;
 921         }
 922     }
 923
 924   g_assert_not_reached ();
 925 }
 926
 927 static void
 928 value_destroy_insert (gpointer value)
 929 {
 930   g_hash_table_remove_all (h);
 931 }
 932
 933 static void
 934 test_destroy_modify (void)
 935 {
 936   FakeFreeData *ffd;
 937   guint i;
 938
 939   g_test_bug ("650459");
 940
 941   fake_free_data = g_ptr_array_new ();
 942
 943   h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
 944
 945   ffd = g_new0 (FakeFreeData, 1);
 946   ffd->string = g_strdup ("a");
 947   g_ptr_array_add (fake_free_data, ffd);
 948   g_hash_table_insert (h, ffd->string, "b");
 949
 950   ffd = g_new0 (FakeFreeData, 1);
 951   ffd->string = g_strdup ("c");
 952   g_ptr_array_add (fake_free_data, ffd);
 953   g_hash_table_insert (h, ffd->string, "d");
 954
 955   ffd = g_new0 (FakeFreeData, 1);
 956   ffd->string = g_strdup ("e");
 957   g_ptr_array_add (fake_free_data, ffd);
 958   g_hash_table_insert (h, ffd->string, "f");
 959
 960   ffd = g_new0 (FakeFreeData, 1);
 961   ffd->string = g_strdup ("g");
 962   g_ptr_array_add (fake_free_data, ffd);
 963   g_hash_table_insert (h, ffd->string, "h");
 964
 965   ffd = g_new0 (FakeFreeData, 1);
 966   ffd->string = g_strdup ("h");
 967   g_ptr_array_add (fake_free_data, ffd);
 968   g_hash_table_insert (h, ffd->string, "k");
 969
 970   ffd = g_new0 (FakeFreeData, 1);
 971   ffd->string = g_strdup ("a");
 972   g_ptr_array_add (fake_free_data, ffd);
 973   g_hash_table_insert (h, ffd->string, "c");
 974
 975   g_hash_table_remove (h, "c");
 976
 977   /* that removed everything... */
 978   for (i = 0; i < fake_free_data->len; i++)
 979     {
 980       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 981
 982       g_assert (ffd->freed);
 983       g_free (ffd->string);
 984       g_free (ffd);
 985     }
 986
 987   g_ptr_array_unref (fake_free_data);
 988
 989   /* ... so this is a no-op */
 990   g_hash_table_remove (h, "e");
 991
 992   g_hash_table_unref (h);
 993 }
 994
 995 static gboolean
 996 find_str (gpointer key, gpointer value, gpointer data)
 997 {
 998   return g_str_equal (key, data);
 999 }
1000
1001 static void
1002 test_find (void)
1003 {
1004   GHashTable *hash;
1005   const gchar *value;
1006
1007   hash = g_hash_table_new (g_str_hash, g_str_equal);
1008
1009   g_hash_table_insert (hash, "a", "A");
1010   g_hash_table_insert (hash, "b", "B");
1011   g_hash_table_insert (hash, "c", "C");
1012   g_hash_table_insert (hash, "d", "D");
1013   g_hash_table_insert (hash, "e", "E");
1014   g_hash_table_insert (hash, "f", "F");
1015
1016   value = g_hash_table_find (hash, find_str, "a");
1017   g_assert_cmpstr (value, ==, "A");
1018
1019   value = g_hash_table_find (hash, find_str, "b");
1020   g_assert_cmpstr (value, ==, "B");
1021
1022   value = g_hash_table_find (hash, find_str, "c");
1023   g_assert_cmpstr (value, ==, "C");
1024
1025   value = g_hash_table_find (hash, find_str, "d");
1026   g_assert_cmpstr (value, ==, "D");
1027
1028   value = g_hash_table_find (hash, find_str, "e");
1029   g_assert_cmpstr (value, ==, "E");
1030
1031   value = g_hash_table_find (hash, find_str, "f");
1032   g_assert_cmpstr (value, ==, "F");
1033
1034   value = g_hash_table_find (hash, find_str, "0");
1035   g_assert (value == NULL);
1036
1037   g_hash_table_unref (hash);
1038 }
1039
1040 gboolean seen_key[6];
1041
1042 static void
1043 foreach_func (gpointer key, gpointer value, gpointer data)
1044 {
1045   seen_key[((char*)key)[0] - 'a'] = TRUE;
1046 }
1047
1048 static void
1049 test_foreach (void)
1050 {
1051   GHashTable *hash;
1052   gint i;
1053
1054   hash = g_hash_table_new (g_str_hash, g_str_equal);
1055
1056   g_hash_table_insert (hash, "a", "A");
1057   g_hash_table_insert (hash, "b", "B");
1058   g_hash_table_insert (hash, "c", "C");
1059   g_hash_table_insert (hash, "d", "D");
1060   g_hash_table_insert (hash, "e", "E");
1061   g_hash_table_insert (hash, "f", "F");
1062
1063   for (i = 0; i < 6; i++)
1064     seen_key[i] = FALSE;
1065
1066   g_hash_table_foreach (hash, foreach_func, NULL);
1067
1068   for (i = 0; i < 6; i++)
1069     g_assert (seen_key[i]);
1070
1071   g_hash_table_unref (hash);
1072 }
1073
1074 static gboolean
1075 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1076 {
1077   GHashTable *hash2 = data;
1078
1079   if (strstr ("ace", (gchar*)key))
1080     {
1081       g_hash_table_insert (hash2, key, value);
1082       return TRUE;
1083     }
1084
1085   return FALSE;
1086 }
1087
1088
1089 static void
1090 test_foreach_steal (void)
1091 {
1092   GHashTable *hash;
1093   GHashTable *hash2;
1094
1095   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1096   hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1097
1098   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1099   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1100   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1101   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1102   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1103   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1104
1105   g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1106
1107   g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1108   g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1109
1110   g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1111   g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1112   g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1113   g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1114   g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1115   g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1116
1117   g_hash_table_unref (hash);
1118   g_hash_table_unref (hash2);
1119 }
1120
1121 struct _GHashTable
1122 {
1123   gint             size;
1124   gint             mod;
1125   guint            mask;
1126   gint             nnodes;
1127   gint             noccupied;  /* nnodes + tombstones */
1128
1129   gpointer        *keys;
1130   guint           *hashes;
1131   gpointer        *values;
1132
1133   GHashFunc        hash_func;
1134   GEqualFunc       key_equal_func;
1135   volatile gint    ref_count;
1136
1137 #ifndef G_DISABLE_ASSERT
1138   int              version;
1139 #endif
1140   GDestroyNotify   key_destroy_func;
1141   GDestroyNotify   value_destroy_func;
1142 };
1143
1144 static void
1145 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1146 {
1147   gint i;
1148
1149   *unused = 0;
1150   *occupied = 0;
1151   *tombstones = 0;
1152   for (i = 0; i < h->size; i++)
1153     {
1154       if (h->hashes[i] == 0)
1155         (*unused)++;
1156       else if (h->hashes[i] == 1)
1157         (*tombstones)++;
1158       else
1159         (*occupied)++;
1160     }
1161 }
1162
1163 static void
1164 check_data (GHashTable *h)
1165 {
1166   gint i;
1167
1168   for (i = 0; i < h->size; i++)
1169     {
1170       if (h->hashes[i] < 2)
1171         {
1172           g_assert (h->keys[i] == NULL);
1173           g_assert (h->values[i] == NULL);
1174         }
1175       else
1176         {
1177           g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1178         }
1179     }
1180 }
1181
1182 static void
1183 check_consistency (GHashTable *h)
1184 {
1185   gint unused;
1186   gint occupied;
1187   gint tombstones;
1188
1189   count_keys (h, &unused, &occupied, &tombstones);
1190
1191   g_assert_cmpint (occupied, ==, h->nnodes);
1192   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1193   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1194
1195   check_data (h);
1196 }
1197
1198 static void
1199 check_counts (GHashTable *h, gint occupied, gint tombstones)
1200 {
1201   g_assert_cmpint (occupied, ==, h->nnodes);
1202   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1203 }
1204
1205 static void
1206 trivial_key_destroy (gpointer key)
1207 {
1208 }
1209
1210 static void
1211 test_internal_consistency (void)
1212 {
1213   GHashTable *h;
1214
1215   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1216
1217   check_counts (h, 0, 0);
1218   check_consistency (h);
1219
1220   g_hash_table_insert (h, "a", "A");
1221   g_hash_table_insert (h, "b", "B");
1222   g_hash_table_insert (h, "c", "C");
1223   g_hash_table_insert (h, "d", "D");
1224   g_hash_table_insert (h, "e", "E");
1225   g_hash_table_insert (h, "f", "F");
1226
1227   check_counts (h, 6, 0);
1228   check_consistency (h);
1229
1230   g_hash_table_remove (h, "a");
1231   check_counts (h, 5, 1);
1232   check_consistency (h);
1233
1234   g_hash_table_remove (h, "b");
1235   check_counts (h, 4, 2);
1236   check_consistency (h);
1237
1238   g_hash_table_insert (h, "c", "c");
1239   check_counts (h, 4, 2);
1240   check_consistency (h);
1241
1242   g_hash_table_insert (h, "a", "A");
1243   check_counts (h, 5, 1);
1244   check_consistency (h);
1245
1246   g_hash_table_remove_all (h);
1247   check_counts (h, 0, 0);
1248   check_consistency (h);
1249
1250   g_hash_table_unref (h);
1251 }
1252
1253 static void
1254 my_key_free (gpointer v)
1255 {
1256   gchar *s = v;
1257   g_assert (s[0] != 'x');
1258   s[0] = 'x';
1259   g_free (v);
1260 }
1261
1262 static void
1263 my_value_free (gpointer v)
1264 {
1265   gchar *s = v;
1266   g_assert (s[0] != 'y');
1267   s[0] = 'y';
1268   g_free (v);
1269 }
1270
1271 static void
1272 test_iter_replace (void)
1273 {
1274   GHashTable *h;
1275   GHashTableIter iter;
1276   gpointer k, v;
1277   gchar *s;
1278
1279   g_test_bug ("662544");
1280
1281   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1282
1283   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1284   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1285   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1286
1287   g_hash_table_iter_init (&iter, h);
1288
1289   while (g_hash_table_iter_next (&iter, &k, &v))
1290     {
1291        s = (gchar*)v;
1292        g_assert (g_ascii_islower (s[0]));
1293        g_hash_table_iter_replace (&iter, g_strdup (k));
1294     }
1295
1296   g_hash_table_unref (h);
1297 }
1298
1299 static void
1300 replace_first_character (gchar *string)
1301 {
1302   string[0] = 'b';
1303 }
1304
1305 static void
1306 test_set_insert_corruption (void)
1307 {
1308   GHashTable *hash_table =
1309     g_hash_table_new_full (g_str_hash, g_str_equal,
1310         (GDestroyNotify) replace_first_character, NULL);
1311   GHashTableIter iter;
1312   gchar a[] = "foo";
1313   gchar b[] = "foo";
1314   gpointer key, value;
1315
1316   g_test_bug ("692815");
1317
1318   g_hash_table_insert (hash_table, a, a);
1319   g_assert (g_hash_table_contains (hash_table, "foo"));
1320
1321   g_hash_table_insert (hash_table, b, b);
1322
1323   g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1324   g_hash_table_iter_init (&iter, hash_table);
1325   if (!g_hash_table_iter_next (&iter, &key, &value))
1326     g_assert_not_reached();
1327
1328   /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1329    * and the sole key in 'hash_table' should be 'a'.
1330    */
1331   g_assert (key != b);
1332   g_assert (key == a);
1333
1334   g_assert_cmpstr (b, ==, "boo");
1335
1336   /* g_hash_table_insert() also says that the value should now be 'b',
1337    * which is probably not what the caller intended but is precisely what they
1338    * asked for.
1339    */
1340   g_assert (value == b);
1341
1342   /* even though the hash has now been de-set-ified: */
1343   g_assert (g_hash_table_contains (hash_table, "foo"));
1344
1345   g_hash_table_unref (hash_table);
1346 }
1347
1348 static void
1349 test_set_to_strv (void)
1350 {
1351   GHashTable *set;
1352   gchar **strv;
1353   guint n;
1354
1355   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1356   g_hash_table_add (set, g_strdup ("xyz"));
1357   g_hash_table_add (set, g_strdup ("xyz"));
1358   g_hash_table_add (set, g_strdup ("abc"));
1359   strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1360   g_hash_table_steal_all (set);
1361   g_hash_table_unref (set);
1362   g_assert_cmpint (n, ==, 2);
1363   n = g_strv_length (strv);
1364   g_assert_cmpint (n, ==, 2);
1365   if (g_str_equal (strv[0], "abc"))
1366     g_assert_cmpstr (strv[1], ==, "xyz");
1367   else
1368     {
1369     g_assert_cmpstr (strv[0], ==, "xyz");
1370     g_assert_cmpstr (strv[1], ==, "abc");
1371     }
1372   g_strfreev (strv);
1373 }
1374
1375 int
1376 main (int argc, char *argv[])
1377 {
1378   g_test_init (&argc, &argv, NULL);
1379
1380   g_test_bug_base ("http://bugzilla.gnome.org/");
1381
1382   g_test_add_func ("/hash/misc", test_hash_misc);
1383   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1384   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1385   g_test_add_func ("/hash/direct", direct_hash_test);
1386   g_test_add_func ("/hash/int", int_hash_test);
1387   g_test_add_func ("/hash/int64", int64_hash_test);
1388   g_test_add_func ("/hash/double", double_hash_test);
1389   g_test_add_func ("/hash/string", string_hash_test);
1390   g_test_add_func ("/hash/set", set_hash_test);
1391   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1392   g_test_add_func ("/hash/ref", test_hash_ref);
1393   g_test_add_func ("/hash/remove-all", test_remove_all);
1394   g_test_add_func ("/hash/find", test_find);
1395   g_test_add_func ("/hash/foreach", test_foreach);
1396   g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1397
1398   /* tests for individual bugs */
1399   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1400   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1401   g_test_add_func ("/hash/consistency", test_internal_consistency);
1402   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1403   g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1404   g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1405
1406   return g_test_run ();
1407
1408 }