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