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                 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 = sgen_alloc_internal_dynamic (new_size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type, TRUE);
  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         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 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 sgen_hash_table_replace (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
 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                 if (old_value)
 109                         memcpy (old_value, entry->data, hash_table->data_size);
 110                 memcpy (entry->data, new_value, hash_table->data_size);
 111                 return FALSE;
 112         }
 113
 114         entry = sgen_alloc_internal (hash_table->entry_mem_type);
 115         entry->key = key;
 116         memcpy (entry->data, new_value, hash_table->data_size);
 117
 118         entry->next = hash_table->table [hash];
 119         hash_table->table [hash] = entry;
 120
 121         hash_table->num_entries++;
 122
 123         return TRUE;
 124 }
 125
 126 gboolean
 127 sgen_hash_table_set_value (SgenHashTable *hash_table, gpointer key, gpointer new_value, gpointer old_value)
 128 {
 129         guint hash;
 130         SgenHashTableEntry *entry;
 131
 132         entry = lookup (hash_table, key, &hash);
 133
 134         if (entry) {
 135                 if (old_value)
 136                         memcpy (old_value, entry->data, hash_table->data_size);
 137                 memcpy (entry->data, new_value, hash_table->data_size);
 138                 return TRUE;
 139         }
 140
 141         return FALSE;
 142 }
 143
 144 gboolean
 145 sgen_hash_table_set_key (SgenHashTable *hash_table, gpointer old_key, gpointer new_key)
 146 {
 147         guint hash;
 148         SgenHashTableEntry *entry;
 149
 150         entry = lookup (hash_table, old_key, &hash);
 151
 152         if (entry) {
 153                 entry->key = new_key;
 154                 return TRUE;
 155         }
 156
 157         return FALSE;
 158 }
 159
 160 gboolean
 161 sgen_hash_table_remove (SgenHashTable *hash_table, gpointer key, gpointer data_return)
 162 {
 163         SgenHashTableEntry *entry, *prev;
 164         guint hash;
 165         GEqualFunc equal = hash_table->equal_func;
 166
 167         rehash_if_necessary (hash_table);
 168         hash = hash_table->hash_func (key) % hash_table->size;
 169
 170         prev = NULL;
 171         for (entry = hash_table->table [hash]; entry; entry = entry->next) {
 172                 if ((equal && equal (entry->key, key)) || (!equal && entry->key == key)) {
 173                         if (prev)
 174                                 prev->next = entry->next;
 175                         else
 176                                 hash_table->table [hash] = entry->next;
 177
 178                         hash_table->num_entries--;
 179
 180                         if (data_return)
 181                                 memcpy (data_return, entry->data, hash_table->data_size);
 182
 183                         sgen_free_internal (entry, hash_table->entry_mem_type);
 184
 185                         return TRUE;
 186                 }
 187                 prev = entry;
 188         }
 189
 190         return FALSE;
 191 }
 192
 193 void
 194 sgen_hash_table_clean (SgenHashTable *hash_table)
 195 {
 196         guint i;
 197
 198         if (!hash_table->size) {
 199                 g_assert (!hash_table->table);
 200                 g_assert (!hash_table->num_entries);
 201                 return;
 202         }
 203
 204         for (i = 0; i < hash_table->size; ++i) {
 205                 SgenHashTableEntry *entry = hash_table->table [i];
 206                 while (entry) {
 207                         SgenHashTableEntry *next = entry->next;
 208                         sgen_free_internal (entry, hash_table->entry_mem_type);
 209                         entry = next;
 210                 }
 211         }
 212
 213         sgen_free_internal_dynamic (hash_table->table, hash_table->size * sizeof (SgenHashTableEntry*), hash_table->table_mem_type);
 214
 215         hash_table->table = NULL;
 216         hash_table->size = 0;
 217         hash_table->num_entries = 0;
 218 }
 219
 220 #endif