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