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 "glib.h"
  34 #include "galias.h"
  35
  36
  37 #define HASH_TABLE_MIN_SIZE 11
  38 #define HASH_TABLE_MAX_SIZE 13845163
  39
  40
  41 typedef struct _GHashNode      GHashNode;
  42
  43 struct _GHashNode
  44 {
  45   gpointer   key;
  46   gpointer   value;
  47   GHashNode *next;
  48   guint      key_hash;
  49 };
  50
  51 struct _GHashTable
  52 {
  53   gint             size;
  54   gint             nnodes;
  55   GHashNode      **nodes;
  56   GHashFunc        hash_func;
  57   GEqualFunc       key_equal_func;
  58   volatile gint    ref_count;
  59   GDestroyNotify   key_destroy_func;
  60   GDestroyNotify   value_destroy_func;
  61 };
  62
  63 static void             g_hash_table_resize       (GHashTable     *hash_table);
  64 static GHashNode**      g_hash_table_lookup_node  (GHashTable     *hash_table,
  65                                                    gconstpointer   key,
  66                                                    guint          *hash_return);
  67 static GHashNode*       g_hash_node_new           (gpointer        key,
  68                                                    gpointer        value,
  69                                                    guint           key_hash);
  70 static guint g_hash_table_foreach_remove_or_steal (GHashTable     *hash_table,
  71                                                    GHRFunc         func,
  72                                                    gpointer        user_data,
  73                                                    gboolean        notify);
  74 static void         g_hash_table_remove_all_nodes (GHashTable *hash_table,
  75                                                    gboolean        notify);
  76
  77 static inline void
  78 g_hash_table_maybe_resize (GHashTable *hash_table)
  79 {
  80   gint nnodes = hash_table->nnodes;
  81   gint size = hash_table->size;
  82
  83   if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) ||
  84       (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE))
  85     g_hash_table_resize (hash_table);
  86 }
  87
  88 /**
  89  * g_hash_table_new:
  90  * @hash_func: a function to create a hash value from a key.
  91  *   Hash values are used to determine where keys are stored within the
  92  *   #GHashTable data structure. The g_direct_hash(), g_int_hash() and
  93  *   g_str_hash() functions are provided for some common types of keys.
  94  *   If hash_func is %NULL, g_direct_hash() is used.
  95  * @key_equal_func: a function to check two keys for equality.  This is
  96  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
  97  *   g_int_equal() and g_str_equal() functions are provided for the most
  98  *   common types of keys. If @key_equal_func is %NULL, keys are compared
  99  *   directly in a similar fashion to g_direct_equal(), but without the
 100  *   overhead of a function call.
 101  *
 102  * Creates a new #GHashTable with a reference count of 1.
 103  *
 104  * Return value: a new #GHashTable.
 105  **/
 106 GHashTable*
 107 g_hash_table_new (GHashFunc    hash_func,
 108                   GEqualFunc   key_equal_func)
 109 {
 110   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 111 }
 112
 113
 114 /**
 115  * g_hash_table_new_full:
 116  * @hash_func: a function to create a hash value from a key.
 117  * @key_equal_func: a function to check two keys for equality.
 118  * @key_destroy_func: a function to free the memory allocated for the key
 119  *   used when removing the entry from the #GHashTable or %NULL if you
 120  *   don't want to supply such a function.
 121  * @value_destroy_func: a function to free the memory allocated for the
 122  *   value used when removing the entry from the #GHashTable or %NULL if
 123  *   you don't want to supply such a function.
 124  *
 125  * Creates a new #GHashTable like g_hash_table_new() with a reference count
 126  * of 1 and allows to specify functions to free the memory allocated for the
 127  * key and value that get called when removing the entry from the #GHashTable.
 128  *
 129  * Return value: a new #GHashTable.
 130  **/
 131 GHashTable*
 132 g_hash_table_new_full (GHashFunc       hash_func,
 133                        GEqualFunc      key_equal_func,
 134                        GDestroyNotify  key_destroy_func,
 135                        GDestroyNotify  value_destroy_func)
 136 {
 137   GHashTable *hash_table;
 138
 139   hash_table = g_slice_new (GHashTable);
 140   hash_table->size               = HASH_TABLE_MIN_SIZE;
 141   hash_table->nnodes             = 0;
 142   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
 143   hash_table->key_equal_func     = key_equal_func;
 144   hash_table->ref_count          = 1;
 145   hash_table->key_destroy_func   = key_destroy_func;
 146   hash_table->value_destroy_func = value_destroy_func;
 147   hash_table->nodes              = g_new0 (GHashNode*, hash_table->size);
 148
 149   return hash_table;
 150 }
 151
 152
 153 /**
 154  * g_hash_table_ref:
 155  * @hash_table: a valid #GHashTable.
 156  *
 157  * Atomically increments the reference count of @hash_table by one.
 158  * This function is MT-safe and may be called from any thread.
 159  *
 160  * Return value: the passed in #GHashTable.
 161  *
 162  * Since: 2.10
 163  **/
 164 GHashTable*
 165 g_hash_table_ref (GHashTable *hash_table)
 166 {
 167   g_return_val_if_fail (hash_table != NULL, NULL);
 168   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 169
 170   g_atomic_int_add (&hash_table->ref_count, 1);
 171   return hash_table;
 172 }
 173
 174 /**
 175  * g_hash_table_unref:
 176  * @hash_table: a valid #GHashTable.
 177  *
 178  * Atomically decrements the reference count of @hash_table by one.
 179  * If the reference count drops to 0, all keys and values will be
 180  * destroyed, and all memory allocated by the hash table is released.
 181  * This function is MT-safe and may be called from any thread.
 182  *
 183  * Since: 2.10
 184  **/
 185 void
 186 g_hash_table_unref (GHashTable *hash_table)
 187 {
 188   g_return_if_fail (hash_table != NULL);
 189   g_return_if_fail (hash_table->ref_count > 0);
 190
 191   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 192     {
 193       g_hash_table_remove_all_nodes (hash_table, FALSE);
 194       g_free (hash_table->nodes);
 195       g_slice_free (GHashTable, hash_table);
 196     }
 197 }
 198
 199 /**
 200  * g_hash_table_destroy:
 201  * @hash_table: a #GHashTable.
 202  *
 203  * Destroys all keys and values in the #GHashTable and decrements its
 204  * reference count by 1. If keys and/or values are dynamically allocated,
 205  * you should either free them first or create the #GHashTable with destroy
 206  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 207  * functions you supplied will be called on all keys and values during the
 208  * destruction phase.
 209  **/
 210 void
 211 g_hash_table_destroy (GHashTable *hash_table)
 212 {
 213   g_return_if_fail (hash_table != NULL);
 214   g_return_if_fail (hash_table->ref_count > 0);
 215
 216   g_hash_table_remove_all (hash_table);
 217   g_hash_table_unref (hash_table);
 218 }
 219
 220 static inline GHashNode**
 221 g_hash_table_lookup_node (GHashTable    *hash_table,
 222                           gconstpointer  key,
 223                           guint         *hash_return)
 224 {
 225   GHashNode **node_ptr;
 226   guint hash_value;
 227
 228   hash_value = (* hash_table->hash_func) (key);
 229   node_ptr = &hash_table->nodes[hash_value % hash_table->size];
 230
 231   if (hash_return)
 232     *hash_return = hash_value;
 233
 234   /* Hash table lookup needs to be fast.
 235    *  We therefore remove the extra conditional of testing
 236    *  whether to call the key_equal_func or not from
 237    *  the inner loop.
 238    *
 239    *  Additional optimisation: first check if our full hash
 240    *  values are equal so we can avoid calling the full-blown
 241    *  key equality function in most cases.
 242    */
 243   if (hash_table->key_equal_func)
 244     while (*node_ptr && (((*node_ptr)->key_hash != hash_value) ||
 245                      !(*hash_table->key_equal_func) ((*node_ptr)->key, key)))
 246       node_ptr = &(*node_ptr)->next;
 247   else
 248     while (*node_ptr && (*node_ptr)->key != key)
 249       node_ptr = &(*node_ptr)->next;
 250
 251   return node_ptr;
 252 }
 253
 254 /**
 255  * g_hash_table_lookup:
 256  * @hash_table: a #GHashTable.
 257  * @key: the key to look up.
 258  *
 259  * Looks up a key in a #GHashTable. Note that this function cannot
 260  * distinguish between a key that is not present and one which is present
 261  * and has the value %NULL. If you need this distinction, use
 262  * g_hash_table_lookup_extended().
 263  *
 264  * Return value: the associated value, or %NULL if the key is not found.
 265  **/
 266 gpointer
 267 g_hash_table_lookup (GHashTable   *hash_table,
 268                      gconstpointer key)
 269 {
 270   GHashNode *node;
 271
 272   g_return_val_if_fail (hash_table != NULL, NULL);
 273
 274   node = *g_hash_table_lookup_node (hash_table, key, NULL);
 275
 276   return node ? node->value : NULL;
 277 }
 278
 279 /**
 280  * g_hash_table_lookup_extended:
 281  * @hash_table: a #GHashTable.
 282  * @lookup_key: the key to look up.
 283  * @orig_key: returns the original key.
 284  * @value: returns the value associated with the key.
 285  *
 286  * Looks up a key in the #GHashTable, returning the original key and the
 287  * associated value and a #gboolean which is %TRUE if the key was found. This
 288  * is useful if you need to free the memory allocated for the original key,
 289  * for example before calling g_hash_table_remove().
 290  *
 291  * Return value: %TRUE if the key was found in the #GHashTable.
 292  **/
 293 gboolean
 294 g_hash_table_lookup_extended (GHashTable    *hash_table,
 295                               gconstpointer  lookup_key,
 296                               gpointer      *orig_key,
 297                               gpointer      *value)
 298 {
 299   GHashNode *node;
 300
 301   g_return_val_if_fail (hash_table != NULL, FALSE);
 302
 303   node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL);
 304
 305   if (node)
 306     {
 307       if (orig_key)
 308         *orig_key = node->key;
 309       if (value)
 310         *value = node->value;
 311       return TRUE;
 312     }
 313   else
 314     return FALSE;
 315 }
 316
 317 static void
 318 g_hash_table_insert_internal (GHashTable *hash_table,
 319                               gpointer    key,
 320                               gpointer    value,
 321                               gboolean    keep_new_key)
 322 {
 323   GHashNode **node_ptr;
 324   guint key_hash;
 325
 326   g_return_if_fail (hash_table != NULL);
 327   g_return_if_fail (hash_table->ref_count > 0);
 328
 329   node_ptr = g_hash_table_lookup_node (hash_table, key, &key_hash);
 330
 331   if (*node_ptr)
 332     {
 333       if (keep_new_key)
 334         {
 335           if (hash_table->key_destroy_func)
 336             hash_table->key_destroy_func ((*node_ptr)->key);
 337           (*node_ptr)->key = key;
 338         }
 339       else
 340         {
 341           if (hash_table->key_destroy_func)
 342             hash_table->key_destroy_func (key);
 343         }
 344
 345       if (hash_table->value_destroy_func)
 346         hash_table->value_destroy_func ((*node_ptr)->value);
 347
 348       (*node_ptr)->value = value;
 349     }
 350   else
 351     {
 352       *node_ptr = g_hash_node_new (key, value, key_hash);
 353       hash_table->nnodes++;
 354       g_hash_table_maybe_resize (hash_table);
 355     }
 356 }
 357
 358 /**
 359  * g_hash_table_insert:
 360  * @hash_table: a #GHashTable.
 361  * @key: a key to insert.
 362  * @value: the value to associate with the key.
 363  *
 364  * Inserts a new key and value into a #GHashTable.
 365  *
 366  * If the key already exists in the #GHashTable its current value is replaced
 367  * with the new value. If you supplied a @value_destroy_func when creating the
 368  * #GHashTable, the old value is freed using that function. If you supplied
 369  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 370  * using that function.
 371  **/
 372 void
 373 g_hash_table_insert (GHashTable *hash_table,
 374                      gpointer    key,
 375                      gpointer    value)
 376 {
 377   return g_hash_table_insert_internal (hash_table, key, value, FALSE);
 378 }
 379
 380 /**
 381  * g_hash_table_replace:
 382  * @hash_table: a #GHashTable.
 383  * @key: a key to insert.
 384  * @value: the value to associate with the key.
 385  *
 386  * Inserts a new key and value into a #GHashTable similar to
 387  * g_hash_table_insert(). The difference is that if the key already exists
 388  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 389  * @value_destroy_func when creating the #GHashTable, the old value is freed
 390  * using that function. If you supplied a @key_destroy_func when creating the
 391  * #GHashTable, the old key is freed using that function.
 392  **/
 393 void
 394 g_hash_table_replace (GHashTable *hash_table,
 395                       gpointer    key,
 396                       gpointer    value)
 397 {
 398   return g_hash_table_insert_internal (hash_table, key, value, TRUE);
 399 }
 400
 401 static void
 402 g_hash_table_remove_node (GHashTable   *hash_table,
 403                           GHashNode  ***node_ptr_ptr,
 404                           gboolean      notify)
 405 {
 406   GHashNode **node_ptr, *node;
 407
 408   node_ptr = *node_ptr_ptr;
 409   node = *node_ptr;
 410
 411   *node_ptr = node->next;
 412
 413   if (notify && hash_table->key_destroy_func)
 414     hash_table->key_destroy_func (node->key);
 415
 416   if (notify && hash_table->value_destroy_func)
 417     hash_table->value_destroy_func (node->value);
 418
 419   g_slice_free (GHashNode, node);
 420
 421   hash_table->nnodes--;
 422 }
 423
 424 static void
 425 g_hash_table_remove_all_nodes (GHashTable *hash_table,
 426                                gboolean    notify)
 427 {
 428   GHashNode **node_ptr;
 429   int i;
 430
 431   for (i = 0; i < hash_table->size; i++)
 432     for (node_ptr = &hash_table->nodes[i]; *node_ptr != NULL;)
 433       g_hash_table_remove_node (hash_table, &node_ptr, notify);
 434
 435   hash_table->nnodes = 0;
 436 }
 437
 438 static gboolean
 439 g_hash_table_remove_internal (GHashTable    *hash_table,
 440                               gconstpointer  key,
 441                               gboolean       notify)
 442 {
 443   GHashNode **node_ptr;
 444
 445   g_return_val_if_fail (hash_table != NULL, FALSE);
 446
 447   node_ptr = g_hash_table_lookup_node (hash_table, key, NULL);
 448   if (*node_ptr == NULL)
 449     return FALSE;
 450
 451   g_hash_table_remove_node (hash_table, &node_ptr, notify);
 452   g_hash_table_maybe_resize (hash_table);
 453
 454   return TRUE;
 455 }
 456
 457 /**
 458  * g_hash_table_remove:
 459  * @hash_table: a #GHashTable.
 460  * @key: the key to remove.
 461  *
 462  * Removes a key and its associated value from a #GHashTable.
 463  *
 464  * If the #GHashTable was created using g_hash_table_new_full(), the
 465  * key and value are freed using the supplied destroy functions, otherwise
 466  * you have to make sure that any dynamically allocated values are freed
 467  * yourself.
 468  *
 469  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 470  **/
 471 gboolean
 472 g_hash_table_remove (GHashTable    *hash_table,
 473                      gconstpointer  key)
 474 {
 475   return g_hash_table_remove_internal (hash_table, key, TRUE);
 476 }
 477
 478 /**
 479  * g_hash_table_remove_all:
 480  * @hash_table: a #GHashTable
 481  *
 482  * Removes all keys and their associated values from a #GHashTable.
 483  *
 484  * If the #GHashTable was created using g_hash_table_new_full(), the keys
 485  * and values are freed using the supplied destroy functions, otherwise you
 486  * have to make sure that any dynamically allocated values are freed
 487  * yourself.
 488  *
 489  * Since: 2.12
 490  **/
 491 void
 492 g_hash_table_remove_all (GHashTable *hash_table)
 493 {
 494   g_return_if_fail (hash_table != NULL);
 495
 496   g_hash_table_remove_all_nodes (hash_table, TRUE);
 497   g_hash_table_maybe_resize (hash_table);
 498 }
 499
 500 /**
 501  * g_hash_table_steal:
 502  * @hash_table: a #GHashTable.
 503  * @key: the key to remove.
 504  *
 505  * Removes a key and its associated value from a #GHashTable without
 506  * calling the key and value destroy functions.
 507  *
 508  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 509  **/
 510 gboolean
 511 g_hash_table_steal (GHashTable    *hash_table,
 512                     gconstpointer  key)
 513 {
 514   return g_hash_table_remove_internal (hash_table, key, FALSE);
 515 }
 516
 517 /**
 518  * g_hash_table_steal_all:
 519  * @hash_table: a #GHashTable.
 520  *
 521  * Removes all keys and their associated values from a #GHashTable
 522  * without calling the key and value destroy functions.
 523  *
 524  * Since: 2.12
 525  **/
 526 void
 527 g_hash_table_steal_all (GHashTable *hash_table)
 528 {
 529   g_return_if_fail (hash_table != NULL);
 530
 531   g_hash_table_remove_all_nodes (hash_table, FALSE);
 532   g_hash_table_maybe_resize (hash_table);
 533 }
 534
 535 /**
 536  * g_hash_table_foreach_remove:
 537  * @hash_table: a #GHashTable.
 538  * @func: the function to call for each key/value pair.
 539  * @user_data: user data to pass to the function.
 540  *
 541  * Calls the given function for each key/value pair in the #GHashTable.
 542  * If the function returns %TRUE, then the key/value pair is removed from the
 543  * #GHashTable. If you supplied key or value destroy functions when creating
 544  * the #GHashTable, they are used to free the memory allocated for the removed
 545  * keys and values.
 546  *
 547  * Return value: the number of key/value pairs removed.
 548  **/
 549 guint
 550 g_hash_table_foreach_remove (GHashTable *hash_table,
 551                              GHRFunc     func,
 552                              gpointer    user_data)
 553 {
 554   g_return_val_if_fail (hash_table != NULL, 0);
 555   g_return_val_if_fail (func != NULL, 0);
 556
 557   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
 558 }
 559
 560 /**
 561  * g_hash_table_foreach_steal:
 562  * @hash_table: a #GHashTable.
 563  * @func: the function to call for each key/value pair.
 564  * @user_data: user data to pass to the function.
 565  *
 566  * Calls the given function for each key/value pair in the #GHashTable.
 567  * If the function returns %TRUE, then the key/value pair is removed from the
 568  * #GHashTable, but no key or value destroy functions are called.
 569  *
 570  * Return value: the number of key/value pairs removed.
 571  **/
 572 guint
 573 g_hash_table_foreach_steal (GHashTable *hash_table,
 574                             GHRFunc     func,
 575                             gpointer    user_data)
 576 {
 577   g_return_val_if_fail (hash_table != NULL, 0);
 578   g_return_val_if_fail (func != NULL, 0);
 579
 580   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
 581 }
 582
 583 static guint
 584 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 585                                       GHRFunc     func,
 586                                       gpointer    user_data,
 587                                       gboolean    notify)
 588 {
 589   GHashNode *node, **node_ptr;
 590   guint deleted = 0;
 591   gint i;
 592
 593   for (i = 0; i < hash_table->size; i++)
 594     for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;)
 595       if ((* func) (node->key, node->value, user_data))
 596         {
 597           g_hash_table_remove_node (hash_table, &node_ptr, notify);
 598           deleted++;
 599         }
 600       else
 601         node_ptr = &node->next;
 602
 603   g_hash_table_maybe_resize (hash_table);
 604
 605   return deleted;
 606 }
 607
 608 /**
 609  * g_hash_table_foreach:
 610  * @hash_table: a #GHashTable.
 611  * @func: the function to call for each key/value pair.
 612  * @user_data: user data to pass to the function.
 613  *
 614  * Calls the given function for each of the key/value pairs in the
 615  * #GHashTable.  The function is passed the key and value of each
 616  * pair, and the given @user_data parameter.  The hash table may not
 617  * be modified while iterating over it (you can't add/remove
 618  * items). To remove all items matching a predicate, use
 619  * g_hash_table_foreach_remove().
 620  *
 621  * See g_hash_table_find() for performance caveats for linear
 622  * order searches in contrast to g_hash_table_lookup().
 623  **/
 624 void
 625 g_hash_table_foreach (GHashTable *hash_table,
 626                       GHFunc      func,
 627                       gpointer    user_data)
 628 {
 629   GHashNode *node;
 630   gint i;
 631
 632   g_return_if_fail (hash_table != NULL);
 633   g_return_if_fail (func != NULL);
 634
 635   for (i = 0; i < hash_table->size; i++)
 636     for (node = hash_table->nodes[i]; node; node = node->next)
 637       (* func) (node->key, node->value, user_data);
 638 }
 639
 640 /**
 641  * g_hash_table_find:
 642  * @hash_table: a #GHashTable.
 643  * @predicate:  function to test the key/value pairs for a certain property.
 644  * @user_data:  user data to pass to the function.
 645  *
 646  * Calls the given function for key/value pairs in the #GHashTable until
 647  * @predicate returns %TRUE.  The function is passed the key and value of
 648  * each pair, and the given @user_data parameter. The hash table may not
 649  * be modified while iterating over it (you can't add/remove items).
 650  *
 651  * Note, that hash tables are really only optimized for forward lookups,
 652  * i.e. g_hash_table_lookup().
 653  * So code that frequently issues g_hash_table_find() or
 654  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
 655  * hash table) should probably be reworked to use additional or different
 656  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
 657  * operation issued for all n values in a hash table ends up needing O(n*n)
 658  * operations).
 659  *
 660  * Return value: The value of the first key/value pair is returned, for which
 661  * func evaluates to %TRUE. If no pair with the requested property is found,
 662  * %NULL is returned.
 663  *
 664  * Since: 2.4
 665  **/
 666 gpointer
 667 g_hash_table_find (GHashTable      *hash_table,
 668                    GHRFunc          predicate,
 669                    gpointer         user_data)
 670 {
 671   GHashNode *node;
 672   gint i;
 673
 674   g_return_val_if_fail (hash_table != NULL, NULL);
 675   g_return_val_if_fail (predicate != NULL, NULL);
 676
 677   for (i = 0; i < hash_table->size; i++)
 678     for (node = hash_table->nodes[i]; node; node = node->next)
 679       if (predicate (node->key, node->value, user_data))
 680         return node->value;
 681   return NULL;
 682 }
 683
 684 /**
 685  * g_hash_table_size:
 686  * @hash_table: a #GHashTable.
 687  *
 688  * Returns the number of elements contained in the #GHashTable.
 689  *
 690  * Return value: the number of key/value pairs in the #GHashTable.
 691  **/
 692 guint
 693 g_hash_table_size (GHashTable *hash_table)
 694 {
 695   g_return_val_if_fail (hash_table != NULL, 0);
 696
 697   return hash_table->nnodes;
 698 }
 699
 700 /**
 701  * g_hash_table_get_keys:
 702  * @hash_table: a #GHashTable
 703  *
 704  * Retrieves every key inside @hash_table. The returned data is valid
 705  * until @hash_table is modified.
 706  *
 707  * Return value: a #GList containing all the keys inside the hash
 708  *   table. The content of the list is owned by the hash table and
 709  *   should not be modified or freed. Use g_list_free() when done
 710  *   using the list.
 711  *
 712  * Since: 2.14
 713  */
 714 GList *
 715 g_hash_table_get_keys (GHashTable *hash_table)
 716 {
 717   GHashNode *node;
 718   gint i;
 719   GList *retval;
 720
 721   g_return_val_if_fail (hash_table != NULL, NULL);
 722
 723   retval = NULL;
 724   for (i = 0; i < hash_table->size; i++)
 725     for (node = hash_table->nodes[i]; node; node = node->next)
 726       retval = g_list_prepend (retval, node->key);
 727
 728   return retval;
 729 }
 730
 731 /**
 732  * g_hash_table_get_values:
 733  * @hash_table: a #GHashTable
 734  *
 735  * Retrieves every value inside @hash_table. The returned data is
 736  * valid until @hash_table is modified.
 737  *
 738  * Return value: a #GList containing all the values inside the hash
 739  *   table. The content of the list is owned by the hash table and
 740  *   should not be modified or freed. Use g_list_free() when done
 741  *   using the list.
 742  *
 743  * Since: 2.14
 744  */
 745 GList *
 746 g_hash_table_get_values (GHashTable *hash_table)
 747 {
 748   GHashNode *node;
 749   gint i;
 750   GList *retval;
 751
 752   g_return_val_if_fail (hash_table != NULL, NULL);
 753
 754   retval = NULL;
 755   for (i = 0; i < hash_table->size; i++)
 756     for (node = hash_table->nodes[i]; node; node = node->next)
 757       retval = g_list_prepend (retval, node->value);
 758
 759   return retval;
 760 }
 761
 762 static void
 763 g_hash_table_resize (GHashTable *hash_table)
 764 {
 765   GHashNode **new_nodes;
 766   GHashNode *node;
 767   GHashNode *next;
 768   guint hash_val;
 769   gint new_size;
 770   gint i;
 771
 772   new_size = g_spaced_primes_closest (hash_table->nnodes);
 773   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 774
 775   new_nodes = g_new0 (GHashNode*, new_size);
 776
 777   for (i = 0; i < hash_table->size; i++)
 778     for (node = hash_table->nodes[i]; node; node = next)
 779       {
 780         next = node->next;
 781
 782         hash_val = node->key_hash % new_size;
 783
 784         node->next = new_nodes[hash_val];
 785         new_nodes[hash_val] = node;
 786       }
 787
 788   g_free (hash_table->nodes);
 789   hash_table->nodes = new_nodes;
 790   hash_table->size = new_size;
 791 }
 792
 793 static GHashNode*
 794 g_hash_node_new (gpointer key,
 795                  gpointer value,
 796                  guint key_hash)
 797 {
 798   GHashNode *hash_node = g_slice_new (GHashNode);
 799
 800   hash_node->key = key;
 801   hash_node->value = value;
 802   hash_node->key_hash = key_hash;
 803   hash_node->next = NULL;
 804
 805   return hash_node;
 806 }
 807
 808 #define __G_HASH_C__
 809 #include "galiasdef.c"