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