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, write to the
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 * Boston, MA 02111-1307, USA.
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/.
28 #undef G_DISABLE_ASSERT
46 fill_hash_table_and_array (GHashTable *hash_table)
50 for (i = 0; i < 10000; i++)
53 g_hash_table_insert (hash_table, &array[i], &array[i]);
58 init_result_array (int result_array[10000])
62 for (i = 0; i < 10000; i++)
67 verify_result_array (int array[10000])
71 for (i = 0; i < 10000; i++)
72 g_assert (array[i] == i);
76 handle_pair (gpointer key, gpointer value, int result_array[10000])
80 g_assert (key == value);
84 g_assert (n >= 0 && n < 10000);
85 g_assert (result_array[n] == -1);
91 my_hash_callback_remove (gpointer key,
104 my_hash_callback_remove_test (gpointer key,
111 g_assert_not_reached ();
115 my_hash_callback (gpointer key,
119 handle_pair (key, value, user_data);
123 my_hash (gconstpointer key)
125 return (guint) *((const gint*) key);
129 my_hash_equal (gconstpointer a,
132 return *((const gint*) a) == *((const gint*) b);
138 * This is a simplified version of the pathalias hashing function.
139 * Thanks to Steve Belovin and Peter Honeyman
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.
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
154 * We reverse the bits to get:
155 * 111101010000000000000000000000001 but drop the last 1
157 * 010010000000000000000000000000001 ditto, for 31-bit crc
161 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
163 static guint CrcTable[128];
166 - crcinit - initialize tables for hash function
168 static void crcinit(void)
173 for (i = 0; i < 128; ++i)
176 for (j = 7 - 1; j >= 0; --j)
184 - hash - Honeyman's nice hashing function
187 honeyman_hash (gconstpointer key)
189 const gchar *name = (const gchar *) key;
193 g_assert (name != NULL);
194 g_assert (*name != 0);
196 size = strlen (name);
199 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
206 second_hash_cmp (gconstpointer a, gconstpointer b)
208 return strcmp (a, b) == 0;
214 one_hash (gconstpointer key)
221 not_even_foreach (gpointer key,
225 const char *_key = (const char *) key;
226 const char *_value = (const char *) value;
230 g_assert (_key != NULL);
231 g_assert (*_key != 0);
232 g_assert (_value != NULL);
233 g_assert (*_value != 0);
237 sprintf (val, "%d value", i);
238 g_assert (strcmp (_value, val) == 0);
240 g_assert ((i % 2) != 0);
245 remove_even_foreach (gpointer key,
249 const char *_key = (const char *) key;
250 const char *_value = (const char *) value;
254 g_assert (_key != NULL);
255 g_assert (*_key != 0);
256 g_assert (_value != NULL);
257 g_assert (*_value != 0);
261 sprintf (val, "%d value", i);
262 g_assert (strcmp (_value, val) == 0);
264 return ((i % 2) == 0) ? TRUE : FALSE;
271 second_hash_test (gconstpointer d)
273 gboolean simple_hash = GPOINTER_TO_INT (d);
276 char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
282 h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
285 g_assert (h != NULL);
286 for (i = 0; i < 20; i++)
288 sprintf (key, "%d", i);
289 g_assert (atoi (key) == i);
291 sprintf (val, "%d value", i);
292 g_assert (atoi (val) == i);
294 g_hash_table_insert (h, g_strdup (key), g_strdup (val));
297 g_assert (g_hash_table_size (h) == 20);
299 for (i = 0; i < 20; i++)
301 sprintf (key, "%d", i);
302 g_assert (atoi(key) == i);
304 v = (char *) g_hash_table_lookup (h, key);
306 g_assert (v != NULL);
308 g_assert (atoi (v) == i);
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);
318 for (i = 0; i < 20; i++)
320 sprintf (key, "%d", i);
321 g_assert (atoi(key) == i);
323 sprintf (val, "%d value", i);
324 g_assert (atoi (val) == i);
326 orig_key = orig_val = NULL;
327 found = g_hash_table_lookup_extended (h, key,
329 (gpointer)&orig_val);
330 if ((i % 2) == 0 || i == 3)
338 g_assert (orig_key != NULL);
339 g_assert (strcmp (key, orig_key) == 0);
341 g_assert (orig_val != NULL);
342 g_assert (strcmp (val, orig_val) == 0);
345 g_hash_table_destroy (h);
349 find_first (gpointer key,
354 gint *test = user_data;
355 return (*v == *test);
359 direct_hash_test (void)
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));
370 g_assert (g_hash_table_size (h) == 20);
372 for (i = 1; i <= 20; i++)
374 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
377 g_assert ((rc - 42) == i);
380 g_hash_table_destroy (h);
384 direct_hash_test2 (void)
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));
395 g_assert (g_hash_table_size (h) == 20);
397 for (i = 1; i <= 20; i++)
399 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
402 g_assert ((rc - 42) == i);
405 g_hash_table_destroy (h);
416 h = g_hash_table_new (g_int_hash, g_int_equal);
417 g_assert (h != NULL);
418 for (i = 0; i < 20; i++)
421 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
424 g_assert (g_hash_table_size (h) == 20);
426 for (i = 0; i < 20; i++)
429 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
431 g_assert_cmpint (rc, ==, i + 42);
434 g_hash_table_destroy (h);
438 int64_hash_test (void)
445 h = g_hash_table_new (g_int64_hash, g_int64_equal);
446 g_assert (h != NULL);
447 for (i = 0; i < 20; i++)
450 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
453 g_assert (g_hash_table_size (h) == 20);
455 for (i = 0; i < 20; i++)
458 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
460 g_assert_cmpint (rc, ==, i + 42);
463 g_hash_table_destroy (h);
467 double_hash_test (void)
474 h = g_hash_table_new (g_double_hash, g_double_equal);
475 g_assert (h != NULL);
476 for (i = 0; i < 20; i++)
478 values[i] = i + 42.5;
479 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
482 g_assert (g_hash_table_size (h) == 20);
484 for (i = 0; i < 20; i++)
487 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
489 g_assert_cmpint (rc, ==, i + 42);
492 g_hash_table_destroy (h);
496 string_free (gpointer data)
500 g_string_free (s, TRUE);
504 string_hash_test (void)
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++)
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));
521 g_assert (g_hash_table_size (h) == 20);
523 s = g_string_new ("");
524 for (i = 0; i < 20; i++)
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));
532 g_assert_cmpint (rc, ==, i + 42);
535 g_string_free (s, TRUE);
536 g_hash_table_destroy (h);
540 set_check (gpointer key,
546 g_assert_not_reached ();
548 g_assert_cmpint (atoi (key) % 7, ==, 2);
556 GHashTable *hash_table =
557 g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
560 for (i = 2; i < 5000; i += 7)
562 char *s = g_strdup_printf ("%d", i);
563 g_assert (g_hash_table_add (hash_table, s));
566 g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
569 g_hash_table_foreach (hash_table, set_check, &i);
570 g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
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"));
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"));
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"));
583 g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
584 g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
586 g_hash_table_destroy (hash_table);
591 test_hash_misc (void)
593 GHashTable *hash_table;
597 GList *keys, *values;
598 gint keys_len, values_len;
600 gpointer ikey, ivalue;
601 int result_array[10000];
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();
610 keys = g_hash_table_get_keys (hash_table);
612 g_assert_not_reached ();
614 values = g_hash_table_get_values (hash_table);
616 g_assert_not_reached ();
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 ();
624 g_list_free (values);
626 init_result_array (result_array);
627 g_hash_table_iter_init (&iter, hash_table);
628 for (i = 0; i < 10000; i++)
630 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
632 handle_pair (ikey, ivalue, result_array);
635 g_hash_table_iter_remove (&iter);
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);
641 fill_hash_table_and_array (hash_table);
643 init_result_array (result_array);
644 g_hash_table_foreach (hash_table, my_hash_callback, result_array);
645 verify_result_array (result_array);
647 for (i = 0; i < 10000; i++)
648 g_hash_table_remove (hash_table, &array[i]);
650 fill_hash_table_and_array (hash_table);
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();
656 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
657 g_hash_table_destroy (hash_table);
659 hash_table = g_hash_table_new (my_hash, my_hash_equal);
660 fill_hash_table_and_array (hash_table);
664 g_hash_table_iter_init (&iter, hash_table);
665 for (i = 0; i < 10000; i++)
667 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
668 g_hash_table_iter_replace (&iter, &n_array[0]);
671 g_hash_table_iter_init (&iter, hash_table);
672 for (i = 0; i < 10000; i++)
674 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
676 g_assert (ivalue == &n_array[0]);
679 g_hash_table_destroy (hash_table);
682 static gint destroy_counter;
685 value_destroy (gpointer value)
696 gboolean abc_seen = FALSE;
697 gboolean cde_seen = FALSE;
698 gboolean xyz_seen = FALSE;
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");
705 g_assert_cmpint (g_hash_table_size (h), == , 3);
707 g_hash_table_iter_init (&iter, h);
709 while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
711 if (strcmp (key, "abc") == 0)
713 g_assert_cmpstr (value, ==, "ABC");
715 g_hash_table_iter_steal (&iter);
717 else if (strcmp (key, "cde") == 0)
719 g_assert_cmpstr (value, ==, "CDE");
722 else if (strcmp (key, "xyz") == 0)
724 g_assert_cmpstr (value, ==, "XYZ");
728 g_assert_cmpint (destroy_counter, ==, 0);
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);
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);
744 null_safe_str_hash (gconstpointer key)
749 return g_str_hash (key);
753 null_safe_str_equal (gconstpointer a, gconstpointer b)
755 return g_strcmp0 (a, b) == 0;
759 test_lookup_null_key (void)
766 g_test_bug ("642944");
768 h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
769 g_hash_table_insert (h, "abc", "ABC");
771 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
774 g_hash_table_insert (h, NULL, "NULL");
776 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
778 g_assert_cmpstr (value, ==, "NULL");
780 g_hash_table_unref (h);
783 static gint destroy_key_counter;
786 key_destroy (gpointer key)
788 destroy_key_counter++;
792 test_remove_all (void)
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");
803 destroy_key_counter = 0;
805 g_hash_table_steal_all (h);
806 g_assert_cmpint (destroy_counter, ==, 0);
807 g_assert_cmpint (destroy_key_counter, ==, 0);
809 g_hash_table_insert (h, "abc", "ABC");
810 g_hash_table_insert (h, "cde", "CDE");
811 g_hash_table_insert (h, "xyz", "XYZ");
813 res = g_hash_table_steal (h, "nosuchkey");
815 g_assert_cmpint (destroy_counter, ==, 0);
816 g_assert_cmpint (destroy_key_counter, ==, 0);
818 res = g_hash_table_steal (h, "xyz");
820 g_assert_cmpint (destroy_counter, ==, 0);
821 g_assert_cmpint (destroy_key_counter, ==, 0);
823 g_hash_table_remove_all (h);
824 g_assert_cmpint (destroy_counter, ==, 2);
825 g_assert_cmpint (destroy_key_counter, ==, 2);
827 g_hash_table_unref (h);
836 hash_func (gconstpointer key)
838 const RefCountedKey *rkey = key;
840 return g_str_hash (rkey->key);
844 eq_func (gconstpointer a, gconstpointer b)
846 const RefCountedKey *aa = a;
847 const RefCountedKey *bb = b;
849 return g_strcmp0 (aa->key, bb->key) == 0;
853 key_unref (gpointer data)
855 RefCountedKey *key = data;
857 g_assert (key->ref_count > 0);
861 if (key->ref_count == 0)
865 static RefCountedKey *
866 key_ref (RefCountedKey *key)
873 static RefCountedKey *
874 key_new (const gchar *key)
878 rkey = g_new (RefCountedKey, 1);
887 set_ref_hash_test (void)
893 h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
895 key1 = key_new ("a");
896 key2 = key_new ("a");
898 g_assert_cmpint (key1->ref_count, ==, 1);
899 g_assert_cmpint (key2->ref_count, ==, 1);
901 g_hash_table_insert (h, key_ref (key1), key_ref (key1));
903 g_assert_cmpint (key1->ref_count, ==, 3);
904 g_assert_cmpint (key2->ref_count, ==, 1);
906 g_hash_table_replace (h, key_ref (key2), key_ref (key2));
908 g_assert_cmpint (key1->ref_count, ==, 1);
909 g_assert_cmpint (key2->ref_count, ==, 3);
911 g_hash_table_remove (h, key1);
913 g_assert_cmpint (key1->ref_count, ==, 1);
914 g_assert_cmpint (key2->ref_count, ==, 1);
916 g_hash_table_unref (h);
929 GPtrArray *fake_free_data;
932 fake_free (gpointer dead)
936 for (i = 0; i < fake_free_data->len; i++)
938 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
940 if (ffd->string == (gchar *) dead)
942 g_assert (!ffd->freed);
948 g_assert_not_reached ();
952 value_destroy_insert (gpointer value)
954 g_hash_table_remove_all (h);
958 test_destroy_modify (void)
963 g_test_bug ("650459");
965 fake_free_data = g_ptr_array_new ();
967 h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
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");
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");
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");
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");
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");
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");
999 g_hash_table_remove (h, "c");
1001 /* that removed everything... */
1002 for (i = 0; i < fake_free_data->len; i++)
1004 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1006 g_assert (ffd->freed);
1007 g_free (ffd->string);
1011 g_ptr_array_unref (fake_free_data);
1013 /* ... so this is a no-op */
1014 g_hash_table_remove (h, "e");
1016 g_hash_table_unref (h);
1020 find_str (gpointer key, gpointer value, gpointer data)
1022 return g_str_equal (key, data);
1031 hash = g_hash_table_new (g_str_hash, g_str_equal);
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");
1040 value = g_hash_table_find (hash, find_str, "a");
1041 g_assert_cmpstr (value, ==, "A");
1043 value = g_hash_table_find (hash, find_str, "b");
1044 g_assert_cmpstr (value, ==, "B");
1046 value = g_hash_table_find (hash, find_str, "c");
1047 g_assert_cmpstr (value, ==, "C");
1049 value = g_hash_table_find (hash, find_str, "d");
1050 g_assert_cmpstr (value, ==, "D");
1052 value = g_hash_table_find (hash, find_str, "e");
1053 g_assert_cmpstr (value, ==, "E");
1055 value = g_hash_table_find (hash, find_str, "f");
1056 g_assert_cmpstr (value, ==, "F");
1058 value = g_hash_table_find (hash, find_str, "0");
1059 g_assert (value == NULL);
1061 g_hash_table_unref (hash);
1064 gboolean seen_key[6];
1067 foreach_func (gpointer key, gpointer value, gpointer data)
1069 seen_key[((char*)key)[0] - 'a'] = TRUE;
1078 hash = g_hash_table_new (g_str_hash, g_str_equal);
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");
1087 for (i = 0; i < 6; i++)
1088 seen_key[i] = FALSE;
1090 g_hash_table_foreach (hash, foreach_func, NULL);
1092 for (i = 0; i < 6; i++)
1093 g_assert (seen_key[i]);
1095 g_hash_table_unref (hash);
1099 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1101 GHashTable *hash2 = data;
1103 if (strstr ("ace", (gchar*)key))
1105 g_hash_table_insert (hash2, key, value);
1114 test_foreach_steal (void)
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);
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"));
1129 g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1131 g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1132 g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
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");
1141 g_hash_table_unref (hash);
1142 g_hash_table_unref (hash2);
1151 gint noccupied; /* nnodes + tombstones */
1157 GHashFunc hash_func;
1158 GEqualFunc key_equal_func;
1159 volatile gint ref_count;
1161 #ifndef G_DISABLE_ASSERT
1164 GDestroyNotify key_destroy_func;
1165 GDestroyNotify value_destroy_func;
1169 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1176 for (i = 0; i < h->size; i++)
1178 if (h->hashes[i] == 0)
1180 else if (h->hashes[i] == 1)
1188 check_data (GHashTable *h)
1192 for (i = 0; i < h->size; i++)
1194 if (h->hashes[i] < 2)
1196 g_assert (h->keys[i] == NULL);
1197 g_assert (h->values[i] == NULL);
1201 g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1207 check_consistency (GHashTable *h)
1213 count_keys (h, &unused, &occupied, &tombstones);
1215 g_assert_cmpint (occupied, ==, h->nnodes);
1216 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1217 g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1223 check_counts (GHashTable *h, gint occupied, gint tombstones)
1225 g_assert_cmpint (occupied, ==, h->nnodes);
1226 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1230 trivial_key_destroy (gpointer key)
1235 test_internal_consistency (void)
1239 h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1241 check_counts (h, 0, 0);
1242 check_consistency (h);
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");
1251 check_counts (h, 6, 0);
1252 check_consistency (h);
1254 g_hash_table_remove (h, "a");
1255 check_counts (h, 5, 1);
1256 check_consistency (h);
1258 g_hash_table_remove (h, "b");
1259 check_counts (h, 4, 2);
1260 check_consistency (h);
1262 g_hash_table_insert (h, "c", "c");
1263 check_counts (h, 4, 2);
1264 check_consistency (h);
1266 g_hash_table_insert (h, "a", "A");
1267 check_counts (h, 5, 1);
1268 check_consistency (h);
1270 g_hash_table_remove_all (h);
1271 check_counts (h, 0, 0);
1272 check_consistency (h);
1274 g_hash_table_unref (h);
1278 my_key_free (gpointer v)
1281 g_assert (s[0] != 'x');
1287 my_value_free (gpointer v)
1290 g_assert (s[0] != 'y');
1296 test_iter_replace (void)
1299 GHashTableIter iter;
1303 g_test_bug ("662544");
1305 h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
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"));
1311 g_hash_table_iter_init (&iter, h);
1313 while (g_hash_table_iter_next (&iter, &k, &v))
1316 g_assert (g_ascii_islower (s[0]));
1317 g_hash_table_iter_replace (&iter, g_strdup (k));
1320 g_hash_table_unref (h);
1324 replace_first_character (gchar *string)
1330 test_set_insert_corruption (void)
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;
1338 gpointer key, value;
1340 g_test_bug ("692815");
1342 g_hash_table_insert (hash_table, a, a);
1343 g_assert (g_hash_table_contains (hash_table, "foo"));
1345 g_hash_table_insert (hash_table, b, b);
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();
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'.
1355 g_assert (key != b);
1356 g_assert (key == a);
1358 g_assert_cmpstr (b, ==, "boo");
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
1364 g_assert (value == b);
1366 /* even though the hash has now been de-set-ified: */
1367 g_assert (g_hash_table_contains (hash_table, "foo"));
1369 g_hash_table_unref (hash_table);
1373 test_set_to_strv (void)
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");
1393 g_assert_cmpstr (strv[0], ==, "xyz");
1394 g_assert_cmpstr (strv[1], ==, "abc");
1400 main (int argc, char *argv[])
1402 g_test_init (&argc, &argv, NULL);
1404 g_test_bug_base ("http://bugzilla.gnome.org/");
1406 g_test_add_func ("/hash/misc", test_hash_misc);
1407 g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1408 g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1409 g_test_add_func ("/hash/direct", direct_hash_test);
1410 g_test_add_func ("/hash/direct2", direct_hash_test2);
1411 g_test_add_func ("/hash/int", int_hash_test);
1412 g_test_add_func ("/hash/int64", int64_hash_test);
1413 g_test_add_func ("/hash/double", double_hash_test);
1414 g_test_add_func ("/hash/string", string_hash_test);
1415 g_test_add_func ("/hash/set", set_hash_test);
1416 g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1417 g_test_add_func ("/hash/ref", test_hash_ref);
1418 g_test_add_func ("/hash/remove-all", test_remove_all);
1419 g_test_add_func ("/hash/find", test_find);
1420 g_test_add_func ("/hash/foreach", test_foreach);
1421 g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1423 /* tests for individual bugs */
1424 g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1425 g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1426 g_test_add_func ("/hash/consistency", test_internal_consistency);
1427 g_test_add_func ("/hash/iter-replace", test_iter_replace);
1428 g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1429 g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1431 return g_test_run ();