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 guint   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       guint i;
 194       for (i = 0; i < hash_table->size; i++)
 195         g_hash_nodes_destroy (hash_table->nodes[i],
 196                               hash_table->key_destroy_func,
 197                               hash_table->value_destroy_func);
 198       g_free (hash_table->nodes);
 199       g_slice_free (GHashTable, hash_table);
 200     }
 201 }
 202
 203 /**
 204  * g_hash_table_destroy:
 205  * @hash_table: a #GHashTable.
 206  *
 207  * Destroys all keys and values in the #GHashTable and decrements its
 208  * reference count by 1. If keys and/or values are dynamically allocated,
 209  * you should either free them first or create the #GHashTable with destroy
 210  * notifiers using g_hash_table_new_full(). In the latter case the destroy
 211  * functions you supplied will be called on all keys and values during the
 212  * destruction phase.
 213  **/
 214 void
 215 g_hash_table_destroy (GHashTable *hash_table)
 216 {
 217   guint i;
 218
 219   g_return_if_fail (hash_table != NULL);
 220   g_return_if_fail (hash_table->ref_count > 0);
 221
 222   for (i = 0; i < hash_table->size; i++)
 223     {
 224       g_hash_nodes_destroy (hash_table->nodes[i],
 225                             hash_table->key_destroy_func,
 226                             hash_table->value_destroy_func);
 227       hash_table->nodes[i] = NULL;
 228     }
 229   hash_table->nnodes = 0;
 230   hash_table->size = HASH_TABLE_MIN_SIZE;
 231
 232   g_hash_table_unref (hash_table);
 233 }
 234
 235 static inline GHashNode**
 236 g_hash_table_lookup_node (GHashTable    *hash_table,
 237                           gconstpointer  key)
 238 {
 239   GHashNode **node;
 240
 241   node = &hash_table->nodes
 242     [(* hash_table->hash_func) (key) % hash_table->size];
 243
 244   /* Hash table lookup needs to be fast.
 245    *  We therefore remove the extra conditional of testing
 246    *  whether to call the key_equal_func or not from
 247    *  the inner loop.
 248    */
 249   if (hash_table->key_equal_func)
 250     while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
 251       node = &(*node)->next;
 252   else
 253     while (*node && (*node)->key != key)
 254       node = &(*node)->next;
 255
 256   return node;
 257 }
 258
 259 /**
 260  * g_hash_table_lookup:
 261  * @hash_table: a #GHashTable.
 262  * @key: the key to look up.
 263  *
 264  * Looks up a key in a #GHashTable. Note that this function cannot
 265  * distinguish between a key that is not present and one which is present
 266  * and has the value %NULL. If you need this distinction, use
 267  * g_hash_table_lookup_extended().
 268  *
 269  * Return value: the associated value, or %NULL if the key is not found.
 270  **/
 271 gpointer
 272 g_hash_table_lookup (GHashTable   *hash_table,
 273                      gconstpointer key)
 274 {
 275   GHashNode *node;
 276
 277   g_return_val_if_fail (hash_table != NULL, NULL);
 278
 279   node = *g_hash_table_lookup_node (hash_table, key);
 280
 281   return node ? node->value : NULL;
 282 }
 283
 284 /**
 285  * g_hash_table_lookup_extended:
 286  * @hash_table: a #GHashTable.
 287  * @lookup_key: the key to look up.
 288  * @orig_key: returns the original key.
 289  * @value: returns the value associated with the key.
 290  *
 291  * Looks up a key in the #GHashTable, returning the original key and the
 292  * associated value and a #gboolean which is %TRUE if the key was found. This
 293  * is useful if you need to free the memory allocated for the original key,
 294  * for example before calling g_hash_table_remove().
 295  *
 296  * Return value: %TRUE if the key was found in the #GHashTable.
 297  **/
 298 gboolean
 299 g_hash_table_lookup_extended (GHashTable    *hash_table,
 300                               gconstpointer  lookup_key,
 301                               gpointer      *orig_key,
 302                               gpointer      *value)
 303 {
 304   GHashNode *node;
 305
 306   g_return_val_if_fail (hash_table != NULL, FALSE);
 307
 308   node = *g_hash_table_lookup_node (hash_table, lookup_key);
 309
 310   if (node)
 311     {
 312       if (orig_key)
 313         *orig_key = node->key;
 314       if (value)
 315         *value = node->value;
 316       return TRUE;
 317     }
 318   else
 319     return FALSE;
 320 }
 321
 322 /**
 323  * g_hash_table_insert:
 324  * @hash_table: a #GHashTable.
 325  * @key: a key to insert.
 326  * @value: the value to associate with the key.
 327  *
 328  * Inserts a new key and value into a #GHashTable.
 329  *
 330  * If the key already exists in the #GHashTable its current value is replaced
 331  * with the new value. If you supplied a @value_destroy_func when creating the
 332  * #GHashTable, the old value is freed using that function. If you supplied
 333  * a @key_destroy_func when creating the #GHashTable, the passed key is freed
 334  * using that function.
 335  **/
 336 void
 337 g_hash_table_insert (GHashTable *hash_table,
 338                      gpointer    key,
 339                      gpointer    value)
 340 {
 341   GHashNode **node;
 342
 343   g_return_if_fail (hash_table != NULL);
 344   g_return_if_fail (hash_table->ref_count > 0);
 345
 346   node = g_hash_table_lookup_node (hash_table, key);
 347
 348   if (*node)
 349     {
 350       /* do not reset node->key in this place, keeping
 351        * the old key is the intended behaviour.
 352        * g_hash_table_replace() can be used instead.
 353        */
 354
 355       /* free the passed key */
 356       if (hash_table->key_destroy_func)
 357         hash_table->key_destroy_func (key);
 358
 359       if (hash_table->value_destroy_func)
 360         hash_table->value_destroy_func ((*node)->value);
 361
 362       (*node)->value = value;
 363     }
 364   else
 365     {
 366       *node = g_hash_node_new (key, value);
 367       hash_table->nnodes++;
 368       G_HASH_TABLE_RESIZE (hash_table);
 369     }
 370 }
 371
 372 /**
 373  * g_hash_table_replace:
 374  * @hash_table: a #GHashTable.
 375  * @key: a key to insert.
 376  * @value: the value to associate with the key.
 377  *
 378  * Inserts a new key and value into a #GHashTable similar to
 379  * g_hash_table_insert(). The difference is that if the key already exists
 380  * in the #GHashTable, it gets replaced by the new key. If you supplied a
 381  * @value_destroy_func when creating the #GHashTable, the old value is freed
 382  * using that function. If you supplied a @key_destroy_func when creating the
 383  * #GHashTable, the old key is freed using that function.
 384  **/
 385 void
 386 g_hash_table_replace (GHashTable *hash_table,
 387                       gpointer    key,
 388                       gpointer    value)
 389 {
 390   GHashNode **node;
 391
 392   g_return_if_fail (hash_table != NULL);
 393   g_return_if_fail (hash_table->ref_count > 0);
 394
 395   node = g_hash_table_lookup_node (hash_table, key);
 396
 397   if (*node)
 398     {
 399       if (hash_table->key_destroy_func)
 400         hash_table->key_destroy_func ((*node)->key);
 401
 402       if (hash_table->value_destroy_func)
 403         hash_table->value_destroy_func ((*node)->value);
 404
 405       (*node)->key   = key;
 406       (*node)->value = value;
 407     }
 408   else
 409     {
 410       *node = g_hash_node_new (key, value);
 411       hash_table->nnodes++;
 412       G_HASH_TABLE_RESIZE (hash_table);
 413     }
 414 }
 415
 416 /**
 417  * g_hash_table_remove:
 418  * @hash_table: a #GHashTable.
 419  * @key: the key to remove.
 420  *
 421  * Removes a key and its associated value from a #GHashTable.
 422  *
 423  * If the #GHashTable was created using g_hash_table_new_full(), the
 424  * key and value are freed using the supplied destroy functions, otherwise
 425  * you have to make sure that any dynamically allocated values are freed
 426  * yourself.
 427  *
 428  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 429  **/
 430 gboolean
 431 g_hash_table_remove (GHashTable    *hash_table,
 432                      gconstpointer  key)
 433 {
 434   GHashNode **node, *dest;
 435
 436   g_return_val_if_fail (hash_table != NULL, FALSE);
 437
 438   node = g_hash_table_lookup_node (hash_table, key);
 439   if (*node)
 440     {
 441       dest = *node;
 442       (*node) = dest->next;
 443       g_hash_node_destroy (dest,
 444                            hash_table->key_destroy_func,
 445                            hash_table->value_destroy_func);
 446       hash_table->nnodes--;
 447
 448       G_HASH_TABLE_RESIZE (hash_table);
 449
 450       return TRUE;
 451     }
 452
 453   return FALSE;
 454 }
 455
 456 /**
 457  * g_hash_table_steal:
 458  * @hash_table: a #GHashTable.
 459  * @key: the key to remove.
 460  *
 461  * Removes a key and its associated value from a #GHashTable without
 462  * calling the key and value destroy functions.
 463  *
 464  * Return value: %TRUE if the key was found and removed from the #GHashTable.
 465  **/
 466 gboolean
 467 g_hash_table_steal (GHashTable    *hash_table,
 468                     gconstpointer  key)
 469 {
 470   GHashNode **node, *dest;
 471
 472   g_return_val_if_fail (hash_table != NULL, FALSE);
 473
 474   node = g_hash_table_lookup_node (hash_table, key);
 475   if (*node)
 476     {
 477       dest = *node;
 478       (*node) = dest->next;
 479       g_hash_node_destroy (dest, NULL, NULL);
 480       hash_table->nnodes--;
 481
 482       G_HASH_TABLE_RESIZE (hash_table);
 483
 484       return TRUE;
 485     }
 486
 487   return FALSE;
 488 }
 489
 490 /**
 491  * g_hash_table_foreach_remove:
 492  * @hash_table: a #GHashTable.
 493  * @func: the function to call for each key/value pair.
 494  * @user_data: user data to pass to the function.
 495  *
 496  * Calls the given function for each key/value pair in the #GHashTable.
 497  * If the function returns %TRUE, then the key/value pair is removed from the
 498  * #GHashTable. If you supplied key or value destroy functions when creating
 499  * the #GHashTable, they are used to free the memory allocated for the removed
 500  * keys and values.
 501  *
 502  * Return value: the number of key/value pairs removed.
 503  **/
 504 guint
 505 g_hash_table_foreach_remove (GHashTable *hash_table,
 506                              GHRFunc     func,
 507                              gpointer    user_data)
 508 {
 509   g_return_val_if_fail (hash_table != NULL, 0);
 510   g_return_val_if_fail (func != NULL, 0);
 511
 512   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
 513 }
 514
 515 /**
 516  * g_hash_table_foreach_steal:
 517  * @hash_table: a #GHashTable.
 518  * @func: the function to call for each key/value pair.
 519  * @user_data: user data to pass to the function.
 520  *
 521  * Calls the given function for each key/value pair in the #GHashTable.
 522  * If the function returns %TRUE, then the key/value pair is removed from the
 523  * #GHashTable, but no key or value destroy functions are called.
 524  *
 525  * Return value: the number of key/value pairs removed.
 526  **/
 527 guint
 528 g_hash_table_foreach_steal (GHashTable *hash_table,
 529                             GHRFunc     func,
 530                             gpointer    user_data)
 531 {
 532   g_return_val_if_fail (hash_table != NULL, 0);
 533   g_return_val_if_fail (func != NULL, 0);
 534
 535   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
 536 }
 537
 538 static guint
 539 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
 540                                       GHRFunc     func,
 541                                       gpointer    user_data,
 542                                       gboolean    notify)
 543 {
 544   GHashNode *node, *prev;
 545   guint i;
 546   guint deleted = 0;
 547
 548   for (i = 0; i < hash_table->size; i++)
 549     {
 550     restart:
 551
 552       prev = NULL;
 553
 554       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
 555         {
 556           if ((* func) (node->key, node->value, user_data))
 557             {
 558               deleted += 1;
 559
 560               hash_table->nnodes -= 1;
 561
 562               if (prev)
 563                 {
 564                   prev->next = node->next;
 565                   g_hash_node_destroy (node,
 566                                        notify ? hash_table->key_destroy_func : NULL,
 567                                        notify ? hash_table->value_destroy_func : NULL);
 568                   node = prev;
 569                 }
 570               else
 571                 {
 572                   hash_table->nodes[i] = node->next;
 573                   g_hash_node_destroy (node,
 574                                        notify ? hash_table->key_destroy_func : NULL,
 575                                        notify ? hash_table->value_destroy_func : NULL);
 576                   goto restart;
 577                 }
 578             }
 579         }
 580     }
 581
 582   G_HASH_TABLE_RESIZE (hash_table);
 583
 584   return deleted;
 585 }
 586
 587 /**
 588  * g_hash_table_foreach:
 589  * @hash_table: a #GHashTable.
 590  * @func: the function to call for each key/value pair.
 591  * @user_data: user data to pass to the function.
 592  *
 593  * Calls the given function for each of the key/value pairs in the
 594  * #GHashTable.  The function is passed the key and value of each
 595  * pair, and the given @user_data parameter.  The hash table may not
 596  * be modified while iterating over it (you can't add/remove
 597  * items). To remove all items matching a predicate, use
 598  * g_hash_table_foreach_remove().
 599  **/
 600 void
 601 g_hash_table_foreach (GHashTable *hash_table,
 602                       GHFunc      func,
 603                       gpointer    user_data)
 604 {
 605   GHashNode *node;
 606   gint i;
 607
 608   g_return_if_fail (hash_table != NULL);
 609   g_return_if_fail (func != NULL);
 610
 611   for (i = 0; i < hash_table->size; i++)
 612     for (node = hash_table->nodes[i]; node; node = node->next)
 613       (* func) (node->key, node->value, user_data);
 614 }
 615
 616 /**
 617  * g_hash_table_find:
 618  * @hash_table: a #GHashTable.
 619  * @predicate:  function to test the key/value pairs for a certain property.
 620  * @user_data:  user data to pass to the function.
 621  *
 622  * Calls the given function for key/value pairs in the #GHashTable until
 623  * @predicate returns %TRUE.  The function is passed the key and value of
 624  * each pair, and the given @user_data parameter. The hash table may not
 625  * be modified while iterating over it (you can't add/remove items).
 626  *
 627  * Return value: The value of the first key/value pair is returned, for which
 628  * func evaluates to %TRUE. If no pair with the requested property is found,
 629  * %NULL is returned.
 630  *
 631  * Since: 2.4
 632  **/
 633 gpointer
 634 g_hash_table_find (GHashTable      *hash_table,
 635                    GHRFunc          predicate,
 636                    gpointer         user_data)
 637 {
 638   GHashNode *node;
 639   gint i;
 640
 641   g_return_val_if_fail (hash_table != NULL, NULL);
 642   g_return_val_if_fail (predicate != NULL, NULL);
 643
 644   for (i = 0; i < hash_table->size; i++)
 645     for (node = hash_table->nodes[i]; node; node = node->next)
 646       if (predicate (node->key, node->value, user_data))
 647         return node->value;
 648   return NULL;
 649 }
 650
 651 /**
 652  * g_hash_table_size:
 653  * @hash_table: a #GHashTable.
 654  *
 655  * Returns the number of elements contained in the #GHashTable.
 656  *
 657  * Return value: the number of key/value pairs in the #GHashTable.
 658  **/
 659 guint
 660 g_hash_table_size (GHashTable *hash_table)
 661 {
 662   g_return_val_if_fail (hash_table != NULL, 0);
 663
 664   return hash_table->nnodes;
 665 }
 666
 667 static void
 668 g_hash_table_resize (GHashTable *hash_table)
 669 {
 670   GHashNode **new_nodes;
 671   GHashNode *node;
 672   GHashNode *next;
 673   guint hash_val;
 674   gint new_size;
 675   gint i;
 676
 677   new_size = g_spaced_primes_closest (hash_table->nnodes);
 678   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 679
 680   new_nodes = g_new0 (GHashNode*, new_size);
 681
 682   for (i = 0; i < hash_table->size; i++)
 683     for (node = hash_table->nodes[i]; node; node = next)
 684       {
 685         next = node->next;
 686
 687         hash_val = (* hash_table->hash_func) (node->key) % new_size;
 688
 689         node->next = new_nodes[hash_val];
 690         new_nodes[hash_val] = node;
 691       }
 692
 693   g_free (hash_table->nodes);
 694   hash_table->nodes = new_nodes;
 695   hash_table->size = new_size;
 696 }
 697
 698 static GHashNode*
 699 g_hash_node_new (gpointer key,
 700                  gpointer value)
 701 {
 702   GHashNode *hash_node = g_slice_new (GHashNode);
 703
 704   hash_node->key = key;
 705   hash_node->value = value;
 706   hash_node->next = NULL;
 707
 708   return hash_node;
 709 }
 710
 711 static void
 712 g_hash_node_destroy (GHashNode      *hash_node,
 713                      GDestroyNotify  key_destroy_func,
 714                      GDestroyNotify  value_destroy_func)
 715 {
 716   if (key_destroy_func)
 717     key_destroy_func (hash_node->key);
 718   if (value_destroy_func)
 719     value_destroy_func (hash_node->value);
 720
 721 #ifdef ENABLE_GC_FRIENDLY
 722   hash_node->key = NULL;
 723   hash_node->value = NULL;
 724 #endif /* ENABLE_GC_FRIENDLY */
 725
 726   g_slice_free (GHashNode, hash_node);
 727 }
 728
 729 static void
 730 g_hash_nodes_destroy (GHashNode *hash_node,
 731                       GFreeFunc  key_destroy_func,
 732                       GFreeFunc  value_destroy_func)
 733 {
 734   while (hash_node)
 735     {
 736       GHashNode *next = hash_node->next;
 737       if (key_destroy_func)
 738         key_destroy_func (hash_node->key);
 739       if (value_destroy_func)
 740         value_destroy_func (hash_node->value);
 741       g_slice_free (GHashNode, hash_node);
 742       hash_node = next;
 743     }
 744 }
 745
 746
 747 #define __G_HASH_C__
 748 #include "galiasdef.c"