1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * SPDX-License-Identifier: LGPL-2.1-or-later
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 */
19
20 /*
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
25 */
26
27 /*
28 * MT safe
29 */
30
31 #include "config.h"
32
33 #include <string.h> /* memset */
34
35 #include "ghash.h"
36 #include "gmacros.h"
37 #include "glib-private.h"
38 #include "gstrfuncs.h"
39 #include "gatomic.h"
40 #include "gtestutils.h"
41 #include "gslice.h"
42 #include "grefcount.h"
43 #include "gvalgrind.h"
44
45 /* The following #pragma is here so we can do this...
46 *
47 * #ifndef USE_SMALL_ARRAYS
48 * is_big = TRUE;
49 * #endif
50 * return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
51 *
52 * ...instead of this...
53 *
54 * #ifndef USE_SMALL_ARRAYS
55 * return *(((gpointer *) a) + index);
56 * #else
57 * return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
58 * #endif
59 *
60 * ...and still compile successfully when -Werror=duplicated-branches is passed. */
61
62 #if defined(__GNUC__) && __GNUC__ > 6
63 #pragma GCC diagnostic ignored "-Wduplicated-branches"
64 #endif
65
66 /**
67 * GHashTable:
68 *
69 * The #GHashTable struct is an opaque data structure to represent a
70 * [Hash Table][glib-Hash-Tables]. It should only be accessed via the
71 * following functions.
72 */
73
74 /**
75 * GHashFunc:
76 * @key: a key
77 *
78 * Specifies the type of the hash function which is passed to
79 * g_hash_table_new() when a #GHashTable is created.
80 *
81 * The function is passed a key and should return a #guint hash value.
82 * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
83 * hash functions which can be used when the key is a #gpointer, #gint*,
84 * and #gchar* respectively.
85 *
86 * g_direct_hash() is also the appropriate hash function for keys
87 * of the form `GINT_TO_POINTER (n)` (or similar macros).
88 *
89 * A good hash functions should produce
90 * hash values that are evenly distributed over a fairly large range.
91 * The modulus is taken with the hash table size (a prime number) to
92 * find the 'bucket' to place each key into. The function should also
93 * be very fast, since it is called for each key lookup.
94 *
95 * Note that the hash functions provided by GLib have these qualities,
96 * but are not particularly robust against manufactured keys that
97 * cause hash collisions. Therefore, you should consider choosing
98 * a more secure hash function when using a GHashTable with keys
99 * that originate in untrusted data (such as HTTP requests).
100 * Using g_str_hash() in that situation might make your application
101 * vulnerable to
102 * [Algorithmic Complexity Attacks](https://lwn.net/Articles/474912/).
103 *
104 * The key to choosing a good hash is unpredictability. Even
105 * cryptographic hashes are very easy to find collisions for when the
106 * remainder is taken modulo a somewhat predictable prime number. There
107 * must be an element of randomness that an attacker is unable to guess.
108 *
109 * Returns: the hash value corresponding to the key
110 */
111
112 /**
113 * GHFunc:
114 * @key: a key
115 * @value: the value corresponding to the key
116 * @user_data: user data passed to g_hash_table_foreach()
117 *
118 * Specifies the type of the function passed to g_hash_table_foreach().
119 * It is called with each key/value pair, together with the @user_data
120 * parameter which is passed to g_hash_table_foreach().
121 */
122
123 /**
124 * GHRFunc:
125 * @key: a key
126 * @value: the value associated with the key
127 * @user_data: user data passed to g_hash_table_remove()
128 *
129 * Specifies the type of the function passed to
130 * g_hash_table_foreach_remove(). It is called with each key/value
131 * pair, together with the @user_data parameter passed to
132 * g_hash_table_foreach_remove(). It should return %TRUE if the
133 * key/value pair should be removed from the #GHashTable.
134 *
135 * Returns: %TRUE if the key/value pair should be removed from the
136 * #GHashTable
137 */
138
139 /**
140 * GEqualFunc:
141 * @a: a value
142 * @b: a value to compare with
143 *
144 * Specifies the type of a function used to test two values for
145 * equality. The function should return %TRUE if both values are equal
146 * and %FALSE otherwise.
147 *
148 * Returns: %TRUE if @a = @b; %FALSE otherwise
149 */
150
151 /**
152 * GHashTableIter:
153 *
154 * A GHashTableIter structure represents an iterator that can be used
155 * to iterate over the elements of a #GHashTable. GHashTableIter
156 * structures are typically allocated on the stack and then initialized
157 * with g_hash_table_iter_init().
158 *
159 * The iteration order of a #GHashTableIter over the keys/values in a hash
160 * table is not defined.
161 */
162
163 /**
164 * g_hash_table_freeze:
165 * @hash_table: a #GHashTable
166 *
167 * This function is deprecated and will be removed in the next major
168 * release of GLib. It does nothing.
169 */
170
171 /**
172 * g_hash_table_thaw:
173 * @hash_table: a #GHashTable
174 *
175 * This function is deprecated and will be removed in the next major
176 * release of GLib. It does nothing.
177 */
178
179 #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */
180
181 #define UNUSED_HASH_VALUE 0
182 #define TOMBSTONE_HASH_VALUE 1
183 #define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
184 #define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
185 #define HASH_IS_REAL(h_) ((h_) >= 2)
186
187 /* If int is smaller than void * on our arch, we start out with
188 * int-sized keys and values and resize to pointer-sized entries as
189 * needed. This saves a good amount of memory when the HT is being
190 * used with e.g. GUINT_TO_POINTER(). */
191
192 #define BIG_ENTRY_SIZE (SIZEOF_VOID_P)
193 #define SMALL_ENTRY_SIZE (SIZEOF_INT)
194
195 /* NB: The USE_SMALL_ARRAYS code assumes pointers are at most 8 bytes. */
196 #if SMALL_ENTRY_SIZE < BIG_ENTRY_SIZE && BIG_ENTRY_SIZE <= 8
197 # define USE_SMALL_ARRAYS
198 #endif
199
200 struct _GHashTable
201 {
202 gsize size;
203 gint mod;
204 guint mask;
205 guint nnodes;
206 guint noccupied; /* nnodes + tombstones */
207
208 guint have_big_keys : 1;
209 guint have_big_values : 1;
210
211 gpointer keys;
212 guint *hashes;
213 gpointer values;
214
215 GHashFunc hash_func;
216 GEqualFunc key_equal_func;
217 gatomicrefcount ref_count;
218 #ifndef G_DISABLE_ASSERT
219 /*
220 * Tracks the structure of the hash table, not its contents: is only
221 * incremented when a node is added or removed (is not incremented
222 * when the key or data of a node is modified).
223 */
224 int version;
225 #endif
226 GDestroyNotify key_destroy_func;
227 GDestroyNotify value_destroy_func;
228 };
229
230 typedef struct
231 {
232 GHashTable *hash_table;
233 gpointer dummy1;
234 gpointer dummy2;
235 gint position;
236 gboolean dummy3;
237 gintptr version;
238 } RealIter;
239
240 G_STATIC_ASSERT (sizeof (GHashTableIter) == sizeof (RealIter));
241 G_STATIC_ASSERT (G_ALIGNOF (GHashTableIter) >= G_ALIGNOF (RealIter));
242
243 /* Each table size has an associated prime modulo (the first prime
244 * lower than the table size) used to find the initial bucket. Probing
245 * then works modulo 2^n. The prime modulo is necessary to get a
246 * good distribution with poor hash functions.
247 */
248 static const gint prime_mod [] =
249 {
250 1, /* For 1 << 0 */
251 2,
252 3,
253 7,
254 13,
255 31,
256 61,
257 127,
258 251,
259 509,
260 1021,
261 2039,
262 4093,
263 8191,
264 16381,
265 32749,
266 65521, /* For 1 << 16 */
267 131071,
268 262139,
269 524287,
270 1048573,
271 2097143,
272 4194301,
273 8388593,
274 16777213,
275 33554393,
276 67108859,
277 134217689,
278 268435399,
279 536870909,
280 1073741789,
281 2147483647 /* For 1 << 31 */
282 };
283
284 static void
285 g_hash_table_set_shift (GHashTable *hash_table, gint shift)
286 {
287 hash_table->size = 1 << shift;
288 hash_table->mod = prime_mod [shift];
289
290 /* hash_table->size is always a power of two, so we can calculate the mask
291 * by simply subtracting 1 from it. The leading assertion ensures that
292 * we're really dealing with a power of two. */
293
294 g_assert ((hash_table->size & (hash_table->size - 1)) == 0);
295 hash_table->mask = hash_table->size - 1;
296 }
297
298 static gint
299 g_hash_table_find_closest_shift (gint n)
300 {
301 gint i;
302
303 for (i = 0; n; i++)
304 n >>= 1;
305
306 return i;
307 }
308
309 static void
310 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
311 {
312 gint shift;
313
314 shift = g_hash_table_find_closest_shift (size);
315 shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
316
317 g_hash_table_set_shift (hash_table, shift);
318 }
319
320 static inline gpointer
321 g_hash_table_realloc_key_or_value_array (gpointer a, guint size, G_GNUC_UNUSED gboolean is_big)
322 {
323 #ifdef USE_SMALL_ARRAYS
324 return g_realloc (a, size * (is_big ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE));
325 #else
326 return g_renew (gpointer, a, size);
327 #endif
328 }
329
330 static inline gpointer
331 g_hash_table_fetch_key_or_value (gpointer a, guint index, gboolean is_big)
332 {
333 #ifndef USE_SMALL_ARRAYS
334 is_big = TRUE;
335 #endif
336 return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
337 }
338
339 static inline void
340 g_hash_table_assign_key_or_value (gpointer a, guint index, gboolean is_big, gpointer v)
341 {
342 #ifndef USE_SMALL_ARRAYS
343 is_big = TRUE;
344 #endif
345 if (is_big)
346 *(((gpointer *) a) + index) = v;
347 else
348 *(((guint *) a) + index) = GPOINTER_TO_UINT (v);
349 }
350
351 static inline gpointer
352 g_hash_table_evict_key_or_value (gpointer a, guint index, gboolean is_big, gpointer v)
353 {
354 #ifndef USE_SMALL_ARRAYS
355 is_big = TRUE;
356 #endif
357 if (is_big)
358 {
359 gpointer r = *(((gpointer *) a) + index);
360 *(((gpointer *) a) + index) = v;
361 return r;
362 }
363 else
364 {
365 gpointer r = GUINT_TO_POINTER (*(((guint *) a) + index));
366 *(((guint *) a) + index) = GPOINTER_TO_UINT (v);
367 return r;
368 }
369 }
370
371 static inline guint
372 g_hash_table_hash_to_index (GHashTable *hash_table, guint hash)
373 {
374 /* Multiply the hash by a small prime before applying the modulo. This
375 * prevents the table from becoming densely packed, even with a poor hash
376 * function. A densely packed table would have poor performance on
377 * workloads with many failed lookups or a high degree of churn. */
378 return (hash * 11) % hash_table->mod;
379 }
380
381 /*
382 * g_hash_table_lookup_node:
383 * @hash_table: our #GHashTable
384 * @key: the key to look up against
385 * @hash_return: key hash return location
386 *
387 * Performs a lookup in the hash table, preserving extra information
388 * usually needed for insertion.
389 *
390 * This function first computes the hash value of the key using the
391 * user's hash function.
392 *
393 * If an entry in the table matching @key is found then this function
394 * returns the index of that entry in the table, and if not, the
395 * index of an unused node (empty or tombstone) where the key can be
396 * inserted.
397 *
398 * The computed hash value is returned in the variable pointed to
399 * by @hash_return. This is to save insertions from having to compute
400 * the hash record again for the new record.
401 *
402 * Returns: index of the described node
403 */
404 static inline guint
405 g_hash_table_lookup_node (GHashTable *hash_table,
406 gconstpointer key,
407 guint *hash_return)
408 {
409 guint node_index;
410 guint node_hash;
411 guint hash_value;
412 guint first_tombstone = 0;
413 gboolean have_tombstone = FALSE;
414 guint step = 0;
415
416 hash_value = hash_table->hash_func (key);
417 if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
418 hash_value = 2;
419
420 *hash_return = hash_value;
421
422 node_index = g_hash_table_hash_to_index (hash_table, hash_value);
423 node_hash = hash_table->hashes[node_index];
424
425 while (!HASH_IS_UNUSED (node_hash))
426 {
427 /* We first check if our full hash values
428 * are equal so we can avoid calling the full-blown
429 * key equality function in most cases.
430 */
431 if (node_hash == hash_value)
432 {
433 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
434
435 if (hash_table->key_equal_func)
436 {
437 if (hash_table->key_equal_func (node_key, key))
438 return node_index;
439 }
440 else if (node_key == key)
441 {
442 return node_index;
443 }
444 }
445 else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
446 {
447 first_tombstone = node_index;
448 have_tombstone = TRUE;
449 }
450
451 step++;
452 node_index += step;
453 node_index &= hash_table->mask;
454 node_hash = hash_table->hashes[node_index];
455 }
456
457 if (have_tombstone)
458 return first_tombstone;
459
460 return node_index;
461 }
462
463 /*
464 * g_hash_table_remove_node:
465 * @hash_table: our #GHashTable
466 * @node: pointer to node to remove
467 * @notify: %TRUE if the destroy notify handlers are to be called
468 *
469 * Removes a node from the hash table and updates the node count.
470 * The node is replaced by a tombstone. No table resize is performed.
471 *
472 * If @notify is %TRUE then the destroy notify functions are called
473 * for the key and value of the hash node.
474 */
475 static void
476 g_hash_table_remove_node (GHashTable *hash_table,
477 gint i,
478 gboolean notify)
479 {
480 gpointer key;
481 gpointer value;
482
483 key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
484 value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
485
486 /* Erect tombstone */
487 hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;
488
489 /* Be GC friendly */
490 g_hash_table_assign_key_or_value (hash_table->keys, i, hash_table->have_big_keys, NULL);
491 g_hash_table_assign_key_or_value (hash_table->values, i, hash_table->have_big_values, NULL);
492
493 g_assert (hash_table->nnodes > 0);
494 hash_table->nnodes--;
495
496 if (notify && hash_table->key_destroy_func)
497 hash_table->key_destroy_func (key);
498
499 if (notify && hash_table->value_destroy_func)
500 hash_table->value_destroy_func (value);
501
502 }
503
504 /*
505 * g_hash_table_setup_storage:
506 * @hash_table: our #GHashTable
507 *
508 * Initialise the hash table size, mask, mod, and arrays.
509 */
510 static void
511 g_hash_table_setup_storage (GHashTable *hash_table)
512 {
513 gboolean small = FALSE;
514
515 /* We want to use small arrays only if:
516 * - we are running on a system where that makes sense (64 bit); and
517 * - we are not running under valgrind.
518 */
519
520 #ifdef USE_SMALL_ARRAYS
521 small = TRUE;
522
523 # ifdef ENABLE_VALGRIND
524 if (RUNNING_ON_VALGRIND)
525 small = FALSE;
526 # endif
527 #endif
528
529 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
530
531 hash_table->have_big_keys = !small;
532 hash_table->have_big_values = !small;
533
534 hash_table->keys = g_hash_table_realloc_key_or_value_array (NULL, hash_table->size, hash_table->have_big_keys);
535 hash_table->values = hash_table->keys;
536 hash_table->hashes = g_new0 (guint, hash_table->size);
537 }
538
539 /*
540 * g_hash_table_remove_all_nodes:
541 * @hash_table: our #GHashTable
542 * @notify: %TRUE if the destroy notify handlers are to be called
543 *
544 * Removes all nodes from the table.
545 *
546 * If @notify is %TRUE then the destroy notify functions are called
547 * for the key and value of the hash node.
548 *
549 * Since this may be a precursor to freeing the table entirely, we'd
550 * ideally perform no resize, and we can indeed avoid that in some
551 * cases. However: in the case that we'll be making callbacks to user
552 * code (via destroy notifies) we need to consider that the user code
553 * might call back into the table again. In this case, we setup a new
554 * set of arrays so that any callers will see an empty (but valid)
555 * table.
556 */
557 static void
558 g_hash_table_remove_all_nodes (GHashTable *hash_table,
559 gboolean notify,
560 gboolean destruction)
561 {
562 int i;
563 gpointer key;
564 gpointer value;
565 gint old_size;
566 gpointer *old_keys;
567 gpointer *old_values;
568 guint *old_hashes;
569 gboolean old_have_big_keys;
570 gboolean old_have_big_values;
571
572 /* If the hash table is already empty, there is nothing to be done. */
573 if (hash_table->nnodes == 0)
574 return;
575
576 hash_table->nnodes = 0;
577 hash_table->noccupied = 0;
578
579 /* Easy case: no callbacks, so we just zero out the arrays */
580 if (!notify ||
581 (hash_table->key_destroy_func == NULL &&
582 hash_table->value_destroy_func == NULL))
583 {
584 if (!destruction)
585 {
586 memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
587
588 #ifdef USE_SMALL_ARRAYS
589 memset (hash_table->keys, 0, hash_table->size * (hash_table->have_big_keys ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE));
590 memset (hash_table->values, 0, hash_table->size * (hash_table->have_big_values ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE));
591 #else
592 memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
593 memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
594 #endif
595 }
596
597 return;
598 }
599
600 /* Hard case: we need to do user callbacks. There are two
601 * possibilities here:
602 *
603 * 1) there are no outstanding references on the table and therefore
604 * nobody should be calling into it again (destroying == true)
605 *
606 * 2) there are outstanding references, and there may be future
607 * calls into the table, either after we return, or from the destroy
608 * notifies that we're about to do (destroying == false)
609 *
610 * We handle both cases by taking the current state of the table into
611 * local variables and replacing it with something else: in the "no
612 * outstanding references" cases we replace it with a bunch of
613 * null/zero values so that any access to the table will fail. In the
614 * "may receive future calls" case, we reinitialise the struct to
615 * appear like a newly-created empty table.
616 *
617 * In both cases, we take over the references for the current state,
618 * freeing them below.
619 */
620 old_size = hash_table->size;
621 old_have_big_keys = hash_table->have_big_keys;
622 old_have_big_values = hash_table->have_big_values;
623 old_keys = g_steal_pointer (&hash_table->keys);
624 old_values = g_steal_pointer (&hash_table->values);
625 old_hashes = g_steal_pointer (&hash_table->hashes);
626
627 if (!destruction)
628 /* Any accesses will see an empty table */
629 g_hash_table_setup_storage (hash_table);
630 else
631 /* Will cause a quick crash on any attempted access */
632 hash_table->size = hash_table->mod = hash_table->mask = 0;
633
634 /* Now do the actual destroy notifies */
635 for (i = 0; i < old_size; i++)
636 {
637 if (HASH_IS_REAL (old_hashes[i]))
638 {
639 key = g_hash_table_fetch_key_or_value (old_keys, i, old_have_big_keys);
640 value = g_hash_table_fetch_key_or_value (old_values, i, old_have_big_values);
641
642 old_hashes[i] = UNUSED_HASH_VALUE;
643
644 g_hash_table_assign_key_or_value (old_keys, i, old_have_big_keys, NULL);
645 g_hash_table_assign_key_or_value (old_values, i, old_have_big_values, NULL);
646
647 if (hash_table->key_destroy_func != NULL)
648 hash_table->key_destroy_func (key);
649
650 if (hash_table->value_destroy_func != NULL)
651 hash_table->value_destroy_func (value);
652 }
653 }
654
655 /* Destroy old storage space. */
656 if (old_keys != old_values)
657 g_free (old_values);
658
659 g_free (old_keys);
660 g_free (old_hashes);
661 }
662
663 static void
664 realloc_arrays (GHashTable *hash_table, gboolean is_a_set)
665 {
666 hash_table->hashes = g_renew (guint, hash_table->hashes, hash_table->size);
667 hash_table->keys = g_hash_table_realloc_key_or_value_array (hash_table->keys, hash_table->size, hash_table->have_big_keys);
668
669 if (is_a_set)
670 hash_table->values = hash_table->keys;
671 else
672 hash_table->values = g_hash_table_realloc_key_or_value_array (hash_table->values, hash_table->size, hash_table->have_big_values);
673 }
674
675 /* When resizing the table in place, we use a temporary bit array to keep
676 * track of which entries have been assigned a proper location in the new
677 * table layout.
678 *
679 * Each bit corresponds to a bucket. A bit is set if an entry was assigned
680 * its corresponding location during the resize and thus should not be
681 * evicted. The array starts out cleared to zero. */
682
683 static inline gboolean
684 get_status_bit (const guint32 *bitmap, guint index)
685 {
686 return (bitmap[index / 32] >> (index % 32)) & 1;
687 }
688
689 static inline void
690 set_status_bit (guint32 *bitmap, guint index)
691 {
692 bitmap[index / 32] |= 1U << (index % 32);
693 }
694
695 /* By calling dedicated resize functions for sets and maps, we avoid 2x
696 * test-and-branch per key in the inner loop. This yields a small
697 * performance improvement at the cost of a bit of macro gunk. */
698
699 #define DEFINE_RESIZE_FUNC(fname) \
700 static void fname (GHashTable *hash_table, guint old_size, guint32 *reallocated_buckets_bitmap) \
701 { \
702 guint i; \
703 \
704 for (i = 0; i < old_size; i++) \
705 { \
706 guint node_hash = hash_table->hashes[i]; \
707 gpointer key, value G_GNUC_UNUSED; \
708 \
709 if (!HASH_IS_REAL (node_hash)) \
710 { \
711 /* Clear tombstones */ \
712 hash_table->hashes[i] = UNUSED_HASH_VALUE; \
713 continue; \
714 } \
715 \
716 /* Skip entries relocated through eviction */ \
717 if (get_status_bit (reallocated_buckets_bitmap, i)) \
718 continue; \
719 \
720 hash_table->hashes[i] = UNUSED_HASH_VALUE; \
721 EVICT_KEYVAL (hash_table, i, NULL, NULL, key, value); \
722 \
723 for (;;) \
724 { \
725 guint hash_val; \
726 guint replaced_hash; \
727 guint step = 0; \
728 \
729 hash_val = g_hash_table_hash_to_index (hash_table, node_hash); \
730 \
731 while (get_status_bit (reallocated_buckets_bitmap, hash_val)) \
732 { \
733 step++; \
734 hash_val += step; \
735 hash_val &= hash_table->mask; \
736 } \
737 \
738 set_status_bit (reallocated_buckets_bitmap, hash_val); \
739 \
740 replaced_hash = hash_table->hashes[hash_val]; \
741 hash_table->hashes[hash_val] = node_hash; \
742 if (!HASH_IS_REAL (replaced_hash)) \
743 { \
744 ASSIGN_KEYVAL (hash_table, hash_val, key, value); \
745 break; \
746 } \
747 \
748 node_hash = replaced_hash; \
749 EVICT_KEYVAL (hash_table, hash_val, key, value, key, value); \
750 } \
751 } \
752 }
753
754 #define ASSIGN_KEYVAL(ht, index, key, value) G_STMT_START{ \
755 g_hash_table_assign_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
756 g_hash_table_assign_key_or_value ((ht)->values, (index), (ht)->have_big_values, (value)); \
757 }G_STMT_END
758
759 #define EVICT_KEYVAL(ht, index, key, value, outkey, outvalue) G_STMT_START{ \
760 (outkey) = g_hash_table_evict_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
761 (outvalue) = g_hash_table_evict_key_or_value ((ht)->values, (index), (ht)->have_big_values, (value)); \
762 }G_STMT_END
763
764 DEFINE_RESIZE_FUNC (resize_map)
765
766 #undef ASSIGN_KEYVAL
767 #undef EVICT_KEYVAL
768
769 #define ASSIGN_KEYVAL(ht, index, key, value) G_STMT_START{ \
770 g_hash_table_assign_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
771 }G_STMT_END
772
773 #define EVICT_KEYVAL(ht, index, key, value, outkey, outvalue) G_STMT_START{ \
774 (outkey) = g_hash_table_evict_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
775 }G_STMT_END
776
777 DEFINE_RESIZE_FUNC (resize_set)
778
779 #undef ASSIGN_KEYVAL
780 #undef EVICT_KEYVAL
781
782 /*
783 * g_hash_table_resize:
784 * @hash_table: our #GHashTable
785 *
786 * Resizes the hash table to the optimal size based on the number of
787 * nodes currently held. If you call this function then a resize will
788 * occur, even if one does not need to occur.
789 * Use g_hash_table_maybe_resize() instead.
790 *
791 * This function may "resize" the hash table to its current size, with
792 * the side effect of cleaning up tombstones and otherwise optimizing
793 * the probe sequences.
794 */
795 static void
796 g_hash_table_resize (GHashTable *hash_table)
797 {
798 guint32 *reallocated_buckets_bitmap;
799 gsize old_size;
800 gboolean is_a_set;
801
802 old_size = hash_table->size;
803 is_a_set = hash_table->keys == hash_table->values;
804
805 /* The outer checks in g_hash_table_maybe_resize() will only consider
806 * cleanup/resize when the load factor goes below .25 (1/4, ignoring
807 * tombstones) or above .9375 (15/16, including tombstones).
808 *
809 * Once this happens, tombstones will always be cleaned out. If our
810 * load sans tombstones is greater than .75 (1/1.333, see below), we'll
811 * take this opportunity to grow the table too.
812 *
813 * Immediately after growing, the load factor will be in the range
814 * .375 .. .469. After shrinking, it will be exactly .5. */
815
816 g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 1.333);
817
818 if (hash_table->size > old_size)
819 {
820 realloc_arrays (hash_table, is_a_set);
821 memset (&hash_table->hashes[old_size], 0, (hash_table->size - old_size) * sizeof (guint));
822
823 reallocated_buckets_bitmap = g_new0 (guint32, (hash_table->size + 31) / 32);
824 }
825 else
826 {
827 reallocated_buckets_bitmap = g_new0 (guint32, (old_size + 31) / 32);
828 }
829
830 if (is_a_set)
831 resize_set (hash_table, old_size, reallocated_buckets_bitmap);
832 else
833 resize_map (hash_table, old_size, reallocated_buckets_bitmap);
834
835 g_free (reallocated_buckets_bitmap);
836
837 if (hash_table->size < old_size)
838 realloc_arrays (hash_table, is_a_set);
839
840 hash_table->noccupied = hash_table->nnodes;
841 }
842
843 /*
844 * g_hash_table_maybe_resize:
845 * @hash_table: our #GHashTable
846 *
847 * Resizes the hash table, if needed.
848 *
849 * Essentially, calls g_hash_table_resize() if the table has strayed
850 * too far from its ideal size for its number of nodes.
851 */
852 static inline void
853 g_hash_table_maybe_resize (GHashTable *hash_table)
854 {
855 gsize noccupied = hash_table->noccupied;
856 gsize size = hash_table->size;
857
858 if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
859 (size <= noccupied + (noccupied / 16)))
860 g_hash_table_resize (hash_table);
861 }
862
863 #ifdef USE_SMALL_ARRAYS
864
865 static inline gboolean
866 entry_is_big (gpointer v)
867 {
868 return (((guintptr) v) >> ((BIG_ENTRY_SIZE - SMALL_ENTRY_SIZE) * 8)) != 0;
869 }
870
871 static inline gboolean
872 g_hash_table_maybe_make_big_keys_or_values (gpointer *a_p, gpointer v, gint ht_size)
873 {
874 if (entry_is_big (v))
875 {
876 guint *a = (guint *) *a_p;
877 gpointer *a_new;
878 gint i;
879
880 a_new = g_new (gpointer, ht_size);
881
882 for (i = 0; i < ht_size; i++)
883 {
884 a_new[i] = GUINT_TO_POINTER (a[i]);
885 }
886
887 g_free (a);
888 *a_p = a_new;
889 return TRUE;
890 }
891
892 return FALSE;
893 }
894
895 #endif
896
897 static inline void
898 g_hash_table_ensure_keyval_fits (GHashTable *hash_table, gpointer key, gpointer value)
899 {
900 gboolean is_a_set = (hash_table->keys == hash_table->values);
901
902 #ifdef USE_SMALL_ARRAYS
903
904 /* Convert from set to map? */
905 if (is_a_set)
906 {
907 if (hash_table->have_big_keys)
908 {
909 if (key != value)
910 hash_table->values = g_memdup2 (hash_table->keys, sizeof (gpointer) * hash_table->size);
911 /* Keys and values are both big now, so no need for further checks */
912 return;
913 }
914 else
915 {
916 if (key != value)
917 {
918 hash_table->values = g_memdup2 (hash_table->keys, sizeof (guint) * hash_table->size);
919 is_a_set = FALSE;
920 }
921 }
922 }
923
924 /* Make keys big? */
925 if (!hash_table->have_big_keys)
926 {
927 hash_table->have_big_keys = g_hash_table_maybe_make_big_keys_or_values (&hash_table->keys, key, hash_table->size);
928
929 if (is_a_set)
930 {
931 hash_table->values = hash_table->keys;
932 hash_table->have_big_values = hash_table->have_big_keys;
933 }
934 }
935
936 /* Make values big? */
937 if (!is_a_set && !hash_table->have_big_values)
938 {
939 hash_table->have_big_values = g_hash_table_maybe_make_big_keys_or_values (&hash_table->values, value, hash_table->size);
940 }
941
942 #else
943
944 /* Just split if necessary */
945 if (is_a_set && key != value)
946 hash_table->values = g_memdup2 (hash_table->keys, sizeof (gpointer) * hash_table->size);
947
948 #endif
949 }
950
951 /**
952 * g_hash_table_new:
953 * @hash_func: a function to create a hash value from a key
954 * @key_equal_func: a function to check two keys for equality
955 *
956 * Creates a new #GHashTable with a reference count of 1.
957 *
958 * Hash values returned by @hash_func are used to determine where keys
959 * are stored within the #GHashTable data structure. The g_direct_hash(),
960 * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash()
961 * functions are provided for some common types of keys.
962 * If @hash_func is %NULL, g_direct_hash() is used.
963 *
964 * @key_equal_func is used when looking up keys in the #GHashTable.
965 * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal()
966 * and g_str_equal() functions are provided for the most common types
967 * of keys. If @key_equal_func is %NULL, keys are compared directly in
968 * a similar fashion to g_direct_equal(), but without the overhead of
969 * a function call. @key_equal_func is called with the key from the hash table
970 * as its first parameter, and the user-provided key to check against as
971 * its second.
972 *
973 * Returns: (transfer full): a new #GHashTable
974 */
975 GHashTable *
976 g_hash_table_new (GHashFunc hash_func,
977 GEqualFunc key_equal_func)
978 {
979 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
980 }
981
982
983 /**
984 * g_hash_table_new_full:
985 * @hash_func: a function to create a hash value from a key
986 * @key_equal_func: a function to check two keys for equality
987 * @key_destroy_func: (nullable): a function to free the memory allocated for the key
988 * used when removing the entry from the #GHashTable, or %NULL
989 * if you don't want to supply such a function.
990 * @value_destroy_func: (nullable): a function to free the memory allocated for the
991 * value used when removing the entry from the #GHashTable, or %NULL
992 * if you don't want to supply such a function.
993 *
994 * Creates a new #GHashTable like g_hash_table_new() with a reference
995 * count of 1 and allows to specify functions to free the memory
996 * allocated for the key and value that get called when removing the
997 * entry from the #GHashTable.
998 *
999 * Since version 2.42 it is permissible for destroy notify functions to
1000 * recursively remove further items from the hash table. This is only
1001 * permissible if the application still holds a reference to the hash table.
1002 * This means that you may need to ensure that the hash table is empty by
1003 * calling g_hash_table_remove_all() before releasing the last reference using
1004 * g_hash_table_unref().
1005 *
1006 * Returns: (transfer full): a new #GHashTable
1007 */
1008 GHashTable *
1009 g_hash_table_new_full (GHashFunc hash_func,
1010 GEqualFunc key_equal_func,
1011 GDestroyNotify key_destroy_func,
1012 GDestroyNotify value_destroy_func)
1013 {
1014 GHashTable *hash_table;
1015
1016 hash_table = g_slice_new (GHashTable);
1017 g_atomic_ref_count_init (&hash_table->ref_count);
1018 hash_table->nnodes = 0;
1019 hash_table->noccupied = 0;
1020 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
1021 hash_table->key_equal_func = key_equal_func;
1022 #ifndef G_DISABLE_ASSERT
1023 hash_table->version = 0;
1024 #endif
1025 hash_table->key_destroy_func = key_destroy_func;
1026 hash_table->value_destroy_func = value_destroy_func;
1027
1028 g_hash_table_setup_storage (hash_table);
1029
1030 return hash_table;
1031 }
1032
1033 /**
1034 * g_hash_table_new_similar:
1035 * @other_hash_table: (not nullable) (transfer none): Another #GHashTable
1036 *
1037 * Creates a new #GHashTable like g_hash_table_new_full() with a reference
1038 * count of 1.
1039 *
1040 * It inherits the hash function, the key equal function, the key destroy function,
1041 * as well as the value destroy function, from @other_hash_table.
1042 *
1043 * The returned hash table will be empty; it will not contain the keys
1044 * or values from @other_hash_table.
1045 *
1046 * Returns: (transfer full) (not nullable): a new #GHashTable
1047 * Since: 2.72
1048 */
1049 GHashTable *
1050 g_hash_table_new_similar (GHashTable *other_hash_table)
1051 {
1052 g_return_val_if_fail (other_hash_table, NULL);
1053
1054 return g_hash_table_new_full (other_hash_table->hash_func,
1055 other_hash_table->key_equal_func,
1056 other_hash_table->key_destroy_func,
1057 other_hash_table->value_destroy_func);
1058 }
1059
1060 /**
1061 * g_hash_table_iter_init:
1062 * @iter: an uninitialized #GHashTableIter
1063 * @hash_table: a #GHashTable
1064 *
1065 * Initializes a key/value pair iterator and associates it with
1066 * @hash_table. Modifying the hash table after calling this function
1067 * invalidates the returned iterator.
1068 *
1069 * The iteration order of a #GHashTableIter over the keys/values in a hash
1070 * table is not defined.
1071 *
1072 * |[<!-- language="C" -->
1073 * GHashTableIter iter;
1074 * gpointer key, value;
1075 *
1076 * g_hash_table_iter_init (&iter, hash_table);
1077 * while (g_hash_table_iter_next (&iter, &key, &value))
1078 * {
1079 * // do something with key and value
1080 * }
1081 * ]|
1082 *
1083 * Since: 2.16
1084 */
1085 void
1086 g_hash_table_iter_init (GHashTableIter *iter,
1087 GHashTable *hash_table)
1088 {
1089 RealIter *ri = (RealIter *) iter;
1090
1091 g_return_if_fail (iter != NULL);
1092 g_return_if_fail (hash_table != NULL);
1093
1094 ri->hash_table = hash_table;
1095 ri->position = -1;
1096 #ifndef G_DISABLE_ASSERT
1097 ri->version = hash_table->version;
1098 #endif
1099 }
1100
1101 /**
1102 * g_hash_table_iter_next:
1103 * @iter: an initialized #GHashTableIter
1104 * @key: (out) (optional) (nullable): a location to store the key
1105 * @value: (out) (optional) (nullable): a location to store the value
1106 *
1107 * Advances @iter and retrieves the key and/or value that are now
1108 * pointed to as a result of this advancement. If %FALSE is returned,
1109 * @key and @value are not set, and the iterator becomes invalid.
1110 *
1111 * Returns: %FALSE if the end of the #GHashTable has been reached.
1112 *
1113 * Since: 2.16
1114 */
1115 gboolean
1116 g_hash_table_iter_next (GHashTableIter *iter,
1117 gpointer *key,
1118 gpointer *value)
1119 {
1120 RealIter *ri = (RealIter *) iter;
1121 gint position;
1122
1123 g_return_val_if_fail (iter != NULL, FALSE);
1124 #ifndef G_DISABLE_ASSERT
1125 g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
1126 #endif
1127 g_return_val_if_fail (ri->position < (gssize) ri->hash_table->size, FALSE);
1128
1129 position = ri->position;
1130
1131 do
1132 {
1133 position++;
1134 if (position >= (gssize) ri->hash_table->size)
1135 {
1136 ri->position = position;
1137 return FALSE;
1138 }
1139 }
1140 while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
1141
1142 if (key != NULL)
1143 *key = g_hash_table_fetch_key_or_value (ri->hash_table->keys, position, ri->hash_table->have_big_keys);
1144 if (value != NULL)
1145 *value = g_hash_table_fetch_key_or_value (ri->hash_table->values, position, ri->hash_table->have_big_values);
1146
1147 ri->position = position;
1148 return TRUE;
1149 }
1150
1151 /**
1152 * g_hash_table_iter_get_hash_table:
1153 * @iter: an initialized #GHashTableIter
1154 *
1155 * Returns the #GHashTable associated with @iter.
1156 *
1157 * Returns: (transfer none): the #GHashTable associated with @iter.
1158 *
1159 * Since: 2.16
1160 */
1161 GHashTable *
1162 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
1163 {
1164 g_return_val_if_fail (iter != NULL, NULL);
1165
1166 return ((RealIter *) iter)->hash_table;
1167 }
1168
1169 static void
1170 iter_remove_or_steal (RealIter *ri, gboolean notify)
1171 {
1172 g_return_if_fail (ri != NULL);
1173 #ifndef G_DISABLE_ASSERT
1174 g_return_if_fail (ri->version == ri->hash_table->version);
1175 #endif
1176 g_return_if_fail (ri->position >= 0);
1177 g_return_if_fail ((gsize) ri->position < ri->hash_table->size);
1178
1179 g_hash_table_remove_node (ri->hash_table, ri->position, notify);
1180
1181 #ifndef G_DISABLE_ASSERT
1182 ri->version++;
1183 ri->hash_table->version++;
1184 #endif
1185 }
1186
1187 /**
1188 * g_hash_table_iter_remove:
1189 * @iter: an initialized #GHashTableIter
1190 *
1191 * Removes the key/value pair currently pointed to by the iterator
1192 * from its associated #GHashTable. Can only be called after
1193 * g_hash_table_iter_next() returned %TRUE, and cannot be called
1194 * more than once for the same key/value pair.
1195 *
1196 * If the #GHashTable was created using g_hash_table_new_full(),
1197 * the key and value are freed using the supplied destroy functions,
1198 * otherwise you have to make sure that any dynamically allocated
1199 * values are freed yourself.
1200 *
1201 * It is safe to continue iterating the #GHashTable afterward:
1202 * |[<!-- language="C" -->
1203 * while (g_hash_table_iter_next (&iter, &key, &value))
1204 * {
1205 * if (condition)
1206 * g_hash_table_iter_remove (&iter);
1207 * }
1208 * ]|
1209 *
1210 * Since: 2.16
1211 */
1212 void
1213 g_hash_table_iter_remove (GHashTableIter *iter)
1214 {
1215 iter_remove_or_steal ((RealIter *) iter, TRUE);
1216 }
1217
1218 /*
1219 * g_hash_table_insert_node:
1220 * @hash_table: our #GHashTable
1221 * @node_index: pointer to node to insert/replace
1222 * @key_hash: key hash
1223 * @key: (nullable): key to replace with, or %NULL
1224 * @value: value to replace with
1225 * @keep_new_key: whether to replace the key in the node with @key
1226 * @reusing_key: whether @key was taken out of the existing node
1227 *
1228 * Inserts a value at @node_index in the hash table and updates it.
1229 *
1230 * If @key has been taken out of the existing node (ie it is not
1231 * passed in via a g_hash_table_insert/replace) call, then @reusing_key
1232 * should be %TRUE.
1233 *
1234 * Returns: %TRUE if the key did not exist yet
1235 */
1236 static gboolean
1237 g_hash_table_insert_node (GHashTable *hash_table,
1238 guint node_index,
1239 guint key_hash,
1240 gpointer new_key,
1241 gpointer new_value,
1242 gboolean keep_new_key,
1243 gboolean reusing_key)
1244 {
1245 gboolean already_exists;
1246 guint old_hash;
1247 gpointer key_to_free = NULL;
1248 gpointer key_to_keep = NULL;
1249 gpointer value_to_free = NULL;
1250
1251 old_hash = hash_table->hashes[node_index];
1252 already_exists = HASH_IS_REAL (old_hash);
1253
1254 /* Proceed in three steps. First, deal with the key because it is the
1255 * most complicated. Then consider if we need to split the table in
1256 * two (because writing the value will result in the set invariant
1257 * becoming broken). Then deal with the value.
1258 *
1259 * There are three cases for the key:
1260 *
1261 * - entry already exists in table, reusing key:
1262 * free the just-passed-in new_key and use the existing value
1263 *
1264 * - entry already exists in table, not reusing key:
1265 * free the entry in the table, use the new key
1266 *
1267 * - entry not already in table:
1268 * use the new key, free nothing
1269 *
1270 * We update the hash at the same time...
1271 */
1272 if (already_exists)
1273 {
1274 /* Note: we must record the old value before writing the new key
1275 * because we might change the value in the event that the two
1276 * arrays are shared.
1277 */
1278 value_to_free = g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values);
1279
1280 if (keep_new_key)
1281 {
1282 key_to_free = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1283 key_to_keep = new_key;
1284 }
1285 else
1286 {
1287 key_to_free = new_key;
1288 key_to_keep = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1289 }
1290 }
1291 else
1292 {
1293 hash_table->hashes[node_index] = key_hash;
1294 key_to_keep = new_key;
1295 }
1296
1297 /* Resize key/value arrays and split table as necessary */
1298 g_hash_table_ensure_keyval_fits (hash_table, key_to_keep, new_value);
1299 g_hash_table_assign_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys, key_to_keep);
1300
1301 /* Step 3: Actually do the write */
1302 g_hash_table_assign_key_or_value (hash_table->values, node_index, hash_table->have_big_values, new_value);
1303
1304 /* Now, the bookkeeping... */
1305 if (!already_exists)
1306 {
1307 hash_table->nnodes++;
1308
1309 if (HASH_IS_UNUSED (old_hash))
1310 {
1311 /* We replaced an empty node, and not a tombstone */
1312 hash_table->noccupied++;
1313 g_hash_table_maybe_resize (hash_table);
1314 }
1315
1316 #ifndef G_DISABLE_ASSERT
1317 hash_table->version++;
1318 #endif
1319 }
1320
1321 if (already_exists)
1322 {
1323 if (hash_table->key_destroy_func && !reusing_key)
1324 (* hash_table->key_destroy_func) (key_to_free);
1325 if (hash_table->value_destroy_func)
1326 (* hash_table->value_destroy_func) (value_to_free);
1327 }
1328
1329 return !already_exists;
1330 }
1331
1332 /**
1333 * g_hash_table_iter_replace:
1334 * @iter: an initialized #GHashTableIter
1335 * @value: the value to replace with
1336 *
1337 * Replaces the value currently pointed to by the iterator
1338 * from its associated #GHashTable. Can only be called after
1339 * g_hash_table_iter_next() returned %TRUE.
1340 *
1341 * If you supplied a @value_destroy_func when creating the
1342 * #GHashTable, the old value is freed using that function.
1343 *
1344 * Since: 2.30
1345 */
1346 void
1347 g_hash_table_iter_replace (GHashTableIter *iter,
1348 gpointer value)
1349 {
1350 RealIter *ri;
1351 guint node_hash;
1352 gpointer key;
1353
1354 ri = (RealIter *) iter;
1355
1356 g_return_if_fail (ri != NULL);
1357 #ifndef G_DISABLE_ASSERT
1358 g_return_if_fail (ri->version == ri->hash_table->version);
1359 #endif
1360 g_return_if_fail (ri->position >= 0);
1361 g_return_if_fail ((gsize) ri->position < ri->hash_table->size);
1362
1363 node_hash = ri->hash_table->hashes[ri->position];
1364
1365 key = g_hash_table_fetch_key_or_value (ri->hash_table->keys, ri->position, ri->hash_table->have_big_keys);
1366
1367 g_hash_table_insert_node (ri->hash_table, ri->position, node_hash, key, value, TRUE, TRUE);
1368
1369 #ifndef G_DISABLE_ASSERT
1370 ri->version++;
1371 ri->hash_table->version++;
1372 #endif
1373 }
1374
1375 /**
1376 * g_hash_table_iter_steal:
1377 * @iter: an initialized #GHashTableIter
1378 *
1379 * Removes the key/value pair currently pointed to by the
1380 * iterator from its associated #GHashTable, without calling
1381 * the key and value destroy functions. Can only be called
1382 * after g_hash_table_iter_next() returned %TRUE, and cannot
1383 * be called more than once for the same key/value pair.
1384 *
1385 * Since: 2.16
1386 */
1387 void
1388 g_hash_table_iter_steal (GHashTableIter *iter)
1389 {
1390 iter_remove_or_steal ((RealIter *) iter, FALSE);
1391 }
1392
1393
1394 /**
1395 * g_hash_table_ref:
1396 * @hash_table: a valid #GHashTable
1397 *
1398 * Atomically increments the reference count of @hash_table by one.
1399 * This function is MT-safe and may be called from any thread.
1400 *
1401 * Returns: (transfer full): the passed in #GHashTable
1402 *
1403 * Since: 2.10
1404 */
1405 GHashTable *
1406 g_hash_table_ref (GHashTable *hash_table)
1407 {
1408 g_return_val_if_fail (hash_table != NULL, NULL);
1409
1410 g_atomic_ref_count_inc (&hash_table->ref_count);
1411
1412 return hash_table;
1413 }
1414
1415 /**
1416 * g_hash_table_unref:
1417 * @hash_table: (transfer full): a valid #GHashTable
1418 *
1419 * Atomically decrements the reference count of @hash_table by one.
1420 * If the reference count drops to 0, all keys and values will be
1421 * destroyed, and all memory allocated by the hash table is released.
1422 * This function is MT-safe and may be called from any thread.
1423 *
1424 * Since: 2.10
1425 */
1426 void
1427 g_hash_table_unref (GHashTable *hash_table)
1428 {
1429 g_return_if_fail (hash_table != NULL);
1430
1431 if (g_atomic_ref_count_dec (&hash_table->ref_count))
1432 {
1433 g_hash_table_remove_all_nodes (hash_table, TRUE, TRUE);
1434 if (hash_table->keys != hash_table->values)
1435 g_free (hash_table->values);
1436 g_free (hash_table->keys);
1437 g_free (hash_table->hashes);
1438 g_slice_free (GHashTable, hash_table);
1439 }
1440 }
1441
1442 /**
1443 * g_hash_table_destroy:
1444 * @hash_table: a #GHashTable
1445 *
1446 * Destroys all keys and values in the #GHashTable and decrements its
1447 * reference count by 1. If keys and/or values are dynamically allocated,
1448 * you should either free them first or create the #GHashTable with destroy
1449 * notifiers using g_hash_table_new_full(). In the latter case the destroy
1450 * functions you supplied will be called on all keys and values during the
1451 * destruction phase.
1452 */
1453 void
1454 g_hash_table_destroy (GHashTable *hash_table)
1455 {
1456 g_return_if_fail (hash_table != NULL);
1457
1458 g_hash_table_remove_all (hash_table);
1459 g_hash_table_unref (hash_table);
1460 }
1461
1462 /**
1463 * g_hash_table_lookup:
1464 * @hash_table: a #GHashTable
1465 * @key: the key to look up
1466 *
1467 * Looks up a key in a #GHashTable. Note that this function cannot
1468 * distinguish between a key that is not present and one which is present
1469 * and has the value %NULL. If you need this distinction, use
1470 * g_hash_table_lookup_extended().
1471 *
1472 * Returns: (nullable): the associated value, or %NULL if the key is not found
1473 */
1474 gpointer
1475 g_hash_table_lookup (GHashTable *hash_table,
1476 gconstpointer key)
1477 {
1478 guint node_index;
1479 guint node_hash;
1480
1481 g_return_val_if_fail (hash_table != NULL, NULL);
1482
1483 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1484
1485 return HASH_IS_REAL (hash_table->hashes[node_index])
1486 ? g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values)
1487 : NULL;
1488 }
1489
1490 /**
1491 * g_hash_table_lookup_extended:
1492 * @hash_table: a #GHashTable
1493 * @lookup_key: the key to look up
1494 * @orig_key: (out) (optional): return location for the original key
1495 * @value: (out) (optional) (nullable): return location for the value associated
1496 * with the key
1497 *
1498 * Looks up a key in the #GHashTable, returning the original key and the
1499 * associated value and a #gboolean which is %TRUE if the key was found. This
1500 * is useful if you need to free the memory allocated for the original key,
1501 * for example before calling g_hash_table_remove().
1502 *
1503 * You can actually pass %NULL for @lookup_key to test
1504 * whether the %NULL key exists, provided the hash and equal functions
1505 * of @hash_table are %NULL-safe.
1506 *
1507 * Returns: %TRUE if the key was found in the #GHashTable
1508 */
1509 gboolean
1510 g_hash_table_lookup_extended (GHashTable *hash_table,
1511 gconstpointer lookup_key,
1512 gpointer *orig_key,
1513 gpointer *value)
1514 {
1515 guint node_index;
1516 guint node_hash;
1517
1518 g_return_val_if_fail (hash_table != NULL, FALSE);
1519
1520 node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1521
1522 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1523 {
1524 if (orig_key != NULL)
1525 *orig_key = NULL;
1526 if (value != NULL)
1527 *value = NULL;
1528
1529 return FALSE;
1530 }
1531
1532 if (orig_key)
1533 *orig_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1534
1535 if (value)
1536 *value = g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values);
1537
1538 return TRUE;
1539 }
1540
1541 /*
1542 * g_hash_table_insert_internal:
1543 * @hash_table: our #GHashTable
1544 * @key: the key to insert
1545 * @value: the value to insert
1546 * @keep_new_key: if %TRUE and this key already exists in the table
1547 * then call the destroy notify function on the old key. If %FALSE
1548 * then call the destroy notify function on the new key.
1549 *
1550 * Implements the common logic for the g_hash_table_insert() and
1551 * g_hash_table_replace() functions.
1552 *
1553 * Do a lookup of @key. If it is found, replace it with the new
1554 * @value (and perhaps the new @key). If it is not found, create
1555 * a new node.
1556 *
1557 * Returns: %TRUE if the key did not exist yet
1558 */
1559 static gboolean
1560 g_hash_table_insert_internal (GHashTable *hash_table,
1561 gpointer key,
1562 gpointer value,
1563 gboolean keep_new_key)
1564 {
1565 guint key_hash;
1566 guint node_index;
1567
1568 g_return_val_if_fail (hash_table != NULL, FALSE);
1569
1570 node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
1571
1572 return g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key, FALSE);
1573 }
1574
1575 /**
1576 * g_hash_table_insert:
1577 * @hash_table: a #GHashTable
1578 * @key: a key to insert
1579 * @value: the value to associate with the key
1580 *
1581 * Inserts a new key and value into a #GHashTable.
1582 *
1583 * If the key already exists in the #GHashTable its current
1584 * value is replaced with the new value. If you supplied a
1585 * @value_destroy_func when creating the #GHashTable, the old
1586 * value is freed using that function. If you supplied a
1587 * @key_destroy_func when creating the #GHashTable, the passed
1588 * key is freed using that function.
1589 *
1590 * Starting from GLib 2.40, this function returns a boolean value to
1591 * indicate whether the newly added value was already in the hash table
1592 * or not.
1593 *
1594 * Returns: %TRUE if the key did not exist yet
1595 */
1596 gboolean
1597 g_hash_table_insert (GHashTable *hash_table,
1598 gpointer key,
1599 gpointer value)
1600 {
1601 return g_hash_table_insert_internal (hash_table, key, value, FALSE);
1602 }
1603
1604 /**
1605 * g_hash_table_replace:
1606 * @hash_table: a #GHashTable
1607 * @key: a key to insert
1608 * @value: the value to associate with the key
1609 *
1610 * Inserts a new key and value into a #GHashTable similar to
1611 * g_hash_table_insert(). The difference is that if the key
1612 * already exists in the #GHashTable, it gets replaced by the
1613 * new key. If you supplied a @value_destroy_func when creating
1614 * the #GHashTable, the old value is freed using that function.
1615 * If you supplied a @key_destroy_func when creating the
1616 * #GHashTable, the old key is freed using that function.
1617 *
1618 * Starting from GLib 2.40, this function returns a boolean value to
1619 * indicate whether the newly added value was already in the hash table
1620 * or not.
1621 *
1622 * Returns: %TRUE if the key did not exist yet
1623 */
1624 gboolean
1625 g_hash_table_replace (GHashTable *hash_table,
1626 gpointer key,
1627 gpointer value)
1628 {
1629 return g_hash_table_insert_internal (hash_table, key, value, TRUE);
1630 }
1631
1632 /**
1633 * g_hash_table_add:
1634 * @hash_table: a #GHashTable
1635 * @key: (transfer full): a key to insert
1636 *
1637 * This is a convenience function for using a #GHashTable as a set. It
1638 * is equivalent to calling g_hash_table_replace() with @key as both the
1639 * key and the value.
1640 *
1641 * In particular, this means that if @key already exists in the hash table, then
1642 * the old copy of @key in the hash table is freed and @key replaces it in the
1643 * table.
1644 *
1645 * When a hash table only ever contains keys that have themselves as the
1646 * corresponding value it is able to be stored more efficiently. See
1647 * the discussion in the section description.
1648 *
1649 * Starting from GLib 2.40, this function returns a boolean value to
1650 * indicate whether the newly added value was already in the hash table
1651 * or not.
1652 *
1653 * Returns: %TRUE if the key did not exist yet
1654 *
1655 * Since: 2.32
1656 */
1657 gboolean
1658 g_hash_table_add (GHashTable *hash_table,
1659 gpointer key)
1660 {
1661 return g_hash_table_insert_internal (hash_table, key, key, TRUE);
1662 }
1663
1664 /**
1665 * g_hash_table_contains:
1666 * @hash_table: a #GHashTable
1667 * @key: a key to check
1668 *
1669 * Checks if @key is in @hash_table.
1670 *
1671 * Returns: %TRUE if @key is in @hash_table, %FALSE otherwise.
1672 *
1673 * Since: 2.32
1674 **/
1675 gboolean
1676 g_hash_table_contains (GHashTable *hash_table,
1677 gconstpointer key)
1678 {
1679 guint node_index;
1680 guint node_hash;
1681
1682 g_return_val_if_fail (hash_table != NULL, FALSE);
1683
1684 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1685
1686 return HASH_IS_REAL (hash_table->hashes[node_index]);
1687 }
1688
1689 /*
1690 * g_hash_table_remove_internal:
1691 * @hash_table: our #GHashTable
1692 * @key: the key to remove
1693 * @notify: %TRUE if the destroy notify handlers are to be called
1694 * Returns: %TRUE if a node was found and removed, else %FALSE
1695 *
1696 * Implements the common logic for the g_hash_table_remove() and
1697 * g_hash_table_steal() functions.
1698 *
1699 * Do a lookup of @key and remove it if it is found, calling the
1700 * destroy notify handlers only if @notify is %TRUE.
1701 */
1702 static gboolean
1703 g_hash_table_remove_internal (GHashTable *hash_table,
1704 gconstpointer key,
1705 gboolean notify)
1706 {
1707 guint node_index;
1708 guint node_hash;
1709
1710 g_return_val_if_fail (hash_table != NULL, FALSE);
1711
1712 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1713
1714 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1715 return FALSE;
1716
1717 g_hash_table_remove_node (hash_table, node_index, notify);
1718 g_hash_table_maybe_resize (hash_table);
1719
1720 #ifndef G_DISABLE_ASSERT
1721 hash_table->version++;
1722 #endif
1723
1724 return TRUE;
1725 }
1726
1727 /**
1728 * g_hash_table_remove:
1729 * @hash_table: a #GHashTable
1730 * @key: the key to remove
1731 *
1732 * Removes a key and its associated value from a #GHashTable.
1733 *
1734 * If the #GHashTable was created using g_hash_table_new_full(), the
1735 * key and value are freed using the supplied destroy functions, otherwise
1736 * you have to make sure that any dynamically allocated values are freed
1737 * yourself.
1738 *
1739 * Returns: %TRUE if the key was found and removed from the #GHashTable
1740 */
1741 gboolean
1742 g_hash_table_remove (GHashTable *hash_table,
1743 gconstpointer key)
1744 {
1745 return g_hash_table_remove_internal (hash_table, key, TRUE);
1746 }
1747
1748 /**
1749 * g_hash_table_steal:
1750 * @hash_table: a #GHashTable
1751 * @key: the key to remove
1752 *
1753 * Removes a key and its associated value from a #GHashTable without
1754 * calling the key and value destroy functions.
1755 *
1756 * Returns: %TRUE if the key was found and removed from the #GHashTable
1757 */
1758 gboolean
1759 g_hash_table_steal (GHashTable *hash_table,
1760 gconstpointer key)
1761 {
1762 return g_hash_table_remove_internal (hash_table, key, FALSE);
1763 }
1764
1765 /**
1766 * g_hash_table_steal_extended:
1767 * @hash_table: a #GHashTable
1768 * @lookup_key: the key to look up
1769 * @stolen_key: (out) (optional) (transfer full): return location for the
1770 * original key
1771 * @stolen_value: (out) (optional) (nullable) (transfer full): return location
1772 * for the value associated with the key
1773 *
1774 * Looks up a key in the #GHashTable, stealing the original key and the
1775 * associated value and returning %TRUE if the key was found. If the key was
1776 * not found, %FALSE is returned.
1777 *
1778 * If found, the stolen key and value are removed from the hash table without
1779 * calling the key and value destroy functions, and ownership is transferred to
1780 * the caller of this method, as with g_hash_table_steal(). That is the case
1781 * regardless whether @stolen_key or @stolen_value output parameters are
1782 * requested.
1783 *
1784 * You can pass %NULL for @lookup_key, provided the hash and equal functions
1785 * of @hash_table are %NULL-safe.
1786 *
1787 * The dictionary implementation optimizes for having all values identical to
1788 * their keys, for example by using g_hash_table_add(). When stealing both the
1789 * key and the value from such a dictionary, the value will be %NULL.
1790 *
1791 * Returns: %TRUE if the key was found in the #GHashTable
1792 * Since: 2.58
1793 */
1794 gboolean
1795 g_hash_table_steal_extended (GHashTable *hash_table,
1796 gconstpointer lookup_key,
1797 gpointer *stolen_key,
1798 gpointer *stolen_value)
1799 {
1800 guint node_index;
1801 guint node_hash;
1802
1803 g_return_val_if_fail (hash_table != NULL, FALSE);
1804
1805 node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1806
1807 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1808 {
1809 if (stolen_key != NULL)
1810 *stolen_key = NULL;
1811 if (stolen_value != NULL)
1812 *stolen_value = NULL;
1813 return FALSE;
1814 }
1815
1816 if (stolen_key != NULL)
1817 {
1818 *stolen_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1819 g_hash_table_assign_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys, NULL);
1820 }
1821
1822 if (stolen_value != NULL)
1823 {
1824 *stolen_value = g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values);
1825 g_hash_table_assign_key_or_value (hash_table->values, node_index, hash_table->have_big_values, NULL);
1826 }
1827
1828 g_hash_table_remove_node (hash_table, node_index, FALSE);
1829 g_hash_table_maybe_resize (hash_table);
1830
1831 #ifndef G_DISABLE_ASSERT
1832 hash_table->version++;
1833 #endif
1834
1835 return TRUE;
1836 }
1837
1838 /**
1839 * g_hash_table_remove_all:
1840 * @hash_table: a #GHashTable
1841 *
1842 * Removes all keys and their associated values from a #GHashTable.
1843 *
1844 * If the #GHashTable was created using g_hash_table_new_full(),
1845 * the keys and values are freed using the supplied destroy functions,
1846 * otherwise you have to make sure that any dynamically allocated
1847 * values are freed yourself.
1848 *
1849 * Since: 2.12
1850 */
1851 void
1852 g_hash_table_remove_all (GHashTable *hash_table)
1853 {
1854 g_return_if_fail (hash_table != NULL);
1855
1856 #ifndef G_DISABLE_ASSERT
1857 if (hash_table->nnodes != 0)
1858 hash_table->version++;
1859 #endif
1860
1861 g_hash_table_remove_all_nodes (hash_table, TRUE, FALSE);
1862 g_hash_table_maybe_resize (hash_table);
1863 }
1864
1865 /**
1866 * g_hash_table_steal_all:
1867 * @hash_table: a #GHashTable
1868 *
1869 * Removes all keys and their associated values from a #GHashTable
1870 * without calling the key and value destroy functions.
1871 *
1872 * Since: 2.12
1873 */
1874 void
1875 g_hash_table_steal_all (GHashTable *hash_table)
1876 {
1877 g_return_if_fail (hash_table != NULL);
1878
1879 #ifndef G_DISABLE_ASSERT
1880 if (hash_table->nnodes != 0)
1881 hash_table->version++;
1882 #endif
1883
1884 g_hash_table_remove_all_nodes (hash_table, FALSE, FALSE);
1885 g_hash_table_maybe_resize (hash_table);
1886 }
1887
1888 /**
1889 * g_hash_table_steal_all_keys: (skip)
1890 * @hash_table: a #GHashTable
1891 *
1892 * Removes all keys and their associated values from a #GHashTable
1893 * without calling the key destroy functions, returning the keys
1894 * as a #GPtrArray with the free func set to the @hash_table key
1895 * destroy function.
1896 *
1897 * Returns: (transfer container): a #GPtrArray containing each key of
1898 * the table. Unref with with g_ptr_array_unref() when done.
1899 *
1900 * Since: 2.76
1901 */
1902 GPtrArray *
1903 g_hash_table_steal_all_keys (GHashTable *hash_table)
1904 {
1905 GPtrArray *array;
1906 GDestroyNotify key_destroy_func;
1907
1908 g_return_val_if_fail (hash_table != NULL, NULL);
1909
1910 array = g_hash_table_get_keys_as_ptr_array (hash_table);
1911
1912 /* Ignore the key destroy notify calls during removal, and use it for the
1913 * array elements instead, but restore it after the hash table has been
1914 * cleared, so that newly added keys will continue using it.
1915 */
1916 key_destroy_func = g_steal_pointer (&hash_table->key_destroy_func);
1917 g_ptr_array_set_free_func (array, key_destroy_func);
1918
1919 g_hash_table_remove_all (hash_table);
1920 hash_table->key_destroy_func = g_steal_pointer (&key_destroy_func);
1921
1922 return array;
1923 }
1924
1925 /**
1926 * g_hash_table_steal_all_values: (skip)
1927 * @hash_table: a #GHashTable
1928 *
1929 * Removes all keys and their associated values from a #GHashTable
1930 * without calling the value destroy functions, returning the values
1931 * as a #GPtrArray with the free func set to the @hash_table value
1932 * destroy function.
1933 *
1934 * Returns: (transfer container): a #GPtrArray containing each value of
1935 * the table. Unref with with g_ptr_array_unref() when done.
1936 *
1937 * Since: 2.76
1938 */
1939 GPtrArray *
1940 g_hash_table_steal_all_values (GHashTable *hash_table)
1941 {
1942 GPtrArray *array;
1943 GDestroyNotify value_destroy_func;
1944
1945 g_return_val_if_fail (hash_table != NULL, NULL);
1946
1947 array = g_hash_table_get_values_as_ptr_array (hash_table);
1948
1949 /* Ignore the value destroy notify calls during removal, and use it for the
1950 * array elements instead, but restore it after the hash table has been
1951 * cleared, so that newly added values will continue using it.
1952 */
1953 value_destroy_func = g_steal_pointer (&hash_table->value_destroy_func);
1954 g_ptr_array_set_free_func (array, value_destroy_func);
1955
1956 g_hash_table_remove_all (hash_table);
1957 hash_table->value_destroy_func = g_steal_pointer (&value_destroy_func);
1958
1959 return array;
1960 }
1961
1962 /*
1963 * g_hash_table_foreach_remove_or_steal:
1964 * @hash_table: a #GHashTable
1965 * @func: the user's callback function
1966 * @user_data: data for @func
1967 * @notify: %TRUE if the destroy notify handlers are to be called
1968 *
1969 * Implements the common logic for g_hash_table_foreach_remove()
1970 * and g_hash_table_foreach_steal().
1971 *
1972 * Iterates over every node in the table, calling @func with the key
1973 * and value of the node (and @user_data). If @func returns %TRUE the
1974 * node is removed from the table.
1975 *
1976 * If @notify is true then the destroy notify handlers will be called
1977 * for each removed node.
1978 */
1979 static guint
1980 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1981 GHRFunc func,
1982 gpointer user_data,
1983 gboolean notify)
1984 {
1985 guint deleted = 0;
1986 gsize i;
1987 #ifndef G_DISABLE_ASSERT
1988 gint version = hash_table->version;
1989 #endif
1990
1991 for (i = 0; i < hash_table->size; i++)
1992 {
1993 guint node_hash = hash_table->hashes[i];
1994 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
1995 gpointer node_value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
1996
1997 if (HASH_IS_REAL (node_hash) &&
1998 (* func) (node_key, node_value, user_data))
1999 {
2000 g_hash_table_remove_node (hash_table, i, notify);
2001 deleted++;
2002 }
2003
2004 #ifndef G_DISABLE_ASSERT
2005 g_return_val_if_fail (version == hash_table->version, 0);
2006 #endif
2007 }
2008
2009 g_hash_table_maybe_resize (hash_table);
2010
2011 #ifndef G_DISABLE_ASSERT
2012 if (deleted > 0)
2013 hash_table->version++;
2014 #endif
2015
2016 return deleted;
2017 }
2018
2019 /**
2020 * g_hash_table_foreach_remove:
2021 * @hash_table: a #GHashTable
2022 * @func: (scope call): the function to call for each key/value pair
2023 * @user_data: user data to pass to the function
2024 *
2025 * Calls the given function for each key/value pair in the
2026 * #GHashTable. If the function returns %TRUE, then the key/value
2027 * pair is removed from the #GHashTable. If you supplied key or
2028 * value destroy functions when creating the #GHashTable, they are
2029 * used to free the memory allocated for the removed keys and values.
2030 *
2031 * See #GHashTableIter for an alternative way to loop over the
2032 * key/value pairs in the hash table.
2033 *
2034 * Returns: the number of key/value pairs removed
2035 */
2036 guint
2037 g_hash_table_foreach_remove (GHashTable *hash_table,
2038 GHRFunc func,
2039 gpointer user_data)
2040 {
2041 g_return_val_if_fail (hash_table != NULL, 0);
2042 g_return_val_if_fail (func != NULL, 0);
2043
2044 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
2045 }
2046
2047 /**
2048 * g_hash_table_foreach_steal:
2049 * @hash_table: a #GHashTable
2050 * @func: (scope call): the function to call for each key/value pair
2051 * @user_data: user data to pass to the function
2052 *
2053 * Calls the given function for each key/value pair in the
2054 * #GHashTable. If the function returns %TRUE, then the key/value
2055 * pair is removed from the #GHashTable, but no key or value
2056 * destroy functions are called.
2057 *
2058 * See #GHashTableIter for an alternative way to loop over the
2059 * key/value pairs in the hash table.
2060 *
2061 * Returns: the number of key/value pairs removed.
2062 */
2063 guint
2064 g_hash_table_foreach_steal (GHashTable *hash_table,
2065 GHRFunc func,
2066 gpointer user_data)
2067 {
2068 g_return_val_if_fail (hash_table != NULL, 0);
2069 g_return_val_if_fail (func != NULL, 0);
2070
2071 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
2072 }
2073
2074 /**
2075 * g_hash_table_foreach:
2076 * @hash_table: a #GHashTable
2077 * @func: (scope call): the function to call for each key/value pair
2078 * @user_data: user data to pass to the function
2079 *
2080 * Calls the given function for each of the key/value pairs in the
2081 * #GHashTable. The function is passed the key and value of each
2082 * pair, and the given @user_data parameter. The hash table may not
2083 * be modified while iterating over it (you can't add/remove
2084 * items). To remove all items matching a predicate, use
2085 * g_hash_table_foreach_remove().
2086 *
2087 * The order in which g_hash_table_foreach() iterates over the keys/values in
2088 * the hash table is not defined.
2089 *
2090 * See g_hash_table_find() for performance caveats for linear
2091 * order searches in contrast to g_hash_table_lookup().
2092 */
2093 void
2094 g_hash_table_foreach (GHashTable *hash_table,
2095 GHFunc func,
2096 gpointer user_data)
2097 {
2098 gsize i;
2099 #ifndef G_DISABLE_ASSERT
2100 gint version;
2101 #endif
2102
2103 g_return_if_fail (hash_table != NULL);
2104 g_return_if_fail (func != NULL);
2105
2106 #ifndef G_DISABLE_ASSERT
2107 version = hash_table->version;
2108 #endif
2109
2110 for (i = 0; i < hash_table->size; i++)
2111 {
2112 guint node_hash = hash_table->hashes[i];
2113 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
2114 gpointer node_value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
2115
2116 if (HASH_IS_REAL (node_hash))
2117 (* func) (node_key, node_value, user_data);
2118
2119 #ifndef G_DISABLE_ASSERT
2120 g_return_if_fail (version == hash_table->version);
2121 #endif
2122 }
2123 }
2124
2125 /**
2126 * g_hash_table_find:
2127 * @hash_table: a #GHashTable
2128 * @predicate: (scope call): function to test the key/value pairs for a certain property
2129 * @user_data: user data to pass to the function
2130 *
2131 * Calls the given function for key/value pairs in the #GHashTable
2132 * until @predicate returns %TRUE. The function is passed the key
2133 * and value of each pair, and the given @user_data parameter. The
2134 * hash table may not be modified while iterating over it (you can't
2135 * add/remove items).
2136 *
2137 * Note, that hash tables are really only optimized for forward
2138 * lookups, i.e. g_hash_table_lookup(). So code that frequently issues
2139 * g_hash_table_find() or g_hash_table_foreach() (e.g. in the order of
2140 * once per every entry in a hash table) should probably be reworked
2141 * to use additional or different data structures for reverse lookups
2142 * (keep in mind that an O(n) find/foreach operation issued for all n
2143 * values in a hash table ends up needing O(n*n) operations).
2144 *
2145 * Returns: (nullable): The value of the first key/value pair is returned,
2146 * for which @predicate evaluates to %TRUE. If no pair with the
2147 * requested property is found, %NULL is returned.
2148 *
2149 * Since: 2.4
2150 */
2151 gpointer
2152 g_hash_table_find (GHashTable *hash_table,
2153 GHRFunc predicate,
2154 gpointer user_data)
2155 {
2156 gsize i;
2157 #ifndef G_DISABLE_ASSERT
2158 gint version;
2159 #endif
2160 gboolean match;
2161
2162 g_return_val_if_fail (hash_table != NULL, NULL);
2163 g_return_val_if_fail (predicate != NULL, NULL);
2164
2165 #ifndef G_DISABLE_ASSERT
2166 version = hash_table->version;
2167 #endif
2168
2169 match = FALSE;
2170
2171 for (i = 0; i < hash_table->size; i++)
2172 {
2173 guint node_hash = hash_table->hashes[i];
2174 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
2175 gpointer node_value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
2176
2177 if (HASH_IS_REAL (node_hash))
2178 match = predicate (node_key, node_value, user_data);
2179
2180 #ifndef G_DISABLE_ASSERT
2181 g_return_val_if_fail (version == hash_table->version, NULL);
2182 #endif
2183
2184 if (match)
2185 return node_value;
2186 }
2187
2188 return NULL;
2189 }
2190
2191 /**
2192 * g_hash_table_size:
2193 * @hash_table: a #GHashTable
2194 *
2195 * Returns the number of elements contained in the #GHashTable.
2196 *
2197 * Returns: the number of key/value pairs in the #GHashTable.
2198 */
2199 guint
2200 g_hash_table_size (GHashTable *hash_table)
2201 {
2202 g_return_val_if_fail (hash_table != NULL, 0);
2203
2204 return hash_table->nnodes;
2205 }
2206
2207 /**
2208 * g_hash_table_get_keys:
2209 * @hash_table: a #GHashTable
2210 *
2211 * Retrieves every key inside @hash_table. The returned data is valid
2212 * until changes to the hash release those keys.
2213 *
2214 * This iterates over every entry in the hash table to build its return value.
2215 * To iterate over the entries in a #GHashTable more efficiently, use a
2216 * #GHashTableIter.
2217 *
2218 * Returns: (transfer container): a #GList containing all the keys
2219 * inside the hash table. The content of the list is owned by the
2220 * hash table and should not be modified or freed. Use g_list_free()
2221 * when done using the list.
2222 *
2223 * Since: 2.14
2224 */
2225 GList *
2226 g_hash_table_get_keys (GHashTable *hash_table)
2227 {
2228 gsize i;
2229 GList *retval;
2230
2231 g_return_val_if_fail (hash_table != NULL, NULL);
2232
2233 retval = NULL;
2234 for (i = 0; i < hash_table->size; i++)
2235 {
2236 if (HASH_IS_REAL (hash_table->hashes[i]))
2237 retval = g_list_prepend (retval, g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys));
2238 }
2239
2240 return retval;
2241 }
2242
2243 /**
2244 * g_hash_table_get_keys_as_array:
2245 * @hash_table: a #GHashTable
2246 * @length: (out) (optional): the length of the returned array
2247 *
2248 * Retrieves every key inside @hash_table, as an array.
2249 *
2250 * The returned array is %NULL-terminated but may contain %NULL as a
2251 * key. Use @length to determine the true length if it's possible that
2252 * %NULL was used as the value for a key.
2253 *
2254 * Note: in the common case of a string-keyed #GHashTable, the return
2255 * value of this function can be conveniently cast to (const gchar **).
2256 *
2257 * This iterates over every entry in the hash table to build its return value.
2258 * To iterate over the entries in a #GHashTable more efficiently, use a
2259 * #GHashTableIter.
2260 *
2261 * You should always free the return result with g_free(). In the
2262 * above-mentioned case of a string-keyed hash table, it may be
2263 * appropriate to use g_strfreev() if you call g_hash_table_steal_all()
2264 * first to transfer ownership of the keys.
2265 *
2266 * Returns: (array length=length) (transfer container): a
2267 * %NULL-terminated array containing each key from the table.
2268 *
2269 * Since: 2.40
2270 **/
2271 gpointer *
2272 g_hash_table_get_keys_as_array (GHashTable *hash_table,
2273 guint *length)
2274 {
2275 gpointer *result;
2276 gsize i, j = 0;
2277
2278 result = g_new (gpointer, hash_table->nnodes + 1);
2279 for (i = 0; i < hash_table->size; i++)
2280 {
2281 if (HASH_IS_REAL (hash_table->hashes[i]))
2282 result[j++] = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
2283 }
2284 g_assert (j == hash_table->nnodes);
2285 result[j] = NULL;
2286
2287 if (length)
2288 *length = j;
2289
2290 return result;
2291 }
2292
2293 /**
2294 * g_hash_table_get_keys_as_ptr_array: (skip)
2295 * @hash_table: a #GHashTable
2296 *
2297 * Retrieves every key inside @hash_table, as a #GPtrArray.
2298 * The returned data is valid until changes to the hash release those keys.
2299 *
2300 * This iterates over every entry in the hash table to build its return value.
2301 * To iterate over the entries in a #GHashTable more efficiently, use a
2302 * #GHashTableIter.
2303 *
2304 * You should always unref the returned array with g_ptr_array_unref().
2305 *
2306 * Returns: (transfer container): a #GPtrArray containing each key from
2307 * the table. Unref with with g_ptr_array_unref() when done.
2308 *
2309 * Since: 2.76
2310 **/
2311 GPtrArray *
2312 g_hash_table_get_keys_as_ptr_array (GHashTable *hash_table)
2313 {
2314 GPtrArray *array;
2315
2316 g_return_val_if_fail (hash_table != NULL, NULL);
2317
2318 array = g_ptr_array_sized_new (hash_table->size);
2319 for (gsize i = 0; i < hash_table->size; ++i)
2320 {
2321 if (HASH_IS_REAL (hash_table->hashes[i]))
2322 {
2323 g_ptr_array_add (array, g_hash_table_fetch_key_or_value (
2324 hash_table->keys, i, hash_table->have_big_keys));
2325 }
2326 }
2327 g_assert (array->len == hash_table->nnodes);
2328
2329 return array;
2330 }
2331
2332 /**
2333 * g_hash_table_get_values:
2334 * @hash_table: a #GHashTable
2335 *
2336 * Retrieves every value inside @hash_table. The returned data
2337 * is valid until @hash_table is modified.
2338 *
2339 * This iterates over every entry in the hash table to build its return value.
2340 * To iterate over the entries in a #GHashTable more efficiently, use a
2341 * #GHashTableIter.
2342 *
2343 * Returns: (transfer container): a #GList containing all the values
2344 * inside the hash table. The content of the list is owned by the
2345 * hash table and should not be modified or freed. Use g_list_free()
2346 * when done using the list.
2347 *
2348 * Since: 2.14
2349 */
2350 GList *
2351 g_hash_table_get_values (GHashTable *hash_table)
2352 {
2353 gsize i;
2354 GList *retval;
2355
2356 g_return_val_if_fail (hash_table != NULL, NULL);
2357
2358 retval = NULL;
2359 for (i = 0; i < hash_table->size; i++)
2360 {
2361 if (HASH_IS_REAL (hash_table->hashes[i]))
2362 retval = g_list_prepend (retval, g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values));
2363 }
2364
2365 return retval;
2366 }
2367
2368 /**
2369 * g_hash_table_get_values_as_ptr_array: (skip)
2370 * @hash_table: a #GHashTable
2371 *
2372 * Retrieves every value inside @hash_table, as a #GPtrArray.
2373 * The returned data is valid until changes to the hash release those values.
2374 *
2375 * This iterates over every entry in the hash table to build its return value.
2376 * To iterate over the entries in a #GHashTable more efficiently, use a
2377 * #GHashTableIter.
2378 *
2379 * You should always unref the returned array with g_ptr_array_unref().
2380 *
2381 * Returns: (transfer container): a #GPtrArray containing each value from
2382 * the table. Unref with with g_ptr_array_unref() when done.
2383 *
2384 * Since: 2.76
2385 **/
2386 GPtrArray *
2387 g_hash_table_get_values_as_ptr_array (GHashTable *hash_table)
2388 {
2389 GPtrArray *array;
2390
2391 g_return_val_if_fail (hash_table != NULL, NULL);
2392
2393 array = g_ptr_array_sized_new (hash_table->size);
2394 for (gsize i = 0; i < hash_table->size; ++i)
2395 {
2396 if (HASH_IS_REAL (hash_table->hashes[i]))
2397 {
2398 g_ptr_array_add (array, g_hash_table_fetch_key_or_value (
2399 hash_table->values, i, hash_table->have_big_values));
2400 }
2401 }
2402 g_assert (array->len == hash_table->nnodes);
2403
2404 return array;
2405 }
2406
2407 /* Hash functions.
2408 */
2409
2410 /**
2411 * g_str_equal:
2412 * @v1: (not nullable): a key
2413 * @v2: (not nullable): a key to compare with @v1
2414 *
2415 * Compares two strings for byte-by-byte equality and returns %TRUE
2416 * if they are equal. It can be passed to g_hash_table_new() as the
2417 * @key_equal_func parameter, when using non-%NULL strings as keys in a
2418 * #GHashTable.
2419 *
2420 * This function is typically used for hash table comparisons, but can be used
2421 * for general purpose comparisons of non-%NULL strings. For a %NULL-safe string
2422 * comparison function, see g_strcmp0().
2423 *
2424 * Returns: %TRUE if the two keys match
2425 */
2426 gboolean
2427 (g_str_equal) (gconstpointer v1,
2428 gconstpointer v2)
2429 {
2430 const gchar *string1 = v1;
2431 const gchar *string2 = v2;
2432
2433 return strcmp (string1, string2) == 0;
2434 }
2435
2436 /**
2437 * g_str_hash:
2438 * @v: (not nullable): a string key
2439 *
2440 * Converts a string to a hash value.
2441 *
2442 * This function implements the widely used "djb" hash apparently
2443 * posted by Daniel Bernstein to comp.lang.c some time ago. The 32
2444 * bit unsigned hash value starts at 5381 and for each byte 'c' in
2445 * the string, is updated: `hash = hash * 33 + c`. This function
2446 * uses the signed value of each byte.
2447 *
2448 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2449 * when using non-%NULL strings as keys in a #GHashTable.
2450 *
2451 * Note that this function may not be a perfect fit for all use cases.
2452 * For example, it produces some hash collisions with strings as short
2453 * as 2.
2454 *
2455 * Returns: a hash value corresponding to the key
2456 */
2457 guint
2458 g_str_hash (gconstpointer v)
2459 {
2460 const signed char *p;
2461 guint32 h = 5381;
2462
2463 for (p = v; *p != '\0'; p++)
2464 h = (h << 5) + h + *p;
2465
2466 return h;
2467 }
2468
2469 /**
2470 * g_direct_hash:
2471 * @v: (nullable): a #gpointer key
2472 *
2473 * Converts a gpointer to a hash value.
2474 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2475 * when using opaque pointers compared by pointer value as keys in a
2476 * #GHashTable.
2477 *
2478 * This hash function is also appropriate for keys that are integers
2479 * stored in pointers, such as `GINT_TO_POINTER (n)`.
2480 *
2481 * Returns: a hash value corresponding to the key.
2482 */
2483 guint
2484 g_direct_hash (gconstpointer v)
2485 {
2486 return GPOINTER_TO_UINT (v);
2487 }
2488
2489 /**
2490 * g_direct_equal:
2491 * @v1: (nullable): a key
2492 * @v2: (nullable): a key to compare with @v1
2493 *
2494 * Compares two #gpointer arguments and returns %TRUE if they are equal.
2495 * It can be passed to g_hash_table_new() as the @key_equal_func
2496 * parameter, when using opaque pointers compared by pointer value as
2497 * keys in a #GHashTable.
2498 *
2499 * This equality function is also appropriate for keys that are integers
2500 * stored in pointers, such as `GINT_TO_POINTER (n)`.
2501 *
2502 * Returns: %TRUE if the two keys match.
2503 */
2504 gboolean
2505 g_direct_equal (gconstpointer v1,
2506 gconstpointer v2)
2507 {
2508 return v1 == v2;
2509 }
2510
2511 /**
2512 * g_int_equal:
2513 * @v1: (not nullable): a pointer to a #gint key
2514 * @v2: (not nullable): a pointer to a #gint key to compare with @v1
2515 *
2516 * Compares the two #gint values being pointed to and returns
2517 * %TRUE if they are equal.
2518 * It can be passed to g_hash_table_new() as the @key_equal_func
2519 * parameter, when using non-%NULL pointers to integers as keys in a
2520 * #GHashTable.
2521 *
2522 * Note that this function acts on pointers to #gint, not on #gint
2523 * directly: if your hash table's keys are of the form
2524 * `GINT_TO_POINTER (n)`, use g_direct_equal() instead.
2525 *
2526 * Returns: %TRUE if the two keys match.
2527 */
2528 gboolean
2529 g_int_equal (gconstpointer v1,
2530 gconstpointer v2)
2531 {
2532 return *((const gint*) v1) == *((const gint*) v2);
2533 }
2534
2535 /**
2536 * g_int_hash:
2537 * @v: (not nullable): a pointer to a #gint key
2538 *
2539 * Converts a pointer to a #gint to a hash value.
2540 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2541 * when using non-%NULL pointers to integer values as keys in a #GHashTable.
2542 *
2543 * Note that this function acts on pointers to #gint, not on #gint
2544 * directly: if your hash table's keys are of the form
2545 * `GINT_TO_POINTER (n)`, use g_direct_hash() instead.
2546 *
2547 * Returns: a hash value corresponding to the key.
2548 */
2549 guint
2550 g_int_hash (gconstpointer v)
2551 {
2552 return *(const gint*) v;
2553 }
2554
2555 /**
2556 * g_uint_equal:
2557 * @v1: (not nullable): a pointer to a #guint key
2558 * @v2: (not nullable): a pointer to a #guint key to compare with @v1
2559 *
2560 * Compares the two #guint values being pointed to and returns
2561 * %TRUE if they are equal.
2562 * It can be passed to g_hash_table_new() as the @key_equal_func
2563 * parameter, when using non-%NULL pointers to integers as keys in a
2564 * #GHashTable.
2565 *
2566 * Note that this function acts on pointers to #guint, not on #guint
2567 * directly: if your hash table's keys are of the form
2568 * `GUINT_TO_POINTER (n)`, use g_direct_equal() instead.
2569 *
2570 * Returns: %TRUE if the two keys match.
2571 */
2572 gboolean
2573 g_uint_equal (gconstpointer v1,
2574 gconstpointer v2)
2575 {
2576 return *((const guint *) v1) == *((const guint *) v2);
2577 }
2578
2579 /**
2580 * g_uint_hash:
2581 * @v: (not nullable): a pointer to a #guint key
2582 *
2583 * Converts a pointer to a #guint to a hash value.
2584 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2585 * when using non-%NULL pointers to integer values as keys in a #GHashTable.
2586 *
2587 * Note that this function acts on pointers to #guint, not on #guint
2588 * directly: if your hash table's keys are of the form
2589 * `GUINT_TO_POINTER (n)`, use g_direct_hash() instead.
2590 *
2591 * Returns: a hash value corresponding to the key.
2592 */
2593 guint
2594 g_uint_hash (gconstpointer v)
2595 {
2596 return *(const guint *) v;
2597 }
2598
2599 /**
2600 * g_int64_equal:
2601 * @v1: (not nullable): a pointer to a #gint64 key
2602 * @v2: (not nullable): a pointer to a #gint64 key to compare with @v1
2603 *
2604 * Compares the two #gint64 values being pointed to and returns
2605 * %TRUE if they are equal.
2606 * It can be passed to g_hash_table_new() as the @key_equal_func
2607 * parameter, when using non-%NULL pointers to 64-bit integers as keys in a
2608 * #GHashTable.
2609 *
2610 * Returns: %TRUE if the two keys match.
2611 *
2612 * Since: 2.22
2613 */
2614 gboolean
2615 g_int64_equal (gconstpointer v1,
2616 gconstpointer v2)
2617 {
2618 return *((const gint64*) v1) == *((const gint64*) v2);
2619 }
2620
2621 /**
2622 * g_int64_hash:
2623 * @v: (not nullable): a pointer to a #gint64 key
2624 *
2625 * Converts a pointer to a #gint64 to a hash value.
2626 *
2627 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2628 * when using non-%NULL pointers to 64-bit integer values as keys in a
2629 * #GHashTable.
2630 *
2631 * Returns: a hash value corresponding to the key.
2632 *
2633 * Since: 2.22
2634 */
2635 guint
2636 g_int64_hash (gconstpointer v)
2637 {
2638 const guint64 *bits = v;
2639
2640 return (guint) ((*bits >> 32) ^ (*bits & 0xffffffffU));
2641 }
2642
2643 /**
2644 * g_double_equal:
2645 * @v1: (not nullable): a pointer to a #gdouble key
2646 * @v2: (not nullable): a pointer to a #gdouble key to compare with @v1
2647 *
2648 * Compares the two #gdouble values being pointed to and returns
2649 * %TRUE if they are equal.
2650 * It can be passed to g_hash_table_new() as the @key_equal_func
2651 * parameter, when using non-%NULL pointers to doubles as keys in a
2652 * #GHashTable.
2653 *
2654 * Returns: %TRUE if the two keys match.
2655 *
2656 * Since: 2.22
2657 */
2658 gboolean
2659 g_double_equal (gconstpointer v1,
2660 gconstpointer v2)
2661 {
2662 return *((const gdouble*) v1) == *((const gdouble*) v2);
2663 }
2664
2665 /**
2666 * g_double_hash:
2667 * @v: (not nullable): a pointer to a #gdouble key
2668 *
2669 * Converts a pointer to a #gdouble to a hash value.
2670 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2671 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2672 * when using non-%NULL pointers to doubles as keys in a #GHashTable.
2673 *
2674 * Returns: a hash value corresponding to the key.
2675 *
2676 * Since: 2.22
2677 */
2678 guint
2679 g_double_hash (gconstpointer v)
2680 {
2681 /* Same as g_int64_hash() */
2682 const guint64 *bits = v;
2683
2684 return (guint) ((*bits >> 32) ^ (*bits & 0xffffffffU));
2685 }