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