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 (hash_table->key_destroy_func)
 342         {
 343           if (keep_new_key)
 344             hash_table->key_destroy_func ((*node)->key);
 345           else
 346             hash_table->key_destroy_func (key);
 347         }
 348
 349       if (hash_table->value_destroy_func)
 350         hash_table->value_destroy_func ((*node)->value);
 351
 352       (*node)->value = value;
 353     }
 354   else
 355     {
 356       *node = g_hash_node_new (key, value, key_hash);
 357       hash_table->nnodes++;
 358       G_HASH_TABLE_RESIZE (hash_table);
 359     }
 360 }
 361
 362 /**
 363  * g_hash_table_insert:
 364  * @hash_table: a #GHashTable.
 365  * @key: a key to insert.
 366  * @value: the value to associate with the key.
 367  *
 368  * Inserts a new key and value into a #GHashTable.
 369  *
 370  * If the key already exists in the #GHashTable its current value is replaced
 371  * with the new value. If you supplied a @value_destroy_func when creating the
 372  * #GHashTable, the old value is freed using that function. If you supplied
 373  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 374  * using that function.
 375  **/
 376 void
 377 g_hash_table_insert (GHashTable *hash_table,
 378                      gpointer    key,
 379                      gpointer    value)
 380 {
 381   return g_hash_table_insert_internal (hash_table, key, value, FALSE);
 382 }
 383
 384 /**
 385  * g_hash_table_replace:
 386  * @hash_table: a #GHashTable.
 387  * @key: a key to insert.
 388  * @value: the value to associate with the key.
 389  *
 390  * Inserts a new key and value into a #GHashTable similar to
 391  * g_hash_table_insert(). The difference is that if the key already exists
 392  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 393  * @value_destroy_func when creating the #GHashTable, the old value is freed
 394  * using that function. If you supplied a @key_destroy_func when creating the
 395  * #GHashTable, the old key is freed using that function.
 396  **/
 397 void
 398 g_hash_table_replace (GHashTable *hash_table,
 399                       gpointer    key,
 400                       gpointer    value)
 401 {
 402   return g_hash_table_insert_internal (hash_table, key, value, TRUE);
 403 }
 404
 405 /**
 406  * g_hash_table_remove:
 407  * @hash_table: a #GHashTable.
 408  * @key: the key to remove.
 409  *
 410  * Removes a key and its associated value from a #GHashTable.
 411  *
 412  * If the #GHashTable was created using g_hash_table_new_full(), the
 413  * key and value are freed using the supplied destroy functions, otherwise
 414  * you have to make sure that any dynamically allocated values are freed
 415  * yourself.
 416  *
 417  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 418  **/
 419 gboolean
 420 g_hash_table_remove (GHashTable    *hash_table,
 421                      gconstpointer  key)
 422 {
 423   GHashNode **node, *dest;
 424
 425   g_return_val_if_fail (hash_table != NULL, FALSE);
 426
 427   node = g_hash_table_lookup_node (hash_table, key, NULL);
 428   if (*node)
 429     {
 430       dest = *node;
 431       (*node) = dest->next;
 432       g_hash_node_destroy (dest,
 433                            hash_table->key_destroy_func,
 434                            hash_table->value_destroy_func);
 435       hash_table->nnodes--;
 436
 437       G_HASH_TABLE_RESIZE (hash_table);
 438
 439       return TRUE;
 440     }
 441
 442   return FALSE;
 443 }
 444
 445 /**
 446  * g_hash_table_remove_all:
 447  * @hash_table: a #GHashTable
 448  *
 449  * Removes all keys and their associated values from a #GHashTable.
 450  *
 451  * If the #GHashTable was created using g_hash_table_new_full(), the keys
 452  * and values are freed using the supplied destroy functions, otherwise you
 453  * have to make sure that any dynamically allocated values are freed
 454  * yourself.
 455  *
 456  * Since: 2.12
 457  **/
 458 void
 459 g_hash_table_remove_all (GHashTable *hash_table)
 460 {
 461   guint i;
 462
 463   g_return_if_fail (hash_table != NULL);
 464
 465   for (i = 0; i < hash_table->size; i++)
 466     {
 467       g_hash_nodes_destroy (hash_table->nodes[i],
 468                             hash_table->key_destroy_func,
 469                             hash_table->value_destroy_func);
 470       hash_table->nodes[i] = NULL;
 471     }
 472   hash_table->nnodes = 0;
 473
 474   G_HASH_TABLE_RESIZE (hash_table);
 475 }
 476
 477 /**
 478  * g_hash_table_steal:
 479  * @hash_table: a #GHashTable.
 480  * @key: the key to remove.
 481  *
 482  * Removes a key and its associated value from a #GHashTable without
 483  * calling the key and value destroy functions.
 484  *
 485  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 486  **/
 487 gboolean
 488 g_hash_table_steal (GHashTable    *hash_table,
 489                     gconstpointer  key)
 490 {
 491   GHashNode **node, *dest;
 492
 493   g_return_val_if_fail (hash_table != NULL, FALSE);
 494
 495   node = g_hash_table_lookup_node (hash_table, key, NULL);
 496   if (*node)
 497     {
 498       dest = *node;
 499       (*node) = dest->next;
 500       g_hash_node_destroy (dest, NULL, NULL);
 501       hash_table->nnodes--;
 502
 503       G_HASH_TABLE_RESIZE (hash_table);
 504
 505       return TRUE;
 506     }
 507
 508   return FALSE;
 509 }
 510
 511 /**
 512  * g_hash_table_steal_all:
 513  * @hash_table: a #GHashTable.
 514  *
 515  * Removes all keys and their associated values from a #GHashTable
 516  * without calling the key and value destroy functions.
 517  *
 518  * Since: 2.12
 519  **/
 520 void
 521 g_hash_table_steal_all (GHashTable *hash_table)
 522 {
 523   guint i;
 524
 525   g_return_if_fail (hash_table != NULL);
 526
 527   for (i = 0; i < hash_table->size; i++)
 528     {
 529       g_hash_nodes_destroy (hash_table->nodes[i], NULL, NULL);
 530       hash_table->nodes[i] = NULL;
 531     }
 532
 533   hash_table->nnodes = 0;
 534
 535   G_HASH_TABLE_RESIZE (hash_table);
 536 }
 537
 538 /**
 539  * g_hash_table_foreach_remove:
 540  * @hash_table: a #GHashTable.
 541  * @func: the function to call for each key/value pair.
 542  * @user_data: user data to pass to the function.
 543  *
 544  * Calls the given function for each key/value pair in the #GHashTable.
 545  * If the function returns %TRUE, then the key/value pair is removed from the
 546  * #GHashTable. If you supplied key or value destroy functions when creating
 547  * the #GHashTable, they are used to free the memory allocated for the removed
 548  * keys and values.
 549  *
 550  * Return value: the number of key/value pairs removed.
 551  **/
 552 guint
 553 g_hash_table_foreach_remove (GHashTable *hash_table,
 554                              GHRFunc     func,
 555                              gpointer    user_data)
 556 {
 557   g_return_val_if_fail (hash_table != NULL, 0);
 558   g_return_val_if_fail (func != NULL, 0);
 559
 560   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
 561 }
 562
 563 /**
 564  * g_hash_table_foreach_steal:
 565  * @hash_table: a #GHashTable.
 566  * @func: the function to call for each key/value pair.
 567  * @user_data: user data to pass to the function.
 568  *
 569  * Calls the given function for each key/value pair in the #GHashTable.
 570  * If the function returns %TRUE, then the key/value pair is removed from the
 571  * #GHashTable, but no key or value destroy functions are called.
 572  *
 573  * Return value: the number of key/value pairs removed.
 574  **/
 575 guint
 576 g_hash_table_foreach_steal (GHashTable *hash_table,
 577                             GHRFunc     func,
 578                             gpointer    user_data)
 579 {
 580   g_return_val_if_fail (hash_table != NULL, 0);
 581   g_return_val_if_fail (func != NULL, 0);
 582
 583   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
 584 }
 585
 586 static guint
 587 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 588                                       GHRFunc     func,
 589                                       gpointer    user_data,
 590                                       gboolean    notify)
 591 {
 592   GHashNode *node, *prev;
 593   gint i;
 594   guint deleted = 0;
 595
 596   for (i = 0; i < hash_table->size; i++)
 597     {
 598     restart:
 599
 600       prev = NULL;
 601
 602       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
 603         {
 604           if ((* func) (node->key, node->value, user_data))
 605             {
 606               deleted += 1;
 607
 608               hash_table->nnodes -= 1;
 609
 610               if (prev)
 611                 {
 612                   prev->next = node->next;
 613                   g_hash_node_destroy (node,
 614                                        notify ? hash_table->key_destroy_func : NULL,
 615                                        notify ? hash_table->value_destroy_func : NULL);
 616                   node = prev;
 617                 }
 618               else
 619                 {
 620                   hash_table->nodes[i] = node->next;
 621                   g_hash_node_destroy (node,
 622                                        notify ? hash_table->key_destroy_func : NULL,
 623                                        notify ? hash_table->value_destroy_func : NULL);
 624                   goto restart;
 625                 }
 626             }
 627         }
 628     }
 629
 630   G_HASH_TABLE_RESIZE (hash_table);
 631
 632   return deleted;
 633 }
 634
 635 /**
 636  * g_hash_table_foreach:
 637  * @hash_table: a #GHashTable.
 638  * @func: the function to call for each key/value pair.
 639  * @user_data: user data to pass to the function.
 640  *
 641  * Calls the given function for each of the key/value pairs in the
 642  * #GHashTable.  The function is passed the key and value of each
 643  * pair, and the given @user_data parameter.  The hash table may not
 644  * be modified while iterating over it (you can't add/remove
 645  * items). To remove all items matching a predicate, use
 646  * g_hash_table_foreach_remove().
 647  *
 648  * See g_hash_table_find() for performance caveats for linear
 649  * order searches in contrast to g_hash_table_lookup().
 650  **/
 651 void
 652 g_hash_table_foreach (GHashTable *hash_table,
 653                       GHFunc      func,
 654                       gpointer    user_data)
 655 {
 656   GHashNode *node;
 657   gint i;
 658
 659   g_return_if_fail (hash_table != NULL);
 660   g_return_if_fail (func != NULL);
 661
 662   for (i = 0; i < hash_table->size; i++)
 663     for (node = hash_table->nodes[i]; node; node = node->next)
 664       (* func) (node->key, node->value, user_data);
 665 }
 666
 667 /**
 668  * g_hash_table_find:
 669  * @hash_table: a #GHashTable.
 670  * @predicate:  function to test the key/value pairs for a certain property.
 671  * @user_data:  user data to pass to the function.
 672  *
 673  * Calls the given function for key/value pairs in the #GHashTable until
 674  * @predicate returns %TRUE.  The function is passed the key and value of
 675  * each pair, and the given @user_data parameter. The hash table may not
 676  * be modified while iterating over it (you can't add/remove items).
 677  *
 678  * Note, that hash tables are really only optimized for forward lookups,
 679  * i.e. g_hash_table_lookup().
 680  * So code that frequently issues g_hash_table_find() or
 681  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
 682  * hash table) should probably be reworked to use additional or different
 683  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
 684  * operation issued for all n values in a hash table ends up needing O(n*n)
 685  * operations).
 686  *
 687  * Return value: The value of the first key/value pair is returned, for which
 688  * func evaluates to %TRUE. If no pair with the requested property is found,
 689  * %NULL is returned.
 690  *
 691  * Since: 2.4
 692  **/
 693 gpointer
 694 g_hash_table_find (GHashTable      *hash_table,
 695                    GHRFunc          predicate,
 696                    gpointer         user_data)
 697 {
 698   GHashNode *node;
 699   gint i;
 700
 701   g_return_val_if_fail (hash_table != NULL, NULL);
 702   g_return_val_if_fail (predicate != NULL, NULL);
 703
 704   for (i = 0; i < hash_table->size; i++)
 705     for (node = hash_table->nodes[i]; node; node = node->next)
 706       if (predicate (node->key, node->value, user_data))
 707         return node->value;
 708   return NULL;
 709 }
 710
 711 /**
 712  * g_hash_table_size:
 713  * @hash_table: a #GHashTable.
 714  *
 715  * Returns the number of elements contained in the #GHashTable.
 716  *
 717  * Return value: the number of key/value pairs in the #GHashTable.
 718  **/
 719 guint
 720 g_hash_table_size (GHashTable *hash_table)
 721 {
 722   g_return_val_if_fail (hash_table != NULL, 0);
 723
 724   return hash_table->nnodes;
 725 }
 726
 727 /**
 728  * g_hash_table_get_keys:
 729  * @hash_table: a #GHashTable
 730  *
 731  * Retrieves every key inside @hash_table. The returned data is valid
 732  * until @hash_table is modified.
 733  *
 734  * Return value: a #GList containing all the keys inside the hash
 735  *   table. The content of the list is owned by the hash table and
 736  *   should not be modified or freed. Use g_list_free() when done
 737  *   using the list.
 738  *
 739  * Since: 2.14
 740  */
 741 GList *
 742 g_hash_table_get_keys (GHashTable *hash_table)
 743 {
 744   GHashNode *node;
 745   gint i;
 746   GList *retval;
 747
 748   g_return_val_if_fail (hash_table != NULL, NULL);
 749
 750   retval = NULL;
 751   for (i = 0; i < hash_table->size; i++)
 752     for (node = hash_table->nodes[i]; node; node = node->next)
 753       retval = g_list_prepend (retval, node->key);
 754
 755   return retval;
 756 }
 757
 758 /**
 759  * g_hash_table_get_values:
 760  * @hash_table: a #GHashTable
 761  *
 762  * Retrieves every value inside @hash_table. The returned data is
 763  * valid until @hash_table is modified.
 764  *
 765  * Return value: a #GList containing all the values inside the hash
 766  *   table. The content of the list is owned by the hash table and
 767  *   should not be modified or freed. Use g_list_free() when done
 768  *   using the list.
 769  *
 770  * Since: 2.14
 771  */
 772 GList *
 773 g_hash_table_get_values (GHashTable *hash_table)
 774 {
 775   GHashNode *node;
 776   gint i;
 777   GList *retval;
 778
 779   g_return_val_if_fail (hash_table != NULL, NULL);
 780
 781   retval = NULL;
 782   for (i = 0; i < hash_table->size; i++)
 783     for (node = hash_table->nodes[i]; node; node = node->next)
 784       retval = g_list_prepend (retval, node->value);
 785
 786   return retval;
 787 }
 788
 789 static void
 790 g_hash_table_resize (GHashTable *hash_table)
 791 {
 792   GHashNode **new_nodes;
 793   GHashNode *node;
 794   GHashNode *next;
 795   guint hash_val;
 796   gint new_size;
 797   gint i;
 798
 799   new_size = g_spaced_primes_closest (hash_table->nnodes);
 800   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 801
 802   new_nodes = g_new0 (GHashNode*, new_size);
 803
 804   for (i = 0; i < hash_table->size; i++)
 805     for (node = hash_table->nodes[i]; node; node = next)
 806       {
 807         next = node->next;
 808
 809         hash_val = node->key_hash % new_size;
 810
 811         node->next = new_nodes[hash_val];
 812         new_nodes[hash_val] = node;
 813       }
 814
 815   g_free (hash_table->nodes);
 816   hash_table->nodes = new_nodes;
 817   hash_table->size = new_size;
 818 }
 819
 820 static GHashNode*
 821 g_hash_node_new (gpointer key,
 822                  gpointer value,
 823                  guint key_hash)
 824 {
 825   GHashNode *hash_node = g_slice_new (GHashNode);
 826
 827   hash_node->key = key;
 828   hash_node->value = value;
 829   hash_node->key_hash = key_hash;
 830   hash_node->next = NULL;
 831
 832   return hash_node;
 833 }
 834
 835 static void
 836 g_hash_node_destroy (GHashNode      *hash_node,
 837                      GDestroyNotify  key_destroy_func,
 838                      GDestroyNotify  value_destroy_func)
 839 {
 840   if (key_destroy_func)
 841     key_destroy_func (hash_node->key);
 842   if (value_destroy_func)
 843     value_destroy_func (hash_node->value);
 844   g_slice_free (GHashNode, hash_node);
 845 }
 846
 847 static void
 848 g_hash_nodes_destroy (GHashNode *hash_node,
 849                       GFreeFunc  key_destroy_func,
 850                       GFreeFunc  value_destroy_func)
 851 {
 852   while (hash_node)
 853     {
 854       GHashNode *next = hash_node->next;
 855       if (key_destroy_func)
 856         key_destroy_func (hash_node->key);
 857       if (value_destroy_func)
 858         value_destroy_func (hash_node->value);
 859       g_slice_free (GHashNode, hash_node);
 860       hash_node = next;
 861     }
 862 }
 863
 864
 865 #define __G_HASH_C__
 866 #include "galiasdef.c"