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   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 843
 844   g_atomic_int_inc (&hash_table->ref_count);
 845
 846   return hash_table;
 847 }
 848
 849 /**
 850  * g_hash_table_unref:
 851  * @hash_table: a valid #GHashTable.
 852  *
 853  * Atomically decrements the reference count of @hash_table by one.
 854  * If the reference count drops to 0, all keys and values will be
 855  * destroyed, and all memory allocated by the hash table is released.
 856  * This function is MT-safe and may be called from any thread.
 857  *
 858  * Since: 2.10
 859  **/
 860 void
 861 g_hash_table_unref (GHashTable *hash_table)
 862 {
 863   g_return_if_fail (hash_table != NULL);
 864   g_return_if_fail (hash_table->ref_count > 0);
 865
 866   if (g_atomic_int_dec_and_test (&hash_table->ref_count))
 867     {
 868       g_hash_table_remove_all_nodes (hash_table, TRUE);
 869       if (hash_table->keys != hash_table->values)
 870         g_free (hash_table->values);
 871       g_free (hash_table->keys);
 872       g_free (hash_table->hashes);
 873       g_slice_free (GHashTable, hash_table);
 874     }
 875 }
 876
 877 /**
 878  * g_hash_table_destroy:
 879  * @hash_table: a #GHashTable.
 880  *
 881  * Destroys all keys and values in the #GHashTable and decrements its
 882  * reference count by 1. If keys and/or values are dynamically allocated,
 883  * you should either free them first or create the #GHashTable with destroy
 884  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 885  * functions you supplied will be called on all keys and values during the
 886  * destruction phase.
 887  **/
 888 void
 889 g_hash_table_destroy (GHashTable *hash_table)
 890 {
 891   g_return_if_fail (hash_table != NULL);
 892   g_return_if_fail (hash_table->ref_count > 0);
 893
 894   g_hash_table_remove_all (hash_table);
 895   g_hash_table_unref (hash_table);
 896 }
 897
 898 /**
 899  * g_hash_table_lookup:
 900  * @hash_table: a #GHashTable.
 901  * @key: the key to look up.
 902  *
 903  * Looks up a key in a #GHashTable. Note that this function cannot
 904  * distinguish between a key that is not present and one which is present
 905  * and has the value %NULL. If you need this distinction, use
 906  * g_hash_table_lookup_extended().
 907  *
 908  * Return value: the associated value, or %NULL if the key is not found.
 909  **/
 910 gpointer
 911 g_hash_table_lookup (GHashTable   *hash_table,
 912                      gconstpointer key)
 913 {
 914   guint node_index;
 915   guint node_hash;
 916
 917   g_return_val_if_fail (hash_table != NULL, NULL);
 918
 919   node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
 920
 921   return HASH_IS_REAL (hash_table->hashes[node_index])
 922     ? hash_table->values[node_index]
 923     : NULL;
 924 }
 925
 926 /**
 927  * g_hash_table_lookup_extended:
 928  * @hash_table: a #GHashTable
 929  * @lookup_key: the key to look up
 930  * @orig_key: return location for the original key, or %NULL
 931  * @value: return location for the value associated with the key, or %NULL
 932  *
 933  * Looks up a key in the #GHashTable, returning the original key and the
 934  * associated value and a #gboolean which is %TRUE if the key was found. This
 935  * is useful if you need to free the memory allocated for the original key,
 936  * for example before calling g_hash_table_remove().
 937  *
 938  * You can actually pass %NULL for @lookup_key to test
 939  * whether the %NULL key exists, provided the hash and equal functions
 940  * of @hash_table are %NULL-safe.
 941  *
 942  * Return value: %TRUE if the key was found in the #GHashTable.
 943  **/
 944 gboolean
 945 g_hash_table_lookup_extended (GHashTable    *hash_table,
 946                               gconstpointer  lookup_key,
 947                               gpointer      *orig_key,
 948                               gpointer      *value)
 949 {
 950   guint node_index;
 951   guint node_hash;
 952
 953   g_return_val_if_fail (hash_table != NULL, FALSE);
 954
 955   node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
 956
 957   if (!HASH_IS_REAL (hash_table->hashes[node_index]))
 958     return FALSE;
 959
 960   if (orig_key)
 961     *orig_key = hash_table->keys[node_index];
 962
 963   if (value)
 964     *value = hash_table->values[node_index];
 965
 966   return TRUE;
 967 }
 968
 969 /*
 970  * g_hash_table_insert_internal:
 971  * @hash_table: our #GHashTable
 972  * @key: the key to insert
 973  * @value: the value to insert
 974  * @keep_new_key: if %TRUE and this key already exists in the table
 975  *   then call the destroy notify function on the old key.  If %FALSE
 976  *   then call the destroy notify function on the new key.
 977  *
 978  * Implements the common logic for the g_hash_table_insert() and
 979  * g_hash_table_replace() functions.
 980  *
 981  * Do a lookup of @key.  If it is found, replace it with the new
 982  * @value (and perhaps the new @key).  If it is not found, create a
 983  * new node.
 984  */
 985 static void
 986 g_hash_table_insert_internal (GHashTable *hash_table,
 987                               gpointer    key,
 988                               gpointer    value,
 989                               gboolean    keep_new_key)
 990 {
 991   guint node_index;
 992   guint key_hash;
 993   guint old_hash;
 994   gpointer old_key;
 995   gpointer old_value;
 996
 997   g_return_if_fail (hash_table != NULL);
 998   g_return_if_fail (hash_table->ref_count > 0);
 999
1000   if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
1001     hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
1002
1003   node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
1004
1005   old_hash = hash_table->hashes[node_index];
1006   old_key = hash_table->keys[node_index];
1007   old_value = hash_table->values[node_index];
1008
1009   if (HASH_IS_REAL (old_hash))
1010     {
1011       if (keep_new_key)
1012         hash_table->keys[node_index] = key;
1013       hash_table->values[node_index] = value;
1014     }
1015   else
1016     {
1017       hash_table->keys[node_index] = key;
1018       hash_table->values[node_index] = value;
1019       hash_table->hashes[node_index] = key_hash;
1020
1021       hash_table->nnodes++;
1022
1023       if (HASH_IS_UNUSED (old_hash))
1024         {
1025           /* We replaced an empty node, and not a tombstone */
1026           hash_table->noccupied++;
1027           g_hash_table_maybe_resize (hash_table);
1028         }
1029
1030 #ifndef G_DISABLE_ASSERT
1031       hash_table->version++;
1032 #endif
1033     }
1034
1035   if (HASH_IS_REAL (old_hash))
1036     {
1037       if (hash_table->key_destroy_func)
1038         hash_table->key_destroy_func (keep_new_key ? old_key : key);
1039       if (hash_table->value_destroy_func)
1040         hash_table->value_destroy_func (old_value);
1041     }
1042 }
1043
1044 /**
1045  * g_hash_table_insert:
1046  * @hash_table: a #GHashTable.
1047  * @key: a key to insert.
1048  * @value: the value to associate with the key.
1049  *
1050  * Inserts a new key and value into a #GHashTable.
1051  *
1052  * If the key already exists in the #GHashTable its current value is replaced
1053  * with the new value. If you supplied a @value_destroy_func when creating the
1054  * #GHashTable, the old value is freed using that function. If you supplied
1055  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
1056  * using that function.
1057  **/
1058 void
1059 g_hash_table_insert (GHashTable *hash_table,
1060                      gpointer    key,
1061                      gpointer    value)
1062 {
1063   g_hash_table_insert_internal (hash_table, key, value, FALSE);
1064 }
1065
1066 /**
1067  * g_hash_table_replace:
1068  * @hash_table: a #GHashTable.
1069  * @key: a key to insert.
1070  * @value: the value to associate with the key.
1071  *
1072  * Inserts a new key and value into a #GHashTable similar to
1073  * g_hash_table_insert(). The difference is that if the key already exists
1074  * in the #GHashTable, it gets replaced by the new key. If you supplied a
1075  * @value_destroy_func when creating the #GHashTable, the old value is freed
1076  * using that function. If you supplied a @key_destroy_func when creating the
1077  * #GHashTable, the old key is freed using that function.
1078  **/
1079 void
1080 g_hash_table_replace (GHashTable *hash_table,
1081                       gpointer    key,
1082                       gpointer    value)
1083 {
1084   g_hash_table_insert_internal (hash_table, key, value, TRUE);
1085 }
1086
1087 /*
1088  * g_hash_table_remove_internal:
1089  * @hash_table: our #GHashTable
1090  * @key: the key to remove
1091  * @notify: %TRUE if the destroy notify handlers are to be called
1092  * Return value: %TRUE if a node was found and removed, else %FALSE
1093  *
1094  * Implements the common logic for the g_hash_table_remove() and
1095  * g_hash_table_steal() functions.
1096  *
1097  * Do a lookup of @key and remove it if it is found, calling the
1098  * destroy notify handlers only if @notify is %TRUE.
1099  */
1100 static gboolean
1101 g_hash_table_remove_internal (GHashTable    *hash_table,
1102                               gconstpointer  key,
1103                               gboolean       notify)
1104 {
1105   guint node_index;
1106   guint node_hash;
1107
1108   g_return_val_if_fail (hash_table != NULL, FALSE);
1109
1110   node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1111
1112   if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1113     return FALSE;
1114
1115   g_hash_table_remove_node (hash_table, node_index, notify);
1116   g_hash_table_maybe_resize (hash_table);
1117
1118 #ifndef G_DISABLE_ASSERT
1119   hash_table->version++;
1120 #endif
1121
1122   return TRUE;
1123 }
1124
1125 /**
1126  * g_hash_table_remove:
1127  * @hash_table: a #GHashTable.
1128  * @key: the key to remove.
1129  *
1130  * Removes a key and its associated value from a #GHashTable.
1131  *
1132  * If the #GHashTable was created using g_hash_table_new_full(), the
1133  * key and value are freed using the supplied destroy functions, otherwise
1134  * you have to make sure that any dynamically allocated values are freed
1135  * yourself.
1136  *
1137  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1138  **/
1139 gboolean
1140 g_hash_table_remove (GHashTable    *hash_table,
1141                      gconstpointer  key)
1142 {
1143   return g_hash_table_remove_internal (hash_table, key, TRUE);
1144 }
1145
1146 /**
1147  * g_hash_table_steal:
1148  * @hash_table: a #GHashTable.
1149  * @key: the key to remove.
1150  *
1151  * Removes a key and its associated value from a #GHashTable without
1152  * calling the key and value destroy functions.
1153  *
1154  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1155  **/
1156 gboolean
1157 g_hash_table_steal (GHashTable    *hash_table,
1158                     gconstpointer  key)
1159 {
1160   return g_hash_table_remove_internal (hash_table, key, FALSE);
1161 }
1162
1163 /**
1164  * g_hash_table_remove_all:
1165  * @hash_table: a #GHashTable
1166  *
1167  * Removes all keys and their associated values from a #GHashTable.
1168  *
1169  * If the #GHashTable was created using g_hash_table_new_full(), the keys
1170  * and values are freed using the supplied destroy functions, otherwise you
1171  * have to make sure that any dynamically allocated values are freed
1172  * yourself.
1173  *
1174  * Since: 2.12
1175  **/
1176 void
1177 g_hash_table_remove_all (GHashTable *hash_table)
1178 {
1179   g_return_if_fail (hash_table != NULL);
1180
1181 #ifndef G_DISABLE_ASSERT
1182   if (hash_table->nnodes != 0)
1183     hash_table->version++;
1184 #endif
1185
1186   g_hash_table_remove_all_nodes (hash_table, TRUE);
1187   g_hash_table_maybe_resize (hash_table);
1188 }
1189
1190 /**
1191  * g_hash_table_steal_all:
1192  * @hash_table: a #GHashTable.
1193  *
1194  * Removes all keys and their associated values from a #GHashTable
1195  * without calling the key and value destroy functions.
1196  *
1197  * Since: 2.12
1198  **/
1199 void
1200 g_hash_table_steal_all (GHashTable *hash_table)
1201 {
1202   g_return_if_fail (hash_table != NULL);
1203
1204 #ifndef G_DISABLE_ASSERT
1205   if (hash_table->nnodes != 0)
1206     hash_table->version++;
1207 #endif
1208
1209   g_hash_table_remove_all_nodes (hash_table, FALSE);
1210   g_hash_table_maybe_resize (hash_table);
1211 }
1212
1213 /*
1214  * g_hash_table_foreach_remove_or_steal:
1215  * @hash_table: our #GHashTable
1216  * @func: the user's callback function
1217  * @user_data: data for @func
1218  * @notify: %TRUE if the destroy notify handlers are to be called
1219  *
1220  * Implements the common logic for g_hash_table_foreach_remove() and
1221  * g_hash_table_foreach_steal().
1222  *
1223  * Iterates over every node in the table, calling @func with the key
1224  * and value of the node (and @user_data).  If @func returns %TRUE the
1225  * node is removed from the table.
1226  *
1227  * If @notify is true then the destroy notify handlers will be called
1228  * for each removed node.
1229  */
1230 static guint
1231 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1232                                       GHRFunc     func,
1233                                       gpointer    user_data,
1234                                       gboolean    notify)
1235 {
1236   guint deleted = 0;
1237   gint i;
1238 #ifndef G_DISABLE_ASSERT
1239   gint version = hash_table->version;
1240 #endif
1241
1242   for (i = 0; i < hash_table->size; i++)
1243     {
1244       guint node_hash = hash_table->hashes[i];
1245       gpointer node_key = hash_table->keys[i];
1246       gpointer node_value = hash_table->values[i];
1247
1248       if (HASH_IS_REAL (node_hash) &&
1249           (* func) (node_key, node_value, user_data))
1250         {
1251           g_hash_table_remove_node (hash_table, i, notify);
1252           deleted++;
1253         }
1254
1255 #ifndef G_DISABLE_ASSERT
1256       g_return_val_if_fail (version == hash_table->version, 0);
1257 #endif
1258     }
1259
1260   g_hash_table_maybe_resize (hash_table);
1261
1262 #ifndef G_DISABLE_ASSERT
1263   if (deleted > 0)
1264     hash_table->version++;
1265 #endif
1266
1267   return deleted;
1268 }
1269
1270 /**
1271  * g_hash_table_foreach_remove:
1272  * @hash_table: a #GHashTable.
1273  * @func: the function to call for each key/value pair.
1274  * @user_data: user data to pass to the function.
1275  *
1276  * Calls the given function for each key/value pair in the #GHashTable.
1277  * If the function returns %TRUE, then the key/value pair is removed from the
1278  * #GHashTable. If you supplied key or value destroy functions when creating
1279  * the #GHashTable, they are used to free the memory allocated for the removed
1280  * keys and values.
1281  *
1282  * See #GHashTableIter for an alternative way to loop over the
1283  * key/value pairs in the hash table.
1284  *
1285  * Return value: the number of key/value pairs removed.
1286  **/
1287 guint
1288 g_hash_table_foreach_remove (GHashTable *hash_table,
1289                              GHRFunc     func,
1290                              gpointer    user_data)
1291 {
1292   g_return_val_if_fail (hash_table != NULL, 0);
1293   g_return_val_if_fail (func != NULL, 0);
1294
1295   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1296 }
1297
1298 /**
1299  * g_hash_table_foreach_steal:
1300  * @hash_table: a #GHashTable.
1301  * @func: the function to call for each key/value pair.
1302  * @user_data: user data to pass to the function.
1303  *
1304  * Calls the given function for each key/value pair in the #GHashTable.
1305  * If the function returns %TRUE, then the key/value pair is removed from the
1306  * #GHashTable, but no key or value destroy functions are called.
1307  *
1308  * See #GHashTableIter for an alternative way to loop over the
1309  * key/value pairs in the hash table.
1310  *
1311  * Return value: the number of key/value pairs removed.
1312  **/
1313 guint
1314 g_hash_table_foreach_steal (GHashTable *hash_table,
1315                             GHRFunc     func,
1316                             gpointer    user_data)
1317 {
1318   g_return_val_if_fail (hash_table != NULL, 0);
1319   g_return_val_if_fail (func != NULL, 0);
1320
1321   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1322 }
1323
1324 /**
1325  * g_hash_table_foreach:
1326  * @hash_table: a #GHashTable.
1327  * @func: the function to call for each key/value pair.
1328  * @user_data: user data to pass to the function.
1329  *
1330  * Calls the given function for each of the key/value pairs in the
1331  * #GHashTable.  The function is passed the key and value of each
1332  * pair, and the given @user_data parameter.  The hash table may not
1333  * be modified while iterating over it (you can't add/remove
1334  * items). To remove all items matching a predicate, use
1335  * g_hash_table_foreach_remove().
1336  *
1337  * See g_hash_table_find() for performance caveats for linear
1338  * order searches in contrast to g_hash_table_lookup().
1339  **/
1340 void
1341 g_hash_table_foreach (GHashTable *hash_table,
1342                       GHFunc      func,
1343                       gpointer    user_data)
1344 {
1345   gint i;
1346 #ifndef G_DISABLE_ASSERT
1347   gint version = hash_table->version;
1348 #endif
1349
1350   g_return_if_fail (hash_table != NULL);
1351   g_return_if_fail (func != NULL);
1352
1353   for (i = 0; i < hash_table->size; i++)
1354     {
1355       guint node_hash = hash_table->hashes[i];
1356       gpointer node_key = hash_table->keys[i];
1357       gpointer node_value = hash_table->values[i];
1358
1359       if (HASH_IS_REAL (node_hash))
1360         (* func) (node_key, node_value, user_data);
1361
1362 #ifndef G_DISABLE_ASSERT
1363       g_return_if_fail (version == hash_table->version);
1364 #endif
1365     }
1366 }
1367
1368 /**
1369  * g_hash_table_find:
1370  * @hash_table: a #GHashTable.
1371  * @predicate:  function to test the key/value pairs for a certain property.
1372  * @user_data:  user data to pass to the function.
1373  *
1374  * Calls the given function for key/value pairs in the #GHashTable until
1375  * @predicate returns %TRUE.  The function is passed the key and value of
1376  * each pair, and the given @user_data parameter. The hash table may not
1377  * be modified while iterating over it (you can't add/remove items).
1378  *
1379  * Note, that hash tables are really only optimized for forward lookups,
1380  * i.e. g_hash_table_lookup().
1381  * So code that frequently issues g_hash_table_find() or
1382  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1383  * hash table) should probably be reworked to use additional or different
1384  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1385  * operation issued for all n values in a hash table ends up needing O(n*n)
1386  * operations).
1387  *
1388  * Return value: The value of the first key/value pair is returned,
1389  *     for which @predicate evaluates to %TRUE. If no pair with the
1390  *     requested property is found, %NULL is returned.
1391  *
1392  * Since: 2.4
1393  **/
1394 gpointer
1395 g_hash_table_find (GHashTable *hash_table,
1396                    GHRFunc     predicate,
1397                    gpointer    user_data)
1398 {
1399   gint i;
1400 #ifndef G_DISABLE_ASSERT
1401   gint version = hash_table->version;
1402 #endif
1403   gboolean match;
1404
1405   g_return_val_if_fail (hash_table != NULL, NULL);
1406   g_return_val_if_fail (predicate != NULL, NULL);
1407
1408   match = FALSE;
1409
1410   for (i = 0; i < hash_table->size; i++)
1411     {
1412       guint node_hash = hash_table->hashes[i];
1413       gpointer node_key = hash_table->keys[i];
1414       gpointer node_value = hash_table->values[i];
1415
1416       if (HASH_IS_REAL (node_hash))
1417         match = predicate (node_key, node_value, user_data);
1418
1419 #ifndef G_DISABLE_ASSERT
1420       g_return_val_if_fail (version == hash_table->version, NULL);
1421 #endif
1422
1423       if (match)
1424         return node_value;
1425     }
1426
1427   return NULL;
1428 }
1429
1430 /**
1431  * g_hash_table_size:
1432  * @hash_table: a #GHashTable.
1433  *
1434  * Returns the number of elements contained in the #GHashTable.
1435  *
1436  * Return value: the number of key/value pairs in the #GHashTable.
1437  **/
1438 guint
1439 g_hash_table_size (GHashTable *hash_table)
1440 {
1441   g_return_val_if_fail (hash_table != NULL, 0);
1442
1443   return hash_table->nnodes;
1444 }
1445
1446 /**
1447  * g_hash_table_get_keys:
1448  * @hash_table: a #GHashTable
1449  *
1450  * Retrieves every key inside @hash_table. The returned data is valid
1451  * until @hash_table is modified.
1452  *
1453  * Return value: a #GList containing all the keys inside the hash
1454  *   table. The content of the list is owned by the hash table and
1455  *   should not be modified or freed. Use g_list_free() when done
1456  *   using the list.
1457  *
1458  * Since: 2.14
1459  */
1460 GList *
1461 g_hash_table_get_keys (GHashTable *hash_table)
1462 {
1463   gint i;
1464   GList *retval;
1465
1466   g_return_val_if_fail (hash_table != NULL, NULL);
1467
1468   retval = NULL;
1469   for (i = 0; i < hash_table->size; i++)
1470     {
1471       if (HASH_IS_REAL (hash_table->hashes[i]))
1472         retval = g_list_prepend (retval, hash_table->keys[i]);
1473     }
1474
1475   return retval;
1476 }
1477
1478 /**
1479  * g_hash_table_get_values:
1480  * @hash_table: a #GHashTable
1481  *
1482  * Retrieves every value inside @hash_table. The returned data is
1483  * valid until @hash_table is modified.
1484  *
1485  * Return value: a #GList containing all the values inside the hash
1486  *   table. The content of the list is owned by the hash table and
1487  *   should not be modified or freed. Use g_list_free() when done
1488  *   using the list.
1489  *
1490  * Since: 2.14
1491  */
1492 GList *
1493 g_hash_table_get_values (GHashTable *hash_table)
1494 {
1495   gint i;
1496   GList *retval;
1497
1498   g_return_val_if_fail (hash_table != NULL, NULL);
1499
1500   retval = NULL;
1501   for (i = 0; i < hash_table->size; i++)
1502     {
1503       if (HASH_IS_REAL (hash_table->hashes[i]))
1504         retval = g_list_prepend (retval, hash_table->values[i]);
1505     }
1506
1507   return retval;
1508 }