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: return location for the original key, or %NULL
 794  * @value: return location for the value associated with the key, or %NULL
 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  * You can actually pass %NULL for @lookup_key to test
 802  * whether the %NULL key exists.
 803  *
 804  * Return value: %TRUE if the key was found in the #GHashTable.
 805  **/
 806 gboolean
 807 g_hash_table_lookup_extended (GHashTable    *hash_table,
 808                               gconstpointer  lookup_key,
 809                               gpointer      *orig_key,
 810                               gpointer      *value)
 811 {
 812   GHashNode *node;
 813   guint      node_index;
 814
 815   g_return_val_if_fail (hash_table != NULL, FALSE);
 816
 817   node_index = g_hash_table_lookup_node (hash_table, lookup_key);
 818   node = &hash_table->nodes [node_index];
 819
 820   if (!node->key_hash)
 821     return FALSE;
 822
 823   if (orig_key)
 824     *orig_key = node->key;
 825
 826   if (value)
 827     *value = node->value;
 828
 829   return TRUE;
 830 }
 831
 832 /*
 833  * g_hash_table_insert_internal:
 834  * @hash_table: our #GHashTable
 835  * @key: the key to insert
 836  * @value: the value to insert
 837  * @keep_new_key: if %TRUE and this key already exists in the table
 838  *   then call the destroy notify function on the old key.  If %FALSE
 839  *   then call the destroy notify function on the new key.
 840  *
 841  * Implements the common logic for the g_hash_table_insert() and
 842  * g_hash_table_replace() functions.
 843  *
 844  * Do a lookup of @key.  If it is found, replace it with the new
 845  * @value (and perhaps the new @key).  If it is not found, create a
 846  * new node.
 847  */
 848 static void
 849 g_hash_table_insert_internal (GHashTable *hash_table,
 850                               gpointer    key,
 851                               gpointer    value,
 852                               gboolean    keep_new_key)
 853 {
 854   GHashNode *node;
 855   guint node_index;
 856   guint key_hash;
 857   guint old_hash;
 858
 859   g_return_if_fail (hash_table != NULL);
 860   g_return_if_fail (hash_table->ref_count > 0);
 861
 862   node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash);
 863   node = &hash_table->nodes [node_index];
 864
 865   old_hash = node->key_hash;
 866
 867   if (old_hash > 1)
 868     {
 869       if (keep_new_key)
 870         {
 871           if (hash_table->key_destroy_func)
 872             hash_table->key_destroy_func (node->key);
 873           node->key = key;
 874         }
 875       else
 876         {
 877           if (hash_table->key_destroy_func)
 878             hash_table->key_destroy_func (key);
 879         }
 880
 881       if (hash_table->value_destroy_func)
 882         hash_table->value_destroy_func (node->value);
 883
 884       node->value = value;
 885     }
 886   else
 887     {
 888       node->key = key;
 889       node->value = value;
 890       node->key_hash = key_hash;
 891
 892       hash_table->nnodes++;
 893
 894       if (old_hash == 0)
 895         {
 896           /* We replaced an empty node, and not a tombstone */
 897           hash_table->noccupied++;
 898           g_hash_table_maybe_resize (hash_table);
 899         }
 900
 901 #ifndef G_DISABLE_ASSERT
 902       hash_table->version++;
 903 #endif
 904     }
 905 }
 906
 907 /**
 908  * g_hash_table_insert:
 909  * @hash_table: a #GHashTable.
 910  * @key: a key to insert.
 911  * @value: the value to associate with the key.
 912  *
 913  * Inserts a new key and value into a #GHashTable.
 914  *
 915  * If the key already exists in the #GHashTable its current value is replaced
 916  * with the new value. If you supplied a @value_destroy_func when creating the
 917  * #GHashTable, the old value is freed using that function. If you supplied
 918  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 919  * using that function.
 920  **/
 921 void
 922 g_hash_table_insert (GHashTable *hash_table,
 923                      gpointer    key,
 924                      gpointer    value)
 925 {
 926   g_hash_table_insert_internal (hash_table, key, value, FALSE);
 927 }
 928
 929 /**
 930  * g_hash_table_replace:
 931  * @hash_table: a #GHashTable.
 932  * @key: a key to insert.
 933  * @value: the value to associate with the key.
 934  *
 935  * Inserts a new key and value into a #GHashTable similar to
 936  * g_hash_table_insert(). The difference is that if the key already exists
 937  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 938  * @value_destroy_func when creating the #GHashTable, the old value is freed
 939  * using that function. If you supplied a @key_destroy_func when creating the
 940  * #GHashTable, the old key is freed using that function.
 941  **/
 942 void
 943 g_hash_table_replace (GHashTable *hash_table,
 944                       gpointer    key,
 945                       gpointer    value)
 946 {
 947   g_hash_table_insert_internal (hash_table, key, value, TRUE);
 948 }
 949
 950 /*
 951  * g_hash_table_remove_internal:
 952  * @hash_table: our #GHashTable
 953  * @key: the key to remove
 954  * @notify: %TRUE if the destroy notify handlers are to be called
 955  * Return value: %TRUE if a node was found and removed, else %FALSE
 956  *
 957  * Implements the common logic for the g_hash_table_remove() and
 958  * g_hash_table_steal() functions.
 959  *
 960  * Do a lookup of @key and remove it if it is found, calling the
 961  * destroy notify handlers only if @notify is %TRUE.
 962  */
 963 static gboolean
 964 g_hash_table_remove_internal (GHashTable    *hash_table,
 965                               gconstpointer  key,
 966                               gboolean       notify)
 967 {
 968   GHashNode *node;
 969   guint node_index;
 970
 971   g_return_val_if_fail (hash_table != NULL, FALSE);
 972
 973   node_index = g_hash_table_lookup_node (hash_table, key);
 974   node = &hash_table->nodes [node_index];
 975
 976   /* g_hash_table_lookup_node() never returns a tombstone, so this is safe */
 977   if (!node->key_hash)
 978     return FALSE;
 979
 980   g_hash_table_remove_node (hash_table, node, notify);
 981   g_hash_table_maybe_resize (hash_table);
 982
 983 #ifndef G_DISABLE_ASSERT
 984   hash_table->version++;
 985 #endif
 986
 987   return TRUE;
 988 }
 989
 990 /**
 991  * g_hash_table_remove:
 992  * @hash_table: a #GHashTable.
 993  * @key: the key to remove.
 994  *
 995  * Removes a key and its associated value from a #GHashTable.
 996  *
 997  * If the #GHashTable was created using g_hash_table_new_full(), the
 998  * key and value are freed using the supplied destroy functions, otherwise
 999  * you have to make sure that any dynamically allocated values are freed
1000  * yourself.
1001  *
1002  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1003  **/
1004 gboolean
1005 g_hash_table_remove (GHashTable    *hash_table,
1006                      gconstpointer  key)
1007 {
1008   return g_hash_table_remove_internal (hash_table, key, TRUE);
1009 }
1010
1011 /**
1012  * g_hash_table_steal:
1013  * @hash_table: a #GHashTable.
1014  * @key: the key to remove.
1015  *
1016  * Removes a key and its associated value from a #GHashTable without
1017  * calling the key and value destroy functions.
1018  *
1019  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1020  **/
1021 gboolean
1022 g_hash_table_steal (GHashTable    *hash_table,
1023                     gconstpointer  key)
1024 {
1025   return g_hash_table_remove_internal (hash_table, key, FALSE);
1026 }
1027
1028 /**
1029  * g_hash_table_remove_all:
1030  * @hash_table: a #GHashTable
1031  *
1032  * Removes all keys and their associated values from a #GHashTable.
1033  *
1034  * If the #GHashTable was created using g_hash_table_new_full(), the keys
1035  * and values are freed using the supplied destroy functions, otherwise you
1036  * have to make sure that any dynamically allocated values are freed
1037  * yourself.
1038  *
1039  * Since: 2.12
1040  **/
1041 void
1042 g_hash_table_remove_all (GHashTable *hash_table)
1043 {
1044   g_return_if_fail (hash_table != NULL);
1045
1046 #ifndef G_DISABLE_ASSERT
1047   if (hash_table->nnodes != 0)
1048     hash_table->version++;
1049 #endif
1050
1051   g_hash_table_remove_all_nodes (hash_table, TRUE);
1052   g_hash_table_maybe_resize (hash_table);
1053 }
1054
1055 /**
1056  * g_hash_table_steal_all:
1057  * @hash_table: a #GHashTable.
1058  *
1059  * Removes all keys and their associated values from a #GHashTable
1060  * without calling the key and value destroy functions.
1061  *
1062  * Since: 2.12
1063  **/
1064 void
1065 g_hash_table_steal_all (GHashTable *hash_table)
1066 {
1067   g_return_if_fail (hash_table != NULL);
1068
1069 #ifndef G_DISABLE_ASSERT
1070   if (hash_table->nnodes != 0)
1071     hash_table->version++;
1072 #endif
1073
1074   g_hash_table_remove_all_nodes (hash_table, FALSE);
1075   g_hash_table_maybe_resize (hash_table);
1076 }
1077
1078 /*
1079  * g_hash_table_foreach_remove_or_steal:
1080  * @hash_table: our #GHashTable
1081  * @func: the user's callback function
1082  * @user_data: data for @func
1083  * @notify: %TRUE if the destroy notify handlers are to be called
1084  *
1085  * Implements the common logic for g_hash_table_foreach_remove() and
1086  * g_hash_table_foreach_steal().
1087  *
1088  * Iterates over every node in the table, calling @func with the key
1089  * and value of the node (and @user_data).  If @func returns %TRUE the
1090  * node is removed from the table.
1091  *
1092  * If @notify is true then the destroy notify handlers will be called
1093  * for each removed node.
1094  */
1095 static guint
1096 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1097                                       GHRFunc     func,
1098                                       gpointer    user_data,
1099                                       gboolean    notify)
1100 {
1101   guint deleted = 0;
1102   gint i;
1103
1104   for (i = 0; i < hash_table->size; i++)
1105     {
1106       GHashNode *node = &hash_table->nodes [i];
1107
1108       if (node->key_hash > 1 && (* func) (node->key, node->value, user_data))
1109         {
1110           g_hash_table_remove_node (hash_table, node, notify);
1111           deleted++;
1112         }
1113     }
1114
1115   g_hash_table_maybe_resize (hash_table);
1116
1117 #ifndef G_DISABLE_ASSERT
1118   if (deleted > 0)
1119     hash_table->version++;
1120 #endif
1121
1122   return deleted;
1123 }
1124
1125 /**
1126  * g_hash_table_foreach_remove:
1127  * @hash_table: a #GHashTable.
1128  * @func: the function to call for each key/value pair.
1129  * @user_data: user data to pass to the function.
1130  *
1131  * Calls the given function for each key/value pair in the #GHashTable.
1132  * If the function returns %TRUE, then the key/value pair is removed from the
1133  * #GHashTable. If you supplied key or value destroy functions when creating
1134  * the #GHashTable, they are used to free the memory allocated for the removed
1135  * keys and values.
1136  *
1137  * See #GHashTableIter for an alternative way to loop over the
1138  * key/value pairs in the hash table.
1139  *
1140  * Return value: the number of key/value pairs removed.
1141  **/
1142 guint
1143 g_hash_table_foreach_remove (GHashTable *hash_table,
1144                              GHRFunc     func,
1145                              gpointer    user_data)
1146 {
1147   g_return_val_if_fail (hash_table != NULL, 0);
1148   g_return_val_if_fail (func != NULL, 0);
1149
1150   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1151 }
1152
1153 /**
1154  * g_hash_table_foreach_steal:
1155  * @hash_table: a #GHashTable.
1156  * @func: the function to call for each key/value pair.
1157  * @user_data: user data to pass to the function.
1158  *
1159  * Calls the given function for each key/value pair in the #GHashTable.
1160  * If the function returns %TRUE, then the key/value pair is removed from the
1161  * #GHashTable, but no key or value destroy functions are called.
1162  *
1163  * See #GHashTableIter for an alternative way to loop over the
1164  * key/value pairs in the hash table.
1165  *
1166  * Return value: the number of key/value pairs removed.
1167  **/
1168 guint
1169 g_hash_table_foreach_steal (GHashTable *hash_table,
1170                             GHRFunc     func,
1171                             gpointer    user_data)
1172 {
1173   g_return_val_if_fail (hash_table != NULL, 0);
1174   g_return_val_if_fail (func != NULL, 0);
1175
1176   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1177 }
1178
1179 /**
1180  * g_hash_table_foreach:
1181  * @hash_table: a #GHashTable.
1182  * @func: the function to call for each key/value pair.
1183  * @user_data: user data to pass to the function.
1184  *
1185  * Calls the given function for each of the key/value pairs in the
1186  * #GHashTable.  The function is passed the key and value of each
1187  * pair, and the given @user_data parameter.  The hash table may not
1188  * be modified while iterating over it (you can't add/remove
1189  * items). To remove all items matching a predicate, use
1190  * g_hash_table_foreach_remove().
1191  *
1192  * See g_hash_table_find() for performance caveats for linear
1193  * order searches in contrast to g_hash_table_lookup().
1194  **/
1195 void
1196 g_hash_table_foreach (GHashTable *hash_table,
1197                       GHFunc      func,
1198                       gpointer    user_data)
1199 {
1200   gint i;
1201
1202   g_return_if_fail (hash_table != NULL);
1203   g_return_if_fail (func != NULL);
1204
1205   for (i = 0; i < hash_table->size; i++)
1206     {
1207       GHashNode *node = &hash_table->nodes [i];
1208
1209       if (node->key_hash > 1)
1210         (* func) (node->key, node->value, user_data);
1211     }
1212 }
1213
1214 /**
1215  * g_hash_table_find:
1216  * @hash_table: a #GHashTable.
1217  * @predicate:  function to test the key/value pairs for a certain property.
1218  * @user_data:  user data to pass to the function.
1219  *
1220  * Calls the given function for key/value pairs in the #GHashTable until
1221  * @predicate returns %TRUE.  The function is passed the key and value of
1222  * each pair, and the given @user_data parameter. The hash table may not
1223  * be modified while iterating over it (you can't add/remove items).
1224  *
1225  * Note, that hash tables are really only optimized for forward lookups,
1226  * i.e. g_hash_table_lookup().
1227  * So code that frequently issues g_hash_table_find() or
1228  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1229  * hash table) should probably be reworked to use additional or different
1230  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1231  * operation issued for all n values in a hash table ends up needing O(n*n)
1232  * operations).
1233  *
1234  * Return value: The value of the first key/value pair is returned, for which
1235  * func evaluates to %TRUE. If no pair with the requested property is found,
1236  * %NULL is returned.
1237  *
1238  * Since: 2.4
1239  **/
1240 gpointer
1241 g_hash_table_find (GHashTable      *hash_table,
1242                    GHRFunc          predicate,
1243                    gpointer         user_data)
1244 {
1245   gint i;
1246
1247   g_return_val_if_fail (hash_table != NULL, NULL);
1248   g_return_val_if_fail (predicate != NULL, NULL);
1249
1250   for (i = 0; i < hash_table->size; i++)
1251     {
1252       GHashNode *node = &hash_table->nodes [i];
1253
1254       if (node->key_hash > 1 && predicate (node->key, node->value, user_data))
1255         return node->value;
1256     }
1257
1258   return NULL;
1259 }
1260
1261 /**
1262  * g_hash_table_size:
1263  * @hash_table: a #GHashTable.
1264  *
1265  * Returns the number of elements contained in the #GHashTable.
1266  *
1267  * Return value: the number of key/value pairs in the #GHashTable.
1268  **/
1269 guint
1270 g_hash_table_size (GHashTable *hash_table)
1271 {
1272   g_return_val_if_fail (hash_table != NULL, 0);
1273
1274   return hash_table->nnodes;
1275 }
1276
1277 /**
1278  * g_hash_table_get_keys:
1279  * @hash_table: a #GHashTable
1280  *
1281  * Retrieves every key inside @hash_table. The returned data is valid
1282  * until @hash_table is modified.
1283  *
1284  * Return value: a #GList containing all the keys inside the hash
1285  *   table. The content of the list is owned by the hash table and
1286  *   should not be modified or freed. Use g_list_free() when done
1287  *   using the list.
1288  *
1289  * Since: 2.14
1290  */
1291 GList *
1292 g_hash_table_get_keys (GHashTable *hash_table)
1293 {
1294   gint i;
1295   GList *retval;
1296
1297   g_return_val_if_fail (hash_table != NULL, NULL);
1298
1299   retval = NULL;
1300   for (i = 0; i < hash_table->size; i++)
1301     {
1302       GHashNode *node = &hash_table->nodes [i];
1303
1304       if (node->key_hash > 1)
1305         retval = g_list_prepend (retval, node->key);
1306     }
1307
1308   return retval;
1309 }
1310
1311 /**
1312  * g_hash_table_get_values:
1313  * @hash_table: a #GHashTable
1314  *
1315  * Retrieves every value inside @hash_table. The returned data is
1316  * valid until @hash_table is modified.
1317  *
1318  * Return value: a #GList containing all the values inside the hash
1319  *   table. The content of the list is owned by the hash table and
1320  *   should not be modified or freed. Use g_list_free() when done
1321  *   using the list.
1322  *
1323  * Since: 2.14
1324  */
1325 GList *
1326 g_hash_table_get_values (GHashTable *hash_table)
1327 {
1328   gint i;
1329   GList *retval;
1330
1331   g_return_val_if_fail (hash_table != NULL, NULL);
1332
1333   retval = NULL;
1334   for (i = 0; i < hash_table->size; i++)
1335     {
1336       GHashNode *node = &hash_table->nodes [i];
1337
1338       if (node->key_hash > 1)
1339         retval = g_list_prepend (retval, node->value);
1340     }
1341
1342   return retval;
1343 }
1344
1345 #define __G_HASH_C__
1346 #include "galiasdef.c"