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