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