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

source code of gtk/subprojects/glib/glib/tests/hash.c