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.1 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, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 /*
  20  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  21  * file for a list of people on the GLib Team.  See the ChangeLog
  22  * files for a list of changes.  These files are distributed with
  23  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  24  */
  25
  26 #undef G_DISABLE_ASSERT
  27 #undef G_LOG_DOMAIN
  28
  29 #include <config.h>
  30
  31 #include <stdio.h>
  32 #include <string.h>
  33 #include <stdlib.h>
  34
  35 #include <glib.h>
  36
  37
  38
  39 int 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       array[i] = i;
  49       g_hash_table_insert (hash_table, &array[i], &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   gint 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 double_hash_test (void)
 464 {
 465   gint       i, rc;
 466   GHashTable     *h;
 467   gdouble values[20];
 468   gdouble key;
 469
 470   h = g_hash_table_new (g_double_hash, g_double_equal);
 471   g_assert (h != NULL);
 472   for (i = 0; i < 20; i++)
 473     {
 474       values[i] = i + 42.5;
 475       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 476     }
 477
 478   g_assert (g_hash_table_size (h) == 20);
 479
 480   for (i = 0; i < 20; i++)
 481     {
 482       key = i + 42.5;
 483       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 484
 485       g_assert_cmpint (rc, ==, i + 42);
 486     }
 487
 488   g_hash_table_destroy (h);
 489 }
 490
 491 static void
 492 string_free (gpointer data)
 493 {
 494   GString *s = data;
 495
 496   g_string_free (s, TRUE);
 497 }
 498
 499 static void
 500 string_hash_test (void)
 501 {
 502   gint       i, rc;
 503   GHashTable     *h;
 504   GString *s;
 505
 506   h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 507   g_assert (h != NULL);
 508   for (i = 0; i < 20; i++)
 509     {
 510       s = g_string_new ("");
 511       g_string_append_printf (s, "%d", i + 42);
 512       g_string_append_c (s, '.');
 513       g_string_prepend_unichar (s, 0x2301);
 514       g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 515     }
 516
 517   g_assert (g_hash_table_size (h) == 20);
 518
 519   s = g_string_new ("");
 520   for (i = 0; i < 20; i++)
 521     {
 522       g_string_assign (s, "");
 523       g_string_append_printf (s, "%d", i + 42);
 524       g_string_append_c (s, '.');
 525       g_string_prepend_unichar (s, 0x2301);
 526       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 527
 528       g_assert_cmpint (rc, ==, i + 42);
 529     }
 530
 531   g_string_free (s, TRUE);
 532   g_hash_table_destroy (h);
 533 }
 534
 535 static void
 536 set_check (gpointer key,
 537            gpointer value,
 538            gpointer user_data)
 539 {
 540   int *pi = user_data;
 541   if (key != value)
 542     g_assert_not_reached ();
 543
 544   g_assert_cmpint (atoi (key) % 7, ==, 2);
 545
 546   (*pi)++;
 547 }
 548
 549 static void
 550 set_hash_test (void)
 551 {
 552   GHashTable *hash_table =
 553     g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 554   int i;
 555
 556   for (i = 2; i < 5000; i += 7)
 557     {
 558       char *s = g_strdup_printf ("%d", i);
 559       g_assert (g_hash_table_add (hash_table, s));
 560     }
 561
 562   g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
 563
 564   i = 0;
 565   g_hash_table_foreach (hash_table, set_check, &i);
 566   g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
 567
 568   g_assert (g_hash_table_contains (hash_table, "2"));
 569   g_assert (g_hash_table_contains (hash_table, "9"));
 570   g_assert (!g_hash_table_contains (hash_table, "a"));
 571
 572   /* this will cause the hash table to loose set nature */
 573   g_assert (g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 574   g_assert (!g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 575
 576   g_assert (g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 577   g_assert (!g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 578
 579   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 580   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 581
 582   g_hash_table_destroy (hash_table);
 583 }
 584
 585
 586 static void
 587 test_hash_misc (void)
 588 {
 589   GHashTable *hash_table;
 590   gint i;
 591   gint value = 120;
 592   gint *pvalue;
 593   GList *keys, *values;
 594   gint keys_len, values_len;
 595   GHashTableIter iter;
 596   gpointer ikey, ivalue;
 597   int result_array[10000];
 598   int n_array[1];
 599
 600   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 601   fill_hash_table_and_array (hash_table);
 602   pvalue = g_hash_table_find (hash_table, find_first, &value);
 603   if (!pvalue || *pvalue != value)
 604     g_assert_not_reached();
 605
 606   keys = g_hash_table_get_keys (hash_table);
 607   if (!keys)
 608     g_assert_not_reached ();
 609
 610   values = g_hash_table_get_values (hash_table);
 611   if (!values)
 612     g_assert_not_reached ();
 613
 614   keys_len = g_list_length (keys);
 615   values_len = g_list_length (values);
 616   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 617     g_assert_not_reached ();
 618
 619   g_list_free (keys);
 620   g_list_free (values);
 621
 622   init_result_array (result_array);
 623   g_hash_table_iter_init (&iter, hash_table);
 624   for (i = 0; i < 10000; i++)
 625     {
 626       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 627
 628       handle_pair (ikey, ivalue, result_array);
 629
 630       if (i % 2)
 631         g_hash_table_iter_remove (&iter);
 632     }
 633   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 634   g_assert (g_hash_table_size (hash_table) == 5000);
 635   verify_result_array (result_array);
 636
 637   fill_hash_table_and_array (hash_table);
 638
 639   init_result_array (result_array);
 640   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 641   verify_result_array (result_array);
 642
 643   for (i = 0; i < 10000; i++)
 644     g_hash_table_remove (hash_table, &array[i]);
 645
 646   fill_hash_table_and_array (hash_table);
 647
 648   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 649       g_hash_table_size (hash_table) != 5000)
 650     g_assert_not_reached();
 651
 652   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 653   g_hash_table_destroy (hash_table);
 654
 655   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 656   fill_hash_table_and_array (hash_table);
 657
 658   n_array[0] = 1;
 659
 660   g_hash_table_iter_init (&iter, hash_table);
 661   for (i = 0; i < 10000; i++)
 662     {
 663       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 664       g_hash_table_iter_replace (&iter, &n_array[0]);
 665     }
 666
 667   g_hash_table_iter_init (&iter, hash_table);
 668   for (i = 0; i < 10000; i++)
 669     {
 670       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 671
 672       g_assert (ivalue == &n_array[0]);
 673     }
 674
 675   g_hash_table_destroy (hash_table);
 676 }
 677
 678 static gint destroy_counter;
 679
 680 static void
 681 value_destroy (gpointer value)
 682 {
 683   destroy_counter++;
 684 }
 685
 686 static void
 687 test_hash_ref (void)
 688 {
 689   GHashTable *h;
 690   GHashTableIter iter;
 691   gchar *key, *value;
 692   gboolean abc_seen = FALSE;
 693   gboolean cde_seen = FALSE;
 694   gboolean xyz_seen = FALSE;
 695
 696   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 697   g_hash_table_insert (h, "abc", "ABC");
 698   g_hash_table_insert (h, "cde", "CDE");
 699   g_hash_table_insert (h, "xyz", "XYZ");
 700
 701   g_assert_cmpint (g_hash_table_size (h), == , 3);
 702
 703   g_hash_table_iter_init (&iter, h);
 704
 705   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 706     {
 707       if (strcmp (key, "abc") == 0)
 708         {
 709           g_assert_cmpstr (value, ==, "ABC");
 710           abc_seen = TRUE;
 711           g_hash_table_iter_steal (&iter);
 712         }
 713       else if (strcmp (key, "cde") == 0)
 714         {
 715           g_assert_cmpstr (value, ==, "CDE");
 716           cde_seen = TRUE;
 717         }
 718       else if (strcmp (key, "xyz") == 0)
 719         {
 720           g_assert_cmpstr (value, ==, "XYZ");
 721           xyz_seen = TRUE;
 722         }
 723     }
 724   g_assert_cmpint (destroy_counter, ==, 0);
 725
 726   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 727   g_assert (abc_seen && cde_seen && xyz_seen);
 728   g_assert_cmpint (g_hash_table_size (h), == , 2);
 729
 730   g_hash_table_ref (h);
 731   g_hash_table_destroy (h);
 732   g_assert_cmpint (g_hash_table_size (h), == , 0);
 733   g_assert_cmpint (destroy_counter, ==, 2);
 734   g_hash_table_insert (h, "uvw", "UVW");
 735   g_hash_table_unref (h);
 736   g_assert_cmpint (destroy_counter, ==, 3);
 737 }
 738
 739 static guint
 740 null_safe_str_hash (gconstpointer key)
 741 {
 742   if (key == NULL)
 743     return 0;
 744   else
 745     return g_str_hash (key);
 746 }
 747
 748 static gboolean
 749 null_safe_str_equal (gconstpointer a, gconstpointer b)
 750 {
 751   return g_strcmp0 (a, b) == 0;
 752 }
 753
 754 static void
 755 test_lookup_null_key (void)
 756 {
 757   GHashTable *h;
 758   gboolean res;
 759   gpointer key;
 760   gpointer value;
 761
 762   g_test_bug ("642944");
 763
 764   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 765   g_hash_table_insert (h, "abc", "ABC");
 766
 767   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 768   g_assert (!res);
 769
 770   g_hash_table_insert (h, NULL, "NULL");
 771
 772   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 773   g_assert (res);
 774   g_assert_cmpstr (value, ==, "NULL");
 775
 776   g_hash_table_unref (h);
 777 }
 778
 779 static gint destroy_key_counter;
 780
 781 static void
 782 key_destroy (gpointer key)
 783 {
 784   destroy_key_counter++;
 785 }
 786
 787 static void
 788 test_remove_all (void)
 789 {
 790   GHashTable *h;
 791   gboolean res;
 792
 793   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 794
 795   g_hash_table_insert (h, "abc", "cde");
 796   g_hash_table_insert (h, "cde", "xyz");
 797   g_hash_table_insert (h, "xyz", "abc");
 798
 799   destroy_counter = 0;
 800   destroy_key_counter = 0;
 801
 802   g_hash_table_steal_all (h);
 803   g_assert_cmpint (destroy_counter, ==, 0);
 804   g_assert_cmpint (destroy_key_counter, ==, 0);
 805
 806   /* Test stealing on an empty hash table. */
 807   g_hash_table_steal_all (h);
 808   g_assert_cmpint (destroy_counter, ==, 0);
 809   g_assert_cmpint (destroy_key_counter, ==, 0);
 810
 811   g_hash_table_insert (h, "abc", "ABC");
 812   g_hash_table_insert (h, "cde", "CDE");
 813   g_hash_table_insert (h, "xyz", "XYZ");
 814
 815   res = g_hash_table_steal (h, "nosuchkey");
 816   g_assert (!res);
 817   g_assert_cmpint (destroy_counter, ==, 0);
 818   g_assert_cmpint (destroy_key_counter, ==, 0);
 819
 820   res = g_hash_table_steal (h, "xyz");
 821   g_assert (res);
 822   g_assert_cmpint (destroy_counter, ==, 0);
 823   g_assert_cmpint (destroy_key_counter, ==, 0);
 824
 825   g_hash_table_remove_all (h);
 826   g_assert_cmpint (destroy_counter, ==, 2);
 827   g_assert_cmpint (destroy_key_counter, ==, 2);
 828
 829   g_hash_table_remove_all (h);
 830   g_assert_cmpint (destroy_counter, ==, 2);
 831   g_assert_cmpint (destroy_key_counter, ==, 2);
 832
 833   g_hash_table_unref (h);
 834 }
 835
 836 GHashTable *recursive_destruction_table = NULL;
 837 static void
 838 recursive_value_destroy (gpointer value)
 839 {
 840   destroy_counter++;
 841
 842   if (recursive_destruction_table)
 843     g_hash_table_remove (recursive_destruction_table, value);
 844 }
 845
 846 static void
 847 test_recursive_remove_all_subprocess (void)
 848 {
 849   GHashTable *h;
 850
 851   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
 852   recursive_destruction_table = h;
 853
 854   /* Add more items compared to test_remove_all, as it would not fail otherwise. */
 855   g_hash_table_insert (h, "abc", "cde");
 856   g_hash_table_insert (h, "cde", "fgh");
 857   g_hash_table_insert (h, "fgh", "ijk");
 858   g_hash_table_insert (h, "ijk", "lmn");
 859   g_hash_table_insert (h, "lmn", "opq");
 860   g_hash_table_insert (h, "opq", "rst");
 861   g_hash_table_insert (h, "rst", "uvw");
 862   g_hash_table_insert (h, "uvw", "xyz");
 863   g_hash_table_insert (h, "xyz", "abc");
 864
 865   destroy_counter = 0;
 866   destroy_key_counter = 0;
 867
 868   g_hash_table_remove_all (h);
 869   g_assert_cmpint (destroy_counter, ==, 9);
 870   g_assert_cmpint (destroy_key_counter, ==, 9);
 871
 872   g_hash_table_unref (h);
 873 }
 874
 875 static void
 876 test_recursive_remove_all (void)
 877 {
 878   g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000, 0);
 879   g_test_trap_assert_passed ();
 880 }
 881
 882 typedef struct {
 883   gint ref_count;
 884   const gchar *key;
 885 } RefCountedKey;
 886
 887 static guint
 888 hash_func (gconstpointer key)
 889 {
 890   const RefCountedKey *rkey = key;
 891
 892   return g_str_hash (rkey->key);
 893 }
 894
 895 static gboolean
 896 eq_func (gconstpointer a, gconstpointer b)
 897 {
 898   const RefCountedKey *aa = a;
 899   const RefCountedKey *bb = b;
 900
 901   return g_strcmp0 (aa->key, bb->key) == 0;
 902 }
 903
 904 static void
 905 key_unref (gpointer data)
 906 {
 907   RefCountedKey *key = data;
 908
 909   g_assert (key->ref_count > 0);
 910
 911   key->ref_count -= 1;
 912
 913   if (key->ref_count == 0)
 914     g_free (key);
 915 }
 916
 917 static RefCountedKey *
 918 key_ref (RefCountedKey *key)
 919 {
 920   key->ref_count += 1;
 921
 922   return key;
 923 }
 924
 925 static RefCountedKey *
 926 key_new (const gchar *key)
 927 {
 928   RefCountedKey *rkey;
 929
 930   rkey = g_new (RefCountedKey, 1);
 931
 932   rkey->ref_count = 1;
 933   rkey->key = key;
 934
 935   return rkey;
 936 }
 937
 938 static void
 939 set_ref_hash_test (void)
 940 {
 941   GHashTable *h;
 942   RefCountedKey *key1;
 943   RefCountedKey *key2;
 944
 945   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 946
 947   key1 = key_new ("a");
 948   key2 = key_new ("a");
 949
 950   g_assert_cmpint (key1->ref_count, ==, 1);
 951   g_assert_cmpint (key2->ref_count, ==, 1);
 952
 953   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 954
 955   g_assert_cmpint (key1->ref_count, ==, 3);
 956   g_assert_cmpint (key2->ref_count, ==, 1);
 957
 958   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 959
 960   g_assert_cmpint (key1->ref_count, ==, 1);
 961   g_assert_cmpint (key2->ref_count, ==, 3);
 962
 963   g_hash_table_remove (h, key1);
 964
 965   g_assert_cmpint (key1->ref_count, ==, 1);
 966   g_assert_cmpint (key2->ref_count, ==, 1);
 967
 968   g_hash_table_unref (h);
 969
 970   key_unref (key1);
 971   key_unref (key2);
 972 }
 973
 974 GHashTable *h;
 975
 976 typedef struct {
 977     gchar *string;
 978     gboolean freed;
 979 } FakeFreeData;
 980
 981 GPtrArray *fake_free_data;
 982
 983 static void
 984 fake_free (gpointer dead)
 985 {
 986   guint i;
 987
 988   for (i = 0; i < fake_free_data->len; i++)
 989     {
 990       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 991
 992       if (ffd->string == (gchar *) dead)
 993         {
 994           g_assert (!ffd->freed);
 995           ffd->freed = TRUE;
 996           return;
 997         }
 998     }
 999
1000   g_assert_not_reached ();
1001 }
1002
1003 static void
1004 value_destroy_insert (gpointer value)
1005 {
1006   g_hash_table_remove_all (h);
1007 }
1008
1009 static void
1010 test_destroy_modify (void)
1011 {
1012   FakeFreeData *ffd;
1013   guint i;
1014
1015   g_test_bug ("650459");
1016
1017   fake_free_data = g_ptr_array_new ();
1018
1019   h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
1020
1021   ffd = g_new0 (FakeFreeData, 1);
1022   ffd->string = g_strdup ("a");
1023   g_ptr_array_add (fake_free_data, ffd);
1024   g_hash_table_insert (h, ffd->string, "b");
1025
1026   ffd = g_new0 (FakeFreeData, 1);
1027   ffd->string = g_strdup ("c");
1028   g_ptr_array_add (fake_free_data, ffd);
1029   g_hash_table_insert (h, ffd->string, "d");
1030
1031   ffd = g_new0 (FakeFreeData, 1);
1032   ffd->string = g_strdup ("e");
1033   g_ptr_array_add (fake_free_data, ffd);
1034   g_hash_table_insert (h, ffd->string, "f");
1035
1036   ffd = g_new0 (FakeFreeData, 1);
1037   ffd->string = g_strdup ("g");
1038   g_ptr_array_add (fake_free_data, ffd);
1039   g_hash_table_insert (h, ffd->string, "h");
1040
1041   ffd = g_new0 (FakeFreeData, 1);
1042   ffd->string = g_strdup ("h");
1043   g_ptr_array_add (fake_free_data, ffd);
1044   g_hash_table_insert (h, ffd->string, "k");
1045
1046   ffd = g_new0 (FakeFreeData, 1);
1047   ffd->string = g_strdup ("a");
1048   g_ptr_array_add (fake_free_data, ffd);
1049   g_hash_table_insert (h, ffd->string, "c");
1050
1051   g_hash_table_remove (h, "c");
1052
1053   /* that removed everything... */
1054   for (i = 0; i < fake_free_data->len; i++)
1055     {
1056       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1057
1058       g_assert (ffd->freed);
1059       g_free (ffd->string);
1060       g_free (ffd);
1061     }
1062
1063   g_ptr_array_unref (fake_free_data);
1064
1065   /* ... so this is a no-op */
1066   g_hash_table_remove (h, "e");
1067
1068   g_hash_table_unref (h);
1069 }
1070
1071 static gboolean
1072 find_str (gpointer key, gpointer value, gpointer data)
1073 {
1074   return g_str_equal (key, data);
1075 }
1076
1077 static void
1078 test_find (void)
1079 {
1080   GHashTable *hash;
1081   const gchar *value;
1082
1083   hash = g_hash_table_new (g_str_hash, g_str_equal);
1084
1085   g_hash_table_insert (hash, "a", "A");
1086   g_hash_table_insert (hash, "b", "B");
1087   g_hash_table_insert (hash, "c", "C");
1088   g_hash_table_insert (hash, "d", "D");
1089   g_hash_table_insert (hash, "e", "E");
1090   g_hash_table_insert (hash, "f", "F");
1091
1092   value = g_hash_table_find (hash, find_str, "a");
1093   g_assert_cmpstr (value, ==, "A");
1094
1095   value = g_hash_table_find (hash, find_str, "b");
1096   g_assert_cmpstr (value, ==, "B");
1097
1098   value = g_hash_table_find (hash, find_str, "c");
1099   g_assert_cmpstr (value, ==, "C");
1100
1101   value = g_hash_table_find (hash, find_str, "d");
1102   g_assert_cmpstr (value, ==, "D");
1103
1104   value = g_hash_table_find (hash, find_str, "e");
1105   g_assert_cmpstr (value, ==, "E");
1106
1107   value = g_hash_table_find (hash, find_str, "f");
1108   g_assert_cmpstr (value, ==, "F");
1109
1110   value = g_hash_table_find (hash, find_str, "0");
1111   g_assert (value == NULL);
1112
1113   g_hash_table_unref (hash);
1114 }
1115
1116 gboolean seen_key[6];
1117
1118 static void
1119 foreach_func (gpointer key, gpointer value, gpointer data)
1120 {
1121   seen_key[((char*)key)[0] - 'a'] = TRUE;
1122 }
1123
1124 static void
1125 test_foreach (void)
1126 {
1127   GHashTable *hash;
1128   gint i;
1129
1130   hash = g_hash_table_new (g_str_hash, g_str_equal);
1131
1132   g_hash_table_insert (hash, "a", "A");
1133   g_hash_table_insert (hash, "b", "B");
1134   g_hash_table_insert (hash, "c", "C");
1135   g_hash_table_insert (hash, "d", "D");
1136   g_hash_table_insert (hash, "e", "E");
1137   g_hash_table_insert (hash, "f", "F");
1138
1139   for (i = 0; i < 6; i++)
1140     seen_key[i] = FALSE;
1141
1142   g_hash_table_foreach (hash, foreach_func, NULL);
1143
1144   for (i = 0; i < 6; i++)
1145     g_assert (seen_key[i]);
1146
1147   g_hash_table_unref (hash);
1148 }
1149
1150 static gboolean
1151 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1152 {
1153   GHashTable *hash2 = data;
1154
1155   if (strstr ("ace", (gchar*)key))
1156     {
1157       g_hash_table_insert (hash2, key, value);
1158       return TRUE;
1159     }
1160
1161   return FALSE;
1162 }
1163
1164
1165 static void
1166 test_foreach_steal (void)
1167 {
1168   GHashTable *hash;
1169   GHashTable *hash2;
1170
1171   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1172   hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1173
1174   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1175   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1176   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1177   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1178   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1179   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1180
1181   g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1182
1183   g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1184   g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1185
1186   g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1187   g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1188   g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1189   g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1190   g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1191   g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1192
1193   g_hash_table_unref (hash);
1194   g_hash_table_unref (hash2);
1195 }
1196
1197 /* Test g_hash_table_steal_extended() works properly with existing and
1198  * non-existing keys. */
1199 static void
1200 test_steal_extended (void)
1201 {
1202   GHashTable *hash;
1203   gchar *stolen_key = NULL, *stolen_value = NULL;
1204
1205   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1206
1207   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1208   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1209   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1210   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1211   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1212   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1213
1214   g_assert_true (g_hash_table_steal_extended (hash, "a",
1215                                               (gpointer *) &stolen_key,
1216                                               (gpointer *) &stolen_value));
1217   g_assert_cmpstr (stolen_key, ==, "a");
1218   g_assert_cmpstr (stolen_value, ==, "A");
1219   g_clear_pointer (&stolen_key, g_free);
1220   g_clear_pointer (&stolen_value, g_free);
1221
1222   g_assert_cmpuint (g_hash_table_size (hash), ==, 5);
1223
1224   g_assert_false (g_hash_table_steal_extended (hash, "a",
1225                                                (gpointer *) &stolen_key,
1226                                                (gpointer *) &stolen_value));
1227   g_assert_null (stolen_key);
1228   g_assert_null (stolen_value);
1229
1230   g_assert_false (g_hash_table_steal_extended (hash, "never a key",
1231                                                (gpointer *) &stolen_key,
1232                                                (gpointer *) &stolen_value));
1233   g_assert_null (stolen_key);
1234   g_assert_null (stolen_value);
1235
1236   g_assert_cmpuint (g_hash_table_size (hash), ==, 5);
1237
1238   g_hash_table_unref (hash);
1239 }
1240
1241 /* Test that passing %NULL to the optional g_hash_table_steal_extended()
1242  * arguments works. */
1243 static void
1244 test_steal_extended_optional (void)
1245 {
1246   GHashTable *hash;
1247   const gchar *stolen_key = NULL, *stolen_value = NULL;
1248
1249   hash = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, NULL);
1250
1251   g_hash_table_insert (hash, "b", "B");
1252   g_hash_table_insert (hash, "c", "C");
1253   g_hash_table_insert (hash, "d", "D");
1254   g_hash_table_insert (hash, "e", "E");
1255   g_hash_table_insert (hash, "f", "F");
1256
1257   g_assert_true (g_hash_table_steal_extended (hash, "b",
1258                                               (gpointer *) &stolen_key,
1259                                               NULL));
1260   g_assert_cmpstr (stolen_key, ==, "b");
1261
1262   g_assert_cmpuint (g_hash_table_size (hash), ==, 4);
1263
1264   g_assert_false (g_hash_table_steal_extended (hash, "b",
1265                                                (gpointer *) &stolen_key,
1266                                                NULL));
1267   g_assert_null (stolen_key);
1268
1269   g_assert_true (g_hash_table_steal_extended (hash, "c",
1270                                               NULL,
1271                                               (gpointer *) &stolen_value));
1272   g_assert_cmpstr (stolen_value, ==, "C");
1273
1274   g_assert_cmpuint (g_hash_table_size (hash), ==, 3);
1275
1276   g_assert_false (g_hash_table_steal_extended (hash, "c",
1277                                                NULL,
1278                                                (gpointer *) &stolen_value));
1279   g_assert_null (stolen_value);
1280
1281   g_assert_true (g_hash_table_steal_extended (hash, "d", NULL, NULL));
1282
1283   g_assert_cmpuint (g_hash_table_size (hash), ==, 2);
1284
1285   g_assert_false (g_hash_table_steal_extended (hash, "d", NULL, NULL));
1286
1287   g_assert_cmpuint (g_hash_table_size (hash), ==, 2);
1288
1289   g_hash_table_unref (hash);
1290 }
1291
1292 /* Test g_hash_table_lookup_extended() works with its optional parameters
1293  * sometimes set to %NULL. */
1294 static void
1295 test_lookup_extended (void)
1296 {
1297   GHashTable *hash;
1298   const gchar *original_key = NULL, *value = NULL;
1299
1300   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1301
1302   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1303   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1304   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1305   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1306   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1307   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1308
1309   g_assert_true (g_hash_table_lookup_extended (hash, "a",
1310                                                (gpointer *) &original_key,
1311                                                (gpointer *) &value));
1312   g_assert_cmpstr (original_key, ==, "a");
1313   g_assert_cmpstr (value, ==, "A");
1314
1315   g_assert_true (g_hash_table_lookup_extended (hash, "b",
1316                                                NULL,
1317                                                (gpointer *) &value));
1318   g_assert_cmpstr (value, ==, "B");
1319
1320   g_assert_true (g_hash_table_lookup_extended (hash, "c",
1321                                                (gpointer *) &original_key,
1322                                                NULL));
1323   g_assert_cmpstr (original_key, ==, "c");
1324
1325   g_assert_true (g_hash_table_lookup_extended (hash, "d", NULL, NULL));
1326
1327   g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
1328                                                 (gpointer *) &original_key,
1329                                                 (gpointer *) &value));
1330   g_assert_null (original_key);
1331   g_assert_null (value);
1332
1333   g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
1334                                                 NULL,
1335                                                 (gpointer *) &value));
1336   g_assert_null (value);
1337
1338   g_assert_false (g_hash_table_lookup_extended (hash, "not a key",
1339                                                 (gpointer *) &original_key,
1340                                                 NULL));
1341   g_assert_null (original_key);
1342
1343   g_assert_false (g_hash_table_lookup_extended (hash, "not a key", NULL, NULL));
1344
1345   g_hash_table_unref (hash);
1346 }
1347
1348 struct _GHashTable
1349 {
1350   gint             size;
1351   gint             mod;
1352   guint            mask;
1353   gint             nnodes;
1354   gint             noccupied;  /* nnodes + tombstones */
1355
1356   guint            have_big_keys : 1;
1357   guint            have_big_values : 1;
1358
1359   gpointer        *keys;
1360   guint           *hashes;
1361   gpointer        *values;
1362
1363   GHashFunc        hash_func;
1364   GEqualFunc       key_equal_func;
1365   volatile gint    ref_count;
1366
1367 #ifndef G_DISABLE_ASSERT
1368   int              version;
1369 #endif
1370   GDestroyNotify   key_destroy_func;
1371   GDestroyNotify   value_destroy_func;
1372 };
1373
1374 static void
1375 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1376 {
1377   gint i;
1378
1379   *unused = 0;
1380   *occupied = 0;
1381   *tombstones = 0;
1382   for (i = 0; i < h->size; i++)
1383     {
1384       if (h->hashes[i] == 0)
1385         (*unused)++;
1386       else if (h->hashes[i] == 1)
1387         (*tombstones)++;
1388       else
1389         (*occupied)++;
1390     }
1391 }
1392
1393 #define BIG_ENTRY_SIZE (SIZEOF_VOID_P)
1394 #define SMALL_ENTRY_SIZE (SIZEOF_INT)
1395
1396 #if SMALL_ENTRY_SIZE < BIG_ENTRY_SIZE
1397 # define USE_SMALL_ARRAYS
1398 #endif
1399
1400 static gpointer
1401 fetch_key_or_value (gpointer a, guint index, gboolean is_big)
1402 {
1403 #ifdef USE_SMALL_ARRAYS
1404   return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
1405 #else
1406   return *(((gpointer *) a) + index);
1407 #endif
1408 }
1409
1410 static void
1411 check_data (GHashTable *h)
1412 {
1413   gint i;
1414
1415   for (i = 0; i < h->size; i++)
1416     {
1417       if (h->hashes[i] >= 2)
1418         {
1419           g_assert_cmpint (h->hashes[i], ==, h->hash_func (fetch_key_or_value (h->keys, i, h->have_big_keys)));
1420         }
1421     }
1422 }
1423
1424 static void
1425 check_consistency (GHashTable *h)
1426 {
1427   gint unused;
1428   gint occupied;
1429   gint tombstones;
1430
1431   count_keys (h, &unused, &occupied, &tombstones);
1432
1433   g_assert_cmpint (occupied, ==, h->nnodes);
1434   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1435   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1436
1437   check_data (h);
1438 }
1439
1440 static void
1441 check_counts (GHashTable *h, gint occupied, gint tombstones)
1442 {
1443   g_assert_cmpint (occupied, ==, h->nnodes);
1444   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1445 }
1446
1447 static void
1448 trivial_key_destroy (gpointer key)
1449 {
1450 }
1451
1452 static void
1453 test_internal_consistency (void)
1454 {
1455   GHashTable *h;
1456
1457   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1458
1459   check_counts (h, 0, 0);
1460   check_consistency (h);
1461
1462   g_hash_table_insert (h, "a", "A");
1463   g_hash_table_insert (h, "b", "B");
1464   g_hash_table_insert (h, "c", "C");
1465   g_hash_table_insert (h, "d", "D");
1466   g_hash_table_insert (h, "e", "E");
1467   g_hash_table_insert (h, "f", "F");
1468
1469   check_counts (h, 6, 0);
1470   check_consistency (h);
1471
1472   g_hash_table_remove (h, "a");
1473   check_counts (h, 5, 1);
1474   check_consistency (h);
1475
1476   g_hash_table_remove (h, "b");
1477   check_counts (h, 4, 2);
1478   check_consistency (h);
1479
1480   g_hash_table_insert (h, "c", "c");
1481   check_counts (h, 4, 2);
1482   check_consistency (h);
1483
1484   g_hash_table_insert (h, "a", "A");
1485   check_counts (h, 5, 1);
1486   check_consistency (h);
1487
1488   g_hash_table_remove_all (h);
1489   check_counts (h, 0, 0);
1490   check_consistency (h);
1491
1492   g_hash_table_unref (h);
1493 }
1494
1495 static void
1496 my_key_free (gpointer v)
1497 {
1498   gchar *s = v;
1499   g_assert (s[0] != 'x');
1500   s[0] = 'x';
1501   g_free (v);
1502 }
1503
1504 static void
1505 my_value_free (gpointer v)
1506 {
1507   gchar *s = v;
1508   g_assert (s[0] != 'y');
1509   s[0] = 'y';
1510   g_free (v);
1511 }
1512
1513 static void
1514 test_iter_replace (void)
1515 {
1516   GHashTable *h;
1517   GHashTableIter iter;
1518   gpointer k, v;
1519   gchar *s;
1520
1521   g_test_bug ("662544");
1522
1523   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1524
1525   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1526   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1527   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1528
1529   g_hash_table_iter_init (&iter, h);
1530
1531   while (g_hash_table_iter_next (&iter, &k, &v))
1532     {
1533        s = (gchar*)v;
1534        g_assert (g_ascii_islower (s[0]));
1535        g_hash_table_iter_replace (&iter, g_strdup (k));
1536     }
1537
1538   g_hash_table_unref (h);
1539 }
1540
1541 static void
1542 replace_first_character (gchar *string)
1543 {
1544   string[0] = 'b';
1545 }
1546
1547 static void
1548 test_set_insert_corruption (void)
1549 {
1550   GHashTable *hash_table =
1551     g_hash_table_new_full (g_str_hash, g_str_equal,
1552         (GDestroyNotify) replace_first_character, NULL);
1553   GHashTableIter iter;
1554   gchar a[] = "foo";
1555   gchar b[] = "foo";
1556   gpointer key, value;
1557
1558   g_test_bug ("692815");
1559
1560   g_hash_table_insert (hash_table, a, a);
1561   g_assert (g_hash_table_contains (hash_table, "foo"));
1562
1563   g_hash_table_insert (hash_table, b, b);
1564
1565   g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1566   g_hash_table_iter_init (&iter, hash_table);
1567   if (!g_hash_table_iter_next (&iter, &key, &value))
1568     g_assert_not_reached();
1569
1570   /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1571    * and the sole key in 'hash_table' should be 'a'.
1572    */
1573   g_assert (key != b);
1574   g_assert (key == a);
1575
1576   g_assert_cmpstr (b, ==, "boo");
1577
1578   /* g_hash_table_insert() also says that the value should now be 'b',
1579    * which is probably not what the caller intended but is precisely what they
1580    * asked for.
1581    */
1582   g_assert (value == b);
1583
1584   /* even though the hash has now been de-set-ified: */
1585   g_assert (g_hash_table_contains (hash_table, "foo"));
1586
1587   g_hash_table_unref (hash_table);
1588 }
1589
1590 static void
1591 test_set_to_strv (void)
1592 {
1593   GHashTable *set;
1594   gchar **strv;
1595   guint n;
1596
1597   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1598   g_hash_table_add (set, g_strdup ("xyz"));
1599   g_hash_table_add (set, g_strdup ("xyz"));
1600   g_hash_table_add (set, g_strdup ("abc"));
1601   strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1602   g_hash_table_steal_all (set);
1603   g_hash_table_unref (set);
1604   g_assert_cmpint (n, ==, 2);
1605   n = g_strv_length (strv);
1606   g_assert_cmpint (n, ==, 2);
1607   if (g_str_equal (strv[0], "abc"))
1608     g_assert_cmpstr (strv[1], ==, "xyz");
1609   else
1610     {
1611     g_assert_cmpstr (strv[0], ==, "xyz");
1612     g_assert_cmpstr (strv[1], ==, "abc");
1613     }
1614   g_strfreev (strv);
1615 }
1616
1617 static gboolean
1618 is_prime (guint p)
1619 {
1620   guint i;
1621
1622   if (p % 2 == 0)
1623     return FALSE;
1624
1625   i = 3;
1626   while (TRUE)
1627     {
1628       if (i * i > p)
1629         return TRUE;
1630
1631       if (p % i == 0)
1632         return FALSE;
1633
1634       i += 2;
1635     }
1636 }
1637
1638 static void
1639 test_primes (void)
1640 {
1641   guint p, q;
1642   gdouble r, min, max;
1643
1644   max = 1.0;
1645   min = 10.0;
1646   q = 1;
1647   while (1) {
1648     p = q;
1649     q = g_spaced_primes_closest (p);
1650     g_assert (is_prime (q));
1651     if (p == 1) continue;
1652     if (q == p) break;
1653     r = q / (gdouble) p;
1654     min = MIN (min, r);
1655     max = MAX (max, r);
1656   };
1657
1658   g_assert_cmpfloat (1.3, <, min);
1659   g_assert_cmpfloat (max, <, 2.0);
1660 }
1661
1662 int
1663 main (int argc, char *argv[])
1664 {
1665   g_test_init (&argc, &argv, NULL);
1666
1667   g_test_bug_base ("http://bugzilla.gnome.org/");
1668
1669   g_test_add_func ("/hash/misc", test_hash_misc);
1670   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1671   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1672   g_test_add_func ("/hash/direct", direct_hash_test);
1673   g_test_add_func ("/hash/direct2", direct_hash_test2);
1674   g_test_add_func ("/hash/int", int_hash_test);
1675   g_test_add_func ("/hash/int64", int64_hash_test);
1676   g_test_add_func ("/hash/double", double_hash_test);
1677   g_test_add_func ("/hash/string", string_hash_test);
1678   g_test_add_func ("/hash/set", set_hash_test);
1679   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1680   g_test_add_func ("/hash/ref", test_hash_ref);
1681   g_test_add_func ("/hash/remove-all", test_remove_all);
1682   g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
1683   g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
1684   g_test_add_func ("/hash/find", test_find);
1685   g_test_add_func ("/hash/foreach", test_foreach);
1686   g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1687   g_test_add_func ("/hash/steal-extended", test_steal_extended);
1688   g_test_add_func ("/hash/steal-extended/optional", test_steal_extended_optional);
1689   g_test_add_func ("/hash/lookup-extended", test_lookup_extended);
1690
1691   /* tests for individual bugs */
1692   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1693   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1694   g_test_add_func ("/hash/consistency", test_internal_consistency);
1695   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1696   g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1697   g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1698   g_test_add_func ("/hash/primes", test_primes);
1699
1700   return g_test_run ();
1701
1702 }