mono/metadata/mono-hash.c

   1 /**
   2  * \file
   3  * Hashtable implementation
   4  *
   5  * Author:
   6  *   Miguel de Icaza (miguel@novell.com)
   7  *
   8  * (C) 2006 Novell, Inc.
   9  *
  10  * Permission is hereby granted, free of charge, to any person obtaining
  11  * a copy of this software and associated documentation files (the
  12  * "Software"), to deal in the Software without restriction, including
  13  * without limitation the rights to use, copy, modify, merge, publish,
  14  * distribute, sublicense, and/or sell copies of the Software, and to
  15  * permit persons to whom the Software is furnished to do so, subject to
  16  * the following conditions:
  17  *
  18  * The above copyright notice and this permission notice shall be
  19  * included in all copies or substantial portions of the Software.
  20  *
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28  */
  29 #include <config.h>
  30 #include <stdio.h>
  31 #include <math.h>
  32 #include <glib.h>
  33 #include "mono-hash.h"
  34 #include "metadata/gc-internals.h"
  35 #include <mono/utils/checked-build.h>
  36 #include <mono/utils/mono-threads-coop.h>
  37
  38 int mono_g_hash_table_max_chain_length;
  39
  40 #ifdef HAVE_BOEHM_GC
  41 #define mg_new0(type,n)  ((type *) GC_MALLOC(sizeof(type) * (n)))
  42 #define mg_new(type,n)   ((type *) GC_MALLOC(sizeof(type) * (n)))
  43 #define mg_free(x)       do { } while (0)
  44 #else
  45 #define mg_new0(x,n)     g_new0(x,n)
  46 #define mg_new(type,n)   g_new(type,n)
  47 #define mg_free(x)       g_free(x)
  48 #endif
  49
  50 struct _MonoGHashTable {
  51         GHashFunc      hash_func;
  52         GEqualFunc     key_equal_func;
  53
  54         MonoObject **keys;
  55         MonoObject **values;
  56         int   table_size;
  57         int   in_use;
  58         GDestroyNotify value_destroy_func, key_destroy_func;
  59         MonoGHashGCType gc_type;
  60         MonoGCRootSource source;
  61         const char *msg;
  62 };
  63
  64 #if UNUSED
  65 static gboolean
  66 test_prime (int x)
  67 {
  68         if ((x & 1) != 0) {
  69                 int n;
  70                 for (n = 3; n< (int)sqrt (x); n += 2) {
  71                         if ((x % n) == 0)
  72                                 return FALSE;
  73                 }
  74                 return TRUE;
  75         }
  76         // There is only one even prime - 2.
  77         return (x == 2);
  78 }
  79
  80 static int
  81 calc_prime (int x)
  82 {
  83         int i;
  84
  85         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
  86                 if (test_prime (i))
  87                         return i;
  88         }
  89         return x;
  90 }
  91 #endif
  92
  93 #define HASH_TABLE_MAX_LOAD_FACTOR 0.7f
  94 /* We didn't really do compaction before, keep it lenient for now */
  95 #define HASH_TABLE_MIN_LOAD_FACTOR 0.05f
  96 /* We triple the table size at rehash time, similar with previous implementation */
  97 #define HASH_TABLE_RESIZE_RATIO 3
  98
  99 static inline void mono_g_hash_table_key_store (MonoGHashTable *hash, int slot, MonoObject* key)
 100 {
 101         MonoObject **key_addr = &hash->keys [slot];
 102         if (hash->gc_type & MONO_HASH_KEY_GC)
 103                 mono_gc_wbarrier_generic_store (key_addr, key);
 104         else
 105                 *key_addr = key;
 106 }
 107
 108 static inline void mono_g_hash_table_value_store (MonoGHashTable *hash, int slot, MonoObject* value)
 109 {
 110         MonoObject **value_addr = &hash->values [slot];
 111         if (hash->gc_type & MONO_HASH_VALUE_GC)
 112                 mono_gc_wbarrier_generic_store (value_addr, value);
 113         else
 114                 *value_addr = value;
 115 }
 116
 117 /* Returns position of key or of an empty slot for it */
 118 static inline int mono_g_hash_table_find_slot (MonoGHashTable *hash, const MonoObject *key)
 119 {
 120         guint start = ((*hash->hash_func) (key)) % hash->table_size;
 121         guint i = start;
 122
 123         if (hash->key_equal_func) {
 124                 GEqualFunc equal = hash->key_equal_func;
 125
 126                 while (hash->keys [i] && !(*equal) (hash->keys [i], key)) {
 127                         i++;
 128                         if (i == hash->table_size)
 129                                 i = 0;
 130                 }
 131         } else {
 132                 while (hash->keys [i] && hash->keys [i] != key) {
 133                         i++;
 134                         if (i == hash->table_size)
 135                                 i = 0;
 136                 }
 137         }
 138
 139         if (i > start && (i - start) > mono_g_hash_table_max_chain_length)
 140                 mono_g_hash_table_max_chain_length = i - start;
 141         else if (i < start && (hash->table_size - (start - i)) > mono_g_hash_table_max_chain_length)
 142                 mono_g_hash_table_max_chain_length = hash->table_size - (start - i);
 143         return i;
 144 }
 145
 146
 147 MonoGHashTable *
 148 mono_g_hash_table_new_type (GHashFunc hash_func, GEqualFunc key_equal_func, MonoGHashGCType type, MonoGCRootSource source, const char *msg)
 149 {
 150         MonoGHashTable *hash;
 151
 152         if (!hash_func)
 153                 hash_func = g_direct_hash;
 154
 155 #ifdef HAVE_SGEN_GC
 156         hash = mg_new0 (MonoGHashTable, 1);
 157 #else
 158         hash = mono_gc_alloc_fixed (sizeof (MonoGHashTable), MONO_GC_ROOT_DESCR_FOR_FIXED (sizeof (MonoGHashTable)), source, msg);
 159 #endif
 160
 161         hash->hash_func = hash_func;
 162         hash->key_equal_func = key_equal_func;
 163
 164         hash->table_size = g_spaced_primes_closest (1);
 165         hash->keys = mg_new0 (MonoObject*, hash->table_size);
 166         hash->values = mg_new0 (MonoObject*, hash->table_size);
 167
 168         hash->gc_type = type;
 169         hash->source = source;
 170         hash->msg = msg;
 171
 172         if (type > MONO_HASH_KEY_VALUE_GC)
 173                 g_error ("wrong type for gc hashtable");
 174
 175 #ifdef HAVE_SGEN_GC
 176         if (hash->gc_type & MONO_HASH_KEY_GC)
 177                 mono_gc_register_root_wbarrier ((char*)hash->keys, sizeof (MonoObject*) * hash->table_size, mono_gc_make_vector_descr (), hash->source, hash->msg);
 178         if (hash->gc_type & MONO_HASH_VALUE_GC)
 179                 mono_gc_register_root_wbarrier ((char*)hash->values, sizeof (MonoObject*) * hash->table_size, mono_gc_make_vector_descr (), hash->source, hash->msg);
 180 #endif
 181
 182         return hash;
 183 }
 184
 185 typedef struct {
 186         MonoGHashTable *hash;
 187         int new_size;
 188         MonoObject **keys;
 189         MonoObject **values;
 190 } RehashData;
 191
 192 static void*
 193 do_rehash (void *_data)
 194 {
 195         RehashData *data = (RehashData *)_data;
 196         MonoGHashTable *hash = data->hash;
 197         int current_size, i;
 198         MonoObject **old_keys;
 199         MonoObject **old_values;
 200
 201         current_size = hash->table_size;
 202         hash->table_size = data->new_size;
 203         old_keys = hash->keys;
 204         old_values = hash->values;
 205         hash->keys = data->keys;
 206         hash->values = data->values;
 207
 208         for (i = 0; i < current_size; i++) {
 209                 if (old_keys [i]) {
 210                         int slot = mono_g_hash_table_find_slot (hash, old_keys [i]);
 211                         mono_g_hash_table_key_store (hash, slot, old_keys [i]);
 212                         mono_g_hash_table_value_store (hash, slot, old_values [i]);
 213                 }
 214         }
 215         return NULL;
 216 }
 217
 218 static void
 219 rehash (MonoGHashTable *hash)
 220 {
 221         MONO_REQ_GC_UNSAFE_MODE; //we must run in unsafe mode to make rehash safe
 222
 223         RehashData data;
 224         void *old_keys G_GNUC_UNUSED = hash->keys; /* unused on Boehm */
 225         void *old_values G_GNUC_UNUSED = hash->values; /* unused on Boehm */
 226
 227         data.hash = hash;
 228         /*
 229          * Rehash to a size that can fit the current elements. Rehash relative to in_use
 230          * to allow also for compaction.
 231          */
 232         data.new_size = g_spaced_primes_closest (hash->in_use / HASH_TABLE_MAX_LOAD_FACTOR * HASH_TABLE_RESIZE_RATIO);
 233         data.keys = mg_new0 (MonoObject*, data.new_size);
 234         data.values = mg_new0 (MonoObject*, data.new_size);
 235
 236 #ifdef HAVE_SGEN_GC
 237         if (hash->gc_type & MONO_HASH_KEY_GC)
 238                 mono_gc_register_root_wbarrier ((char*)data.keys, sizeof (MonoObject*) * data.new_size, mono_gc_make_vector_descr (), hash->source, hash->msg);
 239         if (hash->gc_type & MONO_HASH_VALUE_GC)
 240                 mono_gc_register_root_wbarrier ((char*)data.values, sizeof (MonoObject*) * data.new_size, mono_gc_make_vector_descr (), hash->source, hash->msg);
 241 #endif
 242
 243         if (!mono_threads_is_coop_enabled ()) {
 244                 mono_gc_invoke_with_gc_lock (do_rehash, &data);
 245         } else {
 246                 /* We cannot be preempted */
 247                 do_rehash (&data);
 248         }
 249
 250 #ifdef HAVE_SGEN_GC
 251         if (hash->gc_type & MONO_HASH_KEY_GC)
 252                 mono_gc_deregister_root ((char*)old_keys);
 253         if (hash->gc_type & MONO_HASH_VALUE_GC)
 254                 mono_gc_deregister_root ((char*)old_values);
 255 #endif
 256         mg_free (old_keys);
 257         mg_free (old_values);
 258 }
 259
 260 /**
 261  * mono_g_hash_table_size:
 262  */
 263 guint
 264 mono_g_hash_table_size (MonoGHashTable *hash)
 265 {
 266         g_return_val_if_fail (hash != NULL, 0);
 267
 268         return hash->in_use;
 269 }
 270
 271 /**
 272  * mono_g_hash_table_lookup:
 273  */
 274 gpointer
 275 mono_g_hash_table_lookup (MonoGHashTable *hash, gconstpointer key)
 276 {
 277         gpointer orig_key, value;
 278
 279         if (mono_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 280                 return value;
 281         else
 282                 return NULL;
 283 }
 284
 285 /**
 286  * mono_g_hash_table_lookup_extended:
 287  */
 288 gboolean
 289 mono_g_hash_table_lookup_extended (MonoGHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 290 {
 291         int slot;
 292
 293         g_return_val_if_fail (hash != NULL, FALSE);
 294
 295         slot = mono_g_hash_table_find_slot (hash, key);
 296
 297         if (hash->keys [slot]) {
 298                 *orig_key = hash->keys [slot];
 299                 *value = hash->values [slot];
 300                 return TRUE;
 301         }
 302
 303         return FALSE;
 304 }
 305
 306 /**
 307  * mono_g_hash_table_foreach:
 308  */
 309 void
 310 mono_g_hash_table_foreach (MonoGHashTable *hash, GHFunc func, gpointer user_data)
 311 {
 312         int i;
 313
 314         g_return_if_fail (hash != NULL);
 315         g_return_if_fail (func != NULL);
 316
 317         for (i = 0; i < hash->table_size; i++) {
 318                 if (hash->keys [i])
 319                         (*func)(hash->keys [i], hash->values [i], user_data);
 320         }
 321 }
 322
 323 gpointer
 324 mono_g_hash_table_find (MonoGHashTable *hash, GHRFunc predicate, gpointer user_data)
 325 {
 326         int i;
 327
 328         g_return_val_if_fail (hash != NULL, NULL);
 329         g_return_val_if_fail (predicate != NULL, NULL);
 330
 331         for (i = 0; i < hash->table_size; i++) {
 332                 if (hash->keys [i] && (*predicate)(hash->keys [i], hash->values [i], user_data))
 333                         return hash->values [i];
 334         }
 335         return NULL;
 336 }
 337
 338 /**
 339  * mono_g_hash_table_remove:
 340  */
 341 gboolean
 342 mono_g_hash_table_remove (MonoGHashTable *hash, gconstpointer key)
 343 {
 344         int slot, last_clear_slot;
 345
 346         g_return_val_if_fail (hash != NULL, FALSE);
 347         slot = mono_g_hash_table_find_slot (hash, key);
 348
 349         if (!hash->keys [slot])
 350                 return FALSE;
 351
 352         if (hash->key_destroy_func)
 353                 (*hash->key_destroy_func)(hash->keys [slot]);
 354         hash->keys [slot] = NULL;
 355         if (hash->value_destroy_func)
 356                 (*hash->value_destroy_func)(hash->values [slot]);
 357         hash->values [slot] = NULL;
 358         hash->in_use--;
 359
 360         /*
 361          * When we insert in the hashtable, if the required position is occupied we
 362          * consecutively try out following positions. In order to be able to find
 363          * if a key exists or not in the array (without traversing the entire hash)
 364          * we maintain the constraint that there can be no free slots between two
 365          * entries that are hashed to the same position. This means that, at search
 366          * time, when we encounter a free slot we can stop looking for collissions.
 367          * Similarly, at remove time, we need to shift all following slots to their
 368          * normal slot, until we reach an empty slot.
 369          */
 370         last_clear_slot = slot;
 371         slot = (slot + 1) % hash->table_size;
 372         while (hash->keys [slot]) {
 373                 guint hashcode = ((*hash->hash_func)(hash->keys [slot])) % hash->table_size;
 374                 /*
 375                  * We try to move the current element to last_clear_slot, but only if
 376                  * it brings it closer to its normal position (hashcode)
 377                  */
 378                 if ((last_clear_slot < slot && (hashcode > slot || hashcode <= last_clear_slot)) ||
 379                                 (last_clear_slot > slot && (hashcode > slot && hashcode <= last_clear_slot))) {
 380                         mono_g_hash_table_key_store (hash, last_clear_slot, hash->keys [slot]);
 381                         mono_g_hash_table_value_store (hash, last_clear_slot, hash->values [slot]);
 382                         hash->keys [slot] = NULL;
 383                         hash->values [slot] = NULL;
 384                         last_clear_slot = slot;
 385                 }
 386                 slot++;
 387                 if (slot == hash->table_size)
 388                         slot = 0;
 389         }
 390         return TRUE;
 391 }
 392
 393 /**
 394  * mono_g_hash_table_foreach_remove:
 395  */
 396 guint
 397 mono_g_hash_table_foreach_remove (MonoGHashTable *hash, GHRFunc func, gpointer user_data)
 398 {
 399         int i;
 400         int count = 0;
 401
 402         g_return_val_if_fail (hash != NULL, 0);
 403         g_return_val_if_fail (func != NULL, 0);
 404
 405         for (i = 0; i < hash->table_size; i++) {
 406                 if (hash->keys [i] && (*func)(hash->keys [i], hash->values [i], user_data)) {
 407                         mono_g_hash_table_remove (hash, hash->keys [i]);
 408                         count++;
 409                         /* Retry current slot in case the removal shifted elements */
 410                         i--;
 411                 }
 412         }
 413         if (hash->in_use < hash->table_size * HASH_TABLE_MIN_LOAD_FACTOR)
 414                 rehash (hash);
 415         return count;
 416 }
 417
 418 /**
 419  * mono_g_hash_table_destroy:
 420  */
 421 void
 422 mono_g_hash_table_destroy (MonoGHashTable *hash)
 423 {
 424         int i;
 425
 426         g_return_if_fail (hash != NULL);
 427
 428 #ifdef HAVE_SGEN_GC
 429         if (hash->gc_type & MONO_HASH_KEY_GC)
 430                 mono_gc_deregister_root ((char*)hash->keys);
 431         if (hash->gc_type & MONO_HASH_VALUE_GC)
 432                 mono_gc_deregister_root ((char*)hash->values);
 433 #endif
 434
 435         for (i = 0; i < hash->table_size; i++) {
 436                 if (hash->keys [i]) {
 437                         if (hash->key_destroy_func)
 438                                 (*hash->key_destroy_func)(hash->keys [i]);
 439                         if (hash->value_destroy_func)
 440                                 (*hash->value_destroy_func)(hash->values [i]);
 441                 }
 442         }
 443         mg_free (hash->keys);
 444         mg_free (hash->values);
 445 #ifdef HAVE_SGEN_GC
 446         mg_free (hash);
 447 #else
 448         mono_gc_free_fixed (hash);
 449 #endif
 450 }
 451
 452 static void
 453 mono_g_hash_table_insert_replace (MonoGHashTable *hash, gpointer key, gpointer value, gboolean replace)
 454 {
 455         int slot;
 456         g_return_if_fail (hash != NULL);
 457
 458         if (hash->in_use > (hash->table_size * HASH_TABLE_MAX_LOAD_FACTOR))
 459                 rehash (hash);
 460
 461         slot = mono_g_hash_table_find_slot (hash, key);
 462
 463         if (hash->keys [slot]) {
 464                 if (replace) {
 465                         if (hash->key_destroy_func)
 466                                 (*hash->key_destroy_func)(hash->keys [slot]);
 467                         mono_g_hash_table_key_store (hash, slot, (MonoObject*)key);
 468                 }
 469                 if (hash->value_destroy_func)
 470                         (*hash->value_destroy_func) (hash->values [slot]);
 471                 mono_g_hash_table_value_store (hash, slot, (MonoObject*)value);
 472         } else {
 473                 mono_g_hash_table_key_store (hash, slot, (MonoObject*)key);
 474                 mono_g_hash_table_value_store (hash, slot, (MonoObject*)value);
 475                 hash->in_use++;
 476         }
 477 }
 478
 479 /**
 480  * mono_g_hash_table_insert:
 481  */
 482 void
 483 mono_g_hash_table_insert (MonoGHashTable *h, gpointer k, gpointer v)
 484 {
 485         mono_g_hash_table_insert_replace (h, k, v, FALSE);
 486 }
 487
 488 /**
 489  * mono_g_hash_table_replace:
 490  */
 491 void
 492 mono_g_hash_table_replace(MonoGHashTable *h, gpointer k, gpointer v)
 493 {
 494         mono_g_hash_table_insert_replace (h, k, v, TRUE);
 495 }
 496
 497 void
 498 mono_g_hash_table_print_stats (MonoGHashTable *hash)
 499 {
 500         int i = 0, chain_size = 0, max_chain_size = 0;
 501         gboolean wrapped_around = FALSE;
 502
 503         while (TRUE) {
 504                 if (hash->keys [i]) {
 505                         chain_size++;
 506                 } else {
 507                         max_chain_size = MAX(max_chain_size, chain_size);
 508                         chain_size = 0;
 509                         if (wrapped_around)
 510                                 break;
 511                 }
 512
 513                 if (i == (hash->table_size - 1)) {
 514                         wrapped_around = TRUE;
 515                         i = 0;
 516                 } else {
 517                         i++;
 518                 }
 519         }
 520         /* Rehash to a size that can fit the current elements */
 521         printf ("Size: %d Table Size: %d Max Chain Length: %d\n", hash->in_use, hash->table_size, max_chain_size);
 522 }