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