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