glib/ghash.c

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