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 typedef struct _Slot Slot;
  48
  49 struct _Slot {
  50         MonoObject *key;
  51         MonoObject *value;
  52         Slot    *next;
  53 };
  54
  55 static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
  56
  57 struct _MonoGHashTable {
  58         GHashFunc      hash_func;
  59         GEqualFunc     key_equal_func;
  60
  61         Slot **table;
  62         int   table_size;
  63         int   in_use;
  64         int   threshold;
  65         int   last_rehash;
  66         GDestroyNotify value_destroy_func, key_destroy_func;
  67         MonoGHashGCType gc_type;
  68         MonoGCRootSource source;
  69         const char *msg;
  70 };
  71
  72 #ifdef HAVE_SGEN_GC
  73 static MonoGCDescriptor table_hash_descr = MONO_GC_DESCRIPTOR_NULL;
  74
  75 static void mono_g_hash_mark (void *addr, MonoGCMarkFunc mark_func, void *gc_data);
  76 #endif
  77
  78 static Slot*
  79 new_slot (MonoGHashTable *hash)
  80 {
  81         return mg_new (Slot, 1);
  82 }
  83
  84 static void
  85 free_slot (MonoGHashTable *hash, Slot *slot)
  86 {
  87         mg_free (slot);
  88 }
  89
  90 #if UNUSED
  91 static gboolean
  92 test_prime (int x)
  93 {
  94         if ((x & 1) != 0) {
  95                 int n;
  96                 for (n = 3; n< (int)sqrt (x); n += 2) {
  97                         if ((x % n) == 0)
  98                                 return FALSE;
  99                 }
 100                 return TRUE;
 101         }
 102         // There is only one even prime - 2.
 103         return (x == 2);
 104 }
 105
 106 static int
 107 calc_prime (int x)
 108 {
 109         int i;
 110
 111         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
 112                 if (test_prime (i))
 113                         return i;
 114         }
 115         return x;
 116 }
 117 #endif
 118
 119 MonoGHashTable *
 120 mono_g_hash_table_new_type (GHashFunc hash_func, GEqualFunc key_equal_func, MonoGHashGCType type, MonoGCRootSource source, const char *msg)
 121 {
 122         MonoGHashTable *hash;
 123
 124         if (hash_func == NULL)
 125                 hash_func = g_direct_hash;
 126         if (key_equal_func == NULL)
 127                 key_equal_func = g_direct_equal;
 128
 129 #ifdef HAVE_SGEN_GC
 130         hash = mg_new0 (MonoGHashTable, 1);
 131 #else
 132         hash = mono_gc_alloc_fixed (sizeof (MonoGHashTable), MONO_GC_ROOT_DESCR_FOR_FIXED (sizeof (MonoGHashTable)), source, msg);
 133 #endif
 134
 135         hash->hash_func = hash_func;
 136         hash->key_equal_func = key_equal_func;
 137
 138         hash->table_size = g_spaced_primes_closest (1);
 139         hash->table = mg_new0 (Slot *, hash->table_size);
 140         hash->last_rehash = hash->table_size;
 141
 142         hash->gc_type = type;
 143         hash->source = source;
 144         hash->msg = msg;
 145
 146         if (type > MONO_HASH_KEY_VALUE_GC)
 147                 g_error ("wrong type for gc hashtable");
 148
 149 #ifdef HAVE_SGEN_GC
 150         /*
 151          * We use a user defined marking function to avoid having to register a GC root for
 152          * each hash node.
 153          */
 154         if (!table_hash_descr)
 155                 table_hash_descr = mono_gc_make_root_descr_user (mono_g_hash_mark);
 156         mono_gc_register_root_wbarrier ((char*)hash, sizeof (MonoGHashTable), table_hash_descr, source, msg);
 157 #endif
 158
 159         return hash;
 160 }
 161
 162 typedef struct {
 163         MonoGHashTable *hash;
 164         int new_size;
 165         Slot **table;
 166 } RehashData;
 167
 168 static void*
 169 do_rehash (void *_data)
 170 {
 171         RehashData *data = (RehashData *)_data;
 172         MonoGHashTable *hash = data->hash;
 173         int current_size, i;
 174         Slot **table;
 175
 176         /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
 177         hash->last_rehash = hash->table_size;
 178         current_size = hash->table_size;
 179         hash->table_size = data->new_size;
 180         /* printf ("New size: %d\n", hash->table_size); */
 181         table = hash->table;
 182         hash->table = data->table;
 183
 184         for (i = 0; i < current_size; i++){
 185                 Slot *s, *next;
 186
 187                 for (s = table [i]; s != NULL; s = next){
 188                         guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
 189                         next = s->next;
 190
 191                         s->next = hash->table [hashcode];
 192                         hash->table [hashcode] = s;
 193                 }
 194         }
 195         return table;
 196 }
 197
 198 static void
 199 rehash (MonoGHashTable *hash)
 200 {
 201         MONO_REQ_GC_UNSAFE_MODE; //we must run in unsafe mode to make rehash safe
 202
 203         int diff = ABS (hash->last_rehash - hash->in_use);
 204         RehashData data;
 205         void *old_table G_GNUC_UNUSED; /* unused on Boehm */
 206
 207         /* These are the factors to play with to change the rehashing strategy */
 208         /* I played with them with a large range, and could not really get */
 209         /* something that was too good, maybe the tests are not that great */
 210         if (!(diff * 0.75 > hash->table_size * 2))
 211                 return;
 212
 213         data.hash = hash;
 214         data.new_size = g_spaced_primes_closest (hash->in_use);
 215         data.table = mg_new0 (Slot *, data.new_size);
 216
 217         if (!mono_threads_is_coop_enabled ()) {
 218                 old_table = mono_gc_invoke_with_gc_lock (do_rehash, &data);
 219         } else {
 220                 /* We cannot be preempted */
 221                 old_table = do_rehash (&data);
 222         }
 223
 224         mg_free (old_table);
 225 }
 226
 227 guint
 228 mono_g_hash_table_size (MonoGHashTable *hash)
 229 {
 230         g_return_val_if_fail (hash != NULL, 0);
 231
 232         return hash->in_use;
 233 }
 234
 235 gpointer
 236 mono_g_hash_table_lookup (MonoGHashTable *hash, gconstpointer key)
 237 {
 238         gpointer orig_key, value;
 239
 240         if (mono_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 241                 return value;
 242         else
 243                 return NULL;
 244 }
 245
 246 gboolean
 247 mono_g_hash_table_lookup_extended (MonoGHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 248 {
 249         GEqualFunc equal;
 250         Slot *s;
 251         guint hashcode;
 252
 253         g_return_val_if_fail (hash != NULL, FALSE);
 254         equal = hash->key_equal_func;
 255
 256         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 257
 258         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 259                 if ((*equal)(s->key, key)){
 260                         *orig_key = s->key;
 261                         *value = s->value;
 262                         return TRUE;
 263                 }
 264         }
 265         return FALSE;
 266 }
 267
 268 void
 269 mono_g_hash_table_foreach (MonoGHashTable *hash, GHFunc func, gpointer user_data)
 270 {
 271         int i;
 272
 273         g_return_if_fail (hash != NULL);
 274         g_return_if_fail (func != NULL);
 275
 276         for (i = 0; i < hash->table_size; i++){
 277                 Slot *s;
 278
 279                 for (s = hash->table [i]; s != NULL; s = s->next)
 280                         (*func)(s->key, s->value, user_data);
 281         }
 282 }
 283
 284 gpointer
 285 mono_g_hash_table_find (MonoGHashTable *hash, GHRFunc predicate, gpointer user_data)
 286 {
 287         int i;
 288
 289         g_return_val_if_fail (hash != NULL, NULL);
 290         g_return_val_if_fail (predicate != NULL, NULL);
 291
 292         for (i = 0; i < hash->table_size; i++){
 293                 Slot *s;
 294
 295                 for (s = hash->table [i]; s != NULL; s = s->next)
 296                         if ((*predicate)(s->key, s->value, user_data))
 297                                 return s->value;
 298         }
 299         return NULL;
 300 }
 301
 302 gboolean
 303 mono_g_hash_table_remove (MonoGHashTable *hash, gconstpointer key)
 304 {
 305         GEqualFunc equal;
 306         Slot *s, *last;
 307         guint hashcode;
 308
 309         g_return_val_if_fail (hash != NULL, FALSE);
 310         equal = hash->key_equal_func;
 311
 312         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 313         last = NULL;
 314         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 315                 if ((*equal)(s->key, key)){
 316                         if (hash->key_destroy_func != NULL)
 317                                 (*hash->key_destroy_func)(s->key);
 318                         if (hash->value_destroy_func != NULL)
 319                                 (*hash->value_destroy_func)(s->value);
 320                         if (last == NULL)
 321                                 hash->table [hashcode] = s->next;
 322                         else
 323                                 last->next = s->next;
 324                         free_slot (hash, s);
 325                         hash->in_use--;
 326                         return TRUE;
 327                 }
 328                 last = s;
 329         }
 330         return FALSE;
 331 }
 332
 333 guint
 334 mono_g_hash_table_foreach_remove (MonoGHashTable *hash, GHRFunc func, gpointer user_data)
 335 {
 336         int i;
 337         int count = 0;
 338
 339         g_return_val_if_fail (hash != NULL, 0);
 340         g_return_val_if_fail (func != NULL, 0);
 341
 342         for (i = 0; i < hash->table_size; i++){
 343                 Slot *s, *last;
 344
 345                 last = NULL;
 346                 for (s = hash->table [i]; s != NULL; ){
 347                         if ((*func)(s->key, s->value, user_data)){
 348                                 Slot *n;
 349
 350                                 if (hash->key_destroy_func != NULL)
 351                                         (*hash->key_destroy_func)(s->key);
 352                                 if (hash->value_destroy_func != NULL)
 353                                         (*hash->value_destroy_func)(s->value);
 354                                 if (last == NULL){
 355                                         hash->table [i] = s->next;
 356                                         n = s->next;
 357                                 } else  {
 358                                         last->next = s->next;
 359                                         n = last->next;
 360                                 }
 361                                 free_slot (hash, s);
 362                                 hash->in_use--;
 363                                 count++;
 364                                 s = n;
 365                         } else {
 366                                 last = s;
 367                                 s = s->next;
 368                         }
 369                 }
 370         }
 371         if (count > 0)
 372                 rehash (hash);
 373         return count;
 374 }
 375
 376 void
 377 mono_g_hash_table_destroy (MonoGHashTable *hash)
 378 {
 379         int i;
 380
 381         g_return_if_fail (hash != NULL);
 382
 383 #ifdef HAVE_SGEN_GC
 384         mono_gc_deregister_root ((char*)hash);
 385 #endif
 386
 387         for (i = 0; i < hash->table_size; i++){
 388                 Slot *s, *next;
 389
 390                 for (s = hash->table [i]; s != NULL; s = next){
 391                         next = s->next;
 392
 393                         if (hash->key_destroy_func != NULL)
 394                                 (*hash->key_destroy_func)(s->key);
 395                         if (hash->value_destroy_func != NULL)
 396                                 (*hash->value_destroy_func)(s->value);
 397                         free_slot (hash, s);
 398                 }
 399         }
 400         mg_free (hash->table);
 401 #ifdef HAVE_SGEN_GC
 402         mg_free (hash);
 403 #else
 404         mono_gc_free_fixed (hash);
 405 #endif
 406 }
 407
 408 static void
 409 mono_g_hash_table_insert_replace (MonoGHashTable *hash, gpointer key, gpointer value, gboolean replace)
 410 {
 411         guint hashcode;
 412         Slot *s;
 413         GEqualFunc equal;
 414
 415         g_return_if_fail (hash != NULL);
 416
 417         equal = hash->key_equal_func;
 418         if (hash->in_use >= hash->threshold)
 419                 rehash (hash);
 420
 421         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 422         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 423                 if ((*equal) (s->key, key)){
 424                         if (replace){
 425                                 if (hash->key_destroy_func != NULL)
 426                                         (*hash->key_destroy_func)(s->key);
 427                                 s->key = (MonoObject *)key;
 428                         }
 429                         if (hash->value_destroy_func != NULL)
 430                                 (*hash->value_destroy_func) (s->value);
 431                         s->value = (MonoObject *)value;
 432                         return;
 433                 }
 434         }
 435         s = new_slot (hash);
 436         s->key = (MonoObject *)key;
 437         s->value = (MonoObject *)value;
 438         s->next = hash->table [hashcode];
 439         hash->table [hashcode] = s;
 440         hash->in_use++;
 441 }
 442
 443 void
 444 mono_g_hash_table_insert (MonoGHashTable *h, gpointer k, gpointer v)
 445 {
 446         mono_g_hash_table_insert_replace (h, k, v, FALSE);
 447 }
 448
 449 void
 450 mono_g_hash_table_replace(MonoGHashTable *h, gpointer k, gpointer v)
 451 {
 452         mono_g_hash_table_insert_replace (h, k, v, TRUE);
 453 }
 454
 455 void
 456 mono_g_hash_table_print_stats (MonoGHashTable *table)
 457 {
 458         int i, chain_size, max_chain_size;
 459         Slot *node;
 460
 461         max_chain_size = 0;
 462         for (i = 0; i < table->table_size; i++) {
 463                 chain_size = 0;
 464                 for (node = table->table [i]; node; node = node->next)
 465                         chain_size ++;
 466                 max_chain_size = MAX(max_chain_size, chain_size);
 467         }
 468
 469         printf ("Size: %d Table Size: %d Max Chain Length: %d\n", table->in_use, table->table_size, max_chain_size);
 470 }
 471
 472 #ifdef HAVE_SGEN_GC
 473
 474 /* GC marker function */
 475 static void
 476 mono_g_hash_mark (void *addr, MonoGCMarkFunc mark_func, void *gc_data)
 477 {
 478         MonoGHashTable *table = (MonoGHashTable*)addr;
 479         Slot *node;
 480         int i;
 481
 482         if (table->gc_type == MONO_HASH_KEY_GC) {
 483                 for (i = 0; i < table->table_size; i++) {
 484                         for (node = table->table [i]; node; node = node->next) {
 485                                 if (node->key)
 486                                         mark_func (&node->key, gc_data);
 487                         }
 488                 }
 489         } else if (table->gc_type == MONO_HASH_VALUE_GC) {
 490                 for (i = 0; i < table->table_size; i++) {
 491                         for (node = table->table [i]; node; node = node->next) {
 492                                 if (node->value)
 493                                         mark_func (&node->value, gc_data);
 494                         }
 495                 }
 496         } else if (table->gc_type == MONO_HASH_KEY_VALUE_GC) {
 497                 for (i = 0; i < table->table_size; i++) {
 498                         for (node = table->table [i]; node; node = node->next) {
 499                                 if (node->key)
 500                                         mark_func (&node->key, gc_data);
 501                                 if (node->value)
 502                                         mark_func (&node->value, gc_data);
 503                         }
 504                 }
 505         }
 506 }
 507
 508 #endif