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