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
  41
  42 /**
  43  * SECTION:hash_tables
  44  * @title: Hash Tables
  45  * @short_description: associations between keys and values so that
  46  *                     given a key the value can be found quickly
  47  *
  48  * A #GHashTable provides associations between keys and values which is
  49  * optimized so that given a key, the associated value can be found
  50  * very quickly.
  51  *
  52  * Note that neither keys nor values are copied when inserted into the
  53  * #GHashTable, so they must exist for the lifetime of the #GHashTable.
  54  * This means that the use of static strings is OK, but temporary
  55  * strings (i.e. those created in buffers and those returned by GTK+
  56  * widgets) should be copied with g_strdup() before being inserted.
  57  *
  58  * If keys or values are dynamically allocated, you must be careful to
  59  * ensure that they are freed when they are removed from the
  60  * #GHashTable, and also when they are overwritten by new insertions
  61  * into the #GHashTable. It is also not advisable to mix static strings
  62  * and dynamically-allocated strings in a #GHashTable, because it then
  63  * becomes difficult to determine whether the string should be freed.
  64  *
  65  * To create a #GHashTable, use g_hash_table_new().
  66  *
  67  * To insert a key and value into a #GHashTable, use
  68  * g_hash_table_insert().
  69  *
  70  * To lookup a value corresponding to a given key, use
  71  * g_hash_table_lookup() and g_hash_table_lookup_extended().
  72  *
  73  * g_hash_table_lookup_extended() can also be used to simply
  74  * check if a key is present in the hash table.
  75  *
  76  * To remove a key and value, use g_hash_table_remove().
  77  *
  78  * To call a function for each key and value pair use
  79  * g_hash_table_foreach() or use a iterator to iterate over the
  80  * key/value pairs in the hash table, see #GHashTableIter.
  81  *
  82  * To destroy a #GHashTable use g_hash_table_destroy().
  83  *
  84  * <example>
  85  * <title>Using a GHashTable as a set</title>
  86  * <para>
  87  * A common use-case for hash tables is to store information about
  88  * a set of keys, without associating any particular value with each
  89  * key. GHashTable optimizes one way of doing so: If you store only
  90  * key-value pairs where key == value, then GHashTable does not
  91  * allocate memory to store the values, which can be a considerable
  92  * space saving, if your set is large.
  93  * </para>
  94  * <programlisting>
  95  * GHashTable *
  96  * set_new (GHashFunc      hash_func,
  97  *          GEqualFunc     equal_func,
  98  *          GDestroyNotify destroy)
  99  * {
 100  *   return g_hash_table_new_full (hash_func, equal_func, destroy);
 101  * }
 102  *
 103  * void
 104  * set_insert (GHashTable *set,
 105  *             gpointer    element)
 106  * {
 107  *   g_hash_table_insert (set, element, element);
 108  * }
 109  *
 110  * gboolean
 111  * set_contains (GHashTable *set,
 112  *               gpointer    element)
 113  * {
 114  *   return g_hash_table_lookup_extended (set, element, NULL, NULL);
 115  * }
 116  *
 117  * gboolean
 118  * set_remove (GHashTable *set,
 119  *             gpointer    element)
 120  * {
 121  *   return g_hash_table_remove (set, element);
 122  * }
 123  * </programlisting>
 124  * </example>
 125  */
 126
 127 /**
 128  * GHashTable:
 129  *
 130  * The #GHashTable struct is an opaque data structure to represent a
 131  * <link linkend="glib-Hash-Tables">Hash Table</link>. It should only be
 132  * accessed via the following functions.
 133  **/
 134
 135 /**
 136  * GHashFunc:
 137  * @key: a key.
 138  * @Returns: the hash value corresponding to the key.
 139  *
 140  * Specifies the type of the hash function which is passed to
 141  * g_hash_table_new() when a #GHashTable is created.
 142  *
 143  * The function is passed a key and should return a #guint hash value.
 144  * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
 145  * hash functions which can be used when the key is a #gpointer, #gint,
 146  * and #gchar* respectively.
 147  *
 148  * <!-- FIXME: Need more here. --> The hash values should be evenly
 149  * distributed over a fairly large range? The modulus is taken with the
 150  * hash table size (a prime number) to find the 'bucket' to place each
 151  * key into. The function should also be very fast, since it is called
 152  * for each key lookup.
 153  **/
 154
 155 /**
 156  * GHFunc:
 157  * @key: a key.
 158  * @value: the value corresponding to the key.
 159  * @user_data: user data passed to g_hash_table_foreach().
 160  *
 161  * Specifies the type of the function passed to g_hash_table_foreach().
 162  * It is called with each key/value pair, together with the @user_data
 163  * parameter which is passed to g_hash_table_foreach().
 164  **/
 165
 166 /**
 167  * GHRFunc:
 168  * @key: a key.
 169  * @value: the value associated with the key.
 170  * @user_data: user data passed to g_hash_table_remove().
 171  * @Returns: %TRUE if the key/value pair should be removed from the
 172  *           #GHashTable.
 173  *
 174  * Specifies the type of the function passed to
 175  * g_hash_table_foreach_remove(). It is called with each key/value
 176  * pair, together with the @user_data parameter passed to
 177  * g_hash_table_foreach_remove(). It should return %TRUE if the
 178  * key/value pair should be removed from the #GHashTable.
 179  **/
 180
 181 /**
 182  * GEqualFunc:
 183  * @a: a value.
 184  * @b: a value to compare with.
 185  * @Returns: %TRUE if @a = @b; %FALSE otherwise.
 186  *
 187  * Specifies the type of a function used to test two values for
 188  * equality. The function should return %TRUE if both values are equal
 189  * and %FALSE otherwise.
 190  **/
 191
 192 /**
 193  * GHashTableIter:
 194  *
 195  * A GHashTableIter structure represents an iterator that can be used
 196  * to iterate over the elements of a #GHashTable. GHashTableIter
 197  * structures are typically allocated on the stack and then initialized
 198  * with g_hash_table_iter_init().
 199  **/
 200
 201 #define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */
 202
 203 #define HASH_IS_UNUSED(h_) ((h_) == 0)
 204 #define HASH_IS_TOOMBSTONE(h_) ((h_) == 1)
 205 #define HASH_IS_REAL(h_) ((h_) >= 2)
 206
 207 struct _GHashTable
 208 {
 209   gint             size;
 210   gint             mod;
 211   guint            mask;
 212   gint             nnodes;
 213   gint             noccupied;  /* nnodes + tombstones */
 214
 215   gpointer        *keys;
 216   guint           *hashes;
 217   gpointer        *values;
 218
 219   GHashFunc        hash_func;
 220   GEqualFunc       key_equal_func;
 221   volatile gint    ref_count;
 222 #ifndef G_DISABLE_ASSERT
 223   /*
 224    * Tracks the structure of the hash table, not its contents: is only
 225    * incremented when a node is added or removed (is not incremented
 226    * when the key or data of a node is modified).
 227    */
 228   int              version;
 229 #endif
 230   GDestroyNotify   key_destroy_func;
 231   GDestroyNotify   value_destroy_func;
 232 };
 233
 234 typedef struct
 235 {
 236   GHashTable  *hash_table;
 237   gpointer     dummy1;
 238   gpointer     dummy2;
 239   int          position;
 240   gboolean     dummy3;
 241   int          version;
 242 } RealIter;
 243
 244 /* Each table size has an associated prime modulo (the first prime
 245  * lower than the table size) used to find the initial bucket. Probing
 246  * then works modulo 2^n. The prime modulo is necessary to get a
 247  * good distribution with poor hash functions. */
 248 static const gint prime_mod [] =
 249 {
 250   1,          /* For 1 << 0 */
 251   2,
 252   3,
 253   7,
 254   13,
 255   31,
 256   61,
 257   127,
 258   251,
 259   509,
 260   1021,
 261   2039,
 262   4093,
 263   8191,
 264   16381,
 265   32749,
 266   65521,      /* For 1 << 16 */
 267   131071,
 268   262139,
 269   524287,
 270   1048573,
 271   2097143,
 272   4194301,
 273   8388593,
 274   16777213,
 275   33554393,
 276   67108859,
 277   134217689,
 278   268435399,
 279   536870909,
 280   1073741789,
 281   2147483647  /* For 1 << 31 */
 282 };
 283
 284 static void
 285 g_hash_table_set_shift (GHashTable *hash_table, gint shift)
 286 {
 287   gint i;
 288   guint mask = 0;
 289
 290   hash_table->size = 1 << shift;
 291   hash_table->mod  = prime_mod [shift];
 292
 293   for (i = 0; i < shift; i++)
 294     {
 295       mask <<= 1;
 296       mask |= 1;
 297     }
 298
 299   hash_table->mask = mask;
 300 }
 301
 302 static gint
 303 g_hash_table_find_closest_shift (gint n)
 304 {
 305   gint i;
 306
 307   for (i = 0; n; i++)
 308     n >>= 1;
 309
 310   return i;
 311 }
 312
 313 static void
 314 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
 315 {
 316   gint shift;
 317
 318   shift = g_hash_table_find_closest_shift (size);
 319   shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
 320
 321   g_hash_table_set_shift (hash_table, shift);
 322 }
 323
 324 /*
 325  * g_hash_table_lookup_node:
 326  * @hash_table: our #GHashTable
 327  * @key: the key to lookup against
 328  * @hash_return: key hash return location
 329  * Return value: index of the described node
 330  *
 331  * Performs a lookup in the hash table, preserving extra information
 332  * usually needed for insertion.
 333  *
 334  * This function first computes the hash value of the key using the
 335  * user's hash function.
 336  *
 337  * If an entry in the table matching @key is found then this function
 338  * returns the index of that entry in the table, and if not, the
 339  * index of an unused node (empty or tombstone) where the key can be
 340  * inserted.
 341  *
 342  * The computed hash value is returned in the variable pointed to
 343  * by @hash_return. This is to save insertions from having to compute
 344  * the hash record again for the new record.
 345  */
 346 static inline guint
 347 g_hash_table_lookup_node (GHashTable    *hash_table,
 348                           gconstpointer  key,
 349                           guint         *hash_return)
 350 {
 351   guint node_index;
 352   guint hash_value;
 353   guint first_tombstone;
 354   gboolean have_tombstone = FALSE;
 355   guint step = 0;
 356
 357   hash_value = (* hash_table->hash_func) (key);
 358   if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
 359     hash_value = 2;
 360
 361   *hash_return = hash_value;
 362
 363   node_index = hash_value % hash_table->mod;
 364
 365   while (!HASH_IS_UNUSED (hash_table->hashes[node_index]))
 366     {
 367       guint node_hash = hash_table->hashes[node_index];
 368
 369       /*  We first check if our full hash values
 370        *  are equal so we can avoid calling the full-blown
 371        *  key equality function in most cases.
 372        */
 373
 374       if (node_hash == hash_value)
 375         {
 376           gpointer node_key = hash_table->keys[node_index];
 377
 378           if (hash_table->key_equal_func)
 379             {
 380               if (hash_table->key_equal_func (node_key, key))
 381                 return node_index;
 382             }
 383           else if (node_key == key)
 384             {
 385               return node_index;
 386             }
 387         }
 388       else if (HASH_IS_TOOMBSTONE (node_hash) && !have_tombstone)
 389         {
 390           first_tombstone = node_index;
 391           have_tombstone = TRUE;
 392         }
 393
 394       step++;
 395       node_index += step;
 396       node_index &= hash_table->mask;
 397     }
 398
 399   if (have_tombstone)
 400     return first_tombstone;
 401
 402   return node_index;
 403 }
 404
 405 /*
 406  * g_hash_table_remove_node:
 407  * @hash_table: our #GHashTable
 408  * @node: pointer to node to remove
 409  * @notify: %TRUE if the destroy notify handlers are to be called
 410  *
 411  * Removes a node from the hash table and updates the node count.
 412  * The node is replaced by a tombstone. No table resize is performed.
 413  *
 414  * If @notify is %TRUE then the destroy notify functions are called
 415  * for the key and value of the hash node.
 416  */
 417 static void
 418 g_hash_table_remove_node (GHashTable   *hash_table,
 419                           int           i,
 420                           gboolean      notify)
 421 {
 422   if (notify && hash_table->key_destroy_func)
 423     hash_table->key_destroy_func (hash_table->keys[i]);
 424
 425   if (notify && hash_table->value_destroy_func)
 426     hash_table->value_destroy_func (hash_table->values[i]);
 427
 428   /* Erect tombstone */
 429   hash_table->hashes[i] = 1;
 430
 431   /* Be GC friendly */
 432   hash_table->keys[i] = NULL;
 433   hash_table->values[i] = NULL;
 434
 435   hash_table->nnodes--;
 436 }
 437
 438 /*
 439  * g_hash_table_remove_all_nodes:
 440  * @hash_table: our #GHashTable
 441  * @notify: %TRUE if the destroy notify handlers are to be called
 442  *
 443  * Removes all nodes from the table.  Since this may be a precursor to
 444  * freeing the table entirely, no resize is performed.
 445  *
 446  * If @notify is %TRUE then the destroy notify functions are called
 447  * for the key and value of the hash node.
 448  */
 449 static void
 450 g_hash_table_remove_all_nodes (GHashTable *hash_table,
 451                                gboolean    notify)
 452 {
 453   int i;
 454
 455   if (notify &&
 456       (hash_table->key_destroy_func != NULL ||
 457        hash_table->value_destroy_func != NULL))
 458     {
 459       for (i = 0; i < hash_table->size; i++)
 460         {
 461           if (HASH_IS_REAL (hash_table->hashes[i]))
 462             {
 463               if (hash_table->key_destroy_func != NULL)
 464                 hash_table->key_destroy_func (hash_table->keys[i]);
 465
 466               if (hash_table->value_destroy_func != NULL)
 467                 hash_table->value_destroy_func (hash_table->values[i]);
 468             }
 469         }
 470     }
 471
 472   /* We need to set node->key_hash = 0 for all nodes - might as well be GC
 473    * friendly and clear everything
 474    */
 475   memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
 476   memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
 477   memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
 478
 479   hash_table->nnodes = 0;
 480   hash_table->noccupied = 0;
 481 }
 482
 483 /*
 484  * g_hash_table_resize:
 485  * @hash_table: our #GHashTable
 486  *
 487  * Resizes the hash table to the optimal size based on the number of
 488  * nodes currently held.  If you call this function then a resize will
 489  * occur, even if one does not need to occur.  Use
 490  * g_hash_table_maybe_resize() instead.
 491  *
 492  * This function may "resize" the hash table to its current size, with
 493  * the side effect of cleaning up tombstones and otherwise optimizing
 494  * the probe sequences.
 495  */
 496 static void
 497 g_hash_table_resize (GHashTable *hash_table)
 498 {
 499   gpointer *new_keys;
 500   gpointer *new_values;
 501   guint *new_hashes;
 502   gint old_size;
 503   gint i;
 504
 505   old_size = hash_table->size;
 506   g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
 507
 508   new_keys = g_new0 (gpointer, hash_table->size);
 509   if (hash_table->keys == hash_table->values)
 510     new_values = new_keys;
 511   else
 512     new_values = g_new0 (gpointer, hash_table->size);
 513   new_hashes = g_new0 (guint, hash_table->size);
 514
 515   for (i = 0; i < old_size; i++)
 516     {
 517       guint node_hash = hash_table->hashes[i];
 518       guint hash_val;
 519       guint step = 0;
 520
 521       if (!HASH_IS_REAL (node_hash))
 522         continue;
 523
 524       hash_val = node_hash % hash_table->mod;
 525
 526       while (!HASH_IS_UNUSED (new_hashes[hash_val]))
 527         {
 528           step++;
 529           hash_val += step;
 530           hash_val &= hash_table->mask;
 531         }
 532
 533       new_hashes[hash_val] = hash_table->hashes[i];
 534       new_keys[hash_val] = hash_table->keys[i];
 535       new_values[hash_val] = hash_table->values[i];
 536     }
 537
 538   if (hash_table->keys != hash_table->values)
 539     g_free (hash_table->values);
 540
 541   g_free (hash_table->keys);
 542   g_free (hash_table->hashes);
 543
 544   hash_table->keys = new_keys;
 545   hash_table->values = new_values;
 546   hash_table->hashes = new_hashes;
 547
 548   hash_table->noccupied = hash_table->nnodes;
 549 }
 550
 551 /*
 552  * g_hash_table_maybe_resize:
 553  * @hash_table: our #GHashTable
 554  *
 555  * Resizes the hash table, if needed.
 556  *
 557  * Essentially, calls g_hash_table_resize() if the table has strayed
 558  * too far from its ideal size for its number of nodes.
 559  */
 560 static inline void
 561 g_hash_table_maybe_resize (GHashTable *hash_table)
 562 {
 563   gint noccupied = hash_table->noccupied;
 564   gint size = hash_table->size;
 565
 566   if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
 567       (size <= noccupied + (noccupied / 16)))
 568     g_hash_table_resize (hash_table);
 569 }
 570
 571 /**
 572  * g_hash_table_new:
 573  * @hash_func: a function to create a hash value from a key.
 574  *   Hash values are used to determine where keys are stored within the
 575  *   #GHashTable data structure. The g_direct_hash(), g_int_hash(),
 576  *   g_int64_hash(), g_double_hash() and g_str_hash() functions are provided
 577  *   for some common types of keys.
 578  *   If hash_func is %NULL, g_direct_hash() is used.
 579  * @key_equal_func: a function to check two keys for equality.  This is
 580  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
 581  *   g_int_equal(), g_int64_equal(), g_double_equal() and g_str_equal()
 582  *   functions are provided for the most common types of keys.
 583  *   If @key_equal_func is %NULL, keys are compared directly in a similar
 584  *   fashion to g_direct_equal(), but without the overhead of a function call.
 585  *
 586  * Creates a new #GHashTable with a reference count of 1.
 587  *
 588  * Return value: a new #GHashTable.
 589  **/
 590 GHashTable*
 591 g_hash_table_new (GHashFunc    hash_func,
 592                   GEqualFunc   key_equal_func)
 593 {
 594   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 595 }
 596
 597
 598 /**
 599  * g_hash_table_new_full:
 600  * @hash_func: a function to create a hash value from a key.
 601  * @key_equal_func: a function to check two keys for equality.
 602  * @key_destroy_func: a function to free the memory allocated for the key
 603  *   used when removing the entry from the #GHashTable or %NULL if you
 604  *   don't want to supply such a function.
 605  * @value_destroy_func: a function to free the memory allocated for the
 606  *   value used when removing the entry from the #GHashTable or %NULL if
 607  *   you don't want to supply such a function.
 608  *
 609  * Creates a new #GHashTable like g_hash_table_new() with a reference count
 610  * of 1 and allows to specify functions to free the memory allocated for the
 611  * key and value that get called when removing the entry from the #GHashTable.
 612  *
 613  * Return value: a new #GHashTable.
 614  **/
 615 GHashTable*
 616 g_hash_table_new_full (GHashFunc       hash_func,
 617                        GEqualFunc      key_equal_func,
 618                        GDestroyNotify  key_destroy_func,
 619                        GDestroyNotify  value_destroy_func)
 620 {
 621   GHashTable *hash_table;
 622
 623   hash_table = g_slice_new (GHashTable);
 624   g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
 625   hash_table->nnodes             = 0;
 626   hash_table->noccupied          = 0;
 627   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
 628   hash_table->key_equal_func     = key_equal_func;
 629   hash_table->ref_count          = 1;
 630 #ifndef G_DISABLE_ASSERT
 631   hash_table->version            = 0;
 632 #endif
 633   hash_table->key_destroy_func   = key_destroy_func;
 634   hash_table->value_destroy_func = value_destroy_func;
 635   hash_table->keys               = g_new0 (gpointer, hash_table->size);
 636   hash_table->values             = hash_table->keys;
 637   hash_table->hashes             = g_new0 (guint, hash_table->size);
 638
 639   return hash_table;
 640 }
 641
 642 /**
 643  * g_hash_table_iter_init:
 644  * @iter: an uninitialized #GHashTableIter.
 645  * @hash_table: a #GHashTable.
 646  *
 647  * Initializes a key/value pair iterator and associates it with
 648  * @hash_table. Modifying the hash table after calling this function
 649  * invalidates the returned iterator.
 650  * |[
 651  * GHashTableIter iter;
 652  * gpointer key, value;
 653  *
 654  * g_hash_table_iter_init (&iter, hash_table);
 655  * while (g_hash_table_iter_next (&iter, &key, &value))
 656  *   {
 657  *     /&ast; do something with key and value &ast;/
 658  *   }
 659  * ]|
 660  *
 661  * Since: 2.16
 662  **/
 663 void
 664 g_hash_table_iter_init (GHashTableIter *iter,
 665                         GHashTable     *hash_table)
 666 {
 667   RealIter *ri = (RealIter *) iter;
 668
 669   g_return_if_fail (iter != NULL);
 670   g_return_if_fail (hash_table != NULL);
 671
 672   ri->hash_table = hash_table;
 673   ri->position = -1;
 674 #ifndef G_DISABLE_ASSERT
 675   ri->version = hash_table->version;
 676 #endif
 677 }
 678
 679 /**
 680  * g_hash_table_iter_next:
 681  * @iter: an initialized #GHashTableIter.
 682  * @key: a location to store the key, or %NULL.
 683  * @value: a location to store the value, or %NULL.
 684  *
 685  * Advances @iter and retrieves the key and/or value that are now
 686  * pointed to as a result of this advancement. If %FALSE is returned,
 687  * @key and @value are not set, and the iterator becomes invalid.
 688  *
 689  * Return value: %FALSE if the end of the #GHashTable has been reached.
 690  *
 691  * Since: 2.16
 692  **/
 693 gboolean
 694 g_hash_table_iter_next (GHashTableIter *iter,
 695                         gpointer       *key,
 696                         gpointer       *value)
 697 {
 698   RealIter *ri = (RealIter *) iter;
 699   gint position;
 700
 701   g_return_val_if_fail (iter != NULL, FALSE);
 702 #ifndef G_DISABLE_ASSERT
 703   g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
 704 #endif
 705   g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
 706
 707   position = ri->position;
 708
 709   do
 710     {
 711       position++;
 712       if (position >= ri->hash_table->size)
 713         {
 714           ri->position = position;
 715           return FALSE;
 716         }
 717     }
 718   while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
 719
 720   if (key != NULL)
 721     *key = ri->hash_table->keys[position];
 722   if (value != NULL)
 723     *value = ri->hash_table->values[position];
 724
 725   ri->position = position;
 726   return TRUE;
 727 }
 728
 729 /**
 730  * g_hash_table_iter_get_hash_table:
 731  * @iter: an initialized #GHashTableIter.
 732  *
 733  * Returns the #GHashTable associated with @iter.
 734  *
 735  * Return value: the #GHashTable associated with @iter.
 736  *
 737  * Since: 2.16
 738  **/
 739 GHashTable *
 740 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
 741 {
 742   g_return_val_if_fail (iter != NULL, NULL);
 743
 744   return ((RealIter *) iter)->hash_table;
 745 }
 746
 747 static void
 748 iter_remove_or_steal (RealIter *ri, gboolean notify)
 749 {
 750   g_return_if_fail (ri != NULL);
 751 #ifndef G_DISABLE_ASSERT
 752   g_return_if_fail (ri->version == ri->hash_table->version);
 753 #endif
 754   g_return_if_fail (ri->position >= 0);
 755   g_return_if_fail (ri->position < ri->hash_table->size);
 756
 757   g_hash_table_remove_node (ri->hash_table, ri->position, notify);
 758
 759 #ifndef G_DISABLE_ASSERT
 760   ri->version++;
 761   ri->hash_table->version++;
 762 #endif
 763 }
 764
 765 /**
 766  * g_hash_table_iter_remove:
 767  * @iter: an initialized #GHashTableIter.
 768  *
 769  * Removes the key/value pair currently pointed to by the iterator
 770  * from its associated #GHashTable. Can only be called after
 771  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 772  * than once for the same key/value pair.
 773  *
 774  * If the #GHashTable was created using g_hash_table_new_full(), the
 775  * key and value are freed using the supplied destroy functions, otherwise
 776  * you have to make sure that any dynamically allocated values are freed
 777  * yourself.
 778  *
 779  * Since: 2.16
 780  **/
 781 void
 782 g_hash_table_iter_remove (GHashTableIter *iter)
 783 {
 784   iter_remove_or_steal ((RealIter *) iter, TRUE);
 785 }
 786
 787 /**
 788  * g_hash_table_iter_steal:
 789  * @iter: an initialized #GHashTableIter.
 790  *
 791  * Removes the key/value pair currently pointed to by the iterator
 792  * from its associated #GHashTable, without calling the key and value
 793  * destroy functions. Can only be called after
 794  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 795  * than once for the same key/value pair.
 796  *
 797  * Since: 2.16
 798  **/
 799 void
 800 g_hash_table_iter_steal (GHashTableIter *iter)
 801 {
 802   iter_remove_or_steal ((RealIter *) iter, FALSE);
 803 }
 804
 805
 806 /**
 807  * g_hash_table_ref:
 808  * @hash_table: a valid #GHashTable.
 809  *
 810  * Atomically increments the reference count of @hash_table by one.
 811  * This function is MT-safe and may be called from any thread.
 812  *
 813  * Return value: the passed in #GHashTable.
 814  *
 815  * Since: 2.10
 816  **/
 817 GHashTable*
 818 g_hash_table_ref (GHashTable *hash_table)
 819 {
 820   g_return_val_if_fail (hash_table != NULL, NULL);
 821   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 822
 823   g_atomic_int_add (&hash_table->ref_count, 1);
 824   return hash_table;
 825 }
 826
 827 /**
 828  * g_hash_table_unref:
 829  * @hash_table: a valid #GHashTable.
 830  *
 831  * Atomically decrements the reference count of @hash_table by one.
 832  * If the reference count drops to 0, all keys and values will be
 833  * destroyed, and all memory allocated by the hash table is released.
 834  * This function is MT-safe and may be called from any thread.
 835  *
 836  * Since: 2.10
 837  **/
 838 void
 839 g_hash_table_unref (GHashTable *hash_table)
 840 {
 841   g_return_if_fail (hash_table != NULL);
 842   g_return_if_fail (hash_table->ref_count > 0);
 843
 844   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 845     {
 846       g_hash_table_remove_all_nodes (hash_table, TRUE);
 847       if (hash_table->keys != hash_table->values)
 848         g_free (hash_table->values);
 849       g_free (hash_table->keys);
 850       g_free (hash_table->hashes);
 851       g_slice_free (GHashTable, hash_table);
 852     }
 853 }
 854
 855 /**
 856  * g_hash_table_destroy:
 857  * @hash_table: a #GHashTable.
 858  *
 859  * Destroys all keys and values in the #GHashTable and decrements its
 860  * reference count by 1. If keys and/or values are dynamically allocated,
 861  * you should either free them first or create the #GHashTable with destroy
 862  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 863  * functions you supplied will be called on all keys and values during the
 864  * destruction phase.
 865  **/
 866 void
 867 g_hash_table_destroy (GHashTable *hash_table)
 868 {
 869   g_return_if_fail (hash_table != NULL);
 870   g_return_if_fail (hash_table->ref_count > 0);
 871
 872   g_hash_table_remove_all (hash_table);
 873   g_hash_table_unref (hash_table);
 874 }
 875
 876 /**
 877  * g_hash_table_lookup:
 878  * @hash_table: a #GHashTable.
 879  * @key: the key to look up.
 880  *
 881  * Looks up a key in a #GHashTable. Note that this function cannot
 882  * distinguish between a key that is not present and one which is present
 883  * and has the value %NULL. If you need this distinction, use
 884  * g_hash_table_lookup_extended().
 885  *
 886  * Return value: the associated value, or %NULL if the key is not found.
 887  **/
 888 gpointer
 889 g_hash_table_lookup (GHashTable   *hash_table,
 890                      gconstpointer key)
 891 {
 892   guint node_index;
 893   guint node_hash;
 894
 895   g_return_val_if_fail (hash_table != NULL, NULL);
 896
 897   node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
 898
 899   return HASH_IS_REAL (hash_table->hashes[node_index])
 900     ? hash_table->values[node_index]
 901     : NULL;
 902 }
 903
 904 /**
 905  * g_hash_table_lookup_extended:
 906  * @hash_table: a #GHashTable
 907  * @lookup_key: the key to look up
 908  * @orig_key: return location for the original key, or %NULL
 909  * @value: return location for the value associated with the key, or %NULL
 910  *
 911  * Looks up a key in the #GHashTable, returning the original key and the
 912  * associated value and a #gboolean which is %TRUE if the key was found. This
 913  * is useful if you need to free the memory allocated for the original key,
 914  * for example before calling g_hash_table_remove().
 915  *
 916  * You can actually pass %NULL for @lookup_key to test
 917  * whether the %NULL key exists, provided the hash and equal functions
 918  * of @hash_table are %NULL-safe.
 919  *
 920  * Return value: %TRUE if the key was found in the #GHashTable.
 921  **/
 922 gboolean
 923 g_hash_table_lookup_extended (GHashTable    *hash_table,
 924                               gconstpointer  lookup_key,
 925                               gpointer      *orig_key,
 926                               gpointer      *value)
 927 {
 928   guint node_index;
 929   guint node_hash;
 930
 931   g_return_val_if_fail (hash_table != NULL, FALSE);
 932
 933   node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
 934
 935   if (!HASH_IS_REAL (hash_table->hashes[node_index]))
 936     return FALSE;
 937
 938   if (orig_key)
 939     *orig_key = hash_table->keys[node_index];
 940
 941   if (value)
 942     *value = hash_table->values[node_index];
 943
 944   return TRUE;
 945 }
 946
 947 /*
 948  * g_hash_table_insert_internal:
 949  * @hash_table: our #GHashTable
 950  * @key: the key to insert
 951  * @value: the value to insert
 952  * @keep_new_key: if %TRUE and this key already exists in the table
 953  *   then call the destroy notify function on the old key.  If %FALSE
 954  *   then call the destroy notify function on the new key.
 955  *
 956  * Implements the common logic for the g_hash_table_insert() and
 957  * g_hash_table_replace() functions.
 958  *
 959  * Do a lookup of @key.  If it is found, replace it with the new
 960  * @value (and perhaps the new @key).  If it is not found, create a
 961  * new node.
 962  */
 963 static void
 964 g_hash_table_insert_internal (GHashTable *hash_table,
 965                               gpointer    key,
 966                               gpointer    value,
 967                               gboolean    keep_new_key)
 968 {
 969   guint node_index;
 970   guint key_hash;
 971   guint old_hash;
 972
 973   g_return_if_fail (hash_table != NULL);
 974   g_return_if_fail (hash_table->ref_count > 0);
 975
 976   if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
 977     hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
 978
 979   node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
 980
 981   old_hash = hash_table->hashes[node_index];
 982
 983   if (HASH_IS_REAL (old_hash))
 984     {
 985       if (keep_new_key)
 986         {
 987           if (hash_table->key_destroy_func)
 988             hash_table->key_destroy_func (hash_table->keys[node_index]);
 989           hash_table->keys[node_index] = key;
 990         }
 991       else
 992         {
 993           if (hash_table->key_destroy_func)
 994             hash_table->key_destroy_func (key);
 995         }
 996
 997       if (hash_table->value_destroy_func)
 998         hash_table->value_destroy_func (hash_table->values[node_index]);
 999
1000       hash_table->values[node_index] = value;
1001     }
1002   else
1003     {
1004       hash_table->keys[node_index] = key;
1005       hash_table->values[node_index] = value;
1006       hash_table->hashes[node_index] = key_hash;
1007
1008       hash_table->nnodes++;
1009
1010       if (HASH_IS_UNUSED (old_hash))
1011         {
1012           /* We replaced an empty node, and not a tombstone */
1013           hash_table->noccupied++;
1014           g_hash_table_maybe_resize (hash_table);
1015         }
1016
1017 #ifndef G_DISABLE_ASSERT
1018       hash_table->version++;
1019 #endif
1020     }
1021 }
1022
1023 /**
1024  * g_hash_table_insert:
1025  * @hash_table: a #GHashTable.
1026  * @key: a key to insert.
1027  * @value: the value to associate with the key.
1028  *
1029  * Inserts a new key and value into a #GHashTable.
1030  *
1031  * If the key already exists in the #GHashTable its current value is replaced
1032  * with the new value. If you supplied a @value_destroy_func when creating the
1033  * #GHashTable, the old value is freed using that function. If you supplied
1034  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
1035  * using that function.
1036  **/
1037 void
1038 g_hash_table_insert (GHashTable *hash_table,
1039                      gpointer    key,
1040                      gpointer    value)
1041 {
1042   g_hash_table_insert_internal (hash_table, key, value, FALSE);
1043 }
1044
1045 /**
1046  * g_hash_table_replace:
1047  * @hash_table: a #GHashTable.
1048  * @key: a key to insert.
1049  * @value: the value to associate with the key.
1050  *
1051  * Inserts a new key and value into a #GHashTable similar to
1052  * g_hash_table_insert(). The difference is that if the key already exists
1053  * in the #GHashTable, it gets replaced by the new key. If you supplied a
1054  * @value_destroy_func when creating the #GHashTable, the old value is freed
1055  * using that function. If you supplied a @key_destroy_func when creating the
1056  * #GHashTable, the old key is freed using that function.
1057  **/
1058 void
1059 g_hash_table_replace (GHashTable *hash_table,
1060                       gpointer    key,
1061                       gpointer    value)
1062 {
1063   g_hash_table_insert_internal (hash_table, key, value, TRUE);
1064 }
1065
1066 /*
1067  * g_hash_table_remove_internal:
1068  * @hash_table: our #GHashTable
1069  * @key: the key to remove
1070  * @notify: %TRUE if the destroy notify handlers are to be called
1071  * Return value: %TRUE if a node was found and removed, else %FALSE
1072  *
1073  * Implements the common logic for the g_hash_table_remove() and
1074  * g_hash_table_steal() functions.
1075  *
1076  * Do a lookup of @key and remove it if it is found, calling the
1077  * destroy notify handlers only if @notify is %TRUE.
1078  */
1079 static gboolean
1080 g_hash_table_remove_internal (GHashTable    *hash_table,
1081                               gconstpointer  key,
1082                               gboolean       notify)
1083 {
1084   guint node_index;
1085   guint node_hash;
1086
1087   g_return_val_if_fail (hash_table != NULL, FALSE);
1088
1089   node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1090
1091   if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1092     return FALSE;
1093
1094   g_hash_table_remove_node (hash_table, node_index, notify);
1095   g_hash_table_maybe_resize (hash_table);
1096
1097 #ifndef G_DISABLE_ASSERT
1098   hash_table->version++;
1099 #endif
1100
1101   return TRUE;
1102 }
1103
1104 /**
1105  * g_hash_table_remove:
1106  * @hash_table: a #GHashTable.
1107  * @key: the key to remove.
1108  *
1109  * Removes a key and its associated value from a #GHashTable.
1110  *
1111  * If the #GHashTable was created using g_hash_table_new_full(), the
1112  * key and value are freed using the supplied destroy functions, otherwise
1113  * you have to make sure that any dynamically allocated values are freed
1114  * yourself.
1115  *
1116  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1117  **/
1118 gboolean
1119 g_hash_table_remove (GHashTable    *hash_table,
1120                      gconstpointer  key)
1121 {
1122   return g_hash_table_remove_internal (hash_table, key, TRUE);
1123 }
1124
1125 /**
1126  * g_hash_table_steal:
1127  * @hash_table: a #GHashTable.
1128  * @key: the key to remove.
1129  *
1130  * Removes a key and its associated value from a #GHashTable without
1131  * calling the key and value destroy functions.
1132  *
1133  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1134  **/
1135 gboolean
1136 g_hash_table_steal (GHashTable    *hash_table,
1137                     gconstpointer  key)
1138 {
1139   return g_hash_table_remove_internal (hash_table, key, FALSE);
1140 }
1141
1142 /**
1143  * g_hash_table_remove_all:
1144  * @hash_table: a #GHashTable
1145  *
1146  * Removes all keys and their associated values from a #GHashTable.
1147  *
1148  * If the #GHashTable was created using g_hash_table_new_full(), the keys
1149  * and values are freed using the supplied destroy functions, otherwise you
1150  * have to make sure that any dynamically allocated values are freed
1151  * yourself.
1152  *
1153  * Since: 2.12
1154  **/
1155 void
1156 g_hash_table_remove_all (GHashTable *hash_table)
1157 {
1158   g_return_if_fail (hash_table != NULL);
1159
1160 #ifndef G_DISABLE_ASSERT
1161   if (hash_table->nnodes != 0)
1162     hash_table->version++;
1163 #endif
1164
1165   g_hash_table_remove_all_nodes (hash_table, TRUE);
1166   g_hash_table_maybe_resize (hash_table);
1167 }
1168
1169 /**
1170  * g_hash_table_steal_all:
1171  * @hash_table: a #GHashTable.
1172  *
1173  * Removes all keys and their associated values from a #GHashTable
1174  * without calling the key and value destroy functions.
1175  *
1176  * Since: 2.12
1177  **/
1178 void
1179 g_hash_table_steal_all (GHashTable *hash_table)
1180 {
1181   g_return_if_fail (hash_table != NULL);
1182
1183 #ifndef G_DISABLE_ASSERT
1184   if (hash_table->nnodes != 0)
1185     hash_table->version++;
1186 #endif
1187
1188   g_hash_table_remove_all_nodes (hash_table, FALSE);
1189   g_hash_table_maybe_resize (hash_table);
1190 }
1191
1192 /*
1193  * g_hash_table_foreach_remove_or_steal:
1194  * @hash_table: our #GHashTable
1195  * @func: the user's callback function
1196  * @user_data: data for @func
1197  * @notify: %TRUE if the destroy notify handlers are to be called
1198  *
1199  * Implements the common logic for g_hash_table_foreach_remove() and
1200  * g_hash_table_foreach_steal().
1201  *
1202  * Iterates over every node in the table, calling @func with the key
1203  * and value of the node (and @user_data).  If @func returns %TRUE the
1204  * node is removed from the table.
1205  *
1206  * If @notify is true then the destroy notify handlers will be called
1207  * for each removed node.
1208  */
1209 static guint
1210 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1211                                       GHRFunc     func,
1212                                       gpointer    user_data,
1213                                       gboolean    notify)
1214 {
1215   guint deleted = 0;
1216   gint i;
1217
1218   for (i = 0; i < hash_table->size; i++)
1219     {
1220       guint node_hash = hash_table->hashes[i];
1221       gpointer node_key = hash_table->keys[i];
1222       gpointer node_value = hash_table->values[i];
1223
1224       if (HASH_IS_REAL (node_hash) &&
1225           (* func) (node_key, node_value, user_data))
1226         {
1227           g_hash_table_remove_node (hash_table, i, notify);
1228           deleted++;
1229         }
1230     }
1231
1232   g_hash_table_maybe_resize (hash_table);
1233
1234 #ifndef G_DISABLE_ASSERT
1235   if (deleted > 0)
1236     hash_table->version++;
1237 #endif
1238
1239   return deleted;
1240 }
1241
1242 /**
1243  * g_hash_table_foreach_remove:
1244  * @hash_table: a #GHashTable.
1245  * @func: the function to call for each key/value pair.
1246  * @user_data: user data to pass to the function.
1247  *
1248  * Calls the given function for each key/value pair in the #GHashTable.
1249  * If the function returns %TRUE, then the key/value pair is removed from the
1250  * #GHashTable. If you supplied key or value destroy functions when creating
1251  * the #GHashTable, they are used to free the memory allocated for the removed
1252  * keys and values.
1253  *
1254  * See #GHashTableIter for an alternative way to loop over the
1255  * key/value pairs in the hash table.
1256  *
1257  * Return value: the number of key/value pairs removed.
1258  **/
1259 guint
1260 g_hash_table_foreach_remove (GHashTable *hash_table,
1261                              GHRFunc     func,
1262                              gpointer    user_data)
1263 {
1264   g_return_val_if_fail (hash_table != NULL, 0);
1265   g_return_val_if_fail (func != NULL, 0);
1266
1267   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1268 }
1269
1270 /**
1271  * g_hash_table_foreach_steal:
1272  * @hash_table: a #GHashTable.
1273  * @func: the function to call for each key/value pair.
1274  * @user_data: user data to pass to the function.
1275  *
1276  * Calls the given function for each key/value pair in the #GHashTable.
1277  * If the function returns %TRUE, then the key/value pair is removed from the
1278  * #GHashTable, but no key or value destroy functions are called.
1279  *
1280  * See #GHashTableIter for an alternative way to loop over the
1281  * key/value pairs in the hash table.
1282  *
1283  * Return value: the number of key/value pairs removed.
1284  **/
1285 guint
1286 g_hash_table_foreach_steal (GHashTable *hash_table,
1287                             GHRFunc     func,
1288                             gpointer    user_data)
1289 {
1290   g_return_val_if_fail (hash_table != NULL, 0);
1291   g_return_val_if_fail (func != NULL, 0);
1292
1293   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1294 }
1295
1296 /**
1297  * g_hash_table_foreach:
1298  * @hash_table: a #GHashTable.
1299  * @func: the function to call for each key/value pair.
1300  * @user_data: user data to pass to the function.
1301  *
1302  * Calls the given function for each of the key/value pairs in the
1303  * #GHashTable.  The function is passed the key and value of each
1304  * pair, and the given @user_data parameter.  The hash table may not
1305  * be modified while iterating over it (you can't add/remove
1306  * items). To remove all items matching a predicate, use
1307  * g_hash_table_foreach_remove().
1308  *
1309  * See g_hash_table_find() for performance caveats for linear
1310  * order searches in contrast to g_hash_table_lookup().
1311  **/
1312 void
1313 g_hash_table_foreach (GHashTable *hash_table,
1314                       GHFunc      func,
1315                       gpointer    user_data)
1316 {
1317   gint i;
1318
1319   g_return_if_fail (hash_table != NULL);
1320   g_return_if_fail (func != NULL);
1321
1322   for (i = 0; i < hash_table->size; i++)
1323     {
1324       guint node_hash = hash_table->hashes[i];
1325       gpointer node_key = hash_table->keys[i];
1326       gpointer node_value = hash_table->values[i];
1327
1328       if (HASH_IS_REAL (node_hash))
1329         (* func) (node_key, node_value, user_data);
1330     }
1331 }
1332
1333 /**
1334  * g_hash_table_find:
1335  * @hash_table: a #GHashTable.
1336  * @predicate:  function to test the key/value pairs for a certain property.
1337  * @user_data:  user data to pass to the function.
1338  *
1339  * Calls the given function for key/value pairs in the #GHashTable until
1340  * @predicate returns %TRUE.  The function is passed the key and value of
1341  * each pair, and the given @user_data parameter. The hash table may not
1342  * be modified while iterating over it (you can't add/remove items).
1343  *
1344  * Note, that hash tables are really only optimized for forward lookups,
1345  * i.e. g_hash_table_lookup().
1346  * So code that frequently issues g_hash_table_find() or
1347  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1348  * hash table) should probably be reworked to use additional or different
1349  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1350  * operation issued for all n values in a hash table ends up needing O(n*n)
1351  * operations).
1352  *
1353  * Return value: The value of the first key/value pair is returned, for which
1354  * func evaluates to %TRUE. If no pair with the requested property is found,
1355  * %NULL is returned.
1356  *
1357  * Since: 2.4
1358  **/
1359 gpointer
1360 g_hash_table_find (GHashTable      *hash_table,
1361                    GHRFunc          predicate,
1362                    gpointer         user_data)
1363 {
1364   gint i;
1365
1366   g_return_val_if_fail (hash_table != NULL, NULL);
1367   g_return_val_if_fail (predicate != NULL, NULL);
1368
1369   for (i = 0; i < hash_table->size; i++)
1370     {
1371       guint node_hash = hash_table->hashes[i];
1372       gpointer node_key = hash_table->keys[i];
1373       gpointer node_value = hash_table->values[i];
1374
1375       if (HASH_IS_REAL (node_hash) &&
1376           predicate (node_key, node_value, user_data))
1377         return node_value;
1378     }
1379
1380   return NULL;
1381 }
1382
1383 /**
1384  * g_hash_table_size:
1385  * @hash_table: a #GHashTable.
1386  *
1387  * Returns the number of elements contained in the #GHashTable.
1388  *
1389  * Return value: the number of key/value pairs in the #GHashTable.
1390  **/
1391 guint
1392 g_hash_table_size (GHashTable *hash_table)
1393 {
1394   g_return_val_if_fail (hash_table != NULL, 0);
1395
1396   return hash_table->nnodes;
1397 }
1398
1399 /**
1400  * g_hash_table_get_keys:
1401  * @hash_table: a #GHashTable
1402  *
1403  * Retrieves every key inside @hash_table. The returned data is valid
1404  * until @hash_table is modified.
1405  *
1406  * Return value: a #GList containing all the keys inside the hash
1407  *   table. The content of the list is owned by the hash table and
1408  *   should not be modified or freed. Use g_list_free() when done
1409  *   using the list.
1410  *
1411  * Since: 2.14
1412  */
1413 GList *
1414 g_hash_table_get_keys (GHashTable *hash_table)
1415 {
1416   gint i;
1417   GList *retval;
1418
1419   g_return_val_if_fail (hash_table != NULL, NULL);
1420
1421   retval = NULL;
1422   for (i = 0; i < hash_table->size; i++)
1423     {
1424       if (HASH_IS_REAL (hash_table->hashes[i]))
1425         retval = g_list_prepend (retval, hash_table->keys[i]);
1426     }
1427
1428   return retval;
1429 }
1430
1431 /**
1432  * g_hash_table_get_values:
1433  * @hash_table: a #GHashTable
1434  *
1435  * Retrieves every value inside @hash_table. The returned data is
1436  * valid until @hash_table is modified.
1437  *
1438  * Return value: a #GList containing all the values inside the hash
1439  *   table. The content of the list is owned by the hash table and
1440  *   should not be modified or freed. Use g_list_free() when done
1441  *   using the list.
1442  *
1443  * Since: 2.14
1444  */
1445 GList *
1446 g_hash_table_get_values (GHashTable *hash_table)
1447 {
1448   gint i;
1449   GList *retval;
1450
1451   g_return_val_if_fail (hash_table != NULL, NULL);
1452
1453   retval = NULL;
1454   for (i = 0; i < hash_table->size; i++)
1455     {
1456       if (HASH_IS_REAL (hash_table->hashes[i]))
1457         retval = g_list_prepend (retval, hash_table->values[i]);
1458     }
1459
1460   return retval;
1461 }