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