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