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