mono/utils/mono-value-hash.c

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