glib/tests/hash.c

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