mono/utils/mono-value-hash.c

   1 /*
   2  * mono-value-hash.c: A hash table which only stores values in the hash nodes.
   3  *
   4  * Author:
   5  *   Miguel de Icaza (miguel@novell.com)
   6  *   Zoltan Varga (vargaz@gmail.com)
   7  *
   8  * (C) 2006,2008 Novell, Inc.
   9  *
  10  * Permission is hereby granted, free of charge, to any person obtaining
  11  * a copy of this software and associated documentation files (the
  12  * "Software"), to deal in the Software without restriction, including
  13  * without limitation the rights to use, copy, modify, merge, publish,
  14  * distribute, sublicense, and/or sell copies of the Software, and to
  15  * permit persons to whom the Software is furnished to do so, subject to
  16  * the following conditions:
  17  *
  18  * The above copyright notice and this permission notice shall be
  19  * included in all copies or substantial portions of the Software.
  20  *
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28  */
  29 #include <stdio.h>
  30 #include <math.h>
  31 #include <glib.h>
  32
  33 #include "mono-value-hash.h"
  34
  35 #ifndef G_MAXINT32
  36 #define G_MAXINT32 2147483647
  37 #endif
  38
  39 /*
  40  * This code is based on eglib/ghashtable.c with work done by Hans Petter Jansson
  41  * (hpj@novell.com) to make it use internal probing instead of chaining.
  42  */
  43
  44 #define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */
  45
  46 typedef struct _Slot Slot;
  47
  48 #define GET_VALUE(slot) ((gpointer)((((gsize)((slot)->value)) >> 2) << 2))
  49
  50 #define SET_VALUE(slot,value) ((slot)->value = (value))
  51
  52 #define IS_EMPTY(slot) ((gsize)((slot)->value) == 0)
  53 #define IS_TOMBSTONE(slot) ((gsize)((slot)->value) & 1)
  54
  55 #define MAKE_TOMBSTONE(slot) do { (slot)->value = (gpointer)((gsize)((slot)->value) | 1); } while (1)
  56
  57 #define HASH(table, key) ((table)->hash_func ((key)))
  58
  59 struct _Slot {
  60         /* A NULL value means the slot is empty */
  61         /* The tombstone status is stored in the lowest order bit of the value. */
  62         gpointer value;
  63 };
  64
  65 static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
  66
  67 struct _MonoValueHashTable {
  68         GHashFunc      hash_func;
  69         GEqualFunc     key_equal_func;
  70         MonoValueHashKeyExtractFunc key_extract_func;
  71
  72         Slot *table;
  73         int   table_size;
  74         int   table_mask;
  75         int   in_use;
  76         int   n_occupied;
  77         GDestroyNotify value_destroy_func, key_destroy_func;
  78 };
  79
  80 static void
  81 mono_value_hash_table_set_shift (MonoValueHashTable *hash_table, gint shift)
  82 {
  83         gint i;
  84         guint mask = 0;
  85
  86         hash_table->table_size = 1 << shift;
  87
  88         for (i = 0; i < shift; i++) {
  89                 mask <<= 1;
  90                 mask |= 1;
  91         }
  92
  93         hash_table->table_mask = mask;
  94 }
  95
  96 static gint
  97 mono_value_hash_table_find_closest_shift (gint n)
  98 {
  99         gint i;
 100
 101         for (i = 0; n; i++)
 102                 n >>= 1;
 103
 104         return i;
 105 }
 106
 107 static void
 108 mono_value_hash_table_set_shift_from_size (MonoValueHashTable *hash_table, gint size)
 109 {
 110         gint shift;
 111
 112         shift = mono_value_hash_table_find_closest_shift (size);
 113         shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
 114
 115         mono_value_hash_table_set_shift (hash_table, shift);
 116 }
 117
 118 MonoValueHashTable *
 119 mono_value_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func, MonoValueHashKeyExtractFunc key_extract)
 120 {
 121         MonoValueHashTable *hash;
 122
 123         if (hash_func == NULL)
 124                 hash_func = g_direct_hash;
 125         if (key_equal_func == NULL)
 126                 key_equal_func = g_direct_equal;
 127         hash = g_new0 (MonoValueHashTable, 1);
 128
 129         hash->hash_func = hash_func;
 130         hash->key_equal_func = key_equal_func;
 131         hash->key_extract_func = key_extract;
 132
 133         mono_value_hash_table_set_shift (hash, HASH_TABLE_MIN_SHIFT);
 134         hash->table = g_new0 (Slot, hash->table_size);
 135
 136         return hash;
 137 }
 138
 139 #if 0
 140
 141 MonoValueHashTable *
 142 mono_value_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 143                                                                 GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 144 {
 145         MonoValueHashTable *hash = mono_value_hash_table_new (hash_func, key_equal_func);
 146         if (hash == NULL)
 147                 return NULL;
 148
 149         hash->key_destroy_func = key_destroy_func;
 150         hash->value_destroy_func = value_destroy_func;
 151
 152         return hash;
 153 }
 154
 155 #endif
 156
 157 static void
 158 do_rehash (MonoValueHashTable *hash)
 159 {
 160         int i;
 161         int old_size;
 162         Slot *old_table;
 163
 164         old_size = hash->table_size;
 165         old_table = hash->table;
 166
 167         mono_value_hash_table_set_shift_from_size (hash, hash->in_use * 2);
 168
 169         /* printf ("New size: %d\n", hash->table_size); */
 170         hash->table = g_new0 (Slot, hash->table_size);
 171
 172         for (i = 0; i < old_size; i++){
 173                 Slot *s = &old_table [i];
 174                 Slot *new_s;
 175                 guint hash_val;
 176                 guint step = 0;
 177                 gpointer s_value, s_key;
 178
 179                 if (IS_EMPTY (s) || IS_TOMBSTONE (s))
 180                         continue;
 181
 182                 s_value = GET_VALUE (s);
 183                 s_key = hash->key_extract_func (s_value);
 184                 hash_val = HASH (hash, s_key) & hash->table_mask;
 185                 new_s = &hash->table [hash_val];
 186
 187                 while (!IS_EMPTY (new_s)) {
 188                         step++;
 189                         hash_val += step;
 190                         hash_val &= hash->table_mask;
 191                         new_s = &hash->table [hash_val];
 192                 }
 193
 194                 *new_s = *s;
 195         }
 196         g_free (old_table);
 197         hash->n_occupied = hash->in_use;
 198 }
 199
 200 static void
 201 rehash (MonoValueHashTable *hash)
 202 {
 203         int n_occupied = hash->n_occupied;
 204         int table_size = hash->table_size;
 205
 206         if ((table_size > hash->in_use * 4 && table_size > 1 << HASH_TABLE_MIN_SHIFT) ||
 207             (table_size <= n_occupied + (n_occupied / 16)))
 208                 do_rehash (hash);
 209 }
 210
 211 static void
 212 mono_value_hash_table_insert_replace (MonoValueHashTable *hash, gpointer key, gpointer value, gboolean replace)
 213 {
 214         guint hashcode;
 215         Slot *s;
 216         guint s_index;
 217         GEqualFunc equal;
 218         guint first_tombstone = 0;
 219         gboolean have_tombstone = FALSE;
 220         guint step = 0;
 221
 222         g_assert (value);
 223         g_assert (hash->key_extract_func (value) == key);
 224
 225         g_return_if_fail (hash != NULL);
 226
 227         hashcode = HASH (hash, key);
 228
 229         s_index = hashcode & hash->table_mask;
 230         s = &hash->table [s_index];
 231
 232         equal = hash->key_equal_func;
 233
 234         while (!IS_EMPTY (s)) {
 235                 gpointer s_value = GET_VALUE (s);
 236                 gpointer s_key = hash->key_extract_func (s_value);
 237                 guint s_key_hash = HASH (hash, s_key);
 238                 if (s_key_hash == hashcode && (*equal) (s_key, key)) {
 239                         if (replace){
 240                                 if (hash->key_destroy_func != NULL)
 241                                         (*hash->key_destroy_func)(s_key);
 242                         }
 243                         if (hash->value_destroy_func != NULL)
 244                                 (*hash->value_destroy_func) (GET_VALUE (s));
 245                         SET_VALUE (s, value);
 246                         return;
 247                 } else if (IS_TOMBSTONE (s) && !have_tombstone) {
 248                         first_tombstone = s_index;
 249                         have_tombstone = TRUE;
 250                 }
 251
 252                 step++;
 253                 s_index += step;
 254                 s_index &= hash->table_mask;
 255                 s = &hash->table [s_index];
 256         }
 257
 258         if (have_tombstone) {
 259                 s = &hash->table [first_tombstone];
 260         } else {
 261                 hash->n_occupied++;
 262         }
 263
 264         SET_VALUE (s, value);
 265         hash->in_use++;
 266
 267         rehash (hash);
 268 }
 269
 270 void
 271 mono_value_hash_table_insert (MonoValueHashTable *hash, gpointer key, gpointer value)
 272 {
 273         mono_value_hash_table_insert_replace (hash, key, value, TRUE);
 274 }
 275
 276 static Slot *
 277 lookup_internal (MonoValueHashTable *hash, gconstpointer key)
 278 {
 279         GEqualFunc equal;
 280         Slot *s;
 281         guint hashcode;
 282         guint s_index;
 283         guint step = 0;
 284
 285         hashcode = HASH (hash, key);
 286
 287         s_index = hashcode & hash->table_mask;
 288         s = &hash->table [s_index];
 289
 290         equal = hash->key_equal_func;
 291
 292         while (!IS_EMPTY (s)) {
 293                 gpointer s_value = GET_VALUE (s);
 294                 gpointer s_key = hash->key_extract_func (s_value);
 295                 guint s_key_hash = HASH (hash, s_key);
 296                 if (s_key_hash == hashcode && (*equal) (hash->key_extract_func (s_value), key))
 297                         return s;
 298
 299                 step++;
 300                 s_index += step;
 301                 s_index &= hash->table_mask;
 302                 s = &hash->table [s_index];
 303         }
 304
 305         return NULL;
 306 }
 307
 308 gpointer
 309 mono_value_hash_table_lookup (MonoValueHashTable *hash, gconstpointer key)
 310 {
 311         Slot *slot = lookup_internal (hash, key);
 312
 313         if (slot)
 314                 return GET_VALUE (slot);
 315         else
 316                 return NULL;
 317 }
 318
 319 void
 320 mono_value_hash_table_destroy (MonoValueHashTable *hash)
 321 {
 322         int i;
 323
 324         g_return_if_fail (hash != NULL);
 325
 326         for (i = 0; i < hash->table_size; i++){
 327                 Slot *s = &hash->table [i];
 328
 329                 if (!IS_EMPTY (s) && !IS_TOMBSTONE (s)) {
 330                         if (hash->key_destroy_func != NULL)
 331                                 (*hash->key_destroy_func)(hash->key_extract_func (GET_VALUE (s)));
 332                         if (hash->value_destroy_func != NULL)
 333                                 (*hash->value_destroy_func)(GET_VALUE (s));
 334                 }
 335         }
 336         g_free (hash->table);
 337
 338         g_free (hash);
 339 }