1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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.
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.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
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/.
33 #include <string.h> /* memset */
37 #include "gstrfuncs.h"
39 #include "gtestutils.h"
46 * @short_description: associations between keys and values so that
47 * given a key the value can be found quickly
49 * A #GHashTable provides associations between keys and values which is
50 * optimized so that given a key, the associated value can be found
53 * Note that neither keys nor values are copied when inserted into the
54 * #GHashTable, so they must exist for the lifetime of the #GHashTable.
55 * This means that the use of static strings is OK, but temporary
56 * strings (i.e. those created in buffers and those returned by GTK+
57 * widgets) should be copied with g_strdup() before being inserted.
59 * If keys or values are dynamically allocated, you must be careful to
60 * ensure that they are freed when they are removed from the
61 * #GHashTable, and also when they are overwritten by new insertions
62 * into the #GHashTable. It is also not advisable to mix static strings
63 * and dynamically-allocated strings in a #GHashTable, because it then
64 * becomes difficult to determine whether the string should be freed.
66 * To create a #GHashTable, use g_hash_table_new().
68 * To insert a key and value into a #GHashTable, use
69 * g_hash_table_insert().
71 * To lookup a value corresponding to a given key, use
72 * g_hash_table_lookup() and g_hash_table_lookup_extended().
74 * g_hash_table_lookup_extended() can also be used to simply
75 * check if a key is present in the hash table.
77 * To remove a key and value, use g_hash_table_remove().
79 * To call a function for each key and value pair use
80 * g_hash_table_foreach() or use a iterator to iterate over the
81 * key/value pairs in the hash table, see #GHashTableIter.
83 * To destroy a #GHashTable use g_hash_table_destroy().
86 * <title>Using a GHashTable as a set</title>
88 * A common use-case for hash tables is to store information about
89 * a set of keys, without associating any particular value with each
90 * key. GHashTable optimizes one way of doing so: If you store only
91 * key-value pairs where key == value, then GHashTable does not
92 * allocate memory to store the values, which can be a considerable
93 * space saving, if your set is large.
97 * set_new (GHashFunc hash_func,
98 * GEqualFunc equal_func,
99 * GDestroyNotify destroy)
101 * return g_hash_table_new_full (hash_func, equal_func, destroy, NULL);
105 * set_add (GHashTable *set,
108 * g_hash_table_replace (set, element, element);
112 * set_contains (GHashTable *set,
115 * return g_hash_table_lookup_extended (set, element, NULL, NULL);
119 * set_remove (GHashTable *set,
122 * return g_hash_table_remove (set, element);
127 * As of version 2.32, there is also a g_hash_table_add() function to
128 * add a key to a #GHashTable that is being used as a set.
134 * The #GHashTable struct is an opaque data structure to represent a
135 * <link linkend="glib-Hash-Tables">Hash Table</link>. It should only be
136 * accessed via the following functions.
143 * Specifies the type of the hash function which is passed to
144 * g_hash_table_new() when a #GHashTable is created.
146 * The function is passed a key and should return a #guint hash value.
147 * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
148 * hash functions which can be used when the key is a #gpointer, #gint*,
149 * and #gchar* respectively.
151 * g_direct_hash() is also the appropriate hash function for keys
152 * of the form <literal>GINT_TO_POINTER (n)</literal> (or similar macros).
154 * <!-- FIXME: Need more here. --> A good hash functions should produce
155 * hash values that are evenly distributed over a fairly large range.
156 * The modulus is taken with the hash table size (a prime number) to
157 * find the 'bucket' to place each key into. The function should also
158 * be very fast, since it is called for each key lookup.
160 * Note that the hash functions provided by GLib have these qualities,
161 * but are not particularly robust against manufactured keys that
162 * cause hash collisions. Therefore, you should consider choosing
163 * a more secure hash function when using a GHashTable with keys
164 * that originate in untrusted data (such as HTTP requests).
165 * Using g_str_hash() in that situation might make your application
166 * vulerable to <ulink url="https://lwn.net/Articles/474912/">Algorithmic Complexity Attacks</ulink>.
168 * Returns: the hash value corresponding to the key
174 * @value: the value corresponding to the key
175 * @user_data: user data passed to g_hash_table_foreach()
177 * Specifies the type of the function passed to g_hash_table_foreach().
178 * It is called with each key/value pair, together with the @user_data
179 * parameter which is passed to g_hash_table_foreach().
185 * @value: the value associated with the key
186 * @user_data: user data passed to g_hash_table_remove()
188 * Specifies the type of the function passed to
189 * g_hash_table_foreach_remove(). It is called with each key/value
190 * pair, together with the @user_data parameter passed to
191 * g_hash_table_foreach_remove(). It should return %TRUE if the
192 * key/value pair should be removed from the #GHashTable.
194 * Returns: %TRUE if the key/value pair should be removed from the
201 * @b: a value to compare with
203 * Specifies the type of a function used to test two values for
204 * equality. The function should return %TRUE if both values are equal
205 * and %FALSE otherwise.
207 * Returns: %TRUE if @a = @b; %FALSE otherwise
213 * A GHashTableIter structure represents an iterator that can be used
214 * to iterate over the elements of a #GHashTable. GHashTableIter
215 * structures are typically allocated on the stack and then initialized
216 * with g_hash_table_iter_init().
220 * g_hash_table_freeze:
221 * @hash_table: a #GHashTable
223 * This function is deprecated and will be removed in the next major
224 * release of GLib. It does nothing.
229 * @hash_table: a #GHashTable
231 * This function is deprecated and will be removed in the next major
232 * release of GLib. It does nothing.
235 #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */
237 #define UNUSED_HASH_VALUE 0
238 #define TOMBSTONE_HASH_VALUE 1
239 #define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
240 #define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
241 #define HASH_IS_REAL(h_) ((h_) >= 2)
249 gint noccupied; /* nnodes + tombstones */
256 GEqualFunc key_equal_func;
258 #ifndef G_DISABLE_ASSERT
260 * Tracks the structure of the hash table, not its contents: is only
261 * incremented when a node is added or removed (is not incremented
262 * when the key or data of a node is modified).
266 GDestroyNotify key_destroy_func;
267 GDestroyNotify value_destroy_func;
272 GHashTable *hash_table;
280 /* Each table size has an associated prime modulo (the first prime
281 * lower than the table size) used to find the initial bucket. Probing
282 * then works modulo 2^n. The prime modulo is necessary to get a
283 * good distribution with poor hash functions.
285 static const gint prime_mod [] =
303 65521, /* For 1 << 16 */
318 2147483647 /* For 1 << 31 */
322 g_hash_table_set_shift (GHashTable *hash_table, gint shift)
327 hash_table->size = 1 << shift;
328 hash_table->mod = prime_mod [shift];
330 for (i = 0; i < shift; i++)
336 hash_table->mask = mask;
340 g_hash_table_find_closest_shift (gint n)
351 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
355 shift = g_hash_table_find_closest_shift (size);
356 shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
358 g_hash_table_set_shift (hash_table, shift);
362 * g_hash_table_lookup_node:
363 * @hash_table: our #GHashTable
364 * @key: the key to lookup against
365 * @hash_return: key hash return location
367 * Performs a lookup in the hash table, preserving extra information
368 * usually needed for insertion.
370 * This function first computes the hash value of the key using the
371 * user's hash function.
373 * If an entry in the table matching @key is found then this function
374 * returns the index of that entry in the table, and if not, the
375 * index of an unused node (empty or tombstone) where the key can be
378 * The computed hash value is returned in the variable pointed to
379 * by @hash_return. This is to save insertions from having to compute
380 * the hash record again for the new record.
382 * Returns: index of the described node
385 g_hash_table_lookup_node (GHashTable *hash_table,
392 guint first_tombstone = 0;
393 gboolean have_tombstone = FALSE;
396 hash_value = hash_table->hash_func (key);
397 if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
400 *hash_return = hash_value;
402 node_index = hash_value % hash_table->mod;
403 node_hash = hash_table->hashes[node_index];
405 while (!HASH_IS_UNUSED (node_hash))
407 /* We first check if our full hash values
408 * are equal so we can avoid calling the full-blown
409 * key equality function in most cases.
411 if (node_hash == hash_value)
413 gpointer node_key = hash_table->keys[node_index];
415 if (hash_table->key_equal_func)
417 if (hash_table->key_equal_func (node_key, key))
420 else if (node_key == key)
425 else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
427 first_tombstone = node_index;
428 have_tombstone = TRUE;
433 node_index &= hash_table->mask;
434 node_hash = hash_table->hashes[node_index];
438 return first_tombstone;
444 * g_hash_table_remove_node:
445 * @hash_table: our #GHashTable
446 * @node: pointer to node to remove
447 * @notify: %TRUE if the destroy notify handlers are to be called
449 * Removes a node from the hash table and updates the node count.
450 * The node is replaced by a tombstone. No table resize is performed.
452 * If @notify is %TRUE then the destroy notify functions are called
453 * for the key and value of the hash node.
456 g_hash_table_remove_node (GHashTable *hash_table,
463 key = hash_table->keys[i];
464 value = hash_table->values[i];
466 /* Erect tombstone */
467 hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;
470 hash_table->keys[i] = NULL;
471 hash_table->values[i] = NULL;
473 hash_table->nnodes--;
475 if (notify && hash_table->key_destroy_func)
476 hash_table->key_destroy_func (key);
478 if (notify && hash_table->value_destroy_func)
479 hash_table->value_destroy_func (value);
484 * g_hash_table_remove_all_nodes:
485 * @hash_table: our #GHashTable
486 * @notify: %TRUE if the destroy notify handlers are to be called
488 * Removes all nodes from the table. Since this may be a precursor to
489 * freeing the table entirely, no resize is performed.
491 * If @notify is %TRUE then the destroy notify functions are called
492 * for the key and value of the hash node.
495 g_hash_table_remove_all_nodes (GHashTable *hash_table,
502 hash_table->nnodes = 0;
503 hash_table->noccupied = 0;
506 (hash_table->key_destroy_func == NULL &&
507 hash_table->value_destroy_func == NULL))
509 memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
510 memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
511 memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
516 for (i = 0; i < hash_table->size; i++)
518 if (HASH_IS_REAL (hash_table->hashes[i]))
520 key = hash_table->keys[i];
521 value = hash_table->values[i];
523 hash_table->hashes[i] = UNUSED_HASH_VALUE;
524 hash_table->keys[i] = NULL;
525 hash_table->values[i] = NULL;
527 if (hash_table->key_destroy_func != NULL)
528 hash_table->key_destroy_func (key);
530 if (hash_table->value_destroy_func != NULL)
531 hash_table->value_destroy_func (value);
533 else if (HASH_IS_TOMBSTONE (hash_table->hashes[i]))
535 hash_table->hashes[i] = UNUSED_HASH_VALUE;
541 * g_hash_table_resize:
542 * @hash_table: our #GHashTable
544 * Resizes the hash table to the optimal size based on the number of
545 * nodes currently held. If you call this function then a resize will
546 * occur, even if one does not need to occur.
547 * Use g_hash_table_maybe_resize() instead.
549 * This function may "resize" the hash table to its current size, with
550 * the side effect of cleaning up tombstones and otherwise optimizing
551 * the probe sequences.
554 g_hash_table_resize (GHashTable *hash_table)
557 gpointer *new_values;
562 old_size = hash_table->size;
563 g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
565 new_keys = g_new0 (gpointer, hash_table->size);
566 if (hash_table->keys == hash_table->values)
567 new_values = new_keys;
569 new_values = g_new0 (gpointer, hash_table->size);
570 new_hashes = g_new0 (guint, hash_table->size);
572 for (i = 0; i < old_size; i++)
574 guint node_hash = hash_table->hashes[i];
578 if (!HASH_IS_REAL (node_hash))
581 hash_val = node_hash % hash_table->mod;
583 while (!HASH_IS_UNUSED (new_hashes[hash_val]))
587 hash_val &= hash_table->mask;
590 new_hashes[hash_val] = hash_table->hashes[i];
591 new_keys[hash_val] = hash_table->keys[i];
592 new_values[hash_val] = hash_table->values[i];
595 if (hash_table->keys != hash_table->values)
596 g_free (hash_table->values);
598 g_free (hash_table->keys);
599 g_free (hash_table->hashes);
601 hash_table->keys = new_keys;
602 hash_table->values = new_values;
603 hash_table->hashes = new_hashes;
605 hash_table->noccupied = hash_table->nnodes;
609 * g_hash_table_maybe_resize:
610 * @hash_table: our #GHashTable
612 * Resizes the hash table, if needed.
614 * Essentially, calls g_hash_table_resize() if the table has strayed
615 * too far from its ideal size for its number of nodes.
618 g_hash_table_maybe_resize (GHashTable *hash_table)
620 gint noccupied = hash_table->noccupied;
621 gint size = hash_table->size;
623 if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
624 (size <= noccupied + (noccupied / 16)))
625 g_hash_table_resize (hash_table);
630 * @hash_func: a function to create a hash value from a key
631 * @key_equal_func: a function to check two keys for equality
633 * Creates a new #GHashTable with a reference count of 1.
635 * Hash values returned by @hash_func are used to determine where keys
636 * are stored within the #GHashTable data structure. The g_direct_hash(),
637 * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash()
638 * functions are provided for some common types of keys.
639 * If @hash_func is %NULL, g_direct_hash() is used.
641 * @key_equal_func is used when looking up keys in the #GHashTable.
642 * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal()
643 * and g_str_equal() functions are provided for the most common types
644 * of keys. If @key_equal_func is %NULL, keys are compared directly in
645 * a similar fashion to g_direct_equal(), but without the overhead of
648 * Return value: a new #GHashTable
651 g_hash_table_new (GHashFunc hash_func,
652 GEqualFunc key_equal_func)
654 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
659 * g_hash_table_new_full:
660 * @hash_func: a function to create a hash value from a key
661 * @key_equal_func: a function to check two keys for equality
662 * @key_destroy_func: a function to free the memory allocated for the key
663 * used when removing the entry from the #GHashTable, or %NULL
664 * if you don't want to supply such a function.
665 * @value_destroy_func: a function to free the memory allocated for the
666 * value used when removing the entry from the #GHashTable, or %NULL
667 * if you don't want to supply such a function.
669 * Creates a new #GHashTable like g_hash_table_new() with a reference
670 * count of 1 and allows to specify functions to free the memory
671 * allocated for the key and value that get called when removing the
672 * entry from the #GHashTable.
674 * Return value: a new #GHashTable
677 g_hash_table_new_full (GHashFunc hash_func,
678 GEqualFunc key_equal_func,
679 GDestroyNotify key_destroy_func,
680 GDestroyNotify value_destroy_func)
682 GHashTable *hash_table;
684 hash_table = g_slice_new (GHashTable);
685 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
686 hash_table->nnodes = 0;
687 hash_table->noccupied = 0;
688 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
689 hash_table->key_equal_func = key_equal_func;
690 hash_table->ref_count = 1;
691 #ifndef G_DISABLE_ASSERT
692 hash_table->version = 0;
694 hash_table->key_destroy_func = key_destroy_func;
695 hash_table->value_destroy_func = value_destroy_func;
696 hash_table->keys = g_new0 (gpointer, hash_table->size);
697 hash_table->values = hash_table->keys;
698 hash_table->hashes = g_new0 (guint, hash_table->size);
704 * g_hash_table_iter_init:
705 * @iter: an uninitialized #GHashTableIter
706 * @hash_table: a #GHashTable
708 * Initializes a key/value pair iterator and associates it with
709 * @hash_table. Modifying the hash table after calling this function
710 * invalidates the returned iterator.
712 * GHashTableIter iter;
713 * gpointer key, value;
715 * g_hash_table_iter_init (&iter, hash_table);
716 * while (g_hash_table_iter_next (&iter, &key, &value))
718 * /* do something with key and value */
725 g_hash_table_iter_init (GHashTableIter *iter,
726 GHashTable *hash_table)
728 RealIter *ri = (RealIter *) iter;
730 g_return_if_fail (iter != NULL);
731 g_return_if_fail (hash_table != NULL);
733 ri->hash_table = hash_table;
735 #ifndef G_DISABLE_ASSERT
736 ri->version = hash_table->version;
741 * g_hash_table_iter_next:
742 * @iter: an initialized #GHashTableIter
743 * @key: a location to store the key, or %NULL
744 * @value: a location to store the value, or %NULL
746 * Advances @iter and retrieves the key and/or value that are now
747 * pointed to as a result of this advancement. If %FALSE is returned,
748 * @key and @value are not set, and the iterator becomes invalid.
750 * Return value: %FALSE if the end of the #GHashTable has been reached.
755 g_hash_table_iter_next (GHashTableIter *iter,
759 RealIter *ri = (RealIter *) iter;
762 g_return_val_if_fail (iter != NULL, FALSE);
763 #ifndef G_DISABLE_ASSERT
764 g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
766 g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
768 position = ri->position;
773 if (position >= ri->hash_table->size)
775 ri->position = position;
779 while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
782 *key = ri->hash_table->keys[position];
784 *value = ri->hash_table->values[position];
786 ri->position = position;
791 * g_hash_table_iter_get_hash_table:
792 * @iter: an initialized #GHashTableIter
794 * Returns the #GHashTable associated with @iter.
796 * Return value: the #GHashTable associated with @iter.
801 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
803 g_return_val_if_fail (iter != NULL, NULL);
805 return ((RealIter *) iter)->hash_table;
809 iter_remove_or_steal (RealIter *ri, gboolean notify)
811 g_return_if_fail (ri != NULL);
812 #ifndef G_DISABLE_ASSERT
813 g_return_if_fail (ri->version == ri->hash_table->version);
815 g_return_if_fail (ri->position >= 0);
816 g_return_if_fail (ri->position < ri->hash_table->size);
818 g_hash_table_remove_node (ri->hash_table, ri->position, notify);
820 #ifndef G_DISABLE_ASSERT
822 ri->hash_table->version++;
827 * g_hash_table_iter_remove:
828 * @iter: an initialized #GHashTableIter
830 * Removes the key/value pair currently pointed to by the iterator
831 * from its associated #GHashTable. Can only be called after
832 * g_hash_table_iter_next() returned %TRUE, and cannot be called
833 * more than once for the same key/value pair.
835 * If the #GHashTable was created using g_hash_table_new_full(),
836 * the key and value are freed using the supplied destroy functions,
837 * otherwise you have to make sure that any dynamically allocated
838 * values are freed yourself.
843 g_hash_table_iter_remove (GHashTableIter *iter)
845 iter_remove_or_steal ((RealIter *) iter, TRUE);
849 * g_hash_table_insert_node:
850 * @hash_table: our #GHashTable
851 * @node_index: pointer to node to insert/replace
852 * @key_hash: key hash
853 * @key: key to replace with, or %NULL
854 * @value: value to replace with
855 * @keep_new_key: whether to replace the key in the node with @key
856 * @reusing_key: whether @key was taken out of the existing node
858 * Inserts a value at @node_index in the hash table and updates it.
860 * If @key has been taken out of the existing node (ie it is not
861 * passed in via a g_hash_table_insert/replace) call, then @reusing_key
865 g_hash_table_insert_node (GHashTable *hash_table,
870 gboolean keep_new_key,
871 gboolean reusing_key)
877 if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
878 hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
880 old_hash = hash_table->hashes[node_index];
881 old_key = hash_table->keys[node_index];
882 old_value = hash_table->values[node_index];
884 if (HASH_IS_REAL (old_hash))
887 hash_table->keys[node_index] = key;
888 hash_table->values[node_index] = value;
892 hash_table->keys[node_index] = key;
893 hash_table->values[node_index] = value;
894 hash_table->hashes[node_index] = key_hash;
896 hash_table->nnodes++;
898 if (HASH_IS_UNUSED (old_hash))
900 /* We replaced an empty node, and not a tombstone */
901 hash_table->noccupied++;
902 g_hash_table_maybe_resize (hash_table);
905 #ifndef G_DISABLE_ASSERT
906 hash_table->version++;
910 if (HASH_IS_REAL (old_hash))
912 if (hash_table->key_destroy_func && !reusing_key)
913 hash_table->key_destroy_func (keep_new_key ? old_key : key);
914 if (hash_table->value_destroy_func)
915 hash_table->value_destroy_func (old_value);
920 * g_hash_table_iter_replace:
921 * @iter: an initialized #GHashTableIter
922 * @value: the value to replace with
924 * Replaces the value currently pointed to by the iterator
925 * from its associated #GHashTable. Can only be called after
926 * g_hash_table_iter_next() returned %TRUE.
928 * If you supplied a @value_destroy_func when creating the
929 * #GHashTable, the old value is freed using that function.
934 g_hash_table_iter_replace (GHashTableIter *iter,
941 ri = (RealIter *) iter;
943 g_return_if_fail (ri != NULL);
944 #ifndef G_DISABLE_ASSERT
945 g_return_if_fail (ri->version == ri->hash_table->version);
947 g_return_if_fail (ri->position >= 0);
948 g_return_if_fail (ri->position < ri->hash_table->size);
950 node_hash = ri->hash_table->hashes[ri->position];
951 key = ri->hash_table->keys[ri->position];
953 g_hash_table_insert_node (ri->hash_table, ri->position, node_hash, key, value, TRUE, TRUE);
955 #ifndef G_DISABLE_ASSERT
957 ri->hash_table->version++;
962 * g_hash_table_iter_steal:
963 * @iter: an initialized #GHashTableIter
965 * Removes the key/value pair currently pointed to by the
966 * iterator from its associated #GHashTable, without calling
967 * the key and value destroy functions. Can only be called
968 * after g_hash_table_iter_next() returned %TRUE, and cannot
969 * be called more than once for the same key/value pair.
974 g_hash_table_iter_steal (GHashTableIter *iter)
976 iter_remove_or_steal ((RealIter *) iter, FALSE);
982 * @hash_table: a valid #GHashTable
984 * Atomically increments the reference count of @hash_table by one.
985 * This function is MT-safe and may be called from any thread.
987 * Return value: the passed in #GHashTable
992 g_hash_table_ref (GHashTable *hash_table)
994 g_return_val_if_fail (hash_table != NULL, NULL);
996 g_atomic_int_inc (&hash_table->ref_count);
1002 * g_hash_table_unref:
1003 * @hash_table: a valid #GHashTable
1005 * Atomically decrements the reference count of @hash_table by one.
1006 * If the reference count drops to 0, all keys and values will be
1007 * destroyed, and all memory allocated by the hash table is released.
1008 * This function is MT-safe and may be called from any thread.
1013 g_hash_table_unref (GHashTable *hash_table)
1015 g_return_if_fail (hash_table != NULL);
1017 if (g_atomic_int_dec_and_test (&hash_table->ref_count))
1019 g_hash_table_remove_all_nodes (hash_table, TRUE);
1020 if (hash_table->keys != hash_table->values)
1021 g_free (hash_table->values);
1022 g_free (hash_table->keys);
1023 g_free (hash_table->hashes);
1024 g_slice_free (GHashTable, hash_table);
1029 * g_hash_table_destroy:
1030 * @hash_table: a #GHashTable
1032 * Destroys all keys and values in the #GHashTable and decrements its
1033 * reference count by 1. If keys and/or values are dynamically allocated,
1034 * you should either free them first or create the #GHashTable with destroy
1035 * notifiers using g_hash_table_new_full(). In the latter case the destroy
1036 * functions you supplied will be called on all keys and values during the
1037 * destruction phase.
1040 g_hash_table_destroy (GHashTable *hash_table)
1042 g_return_if_fail (hash_table != NULL);
1044 g_hash_table_remove_all (hash_table);
1045 g_hash_table_unref (hash_table);
1049 * g_hash_table_lookup:
1050 * @hash_table: a #GHashTable
1051 * @key: the key to look up
1053 * Looks up a key in a #GHashTable. Note that this function cannot
1054 * distinguish between a key that is not present and one which is present
1055 * and has the value %NULL. If you need this distinction, use
1056 * g_hash_table_lookup_extended().
1058 * Return value: (allow-none): the associated value, or %NULL if the key is not found
1061 g_hash_table_lookup (GHashTable *hash_table,
1067 g_return_val_if_fail (hash_table != NULL, NULL);
1069 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1071 return HASH_IS_REAL (hash_table->hashes[node_index])
1072 ? hash_table->values[node_index]
1077 * g_hash_table_lookup_extended:
1078 * @hash_table: a #GHashTable
1079 * @lookup_key: the key to look up
1080 * @orig_key: (allow-none): return location for the original key, or %NULL
1081 * @value: (allow-none): return location for the value associated with the key, or %NULL
1083 * Looks up a key in the #GHashTable, returning the original key and the
1084 * associated value and a #gboolean which is %TRUE if the key was found. This
1085 * is useful if you need to free the memory allocated for the original key,
1086 * for example before calling g_hash_table_remove().
1088 * You can actually pass %NULL for @lookup_key to test
1089 * whether the %NULL key exists, provided the hash and equal functions
1090 * of @hash_table are %NULL-safe.
1092 * Return value: %TRUE if the key was found in the #GHashTable
1095 g_hash_table_lookup_extended (GHashTable *hash_table,
1096 gconstpointer lookup_key,
1103 g_return_val_if_fail (hash_table != NULL, FALSE);
1105 node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1107 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1111 *orig_key = hash_table->keys[node_index];
1114 *value = hash_table->values[node_index];
1120 * g_hash_table_insert_internal:
1121 * @hash_table: our #GHashTable
1122 * @key: the key to insert
1123 * @value: the value to insert
1124 * @keep_new_key: if %TRUE and this key already exists in the table
1125 * then call the destroy notify function on the old key. If %FALSE
1126 * then call the destroy notify function on the new key.
1128 * Implements the common logic for the g_hash_table_insert() and
1129 * g_hash_table_replace() functions.
1131 * Do a lookup of @key. If it is found, replace it with the new
1132 * @value (and perhaps the new @key). If it is not found, create
1136 g_hash_table_insert_internal (GHashTable *hash_table,
1139 gboolean keep_new_key)
1144 g_return_if_fail (hash_table != NULL);
1146 node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
1148 g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key, FALSE);
1152 * g_hash_table_insert:
1153 * @hash_table: a #GHashTable
1154 * @key: a key to insert
1155 * @value: the value to associate with the key
1157 * Inserts a new key and value into a #GHashTable.
1159 * If the key already exists in the #GHashTable its current
1160 * value is replaced with the new value. If you supplied a
1161 * @value_destroy_func when creating the #GHashTable, the old
1162 * value is freed using that function. If you supplied a
1163 * @key_destroy_func when creating the #GHashTable, the passed
1164 * key is freed using that function.
1167 g_hash_table_insert (GHashTable *hash_table,
1171 g_hash_table_insert_internal (hash_table, key, value, FALSE);
1175 * g_hash_table_replace:
1176 * @hash_table: a #GHashTable
1177 * @key: a key to insert
1178 * @value: the value to associate with the key
1180 * Inserts a new key and value into a #GHashTable similar to
1181 * g_hash_table_insert(). The difference is that if the key
1182 * already exists in the #GHashTable, it gets replaced by the
1183 * new key. If you supplied a @value_destroy_func when creating
1184 * the #GHashTable, the old value is freed using that function.
1185 * If you supplied a @key_destroy_func when creating the
1186 * #GHashTable, the old key is freed using that function.
1189 g_hash_table_replace (GHashTable *hash_table,
1193 g_hash_table_insert_internal (hash_table, key, value, TRUE);
1198 * @hash_table: a #GHashTable
1199 * @key: a key to insert
1201 * This is a convenience function for using a #GHashTable as a set. It
1202 * is equivalent to calling g_hash_table_replace() with @key as both the
1203 * key and the value.
1205 * When a hash table only ever contains keys that have themselves as the
1206 * corresponding value it is able to be stored more efficiently. See
1207 * the discussion in the section description.
1212 g_hash_table_add (GHashTable *hash_table,
1215 g_hash_table_insert_internal (hash_table, key, key, TRUE);
1219 * g_hash_table_contains:
1220 * @hash_table: a #GHashTable
1221 * @key: a key to check
1223 * Checks if @key is in @hash_table.
1228 g_hash_table_contains (GHashTable *hash_table,
1234 g_return_val_if_fail (hash_table != NULL, FALSE);
1236 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1238 return HASH_IS_REAL (hash_table->hashes[node_index]);
1242 * g_hash_table_remove_internal:
1243 * @hash_table: our #GHashTable
1244 * @key: the key to remove
1245 * @notify: %TRUE if the destroy notify handlers are to be called
1246 * Return value: %TRUE if a node was found and removed, else %FALSE
1248 * Implements the common logic for the g_hash_table_remove() and
1249 * g_hash_table_steal() functions.
1251 * Do a lookup of @key and remove it if it is found, calling the
1252 * destroy notify handlers only if @notify is %TRUE.
1255 g_hash_table_remove_internal (GHashTable *hash_table,
1262 g_return_val_if_fail (hash_table != NULL, FALSE);
1264 node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1266 if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1269 g_hash_table_remove_node (hash_table, node_index, notify);
1270 g_hash_table_maybe_resize (hash_table);
1272 #ifndef G_DISABLE_ASSERT
1273 hash_table->version++;
1280 * g_hash_table_remove:
1281 * @hash_table: a #GHashTable
1282 * @key: the key to remove
1284 * Removes a key and its associated value from a #GHashTable.
1286 * If the #GHashTable was created using g_hash_table_new_full(), the
1287 * key and value are freed using the supplied destroy functions, otherwise
1288 * you have to make sure that any dynamically allocated values are freed
1291 * Returns: %TRUE if the key was found and removed from the #GHashTable
1294 g_hash_table_remove (GHashTable *hash_table,
1297 return g_hash_table_remove_internal (hash_table, key, TRUE);
1301 * g_hash_table_steal:
1302 * @hash_table: a #GHashTable
1303 * @key: the key to remove
1305 * Removes a key and its associated value from a #GHashTable without
1306 * calling the key and value destroy functions.
1308 * Returns: %TRUE if the key was found and removed from the #GHashTable
1311 g_hash_table_steal (GHashTable *hash_table,
1314 return g_hash_table_remove_internal (hash_table, key, FALSE);
1318 * g_hash_table_remove_all:
1319 * @hash_table: a #GHashTable
1321 * Removes all keys and their associated values from a #GHashTable.
1323 * If the #GHashTable was created using g_hash_table_new_full(),
1324 * the keys and values are freed using the supplied destroy functions,
1325 * otherwise you have to make sure that any dynamically allocated
1326 * values are freed yourself.
1331 g_hash_table_remove_all (GHashTable *hash_table)
1333 g_return_if_fail (hash_table != NULL);
1335 #ifndef G_DISABLE_ASSERT
1336 if (hash_table->nnodes != 0)
1337 hash_table->version++;
1340 g_hash_table_remove_all_nodes (hash_table, TRUE);
1341 g_hash_table_maybe_resize (hash_table);
1345 * g_hash_table_steal_all:
1346 * @hash_table: a #GHashTable
1348 * Removes all keys and their associated values from a #GHashTable
1349 * without calling the key and value destroy functions.
1354 g_hash_table_steal_all (GHashTable *hash_table)
1356 g_return_if_fail (hash_table != NULL);
1358 #ifndef G_DISABLE_ASSERT
1359 if (hash_table->nnodes != 0)
1360 hash_table->version++;
1363 g_hash_table_remove_all_nodes (hash_table, FALSE);
1364 g_hash_table_maybe_resize (hash_table);
1368 * g_hash_table_foreach_remove_or_steal:
1369 * @hash_table: a #GHashTable
1370 * @func: the user's callback function
1371 * @user_data: data for @func
1372 * @notify: %TRUE if the destroy notify handlers are to be called
1374 * Implements the common logic for g_hash_table_foreach_remove()
1375 * and g_hash_table_foreach_steal().
1377 * Iterates over every node in the table, calling @func with the key
1378 * and value of the node (and @user_data). If @func returns %TRUE the
1379 * node is removed from the table.
1381 * If @notify is true then the destroy notify handlers will be called
1382 * for each removed node.
1385 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1392 #ifndef G_DISABLE_ASSERT
1393 gint version = hash_table->version;
1396 for (i = 0; i < hash_table->size; i++)
1398 guint node_hash = hash_table->hashes[i];
1399 gpointer node_key = hash_table->keys[i];
1400 gpointer node_value = hash_table->values[i];
1402 if (HASH_IS_REAL (node_hash) &&
1403 (* func) (node_key, node_value, user_data))
1405 g_hash_table_remove_node (hash_table, i, notify);
1409 #ifndef G_DISABLE_ASSERT
1410 g_return_val_if_fail (version == hash_table->version, 0);
1414 g_hash_table_maybe_resize (hash_table);
1416 #ifndef G_DISABLE_ASSERT
1418 hash_table->version++;
1425 * g_hash_table_foreach_remove:
1426 * @hash_table: a #GHashTable
1427 * @func: the function to call for each key/value pair
1428 * @user_data: user data to pass to the function
1430 * Calls the given function for each key/value pair in the
1431 * #GHashTable. If the function returns %TRUE, then the key/value
1432 * pair is removed from the #GHashTable. If you supplied key or
1433 * value destroy functions when creating the #GHashTable, they are
1434 * used to free the memory allocated for the removed keys and values.
1436 * See #GHashTableIter for an alternative way to loop over the
1437 * key/value pairs in the hash table.
1439 * Return value: the number of key/value pairs removed
1442 g_hash_table_foreach_remove (GHashTable *hash_table,
1446 g_return_val_if_fail (hash_table != NULL, 0);
1447 g_return_val_if_fail (func != NULL, 0);
1449 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1453 * g_hash_table_foreach_steal:
1454 * @hash_table: a #GHashTable
1455 * @func: the function to call for each key/value pair
1456 * @user_data: user data to pass to the function
1458 * Calls the given function for each key/value pair in the
1459 * #GHashTable. If the function returns %TRUE, then the key/value
1460 * pair is removed from the #GHashTable, but no key or value
1461 * destroy functions are called.
1463 * See #GHashTableIter for an alternative way to loop over the
1464 * key/value pairs in the hash table.
1466 * Return value: the number of key/value pairs removed.
1469 g_hash_table_foreach_steal (GHashTable *hash_table,
1473 g_return_val_if_fail (hash_table != NULL, 0);
1474 g_return_val_if_fail (func != NULL, 0);
1476 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1480 * g_hash_table_foreach:
1481 * @hash_table: a #GHashTable
1482 * @func: the function to call for each key/value pair
1483 * @user_data: user data to pass to the function
1485 * Calls the given function for each of the key/value pairs in the
1486 * #GHashTable. The function is passed the key and value of each
1487 * pair, and the given @user_data parameter. The hash table may not
1488 * be modified while iterating over it (you can't add/remove
1489 * items). To remove all items matching a predicate, use
1490 * g_hash_table_foreach_remove().
1492 * See g_hash_table_find() for performance caveats for linear
1493 * order searches in contrast to g_hash_table_lookup().
1496 g_hash_table_foreach (GHashTable *hash_table,
1501 #ifndef G_DISABLE_ASSERT
1502 gint version = hash_table->version;
1505 g_return_if_fail (hash_table != NULL);
1506 g_return_if_fail (func != NULL);
1508 for (i = 0; i < hash_table->size; i++)
1510 guint node_hash = hash_table->hashes[i];
1511 gpointer node_key = hash_table->keys[i];
1512 gpointer node_value = hash_table->values[i];
1514 if (HASH_IS_REAL (node_hash))
1515 (* func) (node_key, node_value, user_data);
1517 #ifndef G_DISABLE_ASSERT
1518 g_return_if_fail (version == hash_table->version);
1524 * g_hash_table_find:
1525 * @hash_table: a #GHashTable
1526 * @predicate: function to test the key/value pairs for a certain property
1527 * @user_data: user data to pass to the function
1529 * Calls the given function for key/value pairs in the #GHashTable
1530 * until @predicate returns %TRUE. The function is passed the key
1531 * and value of each pair, and the given @user_data parameter. The
1532 * hash table may not be modified while iterating over it (you can't
1533 * add/remove items).
1535 * Note, that hash tables are really only optimized for forward
1536 * lookups, i.e. g_hash_table_lookup(). So code that frequently issues
1537 * g_hash_table_find() or g_hash_table_foreach() (e.g. in the order of
1538 * once per every entry in a hash table) should probably be reworked
1539 * to use additional or different data structures for reverse lookups
1540 * (keep in mind that an O(n) find/foreach operation issued for all n
1541 * values in a hash table ends up needing O(n*n) operations).
1543 * Return value: (allow-none): The value of the first key/value pair is returned,
1544 * for which @predicate evaluates to %TRUE. If no pair with the
1545 * requested property is found, %NULL is returned.
1550 g_hash_table_find (GHashTable *hash_table,
1555 #ifndef G_DISABLE_ASSERT
1556 gint version = hash_table->version;
1560 g_return_val_if_fail (hash_table != NULL, NULL);
1561 g_return_val_if_fail (predicate != NULL, NULL);
1565 for (i = 0; i < hash_table->size; i++)
1567 guint node_hash = hash_table->hashes[i];
1568 gpointer node_key = hash_table->keys[i];
1569 gpointer node_value = hash_table->values[i];
1571 if (HASH_IS_REAL (node_hash))
1572 match = predicate (node_key, node_value, user_data);
1574 #ifndef G_DISABLE_ASSERT
1575 g_return_val_if_fail (version == hash_table->version, NULL);
1586 * g_hash_table_size:
1587 * @hash_table: a #GHashTable
1589 * Returns the number of elements contained in the #GHashTable.
1591 * Return value: the number of key/value pairs in the #GHashTable.
1594 g_hash_table_size (GHashTable *hash_table)
1596 g_return_val_if_fail (hash_table != NULL, 0);
1598 return hash_table->nnodes;
1602 * g_hash_table_get_keys:
1603 * @hash_table: a #GHashTable
1605 * Retrieves every key inside @hash_table. The returned data
1606 * is valid until @hash_table is modified.
1608 * Return value: a #GList containing all the keys inside the hash
1609 * table. The content of the list is owned by the hash table and
1610 * should not be modified or freed. Use g_list_free() when done
1616 g_hash_table_get_keys (GHashTable *hash_table)
1621 g_return_val_if_fail (hash_table != NULL, NULL);
1624 for (i = 0; i < hash_table->size; i++)
1626 if (HASH_IS_REAL (hash_table->hashes[i]))
1627 retval = g_list_prepend (retval, hash_table->keys[i]);
1634 * g_hash_table_get_values:
1635 * @hash_table: a #GHashTable
1637 * Retrieves every value inside @hash_table. The returned data
1638 * is valid until @hash_table is modified.
1640 * Return value: a #GList containing all the values inside the hash
1641 * table. The content of the list is owned by the hash table and
1642 * should not be modified or freed. Use g_list_free() when done
1648 g_hash_table_get_values (GHashTable *hash_table)
1653 g_return_val_if_fail (hash_table != NULL, NULL);
1656 for (i = 0; i < hash_table->size; i++)
1658 if (HASH_IS_REAL (hash_table->hashes[i]))
1659 retval = g_list_prepend (retval, hash_table->values[i]);
1671 * @v2: a key to compare with @v1
1673 * Compares two strings for byte-by-byte equality and returns %TRUE
1674 * if they are equal. It can be passed to g_hash_table_new() as the
1675 * @key_equal_func parameter, when using non-%NULL strings as keys in a
1678 * Note that this function is primarily meant as a hash table comparison
1679 * function. For a general-purpose, %NULL-safe string comparison function,
1682 * Returns: %TRUE if the two keys match
1685 g_str_equal (gconstpointer v1,
1688 const gchar *string1 = v1;
1689 const gchar *string2 = v2;
1691 return strcmp (string1, string2) == 0;
1698 * Converts a string to a hash value.
1700 * This function implements the widely used "djb" hash apparently posted
1701 * by Daniel Bernstein to comp.lang.c some time ago. The 32 bit
1702 * unsigned hash value starts at 5381 and for each byte 'c' in the
1703 * string, is updated: <literal>hash = hash * 33 + c</literal>. This
1704 * function uses the signed value of each byte.
1706 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1707 * when using non-%NULL strings as keys in a #GHashTable.
1709 * Returns: a hash value corresponding to the key
1712 g_str_hash (gconstpointer v)
1714 const signed char *p;
1717 for (p = v; *p != '\0'; p++)
1718 h = (h << 5) + h + *p;
1725 * @v: (allow-none): a #gpointer key
1727 * Converts a gpointer to a hash value.
1728 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1729 * when using opaque pointers compared by pointer value as keys in a
1732 * This hash function is also appropriate for keys that are integers stored
1733 * in pointers, such as <literal>GINT_TO_POINTER (n)</literal>.
1735 * Returns: a hash value corresponding to the key.
1738 g_direct_hash (gconstpointer v)
1740 return GPOINTER_TO_UINT (v);
1745 * @v1: (allow-none): a key
1746 * @v2: (allow-none): a key to compare with @v1
1748 * Compares two #gpointer arguments and returns %TRUE if they are equal.
1749 * It can be passed to g_hash_table_new() as the @key_equal_func
1750 * parameter, when using opaque pointers compared by pointer value as keys
1753 * This equality function is also appropriate for keys that are integers stored
1754 * in pointers, such as <literal>GINT_TO_POINTER (n)</literal>.
1756 * Returns: %TRUE if the two keys match.
1759 g_direct_equal (gconstpointer v1,
1767 * @v1: a pointer to a #gint key
1768 * @v2: a pointer to a #gint key to compare with @v1
1770 * Compares the two #gint values being pointed to and returns
1771 * %TRUE if they are equal.
1772 * It can be passed to g_hash_table_new() as the @key_equal_func
1773 * parameter, when using non-%NULL pointers to integers as keys in a
1776 * Note that this function acts on pointers to #gint, not on #gint directly:
1777 * if your hash table's keys are of the form
1778 * <literal>GINT_TO_POINTER (n)</literal>, use g_direct_equal() instead.
1780 * Returns: %TRUE if the two keys match.
1783 g_int_equal (gconstpointer v1,
1786 return *((const gint*) v1) == *((const gint*) v2);
1791 * @v: a pointer to a #gint key
1793 * Converts a pointer to a #gint to a hash value.
1794 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1795 * when using non-%NULL pointers to integer values as keys in a #GHashTable.
1797 * Note that this function acts on pointers to #gint, not on #gint directly:
1798 * if your hash table's keys are of the form
1799 * <literal>GINT_TO_POINTER (n)</literal>, use g_direct_hash() instead.
1801 * Returns: a hash value corresponding to the key.
1804 g_int_hash (gconstpointer v)
1806 return *(const gint*) v;
1811 * @v1: a pointer to a #gint64 key
1812 * @v2: a pointer to a #gint64 key to compare with @v1
1814 * Compares the two #gint64 values being pointed to and returns
1815 * %TRUE if they are equal.
1816 * It can be passed to g_hash_table_new() as the @key_equal_func
1817 * parameter, when using non-%NULL pointers to 64-bit integers as keys in a
1820 * Returns: %TRUE if the two keys match.
1825 g_int64_equal (gconstpointer v1,
1828 return *((const gint64*) v1) == *((const gint64*) v2);
1833 * @v: a pointer to a #gint64 key
1835 * Converts a pointer to a #gint64 to a hash value.
1837 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1838 * when using non-%NULL pointers to 64-bit integer values as keys in a
1841 * Returns: a hash value corresponding to the key.
1846 g_int64_hash (gconstpointer v)
1848 return (guint) *(const gint64*) v;
1853 * @v1: a pointer to a #gdouble key
1854 * @v2: a pointer to a #gdouble key to compare with @v1
1856 * Compares the two #gdouble values being pointed to and returns
1857 * %TRUE if they are equal.
1858 * It can be passed to g_hash_table_new() as the @key_equal_func
1859 * parameter, when using non-%NULL pointers to doubles as keys in a
1862 * Returns: %TRUE if the two keys match.
1867 g_double_equal (gconstpointer v1,
1870 return *((const gdouble*) v1) == *((const gdouble*) v2);
1875 * @v: a pointer to a #gdouble key
1877 * Converts a pointer to a #gdouble to a hash value.
1878 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1879 * It can be passed to g_hash_table_new() as the @hash_func parameter,
1880 * when using non-%NULL pointers to doubles as keys in a #GHashTable.
1882 * Returns: a hash value corresponding to the key.
1887 g_double_hash (gconstpointer v)
1889 return (guint) *(const gdouble*) v;