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 #ifndef G_DISABLE_ASSERT
  60   /*
  61    * Tracks the structure of the hash table, not its contents: is only
  62    * incremented when a node is added or removed (is not incremented
  63    * when the key or data of a node is modified).
  64    */
  65   int              version;
  66 #endif
  67   GDestroyNotify   key_destroy_func;
  68   GDestroyNotify   value_destroy_func;
  69 };
  70
  71 typedef struct
  72 {
  73   GHashTable    *hash_table;
  74   GHashNode     *prev_node;
  75   GHashNode     *node;
  76   int           position;
  77   gboolean      pre_advanced;
  78   int           version;
  79 } RealIter;
  80
  81 /*
  82  * g_hash_table_lookup_node:
  83  * @hash_table: our #GHashTable
  84  * @key: the key to lookup against
  85  * @hash_return: optional key hash return location
  86  * Return value: a pointer to the described #GHashNode pointer
  87  *
  88  * Performs a lookup in the hash table.  Virtually all hash operations
  89  * will use this function internally.
  90  *
  91  * This function first computes the hash value of the key using the
  92  * user's hash function.
  93  *
  94  * If an entry in the table matching @key is found then this function
  95  * returns a pointer to the pointer to that entry in the table.  In
  96  * the case that the entry is at the head of a chain, this pointer
  97  * will be an item in the nodes[] array.  In the case that the entry
  98  * is not at the head of a chain, this pointer will be the ->next
  99  * pointer on the node that preceeds it.
 100  *
 101  * In the case that no matching entry exists in the table, a pointer
 102  * to a %NULL pointer will be returned.  To insert a item, this %NULL
 103  * pointer should be updated to point to the new #GHashNode.
 104  *
 105  * If @hash_return is a pass-by-reference parameter.  If it is
 106  * non-%NULL then the computed hash value is returned.  This is to
 107  * save insertions from having to compute the hash record again for
 108  * the new record.
 109  */
 110 static inline GHashNode **
 111 g_hash_table_lookup_node (GHashTable    *hash_table,
 112                           gconstpointer  key,
 113                           guint         *hash_return)
 114 {
 115   GHashNode **node_ptr, *node;
 116   guint hash_value;
 117
 118   hash_value = (* hash_table->hash_func) (key);
 119   node_ptr = &hash_table->nodes[hash_value % hash_table->size];
 120
 121   if (hash_return)
 122     *hash_return = hash_value;
 123
 124   /* Hash table lookup needs to be fast.
 125    *  We therefore remove the extra conditional of testing
 126    *  whether to call the key_equal_func or not from
 127    *  the inner loop.
 128    *
 129    *  Additional optimisation: first check if our full hash
 130    *  values are equal so we can avoid calling the full-blown
 131    *  key equality function in most cases.
 132    */
 133   if (hash_table->key_equal_func)
 134     {
 135       while ((node = *node_ptr))
 136         {
 137           if (node->key_hash == hash_value &&
 138               hash_table->key_equal_func (node->key, key))
 139             break;
 140
 141           node_ptr = &(*node_ptr)->next;
 142         }
 143     }
 144   else
 145     {
 146       while ((node = *node_ptr))
 147         {
 148           if (node->key == key)
 149             break;
 150
 151           node_ptr = &(*node_ptr)->next;
 152         }
 153     }
 154
 155   return node_ptr;
 156 }
 157
 158 /*
 159  * g_hash_table_remove_node:
 160  * @hash_table: our #GHashTable
 161  * @node_ptr_ptr: a pointer to the return value from
 162  *   g_hash_table_lookup_node()
 163  * @notify: %TRUE if the destroy notify handlers are to be called
 164  *
 165  * Removes a node from the hash table and updates the node count.  The
 166  * node is freed.  No table resize is performed.
 167  *
 168  * If @notify is %TRUE then the destroy notify functions are called
 169  * for the key and value of the hash node.
 170  *
 171  * @node_ptr_ptr is a pass-by-reference in/out parameter.  When the
 172  * function is called, it should point to the pointer to the node to
 173  * remove.  This level of indirection is required so that the pointer
 174  * may be updated appropriately once the node has been removed.
 175  *
 176  * Before the function returns, the pointer at @node_ptr_ptr will be
 177  * updated to point to the position in the table that contains the
 178  * pointer to the "next" node in the chain.  This makes this function
 179  * convenient to use from functions that iterate over the entire
 180  * table.  If there is no further item in the chain then the
 181  * #GHashNode pointer will be %NULL (ie: **node_ptr_ptr == %NULL).
 182  *
 183  * Since the pointer in the table to the removed node is replaced with
 184  * either a pointer to the next node or a %NULL pointer as
 185  * appropriate, the pointer at the end of @node_ptr_ptr will never be
 186  * modified at all.  Stay tuned. :)
 187  */
 188 static void
 189 g_hash_table_remove_node (GHashTable   *hash_table,
 190                           GHashNode  ***node_ptr_ptr,
 191                           gboolean      notify)
 192 {
 193   GHashNode **node_ptr, *node;
 194
 195   node_ptr = *node_ptr_ptr;
 196   node = *node_ptr;
 197
 198   *node_ptr = node->next;
 199
 200   if (notify && hash_table->key_destroy_func)
 201     hash_table->key_destroy_func (node->key);
 202
 203   if (notify && hash_table->value_destroy_func)
 204     hash_table->value_destroy_func (node->value);
 205
 206   g_slice_free (GHashNode, node);
 207
 208   hash_table->nnodes--;
 209 }
 210
 211 /*
 212  * g_hash_table_remove_all_nodes:
 213  * @hash_table: our #GHashTable
 214  * @notify: %TRUE if the destroy notify handlers are to be called
 215  *
 216  * Removes all nodes from the table.  Since this may be a precursor to
 217  * freeing the table entirely, no resize is performed.
 218  *
 219  * If @notify is %TRUE then the destroy notify functions are called
 220  * for the key and value of the hash node.
 221  */
 222 static void
 223 g_hash_table_remove_all_nodes (GHashTable *hash_table,
 224                                gboolean    notify)
 225 {
 226   GHashNode **node_ptr;
 227   int i;
 228
 229   for (i = 0; i < hash_table->size; i++)
 230     for (node_ptr = &hash_table->nodes[i]; *node_ptr != NULL;)
 231       g_hash_table_remove_node (hash_table, &node_ptr, notify);
 232
 233   hash_table->nnodes = 0;
 234 }
 235
 236 /*
 237  * g_hash_table_resize:
 238  * @hash_table: our #GHashTable
 239  *
 240  * Resizes the hash table to the optimal size based on the number of
 241  * nodes currently held.  If you call this function then a resize will
 242  * occur, even if one does not need to occur.  Use
 243  * g_hash_table_maybe_resize() instead.
 244  */
 245 static void
 246 g_hash_table_resize (GHashTable *hash_table)
 247 {
 248   GHashNode **new_nodes;
 249   GHashNode *node;
 250   GHashNode *next;
 251   guint hash_val;
 252   gint new_size;
 253   gint i;
 254
 255   new_size = g_spaced_primes_closest (hash_table->nnodes);
 256   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 257
 258   new_nodes = g_new0 (GHashNode*, new_size);
 259
 260   for (i = 0; i < hash_table->size; i++)
 261     for (node = hash_table->nodes[i]; node; node = next)
 262       {
 263         next = node->next;
 264
 265         hash_val = node->key_hash % new_size;
 266
 267         node->next = new_nodes[hash_val];
 268         new_nodes[hash_val] = node;
 269       }
 270
 271   g_free (hash_table->nodes);
 272   hash_table->nodes = new_nodes;
 273   hash_table->size = new_size;
 274 }
 275
 276 /*
 277  * g_hash_table_maybe_resize:
 278  * @hash_table: our #GHashTable
 279  *
 280  * Resizes the hash table, if needed.
 281  *
 282  * Essentially, calls g_hash_table_resize() if the table has strayed
 283  * too far from its ideal size for its number of nodes.
 284  */
 285 static inline void
 286 g_hash_table_maybe_resize (GHashTable *hash_table)
 287 {
 288   gint nnodes = hash_table->nnodes;
 289   gint size = hash_table->size;
 290
 291   if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) ||
 292       (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE))
 293     g_hash_table_resize (hash_table);
 294 }
 295
 296 /**
 297  * g_hash_table_new:
 298  * @hash_func: a function to create a hash value from a key.
 299  *   Hash values are used to determine where keys are stored within the
 300  *   #GHashTable data structure. The g_direct_hash(), g_int_hash() and
 301  *   g_str_hash() functions are provided for some common types of keys.
 302  *   If hash_func is %NULL, g_direct_hash() is used.
 303  * @key_equal_func: a function to check two keys for equality.  This is
 304  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
 305  *   g_int_equal() and g_str_equal() functions are provided for the most
 306  *   common types of keys. If @key_equal_func is %NULL, keys are compared
 307  *   directly in a similar fashion to g_direct_equal(), but without the
 308  *   overhead of a function call.
 309  *
 310  * Creates a new #GHashTable with a reference count of 1.
 311  *
 312  * Return value: a new #GHashTable.
 313  **/
 314 GHashTable*
 315 g_hash_table_new (GHashFunc    hash_func,
 316                   GEqualFunc   key_equal_func)
 317 {
 318   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 319 }
 320
 321
 322 /**
 323  * g_hash_table_new_full:
 324  * @hash_func: a function to create a hash value from a key.
 325  * @key_equal_func: a function to check two keys for equality.
 326  * @key_destroy_func: a function to free the memory allocated for the key
 327  *   used when removing the entry from the #GHashTable or %NULL if you
 328  *   don't want to supply such a function.
 329  * @value_destroy_func: a function to free the memory allocated for the
 330  *   value used when removing the entry from the #GHashTable or %NULL if
 331  *   you don't want to supply such a function.
 332  *
 333  * Creates a new #GHashTable like g_hash_table_new() with a reference count
 334  * of 1 and allows to specify functions to free the memory allocated for the
 335  * key and value that get called when removing the entry from the #GHashTable.
 336  *
 337  * Return value: a new #GHashTable.
 338  **/
 339 GHashTable*
 340 g_hash_table_new_full (GHashFunc       hash_func,
 341                        GEqualFunc      key_equal_func,
 342                        GDestroyNotify  key_destroy_func,
 343                        GDestroyNotify  value_destroy_func)
 344 {
 345   GHashTable *hash_table;
 346
 347   hash_table = g_slice_new (GHashTable);
 348   hash_table->size               = HASH_TABLE_MIN_SIZE;
 349   hash_table->nnodes             = 0;
 350   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
 351   hash_table->key_equal_func     = key_equal_func;
 352   hash_table->ref_count          = 1;
 353 #ifndef G_DISABLE_ASSERT
 354   hash_table->version            = 0;
 355 #endif
 356   hash_table->key_destroy_func   = key_destroy_func;
 357   hash_table->value_destroy_func = value_destroy_func;
 358   hash_table->nodes              = g_new0 (GHashNode*, hash_table->size);
 359
 360   return hash_table;
 361 }
 362
 363 /**
 364  * g_hash_table_iter_init:
 365  * @iter: an uninitialized #GHashTableIter.
 366  * @hash_table: a #GHashTable.
 367  *
 368  * Initializes a key/value pair iterator and associates it with
 369  * @hash_table. Modifying the hash table after calling this function
 370  * invalidates the returned iterator.
 371  * |[
 372  * GHashTableIter iter;
 373  * gpointer key, value;
 374  *
 375  * g_hash_table_iter_init (&iter, hash_table);
 376  * while (g_hash_table_iter_next (&iter, &key, &value))
 377  *   {
 378  *     /&ast; do something with key and value &ast;/
 379  *   }
 380  * ]|
 381  *
 382  * Since: 2.16
 383  **/
 384 void
 385 g_hash_table_iter_init (GHashTableIter *iter,
 386                         GHashTable     *hash_table)
 387 {
 388   RealIter *ri = (RealIter *) iter;
 389
 390   g_return_if_fail (iter != NULL);
 391   g_return_if_fail (hash_table != NULL);
 392
 393   ri->hash_table = hash_table;
 394   ri->prev_node = NULL;
 395   ri->node = NULL;
 396   ri->position = -1;
 397   ri->pre_advanced = FALSE;
 398 #ifndef G_DISABLE_ASSERT
 399   ri->version = hash_table->version;
 400 #endif
 401 }
 402
 403 /**
 404  * g_hash_table_iter_next:
 405  * @iter: an initialized #GHashTableIter.
 406  * @key: a location to store the key, or %NULL.
 407  * @value: a location to store the value, or %NULL.
 408  *
 409  * Advances @iter and retrieves the key and/or value that are now
 410  * pointed to as a result of this advancement. If %FALSE is returned,
 411  * @key and @value are not set, and the iterator becomes invalid.
 412  *
 413  * Return value: %FALSE if the end of the #GHashTable has been reached.
 414  *
 415  * Since: 2.16
 416  **/
 417 gboolean
 418 g_hash_table_iter_next (GHashTableIter *iter,
 419                         gpointer       *key,
 420                         gpointer       *value)
 421 {
 422   RealIter *ri = (RealIter *) iter;
 423
 424   g_return_val_if_fail (iter != NULL, FALSE);
 425 #ifndef G_DISABLE_ASSERT
 426   g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
 427 #endif
 428
 429   if (ri->pre_advanced)
 430     {
 431       ri->pre_advanced = FALSE;
 432
 433       if (ri->node == NULL)
 434         return FALSE;
 435     }
 436   else
 437     {
 438       if (ri->node != NULL)
 439         {
 440           ri->prev_node = ri->node;
 441           ri->node = ri->node->next;
 442         }
 443
 444       while (ri->node == NULL)
 445         {
 446           ri->position++;
 447           if (ri->position >= ri->hash_table->size)
 448             return FALSE;
 449
 450           ri->prev_node = NULL;
 451           ri->node = ri->hash_table->nodes[ri->position];
 452         }
 453     }
 454
 455   if (key != NULL)
 456     *key = ri->node->key;
 457   if (value != NULL)
 458     *value = ri->node->value;
 459
 460   return TRUE;
 461 }
 462
 463 /**
 464  * g_hash_table_iter_get_hash_table:
 465  * @iter: an initialized #GHashTableIter.
 466  *
 467  * Returns the #GHashTable associated with @iter.
 468  *
 469  * Return value: the #GHashTable associated with @iter.
 470  *
 471  * Since: 2.16
 472  **/
 473 GHashTable *
 474 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
 475 {
 476   g_return_val_if_fail (iter != NULL, NULL);
 477
 478   return ((RealIter *) iter)->hash_table;
 479 }
 480
 481 static void
 482 iter_remove_or_steal (RealIter *ri, gboolean notify)
 483 {
 484   GHashNode *prev;
 485   GHashNode *node;
 486   int position;
 487
 488   g_return_if_fail (ri != NULL);
 489 #ifndef G_DISABLE_ASSERT
 490   g_return_if_fail (ri->version == ri->hash_table->version);
 491 #endif
 492   g_return_if_fail (ri->node != NULL);
 493
 494   prev = ri->prev_node;
 495   node = ri->node;
 496   position = ri->position;
 497
 498   /* pre-advance the iterator since we will remove the node */
 499
 500   ri->node = ri->node->next;
 501   /* ri->prev_node is still the correct previous node */
 502
 503   while (ri->node == NULL)
 504     {
 505       ri->position++;
 506       if (ri->position >= ri->hash_table->size)
 507         break;
 508
 509       ri->prev_node = NULL;
 510       ri->node = ri->hash_table->nodes[ri->position];
 511     }
 512
 513   ri->pre_advanced = TRUE;
 514
 515   /* remove the node */
 516
 517   if (prev != NULL)
 518     prev->next = node->next;
 519   else
 520     ri->hash_table->nodes[position] = node->next;
 521
 522   if (notify)
 523     {
 524       if (ri->hash_table->key_destroy_func)
 525         ri->hash_table->key_destroy_func(node->key);
 526       if (ri->hash_table->value_destroy_func)
 527         ri->hash_table->value_destroy_func(node->value);
 528     }
 529
 530   g_slice_free (GHashNode, node);
 531
 532   ri->hash_table->nnodes--;
 533 }
 534
 535 /**
 536  * g_hash_table_iter_remove():
 537  * @iter: an initialized #GHashTableIter.
 538  *
 539  * Removes the key/value pair currently pointed to by the iterator
 540  * from its associated #GHashTable. Can only be called after
 541  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 542  * than once for the same key/value pair.
 543  *
 544  * If the #GHashTable was created using g_hash_table_new_full(), the
 545  * key and value are freed using the supplied destroy functions, otherwise
 546  * you have to make sure that any dynamically allocated values are freed
 547  * yourself.
 548  *
 549  * Since: 2.16
 550  **/
 551 void
 552 g_hash_table_iter_remove (GHashTableIter *iter)
 553 {
 554   iter_remove_or_steal ((RealIter *) iter, TRUE);
 555 }
 556
 557 /**
 558  * g_hash_table_iter_steal():
 559  * @iter: an initialized #GHashTableIter.
 560  *
 561  * Removes the key/value pair currently pointed to by the iterator
 562  * from its associated #GHashTable, without calling the key and value
 563  * destroy functions. Can only be called after
 564  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 565  * than once for the same key/value pair.
 566  *
 567  * Since: 2.16
 568  **/
 569 void
 570 g_hash_table_iter_steal (GHashTableIter *iter)
 571 {
 572   iter_remove_or_steal ((RealIter *) iter, FALSE);
 573 }
 574
 575
 576 /**
 577  * g_hash_table_ref:
 578  * @hash_table: a valid #GHashTable.
 579  *
 580  * Atomically increments the reference count of @hash_table by one.
 581  * This function is MT-safe and may be called from any thread.
 582  *
 583  * Return value: the passed in #GHashTable.
 584  *
 585  * Since: 2.10
 586  **/
 587 GHashTable*
 588 g_hash_table_ref (GHashTable *hash_table)
 589 {
 590   g_return_val_if_fail (hash_table != NULL, NULL);
 591   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 592
 593   g_atomic_int_add (&hash_table->ref_count, 1);
 594   return hash_table;
 595 }
 596
 597 /**
 598  * g_hash_table_unref:
 599  * @hash_table: a valid #GHashTable.
 600  *
 601  * Atomically decrements the reference count of @hash_table by one.
 602  * If the reference count drops to 0, all keys and values will be
 603  * destroyed, and all memory allocated by the hash table is released.
 604  * This function is MT-safe and may be called from any thread.
 605  *
 606  * Since: 2.10
 607  **/
 608 void
 609 g_hash_table_unref (GHashTable *hash_table)
 610 {
 611   g_return_if_fail (hash_table != NULL);
 612   g_return_if_fail (hash_table->ref_count > 0);
 613
 614   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 615     {
 616       g_hash_table_remove_all_nodes (hash_table, TRUE);
 617       g_free (hash_table->nodes);
 618       g_slice_free (GHashTable, hash_table);
 619     }
 620 }
 621
 622 /**
 623  * g_hash_table_destroy:
 624  * @hash_table: a #GHashTable.
 625  *
 626  * Destroys all keys and values in the #GHashTable and decrements its
 627  * reference count by 1. If keys and/or values are dynamically allocated,
 628  * you should either free them first or create the #GHashTable with destroy
 629  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 630  * functions you supplied will be called on all keys and values during the
 631  * destruction phase.
 632  **/
 633 void
 634 g_hash_table_destroy (GHashTable *hash_table)
 635 {
 636   g_return_if_fail (hash_table != NULL);
 637   g_return_if_fail (hash_table->ref_count > 0);
 638
 639   g_hash_table_remove_all (hash_table);
 640   g_hash_table_unref (hash_table);
 641 }
 642
 643 /**
 644  * g_hash_table_lookup:
 645  * @hash_table: a #GHashTable.
 646  * @key: the key to look up.
 647  *
 648  * Looks up a key in a #GHashTable. Note that this function cannot
 649  * distinguish between a key that is not present and one which is present
 650  * and has the value %NULL. If you need this distinction, use
 651  * g_hash_table_lookup_extended().
 652  *
 653  * Return value: the associated value, or %NULL if the key is not found.
 654  **/
 655 gpointer
 656 g_hash_table_lookup (GHashTable   *hash_table,
 657                      gconstpointer key)
 658 {
 659   GHashNode *node;
 660
 661   g_return_val_if_fail (hash_table != NULL, NULL);
 662
 663   node = *g_hash_table_lookup_node (hash_table, key, NULL);
 664
 665   return node ? node->value : NULL;
 666 }
 667
 668 /**
 669  * g_hash_table_lookup_extended:
 670  * @hash_table: a #GHashTable.
 671  * @lookup_key: the key to look up.
 672  * @orig_key: returns the original key.
 673  * @value: returns the value associated with the key.
 674  *
 675  * Looks up a key in the #GHashTable, returning the original key and the
 676  * associated value and a #gboolean which is %TRUE if the key was found. This
 677  * is useful if you need to free the memory allocated for the original key,
 678  * for example before calling g_hash_table_remove().
 679  *
 680  * Return value: %TRUE if the key was found in the #GHashTable.
 681  **/
 682 gboolean
 683 g_hash_table_lookup_extended (GHashTable    *hash_table,
 684                               gconstpointer  lookup_key,
 685                               gpointer      *orig_key,
 686                               gpointer      *value)
 687 {
 688   GHashNode *node;
 689
 690   g_return_val_if_fail (hash_table != NULL, FALSE);
 691
 692   node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL);
 693
 694   if (node == NULL)
 695     return FALSE;
 696
 697   if (orig_key)
 698     *orig_key = node->key;
 699
 700   if (value)
 701     *value = node->value;
 702
 703   return TRUE;
 704 }
 705
 706 /*
 707  * g_hash_table_insert_internal:
 708  * @hash_table: our #GHashTable
 709  * @key: the key to insert
 710  * @value: the value to insert
 711  * @keep_new_key: if %TRUE and this key already exists in the table
 712  *   then call the destroy notify function on the old key.  If %FALSE
 713  *   then call the destroy notify function on the new key.
 714  *
 715  * Implements the common logic for the g_hash_table_insert() and
 716  * g_hash_table_replace() functions.
 717  *
 718  * Do a lookup of @key.  If it is found, replace it with the new
 719  * @value (and perhaps the new @key).  If it is not found, create a
 720  * new node.
 721  */
 722 static void
 723 g_hash_table_insert_internal (GHashTable *hash_table,
 724                               gpointer    key,
 725                               gpointer    value,
 726                               gboolean    keep_new_key)
 727 {
 728   GHashNode **node_ptr, *node;
 729   guint key_hash;
 730
 731   g_return_if_fail (hash_table != NULL);
 732   g_return_if_fail (hash_table->ref_count > 0);
 733
 734   node_ptr = g_hash_table_lookup_node (hash_table, key, &key_hash);
 735
 736   if ((node = *node_ptr))
 737     {
 738       if (keep_new_key)
 739         {
 740           if (hash_table->key_destroy_func)
 741             hash_table->key_destroy_func (node->key);
 742           node->key = key;
 743         }
 744       else
 745         {
 746           if (hash_table->key_destroy_func)
 747             hash_table->key_destroy_func (key);
 748         }
 749
 750       if (hash_table->value_destroy_func)
 751         hash_table->value_destroy_func (node->value);
 752
 753       node->value = value;
 754     }
 755   else
 756     {
 757       node = g_slice_new (GHashNode);
 758
 759       node->key = key;
 760       node->value = value;
 761       node->key_hash = key_hash;
 762       node->next = NULL;
 763
 764       *node_ptr = node;
 765       hash_table->nnodes++;
 766       g_hash_table_maybe_resize (hash_table);
 767
 768 #ifndef G_DISABLE_ASSERT
 769       hash_table->version++;
 770 #endif
 771     }
 772 }
 773
 774 /**
 775  * g_hash_table_insert:
 776  * @hash_table: a #GHashTable.
 777  * @key: a key to insert.
 778  * @value: the value to associate with the key.
 779  *
 780  * Inserts a new key and value into a #GHashTable.
 781  *
 782  * If the key already exists in the #GHashTable its current value is replaced
 783  * with the new value. If you supplied a @value_destroy_func when creating the
 784  * #GHashTable, the old value is freed using that function. If you supplied
 785  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 786  * using that function.
 787  **/
 788 void
 789 g_hash_table_insert (GHashTable *hash_table,
 790                      gpointer    key,
 791                      gpointer    value)
 792 {
 793   g_hash_table_insert_internal (hash_table, key, value, FALSE);
 794 }
 795
 796 /**
 797  * g_hash_table_replace:
 798  * @hash_table: a #GHashTable.
 799  * @key: a key to insert.
 800  * @value: the value to associate with the key.
 801  *
 802  * Inserts a new key and value into a #GHashTable similar to
 803  * g_hash_table_insert(). The difference is that if the key already exists
 804  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 805  * @value_destroy_func when creating the #GHashTable, the old value is freed
 806  * using that function. If you supplied a @key_destroy_func when creating the
 807  * #GHashTable, the old key is freed using that function.
 808  **/
 809 void
 810 g_hash_table_replace (GHashTable *hash_table,
 811                       gpointer    key,
 812                       gpointer    value)
 813 {
 814   g_hash_table_insert_internal (hash_table, key, value, TRUE);
 815 }
 816
 817 /*
 818  * g_hash_table_remove_internal:
 819  * @hash_table: our #GHashTable
 820  * @key: the key to remove
 821  * @notify: %TRUE if the destroy notify handlers are to be called
 822  * Return value: %TRUE if a node was found and removed, else %FALSE
 823  *
 824  * Implements the common logic for the g_hash_table_remove() and
 825  * g_hash_table_steal() functions.
 826  *
 827  * Do a lookup of @key and remove it if it is found, calling the
 828  * destroy notify handlers only if @notify is %TRUE.
 829  */
 830 static gboolean
 831 g_hash_table_remove_internal (GHashTable    *hash_table,
 832                               gconstpointer  key,
 833                               gboolean       notify)
 834 {
 835   GHashNode **node_ptr;
 836
 837   g_return_val_if_fail (hash_table != NULL, FALSE);
 838
 839   node_ptr = g_hash_table_lookup_node (hash_table, key, NULL);
 840   if (*node_ptr == NULL)
 841     return FALSE;
 842
 843   g_hash_table_remove_node (hash_table, &node_ptr, notify);
 844   g_hash_table_maybe_resize (hash_table);
 845
 846 #ifndef G_DISABLE_ASSERT
 847   hash_table->version++;
 848 #endif
 849
 850   return TRUE;
 851 }
 852
 853 /**
 854  * g_hash_table_remove:
 855  * @hash_table: a #GHashTable.
 856  * @key: the key to remove.
 857  *
 858  * Removes a key and its associated value from a #GHashTable.
 859  *
 860  * If the #GHashTable was created using g_hash_table_new_full(), the
 861  * key and value are freed using the supplied destroy functions, otherwise
 862  * you have to make sure that any dynamically allocated values are freed
 863  * yourself.
 864  *
 865  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 866  **/
 867 gboolean
 868 g_hash_table_remove (GHashTable    *hash_table,
 869                      gconstpointer  key)
 870 {
 871   return g_hash_table_remove_internal (hash_table, key, TRUE);
 872 }
 873
 874 /**
 875  * g_hash_table_steal:
 876  * @hash_table: a #GHashTable.
 877  * @key: the key to remove.
 878  *
 879  * Removes a key and its associated value from a #GHashTable without
 880  * calling the key and value destroy functions.
 881  *
 882  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 883  **/
 884 gboolean
 885 g_hash_table_steal (GHashTable    *hash_table,
 886                     gconstpointer  key)
 887 {
 888   return g_hash_table_remove_internal (hash_table, key, FALSE);
 889 }
 890
 891 /**
 892  * g_hash_table_remove_all:
 893  * @hash_table: a #GHashTable
 894  *
 895  * Removes all keys and their associated values from a #GHashTable.
 896  *
 897  * If the #GHashTable was created using g_hash_table_new_full(), the keys
 898  * and values are freed using the supplied destroy functions, otherwise you
 899  * have to make sure that any dynamically allocated values are freed
 900  * yourself.
 901  *
 902  * Since: 2.12
 903  **/
 904 void
 905 g_hash_table_remove_all (GHashTable *hash_table)
 906 {
 907   g_return_if_fail (hash_table != NULL);
 908
 909 #ifndef G_DISABLE_ASSERT
 910   if (hash_table->nnodes != 0)
 911     hash_table->version++;
 912 #endif
 913
 914   g_hash_table_remove_all_nodes (hash_table, TRUE);
 915   g_hash_table_maybe_resize (hash_table);
 916 }
 917
 918 /**
 919  * g_hash_table_steal_all:
 920  * @hash_table: a #GHashTable.
 921  *
 922  * Removes all keys and their associated values from a #GHashTable
 923  * without calling the key and value destroy functions.
 924  *
 925  * Since: 2.12
 926  **/
 927 void
 928 g_hash_table_steal_all (GHashTable *hash_table)
 929 {
 930   g_return_if_fail (hash_table != NULL);
 931
 932 #ifndef G_DISABLE_ASSERT
 933   if (hash_table->nnodes != 0)
 934     hash_table->version++;
 935 #endif
 936
 937   g_hash_table_remove_all_nodes (hash_table, FALSE);
 938   g_hash_table_maybe_resize (hash_table);
 939 }
 940
 941 /*
 942  * g_hash_table_foreach_remove_or_steal:
 943  * @hash_table: our #GHashTable
 944  * @func: the user's callback function
 945  * @user_data: data for @func
 946  * @notify: %TRUE if the destroy notify handlers are to be called
 947  *
 948  * Implements the common logic for g_hash_table_foreach_remove() and
 949  * g_hash_table_foreach_steal().
 950  *
 951  * Iterates over every node in the table, calling @func with the key
 952  * and value of the node (and @user_data).  If @func returns %TRUE the
 953  * node is removed from the table.
 954  *
 955  * If @notify is true then the destroy notify handlers will be called
 956  * for each removed node.
 957  */
 958 static guint
 959 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 960                                       GHRFunc     func,
 961                                       gpointer    user_data,
 962                                       gboolean    notify)
 963 {
 964   GHashNode *node, **node_ptr;
 965   guint deleted = 0;
 966   gint i;
 967
 968   for (i = 0; i < hash_table->size; i++)
 969     for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;)
 970       if ((* func) (node->key, node->value, user_data))
 971         {
 972           g_hash_table_remove_node (hash_table, &node_ptr, notify);
 973           deleted++;
 974         }
 975       else
 976         node_ptr = &node->next;
 977
 978   g_hash_table_maybe_resize (hash_table);
 979
 980 #ifndef G_DISABLE_ASSERT
 981   if (deleted > 0)
 982     hash_table->version++;
 983 #endif
 984
 985   return deleted;
 986 }
 987
 988 /**
 989  * g_hash_table_foreach_remove:
 990  * @hash_table: a #GHashTable.
 991  * @func: the function to call for each key/value pair.
 992  * @user_data: user data to pass to the function.
 993  *
 994  * Calls the given function for each key/value pair in the #GHashTable.
 995  * If the function returns %TRUE, then the key/value pair is removed from the
 996  * #GHashTable. If you supplied key or value destroy functions when creating
 997  * the #GHashTable, they are used to free the memory allocated for the removed
 998  * keys and values.
 999  *
1000  * See #GHashTableIterator for an alternative way to loop over the
1001  * key/value pairs in the hash table.
1002  *
1003  * Return value: the number of key/value pairs removed.
1004  **/
1005 guint
1006 g_hash_table_foreach_remove (GHashTable *hash_table,
1007                              GHRFunc     func,
1008                              gpointer    user_data)
1009 {
1010   g_return_val_if_fail (hash_table != NULL, 0);
1011   g_return_val_if_fail (func != NULL, 0);
1012
1013   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1014 }
1015
1016 /**
1017  * g_hash_table_foreach_steal:
1018  * @hash_table: a #GHashTable.
1019  * @func: the function to call for each key/value pair.
1020  * @user_data: user data to pass to the function.
1021  *
1022  * Calls the given function for each key/value pair in the #GHashTable.
1023  * If the function returns %TRUE, then the key/value pair is removed from the
1024  * #GHashTable, but no key or value destroy functions are called.
1025  *
1026  * See #GHashTableIterator for an alternative way to loop over the
1027  * key/value pairs in the hash table.
1028  *
1029  * Return value: the number of key/value pairs removed.
1030  **/
1031 guint
1032 g_hash_table_foreach_steal (GHashTable *hash_table,
1033                             GHRFunc     func,
1034                             gpointer    user_data)
1035 {
1036   g_return_val_if_fail (hash_table != NULL, 0);
1037   g_return_val_if_fail (func != NULL, 0);
1038
1039   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1040 }
1041
1042 /**
1043  * g_hash_table_foreach:
1044  * @hash_table: a #GHashTable.
1045  * @func: the function to call for each key/value pair.
1046  * @user_data: user data to pass to the function.
1047  *
1048  * Calls the given function for each of the key/value pairs in the
1049  * #GHashTable.  The function is passed the key and value of each
1050  * pair, and the given @user_data parameter.  The hash table may not
1051  * be modified while iterating over it (you can't add/remove
1052  * items). To remove all items matching a predicate, use
1053  * g_hash_table_foreach_remove().
1054  *
1055  * See g_hash_table_find() for performance caveats for linear
1056  * order searches in contrast to g_hash_table_lookup().
1057  **/
1058 void
1059 g_hash_table_foreach (GHashTable *hash_table,
1060                       GHFunc      func,
1061                       gpointer    user_data)
1062 {
1063   GHashNode *node;
1064   gint i;
1065
1066   g_return_if_fail (hash_table != NULL);
1067   g_return_if_fail (func != NULL);
1068
1069   for (i = 0; i < hash_table->size; i++)
1070     for (node = hash_table->nodes[i]; node; node = node->next)
1071       (* func) (node->key, node->value, user_data);
1072 }
1073
1074 /**
1075  * g_hash_table_find:
1076  * @hash_table: a #GHashTable.
1077  * @predicate:  function to test the key/value pairs for a certain property.
1078  * @user_data:  user data to pass to the function.
1079  *
1080  * Calls the given function for key/value pairs in the #GHashTable until
1081  * @predicate returns %TRUE.  The function is passed the key and value of
1082  * each pair, and the given @user_data parameter. The hash table may not
1083  * be modified while iterating over it (you can't add/remove items).
1084  *
1085  * Note, that hash tables are really only optimized for forward lookups,
1086  * i.e. g_hash_table_lookup().
1087  * So code that frequently issues g_hash_table_find() or
1088  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1089  * hash table) should probably be reworked to use additional or different
1090  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1091  * operation issued for all n values in a hash table ends up needing O(n*n)
1092  * operations).
1093  *
1094  * Return value: The value of the first key/value pair is returned, for which
1095  * func evaluates to %TRUE. If no pair with the requested property is found,
1096  * %NULL is returned.
1097  *
1098  * Since: 2.4
1099  **/
1100 gpointer
1101 g_hash_table_find (GHashTable      *hash_table,
1102                    GHRFunc          predicate,
1103                    gpointer         user_data)
1104 {
1105   GHashNode *node;
1106   gint i;
1107
1108   g_return_val_if_fail (hash_table != NULL, NULL);
1109   g_return_val_if_fail (predicate != NULL, NULL);
1110
1111   for (i = 0; i < hash_table->size; i++)
1112     for (node = hash_table->nodes[i]; node; node = node->next)
1113       if (predicate (node->key, node->value, user_data))
1114         return node->value;
1115   return NULL;
1116 }
1117
1118 /**
1119  * g_hash_table_size:
1120  * @hash_table: a #GHashTable.
1121  *
1122  * Returns the number of elements contained in the #GHashTable.
1123  *
1124  * Return value: the number of key/value pairs in the #GHashTable.
1125  **/
1126 guint
1127 g_hash_table_size (GHashTable *hash_table)
1128 {
1129   g_return_val_if_fail (hash_table != NULL, 0);
1130
1131   return hash_table->nnodes;
1132 }
1133
1134 /**
1135  * g_hash_table_get_keys:
1136  * @hash_table: a #GHashTable
1137  *
1138  * Retrieves every key inside @hash_table. The returned data is valid
1139  * until @hash_table is modified.
1140  *
1141  * Return value: a #GList containing all the keys inside the hash
1142  *   table. The content of the list is owned by the hash table and
1143  *   should not be modified or freed. Use g_list_free() when done
1144  *   using the list.
1145  *
1146  * Since: 2.14
1147  */
1148 GList *
1149 g_hash_table_get_keys (GHashTable *hash_table)
1150 {
1151   GHashNode *node;
1152   gint i;
1153   GList *retval;
1154
1155   g_return_val_if_fail (hash_table != NULL, NULL);
1156
1157   retval = NULL;
1158   for (i = 0; i < hash_table->size; i++)
1159     for (node = hash_table->nodes[i]; node; node = node->next)
1160       retval = g_list_prepend (retval, node->key);
1161
1162   return retval;
1163 }
1164
1165 /**
1166  * g_hash_table_get_values:
1167  * @hash_table: a #GHashTable
1168  *
1169  * Retrieves every value inside @hash_table. The returned data is
1170  * valid until @hash_table is modified.
1171  *
1172  * Return value: a #GList containing all the values inside the hash
1173  *   table. The content of the list is owned by the hash table and
1174  *   should not be modified or freed. Use g_list_free() when done
1175  *   using the list.
1176  *
1177  * Since: 2.14
1178  */
1179 GList *
1180 g_hash_table_get_values (GHashTable *hash_table)
1181 {
1182   GHashNode *node;
1183   gint i;
1184   GList *retval;
1185
1186   g_return_val_if_fail (hash_table != NULL, NULL);
1187
1188   retval = NULL;
1189   for (i = 0; i < hash_table->size; i++)
1190     for (node = hash_table->nodes[i]; node; node = node->next)
1191       retval = g_list_prepend (retval, node->value);
1192
1193   return retval;
1194 }
1195
1196 #define __G_HASH_C__
1197 #include "galiasdef.c"