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 <string.h>  /* memset */
  34
  35 #include "glib.h"
  36
  37 /**
  38  * SECTION: hash_tables
  39  * @title: Hash Tables
  40  * @short_description: associations between keys and values so that
  41  *                     given a key the value can be found quickly
  42  *
  43  * A #GHashTable provides associations between keys and values which is
  44  * optimized so that given a key, the associated value can be found
  45  * very quickly.
  46  *
  47  * Note that neither keys nor values are copied when inserted into the
  48  * #GHashTable, so they must exist for the lifetime of the #GHashTable.
  49  * This means that the use of static strings is OK, but temporary
  50  * strings (i.e. those created in buffers and those returned by GTK+
  51  * widgets) should be copied with g_strdup() before being inserted.
  52  *
  53  * If keys or values are dynamically allocated, you must be careful to
  54  * ensure that they are freed when they are removed from the
  55  * #GHashTable, and also when they are overwritten by new insertions
  56  * into the #GHashTable. It is also not advisable to mix static strings
  57  * and dynamically-allocated strings in a #GHashTable, because it then
  58  * becomes difficult to determine whether the string should be freed.
  59  *
  60  * To create a #GHashTable, use g_hash_table_new().
  61  *
  62  * To insert a key and value into a #GHashTable, use
  63  * g_hash_table_insert().
  64  *
  65  * To lookup a value corresponding to a given key, use
  66  * g_hash_table_lookup() and g_hash_table_lookup_extended().
  67  *
  68  * To remove a key and value, use g_hash_table_remove().
  69  *
  70  * To call a function for each key and value pair use
  71  * g_hash_table_foreach() or use a iterator to iterate over the
  72  * key/value pairs in the hash table, see #GHashTableIter.
  73  *
  74  * To destroy a #GHashTable use g_hash_table_destroy().
  75  **/
  76
  77 /**
  78  * GHashTable:
  79  *
  80  * The #GHashTable struct is an opaque data structure to represent a
  81  * <link linkend="glib-Hash-Tables">Hash Table</link>. It should only be
  82  * accessed via the following functions.
  83  **/
  84
  85 /**
  86  * GHashFunc:
  87  * @key: a key.
  88  * @Returns: the hash value corresponding to the key.
  89  *
  90  * Specifies the type of the hash function which is passed to
  91  * g_hash_table_new() when a #GHashTable is created.
  92  *
  93  * The function is passed a key and should return a #guint hash value.
  94  * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
  95  * hash functions which can be used when the key is a #gpointer, #gint,
  96  * and #gchar* respectively.
  97  *
  98  * <!-- FIXME: Need more here. --> The hash values should be evenly
  99  * distributed over a fairly large range? The modulus is taken with the
 100  * hash table size (a prime number) to find the 'bucket' to place each
 101  * key into. The function should also be very fast, since it is called
 102  * for each key lookup.
 103  **/
 104
 105 /**
 106  * GHFunc:
 107  * @key: a key.
 108  * @value: the value corresponding to the key.
 109  * @user_data: user data passed to g_hash_table_foreach().
 110  *
 111  * Specifies the type of the function passed to g_hash_table_foreach().
 112  * It is called with each key/value pair, together with the @user_data
 113  * parameter which is passed to g_hash_table_foreach().
 114  **/
 115
 116 /**
 117  * GHRFunc:
 118  * @key: a key.
 119  * @value: the value associated with the key.
 120  * @user_data: user data passed to g_hash_table_remove().
 121  * @Returns: %TRUE if the key/value pair should be removed from the
 122  *           #GHashTable.
 123  *
 124  * Specifies the type of the function passed to
 125  * g_hash_table_foreach_remove(). It is called with each key/value
 126  * pair, together with the @user_data parameter passed to
 127  * g_hash_table_foreach_remove(). It should return %TRUE if the
 128  * key/value pair should be removed from the #GHashTable.
 129  **/
 130
 131 /**
 132  * GEqualFunc:
 133  * @a: a value.
 134  * @b: a value to compare with.
 135  * @Returns: %TRUE if @a = @b; %FALSE otherwise.
 136  *
 137  * Specifies the type of a function used to test two values for
 138  * equality. The function should return %TRUE if both values are equal
 139  * and %FALSE otherwise.
 140  **/
 141
 142 /**
 143  * GHashTableIter:
 144  *
 145  * A GHashTableIter structure represents an iterator that can be used
 146  * to iterate over the elements of a #GHashTable. GHashTableIter
 147  * structures are typically allocated on the stack and then initialized
 148  * with g_hash_table_iter_init().
 149  **/
 150
 151 #define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */
 152
 153 typedef struct _GHashNode      GHashNode;
 154
 155 struct _GHashNode
 156 {
 157   gpointer   key;
 158   gpointer   value;
 159
 160   /* If key_hash == 0, node is not in use
 161    * If key_hash == 1, node is a tombstone
 162    * If key_hash >= 2, node contains data */
 163   guint      key_hash;
 164 };
 165
 166 struct _GHashTable
 167 {
 168   gint             size;
 169   gint             mod;
 170   guint            mask;
 171   gint             nnodes;
 172   gint             noccupied;  /* nnodes + tombstones */
 173   GHashNode       *nodes;
 174   GHashFunc        hash_func;
 175   GEqualFunc       key_equal_func;
 176   volatile gint    ref_count;
 177 #ifndef G_DISABLE_ASSERT
 178   /*
 179    * Tracks the structure of the hash table, not its contents: is only
 180    * incremented when a node is added or removed (is not incremented
 181    * when the key or data of a node is modified).
 182    */
 183   int              version;
 184 #endif
 185   GDestroyNotify   key_destroy_func;
 186   GDestroyNotify   value_destroy_func;
 187 };
 188
 189 typedef struct
 190 {
 191   GHashTable  *hash_table;
 192   gpointer     dummy1;
 193   gpointer     dummy2;
 194   int          position;
 195   gboolean     dummy3;
 196   int          version;
 197 } RealIter;
 198
 199 /* Each table size has an associated prime modulo (the first prime
 200  * lower than the table size) used to find the initial bucket. Probing
 201  * then works modulo 2^n. The prime modulo is necessary to get a
 202  * good distribution with poor hash functions. */
 203 static const gint prime_mod [] =
 204 {
 205   1,          /* For 1 << 0 */
 206   2,
 207   3,
 208   7,
 209   13,
 210   31,
 211   61,
 212   127,
 213   251,
 214   509,
 215   1021,
 216   2039,
 217   4093,
 218   8191,
 219   16381,
 220   32749,
 221   65521,      /* For 1 << 16 */
 222   131071,
 223   262139,
 224   524287,
 225   1048573,
 226   2097143,
 227   4194301,
 228   8388593,
 229   16777213,
 230   33554393,
 231   67108859,
 232   134217689,
 233   268435399,
 234   536870909,
 235   1073741789,
 236   2147483647  /* For 1 << 31 */
 237 };
 238
 239 static void
 240 g_hash_table_set_shift (GHashTable *hash_table, gint shift)
 241 {
 242   gint i;
 243   guint mask = 0;
 244
 245   hash_table->size = 1 << shift;
 246   hash_table->mod  = prime_mod [shift];
 247
 248   for (i = 0; i < shift; i++)
 249     {
 250       mask <<= 1;
 251       mask |= 1;
 252     }
 253
 254   hash_table->mask = mask;
 255 }
 256
 257 static gint
 258 g_hash_table_find_closest_shift (gint n)
 259 {
 260   gint i;
 261
 262   for (i = 0; n; i++)
 263     n >>= 1;
 264
 265   return i;
 266 }
 267
 268 static void
 269 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
 270 {
 271   gint shift;
 272
 273   shift = g_hash_table_find_closest_shift (size);
 274   shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
 275
 276   g_hash_table_set_shift (hash_table, shift);
 277 }
 278
 279 /*
 280  * g_hash_table_lookup_node:
 281  * @hash_table: our #GHashTable
 282  * @key: the key to lookup against
 283  * @hash_return: optional key hash return location
 284  * Return value: index of the described #GHashNode
 285  *
 286  * Performs a lookup in the hash table.  Virtually all hash operations
 287  * will use this function internally.
 288  *
 289  * This function first computes the hash value of the key using the
 290  * user's hash function.
 291  *
 292  * If an entry in the table matching @key is found then this function
 293  * returns the index of that entry in the table, and if not, the
 294  * index of an empty node (never a tombstone).
 295  */
 296 static inline guint
 297 g_hash_table_lookup_node (GHashTable    *hash_table,
 298                           gconstpointer  key)
 299 {
 300   GHashNode *node;
 301   guint node_index;
 302   guint hash_value;
 303   guint step = 0;
 304
 305   /* Empty buckets have hash_value set to 0, and for tombstones, it's 1.
 306    * We need to make sure our hash value is not one of these. */
 307
 308   hash_value = (* hash_table->hash_func) (key);
 309   if (G_UNLIKELY (hash_value <= 1))
 310     hash_value = 2;
 311
 312   node_index = hash_value % hash_table->mod;
 313   node = &hash_table->nodes [node_index];
 314
 315   while (node->key_hash)
 316     {
 317       /*  We first check if our full hash values
 318        *  are equal so we can avoid calling the full-blown
 319        *  key equality function in most cases.
 320        */
 321
 322       if (node->key_hash == hash_value)
 323         {
 324           if (hash_table->key_equal_func)
 325             {
 326               if (hash_table->key_equal_func (node->key, key))
 327                 break;
 328             }
 329           else if (node->key == key)
 330             {
 331               break;
 332             }
 333         }
 334
 335       step++;
 336       node_index += step;
 337       node_index &= hash_table->mask;
 338       node = &hash_table->nodes [node_index];
 339     }
 340
 341   return node_index;
 342 }
 343
 344 /*
 345  * g_hash_table_lookup_node_for_insertion:
 346  * @hash_table: our #GHashTable
 347  * @key: the key to lookup against
 348  * @hash_return: key hash return location
 349  * Return value: index of the described #GHashNode
 350  *
 351  * Performs a lookup in the hash table, preserving extra information
 352  * usually needed for insertion.
 353  *
 354  * This function first computes the hash value of the key using the
 355  * user's hash function.
 356  *
 357  * If an entry in the table matching @key is found then this function
 358  * returns the index of that entry in the table, and if not, the
 359  * index of an unused node (empty or tombstone) where the key can be
 360  * inserted.
 361  *
 362  * The computed hash value is returned in the variable pointed to
 363  * by @hash_return. This is to save insertions from having to compute
 364  * the hash record again for the new record.
 365  */
 366 static inline guint
 367 g_hash_table_lookup_node_for_insertion (GHashTable    *hash_table,
 368                                         gconstpointer  key,
 369                                         guint         *hash_return)
 370 {
 371   GHashNode *node;
 372   guint node_index;
 373   guint hash_value;
 374   guint first_tombstone;
 375   gboolean have_tombstone = FALSE;
 376   guint step = 0;
 377
 378   /* Empty buckets have hash_value set to 0, and for tombstones, it's 1.
 379    * We need to make sure our hash value is not one of these. */
 380
 381   hash_value = (* hash_table->hash_func) (key);
 382   if (G_UNLIKELY (hash_value <= 1))
 383     hash_value = 2;
 384
 385   *hash_return = hash_value;
 386
 387   node_index = hash_value % hash_table->mod;
 388   node = &hash_table->nodes [node_index];
 389
 390   while (node->key_hash)
 391     {
 392       /*  We first check if our full hash values
 393        *  are equal so we can avoid calling the full-blown
 394        *  key equality function in most cases.
 395        */
 396
 397       if (node->key_hash == hash_value)
 398         {
 399           if (hash_table->key_equal_func)
 400             {
 401               if (hash_table->key_equal_func (node->key, key))
 402                 return node_index;
 403             }
 404           else if (node->key == key)
 405             {
 406               return node_index;
 407             }
 408         }
 409       else if (node->key_hash == 1 && !have_tombstone)
 410         {
 411           first_tombstone = node_index;
 412           have_tombstone = TRUE;
 413         }
 414
 415       step++;
 416       node_index += step;
 417       node_index &= hash_table->mask;
 418       node = &hash_table->nodes [node_index];
 419     }
 420
 421   if (have_tombstone)
 422     return first_tombstone;
 423
 424   return node_index;
 425 }
 426
 427 /*
 428  * g_hash_table_remove_node:
 429  * @hash_table: our #GHashTable
 430  * @node: pointer to node to remove
 431  * @notify: %TRUE if the destroy notify handlers are to be called
 432  *
 433  * Removes a node from the hash table and updates the node count.
 434  * The node is replaced by a tombstone. No table resize is performed.
 435  *
 436  * If @notify is %TRUE then the destroy notify functions are called
 437  * for the key and value of the hash node.
 438  */
 439 static void
 440 g_hash_table_remove_node (GHashTable   *hash_table,
 441                           GHashNode    *node,
 442                           gboolean      notify)
 443 {
 444   if (notify && hash_table->key_destroy_func)
 445     hash_table->key_destroy_func (node->key);
 446
 447   if (notify && hash_table->value_destroy_func)
 448     hash_table->value_destroy_func (node->value);
 449
 450   /* Erect tombstone */
 451   node->key_hash = 1;
 452
 453   /* Be GC friendly */
 454   node->key = NULL;
 455   node->value = NULL;
 456
 457   hash_table->nnodes--;
 458 }
 459
 460 /*
 461  * g_hash_table_remove_all_nodes:
 462  * @hash_table: our #GHashTable
 463  * @notify: %TRUE if the destroy notify handlers are to be called
 464  *
 465  * Removes all nodes from the table.  Since this may be a precursor to
 466  * freeing the table entirely, no resize is performed.
 467  *
 468  * If @notify is %TRUE then the destroy notify functions are called
 469  * for the key and value of the hash node.
 470  */
 471 static void
 472 g_hash_table_remove_all_nodes (GHashTable *hash_table,
 473                                gboolean    notify)
 474 {
 475   int i;
 476
 477   for (i = 0; i < hash_table->size; i++)
 478     {
 479       GHashNode *node = &hash_table->nodes [i];
 480
 481       if (node->key_hash > 1)
 482         {
 483           if (notify && hash_table->key_destroy_func)
 484             hash_table->key_destroy_func (node->key);
 485
 486           if (notify && hash_table->value_destroy_func)
 487             hash_table->value_destroy_func (node->value);
 488         }
 489     }
 490
 491   /* We need to set node->key_hash = 0 for all nodes - might as well be GC
 492    * friendly and clear everything */
 493   memset (hash_table->nodes, 0, hash_table->size * sizeof (GHashNode));
 494
 495   hash_table->nnodes = 0;
 496   hash_table->noccupied = 0;
 497 }
 498
 499 /*
 500  * g_hash_table_resize:
 501  * @hash_table: our #GHashTable
 502  *
 503  * Resizes the hash table to the optimal size based on the number of
 504  * nodes currently held.  If you call this function then a resize will
 505  * occur, even if one does not need to occur.  Use
 506  * g_hash_table_maybe_resize() instead.
 507  *
 508  * This function may "resize" the hash table to its current size, with
 509  * the side effect of cleaning up tombstones and otherwise optimizing
 510  * the probe sequences.
 511  */
 512 static void
 513 g_hash_table_resize (GHashTable *hash_table)
 514 {
 515   GHashNode *new_nodes;
 516   gint old_size;
 517   gint i;
 518
 519   old_size = hash_table->size;
 520   g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
 521
 522   new_nodes = g_new0 (GHashNode, hash_table->size);
 523
 524   for (i = 0; i < old_size; i++)
 525     {
 526       GHashNode *node = &hash_table->nodes [i];
 527       GHashNode *new_node;
 528       guint hash_val;
 529       guint step = 0;
 530
 531       if (node->key_hash <= 1)
 532         continue;
 533
 534       hash_val = node->key_hash % hash_table->mod;
 535       new_node = &new_nodes [hash_val];
 536
 537       while (new_node->key_hash)
 538         {
 539           step++;
 540           hash_val += step;
 541           hash_val &= hash_table->mask;
 542           new_node = &new_nodes [hash_val];
 543         }
 544
 545       *new_node = *node;
 546     }
 547
 548   g_free (hash_table->nodes);
 549   hash_table->nodes = new_nodes;
 550   hash_table->noccupied = hash_table->nnodes;
 551 }
 552
 553 /*
 554  * g_hash_table_maybe_resize:
 555  * @hash_table: our #GHashTable
 556  *
 557  * Resizes the hash table, if needed.
 558  *
 559  * Essentially, calls g_hash_table_resize() if the table has strayed
 560  * too far from its ideal size for its number of nodes.
 561  */
 562 static inline void
 563 g_hash_table_maybe_resize (GHashTable *hash_table)
 564 {
 565   gint noccupied = hash_table->noccupied;
 566   gint size = hash_table->size;
 567
 568   if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
 569       (size <= noccupied + (noccupied / 16)))
 570     g_hash_table_resize (hash_table);
 571 }
 572
 573 /**
 574  * g_hash_table_new:
 575  * @hash_func: a function to create a hash value from a key.
 576  *   Hash values are used to determine where keys are stored within the
 577  *   #GHashTable data structure. The g_direct_hash(), g_int_hash(),
 578  *   g_int64_hash(), g_double_hash() and g_str_hash() functions are provided
 579  *   for some common types of keys.
 580  *   If hash_func is %NULL, g_direct_hash() is used.
 581  * @key_equal_func: a function to check two keys for equality.  This is
 582  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
 583  *   g_int_equal(), g_int64_equal(), g_double_equal() and g_str_equal()
 584  *   functions are provided for the most common types of keys.
 585  *   If @key_equal_func is %NULL, keys are compared directly in a similar
 586  *   fashion to g_direct_equal(), but without the overhead of a function call.
 587  *
 588  * Creates a new #GHashTable with a reference count of 1.
 589  *
 590  * Return value: a new #GHashTable.
 591  **/
 592 GHashTable*
 593 g_hash_table_new (GHashFunc    hash_func,
 594                   GEqualFunc   key_equal_func)
 595 {
 596   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 597 }
 598
 599
 600 /**
 601  * g_hash_table_new_full:
 602  * @hash_func: a function to create a hash value from a key.
 603  * @key_equal_func: a function to check two keys for equality.
 604  * @key_destroy_func: a function to free the memory allocated for the key
 605  *   used when removing the entry from the #GHashTable or %NULL if you
 606  *   don't want to supply such a function.
 607  * @value_destroy_func: a function to free the memory allocated for the
 608  *   value used when removing the entry from the #GHashTable or %NULL if
 609  *   you don't want to supply such a function.
 610  *
 611  * Creates a new #GHashTable like g_hash_table_new() with a reference count
 612  * of 1 and allows to specify functions to free the memory allocated for the
 613  * key and value that get called when removing the entry from the #GHashTable.
 614  *
 615  * Return value: a new #GHashTable.
 616  **/
 617 GHashTable*
 618 g_hash_table_new_full (GHashFunc       hash_func,
 619                        GEqualFunc      key_equal_func,
 620                        GDestroyNotify  key_destroy_func,
 621                        GDestroyNotify  value_destroy_func)
 622 {
 623   GHashTable *hash_table;
 624
 625   hash_table = g_slice_new (GHashTable);
 626   g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
 627   hash_table->nnodes             = 0;
 628   hash_table->noccupied          = 0;
 629   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
 630   hash_table->key_equal_func     = key_equal_func;
 631   hash_table->ref_count          = 1;
 632 #ifndef G_DISABLE_ASSERT
 633   hash_table->version            = 0;
 634 #endif
 635   hash_table->key_destroy_func   = key_destroy_func;
 636   hash_table->value_destroy_func = value_destroy_func;
 637   hash_table->nodes              = g_new0 (GHashNode, hash_table->size);
 638
 639   return hash_table;
 640 }
 641
 642 /**
 643  * g_hash_table_iter_init:
 644  * @iter: an uninitialized #GHashTableIter.
 645  * @hash_table: a #GHashTable.
 646  *
 647  * Initializes a key/value pair iterator and associates it with
 648  * @hash_table. Modifying the hash table after calling this function
 649  * invalidates the returned iterator.
 650  * |[
 651  * GHashTableIter iter;
 652  * gpointer key, value;
 653  *
 654  * g_hash_table_iter_init (&iter, hash_table);
 655  * while (g_hash_table_iter_next (&iter, &key, &value))
 656  *   {
 657  *     /&ast; do something with key and value &ast;/
 658  *   }
 659  * ]|
 660  *
 661  * Since: 2.16
 662  **/
 663 void
 664 g_hash_table_iter_init (GHashTableIter *iter,
 665                         GHashTable     *hash_table)
 666 {
 667   RealIter *ri = (RealIter *) iter;
 668
 669   g_return_if_fail (iter != NULL);
 670   g_return_if_fail (hash_table != NULL);
 671
 672   ri->hash_table = hash_table;
 673   ri->position = -1;
 674 #ifndef G_DISABLE_ASSERT
 675   ri->version = hash_table->version;
 676 #endif
 677 }
 678
 679 /**
 680  * g_hash_table_iter_next:
 681  * @iter: an initialized #GHashTableIter.
 682  * @key: a location to store the key, or %NULL.
 683  * @value: a location to store the value, or %NULL.
 684  *
 685  * Advances @iter and retrieves the key and/or value that are now
 686  * pointed to as a result of this advancement. If %FALSE is returned,
 687  * @key and @value are not set, and the iterator becomes invalid.
 688  *
 689  * Return value: %FALSE if the end of the #GHashTable has been reached.
 690  *
 691  * Since: 2.16
 692  **/
 693 gboolean
 694 g_hash_table_iter_next (GHashTableIter *iter,
 695                         gpointer       *key,
 696                         gpointer       *value)
 697 {
 698   RealIter *ri = (RealIter *) iter;
 699   GHashNode *node;
 700   gint position;
 701
 702   g_return_val_if_fail (iter != NULL, FALSE);
 703 #ifndef G_DISABLE_ASSERT
 704   g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
 705 #endif
 706   g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
 707
 708   position = ri->position;
 709
 710   do
 711     {
 712       position++;
 713       if (position >= ri->hash_table->size)
 714         {
 715           ri->position = position;
 716           return FALSE;
 717         }
 718
 719       node = &ri->hash_table->nodes [position];
 720     }
 721   while (node->key_hash <= 1);
 722
 723   if (key != NULL)
 724     *key = node->key;
 725   if (value != NULL)
 726     *value = node->value;
 727
 728   ri->position = position;
 729   return TRUE;
 730 }
 731
 732 /**
 733  * g_hash_table_iter_get_hash_table:
 734  * @iter: an initialized #GHashTableIter.
 735  *
 736  * Returns the #GHashTable associated with @iter.
 737  *
 738  * Return value: the #GHashTable associated with @iter.
 739  *
 740  * Since: 2.16
 741  **/
 742 GHashTable *
 743 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
 744 {
 745   g_return_val_if_fail (iter != NULL, NULL);
 746
 747   return ((RealIter *) iter)->hash_table;
 748 }
 749
 750 static void
 751 iter_remove_or_steal (RealIter *ri, gboolean notify)
 752 {
 753   g_return_if_fail (ri != NULL);
 754 #ifndef G_DISABLE_ASSERT
 755   g_return_if_fail (ri->version == ri->hash_table->version);
 756 #endif
 757   g_return_if_fail (ri->position >= 0);
 758   g_return_if_fail (ri->position < ri->hash_table->size);
 759
 760   g_hash_table_remove_node (ri->hash_table, &ri->hash_table->nodes [ri->position], notify);
 761
 762 #ifndef G_DISABLE_ASSERT
 763   ri->version++;
 764   ri->hash_table->version++;
 765 #endif
 766 }
 767
 768 /**
 769  * g_hash_table_iter_remove:
 770  * @iter: an initialized #GHashTableIter.
 771  *
 772  * Removes the key/value pair currently pointed to by the iterator
 773  * from its associated #GHashTable. Can only be called after
 774  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 775  * than once for the same key/value pair.
 776  *
 777  * If the #GHashTable was created using g_hash_table_new_full(), the
 778  * key and value are freed using the supplied destroy functions, otherwise
 779  * you have to make sure that any dynamically allocated values are freed
 780  * yourself.
 781  *
 782  * Since: 2.16
 783  **/
 784 void
 785 g_hash_table_iter_remove (GHashTableIter *iter)
 786 {
 787   iter_remove_or_steal ((RealIter *) iter, TRUE);
 788 }
 789
 790 /**
 791  * g_hash_table_iter_steal:
 792  * @iter: an initialized #GHashTableIter.
 793  *
 794  * Removes the key/value pair currently pointed to by the iterator
 795  * from its associated #GHashTable, without calling the key and value
 796  * destroy functions. Can only be called after
 797  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 798  * than once for the same key/value pair.
 799  *
 800  * Since: 2.16
 801  **/
 802 void
 803 g_hash_table_iter_steal (GHashTableIter *iter)
 804 {
 805   iter_remove_or_steal ((RealIter *) iter, FALSE);
 806 }
 807
 808
 809 /**
 810  * g_hash_table_ref:
 811  * @hash_table: a valid #GHashTable.
 812  *
 813  * Atomically increments the reference count of @hash_table by one.
 814  * This function is MT-safe and may be called from any thread.
 815  *
 816  * Return value: the passed in #GHashTable.
 817  *
 818  * Since: 2.10
 819  **/
 820 GHashTable*
 821 g_hash_table_ref (GHashTable *hash_table)
 822 {
 823   g_return_val_if_fail (hash_table != NULL, NULL);
 824   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 825
 826   g_atomic_int_add (&hash_table->ref_count, 1);
 827   return hash_table;
 828 }
 829
 830 /**
 831  * g_hash_table_unref:
 832  * @hash_table: a valid #GHashTable.
 833  *
 834  * Atomically decrements the reference count of @hash_table by one.
 835  * If the reference count drops to 0, all keys and values will be
 836  * destroyed, and all memory allocated by the hash table is released.
 837  * This function is MT-safe and may be called from any thread.
 838  *
 839  * Since: 2.10
 840  **/
 841 void
 842 g_hash_table_unref (GHashTable *hash_table)
 843 {
 844   g_return_if_fail (hash_table != NULL);
 845   g_return_if_fail (hash_table->ref_count > 0);
 846
 847   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 848     {
 849       g_hash_table_remove_all_nodes (hash_table, TRUE);
 850       g_free (hash_table->nodes);
 851       g_slice_free (GHashTable, hash_table);
 852     }
 853 }
 854
 855 /**
 856  * g_hash_table_destroy:
 857  * @hash_table: a #GHashTable.
 858  *
 859  * Destroys all keys and values in the #GHashTable and decrements its
 860  * reference count by 1. If keys and/or values are dynamically allocated,
 861  * you should either free them first or create the #GHashTable with destroy
 862  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 863  * functions you supplied will be called on all keys and values during the
 864  * destruction phase.
 865  **/
 866 void
 867 g_hash_table_destroy (GHashTable *hash_table)
 868 {
 869   g_return_if_fail (hash_table != NULL);
 870   g_return_if_fail (hash_table->ref_count > 0);
 871
 872   g_hash_table_remove_all (hash_table);
 873   g_hash_table_unref (hash_table);
 874 }
 875
 876 /**
 877  * g_hash_table_lookup:
 878  * @hash_table: a #GHashTable.
 879  * @key: the key to look up.
 880  *
 881  * Looks up a key in a #GHashTable. Note that this function cannot
 882  * distinguish between a key that is not present and one which is present
 883  * and has the value %NULL. If you need this distinction, use
 884  * g_hash_table_lookup_extended().
 885  *
 886  * Return value: the associated value, or %NULL if the key is not found.
 887  **/
 888 gpointer
 889 g_hash_table_lookup (GHashTable   *hash_table,
 890                      gconstpointer key)
 891 {
 892   GHashNode *node;
 893   guint      node_index;
 894
 895   g_return_val_if_fail (hash_table != NULL, NULL);
 896
 897   node_index = g_hash_table_lookup_node (hash_table, key);
 898   node = &hash_table->nodes [node_index];
 899
 900   return node->key_hash ? node->value : NULL;
 901 }
 902
 903 /**
 904  * g_hash_table_lookup_extended:
 905  * @hash_table: a #GHashTable
 906  * @lookup_key: the key to look up
 907  * @orig_key: return location for the original key, or %NULL
 908  * @value: return location for the value associated with the key, or %NULL
 909  *
 910  * Looks up a key in the #GHashTable, returning the original key and the
 911  * associated value and a #gboolean which is %TRUE if the key was found. This
 912  * is useful if you need to free the memory allocated for the original key,
 913  * for example before calling g_hash_table_remove().
 914  *
 915  * You can actually pass %NULL for @lookup_key to test
 916  * whether the %NULL key exists.
 917  *
 918  * Return value: %TRUE if the key was found in the #GHashTable.
 919  **/
 920 gboolean
 921 g_hash_table_lookup_extended (GHashTable    *hash_table,
 922                               gconstpointer  lookup_key,
 923                               gpointer      *orig_key,
 924                               gpointer      *value)
 925 {
 926   GHashNode *node;
 927   guint      node_index;
 928
 929   g_return_val_if_fail (hash_table != NULL, FALSE);
 930
 931   node_index = g_hash_table_lookup_node (hash_table, lookup_key);
 932   node = &hash_table->nodes [node_index];
 933
 934   if (!node->key_hash)
 935     return FALSE;
 936
 937   if (orig_key)
 938     *orig_key = node->key;
 939
 940   if (value)
 941     *value = node->value;
 942
 943   return TRUE;
 944 }
 945
 946 /*
 947  * g_hash_table_insert_internal:
 948  * @hash_table: our #GHashTable
 949  * @key: the key to insert
 950  * @value: the value to insert
 951  * @keep_new_key: if %TRUE and this key already exists in the table
 952  *   then call the destroy notify function on the old key.  If %FALSE
 953  *   then call the destroy notify function on the new key.
 954  *
 955  * Implements the common logic for the g_hash_table_insert() and
 956  * g_hash_table_replace() functions.
 957  *
 958  * Do a lookup of @key.  If it is found, replace it with the new
 959  * @value (and perhaps the new @key).  If it is not found, create a
 960  * new node.
 961  */
 962 static void
 963 g_hash_table_insert_internal (GHashTable *hash_table,
 964                               gpointer    key,
 965                               gpointer    value,
 966                               gboolean    keep_new_key)
 967 {
 968   GHashNode *node;
 969   guint node_index;
 970   guint key_hash;
 971   guint old_hash;
 972
 973   g_return_if_fail (hash_table != NULL);
 974   g_return_if_fail (hash_table->ref_count > 0);
 975
 976   node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash);
 977   node = &hash_table->nodes [node_index];
 978
 979   old_hash = node->key_hash;
 980
 981   if (old_hash > 1)
 982     {
 983       if (keep_new_key)
 984         {
 985           if (hash_table->key_destroy_func)
 986             hash_table->key_destroy_func (node->key);
 987           node->key = key;
 988         }
 989       else
 990         {
 991           if (hash_table->key_destroy_func)
 992             hash_table->key_destroy_func (key);
 993         }
 994
 995       if (hash_table->value_destroy_func)
 996         hash_table->value_destroy_func (node->value);
 997
 998       node->value = value;
 999     }
1000   else
1001     {
1002       node->key = key;
1003       node->value = value;
1004       node->key_hash = key_hash;
1005
1006       hash_table->nnodes++;
1007
1008       if (old_hash == 0)
1009         {
1010           /* We replaced an empty node, and not a tombstone */
1011           hash_table->noccupied++;
1012           g_hash_table_maybe_resize (hash_table);
1013         }
1014
1015 #ifndef G_DISABLE_ASSERT
1016       hash_table->version++;
1017 #endif
1018     }
1019 }
1020
1021 /**
1022  * g_hash_table_insert:
1023  * @hash_table: a #GHashTable.
1024  * @key: a key to insert.
1025  * @value: the value to associate with the key.
1026  *
1027  * Inserts a new key and value into a #GHashTable.
1028  *
1029  * If the key already exists in the #GHashTable its current value is replaced
1030  * with the new value. If you supplied a @value_destroy_func when creating the
1031  * #GHashTable, the old value is freed using that function. If you supplied
1032  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
1033  * using that function.
1034  **/
1035 void
1036 g_hash_table_insert (GHashTable *hash_table,
1037                      gpointer    key,
1038                      gpointer    value)
1039 {
1040   g_hash_table_insert_internal (hash_table, key, value, FALSE);
1041 }
1042
1043 /**
1044  * g_hash_table_replace:
1045  * @hash_table: a #GHashTable.
1046  * @key: a key to insert.
1047  * @value: the value to associate with the key.
1048  *
1049  * Inserts a new key and value into a #GHashTable similar to
1050  * g_hash_table_insert(). The difference is that if the key already exists
1051  * in the #GHashTable, it gets replaced by the new key. If you supplied a
1052  * @value_destroy_func when creating the #GHashTable, the old value is freed
1053  * using that function. If you supplied a @key_destroy_func when creating the
1054  * #GHashTable, the old key is freed using that function.
1055  **/
1056 void
1057 g_hash_table_replace (GHashTable *hash_table,
1058                       gpointer    key,
1059                       gpointer    value)
1060 {
1061   g_hash_table_insert_internal (hash_table, key, value, TRUE);
1062 }
1063
1064 /*
1065  * g_hash_table_remove_internal:
1066  * @hash_table: our #GHashTable
1067  * @key: the key to remove
1068  * @notify: %TRUE if the destroy notify handlers are to be called
1069  * Return value: %TRUE if a node was found and removed, else %FALSE
1070  *
1071  * Implements the common logic for the g_hash_table_remove() and
1072  * g_hash_table_steal() functions.
1073  *
1074  * Do a lookup of @key and remove it if it is found, calling the
1075  * destroy notify handlers only if @notify is %TRUE.
1076  */
1077 static gboolean
1078 g_hash_table_remove_internal (GHashTable    *hash_table,
1079                               gconstpointer  key,
1080                               gboolean       notify)
1081 {
1082   GHashNode *node;
1083   guint node_index;
1084
1085   g_return_val_if_fail (hash_table != NULL, FALSE);
1086
1087   node_index = g_hash_table_lookup_node (hash_table, key);
1088   node = &hash_table->nodes [node_index];
1089
1090   /* g_hash_table_lookup_node() never returns a tombstone, so this is safe */
1091   if (!node->key_hash)
1092     return FALSE;
1093
1094   g_hash_table_remove_node (hash_table, node, notify);
1095   g_hash_table_maybe_resize (hash_table);
1096
1097 #ifndef G_DISABLE_ASSERT
1098   hash_table->version++;
1099 #endif
1100
1101   return TRUE;
1102 }
1103
1104 /**
1105  * g_hash_table_remove:
1106  * @hash_table: a #GHashTable.
1107  * @key: the key to remove.
1108  *
1109  * Removes a key and its associated value from a #GHashTable.
1110  *
1111  * If the #GHashTable was created using g_hash_table_new_full(), the
1112  * key and value are freed using the supplied destroy functions, otherwise
1113  * you have to make sure that any dynamically allocated values are freed
1114  * yourself.
1115  *
1116  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1117  **/
1118 gboolean
1119 g_hash_table_remove (GHashTable    *hash_table,
1120                      gconstpointer  key)
1121 {
1122   return g_hash_table_remove_internal (hash_table, key, TRUE);
1123 }
1124
1125 /**
1126  * g_hash_table_steal:
1127  * @hash_table: a #GHashTable.
1128  * @key: the key to remove.
1129  *
1130  * Removes a key and its associated value from a #GHashTable without
1131  * calling the key and value destroy functions.
1132  *
1133  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1134  **/
1135 gboolean
1136 g_hash_table_steal (GHashTable    *hash_table,
1137                     gconstpointer  key)
1138 {
1139   return g_hash_table_remove_internal (hash_table, key, FALSE);
1140 }
1141
1142 /**
1143  * g_hash_table_remove_all:
1144  * @hash_table: a #GHashTable
1145  *
1146  * Removes all keys and their associated values from a #GHashTable.
1147  *
1148  * If the #GHashTable was created using g_hash_table_new_full(), the keys
1149  * and values are freed using the supplied destroy functions, otherwise you
1150  * have to make sure that any dynamically allocated values are freed
1151  * yourself.
1152  *
1153  * Since: 2.12
1154  **/
1155 void
1156 g_hash_table_remove_all (GHashTable *hash_table)
1157 {
1158   g_return_if_fail (hash_table != NULL);
1159
1160 #ifndef G_DISABLE_ASSERT
1161   if (hash_table->nnodes != 0)
1162     hash_table->version++;
1163 #endif
1164
1165   g_hash_table_remove_all_nodes (hash_table, TRUE);
1166   g_hash_table_maybe_resize (hash_table);
1167 }
1168
1169 /**
1170  * g_hash_table_steal_all:
1171  * @hash_table: a #GHashTable.
1172  *
1173  * Removes all keys and their associated values from a #GHashTable
1174  * without calling the key and value destroy functions.
1175  *
1176  * Since: 2.12
1177  **/
1178 void
1179 g_hash_table_steal_all (GHashTable *hash_table)
1180 {
1181   g_return_if_fail (hash_table != NULL);
1182
1183 #ifndef G_DISABLE_ASSERT
1184   if (hash_table->nnodes != 0)
1185     hash_table->version++;
1186 #endif
1187
1188   g_hash_table_remove_all_nodes (hash_table, FALSE);
1189   g_hash_table_maybe_resize (hash_table);
1190 }
1191
1192 /*
1193  * g_hash_table_foreach_remove_or_steal:
1194  * @hash_table: our #GHashTable
1195  * @func: the user's callback function
1196  * @user_data: data for @func
1197  * @notify: %TRUE if the destroy notify handlers are to be called
1198  *
1199  * Implements the common logic for g_hash_table_foreach_remove() and
1200  * g_hash_table_foreach_steal().
1201  *
1202  * Iterates over every node in the table, calling @func with the key
1203  * and value of the node (and @user_data).  If @func returns %TRUE the
1204  * node is removed from the table.
1205  *
1206  * If @notify is true then the destroy notify handlers will be called
1207  * for each removed node.
1208  */
1209 static guint
1210 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1211                                       GHRFunc     func,
1212                                       gpointer    user_data,
1213                                       gboolean    notify)
1214 {
1215   guint deleted = 0;
1216   gint i;
1217
1218   for (i = 0; i < hash_table->size; i++)
1219     {
1220       GHashNode *node = &hash_table->nodes [i];
1221
1222       if (node->key_hash > 1 && (* func) (node->key, node->value, user_data))
1223         {
1224           g_hash_table_remove_node (hash_table, node, notify);
1225           deleted++;
1226         }
1227     }
1228
1229   g_hash_table_maybe_resize (hash_table);
1230
1231 #ifndef G_DISABLE_ASSERT
1232   if (deleted > 0)
1233     hash_table->version++;
1234 #endif
1235
1236   return deleted;
1237 }
1238
1239 /**
1240  * g_hash_table_foreach_remove:
1241  * @hash_table: a #GHashTable.
1242  * @func: the function to call for each key/value pair.
1243  * @user_data: user data to pass to the function.
1244  *
1245  * Calls the given function for each key/value pair in the #GHashTable.
1246  * If the function returns %TRUE, then the key/value pair is removed from the
1247  * #GHashTable. If you supplied key or value destroy functions when creating
1248  * the #GHashTable, they are used to free the memory allocated for the removed
1249  * keys and values.
1250  *
1251  * See #GHashTableIter for an alternative way to loop over the
1252  * key/value pairs in the hash table.
1253  *
1254  * Return value: the number of key/value pairs removed.
1255  **/
1256 guint
1257 g_hash_table_foreach_remove (GHashTable *hash_table,
1258                              GHRFunc     func,
1259                              gpointer    user_data)
1260 {
1261   g_return_val_if_fail (hash_table != NULL, 0);
1262   g_return_val_if_fail (func != NULL, 0);
1263
1264   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1265 }
1266
1267 /**
1268  * g_hash_table_foreach_steal:
1269  * @hash_table: a #GHashTable.
1270  * @func: the function to call for each key/value pair.
1271  * @user_data: user data to pass to the function.
1272  *
1273  * Calls the given function for each key/value pair in the #GHashTable.
1274  * If the function returns %TRUE, then the key/value pair is removed from the
1275  * #GHashTable, but no key or value destroy functions are called.
1276  *
1277  * See #GHashTableIter for an alternative way to loop over the
1278  * key/value pairs in the hash table.
1279  *
1280  * Return value: the number of key/value pairs removed.
1281  **/
1282 guint
1283 g_hash_table_foreach_steal (GHashTable *hash_table,
1284                             GHRFunc     func,
1285                             gpointer    user_data)
1286 {
1287   g_return_val_if_fail (hash_table != NULL, 0);
1288   g_return_val_if_fail (func != NULL, 0);
1289
1290   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1291 }
1292
1293 /**
1294  * g_hash_table_foreach:
1295  * @hash_table: a #GHashTable.
1296  * @func: the function to call for each key/value pair.
1297  * @user_data: user data to pass to the function.
1298  *
1299  * Calls the given function for each of the key/value pairs in the
1300  * #GHashTable.  The function is passed the key and value of each
1301  * pair, and the given @user_data parameter.  The hash table may not
1302  * be modified while iterating over it (you can't add/remove
1303  * items). To remove all items matching a predicate, use
1304  * g_hash_table_foreach_remove().
1305  *
1306  * See g_hash_table_find() for performance caveats for linear
1307  * order searches in contrast to g_hash_table_lookup().
1308  **/
1309 void
1310 g_hash_table_foreach (GHashTable *hash_table,
1311                       GHFunc      func,
1312                       gpointer    user_data)
1313 {
1314   gint i;
1315
1316   g_return_if_fail (hash_table != NULL);
1317   g_return_if_fail (func != NULL);
1318
1319   for (i = 0; i < hash_table->size; i++)
1320     {
1321       GHashNode *node = &hash_table->nodes [i];
1322
1323       if (node->key_hash > 1)
1324         (* func) (node->key, node->value, user_data);
1325     }
1326 }
1327
1328 /**
1329  * g_hash_table_find:
1330  * @hash_table: a #GHashTable.
1331  * @predicate:  function to test the key/value pairs for a certain property.
1332  * @user_data:  user data to pass to the function.
1333  *
1334  * Calls the given function for key/value pairs in the #GHashTable until
1335  * @predicate returns %TRUE.  The function is passed the key and value of
1336  * each pair, and the given @user_data parameter. The hash table may not
1337  * be modified while iterating over it (you can't add/remove items).
1338  *
1339  * Note, that hash tables are really only optimized for forward lookups,
1340  * i.e. g_hash_table_lookup().
1341  * So code that frequently issues g_hash_table_find() or
1342  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1343  * hash table) should probably be reworked to use additional or different
1344  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1345  * operation issued for all n values in a hash table ends up needing O(n*n)
1346  * operations).
1347  *
1348  * Return value: The value of the first key/value pair is returned, for which
1349  * func evaluates to %TRUE. If no pair with the requested property is found,
1350  * %NULL is returned.
1351  *
1352  * Since: 2.4
1353  **/
1354 gpointer
1355 g_hash_table_find (GHashTable      *hash_table,
1356                    GHRFunc          predicate,
1357                    gpointer         user_data)
1358 {
1359   gint i;
1360
1361   g_return_val_if_fail (hash_table != NULL, NULL);
1362   g_return_val_if_fail (predicate != NULL, NULL);
1363
1364   for (i = 0; i < hash_table->size; i++)
1365     {
1366       GHashNode *node = &hash_table->nodes [i];
1367
1368       if (node->key_hash > 1 && predicate (node->key, node->value, user_data))
1369         return node->value;
1370     }
1371
1372   return NULL;
1373 }
1374
1375 /**
1376  * g_hash_table_size:
1377  * @hash_table: a #GHashTable.
1378  *
1379  * Returns the number of elements contained in the #GHashTable.
1380  *
1381  * Return value: the number of key/value pairs in the #GHashTable.
1382  **/
1383 guint
1384 g_hash_table_size (GHashTable *hash_table)
1385 {
1386   g_return_val_if_fail (hash_table != NULL, 0);
1387
1388   return hash_table->nnodes;
1389 }
1390
1391 /**
1392  * g_hash_table_get_keys:
1393  * @hash_table: a #GHashTable
1394  *
1395  * Retrieves every key inside @hash_table. The returned data is valid
1396  * until @hash_table is modified.
1397  *
1398  * Return value: a #GList containing all the keys inside the hash
1399  *   table. The content of the list is owned by the hash table and
1400  *   should not be modified or freed. Use g_list_free() when done
1401  *   using the list.
1402  *
1403  * Since: 2.14
1404  */
1405 GList *
1406 g_hash_table_get_keys (GHashTable *hash_table)
1407 {
1408   gint i;
1409   GList *retval;
1410
1411   g_return_val_if_fail (hash_table != NULL, NULL);
1412
1413   retval = NULL;
1414   for (i = 0; i < hash_table->size; i++)
1415     {
1416       GHashNode *node = &hash_table->nodes [i];
1417
1418       if (node->key_hash > 1)
1419         retval = g_list_prepend (retval, node->key);
1420     }
1421
1422   return retval;
1423 }
1424
1425 /**
1426  * g_hash_table_get_values:
1427  * @hash_table: a #GHashTable
1428  *
1429  * Retrieves every value inside @hash_table. The returned data is
1430  * valid until @hash_table is modified.
1431  *
1432  * Return value: a #GList containing all the values inside the hash
1433  *   table. The content of the list is owned by the hash table and
1434  *   should not be modified or freed. Use g_list_free() when done
1435  *   using the list.
1436  *
1437  * Since: 2.14
1438  */
1439 GList *
1440 g_hash_table_get_values (GHashTable *hash_table)
1441 {
1442   gint i;
1443   GList *retval;
1444
1445   g_return_val_if_fail (hash_table != NULL, NULL);
1446
1447   retval = NULL;
1448   for (i = 0; i < hash_table->size; i++)
1449     {
1450       GHashNode *node = &hash_table->nodes [i];
1451
1452       if (node->key_hash > 1)
1453         retval = g_list_prepend (retval, node->value);
1454     }
1455
1456   return retval;
1457 }