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/os/gc_wrapper.h>
  33 #include "mono-hash.h"
  34 #include "metadata/gc-internal.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         gpointer key;
  50         gpointer 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 };
  68
  69 static const int prime_tbl[] = {
  70         11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
  71         1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
  72         47431, 71143, 106721, 160073, 240101, 360163,
  73         540217, 810343, 1215497, 1823231, 2734867, 4102283,
  74         6153409, 9230113, 13845163
  75 };
  76
  77 static gboolean
  78 test_prime (int x)
  79 {
  80         if ((x & 1) != 0) {
  81                 int n;
  82                 for (n = 3; n< (int)sqrt (x); n += 2) {
  83                         if ((x % n) == 0)
  84                                 return FALSE;
  85                 }
  86                 return TRUE;
  87         }
  88         // There is only one even prime - 2.
  89         return (x == 2);
  90 }
  91
  92 static int
  93 calc_prime (int x)
  94 {
  95         int i;
  96
  97         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
  98                 if (test_prime (i))
  99                         return i;
 100         }
 101         return x;
 102 }
 103
 104 MonoGHashTable *
 105 mono_g_hash_table_new_type (GHashFunc hash_func, GEqualFunc key_equal_func, MonoGHashGCType type)
 106 {
 107         MonoGHashTable *hash = mono_g_hash_table_new (hash_func, key_equal_func);
 108
 109         hash->gc_type = type;
 110
 111         return hash;
 112 }
 113
 114 MonoGHashTable *
 115 mono_g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 116 {
 117         MonoGHashTable *hash;
 118
 119         if (hash_func == NULL)
 120                 hash_func = g_direct_hash;
 121         if (key_equal_func == NULL)
 122                 key_equal_func = g_direct_equal;
 123         hash = mg_new0 (MonoGHashTable, 1);
 124
 125         hash->hash_func = hash_func;
 126         hash->key_equal_func = key_equal_func;
 127
 128         hash->table_size = g_spaced_primes_closest (1);
 129         hash->table = mg_new0 (Slot *, hash->table_size);
 130         hash->last_rehash = hash->table_size;
 131
 132         return hash;
 133 }
 134
 135 MonoGHashTable *
 136 mono_g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 137                             GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 138 {
 139         MonoGHashTable *hash = mono_g_hash_table_new (hash_func, key_equal_func);
 140         if (hash == NULL)
 141                 return NULL;
 142
 143         hash->key_destroy_func = key_destroy_func;
 144         hash->value_destroy_func = value_destroy_func;
 145
 146         return hash;
 147 }
 148
 149 static void
 150 do_rehash (MonoGHashTable *hash)
 151 {
 152         int current_size, i;
 153         Slot **table;
 154
 155         /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
 156         hash->last_rehash = hash->table_size;
 157         current_size = hash->table_size;
 158         hash->table_size = g_spaced_primes_closest (hash->in_use);
 159         /* printf ("New size: %d\n", hash->table_size); */
 160         table = hash->table;
 161         hash->table = mg_new0 (Slot *, hash->table_size);
 162
 163         for (i = 0; i < current_size; i++){
 164                 Slot *s, *next;
 165
 166                 for (s = table [i]; s != NULL; s = next){
 167                         guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
 168                         next = s->next;
 169
 170                         s->next = hash->table [hashcode];
 171                         hash->table [hashcode] = s;
 172                 }
 173         }
 174         mg_free (table);
 175 }
 176
 177 static void
 178 rehash (MonoGHashTable *hash)
 179 {
 180         int diff = ABS (hash->last_rehash, hash->in_use);
 181
 182         /* These are the factors to play with to change the rehashing strategy */
 183         /* I played with them with a large range, and could not really get */
 184         /* something that was too good, maybe the tests are not that great */
 185         if (!(diff * 0.75 > hash->table_size * 2))
 186                 return;
 187         do_rehash (hash);
 188 }
 189
 190 guint
 191 mono_g_hash_table_size (MonoGHashTable *hash)
 192 {
 193         g_return_val_if_fail (hash != NULL, 0);
 194
 195         return hash->in_use;
 196 }
 197
 198 gpointer
 199 mono_g_hash_table_lookup (MonoGHashTable *hash, gconstpointer key)
 200 {
 201         gpointer orig_key, value;
 202
 203         if (mono_g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 204                 return value;
 205         else
 206                 return NULL;
 207 }
 208
 209 gboolean
 210 mono_g_hash_table_lookup_extended (MonoGHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 211 {
 212         GEqualFunc equal;
 213         Slot *s;
 214         guint hashcode;
 215
 216         g_return_val_if_fail (hash != NULL, FALSE);
 217         equal = hash->key_equal_func;
 218
 219         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 220
 221         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 222                 if ((*equal)(s->key, key)){
 223                         *orig_key = s->key;
 224                         *value = s->value;
 225                         return TRUE;
 226                 }
 227         }
 228         return FALSE;
 229 }
 230
 231 void
 232 mono_g_hash_table_foreach (MonoGHashTable *hash, GHFunc func, gpointer user_data)
 233 {
 234         int i;
 235
 236         g_return_if_fail (hash != NULL);
 237         g_return_if_fail (func != NULL);
 238
 239         for (i = 0; i < hash->table_size; i++){
 240                 Slot *s;
 241
 242                 for (s = hash->table [i]; s != NULL; s = s->next)
 243                         (*func)(s->key, s->value, user_data);
 244         }
 245 }
 246
 247 gboolean
 248 mono_g_hash_table_remove (MonoGHashTable *hash, gconstpointer key)
 249 {
 250         GEqualFunc equal;
 251         Slot *s, *last;
 252         guint hashcode;
 253
 254         g_return_val_if_fail (hash != NULL, FALSE);
 255         equal = hash->key_equal_func;
 256
 257         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 258         last = NULL;
 259         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 260                 if ((*equal)(s->key, key)){
 261                         if (hash->key_destroy_func != NULL)
 262                                 (*hash->key_destroy_func)(s->key);
 263                         if (hash->value_destroy_func != NULL)
 264                                 (*hash->value_destroy_func)(s->value);
 265                         if (last == NULL)
 266                                 hash->table [hashcode] = s->next;
 267                         else
 268                                 last->next = s->next;
 269                         mg_free (s);
 270                         hash->in_use--;
 271                         return TRUE;
 272                 }
 273                 last = s;
 274         }
 275         return FALSE;
 276 }
 277
 278 guint
 279 mono_g_hash_table_foreach_remove (MonoGHashTable *hash, GHRFunc func, gpointer user_data)
 280 {
 281         int i;
 282         int count = 0;
 283
 284         g_return_val_if_fail (hash != NULL, 0);
 285         g_return_val_if_fail (func != NULL, 0);
 286
 287         for (i = 0; i < hash->table_size; i++){
 288                 Slot *s, *last;
 289
 290                 last = NULL;
 291                 for (s = hash->table [i]; s != NULL; ){
 292                         if ((*func)(s->key, s->value, user_data)){
 293                                 Slot *n;
 294
 295                                 if (hash->key_destroy_func != NULL)
 296                                         (*hash->key_destroy_func)(s->key);
 297                                 if (hash->value_destroy_func != NULL)
 298                                         (*hash->value_destroy_func)(s->value);
 299                                 if (last == NULL){
 300                                         hash->table [i] = s->next;
 301                                         n = s->next;
 302                                 } else  {
 303                                         last->next = s->next;
 304                                         n = last->next;
 305                                 }
 306                                 mg_free (s);
 307                                 hash->in_use--;
 308                                 count++;
 309                                 s = n;
 310                         } else {
 311                                 last = s;
 312                                 s = s->next;
 313                         }
 314                 }
 315         }
 316         if (count > 0)
 317                 rehash (hash);
 318         return count;
 319 }
 320
 321 void
 322 mono_g_hash_table_destroy (MonoGHashTable *hash)
 323 {
 324         int i;
 325
 326         g_return_if_fail (hash != NULL);
 327
 328         for (i = 0; i < hash->table_size; i++){
 329                 Slot *s, *next;
 330
 331                 for (s = hash->table [i]; s != NULL; s = next){
 332                         next = s->next;
 333
 334                         if (hash->key_destroy_func != NULL)
 335                                 (*hash->key_destroy_func)(s->key);
 336                         if (hash->value_destroy_func != NULL)
 337                                 (*hash->value_destroy_func)(s->value);
 338                         mg_free (s);
 339                 }
 340         }
 341         mg_free (hash->table);
 342         mg_free (hash);
 343 }
 344
 345 void
 346 mono_g_hash_table_insert_replace (MonoGHashTable *hash, gpointer key, gpointer value, gboolean replace)
 347 {
 348         guint hashcode;
 349         Slot *s;
 350         GEqualFunc equal;
 351
 352         g_return_if_fail (hash != NULL);
 353
 354         equal = hash->key_equal_func;
 355         if (hash->in_use >= hash->threshold)
 356                 rehash (hash);
 357
 358         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 359         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 360                 if ((*equal) (s->key, key)){
 361                         if (replace){
 362                                 if (hash->key_destroy_func != NULL)
 363                                         (*hash->key_destroy_func)(s->key);
 364                                 s->key = key;
 365                         }
 366                         if (hash->value_destroy_func != NULL)
 367                                 (*hash->value_destroy_func) (s->value);
 368                         s->value = value;
 369                         return;
 370                 }
 371         }
 372         s = mg_new (Slot, 1);
 373         s->key = key;
 374         s->value = value;
 375         s->next = hash->table [hashcode];
 376         hash->table [hashcode] = s;
 377         hash->in_use++;
 378 }
 379
 380 void
 381 mono_g_hash_table_insert (MonoGHashTable *h, gpointer k, gpointer v)
 382 {
 383         mono_g_hash_table_insert_replace (h, k, v, FALSE);
 384 }
 385
 386 void
 387 mono_g_hash_table_replace(MonoGHashTable *h, gpointer k, gpointer v)
 388 {
 389         mono_g_hash_table_insert_replace (h, k, v, TRUE);
 390 }
 391