nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 */
17  
18 /*
19 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
20 * file for a list of people on the GLib Team. See the ChangeLog
21 * files for a list of changes. These files are distributed with
22 * GLib at ftp://ftp.gtk.org/pub/gtk/.
23 */
24  
25 /*
26 * MT safe
27 */
28  
29 #include "config.h"
30  
31 #include <string.h> /* memset */
32  
33 #include "ghash.h"
34  
35 #include "glib-private.h"
36 #include "gstrfuncs.h"
37 #include "gatomic.h"
38 #include "gtestutils.h"
39 #include "gslice.h"
40  
41  
42 /**
43 * SECTION:hash_tables
44 * @title: Hash Tables
45 * @short_description: associations between keys and values so that
46 * given a key the value can be found quickly
47 *
48 * A #GHashTable provides associations between keys and values which is
49 * optimized so that given a key, the associated value can be found
50 * very quickly.
51 *
52 * Note that neither keys nor values are copied when inserted into the
53 * #GHashTable, so they must exist for the lifetime of the #GHashTable.
54 * This means that the use of static strings is OK, but temporary
55 * strings (i.e. those created in buffers and those returned by GTK+
56 * widgets) should be copied with g_strdup() before being inserted.
57 *
58 * If keys or values are dynamically allocated, you must be careful to
59 * ensure that they are freed when they are removed from the
60 * #GHashTable, and also when they are overwritten by new insertions
61 * into the #GHashTable. It is also not advisable to mix static strings
62 * and dynamically-allocated strings in a #GHashTable, because it then
63 * becomes difficult to determine whether the string should be freed.
64 *
65 * To create a #GHashTable, use g_hash_table_new().
66 *
67 * To insert a key and value into a #GHashTable, use
68 * g_hash_table_insert().
69 *
70 * To lookup a value corresponding to a given key, use
71 * g_hash_table_lookup() and g_hash_table_lookup_extended().
72 *
73 * g_hash_table_lookup_extended() can also be used to simply
74 * check if a key is present in the hash table.
75 *
76 * To remove a key and value, use g_hash_table_remove().
77 *
78 * To call a function for each key and value pair use
79 * g_hash_table_foreach() or use a iterator to iterate over the
80 * key/value pairs in the hash table, see #GHashTableIter.
81 *
82 * To destroy a #GHashTable use g_hash_table_destroy().
83 *
84 * A common use-case for hash tables is to store information about a
85 * set of keys, without associating any particular value with each
86 * key. GHashTable optimizes one way of doing so: If you store only
87 * key-value pairs where key == value, then GHashTable does not
88 * allocate memory to store the values, which can be a considerable
89 * space saving, if your set is large. The functions
90 * g_hash_table_add() and g_hash_table_contains() are designed to be
91 * used when using #GHashTable this way.
92 */
93  
94 /**
95 * GHashTable:
96 *
97 * The #GHashTable struct is an opaque data structure to represent a
98 * [Hash Table][glib-Hash-Tables]. It should only be accessed via the
99 * following functions.
100 */
101  
102 /**
103 * GHashFunc:
104 * @key: a key
105 *
106 * Specifies the type of the hash function which is passed to
107 * g_hash_table_new() when a #GHashTable is created.
108 *
109 * The function is passed a key and should return a #guint hash value.
110 * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
111 * hash functions which can be used when the key is a #gpointer, #gint*,
112 * and #gchar* respectively.
113 *
114 * g_direct_hash() is also the appropriate hash function for keys
115 * of the form `GINT_TO_POINTER (n)` (or similar macros).
116 *
117 * <!-- FIXME: Need more here. --> A good hash functions should produce
118 * hash values that are evenly distributed over a fairly large range.
119 * The modulus is taken with the hash table size (a prime number) to
120 * find the 'bucket' to place each key into. The function should also
121 * be very fast, since it is called for each key lookup.
122 *
123 * Note that the hash functions provided by GLib have these qualities,
124 * but are not particularly robust against manufactured keys that
125 * cause hash collisions. Therefore, you should consider choosing
126 * a more secure hash function when using a GHashTable with keys
127 * that originate in untrusted data (such as HTTP requests).
128 * Using g_str_hash() in that situation might make your application
129 * vulerable to
130 * [Algorithmic Complexity Attacks](https://lwn.net/Articles/474912/).
131 *
132 * The key to choosing a good hash is unpredictability. Even
133 * cryptographic hashes are very easy to find collisions for when the
134 * remainder is taken modulo a somewhat predictable prime number. There
135 * must be an element of randomness that an attacker is unable to guess.
136 *
137 * Returns: the hash value corresponding to the key
138 */
139  
140 /**
141 * GHFunc:
142 * @key: a key
143 * @value: the value corresponding to the key
144 * @user_data: user data passed to g_hash_table_foreach()
145 *
146 * Specifies the type of the function passed to g_hash_table_foreach().
147 * It is called with each key/value pair, together with the @user_data
148 * parameter which is passed to g_hash_table_foreach().
149 */
150  
151 /**
152 * GHRFunc:
153 * @key: a key
154 * @value: the value associated with the key
155 * @user_data: user data passed to g_hash_table_remove()
156 *
157 * Specifies the type of the function passed to
158 * g_hash_table_foreach_remove(). It is called with each key/value
159 * pair, together with the @user_data parameter passed to
160 * g_hash_table_foreach_remove(). It should return %TRUE if the
161 * key/value pair should be removed from the #GHashTable.
162 *
163 * Returns: %TRUE if the key/value pair should be removed from the
164 * #GHashTable
165 */
166  
167 /**
168 * GEqualFunc:
169 * @a: a value
170 * @b: a value to compare with
171 *
172 * Specifies the type of a function used to test two values for
173 * equality. The function should return %TRUE if both values are equal
174 * and %FALSE otherwise.
175 *
176 * Returns: %TRUE if @a = @b; %FALSE otherwise
177 */
178  
179 /**
180 * GHashTableIter:
181 *
182 * A GHashTableIter structure represents an iterator that can be used
183 * to iterate over the elements of a #GHashTable. GHashTableIter
184 * structures are typically allocated on the stack and then initialized
185 * with g_hash_table_iter_init().
186 */
187  
188 /**
189 * g_hash_table_freeze:
190 * @hash_table: a #GHashTable
191 *
192 * This function is deprecated and will be removed in the next major
193 * release of GLib. It does nothing.
194 */
195  
196 /**
197 * g_hash_table_thaw:
198 * @hash_table: a #GHashTable
199 *
200 * This function is deprecated and will be removed in the next major
201 * release of GLib. It does nothing.
202 */
203  
204 #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */
205  
206 #define UNUSED_HASH_VALUE 0
207 #define TOMBSTONE_HASH_VALUE 1
208 #define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
209 #define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
210 #define HASH_IS_REAL(h_) ((h_) >= 2)
211  
212 struct _GHashTable
213 {
214 gint size;
215 gint mod;
216 guint mask;
217 gint nnodes;
218 gint noccupied; /* nnodes + tombstones */
219  
220 gpointer *keys;
221 guint *hashes;
222 gpointer *values;
223  
224 GHashFunc hash_func;
225 GEqualFunc key_equal_func;
226 gint ref_count;
227 #ifndef G_DISABLE_ASSERT
228 /*
229 * Tracks the structure of the hash table, not its contents: is only
230 * incremented when a node is added or removed (is not incremented
231 * when the key or data of a node is modified).
232 */
233 int version;
234 #endif
235 GDestroyNotify key_destroy_func;
236 GDestroyNotify value_destroy_func;
237 };
238  
239 typedef struct
240 {
241 GHashTable *hash_table;
242 gpointer dummy1;
243 gpointer dummy2;
244 int position;
245 gboolean dummy3;
246 int version;
247 } RealIter;
248  
249 G_STATIC_ASSERT (sizeof (GHashTableIter) == sizeof (RealIter));
250 G_STATIC_ASSERT (_g_alignof (GHashTableIter) >= _g_alignof (RealIter));
251  
252 /* Each table size has an associated prime modulo (the first prime
253 * lower than the table size) used to find the initial bucket. Probing
254 * then works modulo 2^n. The prime modulo is necessary to get a
255 * good distribution with poor hash functions.
256 */
257 static const gint prime_mod [] =
258 {
259 1, /* For 1 << 0 */
260 2,
261 3,
262 7,
263 13,
264 31,
265 61,
266 127,
267 251,
268 509,
269 1021,
270 2039,
271 4093,
272 8191,
273 16381,
274 32749,
275 65521, /* For 1 << 16 */
276 131071,
277 262139,
278 524287,
279 1048573,
280 2097143,
281 4194301,
282 8388593,
283 16777213,
284 33554393,
285 67108859,
286 134217689,
287 268435399,
288 536870909,
289 1073741789,
290 2147483647 /* For 1 << 31 */
291 };
292  
293 static void
294 g_hash_table_set_shift (GHashTable *hash_table, gint shift)
295 {
296 gint i;
297 guint mask = 0;
298  
299 hash_table->size = 1 << shift;
300 hash_table->mod = prime_mod [shift];
301  
302 for (i = 0; i < shift; i++)
303 {
304 mask <<= 1;
305 mask |= 1;
306 }
307  
308 hash_table->mask = mask;
309 }
310  
311 static gint
312 g_hash_table_find_closest_shift (gint n)
313 {
314 gint i;
315  
316 for (i = 0; n; i++)
317 n >>= 1;
318  
319 return i;
320 }
321  
322 static void
323 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
324 {
325 gint shift;
326  
327 shift = g_hash_table_find_closest_shift (size);
328 shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
329  
330 g_hash_table_set_shift (hash_table, shift);
331 }
332  
333 /*
334 * g_hash_table_lookup_node:
335 * @hash_table: our #GHashTable
336 * @key: the key to lookup against
337 * @hash_return: key hash return location
338 *
339 * Performs a lookup in the hash table, preserving extra information
340 * usually needed for insertion.
341 *
342 * This function first computes the hash value of the key using the
343 * user's hash function.
344 *
345 * If an entry in the table matching @key is found then this function
346 * returns the index of that entry in the table, and if not, the
347 * index of an unused node (empty or tombstone) where the key can be
348 * inserted.
349 *
350 * The computed hash value is returned in the variable pointed to
351 * by @hash_return. This is to save insertions from having to compute
352 * the hash record again for the new record.
353 *
354 * Returns: index of the described node
355 */
356 static inline guint
357 g_hash_table_lookup_node (GHashTable *hash_table,
358 gconstpointer key,
359 guint *hash_return)
360 {
361 guint node_index;
362 guint node_hash;
363 guint hash_value;
364 guint first_tombstone = 0;
365 gboolean have_tombstone = FALSE;
366 guint step = 0;
367  
368 /* If this happens, then the application is probably doing too much work
369 * from a destroy notifier. The alternative would be to crash any second
370 * (as keys, etc. will be NULL).
371 * Applications need to either use g_hash_table_destroy, or ensure the hash
372 * table is empty prior to removing the last reference using g_hash_table_unref(). */
373 g_assert (hash_table->ref_count > 0);
374  
375 hash_value = hash_table->hash_func (key);
376 if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
377 hash_value = 2;
378  
379 *hash_return = hash_value;
380  
381 node_index = hash_value % hash_table->mod;
382 node_hash = hash_table->hashes[node_index];
383  
384 while (!HASH_IS_UNUSED (node_hash))
385 {
386 /* We first check if our full hash values
387 * are equal so we can avoid calling the full-blown
388 * key equality function in most cases.
389 */
390 if (node_hash == hash_value)
391 {
392 gpointer node_key = hash_table->keys[node_index];
393  
394 if (hash_table->key_equal_func)
395 {
396 if (hash_table->key_equal_func (node_key, key))
397 return node_index;
398 }
399 else if (node_key == key)
400 {
401 return node_index;
402 }
403 }
404 else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
405 {
406 first_tombstone = node_index;
407 have_tombstone = TRUE;
408 }
409  
410 step++;
411 node_index += step;
412 node_index &= hash_table->mask;
413 node_hash = hash_table->hashes[node_index];
414 }
415  
416 if (have_tombstone)
417 return first_tombstone;
418  
419 return node_index;
420 }
421  
422 /*
423 * g_hash_table_remove_node:
424 * @hash_table: our #GHashTable
425 * @node: pointer to node to remove
426 * @notify: %TRUE if the destroy notify handlers are to be called
427 *
428 * Removes a node from the hash table and updates the node count.
429 * The node is replaced by a tombstone. No table resize is performed.
430 *
431 * If @notify is %TRUE then the destroy notify functions are called
432 * for the key and value of the hash node.
433 */
434 static void
435 g_hash_table_remove_node (GHashTable *hash_table,
436 gint i,
437 gboolean notify)
438 {
439 gpointer key;
440 gpointer value;
441  
442 key = hash_table->keys[i];
443 value = hash_table->values[i];
444  
445 /* Erect tombstone */
446 hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;
447  
448 /* Be GC friendly */
449 hash_table->keys[i] = NULL;
450 hash_table->values[i] = NULL;
451  
452 hash_table->nnodes--;
453  
454 if (notify && hash_table->key_destroy_func)
455 hash_table->key_destroy_func (key);
456  
457 if (notify && hash_table->value_destroy_func)
458 hash_table->value_destroy_func (value);
459  
460 }
461  
462 /*
463 * g_hash_table_remove_all_nodes:
464 * @hash_table: our #GHashTable
465 * @notify: %TRUE if the destroy notify handlers are to be called
466 *
467 * Removes all nodes from the table. Since this may be a precursor to
468 * freeing the table entirely, no resize is performed.
469 *
470 * If @notify is %TRUE then the destroy notify functions are called
471 * for the key and value of the hash node.
472 */
473 static void
474 g_hash_table_remove_all_nodes (GHashTable *hash_table,
475 gboolean notify,
476 gboolean destruction)
477 {
478 int i;
479 gpointer key;
480 gpointer value;
481 gint old_size;
482 gpointer *old_keys;
483 gpointer *old_values;
484 guint *old_hashes;
485  
486 /* If the hash table is already empty, there is nothing to be done. */
487 if (hash_table->nnodes == 0)
488 return;
489  
490 hash_table->nnodes = 0;
491 hash_table->noccupied = 0;
492  
493 if (!notify ||
494 (hash_table->key_destroy_func == NULL &&
495 hash_table->value_destroy_func == NULL))
496 {
497 if (!destruction)
498 {
499 memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
500 memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
501 memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
502 }
503  
504 return;
505 }
506  
507 /* Keep the old storage space around to iterate over it. */
508 old_size = hash_table->size;
509 old_keys = hash_table->keys;
510 old_values = hash_table->values;
511 old_hashes = hash_table->hashes;
512  
513 /* Now create a new storage space; If the table is destroyed we can use the
514 * shortcut of not creating a new storage. This saves the allocation at the
515 * cost of not allowing any recursive access.
516 * However, the application doesn't own any reference anymore, so access
517 * is not allowed. If accesses are done, then either an assert or crash
518 * *will* happen. */
519 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
520 if (!destruction)
521 {
522 hash_table->keys = g_new0 (gpointer, hash_table->size);
523 hash_table->values = hash_table->keys;
524 hash_table->hashes = g_new0 (guint, hash_table->size);
525 }
526 else
527 {
528 hash_table->keys = NULL;
529 hash_table->values = NULL;
530 hash_table->hashes = NULL;
531 }
532  
533 for (i = 0; i < old_size; i++)
534 {
535 if (HASH_IS_REAL (old_hashes[i]))
536 {
537 key = old_keys[i];
538 value = old_values[i];
539  
540 old_hashes[i] = UNUSED_HASH_VALUE;
541 old_keys[i] = NULL;
542 old_values[i] = NULL;
543  
544 if (hash_table->key_destroy_func != NULL)
545 hash_table->key_destroy_func (key);
546  
547 if (hash_table->value_destroy_func != NULL)
548 hash_table->value_destroy_func (value);
549 }
550 }
551  
552 /* Destroy old storage space. */
553 if (old_keys != old_values)
554 g_free (old_values);
555  
556 g_free (old_keys);
557 g_free (old_hashes);
558 }
559  
560 /*
561 * g_hash_table_resize:
562 * @hash_table: our #GHashTable
563 *
564 * Resizes the hash table to the optimal size based on the number of
565 * nodes currently held. If you call this function then a resize will
566 * occur, even if one does not need to occur.
567 * Use g_hash_table_maybe_resize() instead.
568 *
569 * This function may "resize" the hash table to its current size, with
570 * the side effect of cleaning up tombstones and otherwise optimizing
571 * the probe sequences.
572 */
573 static void
574 g_hash_table_resize (GHashTable *hash_table)
575 {
576 gpointer *new_keys;
577 gpointer *new_values;
578 guint *new_hashes;
579 gint old_size;
580 gint i;
581  
582 old_size = hash_table->size;
583 g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
584  
585 new_keys = g_new0 (gpointer, hash_table->size);
586 if (hash_table->keys == hash_table->values)
587 new_values = new_keys;
588 else
589 new_values = g_new0 (gpointer, hash_table->size);
590 new_hashes = g_new0 (guint, hash_table->size);
591  
592 for (i = 0; i < old_size; i++)
593 {
594 guint node_hash = hash_table->hashes[i];
595 guint hash_val;
596 guint step = 0;
597  
598 if (!HASH_IS_REAL (node_hash))
599 continue;
600  
601 hash_val = node_hash % hash_table->mod;
602  
603 while (!HASH_IS_UNUSED (new_hashes[hash_val]))
604 {
605 step++;
606 hash_val += step;
607 hash_val &= hash_table->mask;
608 }
609  
610 new_hashes[hash_val] = hash_table->hashes[i];
611 new_keys[hash_val] = hash_table->keys[i];
612 new_values[hash_val] = hash_table->values[i];
613 }
614  
615 if (hash_table->keys != hash_table->values)
616 g_free (hash_table->values);
617  
618 g_free (hash_table->keys);
619 g_free (hash_table->hashes);
620  
621 hash_table->keys = new_keys;
622 hash_table->values = new_values;
623 hash_table->hashes = new_hashes;
624  
625 hash_table->noccupied = hash_table->nnodes;
626 }
627  
628 /*
629 * g_hash_table_maybe_resize:
630 * @hash_table: our #GHashTable
631 *
632 * Resizes the hash table, if needed.
633 *
634 * Essentially, calls g_hash_table_resize() if the table has strayed
635 * too far from its ideal size for its number of nodes.
636 */
637 static inline void
638 g_hash_table_maybe_resize (GHashTable *hash_table)
639 {
640 gint noccupied = hash_table->noccupied;
641 gint size = hash_table->size;
642  
643 if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
644 (size <= noccupied + (noccupied / 16)))
645 g_hash_table_resize (hash_table);
646 }
647  
648 /**
649 * g_hash_table_new:
650 * @hash_func: a function to create a hash value from a key
651 * @key_equal_func: a function to check two keys for equality
652 *
653 * Creates a new #GHashTable with a reference count of 1.
654 *
655 * Hash values returned by @hash_func are used to determine where keys
656 * are stored within the #GHashTable data structure. The g_direct_hash(),
657 * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash()
658 * functions are provided for some common types of keys.
659 * If @hash_func is %NULL, g_direct_hash() is used.
660 *
661 * @key_equal_func is used when looking up keys in the #GHashTable.
662 * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal()
663 * and g_str_equal() functions are provided for the most common types
664 * of keys. If @key_equal_func is %NULL, keys are compared directly in
665 * a similar fashion to g_direct_equal(), but without the overhead of
666 * a function call.
667 *
668 * Returns: a new #GHashTable
669 */
670 GHashTable *
671 g_hash_table_new (GHashFunc hash_func,
672 GEqualFunc key_equal_func)
673 {
674 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
675 }
676  
677  
678 /**
679 * g_hash_table_new_full:
680 * @hash_func: a function to create a hash value from a key
681 * @key_equal_func: a function to check two keys for equality
682 * @key_destroy_func: (nullable): a function to free the memory allocated for the key
683 * used when removing the entry from the #GHashTable, or %NULL
684 * if you don't want to supply such a function.
685 * @value_destroy_func: (nullable): a function to free the memory allocated for the
686 * value used when removing the entry from the #GHashTable, or %NULL
687 * if you don't want to supply such a function.
688 *
689 * Creates a new #GHashTable like g_hash_table_new() with a reference
690 * count of 1 and allows to specify functions to free the memory
691 * allocated for the key and value that get called when removing the
692 * entry from the #GHashTable.
693 *
694 * Since version 2.42 it is permissible for destroy notify functions to
695 * recursively remove further items from the hash table. This is only
696 * permissible if the application still holds a reference to the hash table.
697 * This means that you may need to ensure that the hash table is empty by
698 * calling g_hash_table_remove_all before releasing the last reference using
699 * g_hash_table_unref().
700 *
701 * Returns: a new #GHashTable
702 */
703 GHashTable *
704 g_hash_table_new_full (GHashFunc hash_func,
705 GEqualFunc key_equal_func,
706 GDestroyNotify key_destroy_func,
707 GDestroyNotify value_destroy_func)
708 {
709 GHashTable *hash_table;
710  
711 hash_table = g_slice_new (GHashTable);
712 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
713 hash_table->nnodes = 0;
714 hash_table->noccupied = 0;
715 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
716 hash_table->key_equal_func = key_equal_func;
717 hash_table->ref_count = 1;
718 #ifndef G_DISABLE_ASSERT
719 hash_table->version = 0;
720 #endif
721 hash_table->key_destroy_func = key_destroy_func;
722 hash_table->value_destroy_func = value_destroy_func;
723 hash_table->keys = g_new0 (gpointer, hash_table->size);
724 hash_table->values = hash_table->keys;
725 hash_table->hashes = g_new0 (guint, hash_table->size);
726  
727 return hash_table;
728 }
729  
730 /**
731 * g_hash_table_iter_init:
732 * @iter: an uninitialized #GHashTableIter
733 * @hash_table: a #GHashTable
734 *
735 * Initializes a key/value pair iterator and associates it with
736 * @hash_table. Modifying the hash table after calling this function
737 * invalidates the returned iterator.
738 * |[<!-- language="C" -->
739 * GHashTableIter iter;
740 * gpointer key, value;
741 *
742 * g_hash_table_iter_init (&iter, hash_table);
743 * while (g_hash_table_iter_next (&iter, &key, &value))
744 * {
745 * // do something with key and value
746 * }
747 * ]|
748 *
749 * Since: 2.16
750 */
751 void
752 g_hash_table_iter_init (GHashTableIter *iter,
753 GHashTable *hash_table)
754 {
755 RealIter *ri = (RealIter *) iter;
756  
757 g_return_if_fail (iter != NULL);
758 g_return_if_fail (hash_table != NULL);
759  
760 ri->hash_table = hash_table;
761 ri->position = -1;
762 #ifndef G_DISABLE_ASSERT
763 ri->version = hash_table->version;
764 #endif
765 }
766  
767 /**
768 * g_hash_table_iter_next:
769 * @iter: an initialized #GHashTableIter
770 * @key: (out) (optional): a location to store the key
771 * @value: (out) (nullable) (optional): a location to store the value
772 *
773 * Advances @iter and retrieves the key and/or value that are now
774 * pointed to as a result of this advancement. If %FALSE is returned,
775 * @key and @value are not set, and the iterator becomes invalid.
776 *
777 * Returns: %FALSE if the end of the #GHashTable has been reached.
778 *
779 * Since: 2.16
780 */
781 gboolean
782 g_hash_table_iter_next (GHashTableIter *iter,
783 gpointer *key,
784 gpointer *value)
785 {
786 RealIter *ri = (RealIter *) iter;
787 gint position;
788  
789 g_return_val_if_fail (iter != NULL, FALSE);
790 #ifndef G_DISABLE_ASSERT
791 g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
792 #endif
793 g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
794  
795 position = ri->position;
796  
797 do
798 {
799 position++;
800 if (position >= ri->hash_table->size)
801 {
802 ri->position = position;
803 return FALSE;
804 }
805 }
806 while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
807  
808 if (key != NULL)
809 *key = ri->hash_table->keys[position];
810 if (value != NULL)
811 *value = ri->hash_table->values[position];
812  
813 ri->position = position;
814 return TRUE;
815 }
816  
817 /**
818 * g_hash_table_iter_get_hash_table:
819 * @iter: an initialized #GHashTableIter
820 *
821 * Returns the #GHashTable associated with @iter.
822 *
823 * Returns: the #GHashTable associated with @iter.
824 *
825 * Since: 2.16
826 */
827 GHashTable *
828 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
829 {
830 g_return_val_if_fail (iter != NULL, NULL);
831  
832 return ((RealIter *) iter)->hash_table;
833 }
834  
835 static void
836 iter_remove_or_steal (RealIter *ri, gboolean notify)
837 {
838 g_return_if_fail (ri != NULL);
839 #ifndef G_DISABLE_ASSERT
840 g_return_if_fail (ri->version == ri->hash_table->version);
841 #endif
842 g_return_if_fail (ri->position >= 0);
843 g_return_if_fail (ri->position < ri->hash_table->size);
844  
845 g_hash_table_remove_node (ri->hash_table, ri->position, notify);
846  
847 #ifndef G_DISABLE_ASSERT
848 ri->version++;
849 ri->hash_table->version++;
850 #endif
851 }
852  
853 /**
854 * g_hash_table_iter_remove:
855 * @iter: an initialized #GHashTableIter
856 *
857 * Removes the key/value pair currently pointed to by the iterator
858 * from its associated #GHashTable. Can only be called after
859 * g_hash_table_iter_next() returned %TRUE, and cannot be called
860 * more than once for the same key/value pair.
861 *
862 * If the #GHashTable was created using g_hash_table_new_full(),
863 * the key and value are freed using the supplied destroy functions,
864 * otherwise you have to make sure that any dynamically allocated
865 * values are freed yourself.
866 *
867 * It is safe to continue iterating the #GHashTable afterward:
868 * |[<!-- language="C" -->
869 * while (g_hash_table_iter_next (&iter, &key, &value))
870 * {
871 * if (condition)
872 * g_hash_table_iter_remove (&iter);
873 * }
874 * ]|
875 *
876 * Since: 2.16
877 */
878 void
879 g_hash_table_iter_remove (GHashTableIter *iter)
880 {
881 iter_remove_or_steal ((RealIter *) iter, TRUE);
882 }
883  
884 /*
885 * g_hash_table_insert_node:
886 * @hash_table: our #GHashTable
887 * @node_index: pointer to node to insert/replace
888 * @key_hash: key hash
889 * @key: (nullable): key to replace with, or %NULL
890 * @value: value to replace with
891 * @keep_new_key: whether to replace the key in the node with @key
892 * @reusing_key: whether @key was taken out of the existing node
893 *
894 * Inserts a value at @node_index in the hash table and updates it.
895 *
896 * If @key has been taken out of the existing node (ie it is not
897 * passed in via a g_hash_table_insert/replace) call, then @reusing_key
898 * should be %TRUE.
899 *
900 * Returns: %TRUE if the key did not exist yet
901 */
902 static gboolean
903 g_hash_table_insert_node (GHashTable *hash_table,
904 guint node_index,
905 guint key_hash,
906 gpointer new_key,
907 gpointer new_value,
908 gboolean keep_new_key,
909 gboolean reusing_key)
910 {
911 gboolean already_exists;
912 guint old_hash;
913 gpointer key_to_free = NULL;
914 gpointer value_to_free = NULL;
915  
916 old_hash = hash_table->hashes[node_index];
917 already_exists = HASH_IS_REAL (old_hash);
918  
919 /* Proceed in three steps. First, deal with the key because it is the
920 * most complicated. Then consider if we need to split the table in
921 * two (because writing the value will result in the set invariant
922 * becoming broken). Then deal with the value.
923 *
924 * There are three cases for the key:
925 *
926 * - entry already exists in table, reusing key:
927 * free the just-passed-in new_key and use the existing value
928 *
929 * - entry already exists in table, not reusing key:
930 * free the entry in the table, use the new key
931 *
932 * - entry not already in table:
933 * use the new key, free nothing
934 *
935 * We update the hash at the same time...
936 */
937 if (already_exists)
938 {
939 /* Note: we must record the old value before writing the new key
940 * because we might change the value in the event that the two
941 * arrays are shared.
942 */
943 value_to_free = hash_table->values[node_index];
944  
945 if (keep_new_key)
946 {
947 key_to_free = hash_table->keys[node_index];
948 hash_table->keys[node_index] = new_key;
949 }
950 else
951 key_to_free = new_key;
952 }
953 else
954 {
955 hash_table->hashes[node_index] = key_hash;
956 hash_table->keys[node_index] = new_key;
957 }
958  
959 /* Step two: check if the value that we are about to write to the
960 * table is the same as the key in the same position. If it's not,
961 * split the table.
962 */
963 if (G_UNLIKELY (hash_table->keys == hash_table->values && hash_table->keys[node_index] != new_value))
964 hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
965  
966 /* Step 3: Actually do the write */
967 hash_table->values[node_index] = new_value;
968  
969 /* Now, the bookkeeping... */
970 if (!already_exists)
971 {
972 hash_table->nnodes++;
973  
974 if (HASH_IS_UNUSED (old_hash))
975 {
976 /* We replaced an empty node, and not a tombstone */
977 hash_table->noccupied++;
978 g_hash_table_maybe_resize (hash_table);
979 }
980  
981 #ifndef G_DISABLE_ASSERT
982 hash_table->version++;
983 #endif
984 }
985  
986 if (already_exists)
987 {
988 if (hash_table->key_destroy_func && !reusing_key)
989 (* hash_table->key_destroy_func) (key_to_free);
990 if (hash_table->value_destroy_func)
991 (* hash_table->value_destroy_func) (value_to_free);
992 }
993  
994 return !already_exists;
995 }
996  
997 /**
998 * g_hash_table_iter_replace:
999 * @iter: an initialized #GHashTableIter
1000 * @value: the value to replace with
1001 *
1002 * Replaces the value currently pointed to by the iterator
1003 * from its associated #GHashTable. Can only be called after
1004 * g_hash_table_iter_next() returned %TRUE.
1005 *
1006 * If you supplied a @value_destroy_func when creating the
1007 * #GHashTable, the old value is freed using that function.
1008 *
1009 * Since: 2.30
1010 */
1011 void
1012 g_hash_table_iter_replace (GHashTableIter *iter,
1013 gpointer value)
1014 {
1015 RealIter *ri;
1016 guint node_hash;
1017 gpointer key;
1018  
1019 ri = (RealIter *) iter;
1020  
1021 g_return_if_fail (ri != NULL);
1022 #ifndef G_DISABLE_ASSERT
1023 g_return_if_fail (ri->version == ri->hash_table->version);
1024 #endif
1025 g_return_if_fail (ri->position >= 0);
1026 g_return_if_fail (ri->position < ri->hash_table->size);
1027  
1028 node_hash = ri->hash_table->hashes[ri->position];
1029 key = ri->hash_table->keys[ri->position];
1030  
1031 g_hash_table_insert_node (ri->hash_table, ri->position, node_hash, key, value, TRUE, TRUE);
1032  
1033 #ifndef G_DISABLE_ASSERT
1034 ri->version++;
1035 ri->hash_table->version++;
1036 #endif
1037 }
1038  
1039 /**
1040 * g_hash_table_iter_steal:
1041 * @iter: an initialized #GHashTableIter
1042 *
1043 * Removes the key/value pair currently pointed to by the
1044 * iterator from its associated #GHashTable, without calling
1045 * the key and value destroy functions. Can only be called
1046 * after g_hash_table_iter_next() returned %TRUE, and cannot
1047 * be called more than once for the same key/value pair.
1048 *
1049 * Since: 2.16
1050 */
1051 void
1052 g_hash_table_iter_steal (GHashTableIter *iter)
1053 {
1054 iter_remove_or_steal ((RealIter *) iter, FALSE);
1055 }
1056  
1057  
1058 /**
1059 * g_hash_table_ref:
1060 * @hash_table: a valid #GHashTable
1061 *
1062 * Atomically increments the reference count of @hash_table by one.
1063 * This function is MT-safe and may be called from any thread.
1064 *
1065 * Returns: the passed in #GHashTable
1066 *
1067 * Since: 2.10
1068 */
1069 GHashTable *
1070 g_hash_table_ref (GHashTable *hash_table)
1071 {
1072 g_return_val_if_fail (hash_table != NULL, NULL);
1073  
1074 g_atomic_int_inc (&hash_table->ref_count);
1075  
1076 return hash_table;
1077 }
1078  
1079 /**
1080 * g_hash_table_unref:
1081 * @hash_table: a valid #GHashTable
1082 *
1083 * Atomically decrements the reference count of @hash_table by one.
1084 * If the reference count drops to 0, all keys and values will be
1085 * destroyed, and all memory allocated by the hash table is released.
1086 * This function is MT-safe and may be called from any thread.
1087 *
1088 * Since: 2.10
1089 */
1090 void
1091 g_hash_table_unref (GHashTable *hash_table)
1092 {
1093 g_return_if_fail (hash_table != NULL);
1094  
1095 if (g_atomic_int_dec_and_test (&hash_table->ref_count))
1096 {
1097 g_hash_table_remove_all_nodes (hash_table, TRUE, TRUE);
1098 if (hash_table->keys != hash_table->values)
1099 g_free (hash_table->values);
1100 g_free (hash_table->keys);
1101 g_free (hash_table->hashes);
1102 g_slice_free (GHashTable, hash_table);
1103 }
1104 }
1105  
1106 /**
1107 * g_hash_table_destroy:
1108 * @hash_table: a #GHashTable
1109 *
1110 * Destroys all keys and values in the #GHashTable and decrements its
1111 * reference count by 1. If keys and/or values are dynamically allocated,
1112 * you should either free them first or create the #GHashTable with destroy
1113 * notifiers using g_hash_table_new_full(). In the latter case the destroy
1114 * functions you supplied will be called on all keys and values during the
1115 * destruction phase.
1116 */
1117 void
1118 g_hash_table_destroy (GHashTable *hash_table)
1119 {
1120 g_return_if_fail (hash_table != NULL);
1121  
1122 g_hash_table_remove_all (hash_table);
1123 g_hash_table_unref (hash_table);
1124 }
1125  
1126 /**
1127 * g_hash_table_lookup:
1128 * @hash_table: a #GHashTable
1129 * @key: the key to look up
1130 *
1131 * Looks up a key in a #GHashTable. Note that this function cannot
1132 * distinguish between a key that is not present and one which is present
1133 * and has the value %NULL. If you need this distinction, use
1134 * g_hash_table_lookup_extended().
1135 *
1136 * Returns: (nullable): the associated value, or %NULL if the key is not found
1137 */
1138 gpointer
1139 g_hash_table_lookup (GHashTable *hash_table,
1140 gconstpointer key)
1141 {
1142 guint node_index;
1143 guint node_hash;
1144  
1145 g_return_val_if_fail (hash_table != NULL, NULL);
1146  
1147 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1148  
1149 return HASH_IS_REAL (hash_table->hashes[node_index])
1150 ? hash_table->values[node_index]
1151 : NULL;
1152 }
1153  
1154 /**
1155 * g_hash_table_lookup_extended:
1156 * @hash_table: a #GHashTable
1157 * @lookup_key: the key to look up
1158 * @orig_key: (out) (optional) (nullable): return location for the original key
1159 * @value: (out) (optional) (nullable): return location for the value associated
1160 * with the key
1161 *
1162 * Looks up a key in the #GHashTable, returning the original key and the
1163 * associated value and a #gboolean which is %TRUE if the key was found. This
1164 * is useful if you need to free the memory allocated for the original key,
1165 * for example before calling g_hash_table_remove().
1166 *
1167 * You can actually pass %NULL for @lookup_key to test
1168 * whether the %NULL key exists, provided the hash and equal functions
1169 * of @hash_table are %NULL-safe.
1170 *
1171 * Returns: %TRUE if the key was found in the #GHashTable
1172 */
1173 gboolean
1174 g_hash_table_lookup_extended (GHashTable *hash_table,
1175 gconstpointer lookup_key,
1176 gpointer *orig_key,
1177 gpointer *value)
1178 {
1179 guint node_index;
1180 guint node_hash;
1181  
1182 g_return_val_if_fail (hash_table != NULL, FALSE);
1183  
1184 node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1185  
1186 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1187 return FALSE;
1188  
1189 if (orig_key)
1190 *orig_key = hash_table->keys[node_index];
1191  
1192 if (value)
1193 *value = hash_table->values[node_index];
1194  
1195 return TRUE;
1196 }
1197  
1198 /*
1199 * g_hash_table_insert_internal:
1200 * @hash_table: our #GHashTable
1201 * @key: the key to insert
1202 * @value: the value to insert
1203 * @keep_new_key: if %TRUE and this key already exists in the table
1204 * then call the destroy notify function on the old key. If %FALSE
1205 * then call the destroy notify function on the new key.
1206 *
1207 * Implements the common logic for the g_hash_table_insert() and
1208 * g_hash_table_replace() functions.
1209 *
1210 * Do a lookup of @key. If it is found, replace it with the new
1211 * @value (and perhaps the new @key). If it is not found, create
1212 * a new node.
1213 *
1214 * Returns: %TRUE if the key did not exist yet
1215 */
1216 static gboolean
1217 g_hash_table_insert_internal (GHashTable *hash_table,
1218 gpointer key,
1219 gpointer value,
1220 gboolean keep_new_key)
1221 {
1222 guint key_hash;
1223 guint node_index;
1224  
1225 g_return_val_if_fail (hash_table != NULL, FALSE);
1226  
1227 node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
1228  
1229 return g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key, FALSE);
1230 }
1231  
1232 /**
1233 * g_hash_table_insert:
1234 * @hash_table: a #GHashTable
1235 * @key: a key to insert
1236 * @value: the value to associate with the key
1237 *
1238 * Inserts a new key and value into a #GHashTable.
1239 *
1240 * If the key already exists in the #GHashTable its current
1241 * value is replaced with the new value. If you supplied a
1242 * @value_destroy_func when creating the #GHashTable, the old
1243 * value is freed using that function. If you supplied a
1244 * @key_destroy_func when creating the #GHashTable, the passed
1245 * key is freed using that function.
1246 *
1247 * Returns: %TRUE if the key did not exist yet
1248 */
1249 gboolean
1250 g_hash_table_insert (GHashTable *hash_table,
1251 gpointer key,
1252 gpointer value)
1253 {
1254 return g_hash_table_insert_internal (hash_table, key, value, FALSE);
1255 }
1256  
1257 /**
1258 * g_hash_table_replace:
1259 * @hash_table: a #GHashTable
1260 * @key: a key to insert
1261 * @value: the value to associate with the key
1262 *
1263 * Inserts a new key and value into a #GHashTable similar to
1264 * g_hash_table_insert(). The difference is that if the key
1265 * already exists in the #GHashTable, it gets replaced by the
1266 * new key. If you supplied a @value_destroy_func when creating
1267 * the #GHashTable, the old value is freed using that function.
1268 * If you supplied a @key_destroy_func when creating the
1269 * #GHashTable, the old key is freed using that function.
1270 *
1271 * Returns: %TRUE if the key did not exist yet
1272 */
1273 gboolean
1274 g_hash_table_replace (GHashTable *hash_table,
1275 gpointer key,
1276 gpointer value)
1277 {
1278 return g_hash_table_insert_internal (hash_table, key, value, TRUE);
1279 }
1280  
1281 /**
1282 * g_hash_table_add:
1283 * @hash_table: a #GHashTable
1284 * @key: a key to insert
1285 *
1286 * This is a convenience function for using a #GHashTable as a set. It
1287 * is equivalent to calling g_hash_table_replace() with @key as both the
1288 * key and the value.
1289 *
1290 * When a hash table only ever contains keys that have themselves as the
1291 * corresponding value it is able to be stored more efficiently. See
1292 * the discussion in the section description.
1293 *
1294 * Returns: %TRUE if the key did not exist yet
1295 *
1296 * Since: 2.32
1297 */
1298 gboolean
1299 g_hash_table_add (GHashTable *hash_table,
1300 gpointer key)
1301 {
1302 return g_hash_table_insert_internal (hash_table, key, key, TRUE);
1303 }
1304  
1305 /**
1306 * g_hash_table_contains:
1307 * @hash_table: a #GHashTable
1308 * @key: a key to check
1309 *
1310 * Checks if @key is in @hash_table.
1311 *
1312 * Returns: %TRUE if @key is in @hash_table, %FALSE otherwise.
1313 *
1314 * Since: 2.32
1315 **/
1316 gboolean
1317 g_hash_table_contains (GHashTable *hash_table,
1318 gconstpointer key)
1319 {
1320 guint node_index;
1321 guint node_hash;
1322  
1323 g_return_val_if_fail (hash_table != NULL, FALSE);
1324  
1325 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1326  
1327 return HASH_IS_REAL (hash_table->hashes[node_index]);
1328 }
1329  
1330 /*
1331 * g_hash_table_remove_internal:
1332 * @hash_table: our #GHashTable
1333 * @key: the key to remove
1334 * @notify: %TRUE if the destroy notify handlers are to be called
1335 * Returns: %TRUE if a node was found and removed, else %FALSE
1336 *
1337 * Implements the common logic for the g_hash_table_remove() and
1338 * g_hash_table_steal() functions.
1339 *
1340 * Do a lookup of @key and remove it if it is found, calling the
1341 * destroy notify handlers only if @notify is %TRUE.
1342 */
1343 static gboolean
1344 g_hash_table_remove_internal (GHashTable *hash_table,
1345 gconstpointer key,
1346 gboolean notify)
1347 {
1348 guint node_index;
1349 guint node_hash;
1350  
1351 g_return_val_if_fail (hash_table != NULL, FALSE);
1352  
1353 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1354  
1355 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1356 return FALSE;
1357  
1358 g_hash_table_remove_node (hash_table, node_index, notify);
1359 g_hash_table_maybe_resize (hash_table);
1360  
1361 #ifndef G_DISABLE_ASSERT
1362 hash_table->version++;
1363 #endif
1364  
1365 return TRUE;
1366 }
1367  
1368 /**
1369 * g_hash_table_remove:
1370 * @hash_table: a #GHashTable
1371 * @key: the key to remove
1372 *
1373 * Removes a key and its associated value from a #GHashTable.
1374 *
1375 * If the #GHashTable was created using g_hash_table_new_full(), the
1376 * key and value are freed using the supplied destroy functions, otherwise
1377 * you have to make sure that any dynamically allocated values are freed
1378 * yourself.
1379 *
1380 * Returns: %TRUE if the key was found and removed from the #GHashTable
1381 */
1382 gboolean
1383 g_hash_table_remove (GHashTable *hash_table,
1384 gconstpointer key)
1385 {
1386 return g_hash_table_remove_internal (hash_table, key, TRUE);
1387 }
1388  
1389 /**
1390 * g_hash_table_steal:
1391 * @hash_table: a #GHashTable
1392 * @key: the key to remove
1393 *
1394 * Removes a key and its associated value from a #GHashTable without
1395 * calling the key and value destroy functions.
1396 *
1397 * Returns: %TRUE if the key was found and removed from the #GHashTable
1398 */
1399 gboolean
1400 g_hash_table_steal (GHashTable *hash_table,
1401 gconstpointer key)
1402 {
1403 return g_hash_table_remove_internal (hash_table, key, FALSE);
1404 }
1405  
1406 /**
1407 * g_hash_table_remove_all:
1408 * @hash_table: a #GHashTable
1409 *
1410 * Removes all keys and their associated values from a #GHashTable.
1411 *
1412 * If the #GHashTable was created using g_hash_table_new_full(),
1413 * the keys and values are freed using the supplied destroy functions,
1414 * otherwise you have to make sure that any dynamically allocated
1415 * values are freed yourself.
1416 *
1417 * Since: 2.12
1418 */
1419 void
1420 g_hash_table_remove_all (GHashTable *hash_table)
1421 {
1422 g_return_if_fail (hash_table != NULL);
1423  
1424 #ifndef G_DISABLE_ASSERT
1425 if (hash_table->nnodes != 0)
1426 hash_table->version++;
1427 #endif
1428  
1429 g_hash_table_remove_all_nodes (hash_table, TRUE, FALSE);
1430 g_hash_table_maybe_resize (hash_table);
1431 }
1432  
1433 /**
1434 * g_hash_table_steal_all:
1435 * @hash_table: a #GHashTable
1436 *
1437 * Removes all keys and their associated values from a #GHashTable
1438 * without calling the key and value destroy functions.
1439 *
1440 * Since: 2.12
1441 */
1442 void
1443 g_hash_table_steal_all (GHashTable *hash_table)
1444 {
1445 g_return_if_fail (hash_table != NULL);
1446  
1447 #ifndef G_DISABLE_ASSERT
1448 if (hash_table->nnodes != 0)
1449 hash_table->version++;
1450 #endif
1451  
1452 g_hash_table_remove_all_nodes (hash_table, FALSE, FALSE);
1453 g_hash_table_maybe_resize (hash_table);
1454 }
1455  
1456 /*
1457 * g_hash_table_foreach_remove_or_steal:
1458 * @hash_table: a #GHashTable
1459 * @func: the user's callback function
1460 * @user_data: data for @func
1461 * @notify: %TRUE if the destroy notify handlers are to be called
1462 *
1463 * Implements the common logic for g_hash_table_foreach_remove()
1464 * and g_hash_table_foreach_steal().
1465 *
1466 * Iterates over every node in the table, calling @func with the key
1467 * and value of the node (and @user_data). If @func returns %TRUE the
1468 * node is removed from the table.
1469 *
1470 * If @notify is true then the destroy notify handlers will be called
1471 * for each removed node.
1472 */
1473 static guint
1474 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1475 GHRFunc func,
1476 gpointer user_data,
1477 gboolean notify)
1478 {
1479 guint deleted = 0;
1480 gint i;
1481 #ifndef G_DISABLE_ASSERT
1482 gint version = hash_table->version;
1483 #endif
1484  
1485 for (i = 0; i < hash_table->size; i++)
1486 {
1487 guint node_hash = hash_table->hashes[i];
1488 gpointer node_key = hash_table->keys[i];
1489 gpointer node_value = hash_table->values[i];
1490  
1491 if (HASH_IS_REAL (node_hash) &&
1492 (* func) (node_key, node_value, user_data))
1493 {
1494 g_hash_table_remove_node (hash_table, i, notify);
1495 deleted++;
1496 }
1497  
1498 #ifndef G_DISABLE_ASSERT
1499 g_return_val_if_fail (version == hash_table->version, 0);
1500 #endif
1501 }
1502  
1503 g_hash_table_maybe_resize (hash_table);
1504  
1505 #ifndef G_DISABLE_ASSERT
1506 if (deleted > 0)
1507 hash_table->version++;
1508 #endif
1509  
1510 return deleted;
1511 }
1512  
1513 /**
1514 * g_hash_table_foreach_remove:
1515 * @hash_table: a #GHashTable
1516 * @func: the function to call for each key/value pair
1517 * @user_data: user data to pass to the function
1518 *
1519 * Calls the given function for each key/value pair in the
1520 * #GHashTable. If the function returns %TRUE, then the key/value
1521 * pair is removed from the #GHashTable. If you supplied key or
1522 * value destroy functions when creating the #GHashTable, they are
1523 * used to free the memory allocated for the removed keys and values.
1524 *
1525 * See #GHashTableIter for an alternative way to loop over the
1526 * key/value pairs in the hash table.
1527 *
1528 * Returns: the number of key/value pairs removed
1529 */
1530 guint
1531 g_hash_table_foreach_remove (GHashTable *hash_table,
1532 GHRFunc func,
1533 gpointer user_data)
1534 {
1535 g_return_val_if_fail (hash_table != NULL, 0);
1536 g_return_val_if_fail (func != NULL, 0);
1537  
1538 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1539 }
1540  
1541 /**
1542 * g_hash_table_foreach_steal:
1543 * @hash_table: a #GHashTable
1544 * @func: the function to call for each key/value pair
1545 * @user_data: user data to pass to the function
1546 *
1547 * Calls the given function for each key/value pair in the
1548 * #GHashTable. If the function returns %TRUE, then the key/value
1549 * pair is removed from the #GHashTable, but no key or value
1550 * destroy functions are called.
1551 *
1552 * See #GHashTableIter for an alternative way to loop over the
1553 * key/value pairs in the hash table.
1554 *
1555 * Returns: the number of key/value pairs removed.
1556 */
1557 guint
1558 g_hash_table_foreach_steal (GHashTable *hash_table,
1559 GHRFunc func,
1560 gpointer user_data)
1561 {
1562 g_return_val_if_fail (hash_table != NULL, 0);
1563 g_return_val_if_fail (func != NULL, 0);
1564  
1565 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1566 }
1567  
1568 /**
1569 * g_hash_table_foreach:
1570 * @hash_table: a #GHashTable
1571 * @func: the function to call for each key/value pair
1572 * @user_data: user data to pass to the function
1573 *
1574 * Calls the given function for each of the key/value pairs in the
1575 * #GHashTable. The function is passed the key and value of each
1576 * pair, and the given @user_data parameter. The hash table may not
1577 * be modified while iterating over it (you can't add/remove
1578 * items). To remove all items matching a predicate, use
1579 * g_hash_table_foreach_remove().
1580 *
1581 * See g_hash_table_find() for performance caveats for linear
1582 * order searches in contrast to g_hash_table_lookup().
1583 */
1584 void
1585 g_hash_table_foreach (GHashTable *hash_table,
1586 GHFunc func,
1587 gpointer user_data)
1588 {
1589 gint i;
1590 #ifndef G_DISABLE_ASSERT
1591 gint version;
1592 #endif
1593  
1594 g_return_if_fail (hash_table != NULL);
1595 g_return_if_fail (func != NULL);
1596  
1597 #ifndef G_DISABLE_ASSERT
1598 version = hash_table->version;
1599 #endif
1600  
1601 for (i = 0; i < hash_table->size; i++)
1602 {
1603 guint node_hash = hash_table->hashes[i];
1604 gpointer node_key = hash_table->keys[i];
1605 gpointer node_value = hash_table->values[i];
1606  
1607 if (HASH_IS_REAL (node_hash))
1608 (* func) (node_key, node_value, user_data);
1609  
1610 #ifndef G_DISABLE_ASSERT
1611 g_return_if_fail (version == hash_table->version);
1612 #endif
1613 }
1614 }
1615  
1616 /**
1617 * g_hash_table_find:
1618 * @hash_table: a #GHashTable
1619 * @predicate: function to test the key/value pairs for a certain property
1620 * @user_data: user data to pass to the function
1621 *
1622 * Calls the given function for key/value pairs in the #GHashTable
1623 * until @predicate returns %TRUE. The function is passed the key
1624 * and value of each pair, and the given @user_data parameter. The
1625 * hash table may not be modified while iterating over it (you can't
1626 * add/remove items).
1627 *
1628 * Note, that hash tables are really only optimized for forward
1629 * lookups, i.e. g_hash_table_lookup(). So code that frequently issues
1630 * g_hash_table_find() or g_hash_table_foreach() (e.g. in the order of
1631 * once per every entry in a hash table) should probably be reworked
1632 * to use additional or different data structures for reverse lookups
1633 * (keep in mind that an O(n) find/foreach operation issued for all n
1634 * values in a hash table ends up needing O(n*n) operations).
1635 *
1636 * Returns: (nullable): The value of the first key/value pair is returned,
1637 * for which @predicate evaluates to %TRUE. If no pair with the
1638 * requested property is found, %NULL is returned.
1639 *
1640 * Since: 2.4
1641 */
1642 gpointer
1643 g_hash_table_find (GHashTable *hash_table,
1644 GHRFunc predicate,
1645 gpointer user_data)
1646 {
1647 gint i;
1648 #ifndef G_DISABLE_ASSERT
1649 gint version;
1650 #endif
1651 gboolean match;
1652  
1653 g_return_val_if_fail (hash_table != NULL, NULL);
1654 g_return_val_if_fail (predicate != NULL, NULL);
1655  
1656 #ifndef G_DISABLE_ASSERT
1657 version = hash_table->version;
1658 #endif
1659  
1660 match = FALSE;
1661  
1662 for (i = 0; i < hash_table->size; i++)
1663 {
1664 guint node_hash = hash_table->hashes[i];
1665 gpointer node_key = hash_table->keys[i];
1666 gpointer node_value = hash_table->values[i];
1667  
1668 if (HASH_IS_REAL (node_hash))
1669 match = predicate (node_key, node_value, user_data);
1670  
1671 #ifndef G_DISABLE_ASSERT
1672 g_return_val_if_fail (version == hash_table->version, NULL);
1673 #endif
1674  
1675 if (match)
1676 return node_value;
1677 }
1678  
1679 return NULL;
1680 }
1681  
1682 /**
1683 * g_hash_table_size:
1684 * @hash_table: a #GHashTable
1685 *
1686 * Returns the number of elements contained in the #GHashTable.
1687 *
1688 * Returns: the number of key/value pairs in the #GHashTable.
1689 */
1690 guint
1691 g_hash_table_size (GHashTable *hash_table)
1692 {
1693 g_return_val_if_fail (hash_table != NULL, 0);
1694  
1695 return hash_table->nnodes;
1696 }
1697  
1698 /**
1699 * g_hash_table_get_keys:
1700 * @hash_table: a #GHashTable
1701 *
1702 * Retrieves every key inside @hash_table. The returned data is valid
1703 * until changes to the hash release those keys.
1704 *
1705 * This iterates over every entry in the hash table to build its return value.
1706 * To iterate over the entries in a #GHashTable more efficiently, use a
1707 * #GHashTableIter.
1708 *
1709 * Returns: (transfer container): a #GList containing all the keys
1710 * inside the hash table. The content of the list is owned by the
1711 * hash table and should not be modified or freed. Use g_list_free()
1712 * when done using the list.
1713 *
1714 * Since: 2.14
1715 */
1716 GList *
1717 g_hash_table_get_keys (GHashTable *hash_table)
1718 {
1719 gint i;
1720 GList *retval;
1721  
1722 g_return_val_if_fail (hash_table != NULL, NULL);
1723  
1724 retval = NULL;
1725 for (i = 0; i < hash_table->size; i++)
1726 {
1727 if (HASH_IS_REAL (hash_table->hashes[i]))
1728 retval = g_list_prepend (retval, hash_table->keys[i]);
1729 }
1730  
1731 return retval;
1732 }
1733  
1734 /**
1735 * g_hash_table_get_keys_as_array:
1736 * @hash_table: a #GHashTable
1737 * @length: (out): the length of the returned array
1738 *
1739 * Retrieves every key inside @hash_table, as an array.
1740 *
1741 * The returned array is %NULL-terminated but may contain %NULL as a
1742 * key. Use @length to determine the true length if it's possible that
1743 * %NULL was used as the value for a key.
1744 *
1745 * Note: in the common case of a string-keyed #GHashTable, the return
1746 * value of this function can be conveniently cast to (const gchar **).
1747 *
1748 * This iterates over every entry in the hash table to build its return value.
1749 * To iterate over the entries in a #GHashTable more efficiently, use a
1750 * #GHashTableIter.
1751 *
1752 * You should always free the return result with g_free(). In the
1753 * above-mentioned case of a string-keyed hash table, it may be
1754 * appropriate to use g_strfreev() if you call g_hash_table_steal_all()
1755 * first to transfer ownership of the keys.
1756 *
1757 * Returns: (array length=length) (transfer container): a
1758 * %NULL-terminated array containing each key from the table.
1759 *
1760 * Since: 2.40
1761 **/
1762 gpointer *
1763 g_hash_table_get_keys_as_array (GHashTable *hash_table,
1764 guint *length)
1765 {
1766 gpointer *result;
1767 guint i, j = 0;
1768  
1769 result = g_new (gpointer, hash_table->nnodes + 1);
1770 for (i = 0; i < hash_table->size; i++)
1771 {
1772 if (HASH_IS_REAL (hash_table->hashes[i]))
1773 result[j++] = hash_table->keys[i];
1774 }
1775 g_assert_cmpint (j, ==, hash_table->nnodes);
1776 result[j] = NULL;
1777  
1778 if (length)
1779 *length = j;
1780  
1781 return result;
1782 }
1783  
1784 /**
1785 * g_hash_table_get_values:
1786 * @hash_table: a #GHashTable
1787 *
1788 * Retrieves every value inside @hash_table. The returned data
1789 * is valid until @hash_table is modified.
1790 *
1791 * This iterates over every entry in the hash table to build its return value.
1792 * To iterate over the entries in a #GHashTable more efficiently, use a
1793 * #GHashTableIter.
1794 *
1795 * Returns: (transfer container): a #GList containing all the values
1796 * inside the hash table. The content of the list is owned by the
1797 * hash table and should not be modified or freed. Use g_list_free()
1798 * when done using the list.
1799 *
1800 * Since: 2.14
1801 */
1802 GList *
1803 g_hash_table_get_values (GHashTable *hash_table)
1804 {
1805 gint i;
1806 GList *retval;
1807  
1808 g_return_val_if_fail (hash_table != NULL, NULL);
1809  
1810 retval = NULL;
1811 for (i = 0; i < hash_table->size; i++)
1812 {
1813 if (HASH_IS_REAL (hash_table->hashes[i]))
1814 retval = g_list_prepend (retval, hash_table->values[i]);
1815 }
1816  
1817 return retval;
1818 }
1819  
1820 /* Hash functions.
1821 */
1822  
1823 /**
1824 * g_str_equal:
1825 * @v1: (not nullable): a key
1826 * @v2: (not nullable): a key to compare with @v1
1827 *
1828 * Compares two strings for byte-by-byte equality and returns %TRUE
1829 * if they are equal. It can be passed to g_hash_table_new() as the
1830 * @key_equal_func parameter, when using non-%NULL strings as keys in a
1831 * #GHashTable.
1832 *
1833 * Note that this function is primarily meant as a hash table comparison
1834 * function. For a general-purpose, %NULL-safe string comparison function,
1835 * see g_strcmp0().
1836 *
1837 * Returns: %TRUE if the two keys match
1838 */
1839 gboolean
1840 g_str_equal (gconstpointer v1,
1841 gconstpointer v2)
1842 {
1843 const gchar *string1 = v1;
1844 const gchar *string2 = v2;
1845  
1846 return strcmp (string1, string2) == 0;
1847 }
1848  
1849 /**
1850 * g_str_hash:
1851 * @v: (not nullable): a string key
1852 *
1853 * Converts a string to a hash value.
1854 *
1855 * This function implements the widely used "djb" hash apparently
1856 * posted by Daniel Bernstein to comp.lang.c some time ago. The 32
1857 * bit unsigned hash value starts at 5381 and for each byte 'c' in
1858 * the string, is updated: `hash = hash * 33 + c`. This function
1859 * uses the signed value of each byte.
1860 *
1861 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1862 * when using non-%NULL strings as keys in a #GHashTable.
1863 *
1864 * Note that this function may not be a perfect fit for all use cases.
1865 * For example, it produces some hash collisions with strings as short
1866 * as 2.
1867 *
1868 * Returns: a hash value corresponding to the key
1869 */
1870 guint
1871 g_str_hash (gconstpointer v)
1872 {
1873 const signed char *p;
1874 guint32 h = 5381;
1875  
1876 for (p = v; *p != '\0'; p++)
1877 h = (h << 5) + h + *p;
1878  
1879 return h;
1880 }
1881  
1882 /**
1883 * g_direct_hash:
1884 * @v: (nullable): a #gpointer key
1885 *
1886 * Converts a gpointer to a hash value.
1887 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1888 * when using opaque pointers compared by pointer value as keys in a
1889 * #GHashTable.
1890 *
1891 * This hash function is also appropriate for keys that are integers
1892 * stored in pointers, such as `GINT_TO_POINTER (n)`.
1893 *
1894 * Returns: a hash value corresponding to the key.
1895 */
1896 guint
1897 g_direct_hash (gconstpointer v)
1898 {
1899 return GPOINTER_TO_UINT (v);
1900 }
1901  
1902 /**
1903 * g_direct_equal:
1904 * @v1: (nullable): a key
1905 * @v2: (nullable): a key to compare with @v1
1906 *
1907 * Compares two #gpointer arguments and returns %TRUE if they are equal.
1908 * It can be passed to g_hash_table_new() as the @key_equal_func
1909 * parameter, when using opaque pointers compared by pointer value as
1910 * keys in a #GHashTable.
1911 *
1912 * This equality function is also appropriate for keys that are integers
1913 * stored in pointers, such as `GINT_TO_POINTER (n)`.
1914 *
1915 * Returns: %TRUE if the two keys match.
1916 */
1917 gboolean
1918 g_direct_equal (gconstpointer v1,
1919 gconstpointer v2)
1920 {
1921 return v1 == v2;
1922 }
1923  
1924 /**
1925 * g_int_equal:
1926 * @v1: (not nullable): a pointer to a #gint key
1927 * @v2: (not nullable): a pointer to a #gint key to compare with @v1
1928 *
1929 * Compares the two #gint values being pointed to and returns
1930 * %TRUE if they are equal.
1931 * It can be passed to g_hash_table_new() as the @key_equal_func
1932 * parameter, when using non-%NULL pointers to integers as keys in a
1933 * #GHashTable.
1934 *
1935 * Note that this function acts on pointers to #gint, not on #gint
1936 * directly: if your hash table's keys are of the form
1937 * `GINT_TO_POINTER (n)`, use g_direct_equal() instead.
1938 *
1939 * Returns: %TRUE if the two keys match.
1940 */
1941 gboolean
1942 g_int_equal (gconstpointer v1,
1943 gconstpointer v2)
1944 {
1945 return *((const gint*) v1) == *((const gint*) v2);
1946 }
1947  
1948 /**
1949 * g_int_hash:
1950 * @v: (not nullable): a pointer to a #gint key
1951 *
1952 * Converts a pointer to a #gint to a hash value.
1953 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1954 * when using non-%NULL pointers to integer values as keys in a #GHashTable.
1955 *
1956 * Note that this function acts on pointers to #gint, not on #gint
1957 * directly: if your hash table's keys are of the form
1958 * `GINT_TO_POINTER (n)`, use g_direct_hash() instead.
1959 *
1960 * Returns: a hash value corresponding to the key.
1961 */
1962 guint
1963 g_int_hash (gconstpointer v)
1964 {
1965 return *(const gint*) v;
1966 }
1967  
1968 /**
1969 * g_int64_equal:
1970 * @v1: (not nullable): a pointer to a #gint64 key
1971 * @v2: (not nullable): a pointer to a #gint64 key to compare with @v1
1972 *
1973 * Compares the two #gint64 values being pointed to and returns
1974 * %TRUE if they are equal.
1975 * It can be passed to g_hash_table_new() as the @key_equal_func
1976 * parameter, when using non-%NULL pointers to 64-bit integers as keys in a
1977 * #GHashTable.
1978 *
1979 * Returns: %TRUE if the two keys match.
1980 *
1981 * Since: 2.22
1982 */
1983 gboolean
1984 g_int64_equal (gconstpointer v1,
1985 gconstpointer v2)
1986 {
1987 return *((const gint64*) v1) == *((const gint64*) v2);
1988 }
1989  
1990 /**
1991 * g_int64_hash:
1992 * @v: (not nullable): a pointer to a #gint64 key
1993 *
1994 * Converts a pointer to a #gint64 to a hash value.
1995 *
1996 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1997 * when using non-%NULL pointers to 64-bit integer values as keys in a
1998 * #GHashTable.
1999 *
2000 * Returns: a hash value corresponding to the key.
2001 *
2002 * Since: 2.22
2003 */
2004 guint
2005 g_int64_hash (gconstpointer v)
2006 {
2007 return (guint) *(const gint64*) v;
2008 }
2009  
2010 /**
2011 * g_double_equal:
2012 * @v1: (not nullable): a pointer to a #gdouble key
2013 * @v2: (not nullable): a pointer to a #gdouble key to compare with @v1
2014 *
2015 * Compares the two #gdouble values being pointed to and returns
2016 * %TRUE if they are equal.
2017 * It can be passed to g_hash_table_new() as the @key_equal_func
2018 * parameter, when using non-%NULL pointers to doubles as keys in a
2019 * #GHashTable.
2020 *
2021 * Returns: %TRUE if the two keys match.
2022 *
2023 * Since: 2.22
2024 */
2025 gboolean
2026 g_double_equal (gconstpointer v1,
2027 gconstpointer v2)
2028 {
2029 return *((const gdouble*) v1) == *((const gdouble*) v2);
2030 }
2031  
2032 /**
2033 * g_double_hash:
2034 * @v: (not nullable): a pointer to a #gdouble key
2035 *
2036 * Converts a pointer to a #gdouble to a hash value.
2037 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2038 * It can be passed to g_hash_table_new() as the @hash_func parameter,
2039 * when using non-%NULL pointers to doubles as keys in a #GHashTable.
2040 *
2041 * Returns: a hash value corresponding to the key.
2042 *
2043 * Since: 2.22
2044 */
2045 guint
2046 g_double_hash (gconstpointer v)
2047 {
2048 return (guint) *(const gdouble*) v;
2049 }