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, *node;
 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     {
 245       while ((node = *node_ptr))
 246         {
 247           if (node->key_hash == hash_value &&
 248               hash_table->key_equal_func (node->key, key))
 249             break;
 250
 251           node_ptr = &(*node_ptr)->next;
 252         }
 253     }
 254   else
 255     {
 256       while ((node = *node_ptr))
 257         {
 258           if (node->key == key)
 259             break;
 260
 261           node_ptr = &(*node_ptr)->next;
 262         }
 263     }
 264
 265   return node_ptr;
 266 }
 267
 268 /**
 269  * g_hash_table_lookup:
 270  * @hash_table: a #GHashTable.
 271  * @key: the key to look up.
 272  *
 273  * Looks up a key in a #GHashTable. Note that this function cannot
 274  * distinguish between a key that is not present and one which is present
 275  * and has the value %NULL. If you need this distinction, use
 276  * g_hash_table_lookup_extended().
 277  *
 278  * Return value: the associated value, or %NULL if the key is not found.
 279  **/
 280 gpointer
 281 g_hash_table_lookup (GHashTable   *hash_table,
 282                      gconstpointer key)
 283 {
 284   GHashNode *node;
 285
 286   g_return_val_if_fail (hash_table != NULL, NULL);
 287
 288   node = *g_hash_table_lookup_node (hash_table, key, NULL);
 289
 290   return node ? node->value : NULL;
 291 }
 292
 293 /**
 294  * g_hash_table_lookup_extended:
 295  * @hash_table: a #GHashTable.
 296  * @lookup_key: the key to look up.
 297  * @orig_key: returns the original key.
 298  * @value: returns the value associated with the key.
 299  *
 300  * Looks up a key in the #GHashTable, returning the original key and the
 301  * associated value and a #gboolean which is %TRUE if the key was found. This
 302  * is useful if you need to free the memory allocated for the original key,
 303  * for example before calling g_hash_table_remove().
 304  *
 305  * Return value: %TRUE if the key was found in the #GHashTable.
 306  **/
 307 gboolean
 308 g_hash_table_lookup_extended (GHashTable    *hash_table,
 309                               gconstpointer  lookup_key,
 310                               gpointer      *orig_key,
 311                               gpointer      *value)
 312 {
 313   GHashNode *node;
 314
 315   g_return_val_if_fail (hash_table != NULL, FALSE);
 316
 317   node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL);
 318
 319   if (node == NULL)
 320     return FALSE;
 321
 322   if (orig_key)
 323     *orig_key = node->key;
 324
 325   if (value)
 326     *value = node->value;
 327
 328   return TRUE;
 329 }
 330
 331 static void
 332 g_hash_table_insert_internal (GHashTable *hash_table,
 333                               gpointer    key,
 334                               gpointer    value,
 335                               gboolean    keep_new_key)
 336 {
 337   GHashNode **node_ptr, *node;
 338   guint key_hash;
 339
 340   g_return_if_fail (hash_table != NULL);
 341   g_return_if_fail (hash_table->ref_count > 0);
 342
 343   node_ptr = g_hash_table_lookup_node (hash_table, key, &key_hash);
 344
 345   if ((node = *node_ptr))
 346     {
 347       if (keep_new_key)
 348         {
 349           if (hash_table->key_destroy_func)
 350             hash_table->key_destroy_func (node->key);
 351           node->key = key;
 352         }
 353       else
 354         {
 355           if (hash_table->key_destroy_func)
 356             hash_table->key_destroy_func (key);
 357         }
 358
 359       if (hash_table->value_destroy_func)
 360         hash_table->value_destroy_func (node->value);
 361
 362       node->value = value;
 363     }
 364   else
 365     {
 366       node = g_slice_new (GHashNode);
 367
 368       node->key = key;
 369       node->value = value;
 370       node->key_hash = key_hash;
 371       node->next = NULL;
 372
 373       *node_ptr = node;
 374       hash_table->nnodes++;
 375       g_hash_table_maybe_resize (hash_table);
 376     }
 377 }
 378
 379 /**
 380  * g_hash_table_insert:
 381  * @hash_table: a #GHashTable.
 382  * @key: a key to insert.
 383  * @value: the value to associate with the key.
 384  *
 385  * Inserts a new key and value into a #GHashTable.
 386  *
 387  * If the key already exists in the #GHashTable its current value is replaced
 388  * with the new value. If you supplied a @value_destroy_func when creating the
 389  * #GHashTable, the old value is freed using that function. If you supplied
 390  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 391  * using that function.
 392  **/
 393 void
 394 g_hash_table_insert (GHashTable *hash_table,
 395                      gpointer    key,
 396                      gpointer    value)
 397 {
 398   return g_hash_table_insert_internal (hash_table, key, value, FALSE);
 399 }
 400
 401 /**
 402  * g_hash_table_replace:
 403  * @hash_table: a #GHashTable.
 404  * @key: a key to insert.
 405  * @value: the value to associate with the key.
 406  *
 407  * Inserts a new key and value into a #GHashTable similar to
 408  * g_hash_table_insert(). The difference is that if the key already exists
 409  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 410  * @value_destroy_func when creating the #GHashTable, the old value is freed
 411  * using that function. If you supplied a @key_destroy_func when creating the
 412  * #GHashTable, the old key is freed using that function.
 413  **/
 414 void
 415 g_hash_table_replace (GHashTable *hash_table,
 416                       gpointer    key,
 417                       gpointer    value)
 418 {
 419   return g_hash_table_insert_internal (hash_table, key, value, TRUE);
 420 }
 421
 422 static void
 423 g_hash_table_remove_node (GHashTable   *hash_table,
 424                           GHashNode  ***node_ptr_ptr,
 425                           gboolean      notify)
 426 {
 427   GHashNode **node_ptr, *node;
 428
 429   node_ptr = *node_ptr_ptr;
 430   node = *node_ptr;
 431
 432   *node_ptr = node->next;
 433
 434   if (notify && hash_table->key_destroy_func)
 435     hash_table->key_destroy_func (node->key);
 436
 437   if (notify && hash_table->value_destroy_func)
 438     hash_table->value_destroy_func (node->value);
 439
 440   g_slice_free (GHashNode, node);
 441
 442   hash_table->nnodes--;
 443 }
 444
 445 static void
 446 g_hash_table_remove_all_nodes (GHashTable *hash_table,
 447                                gboolean    notify)
 448 {
 449   GHashNode **node_ptr;
 450   int i;
 451
 452   for (i = 0; i < hash_table->size; i++)
 453     for (node_ptr = &hash_table->nodes[i]; *node_ptr != NULL;)
 454       g_hash_table_remove_node (hash_table, &node_ptr, notify);
 455
 456   hash_table->nnodes = 0;
 457 }
 458
 459 static gboolean
 460 g_hash_table_remove_internal (GHashTable    *hash_table,
 461                               gconstpointer  key,
 462                               gboolean       notify)
 463 {
 464   GHashNode **node_ptr;
 465
 466   g_return_val_if_fail (hash_table != NULL, FALSE);
 467
 468   node_ptr = g_hash_table_lookup_node (hash_table, key, NULL);
 469   if (*node_ptr == NULL)
 470     return FALSE;
 471
 472   g_hash_table_remove_node (hash_table, &node_ptr, notify);
 473   g_hash_table_maybe_resize (hash_table);
 474
 475   return TRUE;
 476 }
 477
 478 /**
 479  * g_hash_table_remove:
 480  * @hash_table: a #GHashTable.
 481  * @key: the key to remove.
 482  *
 483  * Removes a key and its associated value from a #GHashTable.
 484  *
 485  * If the #GHashTable was created using g_hash_table_new_full(), the
 486  * key and value are freed using the supplied destroy functions, otherwise
 487  * you have to make sure that any dynamically allocated values are freed
 488  * yourself.
 489  *
 490  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 491  **/
 492 gboolean
 493 g_hash_table_remove (GHashTable    *hash_table,
 494                      gconstpointer  key)
 495 {
 496   return g_hash_table_remove_internal (hash_table, key, TRUE);
 497 }
 498
 499 /**
 500  * g_hash_table_remove_all:
 501  * @hash_table: a #GHashTable
 502  *
 503  * Removes all keys and their associated values from a #GHashTable.
 504  *
 505  * If the #GHashTable was created using g_hash_table_new_full(), the keys
 506  * and values are freed using the supplied destroy functions, otherwise you
 507  * have to make sure that any dynamically allocated values are freed
 508  * yourself.
 509  *
 510  * Since: 2.12
 511  **/
 512 void
 513 g_hash_table_remove_all (GHashTable *hash_table)
 514 {
 515   g_return_if_fail (hash_table != NULL);
 516
 517   g_hash_table_remove_all_nodes (hash_table, TRUE);
 518   g_hash_table_maybe_resize (hash_table);
 519 }
 520
 521 /**
 522  * g_hash_table_steal:
 523  * @hash_table: a #GHashTable.
 524  * @key: the key to remove.
 525  *
 526  * Removes a key and its associated value from a #GHashTable without
 527  * calling the key and value destroy functions.
 528  *
 529  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 530  **/
 531 gboolean
 532 g_hash_table_steal (GHashTable    *hash_table,
 533                     gconstpointer  key)
 534 {
 535   return g_hash_table_remove_internal (hash_table, key, FALSE);
 536 }
 537
 538 /**
 539  * g_hash_table_steal_all:
 540  * @hash_table: a #GHashTable.
 541  *
 542  * Removes all keys and their associated values from a #GHashTable
 543  * without calling the key and value destroy functions.
 544  *
 545  * Since: 2.12
 546  **/
 547 void
 548 g_hash_table_steal_all (GHashTable *hash_table)
 549 {
 550   g_return_if_fail (hash_table != NULL);
 551
 552   g_hash_table_remove_all_nodes (hash_table, FALSE);
 553   g_hash_table_maybe_resize (hash_table);
 554 }
 555
 556 /**
 557  * g_hash_table_foreach_remove:
 558  * @hash_table: a #GHashTable.
 559  * @func: the function to call for each key/value pair.
 560  * @user_data: user data to pass to the function.
 561  *
 562  * Calls the given function for each key/value pair in the #GHashTable.
 563  * If the function returns %TRUE, then the key/value pair is removed from the
 564  * #GHashTable. If you supplied key or value destroy functions when creating
 565  * the #GHashTable, they are used to free the memory allocated for the removed
 566  * keys and values.
 567  *
 568  * Return value: the number of key/value pairs removed.
 569  **/
 570 guint
 571 g_hash_table_foreach_remove (GHashTable *hash_table,
 572                              GHRFunc     func,
 573                              gpointer    user_data)
 574 {
 575   g_return_val_if_fail (hash_table != NULL, 0);
 576   g_return_val_if_fail (func != NULL, 0);
 577
 578   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
 579 }
 580
 581 /**
 582  * g_hash_table_foreach_steal:
 583  * @hash_table: a #GHashTable.
 584  * @func: the function to call for each key/value pair.
 585  * @user_data: user data to pass to the function.
 586  *
 587  * Calls the given function for each key/value pair in the #GHashTable.
 588  * If the function returns %TRUE, then the key/value pair is removed from the
 589  * #GHashTable, but no key or value destroy functions are called.
 590  *
 591  * Return value: the number of key/value pairs removed.
 592  **/
 593 guint
 594 g_hash_table_foreach_steal (GHashTable *hash_table,
 595                             GHRFunc     func,
 596                             gpointer    user_data)
 597 {
 598   g_return_val_if_fail (hash_table != NULL, 0);
 599   g_return_val_if_fail (func != NULL, 0);
 600
 601   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
 602 }
 603
 604 static guint
 605 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 606                                       GHRFunc     func,
 607                                       gpointer    user_data,
 608                                       gboolean    notify)
 609 {
 610   GHashNode *node, **node_ptr;
 611   guint deleted = 0;
 612   gint i;
 613
 614   for (i = 0; i < hash_table->size; i++)
 615     for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;)
 616       if ((* func) (node->key, node->value, user_data))
 617         {
 618           g_hash_table_remove_node (hash_table, &node_ptr, notify);
 619           deleted++;
 620         }
 621       else
 622         node_ptr = &node->next;
 623
 624   g_hash_table_maybe_resize (hash_table);
 625
 626   return deleted;
 627 }
 628
 629 /**
 630  * g_hash_table_foreach:
 631  * @hash_table: a #GHashTable.
 632  * @func: the function to call for each key/value pair.
 633  * @user_data: user data to pass to the function.
 634  *
 635  * Calls the given function for each of the key/value pairs in the
 636  * #GHashTable.  The function is passed the key and value of each
 637  * pair, and the given @user_data parameter.  The hash table may not
 638  * be modified while iterating over it (you can't add/remove
 639  * items). To remove all items matching a predicate, use
 640  * g_hash_table_foreach_remove().
 641  *
 642  * See g_hash_table_find() for performance caveats for linear
 643  * order searches in contrast to g_hash_table_lookup().
 644  **/
 645 void
 646 g_hash_table_foreach (GHashTable *hash_table,
 647                       GHFunc      func,
 648                       gpointer    user_data)
 649 {
 650   GHashNode *node;
 651   gint i;
 652
 653   g_return_if_fail (hash_table != NULL);
 654   g_return_if_fail (func != NULL);
 655
 656   for (i = 0; i < hash_table->size; i++)
 657     for (node = hash_table->nodes[i]; node; node = node->next)
 658       (* func) (node->key, node->value, user_data);
 659 }
 660
 661 /**
 662  * g_hash_table_find:
 663  * @hash_table: a #GHashTable.
 664  * @predicate:  function to test the key/value pairs for a certain property.
 665  * @user_data:  user data to pass to the function.
 666  *
 667  * Calls the given function for key/value pairs in the #GHashTable until
 668  * @predicate returns %TRUE.  The function is passed the key and value of
 669  * each pair, and the given @user_data parameter. The hash table may not
 670  * be modified while iterating over it (you can't add/remove items).
 671  *
 672  * Note, that hash tables are really only optimized for forward lookups,
 673  * i.e. g_hash_table_lookup().
 674  * So code that frequently issues g_hash_table_find() or
 675  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
 676  * hash table) should probably be reworked to use additional or different
 677  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
 678  * operation issued for all n values in a hash table ends up needing O(n*n)
 679  * operations).
 680  *
 681  * Return value: The value of the first key/value pair is returned, for which
 682  * func evaluates to %TRUE. If no pair with the requested property is found,
 683  * %NULL is returned.
 684  *
 685  * Since: 2.4
 686  **/
 687 gpointer
 688 g_hash_table_find (GHashTable      *hash_table,
 689                    GHRFunc          predicate,
 690                    gpointer         user_data)
 691 {
 692   GHashNode *node;
 693   gint i;
 694
 695   g_return_val_if_fail (hash_table != NULL, NULL);
 696   g_return_val_if_fail (predicate != NULL, NULL);
 697
 698   for (i = 0; i < hash_table->size; i++)
 699     for (node = hash_table->nodes[i]; node; node = node->next)
 700       if (predicate (node->key, node->value, user_data))
 701         return node->value;
 702   return NULL;
 703 }
 704
 705 /**
 706  * g_hash_table_size:
 707  * @hash_table: a #GHashTable.
 708  *
 709  * Returns the number of elements contained in the #GHashTable.
 710  *
 711  * Return value: the number of key/value pairs in the #GHashTable.
 712  **/
 713 guint
 714 g_hash_table_size (GHashTable *hash_table)
 715 {
 716   g_return_val_if_fail (hash_table != NULL, 0);
 717
 718   return hash_table->nnodes;
 719 }
 720
 721 /**
 722  * g_hash_table_get_keys:
 723  * @hash_table: a #GHashTable
 724  *
 725  * Retrieves every key inside @hash_table. The returned data is valid
 726  * until @hash_table is modified.
 727  *
 728  * Return value: a #GList containing all the keys inside the hash
 729  *   table. The content of the list is owned by the hash table and
 730  *   should not be modified or freed. Use g_list_free() when done
 731  *   using the list.
 732  *
 733  * Since: 2.14
 734  */
 735 GList *
 736 g_hash_table_get_keys (GHashTable *hash_table)
 737 {
 738   GHashNode *node;
 739   gint i;
 740   GList *retval;
 741
 742   g_return_val_if_fail (hash_table != NULL, NULL);
 743
 744   retval = NULL;
 745   for (i = 0; i < hash_table->size; i++)
 746     for (node = hash_table->nodes[i]; node; node = node->next)
 747       retval = g_list_prepend (retval, node->key);
 748
 749   return retval;
 750 }
 751
 752 /**
 753  * g_hash_table_get_values:
 754  * @hash_table: a #GHashTable
 755  *
 756  * Retrieves every value inside @hash_table. The returned data is
 757  * valid until @hash_table is modified.
 758  *
 759  * Return value: a #GList containing all the values inside the hash
 760  *   table. The content of the list is owned by the hash table and
 761  *   should not be modified or freed. Use g_list_free() when done
 762  *   using the list.
 763  *
 764  * Since: 2.14
 765  */
 766 GList *
 767 g_hash_table_get_values (GHashTable *hash_table)
 768 {
 769   GHashNode *node;
 770   gint i;
 771   GList *retval;
 772
 773   g_return_val_if_fail (hash_table != NULL, NULL);
 774
 775   retval = NULL;
 776   for (i = 0; i < hash_table->size; i++)
 777     for (node = hash_table->nodes[i]; node; node = node->next)
 778       retval = g_list_prepend (retval, node->value);
 779
 780   return retval;
 781 }
 782
 783 static void
 784 g_hash_table_resize (GHashTable *hash_table)
 785 {
 786   GHashNode **new_nodes;
 787   GHashNode *node;
 788   GHashNode *next;
 789   guint hash_val;
 790   gint new_size;
 791   gint i;
 792
 793   new_size = g_spaced_primes_closest (hash_table->nnodes);
 794   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 795
 796   new_nodes = g_new0 (GHashNode*, new_size);
 797
 798   for (i = 0; i < hash_table->size; i++)
 799     for (node = hash_table->nodes[i]; node; node = next)
 800       {
 801         next = node->next;
 802
 803         hash_val = node->key_hash % new_size;
 804
 805         node->next = new_nodes[hash_val];
 806         new_nodes[hash_val] = node;
 807       }
 808
 809   g_free (hash_table->nodes);
 810   hash_table->nodes = new_nodes;
 811   hash_table->size = new_size;
 812 }
 813
 814 #define __G_HASH_C__
 815 #include "galiasdef.c"