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-internal.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 = _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 #ifdef USE_COOP_GC
 223         /* We cannot be preempted */
 224         old_table = do_rehash (&data);
 225 #else
 226         old_table = mono_gc_invoke_with_gc_lock (do_rehash, &data);
 227 #endif
 228         mg_free (old_table);
 229 }
 230
 231 guint
 232 mono_g_hash_table_size (MonoGHashTable *hash)
 233 {
 234         g_return_val_if_fail (hash != NULL, 0);
 235
 236         return hash->in_use;
 237 }
 238
 239 gpointer
 240 mono_g_hash_table_lookup (MonoGHashTable *hash, gconstpointer key)
 241 {
 242         gpointer orig_key, value;
 243
 244         if (mono_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 245                 return value;
 246         else
 247                 return NULL;
 248 }
 249
 250 gboolean
 251 mono_g_hash_table_lookup_extended (MonoGHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 252 {
 253         GEqualFunc equal;
 254         Slot *s;
 255         guint hashcode;
 256
 257         g_return_val_if_fail (hash != NULL, FALSE);
 258         equal = hash->key_equal_func;
 259
 260         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 261
 262         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 263                 if ((*equal)(s->key, key)){
 264                         *orig_key = s->key;
 265                         *value = s->value;
 266                         return TRUE;
 267                 }
 268         }
 269         return FALSE;
 270 }
 271
 272 void
 273 mono_g_hash_table_foreach (MonoGHashTable *hash, GHFunc func, gpointer user_data)
 274 {
 275         int i;
 276
 277         g_return_if_fail (hash != NULL);
 278         g_return_if_fail (func != NULL);
 279
 280         for (i = 0; i < hash->table_size; i++){
 281                 Slot *s;
 282
 283                 for (s = hash->table [i]; s != NULL; s = s->next)
 284                         (*func)(s->key, s->value, user_data);
 285         }
 286 }
 287
 288 gpointer
 289 mono_g_hash_table_find (MonoGHashTable *hash, GHRFunc predicate, gpointer user_data)
 290 {
 291         int i;
 292
 293         g_return_val_if_fail (hash != NULL, NULL);
 294         g_return_val_if_fail (predicate != NULL, NULL);
 295
 296         for (i = 0; i < hash->table_size; i++){
 297                 Slot *s;
 298
 299                 for (s = hash->table [i]; s != NULL; s = s->next)
 300                         if ((*predicate)(s->key, s->value, user_data))
 301                                 return s->value;
 302         }
 303         return NULL;
 304 }
 305
 306 gboolean
 307 mono_g_hash_table_remove (MonoGHashTable *hash, gconstpointer key)
 308 {
 309         GEqualFunc equal;
 310         Slot *s, *last;
 311         guint hashcode;
 312
 313         g_return_val_if_fail (hash != NULL, FALSE);
 314         equal = hash->key_equal_func;
 315
 316         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 317         last = NULL;
 318         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 319                 if ((*equal)(s->key, key)){
 320                         if (hash->key_destroy_func != NULL)
 321                                 (*hash->key_destroy_func)(s->key);
 322                         if (hash->value_destroy_func != NULL)
 323                                 (*hash->value_destroy_func)(s->value);
 324                         if (last == NULL)
 325                                 hash->table [hashcode] = s->next;
 326                         else
 327                                 last->next = s->next;
 328                         free_slot (hash, s);
 329                         hash->in_use--;
 330                         return TRUE;
 331                 }
 332                 last = s;
 333         }
 334         return FALSE;
 335 }
 336
 337 guint
 338 mono_g_hash_table_foreach_remove (MonoGHashTable *hash, GHRFunc func, gpointer user_data)
 339 {
 340         int i;
 341         int count = 0;
 342
 343         g_return_val_if_fail (hash != NULL, 0);
 344         g_return_val_if_fail (func != NULL, 0);
 345
 346         for (i = 0; i < hash->table_size; i++){
 347                 Slot *s, *last;
 348
 349                 last = NULL;
 350                 for (s = hash->table [i]; s != NULL; ){
 351                         if ((*func)(s->key, s->value, user_data)){
 352                                 Slot *n;
 353
 354                                 if (hash->key_destroy_func != NULL)
 355                                         (*hash->key_destroy_func)(s->key);
 356                                 if (hash->value_destroy_func != NULL)
 357                                         (*hash->value_destroy_func)(s->value);
 358                                 if (last == NULL){
 359                                         hash->table [i] = s->next;
 360                                         n = s->next;
 361                                 } else  {
 362                                         last->next = s->next;
 363                                         n = last->next;
 364                                 }
 365                                 free_slot (hash, s);
 366                                 hash->in_use--;
 367                                 count++;
 368                                 s = n;
 369                         } else {
 370                                 last = s;
 371                                 s = s->next;
 372                         }
 373                 }
 374         }
 375         if (count > 0)
 376                 rehash (hash);
 377         return count;
 378 }
 379
 380 void
 381 mono_g_hash_table_destroy (MonoGHashTable *hash)
 382 {
 383         int i;
 384
 385         g_return_if_fail (hash != NULL);
 386
 387 #ifdef HAVE_SGEN_GC
 388         mono_gc_deregister_root ((char*)hash);
 389 #endif
 390
 391         for (i = 0; i < hash->table_size; i++){
 392                 Slot *s, *next;
 393
 394                 for (s = hash->table [i]; s != NULL; s = next){
 395                         next = s->next;
 396
 397                         if (hash->key_destroy_func != NULL)
 398                                 (*hash->key_destroy_func)(s->key);
 399                         if (hash->value_destroy_func != NULL)
 400                                 (*hash->value_destroy_func)(s->value);
 401                         free_slot (hash, s);
 402                 }
 403         }
 404         mg_free (hash->table);
 405         mg_free (hash);
 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 = key;
 428                         }
 429                         if (hash->value_destroy_func != NULL)
 430                                 (*hash->value_destroy_func) (s->value);
 431                         s->value = value;
 432                         return;
 433                 }
 434         }
 435         s = new_slot (hash);
 436         s->key = key;
 437         s->value = 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