glib/tests/hash.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  * Copyright (C) 1999 The Free Software Foundation
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, 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 #ifdef HAVE_CONFIG_H
  30 #  include <config.h>
  31 #endif
  32
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <stdlib.h>
  36
  37 #include <glib.h>
  38
  39
  40
  41 int array[10000];
  42
  43 static void
  44 fill_hash_table_and_array (GHashTable *hash_table)
  45 {
  46   int i;
  47
  48   for (i = 0; i < 10000; i++)
  49     {
  50       array[i] = i;
  51       g_hash_table_insert (hash_table, &array[i], &array[i]);
  52     }
  53 }
  54
  55 static void
  56 init_result_array (int result_array[10000])
  57 {
  58   int i;
  59
  60   for (i = 0; i < 10000; i++)
  61     result_array[i] = -1;
  62 }
  63
  64 static void
  65 verify_result_array (int array[10000])
  66 {
  67   int i;
  68
  69   for (i = 0; i < 10000; i++)
  70     g_assert (array[i] == i);
  71 }
  72
  73 static void
  74 handle_pair (gpointer key, gpointer value, int result_array[10000])
  75 {
  76   int n;
  77
  78   g_assert (key == value);
  79
  80   n = *((int *) value);
  81
  82   g_assert (n >= 0 && n < 10000);
  83   g_assert (result_array[n] == -1);
  84
  85   result_array[n] = n;
  86 }
  87
  88 static gboolean
  89 my_hash_callback_remove (gpointer key,
  90                          gpointer value,
  91                          gpointer user_data)
  92 {
  93   int *d = value;
  94
  95   if ((*d) % 2)
  96     return TRUE;
  97
  98   return FALSE;
  99 }
 100
 101 static void
 102 my_hash_callback_remove_test (gpointer key,
 103                               gpointer value,
 104                               gpointer user_data)
 105 {
 106   int *d = value;
 107
 108   if ((*d) % 2)
 109     g_assert_not_reached ();
 110 }
 111
 112 static void
 113 my_hash_callback (gpointer key,
 114                   gpointer value,
 115                   gpointer user_data)
 116 {
 117   handle_pair (key, value, user_data);
 118 }
 119
 120 static guint
 121 my_hash (gconstpointer key)
 122 {
 123   return (guint) *((const gint*) key);
 124 }
 125
 126 static gboolean
 127 my_hash_equal (gconstpointer a,
 128                gconstpointer b)
 129 {
 130   return *((const gint*) a) == *((const gint*) b);
 131 }
 132
 133
 134
 135 /*
 136  * This is a simplified version of the pathalias hashing function.
 137  * Thanks to Steve Belovin and Peter Honeyman
 138  *
 139  * hash a string into a long int.  31 bit crc (from andrew appel).
 140  * the crc table is computed at run time by crcinit() -- we could
 141  * precompute, but it takes 1 clock tick on a 750.
 142  *
 143  * This fast table calculation works only if POLY is a prime polynomial
 144  * in the field of integers modulo 2.  Since the coefficients of a
 145  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 146  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 147  * 31 down to 25 are zero.  Happily, we have candidates, from
 148  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 149  *      x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 150  *      x^31 + x^3 + x^0
 151  *
 152  * We reverse the bits to get:
 153  *      111101010000000000000000000000001 but drop the last 1
 154  *         f   5   0   0   0   0   0   0
 155  *      010010000000000000000000000000001 ditto, for 31-bit crc
 156  *         4   8   0   0   0   0   0   0
 157  */
 158
 159 #define POLY 0x48000000L        /* 31-bit polynomial (avoids sign problems) */
 160
 161 static guint CrcTable[128];
 162
 163 /*
 164  - crcinit - initialize tables for hash function
 165  */
 166 static void crcinit(void)
 167 {
 168   int i, j;
 169   guint sum;
 170
 171   for (i = 0; i < 128; ++i)
 172     {
 173       sum = 0L;
 174       for (j = 7 - 1; j >= 0; --j)
 175         if (i & (1 << j))
 176           sum ^= POLY >> j;
 177       CrcTable[i] = sum;
 178     }
 179 }
 180
 181 /*
 182  - hash - Honeyman's nice hashing function
 183  */
 184 static guint
 185 honeyman_hash (gconstpointer key)
 186 {
 187   const gchar *name = (const gchar *) key;
 188   gint size;
 189   guint sum = 0;
 190
 191   g_assert (name != NULL);
 192   g_assert (*name != 0);
 193
 194   size = strlen (name);
 195
 196   while (size--)
 197     sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
 198
 199   return sum;
 200 }
 201
 202
 203 static gboolean
 204 second_hash_cmp (gconstpointer a, gconstpointer b)
 205 {
 206   return strcmp (a, b) == 0;
 207 }
 208
 209
 210
 211 static guint
 212 one_hash (gconstpointer key)
 213 {
 214   return 1;
 215 }
 216
 217
 218 static void
 219 not_even_foreach (gpointer key,
 220                   gpointer value,
 221                   gpointer user_data)
 222 {
 223   const char *_key = (const char *) key;
 224   const char *_value = (const char *) value;
 225   int i;
 226   char val [20];
 227
 228   g_assert (_key != NULL);
 229   g_assert (*_key != 0);
 230   g_assert (_value != NULL);
 231   g_assert (*_value != 0);
 232
 233   i = atoi (_key);
 234
 235   sprintf (val, "%d value", i);
 236   g_assert (strcmp (_value, val) == 0);
 237
 238   g_assert ((i % 2) != 0);
 239   g_assert (i != 3);
 240 }
 241
 242 static gboolean
 243 remove_even_foreach (gpointer key,
 244                      gpointer value,
 245                      gpointer user_data)
 246 {
 247   const char *_key = (const char *) key;
 248   const char *_value = (const char *) value;
 249   int i;
 250   char val [20];
 251
 252   g_assert (_key != NULL);
 253   g_assert (*_key != 0);
 254   g_assert (_value != NULL);
 255   g_assert (*_value != 0);
 256
 257   i = atoi (_key);
 258
 259   sprintf (val, "%d value", i);
 260   g_assert (strcmp (_value, val) == 0);
 261
 262   return ((i % 2) == 0) ? TRUE : FALSE;
 263 }
 264
 265
 266
 267
 268 static void
 269 second_hash_test (gconstpointer d)
 270 {
 271   gboolean simple_hash = GPOINTER_TO_INT (d);
 272
 273   int       i;
 274   char      key[20] = "", val[20]="", *v, *orig_key, *orig_val;
 275   GHashTable     *h;
 276   gboolean found;
 277
 278   crcinit ();
 279
 280   h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
 281                              second_hash_cmp,
 282                              g_free, g_free);
 283   g_assert (h != NULL);
 284   for (i = 0; i < 20; i++)
 285     {
 286       sprintf (key, "%d", i);
 287       g_assert (atoi (key) == i);
 288
 289       sprintf (val, "%d value", i);
 290       g_assert (atoi (val) == i);
 291
 292       g_hash_table_insert (h, g_strdup (key), g_strdup (val));
 293     }
 294
 295   g_assert (g_hash_table_size (h) == 20);
 296
 297   for (i = 0; i < 20; i++)
 298     {
 299       sprintf (key, "%d", i);
 300       g_assert (atoi(key) == i);
 301
 302       v = (char *) g_hash_table_lookup (h, key);
 303
 304       g_assert (v != NULL);
 305       g_assert (*v != 0);
 306       g_assert (atoi (v) == i);
 307     }
 308
 309   sprintf (key, "%d", 3);
 310   g_hash_table_remove (h, key);
 311   g_assert (g_hash_table_size (h) == 19);
 312   g_hash_table_foreach_remove (h, remove_even_foreach, NULL);
 313   g_assert (g_hash_table_size (h) == 9);
 314   g_hash_table_foreach (h, not_even_foreach, NULL);
 315
 316   for (i = 0; i < 20; i++)
 317     {
 318       sprintf (key, "%d", i);
 319       g_assert (atoi(key) == i);
 320
 321       sprintf (val, "%d value", i);
 322       g_assert (atoi (val) == i);
 323
 324       orig_key = orig_val = NULL;
 325       found = g_hash_table_lookup_extended (h, key,
 326                                             (gpointer)&orig_key,
 327                                             (gpointer)&orig_val);
 328       if ((i % 2) == 0 || i == 3)
 329         {
 330           g_assert (!found);
 331           continue;
 332         }
 333
 334       g_assert (found);
 335
 336       g_assert (orig_key != NULL);
 337       g_assert (strcmp (key, orig_key) == 0);
 338
 339       g_assert (orig_val != NULL);
 340       g_assert (strcmp (val, orig_val) == 0);
 341     }
 342
 343   g_hash_table_destroy (h);
 344 }
 345
 346 static gboolean
 347 find_first (gpointer key,
 348             gpointer value,
 349             gpointer user_data)
 350 {
 351   gint *v = value;
 352   gint *test = user_data;
 353   return (*v == *test);
 354 }
 355
 356 static void
 357 direct_hash_test (void)
 358 {
 359   gint       i, rc;
 360   GHashTable     *h;
 361
 362   h = g_hash_table_new (NULL, NULL);
 363   g_assert (h != NULL);
 364   for (i = 1; i <= 20; i++)
 365     g_hash_table_insert (h, GINT_TO_POINTER (i),
 366                          GINT_TO_POINTER (i + 42));
 367
 368   g_assert (g_hash_table_size (h) == 20);
 369
 370   for (i = 1; i <= 20; i++)
 371     {
 372       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 373
 374       g_assert (rc != 0);
 375       g_assert ((rc - 42) == i);
 376     }
 377
 378   g_hash_table_destroy (h);
 379 }
 380
 381 static void
 382 direct_hash_test2 (void)
 383 {
 384   gint       i, rc;
 385   GHashTable     *h;
 386
 387   h = g_hash_table_new (g_direct_hash, g_direct_equal);
 388   g_assert (h != NULL);
 389   for (i = 1; i <= 20; i++)
 390     g_hash_table_insert (h, GINT_TO_POINTER (i),
 391                          GINT_TO_POINTER (i + 42));
 392
 393   g_assert (g_hash_table_size (h) == 20);
 394
 395   for (i = 1; i <= 20; i++)
 396     {
 397       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
 398
 399       g_assert (rc != 0);
 400       g_assert ((rc - 42) == i);
 401     }
 402
 403   g_hash_table_destroy (h);
 404 }
 405
 406 static void
 407 int_hash_test (void)
 408 {
 409   gint       i, rc;
 410   GHashTable     *h;
 411   gint     values[20];
 412   gint key;
 413
 414   h = g_hash_table_new (g_int_hash, g_int_equal);
 415   g_assert (h != NULL);
 416   for (i = 0; i < 20; i++)
 417     {
 418       values[i] = i + 42;
 419       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 420     }
 421
 422   g_assert (g_hash_table_size (h) == 20);
 423
 424   for (i = 0; i < 20; i++)
 425     {
 426       key = i + 42;
 427       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 428
 429       g_assert_cmpint (rc, ==, i + 42);
 430     }
 431
 432   g_hash_table_destroy (h);
 433 }
 434
 435 static void
 436 int64_hash_test (void)
 437 {
 438   gint       i, rc;
 439   GHashTable     *h;
 440   gint64     values[20];
 441   gint64 key;
 442
 443   h = g_hash_table_new (g_int64_hash, g_int64_equal);
 444   g_assert (h != NULL);
 445   for (i = 0; i < 20; i++)
 446     {
 447       values[i] = i + 42;
 448       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 449     }
 450
 451   g_assert (g_hash_table_size (h) == 20);
 452
 453   for (i = 0; i < 20; i++)
 454     {
 455       key = i + 42;
 456       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 457
 458       g_assert_cmpint (rc, ==, i + 42);
 459     }
 460
 461   g_hash_table_destroy (h);
 462 }
 463
 464 static void
 465 double_hash_test (void)
 466 {
 467   gint       i, rc;
 468   GHashTable     *h;
 469   gdouble values[20];
 470   gdouble key;
 471
 472   h = g_hash_table_new (g_double_hash, g_double_equal);
 473   g_assert (h != NULL);
 474   for (i = 0; i < 20; i++)
 475     {
 476       values[i] = i + 42.5;
 477       g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
 478     }
 479
 480   g_assert (g_hash_table_size (h) == 20);
 481
 482   for (i = 0; i < 20; i++)
 483     {
 484       key = i + 42.5;
 485       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
 486
 487       g_assert_cmpint (rc, ==, i + 42);
 488     }
 489
 490   g_hash_table_destroy (h);
 491 }
 492
 493 static void
 494 string_free (gpointer data)
 495 {
 496   GString *s = data;
 497
 498   g_string_free (s, TRUE);
 499 }
 500
 501 static void
 502 string_hash_test (void)
 503 {
 504   gint       i, rc;
 505   GHashTable     *h;
 506   GString *s;
 507
 508   h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
 509   g_assert (h != NULL);
 510   for (i = 0; i < 20; i++)
 511     {
 512       s = g_string_new ("");
 513       g_string_append_printf (s, "%d", i + 42);
 514       g_string_append_c (s, '.');
 515       g_string_prepend_unichar (s, 0x2301);
 516       g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
 517     }
 518
 519   g_assert (g_hash_table_size (h) == 20);
 520
 521   s = g_string_new ("");
 522   for (i = 0; i < 20; i++)
 523     {
 524       g_string_assign (s, "");
 525       g_string_append_printf (s, "%d", i + 42);
 526       g_string_append_c (s, '.');
 527       g_string_prepend_unichar (s, 0x2301);
 528       rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
 529
 530       g_assert_cmpint (rc, ==, i + 42);
 531     }
 532
 533   g_string_free (s, TRUE);
 534   g_hash_table_destroy (h);
 535 }
 536
 537 static void
 538 set_check (gpointer key,
 539            gpointer value,
 540            gpointer user_data)
 541 {
 542   int *pi = user_data;
 543   if (key != value)
 544     g_assert_not_reached ();
 545
 546   g_assert_cmpint (atoi (key) % 7, ==, 2);
 547
 548   (*pi)++;
 549 }
 550
 551 static void
 552 set_hash_test (void)
 553 {
 554   GHashTable *hash_table =
 555     g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 556   int i;
 557
 558   for (i = 2; i < 5000; i += 7)
 559     {
 560       char *s = g_strdup_printf ("%d", i);
 561       g_assert (g_hash_table_add (hash_table, s));
 562     }
 563
 564   g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
 565
 566   i = 0;
 567   g_hash_table_foreach (hash_table, set_check, &i);
 568   g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
 569
 570   g_assert (g_hash_table_contains (hash_table, "2"));
 571   g_assert (g_hash_table_contains (hash_table, "9"));
 572   g_assert (!g_hash_table_contains (hash_table, "a"));
 573
 574   /* this will cause the hash table to loose set nature */
 575   g_assert (g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 576   g_assert (!g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
 577
 578   g_assert (g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 579   g_assert (!g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
 580
 581   g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
 582   g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
 583
 584   g_hash_table_destroy (hash_table);
 585 }
 586
 587
 588 static void
 589 test_hash_misc (void)
 590 {
 591   GHashTable *hash_table;
 592   gint i;
 593   gint value = 120;
 594   gint *pvalue;
 595   GList *keys, *values;
 596   gint keys_len, values_len;
 597   GHashTableIter iter;
 598   gpointer ikey, ivalue;
 599   int result_array[10000];
 600   int n_array[1];
 601
 602   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 603   fill_hash_table_and_array (hash_table);
 604   pvalue = g_hash_table_find (hash_table, find_first, &value);
 605   if (!pvalue || *pvalue != value)
 606     g_assert_not_reached();
 607
 608   keys = g_hash_table_get_keys (hash_table);
 609   if (!keys)
 610     g_assert_not_reached ();
 611
 612   values = g_hash_table_get_values (hash_table);
 613   if (!values)
 614     g_assert_not_reached ();
 615
 616   keys_len = g_list_length (keys);
 617   values_len = g_list_length (values);
 618   if (values_len != keys_len &&  keys_len != g_hash_table_size (hash_table))
 619     g_assert_not_reached ();
 620
 621   g_list_free (keys);
 622   g_list_free (values);
 623
 624   init_result_array (result_array);
 625   g_hash_table_iter_init (&iter, hash_table);
 626   for (i = 0; i < 10000; i++)
 627     {
 628       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 629
 630       handle_pair (ikey, ivalue, result_array);
 631
 632       if (i % 2)
 633         g_hash_table_iter_remove (&iter);
 634     }
 635   g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
 636   g_assert (g_hash_table_size (hash_table) == 5000);
 637   verify_result_array (result_array);
 638
 639   fill_hash_table_and_array (hash_table);
 640
 641   init_result_array (result_array);
 642   g_hash_table_foreach (hash_table, my_hash_callback, result_array);
 643   verify_result_array (result_array);
 644
 645   for (i = 0; i < 10000; i++)
 646     g_hash_table_remove (hash_table, &array[i]);
 647
 648   fill_hash_table_and_array (hash_table);
 649
 650   if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
 651       g_hash_table_size (hash_table) != 5000)
 652     g_assert_not_reached();
 653
 654   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
 655   g_hash_table_destroy (hash_table);
 656
 657   hash_table = g_hash_table_new (my_hash, my_hash_equal);
 658   fill_hash_table_and_array (hash_table);
 659
 660   n_array[0] = 1;
 661
 662   g_hash_table_iter_init (&iter, hash_table);
 663   for (i = 0; i < 10000; i++)
 664     {
 665       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 666       g_hash_table_iter_replace (&iter, &n_array[0]);
 667     }
 668
 669   g_hash_table_iter_init (&iter, hash_table);
 670   for (i = 0; i < 10000; i++)
 671     {
 672       g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
 673
 674       g_assert (ivalue == &n_array[0]);
 675     }
 676
 677   g_hash_table_destroy (hash_table);
 678 }
 679
 680 static gint destroy_counter;
 681
 682 static void
 683 value_destroy (gpointer value)
 684 {
 685   destroy_counter++;
 686 }
 687
 688 static void
 689 test_hash_ref (void)
 690 {
 691   GHashTable *h;
 692   GHashTableIter iter;
 693   gchar *key, *value;
 694   gboolean abc_seen = FALSE;
 695   gboolean cde_seen = FALSE;
 696   gboolean xyz_seen = FALSE;
 697
 698   h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
 699   g_hash_table_insert (h, "abc", "ABC");
 700   g_hash_table_insert (h, "cde", "CDE");
 701   g_hash_table_insert (h, "xyz", "XYZ");
 702
 703   g_assert_cmpint (g_hash_table_size (h), == , 3);
 704
 705   g_hash_table_iter_init (&iter, h);
 706
 707   while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
 708     {
 709       if (strcmp (key, "abc") == 0)
 710         {
 711           g_assert_cmpstr (value, ==, "ABC");
 712           abc_seen = TRUE;
 713           g_hash_table_iter_steal (&iter);
 714         }
 715       else if (strcmp (key, "cde") == 0)
 716         {
 717           g_assert_cmpstr (value, ==, "CDE");
 718           cde_seen = TRUE;
 719         }
 720       else if (strcmp (key, "xyz") == 0)
 721         {
 722           g_assert_cmpstr (value, ==, "XYZ");
 723           xyz_seen = TRUE;
 724         }
 725     }
 726   g_assert_cmpint (destroy_counter, ==, 0);
 727
 728   g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
 729   g_assert (abc_seen && cde_seen && xyz_seen);
 730   g_assert_cmpint (g_hash_table_size (h), == , 2);
 731
 732   g_hash_table_ref (h);
 733   g_hash_table_destroy (h);
 734   g_assert_cmpint (g_hash_table_size (h), == , 0);
 735   g_assert_cmpint (destroy_counter, ==, 2);
 736   g_hash_table_insert (h, "uvw", "UVW");
 737   g_hash_table_unref (h);
 738   g_assert_cmpint (destroy_counter, ==, 3);
 739 }
 740
 741 static guint
 742 null_safe_str_hash (gconstpointer key)
 743 {
 744   if (key == NULL)
 745     return 0;
 746   else
 747     return g_str_hash (key);
 748 }
 749
 750 static gboolean
 751 null_safe_str_equal (gconstpointer a, gconstpointer b)
 752 {
 753   return g_strcmp0 (a, b) == 0;
 754 }
 755
 756 static void
 757 test_lookup_null_key (void)
 758 {
 759   GHashTable *h;
 760   gboolean res;
 761   gpointer key;
 762   gpointer value;
 763
 764   g_test_bug ("642944");
 765
 766   h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
 767   g_hash_table_insert (h, "abc", "ABC");
 768
 769   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 770   g_assert (!res);
 771
 772   g_hash_table_insert (h, NULL, "NULL");
 773
 774   res = g_hash_table_lookup_extended (h, NULL, &key, &value);
 775   g_assert (res);
 776   g_assert_cmpstr (value, ==, "NULL");
 777
 778   g_hash_table_unref (h);
 779 }
 780
 781 static gint destroy_key_counter;
 782
 783 static void
 784 key_destroy (gpointer key)
 785 {
 786   destroy_key_counter++;
 787 }
 788
 789 static void
 790 test_remove_all (void)
 791 {
 792   GHashTable *h;
 793   gboolean res;
 794
 795   h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
 796   g_hash_table_insert (h, "abc", "ABC");
 797   g_hash_table_insert (h, "cde", "CDE");
 798   g_hash_table_insert (h, "xyz", "XYZ");
 799
 800   destroy_counter = 0;
 801   destroy_key_counter = 0;
 802
 803   g_hash_table_steal_all (h);
 804   g_assert_cmpint (destroy_counter, ==, 0);
 805   g_assert_cmpint (destroy_key_counter, ==, 0);
 806
 807   g_hash_table_insert (h, "abc", "ABC");
 808   g_hash_table_insert (h, "cde", "CDE");
 809   g_hash_table_insert (h, "xyz", "XYZ");
 810
 811   res = g_hash_table_steal (h, "nosuchkey");
 812   g_assert (!res);
 813   g_assert_cmpint (destroy_counter, ==, 0);
 814   g_assert_cmpint (destroy_key_counter, ==, 0);
 815
 816   res = g_hash_table_steal (h, "xyz");
 817   g_assert (res);
 818   g_assert_cmpint (destroy_counter, ==, 0);
 819   g_assert_cmpint (destroy_key_counter, ==, 0);
 820
 821   g_hash_table_remove_all (h);
 822   g_assert_cmpint (destroy_counter, ==, 2);
 823   g_assert_cmpint (destroy_key_counter, ==, 2);
 824
 825   g_hash_table_unref (h);
 826 }
 827
 828 typedef struct {
 829   gint ref_count;
 830   const gchar *key;
 831 } RefCountedKey;
 832
 833 static guint
 834 hash_func (gconstpointer key)
 835 {
 836   const RefCountedKey *rkey = key;
 837
 838   return g_str_hash (rkey->key);
 839 }
 840
 841 static gboolean
 842 eq_func (gconstpointer a, gconstpointer b)
 843 {
 844   const RefCountedKey *aa = a;
 845   const RefCountedKey *bb = b;
 846
 847   return g_strcmp0 (aa->key, bb->key) == 0;
 848 }
 849
 850 static void
 851 key_unref (gpointer data)
 852 {
 853   RefCountedKey *key = data;
 854
 855   g_assert (key->ref_count > 0);
 856
 857   key->ref_count -= 1;
 858
 859   if (key->ref_count == 0)
 860     g_free (key);
 861 }
 862
 863 static RefCountedKey *
 864 key_ref (RefCountedKey *key)
 865 {
 866   key->ref_count += 1;
 867
 868   return key;
 869 }
 870
 871 static RefCountedKey *
 872 key_new (const gchar *key)
 873 {
 874   RefCountedKey *rkey;
 875
 876   rkey = g_new (RefCountedKey, 1);
 877
 878   rkey->ref_count = 1;
 879   rkey->key = key;
 880
 881   return rkey;
 882 }
 883
 884 static void
 885 set_ref_hash_test (void)
 886 {
 887   GHashTable *h;
 888   RefCountedKey *key1;
 889   RefCountedKey *key2;
 890
 891   h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
 892
 893   key1 = key_new ("a");
 894   key2 = key_new ("a");
 895
 896   g_assert_cmpint (key1->ref_count, ==, 1);
 897   g_assert_cmpint (key2->ref_count, ==, 1);
 898
 899   g_hash_table_insert (h, key_ref (key1), key_ref (key1));
 900
 901   g_assert_cmpint (key1->ref_count, ==, 3);
 902   g_assert_cmpint (key2->ref_count, ==, 1);
 903
 904   g_hash_table_replace (h, key_ref (key2), key_ref (key2));
 905
 906   g_assert_cmpint (key1->ref_count, ==, 1);
 907   g_assert_cmpint (key2->ref_count, ==, 3);
 908
 909   g_hash_table_remove (h, key1);
 910
 911   g_assert_cmpint (key1->ref_count, ==, 1);
 912   g_assert_cmpint (key2->ref_count, ==, 1);
 913
 914   g_hash_table_unref (h);
 915
 916   key_unref (key1);
 917   key_unref (key2);
 918 }
 919
 920 GHashTable *h;
 921
 922 typedef struct {
 923     gchar *string;
 924     gboolean freed;
 925 } FakeFreeData;
 926
 927 GPtrArray *fake_free_data;
 928
 929 static void
 930 fake_free (gpointer dead)
 931 {
 932   guint i;
 933
 934   for (i = 0; i < fake_free_data->len; i++)
 935     {
 936       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
 937
 938       if (ffd->string == (gchar *) dead)
 939         {
 940           g_assert (!ffd->freed);
 941           ffd->freed = TRUE;
 942           return;
 943         }
 944     }
 945
 946   g_assert_not_reached ();
 947 }
 948
 949 static void
 950 value_destroy_insert (gpointer value)
 951 {
 952   g_hash_table_remove_all (h);
 953 }
 954
 955 static void
 956 test_destroy_modify (void)
 957 {
 958   FakeFreeData *ffd;
 959   guint i;
 960
 961   g_test_bug ("650459");
 962
 963   fake_free_data = g_ptr_array_new ();
 964
 965   h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
 966
 967   ffd = g_new0 (FakeFreeData, 1);
 968   ffd->string = g_strdup ("a");
 969   g_ptr_array_add (fake_free_data, ffd);
 970   g_hash_table_insert (h, ffd->string, "b");
 971
 972   ffd = g_new0 (FakeFreeData, 1);
 973   ffd->string = g_strdup ("c");
 974   g_ptr_array_add (fake_free_data, ffd);
 975   g_hash_table_insert (h, ffd->string, "d");
 976
 977   ffd = g_new0 (FakeFreeData, 1);
 978   ffd->string = g_strdup ("e");
 979   g_ptr_array_add (fake_free_data, ffd);
 980   g_hash_table_insert (h, ffd->string, "f");
 981
 982   ffd = g_new0 (FakeFreeData, 1);
 983   ffd->string = g_strdup ("g");
 984   g_ptr_array_add (fake_free_data, ffd);
 985   g_hash_table_insert (h, ffd->string, "h");
 986
 987   ffd = g_new0 (FakeFreeData, 1);
 988   ffd->string = g_strdup ("h");
 989   g_ptr_array_add (fake_free_data, ffd);
 990   g_hash_table_insert (h, ffd->string, "k");
 991
 992   ffd = g_new0 (FakeFreeData, 1);
 993   ffd->string = g_strdup ("a");
 994   g_ptr_array_add (fake_free_data, ffd);
 995   g_hash_table_insert (h, ffd->string, "c");
 996
 997   g_hash_table_remove (h, "c");
 998
 999   /* that removed everything... */
1000   for (i = 0; i < fake_free_data->len; i++)
1001     {
1002       FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1003
1004       g_assert (ffd->freed);
1005       g_free (ffd->string);
1006       g_free (ffd);
1007     }
1008
1009   g_ptr_array_unref (fake_free_data);
1010
1011   /* ... so this is a no-op */
1012   g_hash_table_remove (h, "e");
1013
1014   g_hash_table_unref (h);
1015 }
1016
1017 static gboolean
1018 find_str (gpointer key, gpointer value, gpointer data)
1019 {
1020   return g_str_equal (key, data);
1021 }
1022
1023 static void
1024 test_find (void)
1025 {
1026   GHashTable *hash;
1027   const gchar *value;
1028
1029   hash = g_hash_table_new (g_str_hash, g_str_equal);
1030
1031   g_hash_table_insert (hash, "a", "A");
1032   g_hash_table_insert (hash, "b", "B");
1033   g_hash_table_insert (hash, "c", "C");
1034   g_hash_table_insert (hash, "d", "D");
1035   g_hash_table_insert (hash, "e", "E");
1036   g_hash_table_insert (hash, "f", "F");
1037
1038   value = g_hash_table_find (hash, find_str, "a");
1039   g_assert_cmpstr (value, ==, "A");
1040
1041   value = g_hash_table_find (hash, find_str, "b");
1042   g_assert_cmpstr (value, ==, "B");
1043
1044   value = g_hash_table_find (hash, find_str, "c");
1045   g_assert_cmpstr (value, ==, "C");
1046
1047   value = g_hash_table_find (hash, find_str, "d");
1048   g_assert_cmpstr (value, ==, "D");
1049
1050   value = g_hash_table_find (hash, find_str, "e");
1051   g_assert_cmpstr (value, ==, "E");
1052
1053   value = g_hash_table_find (hash, find_str, "f");
1054   g_assert_cmpstr (value, ==, "F");
1055
1056   value = g_hash_table_find (hash, find_str, "0");
1057   g_assert (value == NULL);
1058
1059   g_hash_table_unref (hash);
1060 }
1061
1062 gboolean seen_key[6];
1063
1064 static void
1065 foreach_func (gpointer key, gpointer value, gpointer data)
1066 {
1067   seen_key[((char*)key)[0] - 'a'] = TRUE;
1068 }
1069
1070 static void
1071 test_foreach (void)
1072 {
1073   GHashTable *hash;
1074   gint i;
1075
1076   hash = g_hash_table_new (g_str_hash, g_str_equal);
1077
1078   g_hash_table_insert (hash, "a", "A");
1079   g_hash_table_insert (hash, "b", "B");
1080   g_hash_table_insert (hash, "c", "C");
1081   g_hash_table_insert (hash, "d", "D");
1082   g_hash_table_insert (hash, "e", "E");
1083   g_hash_table_insert (hash, "f", "F");
1084
1085   for (i = 0; i < 6; i++)
1086     seen_key[i] = FALSE;
1087
1088   g_hash_table_foreach (hash, foreach_func, NULL);
1089
1090   for (i = 0; i < 6; i++)
1091     g_assert (seen_key[i]);
1092
1093   g_hash_table_unref (hash);
1094 }
1095
1096 static gboolean
1097 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1098 {
1099   GHashTable *hash2 = data;
1100
1101   if (strstr ("ace", (gchar*)key))
1102     {
1103       g_hash_table_insert (hash2, key, value);
1104       return TRUE;
1105     }
1106
1107   return FALSE;
1108 }
1109
1110
1111 static void
1112 test_foreach_steal (void)
1113 {
1114   GHashTable *hash;
1115   GHashTable *hash2;
1116
1117   hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1118   hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1119
1120   g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1121   g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1122   g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1123   g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1124   g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1125   g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1126
1127   g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1128
1129   g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1130   g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1131
1132   g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1133   g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1134   g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1135   g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1136   g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1137   g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1138
1139   g_hash_table_unref (hash);
1140   g_hash_table_unref (hash2);
1141 }
1142
1143 struct _GHashTable
1144 {
1145   gint             size;
1146   gint             mod;
1147   guint            mask;
1148   gint             nnodes;
1149   gint             noccupied;  /* nnodes + tombstones */
1150
1151   gpointer        *keys;
1152   guint           *hashes;
1153   gpointer        *values;
1154
1155   GHashFunc        hash_func;
1156   GEqualFunc       key_equal_func;
1157   volatile gint    ref_count;
1158
1159 #ifndef G_DISABLE_ASSERT
1160   int              version;
1161 #endif
1162   GDestroyNotify   key_destroy_func;
1163   GDestroyNotify   value_destroy_func;
1164 };
1165
1166 static void
1167 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1168 {
1169   gint i;
1170
1171   *unused = 0;
1172   *occupied = 0;
1173   *tombstones = 0;
1174   for (i = 0; i < h->size; i++)
1175     {
1176       if (h->hashes[i] == 0)
1177         (*unused)++;
1178       else if (h->hashes[i] == 1)
1179         (*tombstones)++;
1180       else
1181         (*occupied)++;
1182     }
1183 }
1184
1185 static void
1186 check_data (GHashTable *h)
1187 {
1188   gint i;
1189
1190   for (i = 0; i < h->size; i++)
1191     {
1192       if (h->hashes[i] < 2)
1193         {
1194           g_assert (h->keys[i] == NULL);
1195           g_assert (h->values[i] == NULL);
1196         }
1197       else
1198         {
1199           g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1200         }
1201     }
1202 }
1203
1204 static void
1205 check_consistency (GHashTable *h)
1206 {
1207   gint unused;
1208   gint occupied;
1209   gint tombstones;
1210
1211   count_keys (h, &unused, &occupied, &tombstones);
1212
1213   g_assert_cmpint (occupied, ==, h->nnodes);
1214   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1215   g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1216
1217   check_data (h);
1218 }
1219
1220 static void
1221 check_counts (GHashTable *h, gint occupied, gint tombstones)
1222 {
1223   g_assert_cmpint (occupied, ==, h->nnodes);
1224   g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1225 }
1226
1227 static void
1228 trivial_key_destroy (gpointer key)
1229 {
1230 }
1231
1232 static void
1233 test_internal_consistency (void)
1234 {
1235   GHashTable *h;
1236
1237   h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1238
1239   check_counts (h, 0, 0);
1240   check_consistency (h);
1241
1242   g_hash_table_insert (h, "a", "A");
1243   g_hash_table_insert (h, "b", "B");
1244   g_hash_table_insert (h, "c", "C");
1245   g_hash_table_insert (h, "d", "D");
1246   g_hash_table_insert (h, "e", "E");
1247   g_hash_table_insert (h, "f", "F");
1248
1249   check_counts (h, 6, 0);
1250   check_consistency (h);
1251
1252   g_hash_table_remove (h, "a");
1253   check_counts (h, 5, 1);
1254   check_consistency (h);
1255
1256   g_hash_table_remove (h, "b");
1257   check_counts (h, 4, 2);
1258   check_consistency (h);
1259
1260   g_hash_table_insert (h, "c", "c");
1261   check_counts (h, 4, 2);
1262   check_consistency (h);
1263
1264   g_hash_table_insert (h, "a", "A");
1265   check_counts (h, 5, 1);
1266   check_consistency (h);
1267
1268   g_hash_table_remove_all (h);
1269   check_counts (h, 0, 0);
1270   check_consistency (h);
1271
1272   g_hash_table_unref (h);
1273 }
1274
1275 static void
1276 my_key_free (gpointer v)
1277 {
1278   gchar *s = v;
1279   g_assert (s[0] != 'x');
1280   s[0] = 'x';
1281   g_free (v);
1282 }
1283
1284 static void
1285 my_value_free (gpointer v)
1286 {
1287   gchar *s = v;
1288   g_assert (s[0] != 'y');
1289   s[0] = 'y';
1290   g_free (v);
1291 }
1292
1293 static void
1294 test_iter_replace (void)
1295 {
1296   GHashTable *h;
1297   GHashTableIter iter;
1298   gpointer k, v;
1299   gchar *s;
1300
1301   g_test_bug ("662544");
1302
1303   h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1304
1305   g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1306   g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1307   g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1308
1309   g_hash_table_iter_init (&iter, h);
1310
1311   while (g_hash_table_iter_next (&iter, &k, &v))
1312     {
1313        s = (gchar*)v;
1314        g_assert (g_ascii_islower (s[0]));
1315        g_hash_table_iter_replace (&iter, g_strdup (k));
1316     }
1317
1318   g_hash_table_unref (h);
1319 }
1320
1321 static void
1322 replace_first_character (gchar *string)
1323 {
1324   string[0] = 'b';
1325 }
1326
1327 static void
1328 test_set_insert_corruption (void)
1329 {
1330   GHashTable *hash_table =
1331     g_hash_table_new_full (g_str_hash, g_str_equal,
1332         (GDestroyNotify) replace_first_character, NULL);
1333   GHashTableIter iter;
1334   gchar a[] = "foo";
1335   gchar b[] = "foo";
1336   gpointer key, value;
1337
1338   g_test_bug ("692815");
1339
1340   g_hash_table_insert (hash_table, a, a);
1341   g_assert (g_hash_table_contains (hash_table, "foo"));
1342
1343   g_hash_table_insert (hash_table, b, b);
1344
1345   g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1346   g_hash_table_iter_init (&iter, hash_table);
1347   if (!g_hash_table_iter_next (&iter, &key, &value))
1348     g_assert_not_reached();
1349
1350   /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1351    * and the sole key in 'hash_table' should be 'a'.
1352    */
1353   g_assert (key != b);
1354   g_assert (key == a);
1355
1356   g_assert_cmpstr (b, ==, "boo");
1357
1358   /* g_hash_table_insert() also says that the value should now be 'b',
1359    * which is probably not what the caller intended but is precisely what they
1360    * asked for.
1361    */
1362   g_assert (value == b);
1363
1364   /* even though the hash has now been de-set-ified: */
1365   g_assert (g_hash_table_contains (hash_table, "foo"));
1366
1367   g_hash_table_unref (hash_table);
1368 }
1369
1370 static void
1371 test_set_to_strv (void)
1372 {
1373   GHashTable *set;
1374   gchar **strv;
1375   guint n;
1376
1377   set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1378   g_hash_table_add (set, g_strdup ("xyz"));
1379   g_hash_table_add (set, g_strdup ("xyz"));
1380   g_hash_table_add (set, g_strdup ("abc"));
1381   strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1382   g_hash_table_steal_all (set);
1383   g_hash_table_unref (set);
1384   g_assert_cmpint (n, ==, 2);
1385   n = g_strv_length (strv);
1386   g_assert_cmpint (n, ==, 2);
1387   if (g_str_equal (strv[0], "abc"))
1388     g_assert_cmpstr (strv[1], ==, "xyz");
1389   else
1390     {
1391     g_assert_cmpstr (strv[0], ==, "xyz");
1392     g_assert_cmpstr (strv[1], ==, "abc");
1393     }
1394   g_strfreev (strv);
1395 }
1396
1397 static gboolean
1398 is_prime (guint p)
1399 {
1400   guint i;
1401
1402   if (p % 2 == 0)
1403     return FALSE;
1404
1405   i = 3;
1406   while (TRUE)
1407     {
1408       if (i * i > p)
1409         return TRUE;
1410
1411       if (p % i == 0)
1412         return FALSE;
1413
1414       i += 2;
1415     }
1416 }
1417
1418 static void
1419 test_primes (void)
1420 {
1421   guint p, q;
1422   gdouble r, min, max;
1423
1424   max = 1.0;
1425   min = 10.0;
1426   q = 1;
1427   while (1) {
1428     p = q;
1429     q = g_spaced_primes_closest (p);
1430     g_assert (is_prime (q));
1431     if (p == 1) continue;
1432     if (q == p) break;
1433     r = q / (gdouble) p;
1434     min = MIN (min, r);
1435     max = MAX (max, r);
1436   };
1437
1438   g_assert_cmpfloat (1.3, <, min);
1439   g_assert_cmpfloat (max, <, 2.0);
1440 }
1441
1442 int
1443 main (int argc, char *argv[])
1444 {
1445   g_test_init (&argc, &argv, NULL);
1446
1447   g_test_bug_base ("http://bugzilla.gnome.org/");
1448
1449   g_test_add_func ("/hash/misc", test_hash_misc);
1450   g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1451   g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1452   g_test_add_func ("/hash/direct", direct_hash_test);
1453   g_test_add_func ("/hash/direct2", direct_hash_test2);
1454   g_test_add_func ("/hash/int", int_hash_test);
1455   g_test_add_func ("/hash/int64", int64_hash_test);
1456   g_test_add_func ("/hash/double", double_hash_test);
1457   g_test_add_func ("/hash/string", string_hash_test);
1458   g_test_add_func ("/hash/set", set_hash_test);
1459   g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1460   g_test_add_func ("/hash/ref", test_hash_ref);
1461   g_test_add_func ("/hash/remove-all", test_remove_all);
1462   g_test_add_func ("/hash/find", test_find);
1463   g_test_add_func ("/hash/foreach", test_foreach);
1464   g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1465
1466   /* tests for individual bugs */
1467   g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1468   g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1469   g_test_add_func ("/hash/consistency", test_internal_consistency);
1470   g_test_add_func ("/hash/iter-replace", test_iter_replace);
1471   g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1472   g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1473   g_test_add_func ("/hash/primes", test_primes);
1474
1475   return g_test_run ();
1476
1477 }