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