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