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