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