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(),
 465  *   g_int64_hash(), g_double_hash() and g_str_hash() functions are provided
 466  *   for some common types of keys.
 467  *   If hash_func is %NULL, g_direct_hash() is used.
 468  * @key_equal_func: a function to check two keys for equality.  This is
 469  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
 470  *   g_int_equal(), g_int64_equal(), g_double_equal() and g_str_equal()
 471  *   functions are provided for the most common types of keys.
 472  *   If @key_equal_func is %NULL, keys are compared directly in a similar
 473  *   fashion to g_direct_equal(), but without the overhead of a function call.
 474  *
 475  * Creates a new #GHashTable with a reference count of 1.
 476  *
 477  * Return value: a new #GHashTable.
 478  **/
 479 GHashTable*
 480 g_hash_table_new (GHashFunc    hash_func,
 481                   GEqualFunc   key_equal_func)
 482 {
 483   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 484 }
 485
 486
 487 /**
 488  * g_hash_table_new_full:
 489  * @hash_func: a function to create a hash value from a key.
 490  * @key_equal_func: a function to check two keys for equality.
 491  * @key_destroy_func: a function to free the memory allocated for the key
 492  *   used when removing the entry from the #GHashTable or %NULL if you
 493  *   don't want to supply such a function.
 494  * @value_destroy_func: a function to free the memory allocated for the
 495  *   value used when removing the entry from the #GHashTable or %NULL if
 496  *   you don't want to supply such a function.
 497  *
 498  * Creates a new #GHashTable like g_hash_table_new() with a reference count
 499  * of 1 and allows to specify functions to free the memory allocated for the
 500  * key and value that get called when removing the entry from the #GHashTable.
 501  *
 502  * Return value: a new #GHashTable.
 503  **/
 504 GHashTable*
 505 g_hash_table_new_full (GHashFunc       hash_func,
 506                        GEqualFunc      key_equal_func,
 507                        GDestroyNotify  key_destroy_func,
 508                        GDestroyNotify  value_destroy_func)
 509 {
 510   GHashTable *hash_table;
 511
 512   hash_table = g_slice_new (GHashTable);
 513   g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
 514   hash_table->nnodes             = 0;
 515   hash_table->noccupied          = 0;
 516   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
 517   hash_table->key_equal_func     = key_equal_func;
 518   hash_table->ref_count          = 1;
 519 #ifndef G_DISABLE_ASSERT
 520   hash_table->version            = 0;
 521 #endif
 522   hash_table->key_destroy_func   = key_destroy_func;
 523   hash_table->value_destroy_func = value_destroy_func;
 524   hash_table->nodes              = g_new0 (GHashNode, hash_table->size);
 525
 526   return hash_table;
 527 }
 528
 529 /**
 530  * g_hash_table_iter_init:
 531  * @iter: an uninitialized #GHashTableIter.
 532  * @hash_table: a #GHashTable.
 533  *
 534  * Initializes a key/value pair iterator and associates it with
 535  * @hash_table. Modifying the hash table after calling this function
 536  * invalidates the returned iterator.
 537  * |[
 538  * GHashTableIter iter;
 539  * gpointer key, value;
 540  *
 541  * g_hash_table_iter_init (&iter, hash_table);
 542  * while (g_hash_table_iter_next (&iter, &key, &value))
 543  *   {
 544  *     /&ast; do something with key and value &ast;/
 545  *   }
 546  * ]|
 547  *
 548  * Since: 2.16
 549  **/
 550 void
 551 g_hash_table_iter_init (GHashTableIter *iter,
 552                         GHashTable     *hash_table)
 553 {
 554   RealIter *ri = (RealIter *) iter;
 555
 556   g_return_if_fail (iter != NULL);
 557   g_return_if_fail (hash_table != NULL);
 558
 559   ri->hash_table = hash_table;
 560   ri->position = -1;
 561 #ifndef G_DISABLE_ASSERT
 562   ri->version = hash_table->version;
 563 #endif
 564 }
 565
 566 /**
 567  * g_hash_table_iter_next:
 568  * @iter: an initialized #GHashTableIter.
 569  * @key: a location to store the key, or %NULL.
 570  * @value: a location to store the value, or %NULL.
 571  *
 572  * Advances @iter and retrieves the key and/or value that are now
 573  * pointed to as a result of this advancement. If %FALSE is returned,
 574  * @key and @value are not set, and the iterator becomes invalid.
 575  *
 576  * Return value: %FALSE if the end of the #GHashTable has been reached.
 577  *
 578  * Since: 2.16
 579  **/
 580 gboolean
 581 g_hash_table_iter_next (GHashTableIter *iter,
 582                         gpointer       *key,
 583                         gpointer       *value)
 584 {
 585   RealIter *ri = (RealIter *) iter;
 586   GHashNode *node;
 587   gint position;
 588
 589   g_return_val_if_fail (iter != NULL, FALSE);
 590 #ifndef G_DISABLE_ASSERT
 591   g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
 592 #endif
 593   g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
 594
 595   position = ri->position;
 596
 597   do
 598     {
 599       position++;
 600       if (position >= ri->hash_table->size)
 601         {
 602           ri->position = position;
 603           return FALSE;
 604         }
 605
 606       node = &ri->hash_table->nodes [position];
 607     }
 608   while (node->key_hash <= 1);
 609
 610   if (key != NULL)
 611     *key = node->key;
 612   if (value != NULL)
 613     *value = node->value;
 614
 615   ri->position = position;
 616   return TRUE;
 617 }
 618
 619 /**
 620  * g_hash_table_iter_get_hash_table:
 621  * @iter: an initialized #GHashTableIter.
 622  *
 623  * Returns the #GHashTable associated with @iter.
 624  *
 625  * Return value: the #GHashTable associated with @iter.
 626  *
 627  * Since: 2.16
 628  **/
 629 GHashTable *
 630 g_hash_table_iter_get_hash_table (GHashTableIter *iter)
 631 {
 632   g_return_val_if_fail (iter != NULL, NULL);
 633
 634   return ((RealIter *) iter)->hash_table;
 635 }
 636
 637 static void
 638 iter_remove_or_steal (RealIter *ri, gboolean notify)
 639 {
 640   g_return_if_fail (ri != NULL);
 641 #ifndef G_DISABLE_ASSERT
 642   g_return_if_fail (ri->version == ri->hash_table->version);
 643 #endif
 644   g_return_if_fail (ri->position >= 0);
 645   g_return_if_fail (ri->position < ri->hash_table->size);
 646
 647   g_hash_table_remove_node (ri->hash_table, &ri->hash_table->nodes [ri->position], notify);
 648
 649 #ifndef G_DISABLE_ASSERT
 650   ri->version++;
 651   ri->hash_table->version++;
 652 #endif
 653 }
 654
 655 /**
 656  * g_hash_table_iter_remove():
 657  * @iter: an initialized #GHashTableIter.
 658  *
 659  * Removes the key/value pair currently pointed to by the iterator
 660  * from its associated #GHashTable. Can only be called after
 661  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 662  * than once for the same key/value pair.
 663  *
 664  * If the #GHashTable was created using g_hash_table_new_full(), the
 665  * key and value are freed using the supplied destroy functions, otherwise
 666  * you have to make sure that any dynamically allocated values are freed
 667  * yourself.
 668  *
 669  * Since: 2.16
 670  **/
 671 void
 672 g_hash_table_iter_remove (GHashTableIter *iter)
 673 {
 674   iter_remove_or_steal ((RealIter *) iter, TRUE);
 675 }
 676
 677 /**
 678  * g_hash_table_iter_steal():
 679  * @iter: an initialized #GHashTableIter.
 680  *
 681  * Removes the key/value pair currently pointed to by the iterator
 682  * from its associated #GHashTable, without calling the key and value
 683  * destroy functions. Can only be called after
 684  * g_hash_table_iter_next() returned %TRUE, and cannot be called more
 685  * than once for the same key/value pair.
 686  *
 687  * Since: 2.16
 688  **/
 689 void
 690 g_hash_table_iter_steal (GHashTableIter *iter)
 691 {
 692   iter_remove_or_steal ((RealIter *) iter, FALSE);
 693 }
 694
 695
 696 /**
 697  * g_hash_table_ref:
 698  * @hash_table: a valid #GHashTable.
 699  *
 700  * Atomically increments the reference count of @hash_table by one.
 701  * This function is MT-safe and may be called from any thread.
 702  *
 703  * Return value: the passed in #GHashTable.
 704  *
 705  * Since: 2.10
 706  **/
 707 GHashTable*
 708 g_hash_table_ref (GHashTable *hash_table)
 709 {
 710   g_return_val_if_fail (hash_table != NULL, NULL);
 711   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 712
 713   g_atomic_int_add (&hash_table->ref_count, 1);
 714   return hash_table;
 715 }
 716
 717 /**
 718  * g_hash_table_unref:
 719  * @hash_table: a valid #GHashTable.
 720  *
 721  * Atomically decrements the reference count of @hash_table by one.
 722  * If the reference count drops to 0, all keys and values will be
 723  * destroyed, and all memory allocated by the hash table is released.
 724  * This function is MT-safe and may be called from any thread.
 725  *
 726  * Since: 2.10
 727  **/
 728 void
 729 g_hash_table_unref (GHashTable *hash_table)
 730 {
 731   g_return_if_fail (hash_table != NULL);
 732   g_return_if_fail (hash_table->ref_count > 0);
 733
 734   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 735     {
 736       g_hash_table_remove_all_nodes (hash_table, TRUE);
 737       g_free (hash_table->nodes);
 738       g_slice_free (GHashTable, hash_table);
 739     }
 740 }
 741
 742 /**
 743  * g_hash_table_destroy:
 744  * @hash_table: a #GHashTable.
 745  *
 746  * Destroys all keys and values in the #GHashTable and decrements its
 747  * reference count by 1. If keys and/or values are dynamically allocated,
 748  * you should either free them first or create the #GHashTable with destroy
 749  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 750  * functions you supplied will be called on all keys and values during the
 751  * destruction phase.
 752  **/
 753 void
 754 g_hash_table_destroy (GHashTable *hash_table)
 755 {
 756   g_return_if_fail (hash_table != NULL);
 757   g_return_if_fail (hash_table->ref_count > 0);
 758
 759   g_hash_table_remove_all (hash_table);
 760   g_hash_table_unref (hash_table);
 761 }
 762
 763 /**
 764  * g_hash_table_lookup:
 765  * @hash_table: a #GHashTable.
 766  * @key: the key to look up.
 767  *
 768  * Looks up a key in a #GHashTable. Note that this function cannot
 769  * distinguish between a key that is not present and one which is present
 770  * and has the value %NULL. If you need this distinction, use
 771  * g_hash_table_lookup_extended().
 772  *
 773  * Return value: the associated value, or %NULL if the key is not found.
 774  **/
 775 gpointer
 776 g_hash_table_lookup (GHashTable   *hash_table,
 777                      gconstpointer key)
 778 {
 779   GHashNode *node;
 780   guint      node_index;
 781
 782   g_return_val_if_fail (hash_table != NULL, NULL);
 783
 784   node_index = g_hash_table_lookup_node (hash_table, key);
 785   node = &hash_table->nodes [node_index];
 786
 787   return node->key_hash ? node->value : NULL;
 788 }
 789
 790 /**
 791  * g_hash_table_lookup_extended:
 792  * @hash_table: a #GHashTable
 793  * @lookup_key: the key to look up
 794  * @orig_key: return location for the original key, or %NULL
 795  * @value: return location for the value associated with the key, or %NULL
 796  *
 797  * Looks up a key in the #GHashTable, returning the original key and the
 798  * associated value and a #gboolean which is %TRUE if the key was found. This
 799  * is useful if you need to free the memory allocated for the original key,
 800  * for example before calling g_hash_table_remove().
 801  *
 802  * You can actually pass %NULL for @lookup_key to test
 803  * whether the %NULL key exists.
 804  *
 805  * Return value: %TRUE if the key was found in the #GHashTable.
 806  **/
 807 gboolean
 808 g_hash_table_lookup_extended (GHashTable    *hash_table,
 809                               gconstpointer  lookup_key,
 810                               gpointer      *orig_key,
 811                               gpointer      *value)
 812 {
 813   GHashNode *node;
 814   guint      node_index;
 815
 816   g_return_val_if_fail (hash_table != NULL, FALSE);
 817
 818   node_index = g_hash_table_lookup_node (hash_table, lookup_key);
 819   node = &hash_table->nodes [node_index];
 820
 821   if (!node->key_hash)
 822     return FALSE;
 823
 824   if (orig_key)
 825     *orig_key = node->key;
 826
 827   if (value)
 828     *value = node->value;
 829
 830   return TRUE;
 831 }
 832
 833 /*
 834  * g_hash_table_insert_internal:
 835  * @hash_table: our #GHashTable
 836  * @key: the key to insert
 837  * @value: the value to insert
 838  * @keep_new_key: if %TRUE and this key already exists in the table
 839  *   then call the destroy notify function on the old key.  If %FALSE
 840  *   then call the destroy notify function on the new key.
 841  *
 842  * Implements the common logic for the g_hash_table_insert() and
 843  * g_hash_table_replace() functions.
 844  *
 845  * Do a lookup of @key.  If it is found, replace it with the new
 846  * @value (and perhaps the new @key).  If it is not found, create a
 847  * new node.
 848  */
 849 static void
 850 g_hash_table_insert_internal (GHashTable *hash_table,
 851                               gpointer    key,
 852                               gpointer    value,
 853                               gboolean    keep_new_key)
 854 {
 855   GHashNode *node;
 856   guint node_index;
 857   guint key_hash;
 858   guint old_hash;
 859
 860   g_return_if_fail (hash_table != NULL);
 861   g_return_if_fail (hash_table->ref_count > 0);
 862
 863   node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash);
 864   node = &hash_table->nodes [node_index];
 865
 866   old_hash = node->key_hash;
 867
 868   if (old_hash > 1)
 869     {
 870       if (keep_new_key)
 871         {
 872           if (hash_table->key_destroy_func)
 873             hash_table->key_destroy_func (node->key);
 874           node->key = key;
 875         }
 876       else
 877         {
 878           if (hash_table->key_destroy_func)
 879             hash_table->key_destroy_func (key);
 880         }
 881
 882       if (hash_table->value_destroy_func)
 883         hash_table->value_destroy_func (node->value);
 884
 885       node->value = value;
 886     }
 887   else
 888     {
 889       node->key = key;
 890       node->value = value;
 891       node->key_hash = key_hash;
 892
 893       hash_table->nnodes++;
 894
 895       if (old_hash == 0)
 896         {
 897           /* We replaced an empty node, and not a tombstone */
 898           hash_table->noccupied++;
 899           g_hash_table_maybe_resize (hash_table);
 900         }
 901
 902 #ifndef G_DISABLE_ASSERT
 903       hash_table->version++;
 904 #endif
 905     }
 906 }
 907
 908 /**
 909  * g_hash_table_insert:
 910  * @hash_table: a #GHashTable.
 911  * @key: a key to insert.
 912  * @value: the value to associate with the key.
 913  *
 914  * Inserts a new key and value into a #GHashTable.
 915  *
 916  * If the key already exists in the #GHashTable its current value is replaced
 917  * with the new value. If you supplied a @value_destroy_func when creating the
 918  * #GHashTable, the old value is freed using that function. If you supplied
 919  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 920  * using that function.
 921  **/
 922 void
 923 g_hash_table_insert (GHashTable *hash_table,
 924                      gpointer    key,
 925                      gpointer    value)
 926 {
 927   g_hash_table_insert_internal (hash_table, key, value, FALSE);
 928 }
 929
 930 /**
 931  * g_hash_table_replace:
 932  * @hash_table: a #GHashTable.
 933  * @key: a key to insert.
 934  * @value: the value to associate with the key.
 935  *
 936  * Inserts a new key and value into a #GHashTable similar to
 937  * g_hash_table_insert(). The difference is that if the key already exists
 938  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 939  * @value_destroy_func when creating the #GHashTable, the old value is freed
 940  * using that function. If you supplied a @key_destroy_func when creating the
 941  * #GHashTable, the old key is freed using that function.
 942  **/
 943 void
 944 g_hash_table_replace (GHashTable *hash_table,
 945                       gpointer    key,
 946                       gpointer    value)
 947 {
 948   g_hash_table_insert_internal (hash_table, key, value, TRUE);
 949 }
 950
 951 /*
 952  * g_hash_table_remove_internal:
 953  * @hash_table: our #GHashTable
 954  * @key: the key to remove
 955  * @notify: %TRUE if the destroy notify handlers are to be called
 956  * Return value: %TRUE if a node was found and removed, else %FALSE
 957  *
 958  * Implements the common logic for the g_hash_table_remove() and
 959  * g_hash_table_steal() functions.
 960  *
 961  * Do a lookup of @key and remove it if it is found, calling the
 962  * destroy notify handlers only if @notify is %TRUE.
 963  */
 964 static gboolean
 965 g_hash_table_remove_internal (GHashTable    *hash_table,
 966                               gconstpointer  key,
 967                               gboolean       notify)
 968 {
 969   GHashNode *node;
 970   guint node_index;
 971
 972   g_return_val_if_fail (hash_table != NULL, FALSE);
 973
 974   node_index = g_hash_table_lookup_node (hash_table, key);
 975   node = &hash_table->nodes [node_index];
 976
 977   /* g_hash_table_lookup_node() never returns a tombstone, so this is safe */
 978   if (!node->key_hash)
 979     return FALSE;
 980
 981   g_hash_table_remove_node (hash_table, node, notify);
 982   g_hash_table_maybe_resize (hash_table);
 983
 984 #ifndef G_DISABLE_ASSERT
 985   hash_table->version++;
 986 #endif
 987
 988   return TRUE;
 989 }
 990
 991 /**
 992  * g_hash_table_remove:
 993  * @hash_table: a #GHashTable.
 994  * @key: the key to remove.
 995  *
 996  * Removes a key and its associated value from a #GHashTable.
 997  *
 998  * If the #GHashTable was created using g_hash_table_new_full(), the
 999  * key and value are freed using the supplied destroy functions, otherwise
1000  * you have to make sure that any dynamically allocated values are freed
1001  * yourself.
1002  *
1003  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1004  **/
1005 gboolean
1006 g_hash_table_remove (GHashTable    *hash_table,
1007                      gconstpointer  key)
1008 {
1009   return g_hash_table_remove_internal (hash_table, key, TRUE);
1010 }
1011
1012 /**
1013  * g_hash_table_steal:
1014  * @hash_table: a #GHashTable.
1015  * @key: the key to remove.
1016  *
1017  * Removes a key and its associated value from a #GHashTable without
1018  * calling the key and value destroy functions.
1019  *
1020  * Return value: %TRUE if the key was found and removed from the #GHashTable.
1021  **/
1022 gboolean
1023 g_hash_table_steal (GHashTable    *hash_table,
1024                     gconstpointer  key)
1025 {
1026   return g_hash_table_remove_internal (hash_table, key, FALSE);
1027 }
1028
1029 /**
1030  * g_hash_table_remove_all:
1031  * @hash_table: a #GHashTable
1032  *
1033  * Removes all keys and their associated values from a #GHashTable.
1034  *
1035  * If the #GHashTable was created using g_hash_table_new_full(), the keys
1036  * and values are freed using the supplied destroy functions, otherwise you
1037  * have to make sure that any dynamically allocated values are freed
1038  * yourself.
1039  *
1040  * Since: 2.12
1041  **/
1042 void
1043 g_hash_table_remove_all (GHashTable *hash_table)
1044 {
1045   g_return_if_fail (hash_table != NULL);
1046
1047 #ifndef G_DISABLE_ASSERT
1048   if (hash_table->nnodes != 0)
1049     hash_table->version++;
1050 #endif
1051
1052   g_hash_table_remove_all_nodes (hash_table, TRUE);
1053   g_hash_table_maybe_resize (hash_table);
1054 }
1055
1056 /**
1057  * g_hash_table_steal_all:
1058  * @hash_table: a #GHashTable.
1059  *
1060  * Removes all keys and their associated values from a #GHashTable
1061  * without calling the key and value destroy functions.
1062  *
1063  * Since: 2.12
1064  **/
1065 void
1066 g_hash_table_steal_all (GHashTable *hash_table)
1067 {
1068   g_return_if_fail (hash_table != NULL);
1069
1070 #ifndef G_DISABLE_ASSERT
1071   if (hash_table->nnodes != 0)
1072     hash_table->version++;
1073 #endif
1074
1075   g_hash_table_remove_all_nodes (hash_table, FALSE);
1076   g_hash_table_maybe_resize (hash_table);
1077 }
1078
1079 /*
1080  * g_hash_table_foreach_remove_or_steal:
1081  * @hash_table: our #GHashTable
1082  * @func: the user's callback function
1083  * @user_data: data for @func
1084  * @notify: %TRUE if the destroy notify handlers are to be called
1085  *
1086  * Implements the common logic for g_hash_table_foreach_remove() and
1087  * g_hash_table_foreach_steal().
1088  *
1089  * Iterates over every node in the table, calling @func with the key
1090  * and value of the node (and @user_data).  If @func returns %TRUE the
1091  * node is removed from the table.
1092  *
1093  * If @notify is true then the destroy notify handlers will be called
1094  * for each removed node.
1095  */
1096 static guint
1097 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
1098                                       GHRFunc     func,
1099                                       gpointer    user_data,
1100                                       gboolean    notify)
1101 {
1102   guint deleted = 0;
1103   gint i;
1104
1105   for (i = 0; i < hash_table->size; i++)
1106     {
1107       GHashNode *node = &hash_table->nodes [i];
1108
1109       if (node->key_hash > 1 && (* func) (node->key, node->value, user_data))
1110         {
1111           g_hash_table_remove_node (hash_table, node, notify);
1112           deleted++;
1113         }
1114     }
1115
1116   g_hash_table_maybe_resize (hash_table);
1117
1118 #ifndef G_DISABLE_ASSERT
1119   if (deleted > 0)
1120     hash_table->version++;
1121 #endif
1122
1123   return deleted;
1124 }
1125
1126 /**
1127  * g_hash_table_foreach_remove:
1128  * @hash_table: a #GHashTable.
1129  * @func: the function to call for each key/value pair.
1130  * @user_data: user data to pass to the function.
1131  *
1132  * Calls the given function for each key/value pair in the #GHashTable.
1133  * If the function returns %TRUE, then the key/value pair is removed from the
1134  * #GHashTable. If you supplied key or value destroy functions when creating
1135  * the #GHashTable, they are used to free the memory allocated for the removed
1136  * keys and values.
1137  *
1138  * See #GHashTableIter for an alternative way to loop over the
1139  * key/value pairs in the hash table.
1140  *
1141  * Return value: the number of key/value pairs removed.
1142  **/
1143 guint
1144 g_hash_table_foreach_remove (GHashTable *hash_table,
1145                              GHRFunc     func,
1146                              gpointer    user_data)
1147 {
1148   g_return_val_if_fail (hash_table != NULL, 0);
1149   g_return_val_if_fail (func != NULL, 0);
1150
1151   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
1152 }
1153
1154 /**
1155  * g_hash_table_foreach_steal:
1156  * @hash_table: a #GHashTable.
1157  * @func: the function to call for each key/value pair.
1158  * @user_data: user data to pass to the function.
1159  *
1160  * Calls the given function for each key/value pair in the #GHashTable.
1161  * If the function returns %TRUE, then the key/value pair is removed from the
1162  * #GHashTable, but no key or value destroy functions are called.
1163  *
1164  * See #GHashTableIter for an alternative way to loop over the
1165  * key/value pairs in the hash table.
1166  *
1167  * Return value: the number of key/value pairs removed.
1168  **/
1169 guint
1170 g_hash_table_foreach_steal (GHashTable *hash_table,
1171                             GHRFunc     func,
1172                             gpointer    user_data)
1173 {
1174   g_return_val_if_fail (hash_table != NULL, 0);
1175   g_return_val_if_fail (func != NULL, 0);
1176
1177   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
1178 }
1179
1180 /**
1181  * g_hash_table_foreach:
1182  * @hash_table: a #GHashTable.
1183  * @func: the function to call for each key/value pair.
1184  * @user_data: user data to pass to the function.
1185  *
1186  * Calls the given function for each of the key/value pairs in the
1187  * #GHashTable.  The function is passed the key and value of each
1188  * pair, and the given @user_data parameter.  The hash table may not
1189  * be modified while iterating over it (you can't add/remove
1190  * items). To remove all items matching a predicate, use
1191  * g_hash_table_foreach_remove().
1192  *
1193  * See g_hash_table_find() for performance caveats for linear
1194  * order searches in contrast to g_hash_table_lookup().
1195  **/
1196 void
1197 g_hash_table_foreach (GHashTable *hash_table,
1198                       GHFunc      func,
1199                       gpointer    user_data)
1200 {
1201   gint i;
1202
1203   g_return_if_fail (hash_table != NULL);
1204   g_return_if_fail (func != NULL);
1205
1206   for (i = 0; i < hash_table->size; i++)
1207     {
1208       GHashNode *node = &hash_table->nodes [i];
1209
1210       if (node->key_hash > 1)
1211         (* func) (node->key, node->value, user_data);
1212     }
1213 }
1214
1215 /**
1216  * g_hash_table_find:
1217  * @hash_table: a #GHashTable.
1218  * @predicate:  function to test the key/value pairs for a certain property.
1219  * @user_data:  user data to pass to the function.
1220  *
1221  * Calls the given function for key/value pairs in the #GHashTable until
1222  * @predicate returns %TRUE.  The function is passed the key and value of
1223  * each pair, and the given @user_data parameter. The hash table may not
1224  * be modified while iterating over it (you can't add/remove items).
1225  *
1226  * Note, that hash tables are really only optimized for forward lookups,
1227  * i.e. g_hash_table_lookup().
1228  * So code that frequently issues g_hash_table_find() or
1229  * g_hash_table_foreach() (e.g. in the order of once per every entry in a
1230  * hash table) should probably be reworked to use additional or different
1231  * data structures for reverse lookups (keep in mind that an O(n) find/foreach
1232  * operation issued for all n values in a hash table ends up needing O(n*n)
1233  * operations).
1234  *
1235  * Return value: The value of the first key/value pair is returned, for which
1236  * func evaluates to %TRUE. If no pair with the requested property is found,
1237  * %NULL is returned.
1238  *
1239  * Since: 2.4
1240  **/
1241 gpointer
1242 g_hash_table_find (GHashTable      *hash_table,
1243                    GHRFunc          predicate,
1244                    gpointer         user_data)
1245 {
1246   gint i;
1247
1248   g_return_val_if_fail (hash_table != NULL, NULL);
1249   g_return_val_if_fail (predicate != NULL, NULL);
1250
1251   for (i = 0; i < hash_table->size; i++)
1252     {
1253       GHashNode *node = &hash_table->nodes [i];
1254
1255       if (node->key_hash > 1 && predicate (node->key, node->value, user_data))
1256         return node->value;
1257     }
1258
1259   return NULL;
1260 }
1261
1262 /**
1263  * g_hash_table_size:
1264  * @hash_table: a #GHashTable.
1265  *
1266  * Returns the number of elements contained in the #GHashTable.
1267  *
1268  * Return value: the number of key/value pairs in the #GHashTable.
1269  **/
1270 guint
1271 g_hash_table_size (GHashTable *hash_table)
1272 {
1273   g_return_val_if_fail (hash_table != NULL, 0);
1274
1275   return hash_table->nnodes;
1276 }
1277
1278 /**
1279  * g_hash_table_get_keys:
1280  * @hash_table: a #GHashTable
1281  *
1282  * Retrieves every key inside @hash_table. The returned data is valid
1283  * until @hash_table is modified.
1284  *
1285  * Return value: a #GList containing all the keys inside the hash
1286  *   table. The content of the list is owned by the hash table and
1287  *   should not be modified or freed. Use g_list_free() when done
1288  *   using the list.
1289  *
1290  * Since: 2.14
1291  */
1292 GList *
1293 g_hash_table_get_keys (GHashTable *hash_table)
1294 {
1295   gint i;
1296   GList *retval;
1297
1298   g_return_val_if_fail (hash_table != NULL, NULL);
1299
1300   retval = NULL;
1301   for (i = 0; i < hash_table->size; i++)
1302     {
1303       GHashNode *node = &hash_table->nodes [i];
1304
1305       if (node->key_hash > 1)
1306         retval = g_list_prepend (retval, node->key);
1307     }
1308
1309   return retval;
1310 }
1311
1312 /**
1313  * g_hash_table_get_values:
1314  * @hash_table: a #GHashTable
1315  *
1316  * Retrieves every value inside @hash_table. The returned data is
1317  * valid until @hash_table is modified.
1318  *
1319  * Return value: a #GList containing all the values inside the hash
1320  *   table. The content of the list is owned by the hash table and
1321  *   should not be modified or freed. Use g_list_free() when done
1322  *   using the list.
1323  *
1324  * Since: 2.14
1325  */
1326 GList *
1327 g_hash_table_get_values (GHashTable *hash_table)
1328 {
1329   gint i;
1330   GList *retval;
1331
1332   g_return_val_if_fail (hash_table != NULL, NULL);
1333
1334   retval = NULL;
1335   for (i = 0; i < hash_table->size; i++)
1336     {
1337       GHashNode *node = &hash_table->nodes [i];
1338
1339       if (node->key_hash > 1)
1340         retval = g_list_prepend (retval, node->value);
1341     }
1342
1343   return retval;
1344 }
1345
1346 #define __G_HASH_C__
1347 #include "galiasdef.c"