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