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);
360 direct_hash_test (void)
365 h = g_hash_table_new (NULL, NULL);
366 g_assert (h != NULL);
367 for (i = 1; i <= 20; i++)
368 g_hash_table_insert (h, GINT_TO_POINTER (i),
369 GINT_TO_POINTER (i + 42));
371 g_assert (g_hash_table_size (h) == 20);
373 for (i = 1; i <= 20; i++)
375 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
378 g_assert ((rc - 42) == i);
381 g_hash_table_destroy (h);
392 h = g_hash_table_new (g_int_hash, g_int_equal);
393 g_assert (h != NULL);
394 for (i = 0; i < 20; i++)
397 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
400 g_assert (g_hash_table_size (h) == 20);
402 for (i = 0; i < 20; i++)
405 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
407 g_assert_cmpint (rc, ==, i + 42);
410 g_hash_table_destroy (h);
414 int64_hash_test (void)
421 h = g_hash_table_new (g_int64_hash, g_int64_equal);
422 g_assert (h != NULL);
423 for (i = 0; i < 20; i++)
426 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
429 g_assert (g_hash_table_size (h) == 20);
431 for (i = 0; i < 20; i++)
434 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
436 g_assert_cmpint (rc, ==, i + 42);
439 g_hash_table_destroy (h);
443 double_hash_test (void)
450 h = g_hash_table_new (g_double_hash, g_double_equal);
451 g_assert (h != NULL);
452 for (i = 0; i < 20; i++)
454 values[i] = i + 42.5;
455 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
458 g_assert (g_hash_table_size (h) == 20);
460 for (i = 0; i < 20; i++)
463 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
465 g_assert_cmpint (rc, ==, i + 42);
468 g_hash_table_destroy (h);
472 string_free (gpointer data)
476 g_string_free (s, TRUE);
480 string_hash_test (void)
486 h = g_hash_table_new_full ((GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, string_free, NULL);
487 g_assert (h != NULL);
488 for (i = 0; i < 20; i++)
490 s = g_string_new ("");
491 g_string_append_printf (s, "%d", i + 42);
492 g_string_append_c (s, '.');
493 g_string_prepend_unichar (s, 0x2301);
494 g_hash_table_insert (h, s, GINT_TO_POINTER (i + 42));
497 g_assert (g_hash_table_size (h) == 20);
499 s = g_string_new ("");
500 for (i = 0; i < 20; i++)
502 g_string_assign (s, "");
503 g_string_append_printf (s, "%d", i + 42);
504 g_string_append_c (s, '.');
505 g_string_prepend_unichar (s, 0x2301);
506 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, s));
508 g_assert_cmpint (rc, ==, i + 42);
511 g_string_free (s, TRUE);
512 g_hash_table_destroy (h);
516 set_check (gpointer key,
522 g_assert_not_reached ();
524 g_assert_cmpint (atoi (key) % 7, ==, 2);
532 GHashTable *hash_table =
533 g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
536 for (i = 2; i < 5000; i += 7)
538 char *s = g_strdup_printf ("%d", i);
539 g_assert (g_hash_table_add (hash_table, s));
542 g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
545 g_hash_table_foreach (hash_table, set_check, &i);
546 g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
548 g_assert (g_hash_table_contains (hash_table, "2"));
549 g_assert (g_hash_table_contains (hash_table, "9"));
550 g_assert (!g_hash_table_contains (hash_table, "a"));
552 /* this will cause the hash table to loose set nature */
553 g_assert (g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
554 g_assert (!g_hash_table_insert (hash_table, g_strdup ("a"), "b"));
556 g_assert (g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
557 g_assert (!g_hash_table_replace (hash_table, g_strdup ("c"), "d"));
559 g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
560 g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
562 g_hash_table_destroy (hash_table);
567 test_hash_misc (void)
569 GHashTable *hash_table;
573 GList *keys, *values;
574 gint keys_len, values_len;
576 gpointer ikey, ivalue;
577 int result_array[10000];
580 hash_table = g_hash_table_new (my_hash, my_hash_equal);
581 fill_hash_table_and_array (hash_table);
582 pvalue = g_hash_table_find (hash_table, find_first, &value);
583 if (!pvalue || *pvalue != value)
584 g_assert_not_reached();
586 keys = g_hash_table_get_keys (hash_table);
588 g_assert_not_reached ();
590 values = g_hash_table_get_values (hash_table);
592 g_assert_not_reached ();
594 keys_len = g_list_length (keys);
595 values_len = g_list_length (values);
596 if (values_len != keys_len && keys_len != g_hash_table_size (hash_table))
597 g_assert_not_reached ();
600 g_list_free (values);
602 init_result_array (result_array);
603 g_hash_table_iter_init (&iter, hash_table);
604 for (i = 0; i < 10000; i++)
606 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
608 handle_pair (ikey, ivalue, result_array);
611 g_hash_table_iter_remove (&iter);
613 g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue));
614 g_assert (g_hash_table_size (hash_table) == 5000);
615 verify_result_array (result_array);
617 fill_hash_table_and_array (hash_table);
619 init_result_array (result_array);
620 g_hash_table_foreach (hash_table, my_hash_callback, result_array);
621 verify_result_array (result_array);
623 for (i = 0; i < 10000; i++)
624 g_hash_table_remove (hash_table, &array[i]);
626 fill_hash_table_and_array (hash_table);
628 if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
629 g_hash_table_size (hash_table) != 5000)
630 g_assert_not_reached();
632 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
633 g_hash_table_destroy (hash_table);
635 hash_table = g_hash_table_new (my_hash, my_hash_equal);
636 fill_hash_table_and_array (hash_table);
640 g_hash_table_iter_init (&iter, hash_table);
641 for (i = 0; i < 10000; i++)
643 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
644 g_hash_table_iter_replace (&iter, &n_array[0]);
647 g_hash_table_iter_init (&iter, hash_table);
648 for (i = 0; i < 10000; i++)
650 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
652 g_assert (ivalue == &n_array[0]);
655 g_hash_table_destroy (hash_table);
658 static gint destroy_counter;
661 value_destroy (gpointer value)
672 gboolean abc_seen = FALSE;
673 gboolean cde_seen = FALSE;
674 gboolean xyz_seen = FALSE;
676 h = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, value_destroy);
677 g_hash_table_insert (h, "abc", "ABC");
678 g_hash_table_insert (h, "cde", "CDE");
679 g_hash_table_insert (h, "xyz", "XYZ");
681 g_assert_cmpint (g_hash_table_size (h), == , 3);
683 g_hash_table_iter_init (&iter, h);
685 while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
687 if (strcmp (key, "abc") == 0)
689 g_assert_cmpstr (value, ==, "ABC");
691 g_hash_table_iter_steal (&iter);
693 else if (strcmp (key, "cde") == 0)
695 g_assert_cmpstr (value, ==, "CDE");
698 else if (strcmp (key, "xyz") == 0)
700 g_assert_cmpstr (value, ==, "XYZ");
704 g_assert_cmpint (destroy_counter, ==, 0);
706 g_assert (g_hash_table_iter_get_hash_table (&iter) == h);
707 g_assert (abc_seen && cde_seen && xyz_seen);
708 g_assert_cmpint (g_hash_table_size (h), == , 2);
710 g_hash_table_ref (h);
711 g_hash_table_destroy (h);
712 g_assert_cmpint (g_hash_table_size (h), == , 0);
713 g_assert_cmpint (destroy_counter, ==, 2);
714 g_hash_table_insert (h, "uvw", "UVW");
715 g_hash_table_unref (h);
716 g_assert_cmpint (destroy_counter, ==, 3);
720 null_safe_str_hash (gconstpointer key)
725 return g_str_hash (key);
729 null_safe_str_equal (gconstpointer a, gconstpointer b)
731 return g_strcmp0 (a, b) == 0;
735 test_lookup_null_key (void)
742 g_test_bug ("642944");
744 h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
745 g_hash_table_insert (h, "abc", "ABC");
747 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
750 g_hash_table_insert (h, NULL, "NULL");
752 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
754 g_assert_cmpstr (value, ==, "NULL");
756 g_hash_table_unref (h);
759 static gint destroy_key_counter;
762 key_destroy (gpointer key)
764 destroy_key_counter++;
768 test_remove_all (void)
773 h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
774 g_hash_table_insert (h, "abc", "ABC");
775 g_hash_table_insert (h, "cde", "CDE");
776 g_hash_table_insert (h, "xyz", "XYZ");
779 destroy_key_counter = 0;
781 g_hash_table_steal_all (h);
782 g_assert_cmpint (destroy_counter, ==, 0);
783 g_assert_cmpint (destroy_key_counter, ==, 0);
785 g_hash_table_insert (h, "abc", "ABC");
786 g_hash_table_insert (h, "cde", "CDE");
787 g_hash_table_insert (h, "xyz", "XYZ");
789 res = g_hash_table_steal (h, "nosuchkey");
791 g_assert_cmpint (destroy_counter, ==, 0);
792 g_assert_cmpint (destroy_key_counter, ==, 0);
794 res = g_hash_table_steal (h, "xyz");
796 g_assert_cmpint (destroy_counter, ==, 0);
797 g_assert_cmpint (destroy_key_counter, ==, 0);
799 g_hash_table_remove_all (h);
800 g_assert_cmpint (destroy_counter, ==, 2);
801 g_assert_cmpint (destroy_key_counter, ==, 2);
803 g_hash_table_unref (h);
812 hash_func (gconstpointer key)
814 const RefCountedKey *rkey = key;
816 return g_str_hash (rkey->key);
820 eq_func (gconstpointer a, gconstpointer b)
822 const RefCountedKey *aa = a;
823 const RefCountedKey *bb = b;
825 return g_strcmp0 (aa->key, bb->key) == 0;
829 key_unref (gpointer data)
831 RefCountedKey *key = data;
833 g_assert (key->ref_count > 0);
837 if (key->ref_count == 0)
841 static RefCountedKey *
842 key_ref (RefCountedKey *key)
849 static RefCountedKey *
850 key_new (const gchar *key)
854 rkey = g_new (RefCountedKey, 1);
863 set_ref_hash_test (void)
869 h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
871 key1 = key_new ("a");
872 key2 = key_new ("a");
874 g_assert_cmpint (key1->ref_count, ==, 1);
875 g_assert_cmpint (key2->ref_count, ==, 1);
877 g_hash_table_insert (h, key_ref (key1), key_ref (key1));
879 g_assert_cmpint (key1->ref_count, ==, 3);
880 g_assert_cmpint (key2->ref_count, ==, 1);
882 g_hash_table_replace (h, key_ref (key2), key_ref (key2));
884 g_assert_cmpint (key1->ref_count, ==, 1);
885 g_assert_cmpint (key2->ref_count, ==, 3);
887 g_hash_table_remove (h, key1);
889 g_assert_cmpint (key1->ref_count, ==, 1);
890 g_assert_cmpint (key2->ref_count, ==, 1);
892 g_hash_table_unref (h);
905 GPtrArray *fake_free_data;
908 fake_free (gpointer dead)
912 for (i = 0; i < fake_free_data->len; i++)
914 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
916 if (ffd->string == (gchar *) dead)
918 g_assert (!ffd->freed);
924 g_assert_not_reached ();
928 value_destroy_insert (gpointer value)
930 g_hash_table_remove_all (h);
934 test_destroy_modify (void)
939 g_test_bug ("650459");
941 fake_free_data = g_ptr_array_new ();
943 h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
945 ffd = g_new0 (FakeFreeData, 1);
946 ffd->string = g_strdup ("a");
947 g_ptr_array_add (fake_free_data, ffd);
948 g_hash_table_insert (h, ffd->string, "b");
950 ffd = g_new0 (FakeFreeData, 1);
951 ffd->string = g_strdup ("c");
952 g_ptr_array_add (fake_free_data, ffd);
953 g_hash_table_insert (h, ffd->string, "d");
955 ffd = g_new0 (FakeFreeData, 1);
956 ffd->string = g_strdup ("e");
957 g_ptr_array_add (fake_free_data, ffd);
958 g_hash_table_insert (h, ffd->string, "f");
960 ffd = g_new0 (FakeFreeData, 1);
961 ffd->string = g_strdup ("g");
962 g_ptr_array_add (fake_free_data, ffd);
963 g_hash_table_insert (h, ffd->string, "h");
965 ffd = g_new0 (FakeFreeData, 1);
966 ffd->string = g_strdup ("h");
967 g_ptr_array_add (fake_free_data, ffd);
968 g_hash_table_insert (h, ffd->string, "k");
970 ffd = g_new0 (FakeFreeData, 1);
971 ffd->string = g_strdup ("a");
972 g_ptr_array_add (fake_free_data, ffd);
973 g_hash_table_insert (h, ffd->string, "c");
975 g_hash_table_remove (h, "c");
977 /* that removed everything... */
978 for (i = 0; i < fake_free_data->len; i++)
980 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
982 g_assert (ffd->freed);
983 g_free (ffd->string);
987 g_ptr_array_unref (fake_free_data);
989 /* ... so this is a no-op */
990 g_hash_table_remove (h, "e");
992 g_hash_table_unref (h);
996 find_str (gpointer key, gpointer value, gpointer data)
998 return g_str_equal (key, data);
1007 hash = g_hash_table_new (g_str_hash, g_str_equal);
1009 g_hash_table_insert (hash, "a", "A");
1010 g_hash_table_insert (hash, "b", "B");
1011 g_hash_table_insert (hash, "c", "C");
1012 g_hash_table_insert (hash, "d", "D");
1013 g_hash_table_insert (hash, "e", "E");
1014 g_hash_table_insert (hash, "f", "F");
1016 value = g_hash_table_find (hash, find_str, "a");
1017 g_assert_cmpstr (value, ==, "A");
1019 value = g_hash_table_find (hash, find_str, "b");
1020 g_assert_cmpstr (value, ==, "B");
1022 value = g_hash_table_find (hash, find_str, "c");
1023 g_assert_cmpstr (value, ==, "C");
1025 value = g_hash_table_find (hash, find_str, "d");
1026 g_assert_cmpstr (value, ==, "D");
1028 value = g_hash_table_find (hash, find_str, "e");
1029 g_assert_cmpstr (value, ==, "E");
1031 value = g_hash_table_find (hash, find_str, "f");
1032 g_assert_cmpstr (value, ==, "F");
1034 value = g_hash_table_find (hash, find_str, "0");
1035 g_assert (value == NULL);
1037 g_hash_table_unref (hash);
1040 gboolean seen_key[6];
1043 foreach_func (gpointer key, gpointer value, gpointer data)
1045 seen_key[((char*)key)[0] - 'a'] = TRUE;
1054 hash = g_hash_table_new (g_str_hash, g_str_equal);
1056 g_hash_table_insert (hash, "a", "A");
1057 g_hash_table_insert (hash, "b", "B");
1058 g_hash_table_insert (hash, "c", "C");
1059 g_hash_table_insert (hash, "d", "D");
1060 g_hash_table_insert (hash, "e", "E");
1061 g_hash_table_insert (hash, "f", "F");
1063 for (i = 0; i < 6; i++)
1064 seen_key[i] = FALSE;
1066 g_hash_table_foreach (hash, foreach_func, NULL);
1068 for (i = 0; i < 6; i++)
1069 g_assert (seen_key[i]);
1071 g_hash_table_unref (hash);
1075 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1077 GHashTable *hash2 = data;
1079 if (strstr ("ace", (gchar*)key))
1081 g_hash_table_insert (hash2, key, value);
1090 test_foreach_steal (void)
1095 hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1096 hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1098 g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1099 g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1100 g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1101 g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1102 g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1103 g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1105 g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1107 g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1108 g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1110 g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1111 g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1112 g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1113 g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1114 g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1115 g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1117 g_hash_table_unref (hash);
1118 g_hash_table_unref (hash2);
1127 gint noccupied; /* nnodes + tombstones */
1133 GHashFunc hash_func;
1134 GEqualFunc key_equal_func;
1135 volatile gint ref_count;
1137 #ifndef G_DISABLE_ASSERT
1140 GDestroyNotify key_destroy_func;
1141 GDestroyNotify value_destroy_func;
1145 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1152 for (i = 0; i < h->size; i++)
1154 if (h->hashes[i] == 0)
1156 else if (h->hashes[i] == 1)
1164 check_data (GHashTable *h)
1168 for (i = 0; i < h->size; i++)
1170 if (h->hashes[i] < 2)
1172 g_assert (h->keys[i] == NULL);
1173 g_assert (h->values[i] == NULL);
1177 g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1183 check_consistency (GHashTable *h)
1189 count_keys (h, &unused, &occupied, &tombstones);
1191 g_assert_cmpint (occupied, ==, h->nnodes);
1192 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1193 g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1199 check_counts (GHashTable *h, gint occupied, gint tombstones)
1201 g_assert_cmpint (occupied, ==, h->nnodes);
1202 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1206 trivial_key_destroy (gpointer key)
1211 test_internal_consistency (void)
1215 h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1217 check_counts (h, 0, 0);
1218 check_consistency (h);
1220 g_hash_table_insert (h, "a", "A");
1221 g_hash_table_insert (h, "b", "B");
1222 g_hash_table_insert (h, "c", "C");
1223 g_hash_table_insert (h, "d", "D");
1224 g_hash_table_insert (h, "e", "E");
1225 g_hash_table_insert (h, "f", "F");
1227 check_counts (h, 6, 0);
1228 check_consistency (h);
1230 g_hash_table_remove (h, "a");
1231 check_counts (h, 5, 1);
1232 check_consistency (h);
1234 g_hash_table_remove (h, "b");
1235 check_counts (h, 4, 2);
1236 check_consistency (h);
1238 g_hash_table_insert (h, "c", "c");
1239 check_counts (h, 4, 2);
1240 check_consistency (h);
1242 g_hash_table_insert (h, "a", "A");
1243 check_counts (h, 5, 1);
1244 check_consistency (h);
1246 g_hash_table_remove_all (h);
1247 check_counts (h, 0, 0);
1248 check_consistency (h);
1250 g_hash_table_unref (h);
1254 my_key_free (gpointer v)
1257 g_assert (s[0] != 'x');
1263 my_value_free (gpointer v)
1266 g_assert (s[0] != 'y');
1272 test_iter_replace (void)
1275 GHashTableIter iter;
1279 g_test_bug ("662544");
1281 h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1283 g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1284 g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1285 g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1287 g_hash_table_iter_init (&iter, h);
1289 while (g_hash_table_iter_next (&iter, &k, &v))
1292 g_assert (g_ascii_islower (s[0]));
1293 g_hash_table_iter_replace (&iter, g_strdup (k));
1296 g_hash_table_unref (h);
1300 replace_first_character (gchar *string)
1306 test_set_insert_corruption (void)
1308 GHashTable *hash_table =
1309 g_hash_table_new_full (g_str_hash, g_str_equal,
1310 (GDestroyNotify) replace_first_character, NULL);
1311 GHashTableIter iter;
1314 gpointer key, value;
1316 g_test_bug ("692815");
1318 g_hash_table_insert (hash_table, a, a);
1319 g_assert (g_hash_table_contains (hash_table, "foo"));
1321 g_hash_table_insert (hash_table, b, b);
1323 g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1324 g_hash_table_iter_init (&iter, hash_table);
1325 if (!g_hash_table_iter_next (&iter, &key, &value))
1326 g_assert_not_reached();
1328 /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1329 * and the sole key in 'hash_table' should be 'a'.
1331 g_assert (key != b);
1332 g_assert (key == a);
1334 g_assert_cmpstr (b, ==, "boo");
1336 /* g_hash_table_insert() also says that the value should now be 'b',
1337 * which is probably not what the caller intended but is precisely what they
1340 g_assert (value == b);
1342 /* even though the hash has now been de-set-ified: */
1343 g_assert (g_hash_table_contains (hash_table, "foo"));
1345 g_hash_table_unref (hash_table);
1349 test_set_to_strv (void)
1355 set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1356 g_hash_table_add (set, g_strdup ("xyz"));
1357 g_hash_table_add (set, g_strdup ("xyz"));
1358 g_hash_table_add (set, g_strdup ("abc"));
1359 strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1360 g_hash_table_steal_all (set);
1361 g_hash_table_unref (set);
1362 g_assert_cmpint (n, ==, 2);
1363 n = g_strv_length (strv);
1364 g_assert_cmpint (n, ==, 2);
1365 if (g_str_equal (strv[0], "abc"))
1366 g_assert_cmpstr (strv[1], ==, "xyz");
1369 g_assert_cmpstr (strv[0], ==, "xyz");
1370 g_assert_cmpstr (strv[1], ==, "abc");
1376 main (int argc, char *argv[])
1378 g_test_init (&argc, &argv, NULL);
1380 g_test_bug_base ("http://bugzilla.gnome.org/");
1382 g_test_add_func ("/hash/misc", test_hash_misc);
1383 g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1384 g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1385 g_test_add_func ("/hash/direct", direct_hash_test);
1386 g_test_add_func ("/hash/int", int_hash_test);
1387 g_test_add_func ("/hash/int64", int64_hash_test);
1388 g_test_add_func ("/hash/double", double_hash_test);
1389 g_test_add_func ("/hash/string", string_hash_test);
1390 g_test_add_func ("/hash/set", set_hash_test);
1391 g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1392 g_test_add_func ("/hash/ref", test_hash_ref);
1393 g_test_add_func ("/hash/remove-all", test_remove_all);
1394 g_test_add_func ("/hash/find", test_find);
1395 g_test_add_func ("/hash/foreach", test_foreach);
1396 g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1398 /* tests for individual bugs */
1399 g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1400 g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1401 g_test_add_func ("/hash/consistency", test_internal_consistency);
1402 g_test_add_func ("/hash/iter-replace", test_iter_replace);
1403 g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1404 g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1406 return g_test_run ();