glib/ghash.c

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