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