nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 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 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 #ifdef HAVE_CONFIG_H
30 # include <config.h>
31 #endif
32  
33 #include <stdio.h>
34 #include <string.h>
35 #include <stdlib.h>
36  
37 #include <glib.h>
38  
39  
40  
41 int array[10000];
42  
43 static void
44 fill_hash_table_and_array (GHashTable *hash_table)
45 {
46 int i;
47  
48 for (i = 0; i < 10000; i++)
49 {
50 array[i] = i;
51 g_hash_table_insert (hash_table, &array[i], &array[i]);
52 }
53 }
54  
55 static void
56 init_result_array (int result_array[10000])
57 {
58 int i;
59  
60 for (i = 0; i < 10000; i++)
61 result_array[i] = -1;
62 }
63  
64 static void
65 verify_result_array (int array[10000])
66 {
67 int i;
68  
69 for (i = 0; i < 10000; i++)
70 g_assert (array[i] == i);
71 }
72  
73 static void
74 handle_pair (gpointer key, gpointer value, int result_array[10000])
75 {
76 int n;
77  
78 g_assert (key == value);
79  
80 n = *((int *) value);
81  
82 g_assert (n >= 0 && n < 10000);
83 g_assert (result_array[n] == -1);
84  
85 result_array[n] = n;
86 }
87  
88 static gboolean
89 my_hash_callback_remove (gpointer key,
90 gpointer value,
91 gpointer user_data)
92 {
93 int *d = value;
94  
95 if ((*d) % 2)
96 return TRUE;
97  
98 return FALSE;
99 }
100  
101 static void
102 my_hash_callback_remove_test (gpointer key,
103 gpointer value,
104 gpointer user_data)
105 {
106 int *d = value;
107  
108 if ((*d) % 2)
109 g_assert_not_reached ();
110 }
111  
112 static void
113 my_hash_callback (gpointer key,
114 gpointer value,
115 gpointer user_data)
116 {
117 handle_pair (key, value, user_data);
118 }
119  
120 static guint
121 my_hash (gconstpointer key)
122 {
123 return (guint) *((const gint*) key);
124 }
125  
126 static gboolean
127 my_hash_equal (gconstpointer a,
128 gconstpointer b)
129 {
130 return *((const gint*) a) == *((const gint*) b);
131 }
132  
133  
134  
135 /*
136 * This is a simplified version of the pathalias hashing function.
137 * Thanks to Steve Belovin and Peter Honeyman
138 *
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.
142 *
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
150 * x^31 + x^3 + x^0
151 *
152 * We reverse the bits to get:
153 * 111101010000000000000000000000001 but drop the last 1
154 * f 5 0 0 0 0 0 0
155 * 010010000000000000000000000000001 ditto, for 31-bit crc
156 * 4 8 0 0 0 0 0 0
157 */
158  
159 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
160  
161 static guint CrcTable[128];
162  
163 /*
164 - crcinit - initialize tables for hash function
165 */
166 static void crcinit(void)
167 {
168 int i, j;
169 guint sum;
170  
171 for (i = 0; i < 128; ++i)
172 {
173 sum = 0L;
174 for (j = 7 - 1; j >= 0; --j)
175 if (i & (1 << j))
176 sum ^= POLY >> j;
177 CrcTable[i] = sum;
178 }
179 }
180  
181 /*
182 - hash - Honeyman's nice hashing function
183 */
184 static guint
185 honeyman_hash (gconstpointer key)
186 {
187 const gchar *name = (const gchar *) key;
188 gint size;
189 guint sum = 0;
190  
191 g_assert (name != NULL);
192 g_assert (*name != 0);
193  
194 size = strlen (name);
195  
196 while (size--)
197 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
198  
199 return sum;
200 }
201  
202  
203 static gboolean
204 second_hash_cmp (gconstpointer a, gconstpointer b)
205 {
206 return strcmp (a, b) == 0;
207 }
208  
209  
210  
211 static guint
212 one_hash (gconstpointer key)
213 {
214 return 1;
215 }
216  
217  
218 static void
219 not_even_foreach (gpointer key,
220 gpointer value,
221 gpointer user_data)
222 {
223 const char *_key = (const char *) key;
224 const char *_value = (const char *) value;
225 int i;
226 char val [20];
227  
228 g_assert (_key != NULL);
229 g_assert (*_key != 0);
230 g_assert (_value != NULL);
231 g_assert (*_value != 0);
232  
233 i = atoi (_key);
234  
235 sprintf (val, "%d value", i);
236 g_assert (strcmp (_value, val) == 0);
237  
238 g_assert ((i % 2) != 0);
239 g_assert (i != 3);
240 }
241  
242 static gboolean
243 remove_even_foreach (gpointer key,
244 gpointer value,
245 gpointer user_data)
246 {
247 const char *_key = (const char *) key;
248 const char *_value = (const char *) value;
249 int i;
250 char val [20];
251  
252 g_assert (_key != NULL);
253 g_assert (*_key != 0);
254 g_assert (_value != NULL);
255 g_assert (*_value != 0);
256  
257 i = atoi (_key);
258  
259 sprintf (val, "%d value", i);
260 g_assert (strcmp (_value, val) == 0);
261  
262 return ((i % 2) == 0) ? TRUE : FALSE;
263 }
264  
265  
266  
267  
268 static void
269 second_hash_test (gconstpointer d)
270 {
271 gboolean simple_hash = GPOINTER_TO_INT (d);
272  
273 int i;
274 char key[20] = "", val[20]="", *v, *orig_key, *orig_val;
275 GHashTable *h;
276 gboolean found;
277  
278 crcinit ();
279  
280 h = g_hash_table_new_full (simple_hash ? one_hash : honeyman_hash,
281 second_hash_cmp,
282 g_free, g_free);
283 g_assert (h != NULL);
284 for (i = 0; i < 20; i++)
285 {
286 sprintf (key, "%d", i);
287 g_assert (atoi (key) == i);
288  
289 sprintf (val, "%d value", i);
290 g_assert (atoi (val) == i);
291  
292 g_hash_table_insert (h, g_strdup (key), g_strdup (val));
293 }
294  
295 g_assert (g_hash_table_size (h) == 20);
296  
297 for (i = 0; i < 20; i++)
298 {
299 sprintf (key, "%d", i);
300 g_assert (atoi(key) == i);
301  
302 v = (char *) g_hash_table_lookup (h, key);
303  
304 g_assert (v != NULL);
305 g_assert (*v != 0);
306 g_assert (atoi (v) == i);
307 }
308  
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);
315  
316 for (i = 0; i < 20; i++)
317 {
318 sprintf (key, "%d", i);
319 g_assert (atoi(key) == i);
320  
321 sprintf (val, "%d value", i);
322 g_assert (atoi (val) == i);
323  
324 orig_key = orig_val = NULL;
325 found = g_hash_table_lookup_extended (h, key,
326 (gpointer)&orig_key,
327 (gpointer)&orig_val);
328 if ((i % 2) == 0 || i == 3)
329 {
330 g_assert (!found);
331 continue;
332 }
333  
334 g_assert (found);
335  
336 g_assert (orig_key != NULL);
337 g_assert (strcmp (key, orig_key) == 0);
338  
339 g_assert (orig_val != NULL);
340 g_assert (strcmp (val, orig_val) == 0);
341 }
342  
343 g_hash_table_destroy (h);
344 }
345  
346 static gboolean
347 find_first (gpointer key,
348 gpointer value,
349 gpointer user_data)
350 {
351 gint *v = value;
352 gint *test = user_data;
353 return (*v == *test);
354 }
355  
356 static void
357 direct_hash_test (void)
358 {
359 gint i, rc;
360 GHashTable *h;
361  
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));
367  
368 g_assert (g_hash_table_size (h) == 20);
369  
370 for (i = 1; i <= 20; i++)
371 {
372 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
373  
374 g_assert (rc != 0);
375 g_assert ((rc - 42) == i);
376 }
377  
378 g_hash_table_destroy (h);
379 }
380  
381 static void
382 direct_hash_test2 (void)
383 {
384 gint i, rc;
385 GHashTable *h;
386  
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));
392  
393 g_assert (g_hash_table_size (h) == 20);
394  
395 for (i = 1; i <= 20; i++)
396 {
397 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, GINT_TO_POINTER (i)));
398  
399 g_assert (rc != 0);
400 g_assert ((rc - 42) == i);
401 }
402  
403 g_hash_table_destroy (h);
404 }
405  
406 static void
407 int_hash_test (void)
408 {
409 gint i, rc;
410 GHashTable *h;
411 gint values[20];
412 gint key;
413  
414 h = g_hash_table_new (g_int_hash, g_int_equal);
415 g_assert (h != NULL);
416 for (i = 0; i < 20; i++)
417 {
418 values[i] = i + 42;
419 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
420 }
421  
422 g_assert (g_hash_table_size (h) == 20);
423  
424 for (i = 0; i < 20; i++)
425 {
426 key = i + 42;
427 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
428  
429 g_assert_cmpint (rc, ==, i + 42);
430 }
431  
432 g_hash_table_destroy (h);
433 }
434  
435 static void
436 int64_hash_test (void)
437 {
438 gint i, rc;
439 GHashTable *h;
440 gint64 values[20];
441 gint64 key;
442  
443 h = g_hash_table_new (g_int64_hash, g_int64_equal);
444 g_assert (h != NULL);
445 for (i = 0; i < 20; i++)
446 {
447 values[i] = i + 42;
448 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
449 }
450  
451 g_assert (g_hash_table_size (h) == 20);
452  
453 for (i = 0; i < 20; i++)
454 {
455 key = i + 42;
456 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
457  
458 g_assert_cmpint (rc, ==, i + 42);
459 }
460  
461 g_hash_table_destroy (h);
462 }
463  
464 static void
465 double_hash_test (void)
466 {
467 gint i, rc;
468 GHashTable *h;
469 gdouble values[20];
470 gdouble key;
471  
472 h = g_hash_table_new (g_double_hash, g_double_equal);
473 g_assert (h != NULL);
474 for (i = 0; i < 20; i++)
475 {
476 values[i] = i + 42.5;
477 g_hash_table_insert (h, &values[i], GINT_TO_POINTER (i + 42));
478 }
479  
480 g_assert (g_hash_table_size (h) == 20);
481  
482 for (i = 0; i < 20; i++)
483 {
484 key = i + 42.5;
485 rc = GPOINTER_TO_INT (g_hash_table_lookup (h, &key));
486  
487 g_assert_cmpint (rc, ==, i + 42);
488 }
489  
490 g_hash_table_destroy (h);
491 }
492  
493 static void
494 string_free (gpointer data)
495 {
496 GString *s = data;
497  
498 g_string_free (s, TRUE);
499 }
500  
501 static void
502 string_hash_test (void)
503 {
504 gint i, rc;
505 GHashTable *h;
506 GString *s;
507  
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++)
511 {
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));
517 }
518  
519 g_assert (g_hash_table_size (h) == 20);
520  
521 s = g_string_new ("");
522 for (i = 0; i < 20; i++)
523 {
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));
529  
530 g_assert_cmpint (rc, ==, i + 42);
531 }
532  
533 g_string_free (s, TRUE);
534 g_hash_table_destroy (h);
535 }
536  
537 static void
538 set_check (gpointer key,
539 gpointer value,
540 gpointer user_data)
541 {
542 int *pi = user_data;
543 if (key != value)
544 g_assert_not_reached ();
545  
546 g_assert_cmpint (atoi (key) % 7, ==, 2);
547  
548 (*pi)++;
549 }
550  
551 static void
552 set_hash_test (void)
553 {
554 GHashTable *hash_table =
555 g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
556 int i;
557  
558 for (i = 2; i < 5000; i += 7)
559 {
560 char *s = g_strdup_printf ("%d", i);
561 g_assert (g_hash_table_add (hash_table, s));
562 }
563  
564 g_assert (!g_hash_table_add (hash_table, g_strdup_printf ("%d", 2)));
565  
566 i = 0;
567 g_hash_table_foreach (hash_table, set_check, &i);
568 g_assert_cmpint (i, ==, g_hash_table_size (hash_table));
569  
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"));
573  
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"));
577  
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"));
580  
581 g_assert_cmpstr (g_hash_table_lookup (hash_table, "2"), ==, "2");
582 g_assert_cmpstr (g_hash_table_lookup (hash_table, "a"), ==, "b");
583  
584 g_hash_table_destroy (hash_table);
585 }
586  
587  
588 static void
589 test_hash_misc (void)
590 {
591 GHashTable *hash_table;
592 gint i;
593 gint value = 120;
594 gint *pvalue;
595 GList *keys, *values;
596 gint keys_len, values_len;
597 GHashTableIter iter;
598 gpointer ikey, ivalue;
599 int result_array[10000];
600 int n_array[1];
601  
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();
607  
608 keys = g_hash_table_get_keys (hash_table);
609 if (!keys)
610 g_assert_not_reached ();
611  
612 values = g_hash_table_get_values (hash_table);
613 if (!values)
614 g_assert_not_reached ();
615  
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 ();
620  
621 g_list_free (keys);
622 g_list_free (values);
623  
624 init_result_array (result_array);
625 g_hash_table_iter_init (&iter, hash_table);
626 for (i = 0; i < 10000; i++)
627 {
628 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
629  
630 handle_pair (ikey, ivalue, result_array);
631  
632 if (i % 2)
633 g_hash_table_iter_remove (&iter);
634 }
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);
638  
639 fill_hash_table_and_array (hash_table);
640  
641 init_result_array (result_array);
642 g_hash_table_foreach (hash_table, my_hash_callback, result_array);
643 verify_result_array (result_array);
644  
645 for (i = 0; i < 10000; i++)
646 g_hash_table_remove (hash_table, &array[i]);
647  
648 fill_hash_table_and_array (hash_table);
649  
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();
653  
654 g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);
655 g_hash_table_destroy (hash_table);
656  
657 hash_table = g_hash_table_new (my_hash, my_hash_equal);
658 fill_hash_table_and_array (hash_table);
659  
660 n_array[0] = 1;
661  
662 g_hash_table_iter_init (&iter, hash_table);
663 for (i = 0; i < 10000; i++)
664 {
665 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
666 g_hash_table_iter_replace (&iter, &n_array[0]);
667 }
668  
669 g_hash_table_iter_init (&iter, hash_table);
670 for (i = 0; i < 10000; i++)
671 {
672 g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue));
673  
674 g_assert (ivalue == &n_array[0]);
675 }
676  
677 g_hash_table_destroy (hash_table);
678 }
679  
680 static gint destroy_counter;
681  
682 static void
683 value_destroy (gpointer value)
684 {
685 destroy_counter++;
686 }
687  
688 static void
689 test_hash_ref (void)
690 {
691 GHashTable *h;
692 GHashTableIter iter;
693 gchar *key, *value;
694 gboolean abc_seen = FALSE;
695 gboolean cde_seen = FALSE;
696 gboolean xyz_seen = FALSE;
697  
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");
702  
703 g_assert_cmpint (g_hash_table_size (h), == , 3);
704  
705 g_hash_table_iter_init (&iter, h);
706  
707 while (g_hash_table_iter_next (&iter, (gpointer*)&key, (gpointer*)&value))
708 {
709 if (strcmp (key, "abc") == 0)
710 {
711 g_assert_cmpstr (value, ==, "ABC");
712 abc_seen = TRUE;
713 g_hash_table_iter_steal (&iter);
714 }
715 else if (strcmp (key, "cde") == 0)
716 {
717 g_assert_cmpstr (value, ==, "CDE");
718 cde_seen = TRUE;
719 }
720 else if (strcmp (key, "xyz") == 0)
721 {
722 g_assert_cmpstr (value, ==, "XYZ");
723 xyz_seen = TRUE;
724 }
725 }
726 g_assert_cmpint (destroy_counter, ==, 0);
727  
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);
731  
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);
739 }
740  
741 static guint
742 null_safe_str_hash (gconstpointer key)
743 {
744 if (key == NULL)
745 return 0;
746 else
747 return g_str_hash (key);
748 }
749  
750 static gboolean
751 null_safe_str_equal (gconstpointer a, gconstpointer b)
752 {
753 return g_strcmp0 (a, b) == 0;
754 }
755  
756 static void
757 test_lookup_null_key (void)
758 {
759 GHashTable *h;
760 gboolean res;
761 gpointer key;
762 gpointer value;
763  
764 g_test_bug ("642944");
765  
766 h = g_hash_table_new (null_safe_str_hash, null_safe_str_equal);
767 g_hash_table_insert (h, "abc", "ABC");
768  
769 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
770 g_assert (!res);
771  
772 g_hash_table_insert (h, NULL, "NULL");
773  
774 res = g_hash_table_lookup_extended (h, NULL, &key, &value);
775 g_assert (res);
776 g_assert_cmpstr (value, ==, "NULL");
777  
778 g_hash_table_unref (h);
779 }
780  
781 static gint destroy_key_counter;
782  
783 static void
784 key_destroy (gpointer key)
785 {
786 destroy_key_counter++;
787 }
788  
789 static void
790 test_remove_all (void)
791 {
792 GHashTable *h;
793 gboolean res;
794  
795 h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, value_destroy);
796  
797 g_hash_table_insert (h, "abc", "cde");
798 g_hash_table_insert (h, "cde", "xyz");
799 g_hash_table_insert (h, "xyz", "abc");
800  
801 destroy_counter = 0;
802 destroy_key_counter = 0;
803  
804 g_hash_table_steal_all (h);
805 g_assert_cmpint (destroy_counter, ==, 0);
806 g_assert_cmpint (destroy_key_counter, ==, 0);
807  
808 g_hash_table_insert (h, "abc", "ABC");
809 g_hash_table_insert (h, "cde", "CDE");
810 g_hash_table_insert (h, "xyz", "XYZ");
811  
812 res = g_hash_table_steal (h, "nosuchkey");
813 g_assert (!res);
814 g_assert_cmpint (destroy_counter, ==, 0);
815 g_assert_cmpint (destroy_key_counter, ==, 0);
816  
817 res = g_hash_table_steal (h, "xyz");
818 g_assert (res);
819 g_assert_cmpint (destroy_counter, ==, 0);
820 g_assert_cmpint (destroy_key_counter, ==, 0);
821  
822 g_hash_table_remove_all (h);
823 g_assert_cmpint (destroy_counter, ==, 2);
824 g_assert_cmpint (destroy_key_counter, ==, 2);
825  
826 g_hash_table_remove_all (h);
827 g_assert_cmpint (destroy_counter, ==, 2);
828 g_assert_cmpint (destroy_key_counter, ==, 2);
829  
830 g_hash_table_unref (h);
831 }
832  
833 GHashTable *recursive_destruction_table = NULL;
834 static void
835 recursive_value_destroy (gpointer value)
836 {
837 destroy_counter++;
838  
839 if (recursive_destruction_table)
840 g_hash_table_remove (recursive_destruction_table, value);
841 }
842  
843 static void
844 test_recursive_remove_all_subprocess (void)
845 {
846 GHashTable *h;
847  
848 h = g_hash_table_new_full (g_str_hash, g_str_equal, key_destroy, recursive_value_destroy);
849 recursive_destruction_table = h;
850  
851 /* Add more items compared to test_remove_all, as it would not fail otherwise. */
852 g_hash_table_insert (h, "abc", "cde");
853 g_hash_table_insert (h, "cde", "fgh");
854 g_hash_table_insert (h, "fgh", "ijk");
855 g_hash_table_insert (h, "ijk", "lmn");
856 g_hash_table_insert (h, "lmn", "opq");
857 g_hash_table_insert (h, "opq", "rst");
858 g_hash_table_insert (h, "rst", "uvw");
859 g_hash_table_insert (h, "uvw", "xyz");
860 g_hash_table_insert (h, "xyz", "abc");
861  
862 destroy_counter = 0;
863 destroy_key_counter = 0;
864  
865 g_hash_table_remove_all (h);
866 g_assert_cmpint (destroy_counter, ==, 9);
867 g_assert_cmpint (destroy_key_counter, ==, 9);
868  
869 g_hash_table_unref (h);
870 }
871  
872 static void
873 test_recursive_remove_all (void)
874 {
875 g_test_trap_subprocess ("/hash/recursive-remove-all/subprocess", 1000000, 0);
876 g_test_trap_assert_passed ();
877 }
878  
879 typedef struct {
880 gint ref_count;
881 const gchar *key;
882 } RefCountedKey;
883  
884 static guint
885 hash_func (gconstpointer key)
886 {
887 const RefCountedKey *rkey = key;
888  
889 return g_str_hash (rkey->key);
890 }
891  
892 static gboolean
893 eq_func (gconstpointer a, gconstpointer b)
894 {
895 const RefCountedKey *aa = a;
896 const RefCountedKey *bb = b;
897  
898 return g_strcmp0 (aa->key, bb->key) == 0;
899 }
900  
901 static void
902 key_unref (gpointer data)
903 {
904 RefCountedKey *key = data;
905  
906 g_assert (key->ref_count > 0);
907  
908 key->ref_count -= 1;
909  
910 if (key->ref_count == 0)
911 g_free (key);
912 }
913  
914 static RefCountedKey *
915 key_ref (RefCountedKey *key)
916 {
917 key->ref_count += 1;
918  
919 return key;
920 }
921  
922 static RefCountedKey *
923 key_new (const gchar *key)
924 {
925 RefCountedKey *rkey;
926  
927 rkey = g_new (RefCountedKey, 1);
928  
929 rkey->ref_count = 1;
930 rkey->key = key;
931  
932 return rkey;
933 }
934  
935 static void
936 set_ref_hash_test (void)
937 {
938 GHashTable *h;
939 RefCountedKey *key1;
940 RefCountedKey *key2;
941  
942 h = g_hash_table_new_full (hash_func, eq_func, key_unref, key_unref);
943  
944 key1 = key_new ("a");
945 key2 = key_new ("a");
946  
947 g_assert_cmpint (key1->ref_count, ==, 1);
948 g_assert_cmpint (key2->ref_count, ==, 1);
949  
950 g_hash_table_insert (h, key_ref (key1), key_ref (key1));
951  
952 g_assert_cmpint (key1->ref_count, ==, 3);
953 g_assert_cmpint (key2->ref_count, ==, 1);
954  
955 g_hash_table_replace (h, key_ref (key2), key_ref (key2));
956  
957 g_assert_cmpint (key1->ref_count, ==, 1);
958 g_assert_cmpint (key2->ref_count, ==, 3);
959  
960 g_hash_table_remove (h, key1);
961  
962 g_assert_cmpint (key1->ref_count, ==, 1);
963 g_assert_cmpint (key2->ref_count, ==, 1);
964  
965 g_hash_table_unref (h);
966  
967 key_unref (key1);
968 key_unref (key2);
969 }
970  
971 GHashTable *h;
972  
973 typedef struct {
974 gchar *string;
975 gboolean freed;
976 } FakeFreeData;
977  
978 GPtrArray *fake_free_data;
979  
980 static void
981 fake_free (gpointer dead)
982 {
983 guint i;
984  
985 for (i = 0; i < fake_free_data->len; i++)
986 {
987 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
988  
989 if (ffd->string == (gchar *) dead)
990 {
991 g_assert (!ffd->freed);
992 ffd->freed = TRUE;
993 return;
994 }
995 }
996  
997 g_assert_not_reached ();
998 }
999  
1000 static void
1001 value_destroy_insert (gpointer value)
1002 {
1003 g_hash_table_remove_all (h);
1004 }
1005  
1006 static void
1007 test_destroy_modify (void)
1008 {
1009 FakeFreeData *ffd;
1010 guint i;
1011  
1012 g_test_bug ("650459");
1013  
1014 fake_free_data = g_ptr_array_new ();
1015  
1016 h = g_hash_table_new_full (g_str_hash, g_str_equal, fake_free, value_destroy_insert);
1017  
1018 ffd = g_new0 (FakeFreeData, 1);
1019 ffd->string = g_strdup ("a");
1020 g_ptr_array_add (fake_free_data, ffd);
1021 g_hash_table_insert (h, ffd->string, "b");
1022  
1023 ffd = g_new0 (FakeFreeData, 1);
1024 ffd->string = g_strdup ("c");
1025 g_ptr_array_add (fake_free_data, ffd);
1026 g_hash_table_insert (h, ffd->string, "d");
1027  
1028 ffd = g_new0 (FakeFreeData, 1);
1029 ffd->string = g_strdup ("e");
1030 g_ptr_array_add (fake_free_data, ffd);
1031 g_hash_table_insert (h, ffd->string, "f");
1032  
1033 ffd = g_new0 (FakeFreeData, 1);
1034 ffd->string = g_strdup ("g");
1035 g_ptr_array_add (fake_free_data, ffd);
1036 g_hash_table_insert (h, ffd->string, "h");
1037  
1038 ffd = g_new0 (FakeFreeData, 1);
1039 ffd->string = g_strdup ("h");
1040 g_ptr_array_add (fake_free_data, ffd);
1041 g_hash_table_insert (h, ffd->string, "k");
1042  
1043 ffd = g_new0 (FakeFreeData, 1);
1044 ffd->string = g_strdup ("a");
1045 g_ptr_array_add (fake_free_data, ffd);
1046 g_hash_table_insert (h, ffd->string, "c");
1047  
1048 g_hash_table_remove (h, "c");
1049  
1050 /* that removed everything... */
1051 for (i = 0; i < fake_free_data->len; i++)
1052 {
1053 FakeFreeData *ffd = g_ptr_array_index (fake_free_data, i);
1054  
1055 g_assert (ffd->freed);
1056 g_free (ffd->string);
1057 g_free (ffd);
1058 }
1059  
1060 g_ptr_array_unref (fake_free_data);
1061  
1062 /* ... so this is a no-op */
1063 g_hash_table_remove (h, "e");
1064  
1065 g_hash_table_unref (h);
1066 }
1067  
1068 static gboolean
1069 find_str (gpointer key, gpointer value, gpointer data)
1070 {
1071 return g_str_equal (key, data);
1072 }
1073  
1074 static void
1075 test_find (void)
1076 {
1077 GHashTable *hash;
1078 const gchar *value;
1079  
1080 hash = g_hash_table_new (g_str_hash, g_str_equal);
1081  
1082 g_hash_table_insert (hash, "a", "A");
1083 g_hash_table_insert (hash, "b", "B");
1084 g_hash_table_insert (hash, "c", "C");
1085 g_hash_table_insert (hash, "d", "D");
1086 g_hash_table_insert (hash, "e", "E");
1087 g_hash_table_insert (hash, "f", "F");
1088  
1089 value = g_hash_table_find (hash, find_str, "a");
1090 g_assert_cmpstr (value, ==, "A");
1091  
1092 value = g_hash_table_find (hash, find_str, "b");
1093 g_assert_cmpstr (value, ==, "B");
1094  
1095 value = g_hash_table_find (hash, find_str, "c");
1096 g_assert_cmpstr (value, ==, "C");
1097  
1098 value = g_hash_table_find (hash, find_str, "d");
1099 g_assert_cmpstr (value, ==, "D");
1100  
1101 value = g_hash_table_find (hash, find_str, "e");
1102 g_assert_cmpstr (value, ==, "E");
1103  
1104 value = g_hash_table_find (hash, find_str, "f");
1105 g_assert_cmpstr (value, ==, "F");
1106  
1107 value = g_hash_table_find (hash, find_str, "0");
1108 g_assert (value == NULL);
1109  
1110 g_hash_table_unref (hash);
1111 }
1112  
1113 gboolean seen_key[6];
1114  
1115 static void
1116 foreach_func (gpointer key, gpointer value, gpointer data)
1117 {
1118 seen_key[((char*)key)[0] - 'a'] = TRUE;
1119 }
1120  
1121 static void
1122 test_foreach (void)
1123 {
1124 GHashTable *hash;
1125 gint i;
1126  
1127 hash = g_hash_table_new (g_str_hash, g_str_equal);
1128  
1129 g_hash_table_insert (hash, "a", "A");
1130 g_hash_table_insert (hash, "b", "B");
1131 g_hash_table_insert (hash, "c", "C");
1132 g_hash_table_insert (hash, "d", "D");
1133 g_hash_table_insert (hash, "e", "E");
1134 g_hash_table_insert (hash, "f", "F");
1135  
1136 for (i = 0; i < 6; i++)
1137 seen_key[i] = FALSE;
1138  
1139 g_hash_table_foreach (hash, foreach_func, NULL);
1140  
1141 for (i = 0; i < 6; i++)
1142 g_assert (seen_key[i]);
1143  
1144 g_hash_table_unref (hash);
1145 }
1146  
1147 static gboolean
1148 foreach_steal_func (gpointer key, gpointer value, gpointer data)
1149 {
1150 GHashTable *hash2 = data;
1151  
1152 if (strstr ("ace", (gchar*)key))
1153 {
1154 g_hash_table_insert (hash2, key, value);
1155 return TRUE;
1156 }
1157  
1158 return FALSE;
1159 }
1160  
1161  
1162 static void
1163 test_foreach_steal (void)
1164 {
1165 GHashTable *hash;
1166 GHashTable *hash2;
1167  
1168 hash = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1169 hash2 = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
1170  
1171 g_hash_table_insert (hash, g_strdup ("a"), g_strdup ("A"));
1172 g_hash_table_insert (hash, g_strdup ("b"), g_strdup ("B"));
1173 g_hash_table_insert (hash, g_strdup ("c"), g_strdup ("C"));
1174 g_hash_table_insert (hash, g_strdup ("d"), g_strdup ("D"));
1175 g_hash_table_insert (hash, g_strdup ("e"), g_strdup ("E"));
1176 g_hash_table_insert (hash, g_strdup ("f"), g_strdup ("F"));
1177  
1178 g_hash_table_foreach_steal (hash, foreach_steal_func, hash2);
1179  
1180 g_assert_cmpint (g_hash_table_size (hash), ==, 3);
1181 g_assert_cmpint (g_hash_table_size (hash2), ==, 3);
1182  
1183 g_assert_cmpstr (g_hash_table_lookup (hash2, "a"), ==, "A");
1184 g_assert_cmpstr (g_hash_table_lookup (hash, "b"), ==, "B");
1185 g_assert_cmpstr (g_hash_table_lookup (hash2, "c"), ==, "C");
1186 g_assert_cmpstr (g_hash_table_lookup (hash, "d"), ==, "D");
1187 g_assert_cmpstr (g_hash_table_lookup (hash2, "e"), ==, "E");
1188 g_assert_cmpstr (g_hash_table_lookup (hash, "f"), ==, "F");
1189  
1190 g_hash_table_unref (hash);
1191 g_hash_table_unref (hash2);
1192 }
1193  
1194 struct _GHashTable
1195 {
1196 gint size;
1197 gint mod;
1198 guint mask;
1199 gint nnodes;
1200 gint noccupied; /* nnodes + tombstones */
1201  
1202 gpointer *keys;
1203 guint *hashes;
1204 gpointer *values;
1205  
1206 GHashFunc hash_func;
1207 GEqualFunc key_equal_func;
1208 volatile gint ref_count;
1209  
1210 #ifndef G_DISABLE_ASSERT
1211 int version;
1212 #endif
1213 GDestroyNotify key_destroy_func;
1214 GDestroyNotify value_destroy_func;
1215 };
1216  
1217 static void
1218 count_keys (GHashTable *h, gint *unused, gint *occupied, gint *tombstones)
1219 {
1220 gint i;
1221  
1222 *unused = 0;
1223 *occupied = 0;
1224 *tombstones = 0;
1225 for (i = 0; i < h->size; i++)
1226 {
1227 if (h->hashes[i] == 0)
1228 (*unused)++;
1229 else if (h->hashes[i] == 1)
1230 (*tombstones)++;
1231 else
1232 (*occupied)++;
1233 }
1234 }
1235  
1236 static void
1237 check_data (GHashTable *h)
1238 {
1239 gint i;
1240  
1241 for (i = 0; i < h->size; i++)
1242 {
1243 if (h->hashes[i] < 2)
1244 {
1245 g_assert (h->keys[i] == NULL);
1246 g_assert (h->values[i] == NULL);
1247 }
1248 else
1249 {
1250 g_assert_cmpint (h->hashes[i], ==, h->hash_func (h->keys[i]));
1251 }
1252 }
1253 }
1254  
1255 static void
1256 check_consistency (GHashTable *h)
1257 {
1258 gint unused;
1259 gint occupied;
1260 gint tombstones;
1261  
1262 count_keys (h, &unused, &occupied, &tombstones);
1263  
1264 g_assert_cmpint (occupied, ==, h->nnodes);
1265 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1266 g_assert_cmpint (occupied + tombstones + unused, ==, h->size);
1267  
1268 check_data (h);
1269 }
1270  
1271 static void
1272 check_counts (GHashTable *h, gint occupied, gint tombstones)
1273 {
1274 g_assert_cmpint (occupied, ==, h->nnodes);
1275 g_assert_cmpint (occupied + tombstones, ==, h->noccupied);
1276 }
1277  
1278 static void
1279 trivial_key_destroy (gpointer key)
1280 {
1281 }
1282  
1283 static void
1284 test_internal_consistency (void)
1285 {
1286 GHashTable *h;
1287  
1288 h = g_hash_table_new_full (g_str_hash, g_str_equal, trivial_key_destroy, NULL);
1289  
1290 check_counts (h, 0, 0);
1291 check_consistency (h);
1292  
1293 g_hash_table_insert (h, "a", "A");
1294 g_hash_table_insert (h, "b", "B");
1295 g_hash_table_insert (h, "c", "C");
1296 g_hash_table_insert (h, "d", "D");
1297 g_hash_table_insert (h, "e", "E");
1298 g_hash_table_insert (h, "f", "F");
1299  
1300 check_counts (h, 6, 0);
1301 check_consistency (h);
1302  
1303 g_hash_table_remove (h, "a");
1304 check_counts (h, 5, 1);
1305 check_consistency (h);
1306  
1307 g_hash_table_remove (h, "b");
1308 check_counts (h, 4, 2);
1309 check_consistency (h);
1310  
1311 g_hash_table_insert (h, "c", "c");
1312 check_counts (h, 4, 2);
1313 check_consistency (h);
1314  
1315 g_hash_table_insert (h, "a", "A");
1316 check_counts (h, 5, 1);
1317 check_consistency (h);
1318  
1319 g_hash_table_remove_all (h);
1320 check_counts (h, 0, 0);
1321 check_consistency (h);
1322  
1323 g_hash_table_unref (h);
1324 }
1325  
1326 static void
1327 my_key_free (gpointer v)
1328 {
1329 gchar *s = v;
1330 g_assert (s[0] != 'x');
1331 s[0] = 'x';
1332 g_free (v);
1333 }
1334  
1335 static void
1336 my_value_free (gpointer v)
1337 {
1338 gchar *s = v;
1339 g_assert (s[0] != 'y');
1340 s[0] = 'y';
1341 g_free (v);
1342 }
1343  
1344 static void
1345 test_iter_replace (void)
1346 {
1347 GHashTable *h;
1348 GHashTableIter iter;
1349 gpointer k, v;
1350 gchar *s;
1351  
1352 g_test_bug ("662544");
1353  
1354 h = g_hash_table_new_full (g_str_hash, g_str_equal, my_key_free, my_value_free);
1355  
1356 g_hash_table_insert (h, g_strdup ("A"), g_strdup ("a"));
1357 g_hash_table_insert (h, g_strdup ("B"), g_strdup ("b"));
1358 g_hash_table_insert (h, g_strdup ("C"), g_strdup ("c"));
1359  
1360 g_hash_table_iter_init (&iter, h);
1361  
1362 while (g_hash_table_iter_next (&iter, &k, &v))
1363 {
1364 s = (gchar*)v;
1365 g_assert (g_ascii_islower (s[0]));
1366 g_hash_table_iter_replace (&iter, g_strdup (k));
1367 }
1368  
1369 g_hash_table_unref (h);
1370 }
1371  
1372 static void
1373 replace_first_character (gchar *string)
1374 {
1375 string[0] = 'b';
1376 }
1377  
1378 static void
1379 test_set_insert_corruption (void)
1380 {
1381 GHashTable *hash_table =
1382 g_hash_table_new_full (g_str_hash, g_str_equal,
1383 (GDestroyNotify) replace_first_character, NULL);
1384 GHashTableIter iter;
1385 gchar a[] = "foo";
1386 gchar b[] = "foo";
1387 gpointer key, value;
1388  
1389 g_test_bug ("692815");
1390  
1391 g_hash_table_insert (hash_table, a, a);
1392 g_assert (g_hash_table_contains (hash_table, "foo"));
1393  
1394 g_hash_table_insert (hash_table, b, b);
1395  
1396 g_assert_cmpuint (g_hash_table_size (hash_table), ==, 1);
1397 g_hash_table_iter_init (&iter, hash_table);
1398 if (!g_hash_table_iter_next (&iter, &key, &value))
1399 g_assert_not_reached();
1400  
1401 /* per the documentation to g_hash_table_insert(), 'b' has now been freed,
1402 * and the sole key in 'hash_table' should be 'a'.
1403 */
1404 g_assert (key != b);
1405 g_assert (key == a);
1406  
1407 g_assert_cmpstr (b, ==, "boo");
1408  
1409 /* g_hash_table_insert() also says that the value should now be 'b',
1410 * which is probably not what the caller intended but is precisely what they
1411 * asked for.
1412 */
1413 g_assert (value == b);
1414  
1415 /* even though the hash has now been de-set-ified: */
1416 g_assert (g_hash_table_contains (hash_table, "foo"));
1417  
1418 g_hash_table_unref (hash_table);
1419 }
1420  
1421 static void
1422 test_set_to_strv (void)
1423 {
1424 GHashTable *set;
1425 gchar **strv;
1426 guint n;
1427  
1428 set = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
1429 g_hash_table_add (set, g_strdup ("xyz"));
1430 g_hash_table_add (set, g_strdup ("xyz"));
1431 g_hash_table_add (set, g_strdup ("abc"));
1432 strv = (gchar **) g_hash_table_get_keys_as_array (set, &n);
1433 g_hash_table_steal_all (set);
1434 g_hash_table_unref (set);
1435 g_assert_cmpint (n, ==, 2);
1436 n = g_strv_length (strv);
1437 g_assert_cmpint (n, ==, 2);
1438 if (g_str_equal (strv[0], "abc"))
1439 g_assert_cmpstr (strv[1], ==, "xyz");
1440 else
1441 {
1442 g_assert_cmpstr (strv[0], ==, "xyz");
1443 g_assert_cmpstr (strv[1], ==, "abc");
1444 }
1445 g_strfreev (strv);
1446 }
1447  
1448 static gboolean
1449 is_prime (guint p)
1450 {
1451 guint i;
1452  
1453 if (p % 2 == 0)
1454 return FALSE;
1455  
1456 i = 3;
1457 while (TRUE)
1458 {
1459 if (i * i > p)
1460 return TRUE;
1461  
1462 if (p % i == 0)
1463 return FALSE;
1464  
1465 i += 2;
1466 }
1467 }
1468  
1469 static void
1470 test_primes (void)
1471 {
1472 guint p, q;
1473 gdouble r, min, max;
1474  
1475 max = 1.0;
1476 min = 10.0;
1477 q = 1;
1478 while (1) {
1479 p = q;
1480 q = g_spaced_primes_closest (p);
1481 g_assert (is_prime (q));
1482 if (p == 1) continue;
1483 if (q == p) break;
1484 r = q / (gdouble) p;
1485 min = MIN (min, r);
1486 max = MAX (max, r);
1487 };
1488  
1489 g_assert_cmpfloat (1.3, <, min);
1490 g_assert_cmpfloat (max, <, 2.0);
1491 }
1492  
1493 int
1494 main (int argc, char *argv[])
1495 {
1496 g_test_init (&argc, &argv, NULL);
1497  
1498 g_test_bug_base ("http://bugzilla.gnome.org/");
1499  
1500 g_test_add_func ("/hash/misc", test_hash_misc);
1501 g_test_add_data_func ("/hash/one", GINT_TO_POINTER (TRUE), second_hash_test);
1502 g_test_add_data_func ("/hash/honeyman", GINT_TO_POINTER (FALSE), second_hash_test);
1503 g_test_add_func ("/hash/direct", direct_hash_test);
1504 g_test_add_func ("/hash/direct2", direct_hash_test2);
1505 g_test_add_func ("/hash/int", int_hash_test);
1506 g_test_add_func ("/hash/int64", int64_hash_test);
1507 g_test_add_func ("/hash/double", double_hash_test);
1508 g_test_add_func ("/hash/string", string_hash_test);
1509 g_test_add_func ("/hash/set", set_hash_test);
1510 g_test_add_func ("/hash/set-ref", set_ref_hash_test);
1511 g_test_add_func ("/hash/ref", test_hash_ref);
1512 g_test_add_func ("/hash/remove-all", test_remove_all);
1513 g_test_add_func ("/hash/recursive-remove-all", test_recursive_remove_all);
1514 g_test_add_func ("/hash/recursive-remove-all/subprocess", test_recursive_remove_all_subprocess);
1515 g_test_add_func ("/hash/find", test_find);
1516 g_test_add_func ("/hash/foreach", test_foreach);
1517 g_test_add_func ("/hash/foreach-steal", test_foreach_steal);
1518  
1519 /* tests for individual bugs */
1520 g_test_add_func ("/hash/lookup-null-key", test_lookup_null_key);
1521 g_test_add_func ("/hash/destroy-modify", test_destroy_modify);
1522 g_test_add_func ("/hash/consistency", test_internal_consistency);
1523 g_test_add_func ("/hash/iter-replace", test_iter_replace);
1524 g_test_add_func ("/hash/set-insert-corruption", test_set_insert_corruption);
1525 g_test_add_func ("/hash/set-to-strv", test_set_to_strv);
1526 g_test_add_func ("/hash/primes", test_primes);
1527  
1528 return g_test_run ();
1529  
1530 }