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