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