mono/sgen/sgen-hash-table.c

   1 /**
   2  * \file
   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 <string.h>
  29
  30 #include <mono/sgen/sgen-gc.h>
  31 #include <mono/sgen/sgen-hash-table.h>
  32
  33 #ifdef HEAVY_STATISTICS
  34 static guint64 stat_lookups;
  35 static guint64 stat_lookup_iterations;
  36 static guint64 stat_lookup_max_iterations;
  37 #endif
  38
  39 static void
  40 rehash (SgenHashTable *hash_table)
  41 {
  42         SgenHashTableEntry **old_hash = hash_table->table;
  43         guint old_hash_size = hash_table->size;
  44         guint i, hash, new_size;
  45         SgenHashTableEntry **new_hash;
  46         SgenHashTableEntry *entry, *next;
  47
  48         if (!old_hash) {
  49                 sgen_register_fixed_internal_mem_type (hash_table->entry_mem_type,
  50                                 sizeof (SgenHashTableEntry*) + sizeof (gpointer) + hash_table->data_size);
  51                 new_size = 13;
  52         } else {
  53                 new_size = g_spaced_primes_closest (hash_table->num_entries);
  54         }
  55
  56         new_hash = (SgenHashTableEntry **)sgen_alloc_internal_dynamic (new_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type, TRUE);
  57         for (i = 0; i < old_hash_size; ++i) {
  58                 for (entry = old_hash [i]; entry; entry = next) {
  59                         hash = hash_table->hash_func (entry->key) % new_size;
  60                         next = entry->next;
  61                         entry->next = new_hash [hash];
  62                         new_hash [hash] = entry;
  63                 }
  64         }
  65         sgen_free_internal_dynamic (old_hash, old_hash_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
  66         hash_table->table = new_hash;
  67         hash_table->size = new_size;
  68 }
  69
  70 static void
  71 rehash_if_necessary (SgenHashTable *hash_table)
  72 {
  73         if (hash_table->num_entries >= hash_table->size * 2)
  74                 rehash (hash_table);
  75
  76         SGEN_ASSERT (1, hash_table->size, "rehash guarantees size > 0");
  77 }
  78
  79 static SgenHashTableEntry*
  80 lookup (SgenHashTable *hash_table, gpointer key, guint *_hash)
  81 {
  82         SgenHashTableEntry *entry;
  83         guint hash;
  84         GEqualFunc equal = hash_table->equal_func;
  85 #ifdef HEAVY_STATISTICS
  86         guint64 iterations = 0;
  87         ++stat_lookups;
  88 #endif
  89
  90         if (!hash_table->size)
  91                 return NULL;
  92
  93         hash = hash_table->hash_func (key) % hash_table->size;
  94         if (_hash)
  95                 *_hash = hash;
  96
  97         for (entry = hash_table->table [hash]; entry; entry = entry->next) {
  98 #ifdef HEAVY_STATISTICS
  99                 ++stat_lookup_iterations;
 100                 ++iterations;
 101                 if (iterations > stat_lookup_max_iterations)
 102                         stat_lookup_max_iterations = iterations;
 103 #endif
 104                 if ((equal && equal (entry->key, key)) || (!equal && entry->key == key))
 105                         return entry;
 106         }
 107         return NULL;
 108 }
 109
 110 gpointer
 111 sgen_hash_table_lookup (SgenHashTable *hash_table, gpointer key)
 112 {
 113         SgenHashTableEntry *entry = lookup (hash_table, key, NULL);
 114         if (!entry)
 115                 return NULL;
 116         return entry->data;
 117 }
 118
 119 gboolean
 120 sgen_hash_table_replace (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
 121 {
 122         guint hash;
 123         SgenHashTableEntry *entry;
 124
 125         rehash_if_necessary (hash_table);
 126         entry = lookup (hash_table, key, &hash);
 127
 128         if (entry) {
 129                 if (old_value)
 130                         memcpy (old_value, entry->data, hash_table->data_size);
 131                 memcpy (entry->data, new_value, hash_table->data_size);
 132                 return FALSE;
 133         }
 134
 135         entry = (SgenHashTableEntry *)sgen_alloc_internal (hash_table->entry_mem_type);
 136         entry->key = key;
 137         memcpy (entry->data, new_value, hash_table->data_size);
 138
 139         entry->next = hash_table->table [hash];
 140         hash_table->table [hash] = entry;
 141
 142         hash_table->num_entries++;
 143
 144         return TRUE;
 145 }
 146
 147 gboolean
 148 sgen_hash_table_set_value (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
 149 {
 150         guint hash;
 151         SgenHashTableEntry *entry;
 152
 153         entry = lookup (hash_table, key, &hash);
 154
 155         if (entry) {
 156                 if (old_value)
 157                         memcpy (old_value, entry->data, hash_table->data_size);
 158                 memcpy (entry->data, new_value, hash_table->data_size);
 159                 return TRUE;
 160         }
 161
 162         return FALSE;
 163 }
 164
 165 gboolean
 166 sgen_hash_table_set_key (SgenHashTable *hash_table, gpointer old_key, gpointer new_key)
 167 {
 168         guint hash;
 169         SgenHashTableEntry *entry;
 170
 171         entry = lookup (hash_table, old_key, &hash);
 172
 173         if (entry) {
 174                 entry->key = new_key;
 175                 return TRUE;
 176         }
 177
 178         return FALSE;
 179 }
 180
 181 gboolean
 182 sgen_hash_table_remove (SgenHashTable *hash_table, gpointer key, gpointer data_return)
 183 {
 184         SgenHashTableEntry *entry, *prev;
 185         guint hash;
 186         GEqualFunc equal = hash_table->equal_func;
 187
 188         rehash_if_necessary (hash_table);
 189         hash = hash_table->hash_func (key) % hash_table->size;
 190
 191         prev = NULL;
 192         for (entry = hash_table->table [hash]; entry; entry = entry->next) {
 193                 if ((equal && equal (entry->key, key)) || (!equal && entry->key == key)) {
 194                         if (prev)
 195                                 prev->next = entry->next;
 196                         else
 197                                 hash_table->table [hash] = entry->next;
 198
 199                         hash_table->num_entries--;
 200
 201                         if (data_return)
 202                                 memcpy (data_return, entry->data, hash_table->data_size);
 203
 204                         sgen_free_internal (entry, hash_table->entry_mem_type);
 205
 206                         return TRUE;
 207                 }
 208                 prev = entry;
 209         }
 210
 211         return FALSE;
 212 }
 213
 214 void
 215 sgen_hash_table_clean (SgenHashTable *hash_table)
 216 {
 217         guint i;
 218
 219         if (!hash_table->size) {
 220                 SGEN_ASSERT (1, !hash_table->table, "clean should reset hash_table->table");
 221                 SGEN_ASSERT (1, !hash_table->num_entries, "clean should reset hash_table->num_entries");
 222                 return;
 223         }
 224
 225         for (i = 0; i < hash_table->size; ++i) {
 226                 SgenHashTableEntry *entry = hash_table->table [i];
 227                 while (entry) {
 228                         SgenHashTableEntry *next = entry->next;
 229                         sgen_free_internal (entry, hash_table->entry_mem_type);
 230                         entry = next;
 231                 }
 232         }
 233
 234         sgen_free_internal_dynamic (hash_table->table, hash_table->size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
 235
 236         hash_table->table = NULL;
 237         hash_table->size = 0;
 238         hash_table->num_entries = 0;
 239 }
 240
 241 void
 242 sgen_init_hash_table (void)
 243 {
 244 #ifdef HEAVY_STATISTICS
 245         mono_counters_register ("Hash table lookups", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_lookups);
 246         mono_counters_register ("Hash table lookup iterations", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_lookup_iterations);
 247         mono_counters_register ("Hash table lookup max iterations", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_lookup_max_iterations);
 248 #endif
 249 }
 250
 251 #endif