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