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