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
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.
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.
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/>.
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/.
26 #undef G_DISABLE_ASSERT
44 fill_hash_table_and_array (GHashTable *hash_table)
48 for (i = 0; i < 10000; i++)
51 g_hash_table_insert (hash_table, &array[i], &array[i]);
56 init_result_array (int result_array[10000])
60 for (i = 0; i < 10000; i++)
65 verify_result_array (int array[10000])
69 for (i = 0; i < 10000; i++)
70 g_assert (array[i] == i);
74 handle_pair (gpointer key, gpointer value, int result_array[10000])
78 g_assert (key == value);
82 g_assert (n >= 0 && n < 10000);
83 g_assert (result_array[n] == -1);
89 my_hash_callback_remove (gpointer key,
102 my_hash_callback_remove_test (gpointer key,
109 g_assert_not_reached ();
113 my_hash_callback (gpointer key,
117 handle_pair (key, value, user_data);
121 my_hash (gconstpointer key)
123 return (guint) *((const gint*) key);
127 my_hash_equal (gconstpointer a,
130 return *((const gint*) a) == *((const gint*) b);
136 * This is a simplified version of the pathalias hashing function.
137 * Thanks to Steve Belovin and Peter Honeyman
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.
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
152 * We reverse the bits to get:
153 * 111101010000000000000000000000001 but drop the last 1
155 * 010010000000000000000000000000001 ditto, for 31-bit crc
159 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
161 static guint CrcTable[128];
164 - crcinit - initialize tables for hash function
166 static void crcinit(void)
171 for (i = 0; i < 128; ++i)
174 for (j = 7 - 1; j >= 0; --j)
182 - hash - Honeyman's nice hashing function
185 honeyman_hash (gconstpointer key)
187 const gchar *name = (const gchar *) key;
191 g_assert (name != NULL);
192 g_assert (*name != 0);
194 size = strlen (name);
197 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
204 second_hash_cmp (gconstpointer a, gconstpointer b)
206 return strcmp (a, b) == 0;
212 one_hash (gconstpointer key)
219 not_even_foreach (gpointer key,
223 const char *_key = (const char *) key;
224 const char *_value = (const char *) value;
228 g_assert (_key != NULL);
229 g_assert (*_key != 0);
230 g_assert (_value != NULL);
231 g_assert (*_value != 0);
235 sprintf (val, "%d value", i);
236 g_assert (strcmp (_value, val) == 0);
238 g_assert ((i % 2) != 0);
243 remove_even_foreach (gpointer key,
247 const char *_key = (const char *) key;
248 const char *_value = (const char *) value;
252 g_assert (_key != NULL);
253 g_assert (*_key != 0);
254 g_assert (_value != NULL);
255 g_assert (*_value != 0);
259 sprintf (val, "%d value", i);
260 g_assert (strcmp (_value, val) == 0);
262 return ((i % 2) == 0) ? TRUE : FALSE;
269 second_hash_test (gconstpointer d)
271 gboolean simple_hash = GPOINTER_TO_INT (d);
274 char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
280 h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
283 g_assert (h != NULL);
284 for (i = 0; i < 20; i++)
286 sprintf (key, "%d", i);
287 g_assert (atoi (key) == i);
289 sprintf (val, "%d value", i);
290 g_assert (atoi (val) == i);
292 g_hash_table_insert (h, g_strdup (key), g_strdup (val));
295 g_assert (g_hash_table_size (h) == 20);
297 for (i = 0; i < 20; i++)
299 sprintf (key, "%d", i);
300 g_assert (atoi(key) == i);
302 v = (char *) g_hash_table_lookup (h, key);
304 g_assert (v != NULL);
306 g_assert (atoi (v) == i);
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);
316 for (i = 0; i < 20; i++)
318 sprintf (key, "%d", i);
319 g_assert (atoi(key) == i);
321 sprintf (val, "%d value", i);
322 g_assert (atoi (val) == i);
324 orig_key = orig_val = NULL;
325 found = g_hash_table_lookup_extended (h, key,
327 (gpointer)&orig_val);
328 if ((i % 2) == 0 || i == 3)
336 g_assert (orig_key != NULL);
337 g_assert (strcmp (key, orig_key) == 0);
339 g_assert (orig_val != NULL);
340 g_assert (strcmp (val, orig_val) == 0);
343 g_hash_table_destroy (h);
347 find_first (gpointer key,
352 gint *test = user_data;
353 return (*v == *test);
357 direct_hash_test (void)
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));
368 g_assert (g_hash_table_size (h) == 20);
370 for (i = 1; i <= 20; i++)
372 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
375 g_assert ((rc - 42) == i);
378 g_hash_table_destroy (h);
382 direct_hash_test2 (void)
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));
393 g_assert (g_hash_table_size (h) == 20);
395 for (i = 1; i <= 20; i++)
397 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
400 g_assert ((rc - 42) == i);
403 g_hash_table_destroy (h);
414 h = g_hash_table_new (g_int_hash, g_int_equal);
415 g_assert (h != NULL);
416 for (i = 0; i < 20; i++)
419 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
422 g_assert (g_hash_table_size (h) == 20);
424 for (i = 0; i < 20; i++)
427 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
429 g_assert_cmpint (rc, ==, i + 42);
432 g_hash_table_destroy (h);
436 int64_hash_test (void)
443 h = g_hash_table_new (g_int64_hash, g_int64_equal);
444 g_assert (h != NULL);
445 for (i = 0; i < 20; i++)
448 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
451 g_assert (g_hash_table_size (h) == 20);
453 for (i = 0; i < 20; i++)
456 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
458 g_assert_cmpint (rc, ==, i + 42);
461 g_hash_table_destroy (h);
465 double_hash_test (void)
472 h = g_hash_table_new (g_double_hash, g_double_equal);
473 g_assert (h != NULL);
474 for (i = 0; i < 20; i++)
476 values[i] = i + 42.5;
477 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
480 g_assert (g_hash_table_size (h) == 20);
482 for (i = 0; i < 20; i++)
485 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
487 g_assert_cmpint (rc, ==, i + 42);
490 g_hash_table_destroy (h);
494 string_free (gpointer data)
498 g_string_free (s, TRUE);
502 string_hash_test (void)
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++)
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));
519 g_assert (g_hash_table_size (h) == 20);
521 s = g_string_new ("");
522 for (i = 0; i < 20; i++)
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));
530 g_assert_cmpint (rc, ==, i + 42);
533 g_string_free (s, TRUE);
534 g_hash_table_destroy (h);
538 set_check (gpointer key,
544 g_assert_not_reached ();
546 g_assert_cmpint (atoi (key) % 7, ==, 2);
554 GHashTable *hash_table =
555 g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
558 for (i = 2; i < 5000; i += 7)
560 char *s = g_strdup_printf ("%d", i);
561 g_assert (g_hash_table_add (hash_table, s));
564 g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
567 g_hash_table_foreach (hash_table, set_check, &i);
568 g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
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"));
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"));
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"));
581 g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
582 g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
584 g_hash_table_destroy (hash_table);
589 test_hash_misc (void)
591 GHashTable *hash_table;
595 GList *keys, *values;
596 gint keys_len, values_len;
598 gpointer ikey, ivalue;
599 int result_array[10000];
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();
608 keys = g_hash_table_get_keys (hash_table);
610 g_assert_not_reached ();
612 values = g_hash_table_get_values (hash_table);
614 g_assert_not_reached ();
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 ();
622 g_list_free (values);
624 init_result_array (result_array);
625 g_hash_table_iter_init (&iter, hash_table);
626 for (i = 0; i < 10000; i++)
628 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
630 handle_pair (ikey, ivalue, result_array);
633 g_hash_table_iter_remove (&iter);
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);
639 fill_hash_table_and_array (hash_table);
641 init_result_array (result_array);
642 g_hash_table_foreach (hash_table, my_hash_callback, result_array);
643 verify_result_array (result_array);
645 for (i = 0; i < 10000; i++)
646 g_hash_table_remove (hash_table, &array[i]);
648 fill_hash_table_and_array (hash_table);
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();
654 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
655 g_hash_table_destroy (hash_table);
657 hash_table = g_hash_table_new (my_hash, my_hash_equal);
658 fill_hash_table_and_array (hash_table);
662 g_hash_table_iter_init (&iter, hash_table);
663 for (i = 0; i < 10000; i++)
665 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
666 g_hash_table_iter_replace (&iter, &n_array[0]);
669 g_hash_table_iter_init (&iter, hash_table);
670 for (i = 0; i < 10000; i++)
672 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
674 g_assert (ivalue == &n_array[0]);
677 g_hash_table_destroy (hash_table);
680 static gint destroy_counter;
683 value_destroy (gpointer value)
694 gboolean abc_seen = FALSE;
695 gboolean cde_seen = FALSE;
696 gboolean xyz_seen = FALSE;
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");
703 g_assert_cmpint (g_hash_table_size (h), == , 3);
705 g_hash_table_iter_init (&iter, h);
707 while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
709 if (strcmp (key, "abc") == 0)
711 g_assert_cmpstr (value, ==, "ABC");
713 g_hash_table_iter_steal (&iter);
715 else if (strcmp (key, "cde") == 0)
717 g_assert_cmpstr (value, ==, "CDE");
720 else if (strcmp (key, "xyz") == 0)
722 g_assert_cmpstr (value, ==, "XYZ");
726 g_assert_cmpint (destroy_counter, ==, 0);
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);
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);
742 null_safe_str_hash (gconstpointer key)
747 return g_str_hash (key);
751 null_safe_str_equal (gconstpointer a, gconstpointer b)
753 return g_strcmp0 (a, b) == 0;
757 test_lookup_null_key (void)
764 g_test_bug ("642944");
766 h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
767 g_hash_table_insert (h, "abc", "ABC");
769 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
772 g_hash_table_insert (h, NULL, "NULL");
774 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
776 g_assert_cmpstr (value, ==, "NULL");
778 g_hash_table_unref (h);
781 static gint destroy_key_counter;
784 key_destroy (gpointer key)
786 destroy_key_counter++;
790 test_remove_all (void)
795 h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
797 g_hash_table_insert (h, "abc", "cde");
798 g_hash_table_insert (h, "cde", "xyz");
799 g_hash_table_insert (h, "xyz", "abc");
802 destroy_key_counter = 0;
804 g_hash_table_steal_all (h);
805 g_assert_cmpint (destroy_counter, ==, 0);
806 g_assert_cmpint (destroy_key_counter, ==, 0);
808 g_hash_table_insert (h, "abc", "ABC");
809 g_hash_table_insert (h, "cde", "CDE");
810 g_hash_table_insert (h, "xyz", "XYZ");
812 res = g_hash_table_steal (h, "nosuchkey");
814 g_assert_cmpint (destroy_counter, ==, 0);
815 g_assert_cmpint (destroy_key_counter, ==, 0);
817 res = g_hash_table_steal (h, "xyz");
819 g_assert_cmpint (destroy_counter, ==, 0);
820 g_assert_cmpint (destroy_key_counter, ==, 0);
822 g_hash_table_remove_all (h);
823 g_assert_cmpint (destroy_counter, ==, 2);
824 g_assert_cmpint (destroy_key_counter, ==, 2);
826 g_hash_table_unref (h);
829 GHashTable *recursive_destruction_table = NULL;
831 recursive_value_destroy (gpointer value)
835 if (recursive_destruction_table)
836 g_hash_table_remove (recursive_destruction_table, value);
840 test_recursive_remove_all_subprocess (void)
844 h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
845 recursive_destruction_table = h;
847 /* Add more items compared to test_remove_all, as it would not fail otherwise. */
848 g_hash_table_insert (h, "abc", "cde");
849 g_hash_table_insert (h, "cde", "fgh");
850 g_hash_table_insert (h, "fgh", "ijk");
851 g_hash_table_insert (h, "ijk", "lmn");
852 g_hash_table_insert (h, "lmn", "opq");
853 g_hash_table_insert (h, "opq", "rst");
854 g_hash_table_insert (h, "rst", "uvw");
855 g_hash_table_insert (h, "uvw", "xyz");
856 g_hash_table_insert (h, "xyz", "abc");
859 destroy_key_counter = 0;
861 g_hash_table_remove_all (h);
862 g_assert_cmpint (destroy_counter, ==, 9);
863 g_assert_cmpint (destroy_key_counter, ==, 9);
865 g_hash_table_unref (h);
869 test_recursive_remove_all (void)
871 g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000, 0);
872 g_test_trap_assert_passed ();
881 hash_func (gconstpointer key)
883 const RefCountedKey *rkey = key;
885 return g_str_hash (rkey->key);
889 eq_func (gconstpointer a, gconstpointer b)
891 const RefCountedKey *aa = a;
892 const RefCountedKey *bb = b;
894 return g_strcmp0 (aa->key, bb->key) == 0;
898 key_unref (gpointer data)
900 RefCountedKey *key = data;
902 g_assert (key->ref_count > 0);
906 if (key->ref_count == 0)
910 static RefCountedKey *
911 key_ref (RefCountedKey *key)
918 static RefCountedKey *
919 key_new (const gchar *key)
923 rkey = g_new (RefCountedKey, 1);
932 set_ref_hash_test (void)
938 h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
940 key1 = key_new ("a");
941 key2 = key_new ("a");
943 g_assert_cmpint (key1->ref_count, ==, 1);
944 g_assert_cmpint (key2->ref_count, ==, 1);
946 g_hash_table_insert (h, key_ref (key1), key_ref (key1));
948 g_assert_cmpint (key1->ref_count, ==, 3);
949 g_assert_cmpint (key2->ref_count, ==, 1);
951 g_hash_table_replace (h, key_ref (key2), key_ref (key2));
953 g_assert_cmpint (key1->ref_count, ==, 1);
954 g_assert_cmpint (key2->ref_count, ==, 3);
956 g_hash_table_remove (h, key1);
958 g_assert_cmpint (key1->ref_count, ==, 1);
959 g_assert_cmpint (key2->ref_count, ==, 1);
961 g_hash_table_unref (h);
974 GPtrArray *fake_free_data;
977 fake_free (gpointer dead)
981 for (i = 0; i < fake_free_data->len; i++)
983 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
985 if (ffd->string == (gchar *) dead)
987 g_assert (!ffd->freed);
993 g_assert_not_reached ();
997 value_destroy_insert (gpointer value)
999 g_hash_table_remove_all (h);
1003 test_destroy_modify (void)
1008 g_test_bug ("650459");
1010 fake_free_data = g_ptr_array_new ();
1012 h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
1014 ffd = g_new0 (FakeFreeData, 1);
1015 ffd->string = g_strdup ("a");
1016 g_ptr_array_add (fake_free_data, ffd);
1017 g_hash_table_insert (h, ffd->string, "b");
1019 ffd = g_new0 (FakeFreeData, 1);
1020 ffd->string = g_strdup ("c");
1021 g_ptr_array_add (fake_free_data, ffd);
1022 g_hash_table_insert (h, ffd->string, "d");
1024 ffd = g_new0 (FakeFreeData, 1);
1025 ffd->string = g_strdup ("e");
1026 g_ptr_array_add (fake_free_data, ffd);
1027 g_hash_table_insert (h, ffd->string, "f");
1029 ffd = g_new0 (FakeFreeData, 1);
1030 ffd->string = g_strdup ("g");
1031 g_ptr_array_add (fake_free_data, ffd);
1032 g_hash_table_insert (h, ffd->string, "h");
1034 ffd = g_new0 (FakeFreeData, 1);
1035 ffd->string = g_strdup ("h");
1036 g_ptr_array_add (fake_free_data, ffd);
1037 g_hash_table_insert (h, ffd->string, "k");
1039 ffd = g_new0 (FakeFreeData, 1);
1040 ffd->string = g_strdup ("a");
1041 g_ptr_array_add (fake_free_data, ffd);
1042 g_hash_table_insert (h, ffd->string, "c");
1044 g_hash_table_remove (h, "c");
1046 /* that removed everything... */
1047 for (i = 0; i < fake_free_data->len; i++)
1049 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1051 g_assert (ffd->freed);
1052 g_free (ffd->string);
1056 g_ptr_array_unref (fake_free_data);
1058 /* ... so this is a no-op */
1059 g_hash_table_remove (h, "e");
1061 g_hash_table_unref (h);
1065 find_str (gpointer key, gpointer value, gpointer data)
1067 return g_str_equal (key, data);
1076 hash = g_hash_table_new (g_str_hash, g_str_equal);
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");
1085 value = g_hash_table_find (hash, find_str, "a");
1086 g_assert_cmpstr (value, ==, "A");
1088 value = g_hash_table_find (hash, find_str, "b");
1089 g_assert_cmpstr (value, ==, "B");
1091 value = g_hash_table_find (hash, find_str, "c");
1092 g_assert_cmpstr (value, ==, "C");
1094 value = g_hash_table_find (hash, find_str, "d");
1095 g_assert_cmpstr (value, ==, "D");
1097 value = g_hash_table_find (hash, find_str, "e");
1098 g_assert_cmpstr (value, ==, "E");
1100 value = g_hash_table_find (hash, find_str, "f");
1101 g_assert_cmpstr (value, ==, "F");
1103 value = g_hash_table_find (hash, find_str, "0");
1104 g_assert (value == NULL);
1106 g_hash_table_unref (hash);
1109 gboolean seen_key[6];
1112 foreach_func (gpointer key, gpointer value, gpointer data)
1114 seen_key[((char*)key)[0] - 'a'] = TRUE;
1123 hash = g_hash_table_new (g_str_hash, g_str_equal);
1125 g_hash_table_insert (hash, "a", "A");
1126 g_hash_table_insert (hash, "b", "B");
1127 g_hash_table_insert (hash, "c", "C");
1128 g_hash_table_insert (hash, "d", "D");
1129 g_hash_table_insert (hash, "e", "E");
1130 g_hash_table_insert (hash, "f", "F");
1132 for (i = 0; i < 6; i++)
1133 seen_key[i] = FALSE;
1135 g_hash_table_foreach (hash, foreach_func, NULL);
1137 for (i = 0; i < 6; i++)
1138 g_assert (seen_key[i]);
1140 g_hash_table_unref (hash);
1144 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1146 GHashTable *hash2 = data;
1148 if (strstr ("ace", (gchar*)key))
1150 g_hash_table_insert (hash2, key, value);
1159 test_foreach_steal (void)
1164 hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1165 hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1167 g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1168 g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1169 g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1170 g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1171 g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1172 g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1174 g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1176 g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1177 g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1179 g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1180 g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1181 g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1182 g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1183 g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1184 g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1186 g_hash_table_unref (hash);
1187 g_hash_table_unref (hash2);
1196 gint noccupied; /* nnodes + tombstones */
1202 GHashFunc hash_func;
1203 GEqualFunc key_equal_func;
1204 volatile gint ref_count;
1206 #ifndef G_DISABLE_ASSERT
1209 GDestroyNotify key_destroy_func;
1210 GDestroyNotify value_destroy_func;
1214 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1221 for (i = 0; i < h->size; i++)
1223 if (h->hashes[i] == 0)
1225 else if (h->hashes[i] == 1)
1233 check_data (GHashTable *h)
1237 for (i = 0; i < h->size; i++)
1239 if (h->hashes[i] < 2)
1241 g_assert (h->keys[i] == NULL);
1242 g_assert (h->values[i] == NULL);
1246 g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1252 check_consistency (GHashTable *h)
1258 count_keys (h, &unused, &occupied, &tombstones);
1260 g_assert_cmpint (occupied, ==, h->nnodes);
1261 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1262 g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1268 check_counts (GHashTable *h, gint occupied, gint tombstones)
1270 g_assert_cmpint (occupied, ==, h->nnodes);
1271 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1275 trivial_key_destroy (gpointer key)
1280 test_internal_consistency (void)
1284 h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1286 check_counts (h, 0, 0);
1287 check_consistency (h);
1289 g_hash_table_insert (h, "a", "A");
1290 g_hash_table_insert (h, "b", "B");
1291 g_hash_table_insert (h, "c", "C");
1292 g_hash_table_insert (h, "d", "D");
1293 g_hash_table_insert (h, "e", "E");
1294 g_hash_table_insert (h, "f", "F");
1296 check_counts (h, 6, 0);
1297 check_consistency (h);
1299 g_hash_table_remove (h, "a");
1300 check_counts (h, 5, 1);
1301 check_consistency (h);
1303 g_hash_table_remove (h, "b");
1304 check_counts (h, 4, 2);
1305 check_consistency (h);
1307 g_hash_table_insert (h, "c", "c");
1308 check_counts (h, 4, 2);
1309 check_consistency (h);
1311 g_hash_table_insert (h, "a", "A");
1312 check_counts (h, 5, 1);
1313 check_consistency (h);
1315 g_hash_table_remove_all (h);
1316 check_counts (h, 0, 0);
1317 check_consistency (h);
1319 g_hash_table_unref (h);
1323 my_key_free (gpointer v)
1326 g_assert (s[0] != 'x');
1332 my_value_free (gpointer v)
1335 g_assert (s[0] != 'y');
1341 test_iter_replace (void)
1344 GHashTableIter iter;
1348 g_test_bug ("662544");
1350 h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1352 g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1353 g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1354 g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1356 g_hash_table_iter_init (&iter, h);
1358 while (g_hash_table_iter_next (&iter, &k, &v))
1361 g_assert (g_ascii_islower (s[0]));
1362 g_hash_table_iter_replace (&iter, g_strdup (k));
1365 g_hash_table_unref (h);
1369 replace_first_character (gchar *string)
1375 test_set_insert_corruption (void)
1377 GHashTable *hash_table =
1378 g_hash_table_new_full (g_str_hash, g_str_equal,
1379 (GDestroyNotify) replace_first_character, NULL);
1380 GHashTableIter iter;
1383 gpointer key, value;
1385 g_test_bug ("692815");
1387 g_hash_table_insert (hash_table, a, a);
1388 g_assert (g_hash_table_contains (hash_table, "foo"));
1390 g_hash_table_insert (hash_table, b, b);
1392 g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1393 g_hash_table_iter_init (&iter, hash_table);
1394 if (!g_hash_table_iter_next (&iter, &key, &value))
1395 g_assert_not_reached();
1397 /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1398 * and the sole key in 'hash_table' should be 'a'.
1400 g_assert (key != b);
1401 g_assert (key == a);
1403 g_assert_cmpstr (b, ==, "boo");
1405 /* g_hash_table_insert() also says that the value should now be 'b',
1406 * which is probably not what the caller intended but is precisely what they
1409 g_assert (value == b);
1411 /* even though the hash has now been de-set-ified: */
1412 g_assert (g_hash_table_contains (hash_table, "foo"));
1414 g_hash_table_unref (hash_table);
1418 test_set_to_strv (void)
1424 set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1425 g_hash_table_add (set, g_strdup ("xyz"));
1426 g_hash_table_add (set, g_strdup ("xyz"));
1427 g_hash_table_add (set, g_strdup ("abc"));
1428 strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1429 g_hash_table_steal_all (set);
1430 g_hash_table_unref (set);
1431 g_assert_cmpint (n, ==, 2);
1432 n = g_strv_length (strv);
1433 g_assert_cmpint (n, ==, 2);
1434 if (g_str_equal (strv[0], "abc"))
1435 g_assert_cmpstr (strv[1], ==, "xyz");
1438 g_assert_cmpstr (strv[0], ==, "xyz");
1439 g_assert_cmpstr (strv[1], ==, "abc");
1469 gdouble r, min, max;
1476 q = g_spaced_primes_closest (p);
1477 g_assert (is_prime (q));
1478 if (p == 1) continue;
1480 r = q / (gdouble) p;
1485 g_assert_cmpfloat (1.3, <, min);
1486 g_assert_cmpfloat (max, <, 2.0);
1490 main (int argc, char *argv[])
1492 g_test_init (&argc, &argv, NULL);
1494 g_test_bug_base ("http://bugzilla.gnome.org/");
1496 g_test_add_func ("/hash/misc", test_hash_misc);
1497 g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1498 g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1499 g_test_add_func ("/hash/direct", direct_hash_test);
1500 g_test_add_func ("/hash/direct2", direct_hash_test2);
1501 g_test_add_func ("/hash/int", int_hash_test);
1502 g_test_add_func ("/hash/int64", int64_hash_test);
1503 g_test_add_func ("/hash/double", double_hash_test);
1504 g_test_add_func ("/hash/string", string_hash_test);
1505 g_test_add_func ("/hash/set", set_hash_test);
1506 g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1507 g_test_add_func ("/hash/ref", test_hash_ref);
1508 g_test_add_func ("/hash/remove-all", test_remove_all);
1509 g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
1510 g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
1511 g_test_add_func ("/hash/find", test_find);
1512 g_test_add_func ("/hash/foreach", test_foreach);
1513 g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1515 /* tests for individual bugs */
1516 g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1517 g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1518 g_test_add_func ("/hash/consistency", test_internal_consistency);
1519 g_test_add_func ("/hash/iter-replace", test_iter_replace);
1520 g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1521 g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1522 g_test_add_func ("/hash/primes", test_primes);
1524 return g_test_run ();