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