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