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