gnulib-local/lib/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  * Modified by Bruno Haible for use as a gnulib module.
  29  */
  30
  31 /*
  32  * MT safe
  33  */
  34
  35 #include "config.h"
  36
  37 #include "glib.h"
  38 #if 0
  39 #include "galias.h"
  40 #endif
  41
  42 #undef  CLAMP
  43 #define CLAMP(x, low, high)  (((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))
  44
  45
  46 #define HASH_TABLE_MIN_SIZE 11
  47 #define HASH_TABLE_MAX_SIZE 13845163
  48
  49
  50 typedef struct _GHashNode      GHashNode;
  51
  52 struct _GHashNode
  53 {
  54   gpointer   key;
  55   gpointer   value;
  56   GHashNode *next;
  57 };
  58
  59 struct _GHashTable
  60 {
  61   gint             size;
  62   gint             nnodes;
  63   GHashNode      **nodes;
  64   GHashFunc        hash_func;
  65   GEqualFunc       key_equal_func;
  66   volatile guint   ref_count;
  67   GDestroyNotify   key_destroy_func;
  68   GDestroyNotify   value_destroy_func;
  69 };
  70
  71 #define G_HASH_TABLE_RESIZE(hash_table)                         \
  72    G_STMT_START {                                               \
  73      if ((hash_table->size >= 3 * hash_table->nnodes &&         \
  74           hash_table->size > HASH_TABLE_MIN_SIZE) ||            \
  75          (3 * hash_table->size <= hash_table->nnodes &&         \
  76           hash_table->size < HASH_TABLE_MAX_SIZE))              \
  77            g_hash_table_resize (hash_table);                    \
  78    } G_STMT_END
  79
  80 static void             g_hash_table_resize       (GHashTable     *hash_table);
  81 static GHashNode**      g_hash_table_lookup_node  (GHashTable     *hash_table,
  82                                                    gconstpointer   key);
  83 static GHashNode*       g_hash_node_new           (gpointer        key,
  84                                                    gpointer        value);
  85 #if 0
  86 static void             g_hash_node_destroy       (GHashNode      *hash_node,
  87                                                    GDestroyNotify  key_destroy_func,
  88                                                    GDestroyNotify  value_destroy_func);
  89 static void             g_hash_nodes_destroy      (GHashNode      *hash_node,
  90                                                   GDestroyNotify   key_destroy_func,
  91                                                   GDestroyNotify   value_destroy_func);
  92 static guint g_hash_table_foreach_remove_or_steal (GHashTable     *hash_table,
  93                                                    GHRFunc         func,
  94                                                    gpointer        user_data,
  95                                                    gboolean        notify);
  96 #endif
  97
  98
  99 /**
 100  * g_hash_table_new:
 101  * @hash_func: a function to create a hash value from a key.
 102  *   Hash values are used to determine where keys are stored within the
 103  *   #GHashTable data structure. The g_direct_hash(), g_int_hash() and
 104  *   g_str_hash() functions are provided for some common types of keys.
 105  *   If hash_func is %NULL, g_direct_hash() is used.
 106  * @key_equal_func: a function to check two keys for equality.  This is
 107  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
 108  *   g_int_equal() and g_str_equal() functions are provided for the most
 109  *   common types of keys. If @key_equal_func is %NULL, keys are compared
 110  *   directly in a similar fashion to g_direct_equal(), but without the
 111  *   overhead of a function call.
 112  *
 113  * Creates a new #GHashTable with a reference count of 1.
 114  *
 115  * Return value: a new #GHashTable.
 116  **/
 117 GHashTable*
 118 g_hash_table_new (GHashFunc    hash_func,
 119                   GEqualFunc   key_equal_func)
 120 {
 121   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 122 }
 123
 124
 125 /**
 126  * g_hash_table_new_full:
 127  * @hash_func: a function to create a hash value from a key.
 128  * @key_equal_func: a function to check two keys for equality.
 129  * @key_destroy_func: a function to free the memory allocated for the key
 130  *   used when removing the entry from the #GHashTable or %NULL if you
 131  *   don't want to supply such a function.
 132  * @value_destroy_func: a function to free the memory allocated for the
 133  *   value used when removing the entry from the #GHashTable or %NULL if
 134  *   you don't want to supply such a function.
 135  *
 136  * Creates a new #GHashTable like g_hash_table_new() with a reference count
 137  * of 1 and allows to specify functions to free the memory allocated for the
 138  * key and value that get called when removing the entry from the #GHashTable.
 139  *
 140  * Return value: a new #GHashTable.
 141  **/
 142 GHashTable*
 143 g_hash_table_new_full (GHashFunc       hash_func,
 144                        GEqualFunc      key_equal_func,
 145                        GDestroyNotify  key_destroy_func,
 146                        GDestroyNotify  value_destroy_func)
 147 {
 148   GHashTable *hash_table;
 149
 150   hash_table = g_slice_new (GHashTable);
 151   hash_table->size               = HASH_TABLE_MIN_SIZE;
 152   hash_table->nnodes             = 0;
 153   hash_table->hash_func          = hash_func;
 154   hash_table->key_equal_func     = key_equal_func;
 155   hash_table->ref_count          = 1;
 156   hash_table->key_destroy_func   = key_destroy_func;
 157   hash_table->value_destroy_func = value_destroy_func;
 158   hash_table->nodes              = g_new0 (GHashNode*, hash_table->size);
 159
 160   return hash_table;
 161 }
 162
 163 #if 0
 164
 165 /**
 166  * g_hash_table_ref:
 167  * @hash_table: a valid #GHashTable.
 168  *
 169  * Atomically increments the reference count of @hash_table by one.
 170  * This function is MT-safe and may be called from any thread.
 171  *
 172  * Return value: the passed in #GHashTable.
 173  *
 174  * Since: 2.10
 175  **/
 176 GHashTable*
 177 g_hash_table_ref (GHashTable *hash_table)
 178 {
 179   g_return_val_if_fail (hash_table != NULL, NULL);
 180   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
 181
 182   g_atomic_int_add (&hash_table->ref_count, 1);
 183   return hash_table;
 184 }
 185
 186 /**
 187  * g_hash_table_unref:
 188  * @hash_table: a valid #GHashTable.
 189  *
 190  * Atomically decrements the reference count of @hash_table by one.
 191  * If the reference count drops to 0, all keys and values will be
 192  * destroyed, and all memory allocated by the hash table is released.
 193  * This function is MT-safe and may be called from any thread.
 194  *
 195  * Since: 2.10
 196  **/
 197 void
 198 g_hash_table_unref (GHashTable *hash_table)
 199 {
 200   g_return_if_fail (hash_table != NULL);
 201   g_return_if_fail (hash_table->ref_count > 0);
 202
 203   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
 204     {
 205       gint i;
 206
 207       for (i = 0; i < hash_table->size; i++)
 208         g_hash_nodes_destroy (hash_table->nodes[i],
 209                               hash_table->key_destroy_func,
 210                               hash_table->value_destroy_func);
 211       g_free (hash_table->nodes);
 212       g_slice_free (GHashTable, hash_table);
 213     }
 214 }
 215
 216 /**
 217  * g_hash_table_destroy:
 218  * @hash_table: a #GHashTable.
 219  *
 220  * Destroys all keys and values in the #GHashTable and decrements its
 221  * reference count by 1. If keys and/or values are dynamically allocated,
 222  * you should either free them first or create the #GHashTable with destroy
 223  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 224  * functions you supplied will be called on all keys and values during the
 225  * destruction phase.
 226  **/
 227 void
 228 g_hash_table_destroy (GHashTable *hash_table)
 229 {
 230   g_return_if_fail (hash_table != NULL);
 231   g_return_if_fail (hash_table->ref_count > 0);
 232
 233   g_hash_table_remove_all (hash_table);
 234   g_hash_table_unref (hash_table);
 235 }
 236
 237 #endif
 238
 239 static inline GHashNode**
 240 g_hash_table_lookup_node (GHashTable    *hash_table,
 241                           gconstpointer  key)
 242 {
 243   GHashNode **node;
 244
 245   node = &hash_table->nodes
 246     [(* hash_table->hash_func) (key) % hash_table->size];
 247
 248   /* Hash table lookup needs to be fast.
 249    *  We therefore remove the extra conditional of testing
 250    *  whether to call the key_equal_func or not from
 251    *  the inner loop.
 252    */
 253   if (hash_table->key_equal_func)
 254     while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
 255       node = &(*node)->next;
 256   else
 257     while (*node && (*node)->key != key)
 258       node = &(*node)->next;
 259
 260   return node;
 261 }
 262
 263 /**
 264  * g_hash_table_lookup:
 265  * @hash_table: a #GHashTable.
 266  * @key: the key to look up.
 267  *
 268  * Looks up a key in a #GHashTable. Note that this function cannot
 269  * distinguish between a key that is not present and one which is present
 270  * and has the value %NULL. If you need this distinction, use
 271  * g_hash_table_lookup_extended().
 272  *
 273  * Return value: the associated value, or %NULL if the key is not found.
 274  **/
 275 gpointer
 276 g_hash_table_lookup (GHashTable   *hash_table,
 277                      gconstpointer key)
 278 {
 279   GHashNode *node;
 280
 281   g_return_val_if_fail (hash_table != NULL, NULL);
 282
 283   node = *g_hash_table_lookup_node (hash_table, key);
 284
 285   return node ? node->value : NULL;
 286 }
 287
 288 #if 0
 289
 290 /**
 291  * g_hash_table_lookup_extended:
 292  * @hash_table: a #GHashTable.
 293  * @lookup_key: the key to look up.
 294  * @orig_key: returns the original key.
 295  * @value: returns the value associated with the key.
 296  *
 297  * Looks up a key in the #GHashTable, returning the original key and the
 298  * associated value and a #gboolean which is %TRUE if the key was found. This
 299  * is useful if you need to free the memory allocated for the original key,
 300  * for example before calling g_hash_table_remove().
 301  *
 302  * Return value: %TRUE if the key was found in the #GHashTable.
 303  **/
 304 gboolean
 305 g_hash_table_lookup_extended (GHashTable    *hash_table,
 306                               gconstpointer  lookup_key,
 307                               gpointer      *orig_key,
 308                               gpointer      *value)
 309 {
 310   GHashNode *node;
 311
 312   g_return_val_if_fail (hash_table != NULL, FALSE);
 313
 314   node = *g_hash_table_lookup_node (hash_table, lookup_key);
 315
 316   if (node)
 317     {
 318       if (orig_key)
 319         *orig_key = node->key;
 320       if (value)
 321         *value = node->value;
 322       return TRUE;
 323     }
 324   else
 325     return FALSE;
 326 }
 327
 328 #endif
 329
 330 /**
 331  * g_hash_table_insert:
 332  * @hash_table: a #GHashTable.
 333  * @key: a key to insert.
 334  * @value: the value to associate with the key.
 335  *
 336  * Inserts a new key and value into a #GHashTable.
 337  *
 338  * If the key already exists in the #GHashTable its current value is replaced
 339  * with the new value. If you supplied a @value_destroy_func when creating the
 340  * #GHashTable, the old value is freed using that function. If you supplied
 341  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 342  * using that function.
 343  **/
 344 void
 345 g_hash_table_insert (GHashTable *hash_table,
 346                      gpointer    key,
 347                      gpointer    value)
 348 {
 349   GHashNode **node;
 350
 351   g_return_if_fail (hash_table != NULL);
 352   g_return_if_fail (hash_table->ref_count > 0);
 353
 354   node = g_hash_table_lookup_node (hash_table, key);
 355
 356   if (*node)
 357     {
 358       /* do not reset node->key in this place, keeping
 359        * the old key is the intended behaviour.
 360        * g_hash_table_replace() can be used instead.
 361        */
 362
 363       /* free the passed key */
 364       if (hash_table->key_destroy_func)
 365         hash_table->key_destroy_func (key);
 366
 367       if (hash_table->value_destroy_func)
 368         hash_table->value_destroy_func ((*node)->value);
 369
 370       (*node)->value = value;
 371     }
 372   else
 373     {
 374       *node = g_hash_node_new (key, value);
 375       hash_table->nnodes++;
 376       G_HASH_TABLE_RESIZE (hash_table);
 377     }
 378 }
 379
 380 #if 0
 381
 382 /**
 383  * g_hash_table_replace:
 384  * @hash_table: a #GHashTable.
 385  * @key: a key to insert.
 386  * @value: the value to associate with the key.
 387  *
 388  * Inserts a new key and value into a #GHashTable similar to
 389  * g_hash_table_insert(). The difference is that if the key already exists
 390  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 391  * @value_destroy_func when creating the #GHashTable, the old value is freed
 392  * using that function. If you supplied a @key_destroy_func when creating the
 393  * #GHashTable, the old key is freed using that function.
 394  **/
 395 void
 396 g_hash_table_replace (GHashTable *hash_table,
 397                       gpointer    key,
 398                       gpointer    value)
 399 {
 400   GHashNode **node;
 401
 402   g_return_if_fail (hash_table != NULL);
 403   g_return_if_fail (hash_table->ref_count > 0);
 404
 405   node = g_hash_table_lookup_node (hash_table, key);
 406
 407   if (*node)
 408     {
 409       if (hash_table->key_destroy_func)
 410         hash_table->key_destroy_func ((*node)->key);
 411
 412       if (hash_table->value_destroy_func)
 413         hash_table->value_destroy_func ((*node)->value);
 414
 415       (*node)->key   = key;
 416       (*node)->value = value;
 417     }
 418   else
 419     {
 420       *node = g_hash_node_new (key, value);
 421       hash_table->nnodes++;
 422       G_HASH_TABLE_RESIZE (hash_table);
 423     }
 424 }
 425
 426 /**
 427  * g_hash_table_remove:
 428  * @hash_table: a #GHashTable.
 429  * @key: the key to remove.
 430  *
 431  * Removes a key and its associated value from a #GHashTable.
 432  *
 433  * If the #GHashTable was created using g_hash_table_new_full(), the
 434  * key and value are freed using the supplied destroy functions, otherwise
 435  * you have to make sure that any dynamically allocated values are freed
 436  * yourself.
 437  *
 438  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 439  **/
 440 gboolean
 441 g_hash_table_remove (GHashTable    *hash_table,
 442                      gconstpointer  key)
 443 {
 444   GHashNode **node, *dest;
 445
 446   g_return_val_if_fail (hash_table != NULL, FALSE);
 447
 448   node = g_hash_table_lookup_node (hash_table, key);
 449   if (*node)
 450     {
 451       dest = *node;
 452       (*node) = dest->next;
 453       g_hash_node_destroy (dest,
 454                            hash_table->key_destroy_func,
 455                            hash_table->value_destroy_func);
 456       hash_table->nnodes--;
 457
 458       G_HASH_TABLE_RESIZE (hash_table);
 459
 460       return TRUE;
 461     }
 462
 463   return FALSE;
 464 }
 465
 466 /**
 467  * g_hash_table_remove_all:
 468  * @hash_table: a #GHashTable
 469  *
 470  * Removes all keys and their associated values from a #GHashTable.
 471  *
 472  * If the #GHashTable was created using g_hash_table_new_full(), the keys
 473  * and values are freed using the supplied destroy functions, otherwise you
 474  * have to make sure that any dynamically allocated values are freed
 475  * yourself.
 476  *
 477  * Since: 2.12
 478  **/
 479 void
 480 g_hash_table_remove_all (GHashTable *hash_table)
 481 {
 482   guint i;
 483
 484   g_return_if_fail (hash_table != NULL);
 485
 486   for (i = 0; i < hash_table->size; i++)
 487     {
 488       g_hash_nodes_destroy (hash_table->nodes[i],
 489                             hash_table->key_destroy_func,
 490                             hash_table->value_destroy_func);
 491       hash_table->nodes[i] = NULL;
 492     }
 493   hash_table->nnodes = 0;
 494
 495   G_HASH_TABLE_RESIZE (hash_table);
 496 }
 497
 498 /**
 499  * g_hash_table_steal:
 500  * @hash_table: a #GHashTable.
 501  * @key: the key to remove.
 502  *
 503  * Removes a key and its associated value from a #GHashTable without
 504  * calling the key and value destroy functions.
 505  *
 506  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 507  **/
 508 gboolean
 509 g_hash_table_steal (GHashTable    *hash_table,
 510                     gconstpointer  key)
 511 {
 512   GHashNode **node, *dest;
 513
 514   g_return_val_if_fail (hash_table != NULL, FALSE);
 515
 516   node = g_hash_table_lookup_node (hash_table, key);
 517   if (*node)
 518     {
 519       dest = *node;
 520       (*node) = dest->next;
 521       g_hash_node_destroy (dest, NULL, NULL);
 522       hash_table->nnodes--;
 523
 524       G_HASH_TABLE_RESIZE (hash_table);
 525
 526       return TRUE;
 527     }
 528
 529   return FALSE;
 530 }
 531
 532 /**
 533  * g_hash_table_steal_all:
 534  * @hash_table: a #GHashTable.
 535  *
 536  * Removes all keys and their associated values from a #GHashTable
 537  * without calling the key and value destroy functions.
 538  *
 539  * Since: 2.12
 540  **/
 541 void
 542 g_hash_table_steal_all (GHashTable *hash_table)
 543 {
 544   guint i;
 545
 546   g_return_if_fail (hash_table != NULL);
 547
 548   for (i = 0; i < hash_table->size; i++)
 549     {
 550       g_hash_nodes_destroy (hash_table->nodes[i], NULL, NULL);
 551       hash_table->nodes[i] = NULL;
 552     }
 553
 554   hash_table->nnodes = 0;
 555
 556   G_HASH_TABLE_RESIZE (hash_table);
 557 }
 558
 559 /**
 560  * g_hash_table_foreach_remove:
 561  * @hash_table: a #GHashTable.
 562  * @func: the function to call for each key/value pair.
 563  * @user_data: user data to pass to the function.
 564  *
 565  * Calls the given function for each key/value pair in the #GHashTable.
 566  * If the function returns %TRUE, then the key/value pair is removed from the
 567  * #GHashTable. If you supplied key or value destroy functions when creating
 568  * the #GHashTable, they are used to free the memory allocated for the removed
 569  * keys and values.
 570  *
 571  * Return value: the number of key/value pairs removed.
 572  **/
 573 guint
 574 g_hash_table_foreach_remove (GHashTable *hash_table,
 575                              GHRFunc     func,
 576                              gpointer    user_data)
 577 {
 578   g_return_val_if_fail (hash_table != NULL, 0);
 579   g_return_val_if_fail (func != NULL, 0);
 580
 581   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
 582 }
 583
 584 /**
 585  * g_hash_table_foreach_steal:
 586  * @hash_table: a #GHashTable.
 587  * @func: the function to call for each key/value pair.
 588  * @user_data: user data to pass to the function.
 589  *
 590  * Calls the given function for each key/value pair in the #GHashTable.
 591  * If the function returns %TRUE, then the key/value pair is removed from the
 592  * #GHashTable, but no key or value destroy functions are called.
 593  *
 594  * Return value: the number of key/value pairs removed.
 595  **/
 596 guint
 597 g_hash_table_foreach_steal (GHashTable *hash_table,
 598                             GHRFunc     func,
 599                             gpointer    user_data)
 600 {
 601   g_return_val_if_fail (hash_table != NULL, 0);
 602   g_return_val_if_fail (func != NULL, 0);
 603
 604   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
 605 }
 606
 607 static guint
 608 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 609                                       GHRFunc     func,
 610                                       gpointer    user_data,
 611                                       gboolean    notify)
 612 {
 613   GHashNode *node, *prev;
 614   gint i;
 615   guint deleted = 0;
 616
 617   for (i = 0; i < hash_table->size; i++)
 618     {
 619     restart:
 620
 621       prev = NULL;
 622
 623       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
 624         {
 625           if ((* func) (node->key, node->value, user_data))
 626             {
 627               deleted += 1;
 628
 629               hash_table->nnodes -= 1;
 630
 631               if (prev)
 632                 {
 633                   prev->next = node->next;
 634                   g_hash_node_destroy (node,
 635                                        notify ? hash_table->key_destroy_func : NULL,
 636                                        notify ? hash_table->value_destroy_func : NULL);
 637                   node = prev;
 638                 }
 639               else
 640                 {
 641                   hash_table->nodes[i] = node->next;
 642                   g_hash_node_destroy (node,
 643                                        notify ? hash_table->key_destroy_func : NULL,
 644                                        notify ? hash_table->value_destroy_func : NULL);
 645                   goto restart;
 646                 }
 647             }
 648         }
 649     }
 650
 651   G_HASH_TABLE_RESIZE (hash_table);
 652
 653   return deleted;
 654 }
 655
 656 /**
 657  * g_hash_table_foreach:
 658  * @hash_table: a #GHashTable.
 659  * @func: the function to call for each key/value pair.
 660  * @user_data: user data to pass to the function.
 661  *
 662  * Calls the given function for each of the key/value pairs in the
 663  * #GHashTable.  The function is passed the key and value of each
 664  * pair, and the given @user_data parameter.  The hash table may not
 665  * be modified while iterating over it (you can't add/remove
 666  * items). To remove all items matching a predicate, use
 667  * g_hash_table_foreach_remove().
 668  **/
 669 void
 670 g_hash_table_foreach (GHashTable *hash_table,
 671                       GHFunc      func,
 672                       gpointer    user_data)
 673 {
 674   GHashNode *node;
 675   gint i;
 676
 677   g_return_if_fail (hash_table != NULL);
 678   g_return_if_fail (func != NULL);
 679
 680   for (i = 0; i < hash_table->size; i++)
 681     for (node = hash_table->nodes[i]; node; node = node->next)
 682       (* func) (node->key, node->value, user_data);
 683 }
 684
 685 /**
 686  * g_hash_table_find:
 687  * @hash_table: a #GHashTable.
 688  * @predicate:  function to test the key/value pairs for a certain property.
 689  * @user_data:  user data to pass to the function.
 690  *
 691  * Calls the given function for key/value pairs in the #GHashTable until
 692  * @predicate returns %TRUE.  The function is passed the key and value of
 693  * each pair, and the given @user_data parameter. The hash table may not
 694  * be modified while iterating over it (you can't add/remove items).
 695  *
 696  * Return value: The value of the first key/value pair is returned, for which
 697  * func evaluates to %TRUE. If no pair with the requested property is found,
 698  * %NULL is returned.
 699  *
 700  * Since: 2.4
 701  **/
 702 gpointer
 703 g_hash_table_find (GHashTable      *hash_table,
 704                    GHRFunc          predicate,
 705                    gpointer         user_data)
 706 {
 707   GHashNode *node;
 708   gint i;
 709
 710   g_return_val_if_fail (hash_table != NULL, NULL);
 711   g_return_val_if_fail (predicate != NULL, NULL);
 712
 713   for (i = 0; i < hash_table->size; i++)
 714     for (node = hash_table->nodes[i]; node; node = node->next)
 715       if (predicate (node->key, node->value, user_data))
 716         return node->value;
 717   return NULL;
 718 }
 719
 720 /**
 721  * g_hash_table_size:
 722  * @hash_table: a #GHashTable.
 723  *
 724  * Returns the number of elements contained in the #GHashTable.
 725  *
 726  * Return value: the number of key/value pairs in the #GHashTable.
 727  **/
 728 guint
 729 g_hash_table_size (GHashTable *hash_table)
 730 {
 731   g_return_val_if_fail (hash_table != NULL, 0);
 732
 733   return hash_table->nnodes;
 734 }
 735
 736 #endif
 737
 738 static void
 739 g_hash_table_resize (GHashTable *hash_table)
 740 {
 741   GHashNode **new_nodes;
 742   GHashNode *node;
 743   GHashNode *next;
 744   guint hash_val;
 745   gint new_size;
 746   gint i;
 747
 748   new_size = g_spaced_primes_closest (hash_table->nnodes);
 749   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 750
 751   new_nodes = g_new0 (GHashNode*, new_size);
 752
 753   for (i = 0; i < hash_table->size; i++)
 754     for (node = hash_table->nodes[i]; node; node = next)
 755       {
 756         next = node->next;
 757
 758         hash_val = (* hash_table->hash_func) (node->key) % new_size;
 759
 760         node->next = new_nodes[hash_val];
 761         new_nodes[hash_val] = node;
 762       }
 763
 764   g_free (hash_table->nodes);
 765   hash_table->nodes = new_nodes;
 766   hash_table->size = new_size;
 767 }
 768
 769 static GHashNode*
 770 g_hash_node_new (gpointer key,
 771                  gpointer value)
 772 {
 773   GHashNode *hash_node = g_slice_new (GHashNode);
 774
 775   hash_node->key = key;
 776   hash_node->value = value;
 777   hash_node->next = NULL;
 778
 779   return hash_node;
 780 }
 781
 782 #if 0
 783
 784 static void
 785 g_hash_node_destroy (GHashNode      *hash_node,
 786                      GDestroyNotify  key_destroy_func,
 787                      GDestroyNotify  value_destroy_func)
 788 {
 789   if (key_destroy_func)
 790     key_destroy_func (hash_node->key);
 791   if (value_destroy_func)
 792     value_destroy_func (hash_node->value);
 793   g_slice_free (GHashNode, hash_node);
 794 }
 795
 796 static void
 797 g_hash_nodes_destroy (GHashNode *hash_node,
 798                       GFreeFunc  key_destroy_func,
 799                       GFreeFunc  value_destroy_func)
 800 {
 801   while (hash_node)
 802     {
 803       GHashNode *next = hash_node->next;
 804       if (key_destroy_func)
 805         key_destroy_func (hash_node->key);
 806       if (value_destroy_func)
 807         value_destroy_func (hash_node->value);
 808       g_slice_free (GHashNode, hash_node);
 809       hash_node = next;
 810     }
 811 }
 812
 813
 814 #define __G_HASH_C__
 815 #include "galiasdef.c"
 816 #endif