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