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  * SPDX-License-Identifier: LGPL-2.1-or-later
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  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 #include <config.h>
  32
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <stdlib.h>
  36
  37 #include <glib.h>
  38
  39 static int global_array[10000];
  40
  41 static void
  42 fill_hash_table_and_array (GHashTable *hash_table)
  43 {
  44   int i;
  45
  46   for (i = 0; i < 10000; i++)
  47     {
  48       global_array[i] = i;
  49       g_hash_table_insert (hash_table, &global_array[i], &global_array[i]);
  50     }
  51 }
  52
  53 static void
  54 init_result_array (int result_array[10000])
  55 {
  56   int i;
  57
  58   for (i = 0; i < 10000; i++)
  59     result_array[i] = -1;
  60 }
  61
  62 static void
  63 verify_result_array (int array[10000])
  64 {
  65   int i;
  66
  67   for (i = 0; i < 10000; i++)
  68     g_assert (array[i] == i);
  69 }
  70
  71 static void
  72 handle_pair (gpointer key, gpointer value, int result_array[10000])
  73 {
  74   int n;
  75
  76   g_assert (key == value);
  77
  78   n = *((int *) value);
  79
  80   g_assert (n >= 0 && n < 10000);
  81   g_assert (result_array[n] == -1);
  82
  83   result_array[n] = n;
  84 }
  85
  86 static gboolean
  87 my_hash_callback_remove (gpointer key,
  88                          gpointer value,
  89                          gpointer user_data)
  90 {
  91   int *d = value;
  92
  93   if ((*d) % 2)
  94     return TRUE;
  95
  96   return FALSE;
  97 }
  98
  99 static void
 100 my_hash_callback_remove_test (gpointer key,
 101                               gpointer value,
 102                               gpointer user_data)
 103 {
 104   int *d = value;
 105
 106   if ((*d) % 2)
 107     g_assert_not_reached ();
 108 }
 109
 110 static void
 111 my_hash_callback (gpointer key,
 112                   gpointer value,
 113                   gpointer user_data)
 114 {
 115   handle_pair (key, value, user_data);
 116 }
 117
 118 static guint
 119 my_hash (gconstpointer key)
 120 {
 121   return (guint) *((const gint*) key);
 122 }
 123
 124 static gboolean
 125 my_hash_equal (gconstpointer a,
 126                gconstpointer b)
 127 {
 128   return *((const gint*) a) == *((const gint*) b);
 129 }
 130
 131
 132
 133 /*
 134  * This is a simplified version of the pathalias hashing function.
 135  * Thanks to Steve Belovin and Peter Honeyman
 136  *
 137  * hash a string into a long int.  31 bit crc (from andrew appel).
 138  * the crc table is computed at run time by crcinit() -- we could
 139  * precompute, but it takes 1 clock tick on a 750.
 140  *
 141  * This fast table calculation works only if POLY is a prime polynomial
 142  * in the field of integers modulo 2.  Since the coefficients of a
 143  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 144  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 145  * 31 down to 25 are zero.  Happily, we have candidates, from
 146  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 147  *      x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 148  *      x^31 + x^3 + x^0
 149  *
 150  * We reverse the bits to get:
 151  *      111101010000000000000000000000001 but drop the last 1
 152  *         f   5   0   0   0   0   0   0
 153  *      010010000000000000000000000000001 ditto, for 31-bit crc
 154  *         4   8   0   0   0   0   0   0
 155  */
 156
 157 #define POLY 0x48000000L        /* 31-bit polynomial (avoids sign problems) */
 158
 159 static guint CrcTable[128];
 160
 161 /*
 162  - crcinit - initialize tables for hash function
 163  */
 164 static void crcinit(void)
 165 {
 166   int i, j;
 167   guint sum;
 168
 169   for (i = 0; i < 128; ++i)
 170     {
 171       sum = 0L;
 172       for (j = 7 - 1; j >= 0; --j)
 173         if (i & (1 << j))
 174           sum ^= POLY >> j;
 175       CrcTable[i] = sum;
 176     }
 177 }
 178
 179 /*
 180  - hash - Honeyman's nice hashing function
 181  */
 182 static guint
 183 honeyman_hash (gconstpointer key)
 184 {
 185   const gchar *name = (const gchar *) key;
 186   gsize size;
 187   guint sum = 0;
 188
 189   g_assert (name != NULL);
 190   g_assert (*name != 0);
 191
 192   size = strlen (name);
 193
 194   while (size--)
 195     sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
 196
 197   return sum;
 198 }
 199
 200
 201 static gboolean
 202 second_hash_cmp (gconstpointer a, gconstpointer b)
 203 {
 204   return strcmp (a, b) == 0;
 205 }
 206
 207
 208
 209 static guint
 210 one_hash (gconstpointer key)
 211 {
 212   return 1;
 213 }
 214
 215
 216 static void
 217 not_even_foreach (gpointer key,
 218                   gpointer value,
 219                   gpointer user_data)
 220 {
 221   const char *_key = (const char *) key;
 222   const char *_value = (const char *) value;
 223   int i;
 224   char val [20];
 225
 226   g_assert (_key != NULL);
 227   g_assert (*_key != 0);
 228   g_assert (_value != NULL);
 229   g_assert (*_value != 0);
 230
 231   i = atoi (_key);
 232
 233   sprintf (val, "%d value", i);
 234   g_assert (strcmp (_value, val) == 0);
 235
 236   g_assert ((i % 2) != 0);
 237   g_assert (i != 3);
 238 }
 239
 240 static gboolean
 241 remove_even_foreach (gpointer key,
 242                      gpointer value,
 243                      gpointer user_data)
 244 {
 245   const char *_key = (const char *) key;
 246   const char *_value = (const char *) value;
 247   int i;
 248   char val [20];
 249
 250   g_assert (_key != NULL);
 251   g_assert (*_key != 0);
 252   g_assert (_value != NULL);
 253   g_assert (*_value != 0);
 254
 255   i = atoi (_key);
 256
 257   sprintf (val, "%d value", i);
 258   g_assert (strcmp (_value, val) == 0);
 259
 260   return ((i % 2) == 0) ? TRUE : FALSE;
 261 }
 262
 263
 264
 265
 266 static void
 267 second_hash_test (gconstpointer d)
 268 {
 269   gboolean simple_hash = GPOINTER_TO_INT (d);
 270
 271   int       i;
 272   char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 273   GHashTable     *h;
 274   gboolean found;
 275
 276   crcinit ();
 277
 278   h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
 279                              second_hash_cmp,
 280                              g_free, g_free);
 281   g_assert (h != NULL);
 282   for (i = 0; i < 20; i++)
 283     {
 284       sprintf (key, "%d", i);
 285       g_assert (atoi (key) == i);
 286
 287       sprintf (val, "%d value", i);
 288       g_assert (atoi (val) == i);
 289
 290       g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 291     }
 292
 293   g_assert (g_hash_table_size (h) == 20);
 294
 295   for (i = 0; i < 20; i++)
 296     {
 297       sprintf (key, "%d", i);
 298       g_assert (atoi(key) == i);
 299
 300       v = (char *) g_hash_table_lookup (h, key);
 301
 302       g_assert (v != NULL);
 303       g_assert (*v != 0);
 304       g_assert (atoi (v) == i);
 305     }
 306
 307   sprintf (key, "%d", 3);
 308   g_hash_table_remove (h, key);
 309   g_assert (g_hash_table_size (h) == 19);
 310   g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 311   g_assert (g_hash_table_size (h) == 9);
 312   g_hash_table_foreach (h, not_even_foreach, NULL);
 313
 314   for (i = 0; i < 20; i++)
 315     {
 316       sprintf (key, "%d", i);
 317       g_assert (atoi(key) == i);
 318
 319       sprintf (val, "%d value", i);
 320       g_assert (atoi (val) == i);
 321
 322       orig_key = orig_val = NULL;
 323       found = g_hash_table_lookup_extended (h, key,
 324                                             (gpointer)&orig_key,
 325                                             (gpointer)&orig_val);
 326       if ((i % 2) == 0 || i == 3)
 327         {
 328           g_assert (!found);
 329           continue;
 330         }
 331
 332       g_assert (found);
 333
 334       g_assert (orig_key != NULL);
 335       g_assert (strcmp (key, orig_key) == 0);
 336
 337       g_assert (orig_val != NULL);
 338       g_assert (strcmp (val, orig_val) == 0);
 339     }
 340
 341   g_hash_table_destroy (h);
 342 }
 343
 344 static gboolean
 345 find_first (gpointer key,
 346             gpointer value,
 347             gpointer user_data)
 348 {
 349   gint *v = value;
 350   gint *test = user_data;
 351   return (*v == *test);
 352 }
 353
 354 static void
 355 direct_hash_test (void)
 356 {
 357   gint       i, rc;
 358   GHashTable     *h;
 359
 360   h = g_hash_table_new (NULL, NULL);
 361   g_assert (h != NULL);
 362   for (i = 1; i <= 20; i++)
 363     g_hash_table_insert (h, GINT_TO_POINTER (i),
 364                          GINT_TO_POINTER (i + 42));
 365
 366   g_assert (g_hash_table_size (h) == 20);
 367
 368   for (i = 1; i <= 20; i++)
 369     {
 370       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 371
 372       g_assert (rc != 0);
 373       g_assert ((rc - 42) == i);
 374     }
 375
 376   g_hash_table_destroy (h);
 377 }
 378
 379 static void
 380 direct_hash_test2 (void)
 381 {
 382   gint       i, rc;
 383   GHashTable     *h;
 384
 385   h = g_hash_table_new (g_direct_hash, g_direct_equal);
 386   g_assert (h != NULL);
 387   for (i = 1; i <= 20; i++)
 388     g_hash_table_insert (h, GINT_TO_POINTER (i),
 389                          GINT_TO_POINTER (i + 42));
 390
 391   g_assert (g_hash_table_size (h) == 20);
 392
 393   for (i = 1; i <= 20; i++)
 394     {
 395       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 396
 397       g_assert (rc != 0);
 398       g_assert ((rc - 42) == i);
 399     }
 400
 401   g_hash_table_destroy (h);
 402 }
 403
 404 static void
 405 int_hash_test (void)
 406 {
 407   gint       i, rc;
 408   GHashTable     *h;
 409   gint     values[20];
 410   gint key;
 411
 412   h = g_hash_table_new (g_int_hash, g_int_equal);
 413   g_assert (h != NULL);
 414   for (i = 0; i < 20; i++)
 415     {
 416       values[i] = i + 42;
 417       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 418     }
 419
 420   g_assert (g_hash_table_size (h) == 20);
 421
 422   for (i = 0; i < 20; i++)
 423     {
 424       key = i + 42;
 425       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 426
 427       g_assert_cmpint (rc, ==, i + 42);
 428     }
 429
 430   g_hash_table_destroy (h);
 431 }
 432
 433 static void
 434 int64_hash_test (void)
 435 {
 436   gint       i, rc;
 437   GHashTable     *h;
 438   gint64     values[20];
 439   gint64 key;
 440
 441   h = g_hash_table_new (g_int64_hash, g_int64_equal);
 442   g_assert (h != NULL);
 443   for (i = 0; i < 20; i++)
 444     {
 445       values[i] = i + 42;
 446       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 447     }
 448
 449   g_assert (g_hash_table_size (h) == 20);
 450
 451   for (i = 0; i < 20; i++)
 452     {
 453       key = i + 42;
 454       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 455
 456       g_assert_cmpint (rc, ==, i + 42);
 457     }
 458
 459   g_hash_table_destroy (h);
 460 }
 461
 462 static void
 463 int64_hash_collision_test (void)
 464 {
 465   gint64 m;
 466   gint64 n;
 467
 468   g_test_summary ("Check int64 Hash collisions caused by ignoring high word");
 469
 470   m = 722;
 471   n = ((gint64) 2003 << 32) + 722;
 472   g_assert_cmpuint (g_int64_hash (&m), !=, g_int64_hash (&n));
 473 }
 474
 475 static void
 476 double_hash_test (void)
 477 {
 478   gint       i, rc;
 479   GHashTable     *h;
 480   gdouble values[20];
 481   gdouble key;
 482
 483   h = g_hash_table_new (g_double_hash, g_double_equal);
 484   g_assert (h != NULL);
 485   for (i = 0; i < 20; i++)
 486     {
 487       values[i] = i + 42.5;
 488       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 489     }
 490
 491   g_assert (g_hash_table_size (h) == 20);
 492
 493   for (i = 0; i < 20; i++)
 494     {
 495       key = i + 42.5;
 496       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 497
 498       g_assert_cmpint (rc, ==, i + 42);
 499     }
 500
 501   g_hash_table_destroy (h);
 502 }
 503
 504 static void
 505 double_hash_collision_test (void)
 506 {
 507   gdouble m;
 508   gdouble n;
 509
 510   g_test_summary ("Check double Hash collisions caused by int conversion " \
 511                   "and by numbers larger than 2^64-1 (G_MAXUINT64)");
 512   g_test_bug ("https://gitlab.gnome.org/GNOME/glib/-/issues/2771");
 513
 514   /* Equal when directly converted to integers */
 515   m = 0.1;
 516   n = 0.2;
 517   g_assert_cmpuint (g_double_hash (&m), !=, g_double_hash (&n));
 518
 519   /* Numbers larger than 2^64-1 (G_MAXUINT64) */
 520   m = 1e100;
 521   n = 1e200;
 522   g_assert_cmpuint (g_double_hash (&m), !=, g_double_hash (&n));
 523 }
 524
 525 static void
 526 string_free (gpointer data)
 527 {
 528   GString *s = data;
 529
 530   g_string_free (s, TRUE);
 531 }
 532
 533 static void
 534 string_hash_test (void)
 535 {
 536   gint       i, rc;
 537   GHashTable     *h;
 538   GString *s;
 539
 540   h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 541   g_assert (h != NULL);
 542   for (i = 0; i < 20; i++)
 543     {
 544       s = g_string_new ("");
 545       g_string_append_printf (s, "%d", i + 42);
 546       g_string_append_c (s, '.');
 547       g_string_prepend_unichar (s, 0x2301);
 548       g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 549     }
 550
 551   g_assert (g_hash_table_size (h) == 20);
 552
 553   s = g_string_new ("");
 554   for (i = 0; i < 20; i++)
 555     {
 556       g_string_assign (s, "");
 557       g_string_append_printf (s, "%d", i + 42);
 558       g_string_append_c (s, '.');
 559       g_string_prepend_unichar (s, 0x2301);
 560       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 561
 562       g_assert_cmpint (rc, ==, i + 42);
 563     }
 564
 565   g_string_free (s, TRUE);
 566   g_hash_table_destroy (h);
 567 }
 568
 569 static void
 570 set_check (gpointer key,
 571            gpointer value,
 572            gpointer user_data)
 573 {
 574   int *pi = user_data;
 575   if (key != value)
 576     g_assert_not_reached ();
 577
 578   g_assert_cmpint (atoi (key) % 7, ==, 2);
 579
 580   (*pi)++;
 581 }
 582
 583 static void
 584 set_hash_test (void)
 585 {
 586   GHashTable *hash_table =
 587     g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 588   int i;
 589
 590   for (i = 2; i < 5000; i += 7)
 591     {
 592       char *s = g_strdup_printf ("%d", i);
 593       g_assert (g_hash_table_add (hash_table, s));
 594     }
 595
 596   g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
 597
 598   i = 0;
 599   g_hash_table_foreach (hash_table, set_check, &i);
 600   g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
 601
 602   g_assert (g_hash_table_contains (hash_table, "2"));
 603   g_assert (g_hash_table_contains (hash_table, "9"));
 604   g_assert (!g_hash_table_contains (hash_table, "a"));
 605
 606   /* this will cause the hash table to loose set nature */
 607   g_assert (g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 608   g_assert (!g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 609
 610   g_assert (g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 611   g_assert (!g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 612
 613   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 614   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 615
 616   g_hash_table_destroy (hash_table);
 617 }
 618
 619
 620 static void
 621 test_hash_misc (void)
 622 {
 623   GHashTable *hash_table;
 624   gint i;
 625   gint value = 120;
 626   gint *pvalue;
 627   GList *keys, *values;
 628   gsize keys_len, values_len;
 629   GHashTableIter iter;
 630   gpointer ikey, ivalue;
 631   int result_array[10000];
 632   int n_array[1];
 633
 634   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 635   fill_hash_table_and_array (hash_table);
 636   pvalue = g_hash_table_find (hash_table, find_first, &value);
 637   if (!pvalue || *pvalue != value)
 638     g_assert_not_reached();
 639
 640   keys = g_hash_table_get_keys (hash_table);
 641   if (!keys)
 642     g_assert_not_reached ();
 643
 644   values = g_hash_table_get_values (hash_table);
 645   if (!values)
 646     g_assert_not_reached ();
 647
 648   keys_len = g_list_length (keys);
 649   values_len = g_list_length (values);
 650   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 651     g_assert_not_reached ();
 652
 653   g_list_free (keys);
 654   g_list_free (values);
 655
 656   init_result_array (result_array);
 657   g_hash_table_iter_init (&iter, hash_table);
 658   for (i = 0; i < 10000; i++)
 659     {
 660       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 661
 662       handle_pair (ikey, ivalue, result_array);
 663
 664       if (i % 2)
 665         g_hash_table_iter_remove (&iter);
 666     }
 667   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 668   g_assert (g_hash_table_size (hash_table) == 5000);
 669   verify_result_array (result_array);
 670
 671   fill_hash_table_and_array (hash_table);
 672
 673   init_result_array (result_array);
 674   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 675   verify_result_array (result_array);
 676
 677   for (i = 0; i < 10000; i++)
 678     g_hash_table_remove (hash_table, &global_array[i]);
 679
 680   fill_hash_table_and_array (hash_table);
 681
 682   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 683       g_hash_table_size (hash_table) != 5000)
 684     g_assert_not_reached();
 685
 686   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 687   g_hash_table_destroy (hash_table);
 688
 689   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 690   fill_hash_table_and_array (hash_table);
 691
 692   n_array[0] = 1;
 693
 694   g_hash_table_iter_init (&iter, hash_table);
 695   for (i = 0; i < 10000; i++)
 696     {
 697       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 698       g_hash_table_iter_replace (&iter, &n_array[0]);
 699     }
 700
 701   g_hash_table_iter_init (&iter, hash_table);
 702   for (i = 0; i < 10000; i++)
 703     {
 704       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 705
 706       g_assert (ivalue == &n_array[0]);
 707     }
 708
 709   g_hash_table_destroy (hash_table);
 710 }
 711
 712 static gint destroy_counter;
 713
 714 static void
 715 value_destroy (gpointer value)
 716 {
 717   destroy_counter++;
 718 }
 719
 720 static void
 721 test_hash_ref (void)
 722 {
 723   GHashTable *h;
 724   GHashTableIter iter;
 725   gchar *key, *value;
 726   gboolean abc_seen = FALSE;
 727   gboolean cde_seen = FALSE;
 728   gboolean xyz_seen = FALSE;
 729
 730   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 731   g_hash_table_insert (h, "abc", "ABC");
 732   g_hash_table_insert (h, "cde", "CDE");
 733   g_hash_table_insert (h, "xyz", "XYZ");
 734
 735   g_assert_cmpint (g_hash_table_size (h), == , 3);
 736
 737   g_hash_table_iter_init (&iter, h);
 738
 739   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 740     {
 741       if (strcmp (key, "abc") == 0)
 742         {
 743           g_assert_cmpstr (value, ==, "ABC");
 744           abc_seen = TRUE;
 745           g_hash_table_iter_steal (&iter);
 746         }
 747       else if (strcmp (key, "cde") == 0)
 748         {
 749           g_assert_cmpstr (value, ==, "CDE");
 750           cde_seen = TRUE;
 751         }
 752       else if (strcmp (key, "xyz") == 0)
 753         {
 754           g_assert_cmpstr (value, ==, "XYZ");
 755           xyz_seen = TRUE;
 756         }
 757     }
 758   g_assert_cmpint (destroy_counter, ==, 0);
 759
 760   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 761   g_assert (abc_seen && cde_seen && xyz_seen);
 762   g_assert_cmpint (g_hash_table_size (h), == , 2);
 763
 764   g_hash_table_ref (h);
 765   g_hash_table_destroy (h);
 766   g_assert_cmpint (g_hash_table_size (h), == , 0);
 767   g_assert_cmpint (destroy_counter, ==, 2);
 768   g_hash_table_insert (h, "uvw", "UVW");
 769   g_hash_table_unref (h);
 770   g_assert_cmpint (destroy_counter, ==, 3);
 771 }
 772
 773 static guint
 774 null_safe_str_hash (gconstpointer key)
 775 {
 776   if (key == NULL)
 777     return 0;
 778   else
 779     return g_str_hash (key);
 780 }
 781
 782 static gboolean
 783 null_safe_str_equal (gconstpointer a, gconstpointer b)
 784 {
 785   return g_strcmp0 (a, b) == 0;
 786 }
 787
 788 static void
 789 test_lookup_null_key (void)
 790 {
 791   GHashTable *h;
 792   gboolean res;
 793   gpointer key;
 794   gpointer value;
 795
 796   g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=642944");
 797
 798   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 799   g_hash_table_insert (h, "abc", "ABC");
 800
 801   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 802   g_assert (!res);
 803
 804   g_hash_table_insert (h, NULL, "NULL");
 805
 806   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 807   g_assert (res);
 808   g_assert_cmpstr (value, ==, "NULL");
 809
 810   g_hash_table_unref (h);
 811 }
 812
 813 static gint destroy_key_counter;
 814
 815 static void
 816 key_destroy (gpointer key)
 817 {
 818   destroy_key_counter++;
 819 }
 820
 821 static void
 822 test_remove_all (void)
 823 {
 824   GHashTable *h;
 825   gboolean res;
 826
 827   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 828
 829   g_hash_table_insert (h, "abc", "cde");
 830   g_hash_table_insert (h, "cde", "xyz");
 831   g_hash_table_insert (h, "xyz", "abc");
 832
 833   destroy_counter = 0;
 834   destroy_key_counter = 0;
 835
 836   g_hash_table_steal_all (h);
 837   g_assert_cmpint (destroy_counter, ==, 0);
 838   g_assert_cmpint (destroy_key_counter, ==, 0);
 839
 840   /* Test stealing on an empty hash table. */
 841   g_hash_table_steal_all (h);
 842   g_assert_cmpint (destroy_counter, ==, 0);
 843   g_assert_cmpint (destroy_key_counter, ==, 0);
 844
 845   g_hash_table_insert (h, "abc", "ABC");
 846   g_hash_table_insert (h, "cde", "CDE");
 847   g_hash_table_insert (h, "xyz", "XYZ");
 848
 849   res = g_hash_table_steal (h, "nosuchkey");
 850   g_assert (!res);
 851   g_assert_cmpint (destroy_counter, ==, 0);
 852   g_assert_cmpint (destroy_key_counter, ==, 0);
 853
 854   res = g_hash_table_steal (h, "xyz");
 855   g_assert (res);
 856   g_assert_cmpint (destroy_counter, ==, 0);
 857   g_assert_cmpint (destroy_key_counter, ==, 0);
 858
 859   g_hash_table_remove_all (h);
 860   g_assert_cmpint (destroy_counter, ==, 2);
 861   g_assert_cmpint (destroy_key_counter, ==, 2);
 862
 863   g_hash_table_remove_all (h);
 864   g_assert_cmpint (destroy_counter, ==, 2);
 865   g_assert_cmpint (destroy_key_counter, ==, 2);
 866
 867   g_hash_table_unref (h);
 868 }
 869
 870 GHashTable *recursive_destruction_table = NULL;
 871 static void
 872 recursive_value_destroy (gpointer value)
 873 {
 874   destroy_counter++;
 875
 876   if (recursive_destruction_table)
 877     g_hash_table_remove (recursive_destruction_table, value);
 878 }
 879
 880 static void
 881 test_recursive_remove_all_subprocess (void)
 882 {
 883   GHashTable *h;
 884
 885   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
 886   recursive_destruction_table = h;
 887
 888   /* Add more items compared to test_remove_all, as it would not fail otherwise. */
 889   g_hash_table_insert (h, "abc", "cde");
 890   g_hash_table_insert (h, "cde", "fgh");
 891   g_hash_table_insert (h, "fgh", "ijk");
 892   g_hash_table_insert (h, "ijk", "lmn");
 893   g_hash_table_insert (h, "lmn", "opq");
 894   g_hash_table_insert (h, "opq", "rst");
 895   g_hash_table_insert (h, "rst", "uvw");
 896   g_hash_table_insert (h, "uvw", "xyz");
 897   g_hash_table_insert (h, "xyz", "abc");
 898
 899   destroy_counter = 0;
 900   destroy_key_counter = 0;
 901
 902   g_hash_table_remove_all (h);
 903   g_assert_cmpint (destroy_counter, ==, 9);
 904   g_assert_cmpint (destroy_key_counter, ==, 9);
 905
 906   g_hash_table_unref (h);
 907 }
 908
 909 static void
 910 test_recursive_remove_all (void)
 911 {
 912   g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000,
 913                           G_TEST_SUBPROCESS_DEFAULT);
 914   g_test_trap_assert_passed ();
 915 }
 916
 917 typedef struct {
 918   gint ref_count;
 919   const gchar *key;
 920 } RefCountedKey;
 921
 922 static guint
 923 hash_func (gconstpointer key)
 924 {
 925   const RefCountedKey *rkey = key;
 926
 927   return g_str_hash (rkey->key);
 928 }
 929
 930 static gboolean
 931 eq_func (gconstpointer a, gconstpointer b)
 932 {
 933   const RefCountedKey *aa = a;
 934   const RefCountedKey *bb = b;
 935
 936   return g_strcmp0 (aa->key, bb->key) == 0;
 937 }
 938
 939 static void
 940 key_unref (gpointer data)
 941 {
 942   RefCountedKey *key = data;
 943
 944   g_assert (key->ref_count > 0);
 945
 946   key->ref_count -= 1;
 947
 948   if (key->ref_count == 0)
 949     g_free (key);
 950 }
 951
 952 static RefCountedKey *
 953 key_ref (RefCountedKey *key)
 954 {
 955   key->ref_count += 1;
 956
 957   return key;
 958 }
 959
 960 static RefCountedKey *
 961 key_new (const gchar *key)
 962 {
 963   RefCountedKey *rkey;
 964
 965   rkey = g_new (RefCountedKey, 1);
 966
 967   rkey->ref_count = 1;
 968   rkey->key = key;
 969
 970   return rkey;
 971 }
 972
 973 static void
 974 set_ref_hash_test (void)
 975 {
 976   GHashTable *h;
 977   RefCountedKey *key1;
 978   RefCountedKey *key2;
 979
 980   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 981
 982   key1 = key_new ("a");
 983   key2 = key_new ("a");
 984
 985   g_assert_cmpint (key1->ref_count, ==, 1);
 986   g_assert_cmpint (key2->ref_count, ==, 1);
 987
 988   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 989
 990   g_assert_cmpint (key1->ref_count, ==, 3);
 991   g_assert_cmpint (key2->ref_count, ==, 1);
 992
 993   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 994
 995   g_assert_cmpint (key1->ref_count, ==, 1);
 996   g_assert_cmpint (key2->ref_count, ==, 3);
 997
 998   g_hash_table_remove (h, key1);
 999
1000   g_assert_cmpint (key1->ref_count, ==, 1);
1001   g_assert_cmpint (key2->ref_count, ==, 1);
1002
1003   g_hash_table_unref (h);
1004
1005   key_unref (key1);
1006   key_unref (key2);
1007 }
1008
1009 static GHashTable *global_hashtable;
1010
1011 typedef struct {
1012     gchar *string;
1013     gboolean freed;
1014 } FakeFreeData;
1015
1016 static GPtrArray *fake_free_data;
1017
1018 static void
1019 fake_free (gpointer dead)
1020 {
1021   guint i;
1022
1023   for (i = 0; i < fake_free_data->len; i++)
1024     {
1025       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1026
1027       if (ffd->string == (gchar *) dead)
1028         {
1029           g_assert (!ffd->freed);
1030           ffd->freed = TRUE;
1031           return;
1032         }
1033     }
1034
1035   g_assert_not_reached ();
1036 }
1037
1038 static void
1039 value_destroy_insert (gpointer value)
1040 {
1041   g_hash_table_remove_all (global_hashtable);
1042 }
1043
1044 static void
1045 test_destroy_modify (void)
1046 {
1047   FakeFreeData *ffd;
1048   guint i;
1049
1050   g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=650459");
1051
1052   fake_free_data = g_ptr_array_new ();
1053
1054   global_hashtable = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
1055
1056   ffd = g_new0 (FakeFreeData, 1);
1057   ffd->string = g_strdup ("a");
1058   g_ptr_array_add (fake_free_data, ffd);
1059   g_hash_table_insert (global_hashtable, ffd->string, "b");
1060
1061   ffd = g_new0 (FakeFreeData, 1);
1062   ffd->string = g_strdup ("c");
1063   g_ptr_array_add (fake_free_data, ffd);
1064   g_hash_table_insert (global_hashtable, ffd->string, "d");
1065
1066   ffd = g_new0 (FakeFreeData, 1);
1067   ffd->string = g_strdup ("e");
1068   g_ptr_array_add (fake_free_data, ffd);
1069   g_hash_table_insert (global_hashtable, ffd->string, "f");
1070
1071   ffd = g_new0 (FakeFreeData, 1);
1072   ffd->string = g_strdup ("g");
1073   g_ptr_array_add (fake_free_data, ffd);
1074   g_hash_table_insert (global_hashtable, ffd->string, "h");
1075
1076   ffd = g_new0 (FakeFreeData, 1);
1077   ffd->string = g_strdup ("h");
1078   g_ptr_array_add (fake_free_data, ffd);
1079   g_hash_table_insert (global_hashtable, ffd->string, "k");
1080
1081   ffd = g_new0 (FakeFreeData, 1);
1082   ffd->string = g_strdup ("a");
1083   g_ptr_array_add (fake_free_data, ffd);
1084   g_hash_table_insert (global_hashtable, ffd->string, "c");
1085
1086   g_hash_table_remove (global_hashtable, "c");
1087
1088   /* that removed everything... */
1089   for (i = 0; i < fake_free_data->len; i++)
1090     {
1091       ffd = g_ptr_array_index (fake_free_data, i);
1092
1093       g_assert (ffd->freed);
1094       g_free (ffd->string);
1095       g_free (ffd);
1096     }
1097
1098   g_ptr_array_unref (fake_free_data);
1099
1100   /* ... so this is a no-op */
1101   g_hash_table_remove (global_hashtable, "e");
1102
1103   g_hash_table_unref (global_hashtable);
1104 }
1105
1106 static gboolean
1107 find_str (gpointer key, gpointer value, gpointer data)
1108 {
1109   return g_str_equal (key, data);
1110 }
1111
1112 static void
1113 test_find (void)
1114 {
1115   GHashTable *hash;
1116   const gchar *value;
1117
1118   hash = g_hash_table_new (g_str_hash, g_str_equal);
1119
1120   g_hash_table_insert (hash, "a", "A");
1121   g_hash_table_insert (hash, "b", "B");
1122   g_hash_table_insert (hash, "c", "C");
1123   g_hash_table_insert (hash, "d", "D");
1124   g_hash_table_insert (hash, "e", "E");
1125   g_hash_table_insert (hash, "f", "F");
1126
1127   value = g_hash_table_find (hash, find_str, "a");
1128   g_assert_cmpstr (value, ==, "A");
1129
1130   value = g_hash_table_find (hash, find_str, "b");
1131   g_assert_cmpstr (value, ==, "B");
1132
1133   value = g_hash_table_find (hash, find_str, "c");
1134   g_assert_cmpstr (value, ==, "C");
1135
1136   value = g_hash_table_find (hash, find_str, "d");
1137   g_assert_cmpstr (value, ==, "D");
1138
1139   value = g_hash_table_find (hash, find_str, "e");
1140   g_assert_cmpstr (value, ==, "E");
1141
1142   value = g_hash_table_find (hash, find_str, "f");
1143   g_assert_cmpstr (value, ==, "F");
1144
1145   value = g_hash_table_find (hash, find_str, "0");
1146   g_assert (value == NULL);
1147
1148   g_hash_table_unref (hash);
1149 }
1150
1151 gboolean seen_key[6];
1152
1153 static void
1154 foreach_func (gpointer key, gpointer value, gpointer data)
1155 {
1156   seen_key[((char*)key)[0] - 'a'] = TRUE;
1157 }
1158
1159 static void
1160 test_foreach (void)
1161 {
1162   GHashTable *hash;
1163   gint i;
1164
1165   hash = g_hash_table_new (g_str_hash, g_str_equal);
1166
1167   g_hash_table_insert (hash, "a", "A");
1168   g_hash_table_insert (hash, "b", "B");
1169   g_hash_table_insert (hash, "c", "C");
1170   g_hash_table_insert (hash, "d", "D");
1171   g_hash_table_insert (hash, "e", "E");
1172   g_hash_table_insert (hash, "f", "F");
1173
1174   for (i = 0; i < 6; i++)
1175     seen_key[i] = FALSE;
1176
1177   g_hash_table_foreach (hash, foreach_func, NULL);
1178
1179   for (i = 0; i < 6; i++)
1180     g_assert (seen_key[i]);
1181
1182   g_hash_table_unref (hash);
1183 }
1184
1185 static gboolean
1186 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1187 {
1188   GHashTable *hash2 = data;
1189
1190   if (strstr ("ace", (gchar*)key))
1191     {
1192       g_hash_table_insert (hash2, key, value);
1193       return TRUE;
1194     }
1195
1196   return FALSE;
1197 }
1198
1199
1200 static void
1201 test_foreach_steal (void)
1202 {
1203   GHashTable *hash;
1204   GHashTable *hash2;
1205
1206   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1207   hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1208
1209   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1210   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1211   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1212   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1213   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1214   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1215
1216   g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1217
1218   g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1219   g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1220
1221   g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1222   g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1223   g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1224   g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1225   g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1226   g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1227
1228   g_hash_table_unref (hash);
1229   g_hash_table_unref (hash2);
1230 }
1231
1232 /* Test g_hash_table_steal_extended() works properly with existing and
1233  * non-existing keys. */
1234 static void
1235 test_steal_extended (void)
1236 {
1237   GHashTable *hash;
1238   gchar *stolen_key = NULL, *stolen_value = NULL;
1239
1240   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1241
1242   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1243   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1244   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1245   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1246   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1247   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1248
1249   g_assert_true (g_hash_table_steal_extended (hash, "a",
1250                                               (gpointer *) &stolen_key,
1251                                               (gpointer *) &stolen_value));
1252   g_assert_cmpstr (stolen_key, ==, "a");
1253   g_assert_cmpstr (stolen_value, ==, "A");
1254   g_clear_pointer (&stolen_key, g_free);
1255   g_clear_pointer (&stolen_value, g_free);
1256
1257   g_assert_cmpuint (g_hash_table_size (hash), ==, 5);
1258
1259   g_assert_false (g_hash_table_steal_extended (hash, "a",
1260                                                (gpointer *) &stolen_key,
1261                                                (gpointer *) &stolen_value));
1262   g_assert_null (stolen_key);
1263   g_assert_null (stolen_value);
1264
1265   g_assert_false (g_hash_table_steal_extended (hash, "never a key",
1266                                                (gpointer *) &stolen_key,
1267                                                (gpointer *) &stolen_value));
1268   g_assert_null (stolen_key);
1269   g_assert_null (stolen_value);
1270
1271   g_assert_cmpuint (g_hash_table_size (hash), ==, 5);
1272
1273   g_hash_table_unref (hash);
1274 }
1275
1276 /* Test that passing %NULL to the optional g_hash_table_steal_extended()
1277  * arguments works. */
1278 static void
1279 test_steal_extended_optional (void)
1280 {
1281   GHashTable *hash;
1282   const gchar *stolen_key = NULL, *stolen_value = NULL;
1283
1284   hash = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, NULL);
1285
1286   g_hash_table_insert (hash, "b", "B");
1287   g_hash_table_insert (hash, "c", "C");
1288   g_hash_table_insert (hash, "d", "D");
1289   g_hash_table_insert (hash, "e", "E");
1290   g_hash_table_insert (hash, "f", "F");
1291
1292   g_assert_true (g_hash_table_steal_extended (hash, "b",
1293                                               (gpointer *) &stolen_key,
1294                                               NULL));
1295   g_assert_cmpstr (stolen_key, ==, "b");
1296
1297   g_assert_cmpuint (g_hash_table_size (hash), ==, 4);
1298
1299   g_assert_false (g_hash_table_steal_extended (hash, "b",
1300                                                (gpointer *) &stolen_key,
1301                                                NULL));
1302   g_assert_null (stolen_key);
1303
1304   g_assert_true (g_hash_table_steal_extended (hash, "c",
1305                                               NULL,
1306                                               (gpointer *) &stolen_value));
1307   g_assert_cmpstr (stolen_value, ==, "C");
1308
1309   g_assert_cmpuint (g_hash_table_size (hash), ==, 3);
1310
1311   g_assert_false (g_hash_table_steal_extended (hash, "c",
1312                                                NULL,
1313                                                (gpointer *) &stolen_value));
1314   g_assert_null (stolen_value);
1315
1316   g_assert_true (g_hash_table_steal_extended (hash, "d", NULL, NULL));
1317
1318   g_assert_cmpuint (g_hash_table_size (hash), ==, 2);
1319
1320   g_assert_false (g_hash_table_steal_extended (hash, "d", NULL, NULL));
1321
1322   g_assert_cmpuint (g_hash_table_size (hash), ==, 2);
1323
1324   g_hash_table_unref (hash);
1325 }
1326
1327 /* Test g_hash_table_lookup_extended() works with its optional parameters
1328  * sometimes set to %NULL. */
1329 static void
1330 test_lookup_extended (void)
1331 {
1332   GHashTable *hash;
1333   const gchar *original_key = NULL, *value = NULL;
1334
1335   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1336
1337   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1338   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1339   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1340   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1341   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1342   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1343
1344   g_assert_true (g_hash_table_lookup_extended (hash, "a",
1345                                                (gpointer *) &original_key,
1346                                                (gpointer *) &value));
1347   g_assert_cmpstr (original_key, ==, "a");
1348   g_assert_cmpstr (value, ==, "A");
1349
1350   g_assert_true (g_hash_table_lookup_extended (hash, "b",
1351                                                NULL,
1352                                                (gpointer *) &value));
1353   g_assert_cmpstr (value, ==, "B");
1354
1355   g_assert_true (g_hash_table_lookup_extended (hash, "c",
1356                                                (gpointer *) &original_key,
1357                                                NULL));
1358   g_assert_cmpstr (original_key, ==, "c");
1359
1360   g_assert_true (g_hash_table_lookup_extended (hash, "d", NULL, NULL));
1361
1362   g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
1363                                                 (gpointer *) &original_key,
1364                                                 (gpointer *) &value));
1365   g_assert_null (original_key);
1366   g_assert_null (value);
1367
1368   g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
1369                                                 NULL,
1370                                                 (gpointer *) &value));
1371   g_assert_null (value);
1372
1373   g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
1374                                                 (gpointer *) &original_key,
1375                                                 NULL));
1376   g_assert_null (original_key);
1377
1378   g_assert_false (g_hash_table_lookup_extended (hash, "not a key", NULL, NULL));
1379
1380   g_hash_table_unref (hash);
1381 }
1382
1383 static void
1384 inc_state (gpointer user_data)
1385 {
1386   int *state = user_data;
1387   g_assert_cmpint (*state, ==, 0);
1388   *state = 1;
1389 }
1390
1391 static void
1392 test_new_similar (void)
1393 {
1394   GHashTable *hash1;
1395   GHashTable *hash2;
1396   int state1;
1397   int state2;
1398
1399   hash1 = g_hash_table_new_full (g_str_hash, g_str_equal,
1400                                  g_free, inc_state);
1401   state1 = 0;
1402   g_hash_table_insert (hash1,
1403                        g_strdup ("test"),
1404                        &state1);
1405   g_assert_true (g_hash_table_lookup (hash1, "test") == &state1);
1406
1407   hash2 = g_hash_table_new_similar (hash1);
1408
1409   g_assert_true (g_hash_table_lookup (hash1, "test") == &state1);
1410   g_assert_null (g_hash_table_lookup (hash2, "test"));
1411
1412   state2 = 0;
1413   g_hash_table_insert (hash2, g_strdup ("test"), &state2);
1414   g_assert_true (g_hash_table_lookup (hash2, "test") == &state2);
1415   g_hash_table_remove (hash2, "test");
1416   g_assert_cmpint (state2, ==, 1);
1417
1418   g_assert_cmpint (state1, ==, 0);
1419   g_hash_table_remove (hash1, "test");
1420   g_assert_cmpint (state1, ==, 1);
1421
1422   g_hash_table_unref (hash1);
1423   g_hash_table_unref (hash2);
1424 }
1425
1426 struct _GHashTable
1427 {
1428   gsize            size;
1429   gint             mod;
1430   guint            mask;
1431   gint             nnodes;
1432   gint             noccupied;  /* nnodes + tombstones */
1433
1434   guint            have_big_keys : 1;
1435   guint            have_big_values : 1;
1436
1437   gpointer        *keys;
1438   guint           *hashes;
1439   gpointer        *values;
1440
1441   GHashFunc        hash_func;
1442   GEqualFunc       key_equal_func;
1443   gint             ref_count;  /* (atomic) */
1444
1445 #ifndef G_DISABLE_ASSERT
1446   int              version;
1447 #endif
1448   GDestroyNotify   key_destroy_func;
1449   GDestroyNotify   value_destroy_func;
1450 };
1451
1452 static void
1453 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1454 {
1455   gsize i;
1456
1457   *unused = 0;
1458   *occupied = 0;
1459   *tombstones = 0;
1460   for (i = 0; i < h->size; i++)
1461     {
1462       if (h->hashes[i] == 0)
1463         (*unused)++;
1464       else if (h->hashes[i] == 1)
1465         (*tombstones)++;
1466       else
1467         (*occupied)++;
1468     }
1469 }
1470
1471 #define BIG_ENTRY_SIZE (SIZEOF_VOID_P)
1472 #define SMALL_ENTRY_SIZE (SIZEOF_INT)
1473
1474 #if SMALL_ENTRY_SIZE < BIG_ENTRY_SIZE
1475 # define USE_SMALL_ARRAYS
1476 #endif
1477
1478 static gpointer
1479 fetch_key_or_value (gpointer a, guint index, gboolean is_big)
1480 {
1481 #ifdef USE_SMALL_ARRAYS
1482   return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
1483 #else
1484   return *(((gpointer *) a) + index);
1485 #endif
1486 }
1487
1488 static void
1489 check_data (GHashTable *h)
1490 {
1491   gsize i;
1492
1493   for (i = 0; i < h->size; i++)
1494     {
1495       if (h->hashes[i] >= 2)
1496         {
1497           g_assert_cmpint (h->hashes[i], ==, h->hash_func (fetch_key_or_value (h->keys, i, h->have_big_keys)));
1498         }
1499     }
1500 }
1501
1502 static void
1503 check_consistency (GHashTable *h)
1504 {
1505   gint unused;
1506   gint occupied;
1507   gint tombstones;
1508
1509   count_keys (h, &unused, &occupied, &tombstones);
1510
1511   g_assert_cmpint (occupied, ==, h->nnodes);
1512   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1513   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1514
1515   check_data (h);
1516 }
1517
1518 static void
1519 check_counts (GHashTable *h, gint occupied, gint tombstones)
1520 {
1521   g_assert_cmpint (occupied, ==, h->nnodes);
1522   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1523 }
1524
1525 static void
1526 trivial_key_destroy (gpointer key)
1527 {
1528 }
1529
1530 static void
1531 test_internal_consistency (void)
1532 {
1533   GHashTable *h;
1534
1535   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1536
1537   check_counts (h, 0, 0);
1538   check_consistency (h);
1539
1540   g_hash_table_insert (h, "a", "A");
1541   g_hash_table_insert (h, "b", "B");
1542   g_hash_table_insert (h, "c", "C");
1543   g_hash_table_insert (h, "d", "D");
1544   g_hash_table_insert (h, "e", "E");
1545   g_hash_table_insert (h, "f", "F");
1546
1547   check_counts (h, 6, 0);
1548   check_consistency (h);
1549
1550   g_hash_table_remove (h, "a");
1551   check_counts (h, 5, 1);
1552   check_consistency (h);
1553
1554   g_hash_table_remove (h, "b");
1555   check_counts (h, 4, 2);
1556   check_consistency (h);
1557
1558   g_hash_table_insert (h, "c", "c");
1559   check_counts (h, 4, 2);
1560   check_consistency (h);
1561
1562   g_hash_table_insert (h, "a", "A");
1563   check_counts (h, 5, 1);
1564   check_consistency (h);
1565
1566   g_hash_table_remove_all (h);
1567   check_counts (h, 0, 0);
1568   check_consistency (h);
1569
1570   g_hash_table_unref (h);
1571 }
1572
1573 static void
1574 my_key_free (gpointer v)
1575 {
1576   gchar *s = v;
1577   g_assert (s[0] != 'x');
1578   s[0] = 'x';
1579   g_free (v);
1580 }
1581
1582 static void
1583 my_value_free (gpointer v)
1584 {
1585   gchar *s = v;
1586   g_assert (s[0] != 'y');
1587   s[0] = 'y';
1588   g_free (v);
1589 }
1590
1591 static void
1592 test_iter_replace (void)
1593 {
1594   GHashTable *h;
1595   GHashTableIter iter;
1596   gpointer k, v;
1597   gchar *s;
1598
1599   g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=662544");
1600
1601   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1602
1603   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1604   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1605   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1606
1607   g_hash_table_iter_init (&iter, h);
1608
1609   while (g_hash_table_iter_next (&iter, &k, &v))
1610     {
1611        s = (gchar*)v;
1612        g_assert (g_ascii_islower (s[0]));
1613        g_hash_table_iter_replace (&iter, g_strdup (k));
1614     }
1615
1616   g_hash_table_unref (h);
1617 }
1618
1619 static void
1620 replace_first_character (gchar *string)
1621 {
1622   string[0] = 'b';
1623 }
1624
1625 static void
1626 test_set_insert_corruption (void)
1627 {
1628   GHashTable *hash_table =
1629     g_hash_table_new_full (g_str_hash, g_str_equal,
1630         (GDestroyNotify) replace_first_character, NULL);
1631   GHashTableIter iter;
1632   gchar a[] = "foo";
1633   gchar b[] = "foo";
1634   gpointer key, value;
1635
1636   g_test_bug ("https://bugzilla.gnome.org/show_bug.cgi?id=692815");
1637
1638   g_hash_table_insert (hash_table, a, a);
1639   g_assert (g_hash_table_contains (hash_table, "foo"));
1640
1641   g_hash_table_insert (hash_table, b, b);
1642
1643   g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1644   g_hash_table_iter_init (&iter, hash_table);
1645   if (!g_hash_table_iter_next (&iter, &key, &value))
1646     g_assert_not_reached();
1647
1648   /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1649    * and the sole key in 'hash_table' should be 'a'.
1650    */
1651   g_assert (key != b);
1652   g_assert (key == a);
1653
1654   g_assert_cmpstr (b, ==, "boo");
1655
1656   /* g_hash_table_insert() also says that the value should now be 'b',
1657    * which is probably not what the caller intended but is precisely what they
1658    * asked for.
1659    */
1660   g_assert (value == b);
1661
1662   /* even though the hash has now been de-set-ified: */
1663   g_assert (g_hash_table_contains (hash_table, "foo"));
1664
1665   g_hash_table_unref (hash_table);
1666 }
1667
1668 static void
1669 test_set_to_strv (void)
1670 {
1671   GHashTable *set;
1672   gchar **strv;
1673   guint n;
1674
1675   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1676   g_hash_table_add (set, g_strdup ("xyz"));
1677   g_hash_table_add (set, g_strdup ("xyz"));
1678   g_hash_table_add (set, g_strdup ("abc"));
1679   strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1680   g_hash_table_steal_all (set);
1681   g_hash_table_unref (set);
1682   g_assert_cmpint (n, ==, 2);
1683   n = g_strv_length (strv);
1684   g_assert_cmpint (n, ==, 2);
1685   if (g_str_equal (strv[0], "abc"))
1686     g_assert_cmpstr (strv[1], ==, "xyz");
1687   else
1688     {
1689     g_assert_cmpstr (strv[0], ==, "xyz");
1690     g_assert_cmpstr (strv[1], ==, "abc");
1691     }
1692   g_strfreev (strv);
1693 }
1694
1695 static void
1696 test_set_get_keys_as_ptr_array (void)
1697 {
1698   GHashTable *set;
1699   GPtrArray *array;
1700
1701   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1702   g_hash_table_add (set, g_strdup ("xyz"));
1703   g_hash_table_add (set, g_strdup ("xyz"));
1704   g_hash_table_add (set, g_strdup ("abc"));
1705
1706   array = g_hash_table_get_keys_as_ptr_array (set);
1707   g_hash_table_steal_all (set);
1708   g_hash_table_unref (set);
1709   g_ptr_array_set_free_func (array, g_free);
1710
1711   g_assert_cmpint (array->len, ==, 2);
1712   g_ptr_array_add (array, NULL);
1713
1714   g_assert_true (
1715     g_strv_equal ((const gchar * const[]) { "xyz", "abc", NULL },
1716                   (const gchar * const*) array->pdata) ||
1717     g_strv_equal ((const gchar * const[]) { "abc", "xyz", NULL },
1718                   (const gchar * const*) array->pdata)
1719   );
1720
1721   g_clear_pointer (&array, g_ptr_array_unref);
1722 }
1723
1724 static void
1725 test_set_get_values_as_ptr_array (void)
1726 {
1727   GHashTable *table;
1728   GPtrArray *array;
1729
1730   table = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1731   g_hash_table_insert (table, g_strdup ("xyz"), GUINT_TO_POINTER (0));
1732   g_hash_table_insert (table, g_strdup ("xyz"), GUINT_TO_POINTER (1));
1733   g_hash_table_insert (table, g_strdup ("abc"), GUINT_TO_POINTER (2));
1734
1735   array = g_hash_table_get_values_as_ptr_array (table);
1736   g_clear_pointer (&table, g_hash_table_unref);
1737
1738   g_assert_cmpint (array->len, ==, 2);
1739   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (1), NULL));
1740   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (2), NULL));
1741
1742   g_assert_true (
1743     memcmp ((gpointer []) { GUINT_TO_POINTER (1), GUINT_TO_POINTER (2) },
1744             array->pdata, array->len * sizeof (gpointer)) == 0 ||
1745     memcmp ((gpointer []) { GUINT_TO_POINTER (2), GUINT_TO_POINTER (1) },
1746             array->pdata, array->len * sizeof (gpointer)) == 0
1747   );
1748
1749   g_clear_pointer (&array, g_ptr_array_unref);
1750 }
1751
1752 static void
1753 test_steal_all_keys (void)
1754 {
1755   GHashTable *table;
1756   GPtrArray *array;
1757
1758   table = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1759   g_hash_table_insert (table, g_strdup ("xyz"), GUINT_TO_POINTER (0));
1760   g_hash_table_insert (table, g_strdup ("xyz"), GUINT_TO_POINTER (1));
1761   g_hash_table_insert (table, g_strdup ("abc"), GUINT_TO_POINTER (2));
1762
1763   array = g_hash_table_steal_all_keys (table);
1764   g_assert_cmpuint (g_hash_table_size (table), ==, 0);
1765
1766   g_hash_table_insert (table, g_strdup ("do-not-leak-me"), GUINT_TO_POINTER (5));
1767   g_clear_pointer (&table, g_hash_table_unref);
1768
1769   g_assert_cmpint (array->len, ==, 2);
1770   g_ptr_array_add (array, NULL);
1771
1772   g_assert_true (
1773     g_strv_equal ((const gchar * const[]) { "xyz", "abc", NULL },
1774                   (const gchar * const*) array->pdata) ||
1775     g_strv_equal ((const gchar * const[]) { "abc", "xyz", NULL },
1776                   (const gchar * const*) array->pdata)
1777   );
1778
1779   g_clear_pointer (&array, g_ptr_array_unref);
1780
1781   table = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, g_free);
1782   g_hash_table_insert (table, GUINT_TO_POINTER (0), g_strdup ("xyz"));
1783   g_hash_table_insert (table, GUINT_TO_POINTER (1), g_strdup ("xyz"));
1784   g_hash_table_insert (table, GUINT_TO_POINTER (2), g_strdup ("abc"));
1785
1786   array = g_hash_table_steal_all_keys (table);
1787   g_assert_cmpuint (g_hash_table_size (table), ==, 0);
1788
1789   g_hash_table_insert (table, GUINT_TO_POINTER (5), g_strdup ("do-not-leak-me"));
1790   g_clear_pointer (&table, g_hash_table_unref);
1791
1792   g_assert_cmpint (array->len, ==, 3);
1793   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (0), NULL));
1794   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (1), NULL));
1795   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (2), NULL));
1796
1797   g_clear_pointer (&array, g_ptr_array_unref);
1798 }
1799
1800 static void
1801 test_steal_all_values (void)
1802 {
1803   GHashTable *table;
1804   GPtrArray *array;
1805
1806   table = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1807   g_hash_table_insert (table, g_strdup ("xyz"), GUINT_TO_POINTER (0));
1808   g_hash_table_insert (table, g_strdup ("xyz"), GUINT_TO_POINTER (1));
1809   g_hash_table_insert (table, g_strdup ("abc"), GUINT_TO_POINTER (2));
1810
1811   array = g_hash_table_steal_all_values (table);
1812   g_assert_cmpuint (g_hash_table_size (table), ==, 0);
1813
1814   g_hash_table_insert (table, g_strdup ("do-not-leak-me"), GUINT_TO_POINTER (5));
1815   g_clear_pointer (&table, g_hash_table_unref);
1816
1817   g_assert_cmpint (array->len, ==, 2);
1818   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (1), NULL));
1819   g_assert_true (g_ptr_array_find (array, GUINT_TO_POINTER (2), NULL));
1820
1821   g_assert_true (
1822     memcmp ((gpointer []) { GUINT_TO_POINTER (1), GUINT_TO_POINTER (2) },
1823             array->pdata, array->len * sizeof (gpointer)) == 0 ||
1824     memcmp ((gpointer []) { GUINT_TO_POINTER (2), GUINT_TO_POINTER (1) },
1825             array->pdata, array->len * sizeof (gpointer)) == 0
1826   );
1827
1828   g_clear_pointer (&array, g_ptr_array_unref);
1829
1830   table = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, g_free);
1831   g_hash_table_insert (table, GUINT_TO_POINTER (0), g_strdup ("xyz"));
1832   g_hash_table_insert (table, GUINT_TO_POINTER (1), g_strdup ("foo"));
1833   g_hash_table_insert (table, GUINT_TO_POINTER (2), g_strdup ("abc"));
1834
1835   array = g_hash_table_steal_all_values (table);
1836   g_assert_cmpuint (g_hash_table_size (table), ==, 0);
1837
1838   g_hash_table_insert (table, GUINT_TO_POINTER (5), g_strdup ("do-not-leak-me"));
1839   g_clear_pointer (&table, g_hash_table_unref);
1840
1841   g_assert_cmpint (array->len, ==, 3);
1842   g_assert_true (
1843     g_ptr_array_find_with_equal_func (array, "xyz", g_str_equal, NULL));
1844   g_assert_true (
1845     g_ptr_array_find_with_equal_func (array, "foo", g_str_equal, NULL));
1846   g_assert_true (
1847     g_ptr_array_find_with_equal_func (array, "abc", g_str_equal, NULL));
1848
1849   g_clear_pointer (&array, g_ptr_array_unref);
1850 }
1851
1852 static gboolean
1853 is_prime (guint p)
1854 {
1855   guint i;
1856
1857   if (p % 2 == 0)
1858     return FALSE;
1859
1860   i = 3;
1861   while (TRUE)
1862     {
1863       if (i * i > p)
1864         return TRUE;
1865
1866       if (p % i == 0)
1867         return FALSE;
1868
1869       i += 2;
1870     }
1871 }
1872
1873 static void
1874 test_primes (void)
1875 {
1876   guint p, q;
1877   gdouble r, min, max;
1878
1879   max = 1.0;
1880   min = 10.0;
1881   q = 1;
1882   while (1) {
1883     p = q;
1884     q = g_spaced_primes_closest (p);
1885     g_assert (is_prime (q));
1886     if (p == 1) continue;
1887     if (q == p) break;
1888     r = q / (gdouble) p;
1889     min = MIN (min, r);
1890     max = MAX (max, r);
1891   };
1892
1893   g_assert_cmpfloat (1.3, <, min);
1894   g_assert_cmpfloat (max, <, 2.0);
1895 }
1896
1897 int
1898 main (int argc, char *argv[])
1899 {
1900   g_test_init (&argc, &argv, NULL);
1901
1902   g_test_add_func ("/hash/misc", test_hash_misc);
1903   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1904   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1905   g_test_add_func ("/hash/direct", direct_hash_test);
1906   g_test_add_func ("/hash/direct2", direct_hash_test2);
1907   g_test_add_func ("/hash/int", int_hash_test);
1908   g_test_add_func ("/hash/int64", int64_hash_test);
1909   g_test_add_func ("/hash/int64/collisions", int64_hash_collision_test);
1910   g_test_add_func ("/hash/double", double_hash_test);
1911   g_test_add_func ("/hash/double/collisions", double_hash_collision_test);
1912   g_test_add_func ("/hash/string", string_hash_test);
1913   g_test_add_func ("/hash/set", set_hash_test);
1914   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1915   g_test_add_func ("/hash/ref", test_hash_ref);
1916   g_test_add_func ("/hash/remove-all", test_remove_all);
1917   g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
1918   g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
1919   g_test_add_func ("/hash/find", test_find);
1920   g_test_add_func ("/hash/foreach", test_foreach);
1921   g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1922   g_test_add_func ("/hash/steal-extended", test_steal_extended);
1923   g_test_add_func ("/hash/steal-extended/optional", test_steal_extended_optional);
1924   g_test_add_func ("/hash/steal-all-keys", test_steal_all_keys);
1925   g_test_add_func ("/hash/steal-all-values", test_steal_all_values);
1926   g_test_add_func ("/hash/lookup-extended", test_lookup_extended);
1927   g_test_add_func ("/hash/new-similar", test_new_similar);
1928
1929   /* tests for individual bugs */
1930   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1931   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1932   g_test_add_func ("/hash/consistency", test_internal_consistency);
1933   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1934   g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1935   g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1936   g_test_add_func ("/hash/get-keys-as-ptr-array", test_set_get_keys_as_ptr_array);
1937   g_test_add_func ("/hash/get-values-as-ptr-array", test_set_get_values_as_ptr_array);
1938   g_test_add_func ("/hash/primes", test_primes);
1939
1940   return g_test_run ();
1941
1942 }