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