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 ();