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