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