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;
35 GDestroyNotify key_destroy_func;
36 GDestroyNotify value_destroy_func;
40 conc_table_new (int size)
42 conc_table *res = g_new (conc_table, 1);
43 res->table_size = size;
44 res->kvs = g_new0 (key_value_pair, size);
49 conc_table_free (gpointer ptr)
51 conc_table *table = (conc_table *)ptr;
57 conc_table_lf_free (conc_table *table)
59 mono_thread_hazardous_try_free (table, conc_table_free);
64 A common problem with power of two hashtables is that it leads of bad clustering when dealing
67 The solution here is to mix the bits from two primes plus the hash itself, it produces a better spread
68 than just the numbers.
71 static MONO_ALWAYS_INLINE int
74 return ((hash * 215497) >> 16) ^ (hash * 1823231 + hash);
77 static MONO_ALWAYS_INLINE void
78 insert_one_local (conc_table *table, GHashFunc hash_func, gpointer key, gpointer value)
80 key_value_pair *kvs = table->kvs;
81 int table_mask = table->table_size - 1;
82 int hash = mix_hash (hash_func (key));
83 int i = hash & table_mask;
85 while (table->kvs [i].key)
86 i = (i + 1) & table_mask;
89 kvs [i].value = value;
92 /* LOCKING: Must be called holding hash_table->mutex */
94 expand_table (MonoConcurrentHashTable *hash_table)
96 conc_table *old_table = (conc_table*)hash_table->table;
97 conc_table *new_table = conc_table_new (old_table->table_size * 2);
98 key_value_pair *kvs = old_table->kvs;
101 for (i = 0; i < old_table->table_size; ++i) {
102 if (kvs [i].key && kvs [i].key != TOMBSTONE)
103 insert_one_local (new_table, hash_table->hash_func, kvs [i].key, kvs [i].value);
105 mono_memory_barrier ();
106 hash_table->table = new_table;
107 hash_table->overflow_count = (int)(new_table->table_size * LOAD_FACTOR);
108 conc_table_lf_free (old_table);
112 MonoConcurrentHashTable*
113 mono_conc_hashtable_new (GHashFunc hash_func, GEqualFunc key_equal_func)
115 MonoConcurrentHashTable *res = g_new0 (MonoConcurrentHashTable, 1);
116 res->hash_func = hash_func ? hash_func : g_direct_hash;
117 res->equal_func = key_equal_func ? key_equal_func : g_direct_equal;
118 // res->equal_func = g_direct_equal;
119 res->table = conc_table_new (INITIAL_SIZE);
120 res->element_count = 0;
121 res->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
125 MonoConcurrentHashTable*
126 mono_conc_hashtable_new_full (GHashFunc hash_func, GEqualFunc key_equal_func, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
128 MonoConcurrentHashTable *res = mono_conc_hashtable_new (hash_func, key_equal_func);
129 res->key_destroy_func = key_destroy_func;
130 res->value_destroy_func = value_destroy_func;
136 mono_conc_hashtable_destroy (MonoConcurrentHashTable *hash_table)
138 if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
140 conc_table *table = (conc_table*)hash_table->table;
141 key_value_pair *kvs = table->kvs;
143 for (i = 0; i < table->table_size; ++i) {
144 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
145 if (hash_table->key_destroy_func)
146 (hash_table->key_destroy_func) (kvs [i].key);
147 if (hash_table->value_destroy_func)
148 (hash_table->value_destroy_func) (kvs [i].value);
152 conc_table_free ((gpointer)hash_table->table);
157 mono_conc_hashtable_lookup (MonoConcurrentHashTable *hash_table, gpointer key)
159 MonoThreadHazardPointers* hp;
161 int hash, i, table_mask;
163 hash = mix_hash (hash_table->hash_func (key));
164 hp = mono_hazard_pointer_get ();
167 table = (conc_table *)mono_get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
168 table_mask = table->table_size - 1;
170 i = hash & table_mask;
172 if (G_LIKELY (!hash_table->equal_func)) {
173 while (kvs [i].key) {
174 if (key == kvs [i].key) {
176 /* The read of keys must happen before the read of values */
177 mono_memory_barrier ();
178 value = kvs [i].value;
179 /* FIXME check for NULL if we add suppport for removal */
180 mono_hazard_pointer_clear (hp, 0);
183 i = (i + 1) & table_mask;
186 GEqualFunc equal = hash_table->equal_func;
188 while (kvs [i].key) {
189 if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
191 /* The read of keys must happen before the read of values */
192 mono_memory_barrier ();
193 value = kvs [i].value;
195 /* We just read a value been deleted, try again. */
196 if (G_UNLIKELY (!value))
199 mono_hazard_pointer_clear (hp, 0);
202 i = (i + 1) & table_mask;
206 /* The table might have expanded and the value is now on the newer table */
207 mono_memory_barrier ();
208 if (hash_table->table != table)
211 mono_hazard_pointer_clear (hp, 0);
216 * mono_conc_hashtable_remove:
218 * Remove a value from the hashtable. Requires external locking
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));
233 table = (conc_table*)hash_table->table;
235 table_mask = table->table_size - 1;
236 i = hash & table_mask;
238 if (!hash_table->equal_func) {
241 return NULL; /*key not found*/
244 if (key == kvs [i].key) {
245 gpointer value = kvs [i].value;
246 kvs [i].value = NULL;
247 mono_memory_barrier ();
248 kvs [i].key = TOMBSTONE;
250 if (hash_table->key_destroy_func != NULL)
251 (*hash_table->key_destroy_func) (key);
252 if (hash_table->value_destroy_func != NULL)
253 (*hash_table->value_destroy_func) (value);
257 i = (i + 1) & table_mask;
260 GEqualFunc equal = hash_table->equal_func;
263 return NULL; /*key not found*/
266 if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
267 gpointer old_key = kvs [i].key;
268 gpointer value = kvs [i].value;
269 kvs [i].value = NULL;
270 mono_memory_barrier ();
271 kvs [i].key = TOMBSTONE;
273 if (hash_table->key_destroy_func != NULL)
274 (*hash_table->key_destroy_func) (old_key);
275 if (hash_table->value_destroy_func != NULL)
276 (*hash_table->value_destroy_func) (value);
280 i = (i + 1) & table_mask;
285 * mono_conc_hashtable_insert:
287 * Insert a value into the hashtable. Requires external locking.
288 * @Returns the old value if key is already present or null
291 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
295 int hash, i, table_mask;
297 g_assert (key != NULL && key != TOMBSTONE);
298 g_assert (value != NULL);
300 hash = mix_hash (hash_table->hash_func (key));
302 if (hash_table->element_count >= hash_table->overflow_count)
303 expand_table (hash_table);
305 table = (conc_table*)hash_table->table;
307 table_mask = table->table_size - 1;
308 i = hash & table_mask;
310 if (!hash_table->equal_func) {
312 if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
313 kvs [i].value = value;
314 /* The write to values must happen after the write to keys */
315 mono_memory_barrier ();
317 ++hash_table->element_count;
320 if (key == kvs [i].key) {
321 gpointer value = kvs [i].value;
324 i = (i + 1) & table_mask;
327 GEqualFunc equal = hash_table->equal_func;
329 if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
330 kvs [i].value = value;
331 /* The write to values must happen after the write to keys */
332 mono_memory_barrier ();
334 ++hash_table->element_count;
337 if (equal (key, kvs [i].key)) {
338 gpointer value = kvs [i].value;
341 i = (i + 1) & table_mask;
347 * mono_conc_hashtable_foreach:
349 * Calls @func for each value in the hashtable. Requires external locking.
352 mono_conc_hashtable_foreach (MonoConcurrentHashTable *hash_table, GHFunc func, gpointer userdata)
355 conc_table *table = (conc_table*)hash_table->table;
356 key_value_pair *kvs = table->kvs;
358 for (i = 0; i < table->table_size; ++i) {
359 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
360 func (kvs [i].key, kvs [i].value, userdata);