2 * mono-conc-hashtable.h: A mostly concurrent hashtable
5 * Rodrigo Kumpera (kumpera@gmail.com)
10 #include "mono-conc-hashtable.h"
11 #include <mono/utils/hazard-pointer.h>
13 /* Configuration knobs. */
15 #define INITIAL_SIZE 32
16 #define LOAD_FACTOR 0.75f
17 #define TOMBSTONE ((gpointer)(ssize_t)-1)
29 struct _MonoConcurrentHashTable {
30 volatile conc_table *table; /* goes to HP0 */
32 GEqualFunc equal_func;
36 GDestroyNotify key_destroy_func;
37 GDestroyNotify value_destroy_func;
41 conc_table_new (int size)
43 conc_table *res = g_new (conc_table, 1);
44 res->table_size = size;
45 res->kvs = g_new0 (key_value_pair, size);
50 conc_table_free (gpointer ptr)
52 conc_table *table = ptr;
58 conc_table_lf_free (conc_table *table)
60 mono_thread_hazardous_free_or_queue (table, conc_table_free, TRUE, FALSE);
65 A common problem with power of two hashtables is that it leads of bad clustering when dealing
68 The solution here is to mix the bits from two primes plus the hash itself, it produces a better spread
69 than just the numbers.
72 static MONO_ALWAYS_INLINE int
75 return ((hash * 215497) >> 16) ^ (hash * 1823231 + hash);
78 static MONO_ALWAYS_INLINE void
79 insert_one_local (conc_table *table, GHashFunc hash_func, gpointer key, gpointer value)
81 key_value_pair *kvs = table->kvs;
82 int table_mask = table->table_size - 1;
83 int hash = mix_hash (hash_func (key));
84 int i = hash & table_mask;
86 while (table->kvs [i].key)
87 i = (i + 1) & table_mask;
90 kvs [i].value = value;
93 /* LOCKING: Must be called holding hash_table->mutex */
95 expand_table (MonoConcurrentHashTable *hash_table)
97 conc_table *old_table = (conc_table*)hash_table->table;
98 conc_table *new_table = conc_table_new (old_table->table_size * 2);
99 key_value_pair *kvs = old_table->kvs;
102 for (i = 0; i < old_table->table_size; ++i) {
103 if (kvs [i].key && kvs [i].key != TOMBSTONE)
104 insert_one_local (new_table, hash_table->hash_func, kvs [i].key, kvs [i].value);
106 mono_memory_barrier ();
107 hash_table->table = new_table;
108 hash_table->overflow_count = (int)(new_table->table_size * LOAD_FACTOR);
109 conc_table_lf_free (old_table);
113 MonoConcurrentHashTable*
114 mono_conc_hashtable_new (mono_mutex_t *mutex, GHashFunc hash_func, GEqualFunc key_equal_func)
116 MonoConcurrentHashTable *res = g_new0 (MonoConcurrentHashTable, 1);
118 res->hash_func = hash_func ? hash_func : g_direct_hash;
119 res->equal_func = key_equal_func;
120 // res->equal_func = g_direct_equal;
121 res->table = conc_table_new (INITIAL_SIZE);
122 res->element_count = 0;
123 res->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
127 MonoConcurrentHashTable*
128 mono_conc_hashtable_new_full (mono_mutex_t *mutex, GHashFunc hash_func, GEqualFunc key_equal_func, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
130 MonoConcurrentHashTable *res = mono_conc_hashtable_new (mutex, hash_func, key_equal_func);
131 res->key_destroy_func = key_destroy_func;
132 res->value_destroy_func = value_destroy_func;
138 mono_conc_hashtable_destroy (MonoConcurrentHashTable *hash_table)
140 if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
142 conc_table *table = (conc_table*)hash_table->table;
143 key_value_pair *kvs = table->kvs;
145 for (i = 0; i < table->table_size; ++i) {
146 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
147 if (hash_table->key_destroy_func)
148 (hash_table->key_destroy_func) (kvs [i].key);
149 if (hash_table->value_destroy_func)
150 (hash_table->value_destroy_func) (kvs [i].value);
154 conc_table_free ((gpointer)hash_table->table);
159 mono_conc_hashtable_lookup (MonoConcurrentHashTable *hash_table, gpointer key)
161 MonoThreadHazardPointers* hp;
163 int hash, i, table_mask;
165 hash = mix_hash (hash_table->hash_func (key));
166 hp = mono_hazard_pointer_get ();
169 table = get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
170 table_mask = table->table_size - 1;
172 i = hash & table_mask;
174 if (G_LIKELY (!hash_table->equal_func)) {
175 while (kvs [i].key) {
176 if (key == kvs [i].key) {
178 /* The read of keys must happen before the read of values */
179 mono_memory_barrier ();
180 value = kvs [i].value;
181 /* FIXME check for NULL if we add suppport for removal */
182 mono_hazard_pointer_clear (hp, 0);
185 i = (i + 1) & table_mask;
188 GEqualFunc equal = hash_table->equal_func;
190 while (kvs [i].key) {
191 if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
193 /* The read of keys must happen before the read of values */
194 mono_memory_barrier ();
195 value = kvs [i].value;
197 /* We just read a value been deleted, try again. */
198 if (G_UNLIKELY (!value))
201 mono_hazard_pointer_clear (hp, 0);
204 i = (i + 1) & table_mask;
208 /* The table might have expanded and the value is now on the newer table */
209 mono_memory_barrier ();
210 if (hash_table->table != table)
213 mono_hazard_pointer_clear (hp, 0);
218 * mono_conc_hashtable_remove
220 * @Returns the old value if key is already present or null
223 mono_conc_hashtable_remove (MonoConcurrentHashTable *hash_table, gpointer key)
227 int hash, i, table_mask;
229 g_assert (key != NULL && key != TOMBSTONE);
231 hash = mix_hash (hash_table->hash_func (key));
232 mono_mutex_lock (hash_table->mutex);
234 table = (conc_table*)hash_table->table;
236 table_mask = table->table_size - 1;
237 i = hash & table_mask;
239 if (!hash_table->equal_func) {
242 mono_mutex_unlock (hash_table->mutex);
243 return NULL; /*key not found*/
246 if (key == kvs [i].key) {
247 gpointer value = kvs [i].value;
248 kvs [i].value = NULL;
249 mono_memory_barrier ();
250 kvs [i].key = TOMBSTONE;
252 mono_mutex_unlock (hash_table->mutex);
253 if (hash_table->key_destroy_func != NULL)
254 (*hash_table->key_destroy_func) (key);
255 if (hash_table->value_destroy_func != NULL)
256 (*hash_table->value_destroy_func) (value);
260 i = (i + 1) & table_mask;
263 GEqualFunc equal = hash_table->equal_func;
266 mono_mutex_unlock (hash_table->mutex);
267 return NULL; /*key not found*/
270 if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
271 gpointer old_key = kvs [i].key;
272 gpointer value = kvs [i].value;
273 kvs [i].value = NULL;
274 mono_memory_barrier ();
275 kvs [i].key = TOMBSTONE;
277 mono_mutex_unlock (hash_table->mutex);
278 if (hash_table->key_destroy_func != NULL)
279 (*hash_table->key_destroy_func) (old_key);
280 if (hash_table->value_destroy_func != NULL)
281 (*hash_table->value_destroy_func) (value);
285 i = (i + 1) & table_mask;
290 * mono_conc_hashtable_insert
292 * @Returns the old value if key is already present or null
295 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
299 int hash, i, table_mask;
301 g_assert (key != NULL && key != TOMBSTONE);
302 g_assert (value != NULL);
304 hash = mix_hash (hash_table->hash_func (key));
305 mono_mutex_lock (hash_table->mutex);
307 if (hash_table->element_count >= hash_table->overflow_count)
308 expand_table (hash_table);
310 table = (conc_table*)hash_table->table;
312 table_mask = table->table_size - 1;
313 i = hash & table_mask;
315 if (!hash_table->equal_func) {
317 if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
318 kvs [i].value = value;
319 /* The write to values must happen after the write to keys */
320 mono_memory_barrier ();
322 ++hash_table->element_count;
323 mono_mutex_unlock (hash_table->mutex);
326 if (key == kvs [i].key) {
327 gpointer value = kvs [i].value;
328 mono_mutex_unlock (hash_table->mutex);
331 i = (i + 1) & table_mask;
334 GEqualFunc equal = hash_table->equal_func;
336 if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
337 kvs [i].value = value;
338 /* The write to values must happen after the write to keys */
339 mono_memory_barrier ();
341 ++hash_table->element_count;
342 mono_mutex_unlock (hash_table->mutex);
345 if (equal (key, kvs [i].key)) {
346 gpointer value = kvs [i].value;
347 mono_mutex_unlock (hash_table->mutex);
350 i = (i + 1) & table_mask;