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