mono/metadata/sgen-hash-table.c

   1 /*
   2  * sgen-hash-table.c
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  19  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  20  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  21  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 #include "config.h"
  25
  26 #ifdef HAVE_SGEN_GC
  27
  28 #include <mono/metadata/sgen-gc.h>
  29 #include <mono/metadata/sgen-hash-table.h>
  30 #include <mono/utils/mono-counters.h>
  31
  32 #ifdef HEAVY_STATISTICS
  33 static long long stat_lookups;
  34 static long long stat_lookup_iterations;
  35 static long long stat_lookup_max_iterations;
  36 #endif
  37
  38 static void
  39 rehash (SgenHashTable *hash_table)
  40 {
  41         SgenHashTableEntry **old_hash = hash_table->table;
  42         guint old_hash_size = hash_table->size;
  43         guint i, hash, new_size;
  44         SgenHashTableEntry **new_hash;
  45         SgenHashTableEntry *entry, *next;
  46
  47         if (!old_hash) {
  48                 sgen_register_fixed_internal_mem_type (hash_table->entry_mem_type,
  49                                 sizeof (SgenHashTableEntry*) + sizeof (gpointer) + hash_table->data_size);
  50                 new_size = 13;
  51         } else {
  52                 new_size = g_spaced_primes_closest (hash_table->num_entries);
  53         }
  54
  55         new_hash = sgen_alloc_internal_dynamic (new_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type, TRUE);
  56         for (i = 0; i < old_hash_size; ++i) {
  57                 for (entry = old_hash [i]; entry; entry = next) {
  58                         hash = hash_table->hash_func (entry->key) % new_size;
  59                         next = entry->next;
  60                         entry->next = new_hash [hash];
  61                         new_hash [hash] = entry;
  62                 }
  63         }
  64         sgen_free_internal_dynamic (old_hash, old_hash_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
  65         hash_table->table = new_hash;
  66         hash_table->size = new_size;
  67 }
  68
  69 static void
  70 rehash_if_necessary (SgenHashTable *hash_table)
  71 {
  72         if (hash_table->num_entries >= hash_table->size * 2)
  73                 rehash (hash_table);
  74
  75         SGEN_ASSERT (1, hash_table->size, "rehash guarantees size > 0");
  76 }
  77
  78 static SgenHashTableEntry*
  79 lookup (SgenHashTable *hash_table, gpointer key, guint *_hash)
  80 {
  81         SgenHashTableEntry *entry;
  82         guint hash;
  83         GEqualFunc equal = hash_table->equal_func;
  84 #ifdef HEAVY_STATISTICS
  85         long long iterations = 0;
  86         ++stat_lookups;
  87 #endif
  88
  89         if (!hash_table->size)
  90                 return NULL;
  91
  92         hash = hash_table->hash_func (key) % hash_table->size;
  93         if (_hash)
  94                 *_hash = hash;
  95
  96         for (entry = hash_table->table [hash]; entry; entry = entry->next) {
  97 #ifdef HEAVY_STATISTICS
  98                 ++stat_lookup_iterations;
  99                 ++iterations;
 100                 if (iterations > stat_lookup_max_iterations)
 101                         stat_lookup_max_iterations = iterations;
 102 #endif
 103                 if ((equal && equal (entry->key, key)) || (!equal && entry->key == key))
 104                         return entry;
 105         }
 106         return NULL;
 107 }
 108
 109 gpointer
 110 sgen_hash_table_lookup (SgenHashTable *hash_table, gpointer key)
 111 {
 112         SgenHashTableEntry *entry = lookup (hash_table, key, NULL);
 113         if (!entry)
 114                 return NULL;
 115         return entry->data;
 116 }
 117
 118 gboolean
 119 sgen_hash_table_replace (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
 120 {
 121         guint hash;
 122         SgenHashTableEntry *entry;
 123
 124         rehash_if_necessary (hash_table);
 125         entry = lookup (hash_table, key, &hash);
 126
 127         if (entry) {
 128                 if (old_value)
 129                         memcpy (old_value, entry->data, hash_table->data_size);
 130                 memcpy (entry->data, new_value, hash_table->data_size);
 131                 return FALSE;
 132         }
 133
 134         entry = sgen_alloc_internal (hash_table->entry_mem_type);
 135         entry->key = key;
 136         memcpy (entry->data, new_value, hash_table->data_size);
 137
 138         entry->next = hash_table->table [hash];
 139         hash_table->table [hash] = entry;
 140
 141         hash_table->num_entries++;
 142
 143         return TRUE;
 144 }
 145
 146 gboolean
 147 sgen_hash_table_set_value (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
 148 {
 149         guint hash;
 150         SgenHashTableEntry *entry;
 151
 152         entry = lookup (hash_table, key, &hash);
 153
 154         if (entry) {
 155                 if (old_value)
 156                         memcpy (old_value, entry->data, hash_table->data_size);
 157                 memcpy (entry->data, new_value, hash_table->data_size);
 158                 return TRUE;
 159         }
 160
 161         return FALSE;
 162 }
 163
 164 gboolean
 165 sgen_hash_table_set_key (SgenHashTable *hash_table, gpointer old_key, gpointer new_key)
 166 {
 167         guint hash;
 168         SgenHashTableEntry *entry;
 169
 170         entry = lookup (hash_table, old_key, &hash);
 171
 172         if (entry) {
 173                 entry->key = new_key;
 174                 return TRUE;
 175         }
 176
 177         return FALSE;
 178 }
 179
 180 gboolean
 181 sgen_hash_table_remove (SgenHashTable *hash_table, gpointer key, gpointer data_return)
 182 {
 183         SgenHashTableEntry *entry, *prev;
 184         guint hash;
 185         GEqualFunc equal = hash_table->equal_func;
 186
 187         rehash_if_necessary (hash_table);
 188         hash = hash_table->hash_func (key) % hash_table->size;
 189
 190         prev = NULL;
 191         for (entry = hash_table->table [hash]; entry; entry = entry->next) {
 192                 if ((equal && equal (entry->key, key)) || (!equal && entry->key == key)) {
 193                         if (prev)
 194                                 prev->next = entry->next;
 195                         else
 196                                 hash_table->table [hash] = entry->next;
 197
 198                         hash_table->num_entries--;
 199
 200                         if (data_return)
 201                                 memcpy (data_return, entry->data, hash_table->data_size);
 202
 203                         sgen_free_internal (entry, hash_table->entry_mem_type);
 204
 205                         return TRUE;
 206                 }
 207                 prev = entry;
 208         }
 209
 210         return FALSE;
 211 }
 212
 213 void
 214 sgen_hash_table_clean (SgenHashTable *hash_table)
 215 {
 216         guint i;
 217
 218         if (!hash_table->size) {
 219                 SGEN_ASSERT (1, !hash_table->table, "clean should reset hash_table->table");
 220                 SGEN_ASSERT (1, !hash_table->num_entries, "clean should reset hash_table->num_entries");
 221                 return;
 222         }
 223
 224         for (i = 0; i < hash_table->size; ++i) {
 225                 SgenHashTableEntry *entry = hash_table->table [i];
 226                 while (entry) {
 227                         SgenHashTableEntry *next = entry->next;
 228                         sgen_free_internal (entry, hash_table->entry_mem_type);
 229                         entry = next;
 230                 }
 231         }
 232
 233         sgen_free_internal_dynamic (hash_table->table, hash_table->size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
 234
 235         hash_table->table = NULL;
 236         hash_table->size = 0;
 237         hash_table->num_entries = 0;
 238 }
 239
 240 void
 241 sgen_init_hash_table (void)
 242 {
 243 #ifdef HEAVY_STATISTICS
 244         mono_counters_register ("Hash table lookups", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_lookups);
 245         mono_counters_register ("Hash table lookup iterations", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_lookup_iterations);
 246         mono_counters_register ("Hash table lookup max iterations", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_lookup_max_iterations);
 247 #endif
 248 }
 249
 250 #endif