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   g_hash_table_insert (h, "abc", "ABC");
 807   g_hash_table_insert (h, "cde", "CDE");
 808   g_hash_table_insert (h, "xyz", "XYZ");
 809
 810   res = g_hash_table_steal (h, "nosuchkey");
 811   g_assert (!res);
 812   g_assert_cmpint (destroy_counter, ==, 0);
 813   g_assert_cmpint (destroy_key_counter, ==, 0);
 814
 815   res = g_hash_table_steal (h, "xyz");
 816   g_assert (res);
 817   g_assert_cmpint (destroy_counter, ==, 0);
 818   g_assert_cmpint (destroy_key_counter, ==, 0);
 819
 820   g_hash_table_remove_all (h);
 821   g_assert_cmpint (destroy_counter, ==, 2);
 822   g_assert_cmpint (destroy_key_counter, ==, 2);
 823
 824   g_hash_table_remove_all (h);
 825   g_assert_cmpint (destroy_counter, ==, 2);
 826   g_assert_cmpint (destroy_key_counter, ==, 2);
 827
 828   g_hash_table_unref (h);
 829 }
 830
 831 GHashTable *recursive_destruction_table = NULL;
 832 static void
 833 recursive_value_destroy (gpointer value)
 834 {
 835   destroy_counter++;
 836
 837   if (recursive_destruction_table)
 838     g_hash_table_remove (recursive_destruction_table, value);
 839 }
 840
 841 static void
 842 test_recursive_remove_all_subprocess (void)
 843 {
 844   GHashTable *h;
 845
 846   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
 847   recursive_destruction_table = h;
 848
 849   /* Add more items compared to test_remove_all, as it would not fail otherwise. */
 850   g_hash_table_insert (h, "abc", "cde");
 851   g_hash_table_insert (h, "cde", "fgh");
 852   g_hash_table_insert (h, "fgh", "ijk");
 853   g_hash_table_insert (h, "ijk", "lmn");
 854   g_hash_table_insert (h, "lmn", "opq");
 855   g_hash_table_insert (h, "opq", "rst");
 856   g_hash_table_insert (h, "rst", "uvw");
 857   g_hash_table_insert (h, "uvw", "xyz");
 858   g_hash_table_insert (h, "xyz", "abc");
 859
 860   destroy_counter = 0;
 861   destroy_key_counter = 0;
 862
 863   g_hash_table_remove_all (h);
 864   g_assert_cmpint (destroy_counter, ==, 9);
 865   g_assert_cmpint (destroy_key_counter, ==, 9);
 866
 867   g_hash_table_unref (h);
 868 }
 869
 870 static void
 871 test_recursive_remove_all (void)
 872 {
 873   g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000, 0);
 874   g_test_trap_assert_passed ();
 875 }
 876
 877 typedef struct {
 878   gint ref_count;
 879   const gchar *key;
 880 } RefCountedKey;
 881
 882 static guint
 883 hash_func (gconstpointer key)
 884 {
 885   const RefCountedKey *rkey = key;
 886
 887   return g_str_hash (rkey->key);
 888 }
 889
 890 static gboolean
 891 eq_func (gconstpointer a, gconstpointer b)
 892 {
 893   const RefCountedKey *aa = a;
 894   const RefCountedKey *bb = b;
 895
 896   return g_strcmp0 (aa->key, bb->key) == 0;
 897 }
 898
 899 static void
 900 key_unref (gpointer data)
 901 {
 902   RefCountedKey *key = data;
 903
 904   g_assert (key->ref_count > 0);
 905
 906   key->ref_count -= 1;
 907
 908   if (key->ref_count == 0)
 909     g_free (key);
 910 }
 911
 912 static RefCountedKey *
 913 key_ref (RefCountedKey *key)
 914 {
 915   key->ref_count += 1;
 916
 917   return key;
 918 }
 919
 920 static RefCountedKey *
 921 key_new (const gchar *key)
 922 {
 923   RefCountedKey *rkey;
 924
 925   rkey = g_new (RefCountedKey, 1);
 926
 927   rkey->ref_count = 1;
 928   rkey->key = key;
 929
 930   return rkey;
 931 }
 932
 933 static void
 934 set_ref_hash_test (void)
 935 {
 936   GHashTable *h;
 937   RefCountedKey *key1;
 938   RefCountedKey *key2;
 939
 940   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 941
 942   key1 = key_new ("a");
 943   key2 = key_new ("a");
 944
 945   g_assert_cmpint (key1->ref_count, ==, 1);
 946   g_assert_cmpint (key2->ref_count, ==, 1);
 947
 948   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 949
 950   g_assert_cmpint (key1->ref_count, ==, 3);
 951   g_assert_cmpint (key2->ref_count, ==, 1);
 952
 953   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 954
 955   g_assert_cmpint (key1->ref_count, ==, 1);
 956   g_assert_cmpint (key2->ref_count, ==, 3);
 957
 958   g_hash_table_remove (h, key1);
 959
 960   g_assert_cmpint (key1->ref_count, ==, 1);
 961   g_assert_cmpint (key2->ref_count, ==, 1);
 962
 963   g_hash_table_unref (h);
 964
 965   key_unref (key1);
 966   key_unref (key2);
 967 }
 968
 969 GHashTable *h;
 970
 971 typedef struct {
 972     gchar *string;
 973     gboolean freed;
 974 } FakeFreeData;
 975
 976 GPtrArray *fake_free_data;
 977
 978 static void
 979 fake_free (gpointer dead)
 980 {
 981   guint i;
 982
 983   for (i = 0; i < fake_free_data->len; i++)
 984     {
 985       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 986
 987       if (ffd->string == (gchar *) dead)
 988         {
 989           g_assert (!ffd->freed);
 990           ffd->freed = TRUE;
 991           return;
 992         }
 993     }
 994
 995   g_assert_not_reached ();
 996 }
 997
 998 static void
 999 value_destroy_insert (gpointer value)
1000 {
1001   g_hash_table_remove_all (h);
1002 }
1003
1004 static void
1005 test_destroy_modify (void)
1006 {
1007   FakeFreeData *ffd;
1008   guint i;
1009
1010   g_test_bug ("650459");
1011
1012   fake_free_data = g_ptr_array_new ();
1013
1014   h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
1015
1016   ffd = g_new0 (FakeFreeData, 1);
1017   ffd->string = g_strdup ("a");
1018   g_ptr_array_add (fake_free_data, ffd);
1019   g_hash_table_insert (h, ffd->string, "b");
1020
1021   ffd = g_new0 (FakeFreeData, 1);
1022   ffd->string = g_strdup ("c");
1023   g_ptr_array_add (fake_free_data, ffd);
1024   g_hash_table_insert (h, ffd->string, "d");
1025
1026   ffd = g_new0 (FakeFreeData, 1);
1027   ffd->string = g_strdup ("e");
1028   g_ptr_array_add (fake_free_data, ffd);
1029   g_hash_table_insert (h, ffd->string, "f");
1030
1031   ffd = g_new0 (FakeFreeData, 1);
1032   ffd->string = g_strdup ("g");
1033   g_ptr_array_add (fake_free_data, ffd);
1034   g_hash_table_insert (h, ffd->string, "h");
1035
1036   ffd = g_new0 (FakeFreeData, 1);
1037   ffd->string = g_strdup ("h");
1038   g_ptr_array_add (fake_free_data, ffd);
1039   g_hash_table_insert (h, ffd->string, "k");
1040
1041   ffd = g_new0 (FakeFreeData, 1);
1042   ffd->string = g_strdup ("a");
1043   g_ptr_array_add (fake_free_data, ffd);
1044   g_hash_table_insert (h, ffd->string, "c");
1045
1046   g_hash_table_remove (h, "c");
1047
1048   /* that removed everything... */
1049   for (i = 0; i < fake_free_data->len; i++)
1050     {
1051       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1052
1053       g_assert (ffd->freed);
1054       g_free (ffd->string);
1055       g_free (ffd);
1056     }
1057
1058   g_ptr_array_unref (fake_free_data);
1059
1060   /* ... so this is a no-op */
1061   g_hash_table_remove (h, "e");
1062
1063   g_hash_table_unref (h);
1064 }
1065
1066 static gboolean
1067 find_str (gpointer key, gpointer value, gpointer data)
1068 {
1069   return g_str_equal (key, data);
1070 }
1071
1072 static void
1073 test_find (void)
1074 {
1075   GHashTable *hash;
1076   const gchar *value;
1077
1078   hash = g_hash_table_new (g_str_hash, g_str_equal);
1079
1080   g_hash_table_insert (hash, "a", "A");
1081   g_hash_table_insert (hash, "b", "B");
1082   g_hash_table_insert (hash, "c", "C");
1083   g_hash_table_insert (hash, "d", "D");
1084   g_hash_table_insert (hash, "e", "E");
1085   g_hash_table_insert (hash, "f", "F");
1086
1087   value = g_hash_table_find (hash, find_str, "a");
1088   g_assert_cmpstr (value, ==, "A");
1089
1090   value = g_hash_table_find (hash, find_str, "b");
1091   g_assert_cmpstr (value, ==, "B");
1092
1093   value = g_hash_table_find (hash, find_str, "c");
1094   g_assert_cmpstr (value, ==, "C");
1095
1096   value = g_hash_table_find (hash, find_str, "d");
1097   g_assert_cmpstr (value, ==, "D");
1098
1099   value = g_hash_table_find (hash, find_str, "e");
1100   g_assert_cmpstr (value, ==, "E");
1101
1102   value = g_hash_table_find (hash, find_str, "f");
1103   g_assert_cmpstr (value, ==, "F");
1104
1105   value = g_hash_table_find (hash, find_str, "0");
1106   g_assert (value == NULL);
1107
1108   g_hash_table_unref (hash);
1109 }
1110
1111 gboolean seen_key[6];
1112
1113 static void
1114 foreach_func (gpointer key, gpointer value, gpointer data)
1115 {
1116   seen_key[((char*)key)[0] - 'a'] = TRUE;
1117 }
1118
1119 static void
1120 test_foreach (void)
1121 {
1122   GHashTable *hash;
1123   gint i;
1124
1125   hash = g_hash_table_new (g_str_hash, g_str_equal);
1126
1127   g_hash_table_insert (hash, "a", "A");
1128   g_hash_table_insert (hash, "b", "B");
1129   g_hash_table_insert (hash, "c", "C");
1130   g_hash_table_insert (hash, "d", "D");
1131   g_hash_table_insert (hash, "e", "E");
1132   g_hash_table_insert (hash, "f", "F");
1133
1134   for (i = 0; i < 6; i++)
1135     seen_key[i] = FALSE;
1136
1137   g_hash_table_foreach (hash, foreach_func, NULL);
1138
1139   for (i = 0; i < 6; i++)
1140     g_assert (seen_key[i]);
1141
1142   g_hash_table_unref (hash);
1143 }
1144
1145 static gboolean
1146 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1147 {
1148   GHashTable *hash2 = data;
1149
1150   if (strstr ("ace", (gchar*)key))
1151     {
1152       g_hash_table_insert (hash2, key, value);
1153       return TRUE;
1154     }
1155
1156   return FALSE;
1157 }
1158
1159
1160 static void
1161 test_foreach_steal (void)
1162 {
1163   GHashTable *hash;
1164   GHashTable *hash2;
1165
1166   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1167   hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1168
1169   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1170   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1171   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1172   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1173   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1174   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1175
1176   g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1177
1178   g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1179   g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1180
1181   g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1182   g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1183   g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1184   g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1185   g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1186   g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1187
1188   g_hash_table_unref (hash);
1189   g_hash_table_unref (hash2);
1190 }
1191
1192 /* Test g_hash_table_steal_extended() works properly with existing and
1193  * non-existing keys. */
1194 static void
1195 test_steal_extended (void)
1196 {
1197   GHashTable *hash;
1198   gchar *stolen_key = NULL, *stolen_value = NULL;
1199
1200   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1201
1202   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1203   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1204   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1205   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1206   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1207   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1208
1209   g_assert_true (g_hash_table_steal_extended (hash, "a",
1210                                               (gpointer *) &stolen_key,
1211                                               (gpointer *) &stolen_value));
1212   g_assert_cmpstr (stolen_key, ==, "a");
1213   g_assert_cmpstr (stolen_value, ==, "A");
1214   g_clear_pointer (&stolen_key, g_free);
1215   g_clear_pointer (&stolen_value, g_free);
1216
1217   g_assert_cmpuint (g_hash_table_size (hash), ==, 5);
1218
1219   g_assert_false (g_hash_table_steal_extended (hash, "a",
1220                                                (gpointer *) &stolen_key,
1221                                                (gpointer *) &stolen_value));
1222   g_assert_null (stolen_key);
1223   g_assert_null (stolen_value);
1224
1225   g_assert_false (g_hash_table_steal_extended (hash, "never a key",
1226                                                (gpointer *) &stolen_key,
1227                                                (gpointer *) &stolen_value));
1228   g_assert_null (stolen_key);
1229   g_assert_null (stolen_value);
1230
1231   g_assert_cmpuint (g_hash_table_size (hash), ==, 5);
1232
1233   g_hash_table_unref (hash);
1234 }
1235
1236 struct _GHashTable
1237 {
1238   gint             size;
1239   gint             mod;
1240   guint            mask;
1241   gint             nnodes;
1242   gint             noccupied;  /* nnodes + tombstones */
1243
1244   gpointer        *keys;
1245   guint           *hashes;
1246   gpointer        *values;
1247
1248   GHashFunc        hash_func;
1249   GEqualFunc       key_equal_func;
1250   volatile gint    ref_count;
1251
1252 #ifndef G_DISABLE_ASSERT
1253   int              version;
1254 #endif
1255   GDestroyNotify   key_destroy_func;
1256   GDestroyNotify   value_destroy_func;
1257 };
1258
1259 static void
1260 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1261 {
1262   gint i;
1263
1264   *unused = 0;
1265   *occupied = 0;
1266   *tombstones = 0;
1267   for (i = 0; i < h->size; i++)
1268     {
1269       if (h->hashes[i] == 0)
1270         (*unused)++;
1271       else if (h->hashes[i] == 1)
1272         (*tombstones)++;
1273       else
1274         (*occupied)++;
1275     }
1276 }
1277
1278 static void
1279 check_data (GHashTable *h)
1280 {
1281   gint i;
1282
1283   for (i = 0; i < h->size; i++)
1284     {
1285       if (h->hashes[i] < 2)
1286         {
1287           g_assert (h->keys[i] == NULL);
1288           g_assert (h->values[i] == NULL);
1289         }
1290       else
1291         {
1292           g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1293         }
1294     }
1295 }
1296
1297 static void
1298 check_consistency (GHashTable *h)
1299 {
1300   gint unused;
1301   gint occupied;
1302   gint tombstones;
1303
1304   count_keys (h, &unused, &occupied, &tombstones);
1305
1306   g_assert_cmpint (occupied, ==, h->nnodes);
1307   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1308   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1309
1310   check_data (h);
1311 }
1312
1313 static void
1314 check_counts (GHashTable *h, gint occupied, gint tombstones)
1315 {
1316   g_assert_cmpint (occupied, ==, h->nnodes);
1317   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1318 }
1319
1320 static void
1321 trivial_key_destroy (gpointer key)
1322 {
1323 }
1324
1325 static void
1326 test_internal_consistency (void)
1327 {
1328   GHashTable *h;
1329
1330   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1331
1332   check_counts (h, 0, 0);
1333   check_consistency (h);
1334
1335   g_hash_table_insert (h, "a", "A");
1336   g_hash_table_insert (h, "b", "B");
1337   g_hash_table_insert (h, "c", "C");
1338   g_hash_table_insert (h, "d", "D");
1339   g_hash_table_insert (h, "e", "E");
1340   g_hash_table_insert (h, "f", "F");
1341
1342   check_counts (h, 6, 0);
1343   check_consistency (h);
1344
1345   g_hash_table_remove (h, "a");
1346   check_counts (h, 5, 1);
1347   check_consistency (h);
1348
1349   g_hash_table_remove (h, "b");
1350   check_counts (h, 4, 2);
1351   check_consistency (h);
1352
1353   g_hash_table_insert (h, "c", "c");
1354   check_counts (h, 4, 2);
1355   check_consistency (h);
1356
1357   g_hash_table_insert (h, "a", "A");
1358   check_counts (h, 5, 1);
1359   check_consistency (h);
1360
1361   g_hash_table_remove_all (h);
1362   check_counts (h, 0, 0);
1363   check_consistency (h);
1364
1365   g_hash_table_unref (h);
1366 }
1367
1368 static void
1369 my_key_free (gpointer v)
1370 {
1371   gchar *s = v;
1372   g_assert (s[0] != 'x');
1373   s[0] = 'x';
1374   g_free (v);
1375 }
1376
1377 static void
1378 my_value_free (gpointer v)
1379 {
1380   gchar *s = v;
1381   g_assert (s[0] != 'y');
1382   s[0] = 'y';
1383   g_free (v);
1384 }
1385
1386 static void
1387 test_iter_replace (void)
1388 {
1389   GHashTable *h;
1390   GHashTableIter iter;
1391   gpointer k, v;
1392   gchar *s;
1393
1394   g_test_bug ("662544");
1395
1396   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1397
1398   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1399   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1400   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1401
1402   g_hash_table_iter_init (&iter, h);
1403
1404   while (g_hash_table_iter_next (&iter, &k, &v))
1405     {
1406        s = (gchar*)v;
1407        g_assert (g_ascii_islower (s[0]));
1408        g_hash_table_iter_replace (&iter, g_strdup (k));
1409     }
1410
1411   g_hash_table_unref (h);
1412 }
1413
1414 static void
1415 replace_first_character (gchar *string)
1416 {
1417   string[0] = 'b';
1418 }
1419
1420 static void
1421 test_set_insert_corruption (void)
1422 {
1423   GHashTable *hash_table =
1424     g_hash_table_new_full (g_str_hash, g_str_equal,
1425         (GDestroyNotify) replace_first_character, NULL);
1426   GHashTableIter iter;
1427   gchar a[] = "foo";
1428   gchar b[] = "foo";
1429   gpointer key, value;
1430
1431   g_test_bug ("692815");
1432
1433   g_hash_table_insert (hash_table, a, a);
1434   g_assert (g_hash_table_contains (hash_table, "foo"));
1435
1436   g_hash_table_insert (hash_table, b, b);
1437
1438   g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1439   g_hash_table_iter_init (&iter, hash_table);
1440   if (!g_hash_table_iter_next (&iter, &key, &value))
1441     g_assert_not_reached();
1442
1443   /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1444    * and the sole key in 'hash_table' should be 'a'.
1445    */
1446   g_assert (key != b);
1447   g_assert (key == a);
1448
1449   g_assert_cmpstr (b, ==, "boo");
1450
1451   /* g_hash_table_insert() also says that the value should now be 'b',
1452    * which is probably not what the caller intended but is precisely what they
1453    * asked for.
1454    */
1455   g_assert (value == b);
1456
1457   /* even though the hash has now been de-set-ified: */
1458   g_assert (g_hash_table_contains (hash_table, "foo"));
1459
1460   g_hash_table_unref (hash_table);
1461 }
1462
1463 static void
1464 test_set_to_strv (void)
1465 {
1466   GHashTable *set;
1467   gchar **strv;
1468   guint n;
1469
1470   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1471   g_hash_table_add (set, g_strdup ("xyz"));
1472   g_hash_table_add (set, g_strdup ("xyz"));
1473   g_hash_table_add (set, g_strdup ("abc"));
1474   strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1475   g_hash_table_steal_all (set);
1476   g_hash_table_unref (set);
1477   g_assert_cmpint (n, ==, 2);
1478   n = g_strv_length (strv);
1479   g_assert_cmpint (n, ==, 2);
1480   if (g_str_equal (strv[0], "abc"))
1481     g_assert_cmpstr (strv[1], ==, "xyz");
1482   else
1483     {
1484     g_assert_cmpstr (strv[0], ==, "xyz");
1485     g_assert_cmpstr (strv[1], ==, "abc");
1486     }
1487   g_strfreev (strv);
1488 }
1489
1490 static gboolean
1491 is_prime (guint p)
1492 {
1493   guint i;
1494
1495   if (p % 2 == 0)
1496     return FALSE;
1497
1498   i = 3;
1499   while (TRUE)
1500     {
1501       if (i * i > p)
1502         return TRUE;
1503
1504       if (p % i == 0)
1505         return FALSE;
1506
1507       i += 2;
1508     }
1509 }
1510
1511 static void
1512 test_primes (void)
1513 {
1514   guint p, q;
1515   gdouble r, min, max;
1516
1517   max = 1.0;
1518   min = 10.0;
1519   q = 1;
1520   while (1) {
1521     p = q;
1522     q = g_spaced_primes_closest (p);
1523     g_assert (is_prime (q));
1524     if (p == 1) continue;
1525     if (q == p) break;
1526     r = q / (gdouble) p;
1527     min = MIN (min, r);
1528     max = MAX (max, r);
1529   };
1530
1531   g_assert_cmpfloat (1.3, <, min);
1532   g_assert_cmpfloat (max, <, 2.0);
1533 }
1534
1535 int
1536 main (int argc, char *argv[])
1537 {
1538   g_test_init (&argc, &argv, NULL);
1539
1540   g_test_bug_base ("http://bugzilla.gnome.org/");
1541
1542   g_test_add_func ("/hash/misc", test_hash_misc);
1543   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1544   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1545   g_test_add_func ("/hash/direct", direct_hash_test);
1546   g_test_add_func ("/hash/direct2", direct_hash_test2);
1547   g_test_add_func ("/hash/int", int_hash_test);
1548   g_test_add_func ("/hash/int64", int64_hash_test);
1549   g_test_add_func ("/hash/double", double_hash_test);
1550   g_test_add_func ("/hash/string", string_hash_test);
1551   g_test_add_func ("/hash/set", set_hash_test);
1552   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1553   g_test_add_func ("/hash/ref", test_hash_ref);
1554   g_test_add_func ("/hash/remove-all", test_remove_all);
1555   g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
1556   g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
1557   g_test_add_func ("/hash/find", test_find);
1558   g_test_add_func ("/hash/foreach", test_foreach);
1559   g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1560   g_test_add_func ("/hash/steal-extended", test_steal_extended);
1561
1562   /* tests for individual bugs */
1563   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1564   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1565   g_test_add_func ("/hash/consistency", test_internal_consistency);
1566   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1567   g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1568   g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1569   g_test_add_func ("/hash/primes", test_primes);
1570
1571   return g_test_run ();
1572
1573 }