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