glib/ghash.c

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