1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * SPDX-License-Identifier: LGPL-2.1-or-later
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.
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.
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/>.
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/.
33 #include <string.h> /* memset */
37 #include "glib-private.h"
38 #include "gstrfuncs.h"
40 #include "gtestutils.h"
42 #include "grefcount.h"
43 #include "gvalgrind.h"
45 /* The following #pragma is here so we can do this...
47 * #ifndef USE_SMALL_ARRAYS
50 * return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
52 * ...instead of this...
54 * #ifndef USE_SMALL_ARRAYS
55 * return *(((gpointer *) a) + index);
57 * return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
60 * ...and still compile successfully when -Werror=duplicated-branches is passed. */
62 #if defined(__GNUC__) && __GNUC__ > 6
63 #pragma GCC diagnostic ignored "-Wduplicated-branches"
69 * @short_description: associations between keys and values so that
70 * given a key the value can be found quickly
72 * A #GHashTable provides associations between keys and values which is
73 * optimized so that given a key, the associated value can be found,
74 * inserted or removed in amortized O(1). All operations going through
75 * each element take O(n) time (list all keys/values, table resize, etc.).
77 * Note that neither keys nor values are copied when inserted into the
78 * #GHashTable, so they must exist for the lifetime of the #GHashTable.
79 * This means that the use of static strings is OK, but temporary
80 * strings (i.e. those created in buffers and those returned by GTK
81 * widgets) should be copied with g_strdup() before being inserted.
83 * If keys or values are dynamically allocated, you must be careful to
84 * ensure that they are freed when they are removed from the
85 * #GHashTable, and also when they are overwritten by new insertions
86 * into the #GHashTable. It is also not advisable to mix static strings
87 * and dynamically-allocated strings in a #GHashTable, because it then
88 * becomes difficult to determine whether the string should be freed.
90 * To create a #GHashTable, use g_hash_table_new().
92 * To insert a key and value into a #GHashTable, use
93 * g_hash_table_insert().
95 * To look up a value corresponding to a given key, use
96 * g_hash_table_lookup() and g_hash_table_lookup_extended().
98 * g_hash_table_lookup_extended() can also be used to simply
99 * check if a key is present in the hash table.
101 * To remove a key and value, use g_hash_table_remove().
103 * To call a function for each key and value pair use
104 * g_hash_table_foreach() or use an iterator to iterate over the
105 * key/value pairs in the hash table, see #GHashTableIter. The iteration order
106 * of a hash table is not defined, and you must not rely on iterating over
107 * keys/values in the same order as they were inserted.
109 * To destroy a #GHashTable use g_hash_table_destroy().
111 * A common use-case for hash tables is to store information about a
112 * set of keys, without associating any particular value with each
113 * key. GHashTable optimizes one way of doing so: If you store only
114 * key-value pairs where key == value, then GHashTable does not
115 * allocate memory to store the values, which can be a considerable
116 * space saving, if your set is large. The functions
117 * g_hash_table_add() and g_hash_table_contains() are designed to be
118 * used when using #GHashTable this way.
120 * #GHashTable is not designed to be statically initialised with keys and
121 * values known at compile time. To build a static hash table, use a tool such
122 * as [gperf](https://www.gnu.org/software/gperf/).
128 * The #GHashTable struct is an opaque data structure to represent a
129 * [Hash Table][glib-Hash-Tables]. It should only be accessed via the
130 * following functions.
137 * Specifies the type of the hash function which is passed to
138 * g_hash_table_new() when a #GHashTable is created.
140 * The function is passed a key and should return a #guint hash value.
141 * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
142 * hash functions which can be used when the key is a #gpointer, #gint*,
143 * and #gchar* respectively.
145 * g_direct_hash() is also the appropriate hash function for keys
146 * of the form `GINT_TO_POINTER (n)` (or similar macros).
148 * A good hash functions should produce
149 * hash values that are evenly distributed over a fairly large range.
150 * The modulus is taken with the hash table size (a prime number) to
151 * find the 'bucket' to place each key into. The function should also
152 * be very fast, since it is called for each key lookup.
154 * Note that the hash functions provided by GLib have these qualities,
155 * but are not particularly robust against manufactured keys that
156 * cause hash collisions. Therefore, you should consider choosing
157 * a more secure hash function when using a GHashTable with keys
158 * that originate in untrusted data (such as HTTP requests).
159 * Using g_str_hash() in that situation might make your application
161 * [Algorithmic Complexity Attacks](https://lwn.net/Articles/474912/).
163 * The key to choosing a good hash is unpredictability. Even
164 * cryptographic hashes are very easy to find collisions for when the
165 * remainder is taken modulo a somewhat predictable prime number. There
166 * must be an element of randomness that an attacker is unable to guess.
168 * Returns: the hash value corresponding to the key
174 * @value: the value corresponding to the key
175 * @user_data: user data passed to g_hash_table_foreach()
177 * Specifies the type of the function passed to g_hash_table_foreach().
178 * It is called with each key/value pair, together with the @user_data
179 * parameter which is passed to g_hash_table_foreach().
185 * @value: the value associated with the key
186 * @user_data: user data passed to g_hash_table_remove()
188 * Specifies the type of the function passed to
189 * g_hash_table_foreach_remove(). It is called with each key/value
190 * pair, together with the @user_data parameter passed to
191 * g_hash_table_foreach_remove(). It should return %TRUE if the
192 * key/value pair should be removed from the #GHashTable.
194 * Returns: %TRUE if the key/value pair should be removed from the
201 * @b: a value to compare with
203 * Specifies the type of a function used to test two values for
204 * equality. The function should return %TRUE if both values are equal
205 * and %FALSE otherwise.
207 * Returns: %TRUE if @a = @b; %FALSE otherwise
213 * A GHashTableIter structure represents an iterator that can be used
214 * to iterate over the elements of a #GHashTable. GHashTableIter
215 * structures are typically allocated on the stack and then initialized
216 * with g_hash_table_iter_init().
218 * The iteration order of a #GHashTableIter over the keys/values in a hash
219 * table is not defined.
223 * g_hash_table_freeze:
224 * @hash_table: a #GHashTable
226 * This function is deprecated and will be removed in the next major
227 * release of GLib. It does nothing.
232 * @hash_table: a #GHashTable
234 * This function is deprecated and will be removed in the next major
235 * release of GLib. It does nothing.
238 #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */
240 #define UNUSED_HASH_VALUE 0
241 #define TOMBSTONE_HASH_VALUE 1
242 #define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
243 #define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
244 #define HASH_IS_REAL(h_) ((h_) >= 2)
246 /* If int is smaller than void * on our arch, we start out with
247 * int-sized keys and values and resize to pointer-sized entries as
248 * needed. This saves a good amount of memory when the HT is being
249 * used with e.g. GUINT_TO_POINTER(). */
251 #define BIG_ENTRY_SIZE (SIZEOF_VOID_P)
252 #define SMALL_ENTRY_SIZE (SIZEOF_INT)
254 #if SMALL_ENTRY_SIZE < BIG_ENTRY_SIZE
255 # define USE_SMALL_ARRAYS
264 gint noccupied; /* nnodes + tombstones */
266 guint have_big_keys : 1;
267 guint have_big_values : 1;
274 GEqualFunc key_equal_func;
275 gatomicrefcount ref_count;
276 #ifndef G_DISABLE_ASSERT
278 * Tracks the structure of the hash table, not its contents: is only
279 * incremented when a node is added or removed (is not incremented
280 * when the key or data of a node is modified).
284 GDestroyNotify key_destroy_func;
285 GDestroyNotify value_destroy_func;
290 GHashTable *hash_table;
298 G_STATIC_ASSERT (sizeof (GHashTableIter) == sizeof (RealIter));
299 G_STATIC_ASSERT (G_ALIGNOF (GHashTableIter) >= G_ALIGNOF (RealIter));
301 /* Each table size has an associated prime modulo (the first prime
302 * lower than the table size) used to find the initial bucket. Probing
303 * then works modulo 2^n. The prime modulo is necessary to get a
304 * good distribution with poor hash functions.
306 static const gint prime_mod [] =
324 65521, /* For 1 << 16 */
339 2147483647 /* For 1 << 31 */
343 g_hash_table_set_shift (GHashTable *hash_table, gint shift)
345 hash_table->size = 1 << shift;
346 hash_table->mod = prime_mod [shift];
348 /* hash_table->size is always a power of two, so we can calculate the mask
349 * by simply subtracting 1 from it. The leading assertion ensures that
350 * we're really dealing with a power of two. */
352 g_assert ((hash_table->size & (hash_table->size - 1)) == 0);
353 hash_table->mask = hash_table->size - 1;
357 g_hash_table_find_closest_shift (gint n)
368 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
372 shift = g_hash_table_find_closest_shift (size);
373 shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
375 g_hash_table_set_shift (hash_table, shift);
378 static inline gpointer
379 g_hash_table_realloc_key_or_value_array (gpointer a, guint size, G_GNUC_UNUSED gboolean is_big)
381 #ifdef USE_SMALL_ARRAYS
382 return g_realloc (a, size * (is_big ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE));
384 return g_renew (gpointer, a, size);
388 static inline gpointer
389 g_hash_table_fetch_key_or_value (gpointer a, guint index, gboolean is_big)
391 #ifndef USE_SMALL_ARRAYS
394 return is_big ? *(((gpointer *) a) + index) : GUINT_TO_POINTER (*(((guint *) a) + index));
398 g_hash_table_assign_key_or_value (gpointer a, guint index, gboolean is_big, gpointer v)
400 #ifndef USE_SMALL_ARRAYS
404 *(((gpointer *) a) + index) = v;
406 *(((guint *) a) + index) = GPOINTER_TO_UINT (v);
409 static inline gpointer
410 g_hash_table_evict_key_or_value (gpointer a, guint index, gboolean is_big, gpointer v)
412 #ifndef USE_SMALL_ARRAYS
417 gpointer r = *(((gpointer *) a) + index);
418 *(((gpointer *) a) + index) = v;
423 gpointer r = GUINT_TO_POINTER (*(((guint *) a) + index));
424 *(((guint *) a) + index) = GPOINTER_TO_UINT (v);
430 g_hash_table_hash_to_index (GHashTable *hash_table, guint hash)
432 /* Multiply the hash by a small prime before applying the modulo. This
433 * prevents the table from becoming densely packed, even with a poor hash
434 * function. A densely packed table would have poor performance on
435 * workloads with many failed lookups or a high degree of churn. */
436 return (hash * 11) % hash_table->mod;
440 * g_hash_table_lookup_node:
441 * @hash_table: our #GHashTable
442 * @key: the key to look up against
443 * @hash_return: key hash return location
445 * Performs a lookup in the hash table, preserving extra information
446 * usually needed for insertion.
448 * This function first computes the hash value of the key using the
449 * user's hash function.
451 * If an entry in the table matching @key is found then this function
452 * returns the index of that entry in the table, and if not, the
453 * index of an unused node (empty or tombstone) where the key can be
456 * The computed hash value is returned in the variable pointed to
457 * by @hash_return. This is to save insertions from having to compute
458 * the hash record again for the new record.
460 * Returns: index of the described node
463 g_hash_table_lookup_node (GHashTable *hash_table,
470 guint first_tombstone = 0;
471 gboolean have_tombstone = FALSE;
474 hash_value = hash_table->hash_func (key);
475 if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
478 *hash_return = hash_value;
480 node_index = g_hash_table_hash_to_index (hash_table, hash_value);
481 node_hash = hash_table->hashes[node_index];
483 while (!HASH_IS_UNUSED (node_hash))
485 /* We first check if our full hash values
486 * are equal so we can avoid calling the full-blown
487 * key equality function in most cases.
489 if (node_hash == hash_value)
491 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
493 if (hash_table->key_equal_func)
495 if (hash_table->key_equal_func (node_key, key))
498 else if (node_key == key)
503 else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
505 first_tombstone = node_index;
506 have_tombstone = TRUE;
511 node_index &= hash_table->mask;
512 node_hash = hash_table->hashes[node_index];
516 return first_tombstone;
522 * g_hash_table_remove_node:
523 * @hash_table: our #GHashTable
524 * @node: pointer to node to remove
525 * @notify: %TRUE if the destroy notify handlers are to be called
527 * Removes a node from the hash table and updates the node count.
528 * The node is replaced by a tombstone. No table resize is performed.
530 * If @notify is %TRUE then the destroy notify functions are called
531 * for the key and value of the hash node.
534 g_hash_table_remove_node (GHashTable *hash_table,
541 key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
542 value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
544 /* Erect tombstone */
545 hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;
548 g_hash_table_assign_key_or_value (hash_table->keys, i, hash_table->have_big_keys, NULL);
549 g_hash_table_assign_key_or_value (hash_table->values, i, hash_table->have_big_values, NULL);
551 hash_table->nnodes--;
553 if (notify && hash_table->key_destroy_func)
554 hash_table->key_destroy_func (key);
556 if (notify && hash_table->value_destroy_func)
557 hash_table->value_destroy_func (value);
562 * g_hash_table_setup_storage:
563 * @hash_table: our #GHashTable
565 * Initialise the hash table size, mask, mod, and arrays.
568 g_hash_table_setup_storage (GHashTable *hash_table)
570 gboolean small = FALSE;
572 /* We want to use small arrays only if:
573 * - we are running on a system where that makes sense (64 bit); and
574 * - we are not running under valgrind.
577 #ifdef USE_SMALL_ARRAYS
580 # ifdef ENABLE_VALGRIND
581 if (RUNNING_ON_VALGRIND)
586 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
588 hash_table->have_big_keys = !small;
589 hash_table->have_big_values = !small;
591 hash_table->keys = g_hash_table_realloc_key_or_value_array (NULL, hash_table->size, hash_table->have_big_keys);
592 hash_table->values = hash_table->keys;
593 hash_table->hashes = g_new0 (guint, hash_table->size);
597 * g_hash_table_remove_all_nodes:
598 * @hash_table: our #GHashTable
599 * @notify: %TRUE if the destroy notify handlers are to be called
601 * Removes all nodes from the table.
603 * If @notify is %TRUE then the destroy notify functions are called
604 * for the key and value of the hash node.
606 * Since this may be a precursor to freeing the table entirely, we'd
607 * ideally perform no resize, and we can indeed avoid that in some
608 * cases. However: in the case that we'll be making callbacks to user
609 * code (via destroy notifies) we need to consider that the user code
610 * might call back into the table again. In this case, we setup a new
611 * set of arrays so that any callers will see an empty (but valid)
615 g_hash_table_remove_all_nodes (GHashTable *hash_table,
617 gboolean destruction)
624 gpointer *old_values;
626 gboolean old_have_big_keys;
627 gboolean old_have_big_values;
629 /* If the hash table is already empty, there is nothing to be done. */
630 if (hash_table->nnodes == 0)
633 hash_table->nnodes = 0;
634 hash_table->noccupied = 0;
636 /* Easy case: no callbacks, so we just zero out the arrays */
638 (hash_table->key_destroy_func == NULL &&
639 hash_table->value_destroy_func == NULL))
643 memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
645 #ifdef USE_SMALL_ARRAYS
646 memset (hash_table->keys, 0, hash_table->size * (hash_table->have_big_keys ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE));
647 memset (hash_table->values, 0, hash_table->size * (hash_table->have_big_values ? BIG_ENTRY_SIZE : SMALL_ENTRY_SIZE));
649 memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
650 memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
657 /* Hard case: we need to do user callbacks. There are two
658 * possibilities here:
660 * 1) there are no outstanding references on the table and therefore
661 * nobody should be calling into it again (destroying == true)
663 * 2) there are outstanding references, and there may be future
664 * calls into the table, either after we return, or from the destroy
665 * notifies that we're about to do (destroying == false)
667 * We handle both cases by taking the current state of the table into
668 * local variables and replacing it with something else: in the "no
669 * outstanding references" cases we replace it with a bunch of
670 * null/zero values so that any access to the table will fail. In the
671 * "may receive future calls" case, we reinitialise the struct to
672 * appear like a newly-created empty table.
674 * In both cases, we take over the references for the current state,
675 * freeing them below.
677 old_size = hash_table->size;
678 old_have_big_keys = hash_table->have_big_keys;
679 old_have_big_values = hash_table->have_big_values;
680 old_keys = g_steal_pointer (&hash_table->keys);
681 old_values = g_steal_pointer (&hash_table->values);
682 old_hashes = g_steal_pointer (&hash_table->hashes);
685 /* Any accesses will see an empty table */
686 g_hash_table_setup_storage (hash_table);
688 /* Will cause a quick crash on any attempted access */
689 hash_table->size = hash_table->mod = hash_table->mask = 0;
691 /* Now do the actual destroy notifies */
692 for (i = 0; i < old_size; i++)
694 if (HASH_IS_REAL (old_hashes[i]))
696 key = g_hash_table_fetch_key_or_value (old_keys, i, old_have_big_keys);
697 value = g_hash_table_fetch_key_or_value (old_values, i, old_have_big_values);
699 old_hashes[i] = UNUSED_HASH_VALUE;
701 g_hash_table_assign_key_or_value (old_keys, i, old_have_big_keys, NULL);
702 g_hash_table_assign_key_or_value (old_values, i, old_have_big_values, NULL);
704 if (hash_table->key_destroy_func != NULL)
705 hash_table->key_destroy_func (key);
707 if (hash_table->value_destroy_func != NULL)
708 hash_table->value_destroy_func (value);
712 /* Destroy old storage space. */
713 if (old_keys != old_values)
721 realloc_arrays (GHashTable *hash_table, gboolean is_a_set)
723 hash_table->hashes = g_renew (guint, hash_table->hashes, hash_table->size);
724 hash_table->keys = g_hash_table_realloc_key_or_value_array (hash_table->keys, hash_table->size, hash_table->have_big_keys);
727 hash_table->values = hash_table->keys;
729 hash_table->values = g_hash_table_realloc_key_or_value_array (hash_table->values, hash_table->size, hash_table->have_big_values);
732 /* When resizing the table in place, we use a temporary bit array to keep
733 * track of which entries have been assigned a proper location in the new
736 * Each bit corresponds to a bucket. A bit is set if an entry was assigned
737 * its corresponding location during the resize and thus should not be
738 * evicted. The array starts out cleared to zero. */
740 static inline gboolean
741 get_status_bit (const guint32 *bitmap, guint index)
743 return (bitmap[index / 32] >> (index % 32)) & 1;
747 set_status_bit (guint32 *bitmap, guint index)
749 bitmap[index / 32] |= 1U << (index % 32);
752 /* By calling dedicated resize functions for sets and maps, we avoid 2x
753 * test-and-branch per key in the inner loop. This yields a small
754 * performance improvement at the cost of a bit of macro gunk. */
756 #define DEFINE_RESIZE_FUNC(fname) \
757 static void fname (GHashTable *hash_table, guint old_size, guint32 *reallocated_buckets_bitmap) \
761 for (i = 0; i < old_size; i++) \
763 guint node_hash = hash_table->hashes[i]; \
764 gpointer key, value G_GNUC_UNUSED; \
766 if (!HASH_IS_REAL (node_hash)) \
768 /* Clear tombstones */ \
769 hash_table->hashes[i] = UNUSED_HASH_VALUE; \
773 /* Skip entries relocated through eviction */ \
774 if (get_status_bit (reallocated_buckets_bitmap, i)) \
777 hash_table->hashes[i] = UNUSED_HASH_VALUE; \
778 EVICT_KEYVAL (hash_table, i, NULL, NULL, key, value); \
783 guint replaced_hash; \
786 hash_val = g_hash_table_hash_to_index (hash_table, node_hash); \
788 while (get_status_bit (reallocated_buckets_bitmap, hash_val)) \
792 hash_val &= hash_table->mask; \
795 set_status_bit (reallocated_buckets_bitmap, hash_val); \
797 replaced_hash = hash_table->hashes[hash_val]; \
798 hash_table->hashes[hash_val] = node_hash; \
799 if (!HASH_IS_REAL (replaced_hash)) \
801 ASSIGN_KEYVAL (hash_table, hash_val, key, value); \
805 node_hash = replaced_hash; \
806 EVICT_KEYVAL (hash_table, hash_val, key, value, key, value); \
811 #define ASSIGN_KEYVAL(ht, index, key, value) G_STMT_START{ \
812 g_hash_table_assign_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
813 g_hash_table_assign_key_or_value ((ht)->values, (index), (ht)->have_big_values, (value)); \
816 #define EVICT_KEYVAL(ht, index, key, value, outkey, outvalue) G_STMT_START{ \
817 (outkey) = g_hash_table_evict_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
818 (outvalue) = g_hash_table_evict_key_or_value ((ht)->values, (index), (ht)->have_big_values, (value)); \
821 DEFINE_RESIZE_FUNC (resize_map)
826 #define ASSIGN_KEYVAL(ht, index, key, value) G_STMT_START{ \
827 g_hash_table_assign_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
830 #define EVICT_KEYVAL(ht, index, key, value, outkey, outvalue) G_STMT_START{ \
831 (outkey) = g_hash_table_evict_key_or_value ((ht)->keys, (index), (ht)->have_big_keys, (key)); \
834 DEFINE_RESIZE_FUNC (resize_set)
840 * g_hash_table_resize:
841 * @hash_table: our #GHashTable
843 * Resizes the hash table to the optimal size based on the number of
844 * nodes currently held. If you call this function then a resize will
845 * occur, even if one does not need to occur.
846 * Use g_hash_table_maybe_resize() instead.
848 * This function may "resize" the hash table to its current size, with
849 * the side effect of cleaning up tombstones and otherwise optimizing
850 * the probe sequences.
853 g_hash_table_resize (GHashTable *hash_table)
855 guint32 *reallocated_buckets_bitmap;
859 old_size = hash_table->size;
860 is_a_set = hash_table->keys == hash_table->values;
862 /* The outer checks in g_hash_table_maybe_resize() will only consider
863 * cleanup/resize when the load factor goes below .25 (1/4, ignoring
864 * tombstones) or above .9375 (15/16, including tombstones).
866 * Once this happens, tombstones will always be cleaned out. If our
867 * load sans tombstones is greater than .75 (1/1.333, see below), we'll
868 * take this opportunity to grow the table too.
870 * Immediately after growing, the load factor will be in the range
871 * .375 .. .469. After shrinking, it will be exactly .5. */
873 g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 1.333);
875 if (hash_table->size > old_size)
877 realloc_arrays (hash_table, is_a_set);
878 memset (&hash_table->hashes[old_size], 0, (hash_table->size - old_size) * sizeof (guint));
880 reallocated_buckets_bitmap = g_new0 (guint32, (hash_table->size + 31) / 32);
884 reallocated_buckets_bitmap = g_new0 (guint32, (old_size + 31) / 32);
888 resize_set (hash_table, old_size, reallocated_buckets_bitmap);
890 resize_map (hash_table, old_size, reallocated_buckets_bitmap);
892 g_free (reallocated_buckets_bitmap);
894 if (hash_table->size < old_size)
895 realloc_arrays (hash_table, is_a_set);
897 hash_table->noccupied = hash_table->nnodes;
901 * g_hash_table_maybe_resize:
902 * @hash_table: our #GHashTable
904 * Resizes the hash table, if needed.
906 * Essentially, calls g_hash_table_resize() if the table has strayed
907 * too far from its ideal size for its number of nodes.
910 g_hash_table_maybe_resize (GHashTable *hash_table)
912 gint noccupied = hash_table->noccupied;
913 gint size = hash_table->size;
915 if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
916 (size <= noccupied + (noccupied / 16)))
917 g_hash_table_resize (hash_table);
920 #ifdef USE_SMALL_ARRAYS
922 static inline gboolean
923 entry_is_big (gpointer v)
925 return (((guintptr) v) >> ((BIG_ENTRY_SIZE - SMALL_ENTRY_SIZE) * 8)) != 0;
928 static inline gboolean
929 g_hash_table_maybe_make_big_keys_or_values (gpointer *a_p, gpointer v, gint ht_size)
931 if (entry_is_big (v))
933 guint *a = (guint *) *a_p;
937 a_new = g_new (gpointer, ht_size);
939 for (i = 0; i < ht_size; i++)
941 a_new[i] = GUINT_TO_POINTER (a[i]);
955 g_hash_table_ensure_keyval_fits (GHashTable *hash_table, gpointer key, gpointer value)
957 gboolean is_a_set = (hash_table->keys == hash_table->values);
959 #ifdef USE_SMALL_ARRAYS
961 /* Convert from set to map? */
964 if (hash_table->have_big_keys)
967 hash_table->values = g_memdup2 (hash_table->keys, sizeof (gpointer) * hash_table->size);
968 /* Keys and values are both big now, so no need for further checks */
975 hash_table->values = g_memdup2 (hash_table->keys, sizeof (guint) * hash_table->size);
982 if (!hash_table->have_big_keys)
984 hash_table->have_big_keys = g_hash_table_maybe_make_big_keys_or_values (&hash_table->keys, key, hash_table->size);
988 hash_table->values = hash_table->keys;
989 hash_table->have_big_values = hash_table->have_big_keys;
993 /* Make values big? */
994 if (!is_a_set && !hash_table->have_big_values)
996 hash_table->have_big_values = g_hash_table_maybe_make_big_keys_or_values (&hash_table->values, value, hash_table->size);
1001 /* Just split if necessary */
1002 if (is_a_set && key != value)
1003 hash_table->values = g_memdup2 (hash_table->keys, sizeof (gpointer) * hash_table->size);
1010 * @hash_func: a function to create a hash value from a key
1011 * @key_equal_func: a function to check two keys for equality
1013 * Creates a new #GHashTable with a reference count of 1.
1015 * Hash values returned by @hash_func are used to determine where keys
1016 * are stored within the #GHashTable data structure. The g_direct_hash(),
1017 * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash()
1018 * functions are provided for some common types of keys.
1019 * If @hash_func is %NULL, g_direct_hash() is used.
1021 * @key_equal_func is used when looking up keys in the #GHashTable.
1022 * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal()
1023 * and g_str_equal() functions are provided for the most common types
1024 * of keys. If @key_equal_func is %NULL, keys are compared directly in
1025 * a similar fashion to g_direct_equal(), but without the overhead of
1026 * a function call. @key_equal_func is called with the key from the hash table
1027 * as its first parameter, and the user-provided key to check against as
1030 * Returns: a new #GHashTable
1033 g_hash_table_new (GHashFunc hash_func,
1034 GEqualFunc key_equal_func)
1036 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
1041 * g_hash_table_new_full:
1042 * @hash_func: a function to create a hash value from a key
1043 * @key_equal_func: a function to check two keys for equality
1044 * @key_destroy_func: (nullable): a function to free the memory allocated for the key
1045 * used when removing the entry from the #GHashTable, or %NULL
1046 * if you don't want to supply such a function.
1047 * @value_destroy_func: (nullable): a function to free the memory allocated for the
1048 * value used when removing the entry from the #GHashTable, or %NULL
1049 * if you don't want to supply such a function.
1051 * Creates a new #GHashTable like g_hash_table_new() with a reference
1052 * count of 1 and allows to specify functions to free the memory
1053 * allocated for the key and value that get called when removing the
1054 * entry from the #GHashTable.
1056 * Since version 2.42 it is permissible for destroy notify functions to
1057 * recursively remove further items from the hash table. This is only
1058 * permissible if the application still holds a reference to the hash table.
1059 * This means that you may need to ensure that the hash table is empty by
1060 * calling g_hash_table_remove_all() before releasing the last reference using
1061 * g_hash_table_unref().
1063 * Returns: a new #GHashTable
1066 g_hash_table_new_full (GHashFunc hash_func,
1067 GEqualFunc key_equal_func,
1068 GDestroyNotify key_destroy_func,
1069 GDestroyNotify value_destroy_func)
1071 GHashTable *hash_table;
1073 hash_table = g_slice_new (GHashTable);
1074 g_atomic_ref_count_init (&hash_table->ref_count);
1075 hash_table->nnodes = 0;
1076 hash_table->noccupied = 0;
1077 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
1078 hash_table->key_equal_func = key_equal_func;
1079 #ifndef G_DISABLE_ASSERT
1080 hash_table->version = 0;
1082 hash_table->key_destroy_func = key_destroy_func;
1083 hash_table->value_destroy_func = value_destroy_func;
1085 g_hash_table_setup_storage (hash_table);
1091 * g_hash_table_new_similar:
1092 * @other_hash_table: (not nullable) (transfer none): Another #GHashTable
1094 * Creates a new #GHashTable like g_hash_table_new_full() with a reference
1097 * It inherits the hash function, the key equal function, the key destroy function,
1098 * as well as the value destroy function, from @other_hash_table.
1100 * The returned hash table will be empty; it will not contain the keys
1101 * or values from @other_hash_table.
1103 * Returns: (transfer full) (not nullable): a new #GHashTable
1107 g_hash_table_new_similar (GHashTable *other_hash_table)
1109 g_return_val_if_fail (other_hash_table, NULL);
1111 return g_hash_table_new_full (other_hash_table->hash_func,
1112 other_hash_table->key_equal_func,
1113 other_hash_table->key_destroy_func,
1114 other_hash_table->value_destroy_func);
1118 * g_hash_table_iter_init:
1119 * @iter: an uninitialized #GHashTableIter
1120 * @hash_table: a #GHashTable
1122 * Initializes a key/value pair iterator and associates it with
1123 * @hash_table. Modifying the hash table after calling this function
1124 * invalidates the returned iterator.
1126 * The iteration order of a #GHashTableIter over the keys/values in a hash
1127 * table is not defined.
1129 * |[<!-- language="C" -->
1130 * GHashTableIter iter;
1131 * gpointer key, value;
1133 * g_hash_table_iter_init (&iter, hash_table);
1134 * while (g_hash_table_iter_next (&iter, &key, &value))
1136 * // do something with key and value
1143 g_hash_table_iter_init (GHashTableIter *iter,
1144 GHashTable *hash_table)
1146 RealIter *ri = (RealIter *) iter;
1148 g_return_if_fail (iter != NULL);
1149 g_return_if_fail (hash_table != NULL);
1151 ri->hash_table = hash_table;
1153 #ifndef G_DISABLE_ASSERT
1154 ri->version = hash_table->version;
1159 * g_hash_table_iter_next:
1160 * @iter: an initialized #GHashTableIter
1161 * @key: (out) (optional): a location to store the key
1162 * @value: (out) (optional) (nullable): a location to store the value
1164 * Advances @iter and retrieves the key and/or value that are now
1165 * pointed to as a result of this advancement. If %FALSE is returned,
1166 * @key and @value are not set, and the iterator becomes invalid.
1168 * Returns: %FALSE if the end of the #GHashTable has been reached.
1173 g_hash_table_iter_next (GHashTableIter *iter,
1177 RealIter *ri = (RealIter *) iter;
1180 g_return_val_if_fail (iter != NULL, FALSE);
1181 #ifndef G_DISABLE_ASSERT
1182 g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
1184 g_return_val_if_fail (ri->position < (gssize) ri->hash_table->size, FALSE);
1186 position = ri->position;
1191 if (position >= (gssize) ri->hash_table->size)
1193 ri->position = position;
1197 while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
1200 *key = g_hash_table_fetch_key_or_value (ri->hash_table->keys, position, ri->hash_table->have_big_keys);
1202 *value = g_hash_table_fetch_key_or_value (ri->hash_table->values, position, ri->hash_table->have_big_values);
1204 ri->position = position;
1209 * g_hash_table_iter_get_hash_table:
1210 * @iter: an initialized #GHashTableIter
1212 * Returns the #GHashTable associated with @iter.
1214 * Returns: the #GHashTable associated with @iter.
1219 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
1221 g_return_val_if_fail (iter != NULL, NULL);
1223 return ((RealIter *) iter)->hash_table;
1227 iter_remove_or_steal (RealIter *ri, gboolean notify)
1229 g_return_if_fail (ri != NULL);
1230 #ifndef G_DISABLE_ASSERT
1231 g_return_if_fail (ri->version == ri->hash_table->version);
1233 g_return_if_fail (ri->position >= 0);
1234 g_return_if_fail ((gsize) ri->position < ri->hash_table->size);
1236 g_hash_table_remove_node (ri->hash_table, ri->position, notify);
1238 #ifndef G_DISABLE_ASSERT
1240 ri->hash_table->version++;
1245 * g_hash_table_iter_remove:
1246 * @iter: an initialized #GHashTableIter
1248 * Removes the key/value pair currently pointed to by the iterator
1249 * from its associated #GHashTable. Can only be called after
1250 * g_hash_table_iter_next() returned %TRUE, and cannot be called
1251 * more than once for the same key/value pair.
1253 * If the #GHashTable was created using g_hash_table_new_full(),
1254 * the key and value are freed using the supplied destroy functions,
1255 * otherwise you have to make sure that any dynamically allocated
1256 * values are freed yourself.
1258 * It is safe to continue iterating the #GHashTable afterward:
1259 * |[<!-- language="C" -->
1260 * while (g_hash_table_iter_next (&iter, &key, &value))
1263 * g_hash_table_iter_remove (&iter);
1270 g_hash_table_iter_remove (GHashTableIter *iter)
1272 iter_remove_or_steal ((RealIter *) iter, TRUE);
1276 * g_hash_table_insert_node:
1277 * @hash_table: our #GHashTable
1278 * @node_index: pointer to node to insert/replace
1279 * @key_hash: key hash
1280 * @key: (nullable): key to replace with, or %NULL
1281 * @value: value to replace with
1282 * @keep_new_key: whether to replace the key in the node with @key
1283 * @reusing_key: whether @key was taken out of the existing node
1285 * Inserts a value at @node_index in the hash table and updates it.
1287 * If @key has been taken out of the existing node (ie it is not
1288 * passed in via a g_hash_table_insert/replace) call, then @reusing_key
1291 * Returns: %TRUE if the key did not exist yet
1294 g_hash_table_insert_node (GHashTable *hash_table,
1299 gboolean keep_new_key,
1300 gboolean reusing_key)
1302 gboolean already_exists;
1304 gpointer key_to_free = NULL;
1305 gpointer key_to_keep = NULL;
1306 gpointer value_to_free = NULL;
1308 old_hash = hash_table->hashes[node_index];
1309 already_exists = HASH_IS_REAL (old_hash);
1311 /* Proceed in three steps. First, deal with the key because it is the
1312 * most complicated. Then consider if we need to split the table in
1313 * two (because writing the value will result in the set invariant
1314 * becoming broken). Then deal with the value.
1316 * There are three cases for the key:
1318 * - entry already exists in table, reusing key:
1319 * free the just-passed-in new_key and use the existing value
1321 * - entry already exists in table, not reusing key:
1322 * free the entry in the table, use the new key
1324 * - entry not already in table:
1325 * use the new key, free nothing
1327 * We update the hash at the same time...
1331 /* Note: we must record the old value before writing the new key
1332 * because we might change the value in the event that the two
1333 * arrays are shared.
1335 value_to_free = g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values);
1339 key_to_free = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1340 key_to_keep = new_key;
1344 key_to_free = new_key;
1345 key_to_keep = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1350 hash_table->hashes[node_index] = key_hash;
1351 key_to_keep = new_key;
1354 /* Resize key/value arrays and split table as necessary */
1355 g_hash_table_ensure_keyval_fits (hash_table, key_to_keep, new_value);
1356 g_hash_table_assign_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys, key_to_keep);
1358 /* Step 3: Actually do the write */
1359 g_hash_table_assign_key_or_value (hash_table->values, node_index, hash_table->have_big_values, new_value);
1361 /* Now, the bookkeeping... */
1362 if (!already_exists)
1364 hash_table->nnodes++;
1366 if (HASH_IS_UNUSED (old_hash))
1368 /* We replaced an empty node, and not a tombstone */
1369 hash_table->noccupied++;
1370 g_hash_table_maybe_resize (hash_table);
1373 #ifndef G_DISABLE_ASSERT
1374 hash_table->version++;
1380 if (hash_table->key_destroy_func && !reusing_key)
1381 (* hash_table->key_destroy_func) (key_to_free);
1382 if (hash_table->value_destroy_func)
1383 (* hash_table->value_destroy_func) (value_to_free);
1386 return !already_exists;
1390 * g_hash_table_iter_replace:
1391 * @iter: an initialized #GHashTableIter
1392 * @value: the value to replace with
1394 * Replaces the value currently pointed to by the iterator
1395 * from its associated #GHashTable. Can only be called after
1396 * g_hash_table_iter_next() returned %TRUE.
1398 * If you supplied a @value_destroy_func when creating the
1399 * #GHashTable, the old value is freed using that function.
1404 g_hash_table_iter_replace (GHashTableIter *iter,
1411 ri = (RealIter *) iter;
1413 g_return_if_fail (ri != NULL);
1414 #ifndef G_DISABLE_ASSERT
1415 g_return_if_fail (ri->version == ri->hash_table->version);
1417 g_return_if_fail (ri->position >= 0);
1418 g_return_if_fail ((gsize) ri->position < ri->hash_table->size);
1420 node_hash = ri->hash_table->hashes[ri->position];
1422 key = g_hash_table_fetch_key_or_value (ri->hash_table->keys, ri->position, ri->hash_table->have_big_keys);
1424 g_hash_table_insert_node (ri->hash_table, ri->position, node_hash, key, value, TRUE, TRUE);
1426 #ifndef G_DISABLE_ASSERT
1428 ri->hash_table->version++;
1433 * g_hash_table_iter_steal:
1434 * @iter: an initialized #GHashTableIter
1436 * Removes the key/value pair currently pointed to by the
1437 * iterator from its associated #GHashTable, without calling
1438 * the key and value destroy functions. Can only be called
1439 * after g_hash_table_iter_next() returned %TRUE, and cannot
1440 * be called more than once for the same key/value pair.
1445 g_hash_table_iter_steal (GHashTableIter *iter)
1447 iter_remove_or_steal ((RealIter *) iter, FALSE);
1453 * @hash_table: a valid #GHashTable
1455 * Atomically increments the reference count of @hash_table by one.
1456 * This function is MT-safe and may be called from any thread.
1458 * Returns: the passed in #GHashTable
1463 g_hash_table_ref (GHashTable *hash_table)
1465 g_return_val_if_fail (hash_table != NULL, NULL);
1467 g_atomic_ref_count_inc (&hash_table->ref_count);
1473 * g_hash_table_unref:
1474 * @hash_table: a valid #GHashTable
1476 * Atomically decrements the reference count of @hash_table by one.
1477 * If the reference count drops to 0, all keys and values will be
1478 * destroyed, and all memory allocated by the hash table is released.
1479 * This function is MT-safe and may be called from any thread.
1484 g_hash_table_unref (GHashTable *hash_table)
1486 g_return_if_fail (hash_table != NULL);
1488 if (g_atomic_ref_count_dec (&hash_table->ref_count))
1490 g_hash_table_remove_all_nodes (hash_table, TRUE, TRUE);
1491 if (hash_table->keys != hash_table->values)
1492 g_free (hash_table->values);
1493 g_free (hash_table->keys);
1494 g_free (hash_table->hashes);
1495 g_slice_free (GHashTable, hash_table);
1500 * g_hash_table_destroy:
1501 * @hash_table: a #GHashTable
1503 * Destroys all keys and values in the #GHashTable and decrements its
1504 * reference count by 1. If keys and/or values are dynamically allocated,
1505 * you should either free them first or create the #GHashTable with destroy
1506 * notifiers using g_hash_table_new_full(). In the latter case the destroy
1507 * functions you supplied will be called on all keys and values during the
1508 * destruction phase.
1511 g_hash_table_destroy (GHashTable *hash_table)
1513 g_return_if_fail (hash_table != NULL);
1515 g_hash_table_remove_all (hash_table);
1516 g_hash_table_unref (hash_table);
1520 * g_hash_table_lookup:
1521 * @hash_table: a #GHashTable
1522 * @key: the key to look up
1524 * Looks up a key in a #GHashTable. Note that this function cannot
1525 * distinguish between a key that is not present and one which is present
1526 * and has the value %NULL. If you need this distinction, use
1527 * g_hash_table_lookup_extended().
1529 * Returns: (nullable): the associated value, or %NULL if the key is not found
1532 g_hash_table_lookup (GHashTable *hash_table,
1538 g_return_val_if_fail (hash_table != NULL, NULL);
1540 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1542 return HASH_IS_REAL (hash_table->hashes[node_index])
1543 ? g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values)
1548 * g_hash_table_lookup_extended:
1549 * @hash_table: a #GHashTable
1550 * @lookup_key: the key to look up
1551 * @orig_key: (out) (optional): return location for the original key
1552 * @value: (out) (optional) (nullable): return location for the value associated
1555 * Looks up a key in the #GHashTable, returning the original key and the
1556 * associated value and a #gboolean which is %TRUE if the key was found. This
1557 * is useful if you need to free the memory allocated for the original key,
1558 * for example before calling g_hash_table_remove().
1560 * You can actually pass %NULL for @lookup_key to test
1561 * whether the %NULL key exists, provided the hash and equal functions
1562 * of @hash_table are %NULL-safe.
1564 * Returns: %TRUE if the key was found in the #GHashTable
1567 g_hash_table_lookup_extended (GHashTable *hash_table,
1568 gconstpointer lookup_key,
1575 g_return_val_if_fail (hash_table != NULL, FALSE);
1577 node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1579 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1581 if (orig_key != NULL)
1590 *orig_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1593 *value = g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values);
1599 * g_hash_table_insert_internal:
1600 * @hash_table: our #GHashTable
1601 * @key: the key to insert
1602 * @value: the value to insert
1603 * @keep_new_key: if %TRUE and this key already exists in the table
1604 * then call the destroy notify function on the old key. If %FALSE
1605 * then call the destroy notify function on the new key.
1607 * Implements the common logic for the g_hash_table_insert() and
1608 * g_hash_table_replace() functions.
1610 * Do a lookup of @key. If it is found, replace it with the new
1611 * @value (and perhaps the new @key). If it is not found, create
1614 * Returns: %TRUE if the key did not exist yet
1617 g_hash_table_insert_internal (GHashTable *hash_table,
1620 gboolean keep_new_key)
1625 g_return_val_if_fail (hash_table != NULL, FALSE);
1627 node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
1629 return g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key, FALSE);
1633 * g_hash_table_insert:
1634 * @hash_table: a #GHashTable
1635 * @key: a key to insert
1636 * @value: the value to associate with the key
1638 * Inserts a new key and value into a #GHashTable.
1640 * If the key already exists in the #GHashTable its current
1641 * value is replaced with the new value. If you supplied a
1642 * @value_destroy_func when creating the #GHashTable, the old
1643 * value is freed using that function. If you supplied a
1644 * @key_destroy_func when creating the #GHashTable, the passed
1645 * key is freed using that function.
1647 * Starting from GLib 2.40, this function returns a boolean value to
1648 * indicate whether the newly added value was already in the hash table
1651 * Returns: %TRUE if the key did not exist yet
1654 g_hash_table_insert (GHashTable *hash_table,
1658 return g_hash_table_insert_internal (hash_table, key, value, FALSE);
1662 * g_hash_table_replace:
1663 * @hash_table: a #GHashTable
1664 * @key: a key to insert
1665 * @value: the value to associate with the key
1667 * Inserts a new key and value into a #GHashTable similar to
1668 * g_hash_table_insert(). The difference is that if the key
1669 * already exists in the #GHashTable, it gets replaced by the
1670 * new key. If you supplied a @value_destroy_func when creating
1671 * the #GHashTable, the old value is freed using that function.
1672 * If you supplied a @key_destroy_func when creating the
1673 * #GHashTable, the old key is freed using that function.
1675 * Starting from GLib 2.40, this function returns a boolean value to
1676 * indicate whether the newly added value was already in the hash table
1679 * Returns: %TRUE if the key did not exist yet
1682 g_hash_table_replace (GHashTable *hash_table,
1686 return g_hash_table_insert_internal (hash_table, key, value, TRUE);
1691 * @hash_table: a #GHashTable
1692 * @key: (transfer full): a key to insert
1694 * This is a convenience function for using a #GHashTable as a set. It
1695 * is equivalent to calling g_hash_table_replace() with @key as both the
1696 * key and the value.
1698 * In particular, this means that if @key already exists in the hash table, then
1699 * the old copy of @key in the hash table is freed and @key replaces it in the
1702 * When a hash table only ever contains keys that have themselves as the
1703 * corresponding value it is able to be stored more efficiently. See
1704 * the discussion in the section description.
1706 * Starting from GLib 2.40, this function returns a boolean value to
1707 * indicate whether the newly added value was already in the hash table
1710 * Returns: %TRUE if the key did not exist yet
1715 g_hash_table_add (GHashTable *hash_table,
1718 return g_hash_table_insert_internal (hash_table, key, key, TRUE);
1722 * g_hash_table_contains:
1723 * @hash_table: a #GHashTable
1724 * @key: a key to check
1726 * Checks if @key is in @hash_table.
1728 * Returns: %TRUE if @key is in @hash_table, %FALSE otherwise.
1733 g_hash_table_contains (GHashTable *hash_table,
1739 g_return_val_if_fail (hash_table != NULL, FALSE);
1741 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1743 return HASH_IS_REAL (hash_table->hashes[node_index]);
1747 * g_hash_table_remove_internal:
1748 * @hash_table: our #GHashTable
1749 * @key: the key to remove
1750 * @notify: %TRUE if the destroy notify handlers are to be called
1751 * Returns: %TRUE if a node was found and removed, else %FALSE
1753 * Implements the common logic for the g_hash_table_remove() and
1754 * g_hash_table_steal() functions.
1756 * Do a lookup of @key and remove it if it is found, calling the
1757 * destroy notify handlers only if @notify is %TRUE.
1760 g_hash_table_remove_internal (GHashTable *hash_table,
1767 g_return_val_if_fail (hash_table != NULL, FALSE);
1769 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1771 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1774 g_hash_table_remove_node (hash_table, node_index, notify);
1775 g_hash_table_maybe_resize (hash_table);
1777 #ifndef G_DISABLE_ASSERT
1778 hash_table->version++;
1785 * g_hash_table_remove:
1786 * @hash_table: a #GHashTable
1787 * @key: the key to remove
1789 * Removes a key and its associated value from a #GHashTable.
1791 * If the #GHashTable was created using g_hash_table_new_full(), the
1792 * key and value are freed using the supplied destroy functions, otherwise
1793 * you have to make sure that any dynamically allocated values are freed
1796 * Returns: %TRUE if the key was found and removed from the #GHashTable
1799 g_hash_table_remove (GHashTable *hash_table,
1802 return g_hash_table_remove_internal (hash_table, key, TRUE);
1806 * g_hash_table_steal:
1807 * @hash_table: a #GHashTable
1808 * @key: the key to remove
1810 * Removes a key and its associated value from a #GHashTable without
1811 * calling the key and value destroy functions.
1813 * Returns: %TRUE if the key was found and removed from the #GHashTable
1816 g_hash_table_steal (GHashTable *hash_table,
1819 return g_hash_table_remove_internal (hash_table, key, FALSE);
1823 * g_hash_table_steal_extended:
1824 * @hash_table: a #GHashTable
1825 * @lookup_key: the key to look up
1826 * @stolen_key: (out) (optional) (transfer full): return location for the
1828 * @stolen_value: (out) (optional) (nullable) (transfer full): return location
1829 * for the value associated with the key
1831 * Looks up a key in the #GHashTable, stealing the original key and the
1832 * associated value and returning %TRUE if the key was found. If the key was
1833 * not found, %FALSE is returned.
1835 * If found, the stolen key and value are removed from the hash table without
1836 * calling the key and value destroy functions, and ownership is transferred to
1837 * the caller of this method; as with g_hash_table_steal().
1839 * You can pass %NULL for @lookup_key, provided the hash and equal functions
1840 * of @hash_table are %NULL-safe.
1842 * The dictionary implementation optimizes for having all values identical to
1843 * their keys, for example by using g_hash_table_add(). When stealing both the
1844 * key and the value from such a dictionary, the value will be %NULL.
1846 * Returns: %TRUE if the key was found in the #GHashTable
1850 g_hash_table_steal_extended (GHashTable *hash_table,
1851 gconstpointer lookup_key,
1852 gpointer *stolen_key,
1853 gpointer *stolen_value)
1858 g_return_val_if_fail (hash_table != NULL, FALSE);
1860 node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1862 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1864 if (stolen_key != NULL)
1866 if (stolen_value != NULL)
1867 *stolen_value = NULL;
1871 if (stolen_key != NULL)
1873 *stolen_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
1874 g_hash_table_assign_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys, NULL);
1877 if (stolen_value != NULL)
1879 *stolen_value = g_hash_table_fetch_key_or_value (hash_table->values, node_index, hash_table->have_big_values);
1880 g_hash_table_assign_key_or_value (hash_table->values, node_index, hash_table->have_big_values, NULL);
1883 g_hash_table_remove_node (hash_table, node_index, FALSE);
1884 g_hash_table_maybe_resize (hash_table);
1886 #ifndef G_DISABLE_ASSERT
1887 hash_table->version++;
1894 * g_hash_table_remove_all:
1895 * @hash_table: a #GHashTable
1897 * Removes all keys and their associated values from a #GHashTable.
1899 * If the #GHashTable was created using g_hash_table_new_full(),
1900 * the keys and values are freed using the supplied destroy functions,
1901 * otherwise you have to make sure that any dynamically allocated
1902 * values are freed yourself.
1907 g_hash_table_remove_all (GHashTable *hash_table)
1909 g_return_if_fail (hash_table != NULL);
1911 #ifndef G_DISABLE_ASSERT
1912 if (hash_table->nnodes != 0)
1913 hash_table->version++;
1916 g_hash_table_remove_all_nodes (hash_table, TRUE, FALSE);
1917 g_hash_table_maybe_resize (hash_table);
1921 * g_hash_table_steal_all:
1922 * @hash_table: a #GHashTable
1924 * Removes all keys and their associated values from a #GHashTable
1925 * without calling the key and value destroy functions.
1930 g_hash_table_steal_all (GHashTable *hash_table)
1932 g_return_if_fail (hash_table != NULL);
1934 #ifndef G_DISABLE_ASSERT
1935 if (hash_table->nnodes != 0)
1936 hash_table->version++;
1939 g_hash_table_remove_all_nodes (hash_table, FALSE, FALSE);
1940 g_hash_table_maybe_resize (hash_table);
1944 * g_hash_table_foreach_remove_or_steal:
1945 * @hash_table: a #GHashTable
1946 * @func: the user's callback function
1947 * @user_data: data for @func
1948 * @notify: %TRUE if the destroy notify handlers are to be called
1950 * Implements the common logic for g_hash_table_foreach_remove()
1951 * and g_hash_table_foreach_steal().
1953 * Iterates over every node in the table, calling @func with the key
1954 * and value of the node (and @user_data). If @func returns %TRUE the
1955 * node is removed from the table.
1957 * If @notify is true then the destroy notify handlers will be called
1958 * for each removed node.
1961 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1968 #ifndef G_DISABLE_ASSERT
1969 gint version = hash_table->version;
1972 for (i = 0; i < hash_table->size; i++)
1974 guint node_hash = hash_table->hashes[i];
1975 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
1976 gpointer node_value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
1978 if (HASH_IS_REAL (node_hash) &&
1979 (* func) (node_key, node_value, user_data))
1981 g_hash_table_remove_node (hash_table, i, notify);
1985 #ifndef G_DISABLE_ASSERT
1986 g_return_val_if_fail (version == hash_table->version, 0);
1990 g_hash_table_maybe_resize (hash_table);
1992 #ifndef G_DISABLE_ASSERT
1994 hash_table->version++;
2001 * g_hash_table_foreach_remove:
2002 * @hash_table: a #GHashTable
2003 * @func: the function to call for each key/value pair
2004 * @user_data: user data to pass to the function
2006 * Calls the given function for each key/value pair in the
2007 * #GHashTable. If the function returns %TRUE, then the key/value
2008 * pair is removed from the #GHashTable. If you supplied key or
2009 * value destroy functions when creating the #GHashTable, they are
2010 * used to free the memory allocated for the removed keys and values.
2012 * See #GHashTableIter for an alternative way to loop over the
2013 * key/value pairs in the hash table.
2015 * Returns: the number of key/value pairs removed
2018 g_hash_table_foreach_remove (GHashTable *hash_table,
2022 g_return_val_if_fail (hash_table != NULL, 0);
2023 g_return_val_if_fail (func != NULL, 0);
2025 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
2029 * g_hash_table_foreach_steal:
2030 * @hash_table: a #GHashTable
2031 * @func: the function to call for each key/value pair
2032 * @user_data: user data to pass to the function
2034 * Calls the given function for each key/value pair in the
2035 * #GHashTable. If the function returns %TRUE, then the key/value
2036 * pair is removed from the #GHashTable, but no key or value
2037 * destroy functions are called.
2039 * See #GHashTableIter for an alternative way to loop over the
2040 * key/value pairs in the hash table.
2042 * Returns: the number of key/value pairs removed.
2045 g_hash_table_foreach_steal (GHashTable *hash_table,
2049 g_return_val_if_fail (hash_table != NULL, 0);
2050 g_return_val_if_fail (func != NULL, 0);
2052 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
2056 * g_hash_table_foreach:
2057 * @hash_table: a #GHashTable
2058 * @func: the function to call for each key/value pair
2059 * @user_data: user data to pass to the function
2061 * Calls the given function for each of the key/value pairs in the
2062 * #GHashTable. The function is passed the key and value of each
2063 * pair, and the given @user_data parameter. The hash table may not
2064 * be modified while iterating over it (you can't add/remove
2065 * items). To remove all items matching a predicate, use
2066 * g_hash_table_foreach_remove().
2068 * The order in which g_hash_table_foreach() iterates over the keys/values in
2069 * the hash table is not defined.
2071 * See g_hash_table_find() for performance caveats for linear
2072 * order searches in contrast to g_hash_table_lookup().
2075 g_hash_table_foreach (GHashTable *hash_table,
2080 #ifndef G_DISABLE_ASSERT
2084 g_return_if_fail (hash_table != NULL);
2085 g_return_if_fail (func != NULL);
2087 #ifndef G_DISABLE_ASSERT
2088 version = hash_table->version;
2091 for (i = 0; i < hash_table->size; i++)
2093 guint node_hash = hash_table->hashes[i];
2094 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
2095 gpointer node_value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
2097 if (HASH_IS_REAL (node_hash))
2098 (* func) (node_key, node_value, user_data);
2100 #ifndef G_DISABLE_ASSERT
2101 g_return_if_fail (version == hash_table->version);
2107 * g_hash_table_find:
2108 * @hash_table: a #GHashTable
2109 * @predicate: function to test the key/value pairs for a certain property
2110 * @user_data: user data to pass to the function
2112 * Calls the given function for key/value pairs in the #GHashTable
2113 * until @predicate returns %TRUE. The function is passed the key
2114 * and value of each pair, and the given @user_data parameter. The
2115 * hash table may not be modified while iterating over it (you can't
2116 * add/remove items).
2118 * Note, that hash tables are really only optimized for forward
2119 * lookups, i.e. g_hash_table_lookup(). So code that frequently issues
2120 * g_hash_table_find() or g_hash_table_foreach() (e.g. in the order of
2121 * once per every entry in a hash table) should probably be reworked
2122 * to use additional or different data structures for reverse lookups
2123 * (keep in mind that an O(n) find/foreach operation issued for all n
2124 * values in a hash table ends up needing O(n*n) operations).
2126 * Returns: (nullable): The value of the first key/value pair is returned,
2127 * for which @predicate evaluates to %TRUE. If no pair with the
2128 * requested property is found, %NULL is returned.
2133 g_hash_table_find (GHashTable *hash_table,
2138 #ifndef G_DISABLE_ASSERT
2143 g_return_val_if_fail (hash_table != NULL, NULL);
2144 g_return_val_if_fail (predicate != NULL, NULL);
2146 #ifndef G_DISABLE_ASSERT
2147 version = hash_table->version;
2152 for (i = 0; i < hash_table->size; i++)
2154 guint node_hash = hash_table->hashes[i];
2155 gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
2156 gpointer node_value = g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values);
2158 if (HASH_IS_REAL (node_hash))
2159 match = predicate (node_key, node_value, user_data);
2161 #ifndef G_DISABLE_ASSERT
2162 g_return_val_if_fail (version == hash_table->version, NULL);
2173 * g_hash_table_size:
2174 * @hash_table: a #GHashTable
2176 * Returns the number of elements contained in the #GHashTable.
2178 * Returns: the number of key/value pairs in the #GHashTable.
2181 g_hash_table_size (GHashTable *hash_table)
2183 g_return_val_if_fail (hash_table != NULL, 0);
2185 return hash_table->nnodes;
2189 * g_hash_table_get_keys:
2190 * @hash_table: a #GHashTable
2192 * Retrieves every key inside @hash_table. The returned data is valid
2193 * until changes to the hash release those keys.
2195 * This iterates over every entry in the hash table to build its return value.
2196 * To iterate over the entries in a #GHashTable more efficiently, use a
2199 * Returns: (transfer container): a #GList containing all the keys
2200 * inside the hash table. The content of the list is owned by the
2201 * hash table and should not be modified or freed. Use g_list_free()
2202 * when done using the list.
2207 g_hash_table_get_keys (GHashTable *hash_table)
2212 g_return_val_if_fail (hash_table != NULL, NULL);
2215 for (i = 0; i < hash_table->size; i++)
2217 if (HASH_IS_REAL (hash_table->hashes[i]))
2218 retval = g_list_prepend (retval, g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys));
2225 * g_hash_table_get_keys_as_array:
2226 * @hash_table: a #GHashTable
2227 * @length: (out) (optional): the length of the returned array
2229 * Retrieves every key inside @hash_table, as an array.
2231 * The returned array is %NULL-terminated but may contain %NULL as a
2232 * key. Use @length to determine the true length if it's possible that
2233 * %NULL was used as the value for a key.
2235 * Note: in the common case of a string-keyed #GHashTable, the return
2236 * value of this function can be conveniently cast to (const gchar **).
2238 * This iterates over every entry in the hash table to build its return value.
2239 * To iterate over the entries in a #GHashTable more efficiently, use a
2242 * You should always free the return result with g_free(). In the
2243 * above-mentioned case of a string-keyed hash table, it may be
2244 * appropriate to use g_strfreev() if you call g_hash_table_steal_all()
2245 * first to transfer ownership of the keys.
2247 * Returns: (array length=length) (transfer container): a
2248 * %NULL-terminated array containing each key from the table.
2253 g_hash_table_get_keys_as_array (GHashTable *hash_table,
2259 result = g_new (gpointer, hash_table->nnodes + 1);
2260 for (i = 0; i < hash_table->size; i++)
2262 if (HASH_IS_REAL (hash_table->hashes[i]))
2263 result[j++] = g_hash_table_fetch_key_or_value (hash_table->keys, i, hash_table->have_big_keys);
2265 g_assert_cmpint (j, ==, hash_table->nnodes);
2275 * g_hash_table_get_values:
2276 * @hash_table: a #GHashTable
2278 * Retrieves every value inside @hash_table. The returned data
2279 * is valid until @hash_table is modified.
2281 * This iterates over every entry in the hash table to build its return value.
2282 * To iterate over the entries in a #GHashTable more efficiently, use a
2285 * Returns: (transfer container): a #GList containing all the values
2286 * inside the hash table. The content of the list is owned by the
2287 * hash table and should not be modified or freed. Use g_list_free()
2288 * when done using the list.
2293 g_hash_table_get_values (GHashTable *hash_table)
2298 g_return_val_if_fail (hash_table != NULL, NULL);
2301 for (i = 0; i < hash_table->size; i++)
2303 if (HASH_IS_REAL (hash_table->hashes[i]))
2304 retval = g_list_prepend (retval, g_hash_table_fetch_key_or_value (hash_table->values, i, hash_table->have_big_values));
2315 * @v1: (not nullable): a key
2316 * @v2: (not nullable): a key to compare with @v1
2318 * Compares two strings for byte-by-byte equality and returns %TRUE
2319 * if they are equal. It can be passed to g_hash_table_new() as the
2320 * @key_equal_func parameter, when using non-%NULL strings as keys in a
2323 * This function is typically used for hash table comparisons, but can be used
2324 * for general purpose comparisons of non-%NULL strings. For a %NULL-safe string
2325 * comparison function, see g_strcmp0().
2327 * Returns: %TRUE if the two keys match
2330 (g_str_equal) (gconstpointer v1,
2333 const gchar *string1 = v1;
2334 const gchar *string2 = v2;
2336 return strcmp (string1, string2) == 0;
2341 * @v: (not nullable): a string key
2343 * Converts a string to a hash value.
2345 * This function implements the widely used "djb" hash apparently
2346 * posted by Daniel Bernstein to comp.lang.c some time ago. The 32
2347 * bit unsigned hash value starts at 5381 and for each byte 'c' in
2348 * the string, is updated: `hash = hash * 33 + c`. This function
2349 * uses the signed value of each byte.
2351 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2352 * when using non-%NULL strings as keys in a #GHashTable.
2354 * Note that this function may not be a perfect fit for all use cases.
2355 * For example, it produces some hash collisions with strings as short
2358 * Returns: a hash value corresponding to the key
2361 g_str_hash (gconstpointer v)
2363 const signed char *p;
2366 for (p = v; *p != '\0'; p++)
2367 h = (h << 5) + h + *p;
2374 * @v: (nullable): a #gpointer key
2376 * Converts a gpointer to a hash value.
2377 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2378 * when using opaque pointers compared by pointer value as keys in a
2381 * This hash function is also appropriate for keys that are integers
2382 * stored in pointers, such as `GINT_TO_POINTER (n)`.
2384 * Returns: a hash value corresponding to the key.
2387 g_direct_hash (gconstpointer v)
2389 return GPOINTER_TO_UINT (v);
2394 * @v1: (nullable): a key
2395 * @v2: (nullable): a key to compare with @v1
2397 * Compares two #gpointer arguments and returns %TRUE if they are equal.
2398 * It can be passed to g_hash_table_new() as the @key_equal_func
2399 * parameter, when using opaque pointers compared by pointer value as
2400 * keys in a #GHashTable.
2402 * This equality function is also appropriate for keys that are integers
2403 * stored in pointers, such as `GINT_TO_POINTER (n)`.
2405 * Returns: %TRUE if the two keys match.
2408 g_direct_equal (gconstpointer v1,
2416 * @v1: (not nullable): a pointer to a #gint key
2417 * @v2: (not nullable): a pointer to a #gint key to compare with @v1
2419 * Compares the two #gint values being pointed to and returns
2420 * %TRUE if they are equal.
2421 * It can be passed to g_hash_table_new() as the @key_equal_func
2422 * parameter, when using non-%NULL pointers to integers as keys in a
2425 * Note that this function acts on pointers to #gint, not on #gint
2426 * directly: if your hash table's keys are of the form
2427 * `GINT_TO_POINTER (n)`, use g_direct_equal() instead.
2429 * Returns: %TRUE if the two keys match.
2432 g_int_equal (gconstpointer v1,
2435 return *((const gint*) v1) == *((const gint*) v2);
2440 * @v: (not nullable): a pointer to a #gint key
2442 * Converts a pointer to a #gint to a hash value.
2443 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2444 * when using non-%NULL pointers to integer values as keys in a #GHashTable.
2446 * Note that this function acts on pointers to #gint, not on #gint
2447 * directly: if your hash table's keys are of the form
2448 * `GINT_TO_POINTER (n)`, use g_direct_hash() instead.
2450 * Returns: a hash value corresponding to the key.
2453 g_int_hash (gconstpointer v)
2455 return *(const gint*) v;
2460 * @v1: (not nullable): a pointer to a #gint64 key
2461 * @v2: (not nullable): a pointer to a #gint64 key to compare with @v1
2463 * Compares the two #gint64 values being pointed to and returns
2464 * %TRUE if they are equal.
2465 * It can be passed to g_hash_table_new() as the @key_equal_func
2466 * parameter, when using non-%NULL pointers to 64-bit integers as keys in a
2469 * Returns: %TRUE if the two keys match.
2474 g_int64_equal (gconstpointer v1,
2477 return *((const gint64*) v1) == *((const gint64*) v2);
2482 * @v: (not nullable): a pointer to a #gint64 key
2484 * Converts a pointer to a #gint64 to a hash value.
2486 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2487 * when using non-%NULL pointers to 64-bit integer values as keys in a
2490 * Returns: a hash value corresponding to the key.
2495 g_int64_hash (gconstpointer v)
2497 return (guint) *(const gint64*) v;
2502 * @v1: (not nullable): a pointer to a #gdouble key
2503 * @v2: (not nullable): a pointer to a #gdouble key to compare with @v1
2505 * Compares the two #gdouble values being pointed to and returns
2506 * %TRUE if they are equal.
2507 * It can be passed to g_hash_table_new() as the @key_equal_func
2508 * parameter, when using non-%NULL pointers to doubles as keys in a
2511 * Returns: %TRUE if the two keys match.
2516 g_double_equal (gconstpointer v1,
2519 return *((const gdouble*) v1) == *((const gdouble*) v2);
2524 * @v: (not nullable): a pointer to a #gdouble key
2526 * Converts a pointer to a #gdouble to a hash value.
2527 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2528 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2529 * when using non-%NULL pointers to doubles as keys in a #GHashTable.
2531 * Returns: a hash value corresponding to the key.
2536 g_double_hash (gconstpointer v)
2538 return (guint) *(const gdouble*) v;