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