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