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