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