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 #ifndef G_DISABLE_ASSERT
 535   ri->version++;
 536   ri->hash_table->version++;
 537 #endif
 538 }
 539
 540 /**
 541  * g_hash_table_iter_remove():
 542  * @iter: an initialized #GHashTableIter.
 543  *
 544  * Removes the key/value pair currently pointed to by the iterator
 545  * from its associated #GHashTable. Can only be called after
 546  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 547  * than once for the same key/value pair.
 548  *
 549  * If the #GHashTable was created using g_hash_table_new_full(), the
 550  * key and value are freed using the supplied destroy functions, otherwise
 551  * you have to make sure that any dynamically allocated values are freed
 552  * yourself.
 553  *
 554  * Since: 2.16
 555  **/
 556 void
 557 g_hash_table_iter_remove (GHashTableIter *iter)
 558 {
 559   iter_remove_or_steal ((RealIter *) iter, TRUE);
 560 }
 561
 562 /**
 563  * g_hash_table_iter_steal():
 564  * @iter: an initialized #GHashTableIter.
 565  *
 566  * Removes the key/value pair currently pointed to by the iterator
 567  * from its associated #GHashTable, without calling the key and value
 568  * destroy functions. Can only be called after
 569  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 570  * than once for the same key/value pair.
 571  *
 572  * Since: 2.16
 573  **/
 574 void
 575 g_hash_table_iter_steal (GHashTableIter *iter)
 576 {
 577   iter_remove_or_steal ((RealIter *) iter, FALSE);
 578 }
 579
 580
 581 /**
 582  * g_hash_table_ref:
 583  * @hash_table: a valid #GHashTable.
 584  *
 585  * Atomically increments the reference count of @hash_table by one.
 586  * This function is MT-safe and may be called from any thread.
 587  *
 588  * Return value: the passed in #GHashTable.
 589  *
 590  * Since: 2.10
 591  **/
 592 GHashTable*
 593 g_hash_table_ref (GHashTable *hash_table)
 594 {
 595   g_return_val_if_fail (hash_table != NULL, NULL);
 596   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 597
 598   g_atomic_int_add (&hash_table->ref_count, 1);
 599   return hash_table;
 600 }
 601
 602 /**
 603  * g_hash_table_unref:
 604  * @hash_table: a valid #GHashTable.
 605  *
 606  * Atomically decrements the reference count of @hash_table by one.
 607  * If the reference count drops to 0, all keys and values will be
 608  * destroyed, and all memory allocated by the hash table is released.
 609  * This function is MT-safe and may be called from any thread.
 610  *
 611  * Since: 2.10
 612  **/
 613 void
 614 g_hash_table_unref (GHashTable *hash_table)
 615 {
 616   g_return_if_fail (hash_table != NULL);
 617   g_return_if_fail (hash_table->ref_count > 0);
 618
 619   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 620     {
 621       g_hash_table_remove_all_nodes (hash_table, TRUE);
 622       g_free (hash_table->nodes);
 623       g_slice_free (GHashTable, hash_table);
 624     }
 625 }
 626
 627 /**
 628  * g_hash_table_destroy:
 629  * @hash_table: a #GHashTable.
 630  *
 631  * Destroys all keys and values in the #GHashTable and decrements its
 632  * reference count by 1. If keys and/or values are dynamically allocated,
 633  * you should either free them first or create the #GHashTable with destroy
 634  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 635  * functions you supplied will be called on all keys and values during the
 636  * destruction phase.
 637  **/
 638 void
 639 g_hash_table_destroy (GHashTable *hash_table)
 640 {
 641   g_return_if_fail (hash_table != NULL);
 642   g_return_if_fail (hash_table->ref_count > 0);
 643
 644   g_hash_table_remove_all (hash_table);
 645   g_hash_table_unref (hash_table);
 646 }
 647
 648 /**
 649  * g_hash_table_lookup:
 650  * @hash_table: a #GHashTable.
 651  * @key: the key to look up.
 652  *
 653  * Looks up a key in a #GHashTable. Note that this function cannot
 654  * distinguish between a key that is not present and one which is present
 655  * and has the value %NULL. If you need this distinction, use
 656  * g_hash_table_lookup_extended().
 657  *
 658  * Return value: the associated value, or %NULL if the key is not found.
 659  **/
 660 gpointer
 661 g_hash_table_lookup (GHashTable   *hash_table,
 662                      gconstpointer key)
 663 {
 664   GHashNode *node;
 665
 666   g_return_val_if_fail (hash_table != NULL, NULL);
 667
 668   node = *g_hash_table_lookup_node (hash_table, key, NULL);
 669
 670   return node ? node->value : NULL;
 671 }
 672
 673 /**
 674  * g_hash_table_lookup_extended:
 675  * @hash_table: a #GHashTable.
 676  * @lookup_key: the key to look up.
 677  * @orig_key: returns the original key.
 678  * @value: returns the value associated with the key.
 679  *
 680  * Looks up a key in the #GHashTable, returning the original key and the
 681  * associated value and a #gboolean which is %TRUE if the key was found. This
 682  * is useful if you need to free the memory allocated for the original key,
 683  * for example before calling g_hash_table_remove().
 684  *
 685  * Return value: %TRUE if the key was found in the #GHashTable.
 686  **/
 687 gboolean
 688 g_hash_table_lookup_extended (GHashTable    *hash_table,
 689                               gconstpointer  lookup_key,
 690                               gpointer      *orig_key,
 691                               gpointer      *value)
 692 {
 693   GHashNode *node;
 694
 695   g_return_val_if_fail (hash_table != NULL, FALSE);
 696
 697   node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL);
 698
 699   if (node == NULL)
 700     return FALSE;
 701
 702   if (orig_key)
 703     *orig_key = node->key;
 704
 705   if (value)
 706     *value = node->value;
 707
 708   return TRUE;
 709 }
 710
 711 /*
 712  * g_hash_table_insert_internal:
 713  * @hash_table: our #GHashTable
 714  * @key: the key to insert
 715  * @value: the value to insert
 716  * @keep_new_key: if %TRUE and this key already exists in the table
 717  *   then call the destroy notify function on the old key.  If %FALSE
 718  *   then call the destroy notify function on the new key.
 719  *
 720  * Implements the common logic for the g_hash_table_insert() and
 721  * g_hash_table_replace() functions.
 722  *
 723  * Do a lookup of @key.  If it is found, replace it with the new
 724  * @value (and perhaps the new @key).  If it is not found, create a
 725  * new node.
 726  */
 727 static void
 728 g_hash_table_insert_internal (GHashTable *hash_table,
 729                               gpointer    key,
 730                               gpointer    value,
 731                               gboolean    keep_new_key)
 732 {
 733   GHashNode **node_ptr, *node;
 734   guint key_hash;
 735
 736   g_return_if_fail (hash_table != NULL);
 737   g_return_if_fail (hash_table->ref_count > 0);
 738
 739   node_ptr = g_hash_table_lookup_node (hash_table, key, &key_hash);
 740
 741   if ((node = *node_ptr))
 742     {
 743       if (keep_new_key)
 744         {
 745           if (hash_table->key_destroy_func)
 746             hash_table->key_destroy_func (node->key);
 747           node->key = key;
 748         }
 749       else
 750         {
 751           if (hash_table->key_destroy_func)
 752             hash_table->key_destroy_func (key);
 753         }
 754
 755       if (hash_table->value_destroy_func)
 756         hash_table->value_destroy_func (node->value);
 757
 758       node->value = value;
 759     }
 760   else
 761     {
 762       node = g_slice_new (GHashNode);
 763
 764       node->key = key;
 765       node->value = value;
 766       node->key_hash = key_hash;
 767       node->next = NULL;
 768
 769       *node_ptr = node;
 770       hash_table->nnodes++;
 771       g_hash_table_maybe_resize (hash_table);
 772
 773 #ifndef G_DISABLE_ASSERT
 774       hash_table->version++;
 775 #endif
 776     }
 777 }
 778
 779 /**
 780  * g_hash_table_insert:
 781  * @hash_table: a #GHashTable.
 782  * @key: a key to insert.
 783  * @value: the value to associate with the key.
 784  *
 785  * Inserts a new key and value into a #GHashTable.
 786  *
 787  * If the key already exists in the #GHashTable its current value is replaced
 788  * with the new value. If you supplied a @value_destroy_func when creating the
 789  * #GHashTable, the old value is freed using that function. If you supplied
 790  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 791  * using that function.
 792  **/
 793 void
 794 g_hash_table_insert (GHashTable *hash_table,
 795                      gpointer    key,
 796                      gpointer    value)
 797 {
 798   g_hash_table_insert_internal (hash_table, key, value, FALSE);
 799 }
 800
 801 /**
 802  * g_hash_table_replace:
 803  * @hash_table: a #GHashTable.
 804  * @key: a key to insert.
 805  * @value: the value to associate with the key.
 806  *
 807  * Inserts a new key and value into a #GHashTable similar to
 808  * g_hash_table_insert(). The difference is that if the key already exists
 809  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 810  * @value_destroy_func when creating the #GHashTable, the old value is freed
 811  * using that function. If you supplied a @key_destroy_func when creating the
 812  * #GHashTable, the old key is freed using that function.
 813  **/
 814 void
 815 g_hash_table_replace (GHashTable *hash_table,
 816                       gpointer    key,
 817                       gpointer    value)
 818 {
 819   g_hash_table_insert_internal (hash_table, key, value, TRUE);
 820 }
 821
 822 /*
 823  * g_hash_table_remove_internal:
 824  * @hash_table: our #GHashTable
 825  * @key: the key to remove
 826  * @notify: %TRUE if the destroy notify handlers are to be called
 827  * Return value: %TRUE if a node was found and removed, else %FALSE
 828  *
 829  * Implements the common logic for the g_hash_table_remove() and
 830  * g_hash_table_steal() functions.
 831  *
 832  * Do a lookup of @key and remove it if it is found, calling the
 833  * destroy notify handlers only if @notify is %TRUE.
 834  */
 835 static gboolean
 836 g_hash_table_remove_internal (GHashTable    *hash_table,
 837                               gconstpointer  key,
 838                               gboolean       notify)
 839 {
 840   GHashNode **node_ptr;
 841
 842   g_return_val_if_fail (hash_table != NULL, FALSE);
 843
 844   node_ptr = g_hash_table_lookup_node (hash_table, key, NULL);
 845   if (*node_ptr == NULL)
 846     return FALSE;
 847
 848   g_hash_table_remove_node (hash_table, &node_ptr, notify);
 849   g_hash_table_maybe_resize (hash_table);
 850
 851 #ifndef G_DISABLE_ASSERT
 852   hash_table->version++;
 853 #endif
 854
 855   return TRUE;
 856 }
 857
 858 /**
 859  * g_hash_table_remove:
 860  * @hash_table: a #GHashTable.
 861  * @key: the key to remove.
 862  *
 863  * Removes a key and its associated value from a #GHashTable.
 864  *
 865  * If the #GHashTable was created using g_hash_table_new_full(), the
 866  * key and value are freed using the supplied destroy functions, otherwise
 867  * you have to make sure that any dynamically allocated values are freed
 868  * yourself.
 869  *
 870  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 871  **/
 872 gboolean
 873 g_hash_table_remove (GHashTable    *hash_table,
 874                      gconstpointer  key)
 875 {
 876   return g_hash_table_remove_internal (hash_table, key, TRUE);
 877 }
 878
 879 /**
 880  * g_hash_table_steal:
 881  * @hash_table: a #GHashTable.
 882  * @key: the key to remove.
 883  *
 884  * Removes a key and its associated value from a #GHashTable without
 885  * calling the key and value destroy functions.
 886  *
 887  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 888  **/
 889 gboolean
 890 g_hash_table_steal (GHashTable    *hash_table,
 891                     gconstpointer  key)
 892 {
 893   return g_hash_table_remove_internal (hash_table, key, FALSE);
 894 }
 895
 896 /**
 897  * g_hash_table_remove_all:
 898  * @hash_table: a #GHashTable
 899  *
 900  * Removes all keys and their associated values from a #GHashTable.
 901  *
 902  * If the #GHashTable was created using g_hash_table_new_full(), the keys
 903  * and values are freed using the supplied destroy functions, otherwise you
 904  * have to make sure that any dynamically allocated values are freed
 905  * yourself.
 906  *
 907  * Since: 2.12
 908  **/
 909 void
 910 g_hash_table_remove_all (GHashTable *hash_table)
 911 {
 912   g_return_if_fail (hash_table != NULL);
 913
 914 #ifndef G_DISABLE_ASSERT
 915   if (hash_table->nnodes != 0)
 916     hash_table->version++;
 917 #endif
 918
 919   g_hash_table_remove_all_nodes (hash_table, TRUE);
 920   g_hash_table_maybe_resize (hash_table);
 921 }
 922
 923 /**
 924  * g_hash_table_steal_all:
 925  * @hash_table: a #GHashTable.
 926  *
 927  * Removes all keys and their associated values from a #GHashTable
 928  * without calling the key and value destroy functions.
 929  *
 930  * Since: 2.12
 931  **/
 932 void
 933 g_hash_table_steal_all (GHashTable *hash_table)
 934 {
 935   g_return_if_fail (hash_table != NULL);
 936
 937 #ifndef G_DISABLE_ASSERT
 938   if (hash_table->nnodes != 0)
 939     hash_table->version++;
 940 #endif
 941
 942   g_hash_table_remove_all_nodes (hash_table, FALSE);
 943   g_hash_table_maybe_resize (hash_table);
 944 }
 945
 946 /*
 947  * g_hash_table_foreach_remove_or_steal:
 948  * @hash_table: our #GHashTable
 949  * @func: the user's callback function
 950  * @user_data: data for @func
 951  * @notify: %TRUE if the destroy notify handlers are to be called
 952  *
 953  * Implements the common logic for g_hash_table_foreach_remove() and
 954  * g_hash_table_foreach_steal().
 955  *
 956  * Iterates over every node in the table, calling @func with the key
 957  * and value of the node (and @user_data).  If @func returns %TRUE the
 958  * node is removed from the table.
 959  *
 960  * If @notify is true then the destroy notify handlers will be called
 961  * for each removed node.
 962  */
 963 static guint
 964 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 965                                       GHRFunc     func,
 966                                       gpointer    user_data,
 967                                       gboolean    notify)
 968 {
 969   GHashNode *node, **node_ptr;
 970   guint deleted = 0;
 971   gint i;
 972
 973   for (i = 0; i < hash_table->size; i++)
 974     for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;)
 975       if ((* func) (node->key, node->value, user_data))
 976         {
 977           g_hash_table_remove_node (hash_table, &node_ptr, notify);
 978           deleted++;
 979         }
 980       else
 981         node_ptr = &node->next;
 982
 983   g_hash_table_maybe_resize (hash_table);
 984
 985 #ifndef G_DISABLE_ASSERT
 986   if (deleted > 0)
 987     hash_table->version++;
 988 #endif
 989
 990   return deleted;
 991 }
 992
 993 /**
 994  * g_hash_table_foreach_remove:
 995  * @hash_table: a #GHashTable.
 996  * @func: the function to call for each key/value pair.
 997  * @user_data: user data to pass to the function.
 998  *
 999  * Calls the given function for each key/value pair in the #GHashTable.
1000  * If the function returns %TRUE, then the key/value pair is removed from the
1001  * #GHashTable. If you supplied key or value destroy functions when creating
1002  * the #GHashTable, they are used to free the memory allocated for the removed
1003  * keys and values.
1004  *
1005  * See #GHashTableIterator for an alternative way to loop over the
1006  * key/value pairs in the hash table.
1007  *
1008  * Return value: the number of key/value pairs removed.
1009  **/
1010 guint
1011 g_hash_table_foreach_remove (GHashTable *hash_table,
1012                              GHRFunc     func,
1013                              gpointer    user_data)
1014 {
1015   g_return_val_if_fail (hash_table != NULL, 0);
1016   g_return_val_if_fail (func != NULL, 0);
1017
1018   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1019 }
1020
1021 /**
1022  * g_hash_table_foreach_steal:
1023  * @hash_table: a #GHashTable.
1024  * @func: the function to call for each key/value pair.
1025  * @user_data: user data to pass to the function.
1026  *
1027  * Calls the given function for each key/value pair in the #GHashTable.
1028  * If the function returns %TRUE, then the key/value pair is removed from the
1029  * #GHashTable, but no key or value destroy functions are called.
1030  *
1031  * See #GHashTableIterator for an alternative way to loop over the
1032  * key/value pairs in the hash table.
1033  *
1034  * Return value: the number of key/value pairs removed.
1035  **/
1036 guint
1037 g_hash_table_foreach_steal (GHashTable *hash_table,
1038                             GHRFunc     func,
1039                             gpointer    user_data)
1040 {
1041   g_return_val_if_fail (hash_table != NULL, 0);
1042   g_return_val_if_fail (func != NULL, 0);
1043
1044   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1045 }
1046
1047 /**
1048  * g_hash_table_foreach:
1049  * @hash_table: a #GHashTable.
1050  * @func: the function to call for each key/value pair.
1051  * @user_data: user data to pass to the function.
1052  *
1053  * Calls the given function for each of the key/value pairs in the
1054  * #GHashTable.  The function is passed the key and value of each
1055  * pair, and the given @user_data parameter.  The hash table may not
1056  * be modified while iterating over it (you can't add/remove
1057  * items). To remove all items matching a predicate, use
1058  * g_hash_table_foreach_remove().
1059  *
1060  * See g_hash_table_find() for performance caveats for linear
1061  * order searches in contrast to g_hash_table_lookup().
1062  **/
1063 void
1064 g_hash_table_foreach (GHashTable *hash_table,
1065                       GHFunc      func,
1066                       gpointer    user_data)
1067 {
1068   GHashNode *node;
1069   gint i;
1070
1071   g_return_if_fail (hash_table != NULL);
1072   g_return_if_fail (func != NULL);
1073
1074   for (i = 0; i < hash_table->size; i++)
1075     for (node = hash_table->nodes[i]; node; node = node->next)
1076       (* func) (node->key, node->value, user_data);
1077 }
1078
1079 /**
1080  * g_hash_table_find:
1081  * @hash_table: a #GHashTable.
1082  * @predicate:  function to test the key/value pairs for a certain property.
1083  * @user_data:  user data to pass to the function.
1084  *
1085  * Calls the given function for key/value pairs in the #GHashTable until
1086  * @predicate returns %TRUE.  The function is passed the key and value of
1087  * each pair, and the given @user_data parameter. The hash table may not
1088  * be modified while iterating over it (you can't add/remove items).
1089  *
1090  * Note, that hash tables are really only optimized for forward lookups,
1091  * i.e. g_hash_table_lookup().
1092  * So code that frequently issues g_hash_table_find() or
1093  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1094  * hash table) should probably be reworked to use additional or different
1095  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1096  * operation issued for all n values in a hash table ends up needing O(n*n)
1097  * operations).
1098  *
1099  * Return value: The value of the first key/value pair is returned, for which
1100  * func evaluates to %TRUE. If no pair with the requested property is found,
1101  * %NULL is returned.
1102  *
1103  * Since: 2.4
1104  **/
1105 gpointer
1106 g_hash_table_find (GHashTable      *hash_table,
1107                    GHRFunc          predicate,
1108                    gpointer         user_data)
1109 {
1110   GHashNode *node;
1111   gint i;
1112
1113   g_return_val_if_fail (hash_table != NULL, NULL);
1114   g_return_val_if_fail (predicate != NULL, NULL);
1115
1116   for (i = 0; i < hash_table->size; i++)
1117     for (node = hash_table->nodes[i]; node; node = node->next)
1118       if (predicate (node->key, node->value, user_data))
1119         return node->value;
1120   return NULL;
1121 }
1122
1123 /**
1124  * g_hash_table_size:
1125  * @hash_table: a #GHashTable.
1126  *
1127  * Returns the number of elements contained in the #GHashTable.
1128  *
1129  * Return value: the number of key/value pairs in the #GHashTable.
1130  **/
1131 guint
1132 g_hash_table_size (GHashTable *hash_table)
1133 {
1134   g_return_val_if_fail (hash_table != NULL, 0);
1135
1136   return hash_table->nnodes;
1137 }
1138
1139 /**
1140  * g_hash_table_get_keys:
1141  * @hash_table: a #GHashTable
1142  *
1143  * Retrieves every key inside @hash_table. The returned data is valid
1144  * until @hash_table is modified.
1145  *
1146  * Return value: a #GList containing all the keys inside the hash
1147  *   table. The content of the list is owned by the hash table and
1148  *   should not be modified or freed. Use g_list_free() when done
1149  *   using the list.
1150  *
1151  * Since: 2.14
1152  */
1153 GList *
1154 g_hash_table_get_keys (GHashTable *hash_table)
1155 {
1156   GHashNode *node;
1157   gint i;
1158   GList *retval;
1159
1160   g_return_val_if_fail (hash_table != NULL, NULL);
1161
1162   retval = NULL;
1163   for (i = 0; i < hash_table->size; i++)
1164     for (node = hash_table->nodes[i]; node; node = node->next)
1165       retval = g_list_prepend (retval, node->key);
1166
1167   return retval;
1168 }
1169
1170 /**
1171  * g_hash_table_get_values:
1172  * @hash_table: a #GHashTable
1173  *
1174  * Retrieves every value inside @hash_table. The returned data is
1175  * valid until @hash_table is modified.
1176  *
1177  * Return value: a #GList containing all the values inside the hash
1178  *   table. The content of the list is owned by the hash table and
1179  *   should not be modified or freed. Use g_list_free() when done
1180  *   using the list.
1181  *
1182  * Since: 2.14
1183  */
1184 GList *
1185 g_hash_table_get_values (GHashTable *hash_table)
1186 {
1187   GHashNode *node;
1188   gint i;
1189   GList *retval;
1190
1191   g_return_val_if_fail (hash_table != NULL, NULL);
1192
1193   retval = NULL;
1194   for (i = 0; i < hash_table->size; i++)
1195     for (node = hash_table->nodes[i]; node; node = node->next)
1196       retval = g_list_prepend (retval, node->value);
1197
1198   return retval;
1199 }
1200
1201 #define __G_HASH_C__
1202 #include "galiasdef.c"