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