mono/metadata/mono-hash.c

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