glib/ghash.c

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