/**
|
* \file
|
* A mostly concurrent hashtable
|
*
|
* Author:
|
* Rodrigo Kumpera (kumpera@gmail.com)
|
*
|
* (C) 2014 Xamarin
|
*/
|
|
#include "mono-conc-hashtable.h"
|
#include <mono/utils/hazard-pointer.h>
|
|
/* Configuration knobs. */
|
|
#define INITIAL_SIZE 32
|
#define LOAD_FACTOR 0.75f
|
#define TOMBSTONE ((gpointer)(ssize_t)-1)
|
|
typedef struct {
|
gpointer key;
|
gpointer value;
|
} key_value_pair;
|
|
typedef struct {
|
int table_size;
|
key_value_pair *kvs;
|
} conc_table;
|
|
struct _MonoConcurrentHashTable {
|
volatile conc_table *table; /* goes to HP0 */
|
GHashFunc hash_func;
|
GEqualFunc equal_func;
|
int element_count;
|
int overflow_count;
|
GDestroyNotify key_destroy_func;
|
GDestroyNotify value_destroy_func;
|
};
|
|
static conc_table*
|
conc_table_new (int size)
|
{
|
conc_table *res = g_new (conc_table, 1);
|
res->table_size = size;
|
res->kvs = g_new0 (key_value_pair, size);
|
return res;
|
}
|
|
static void
|
conc_table_free (gpointer ptr)
|
{
|
conc_table *table = (conc_table *)ptr;
|
g_free (table->kvs);
|
g_free (table);
|
}
|
|
static void
|
conc_table_lf_free (conc_table *table)
|
{
|
mono_thread_hazardous_try_free (table, conc_table_free);
|
}
|
|
|
/*
|
A common problem with power of two hashtables is that it leads of bad clustering when dealing
|
with aligned numbers.
|
|
The solution here is to mix the bits from two primes plus the hash itself, it produces a better spread
|
than just the numbers.
|
*/
|
|
static MONO_ALWAYS_INLINE int
|
mix_hash (int hash)
|
{
|
return ((hash * 215497) >> 16) ^ (hash * 1823231 + hash);
|
}
|
|
static MONO_ALWAYS_INLINE void
|
insert_one_local (conc_table *table, GHashFunc hash_func, gpointer key, gpointer value)
|
{
|
key_value_pair *kvs = table->kvs;
|
int table_mask = table->table_size - 1;
|
int hash = mix_hash (hash_func (key));
|
int i = hash & table_mask;
|
|
while (table->kvs [i].key)
|
i = (i + 1) & table_mask;
|
|
kvs [i].key = key;
|
kvs [i].value = value;
|
}
|
|
/* LOCKING: Must be called holding hash_table->mutex */
|
static void
|
expand_table (MonoConcurrentHashTable *hash_table)
|
{
|
conc_table *old_table = (conc_table*)hash_table->table;
|
conc_table *new_table = conc_table_new (old_table->table_size * 2);
|
key_value_pair *kvs = old_table->kvs;
|
int i;
|
|
for (i = 0; i < old_table->table_size; ++i) {
|
if (kvs [i].key && kvs [i].key != TOMBSTONE)
|
insert_one_local (new_table, hash_table->hash_func, kvs [i].key, kvs [i].value);
|
}
|
mono_memory_barrier ();
|
hash_table->table = new_table;
|
hash_table->overflow_count = (int)(new_table->table_size * LOAD_FACTOR);
|
conc_table_lf_free (old_table);
|
}
|
|
|
MonoConcurrentHashTable*
|
mono_conc_hashtable_new (GHashFunc hash_func, GEqualFunc key_equal_func)
|
{
|
MonoConcurrentHashTable *res = g_new0 (MonoConcurrentHashTable, 1);
|
res->hash_func = hash_func ? hash_func : g_direct_hash;
|
res->equal_func = key_equal_func;
|
// res->equal_func = g_direct_equal;
|
res->table = conc_table_new (INITIAL_SIZE);
|
res->element_count = 0;
|
res->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
|
return res;
|
}
|
|
MonoConcurrentHashTable*
|
mono_conc_hashtable_new_full (GHashFunc hash_func, GEqualFunc key_equal_func, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
|
{
|
MonoConcurrentHashTable *res = mono_conc_hashtable_new (hash_func, key_equal_func);
|
res->key_destroy_func = key_destroy_func;
|
res->value_destroy_func = value_destroy_func;
|
return res;
|
}
|
|
|
void
|
mono_conc_hashtable_destroy (MonoConcurrentHashTable *hash_table)
|
{
|
if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
|
int i;
|
conc_table *table = (conc_table*)hash_table->table;
|
key_value_pair *kvs = table->kvs;
|
|
for (i = 0; i < table->table_size; ++i) {
|
if (kvs [i].key && kvs [i].key != TOMBSTONE) {
|
if (hash_table->key_destroy_func)
|
(hash_table->key_destroy_func) (kvs [i].key);
|
if (hash_table->value_destroy_func)
|
(hash_table->value_destroy_func) (kvs [i].value);
|
}
|
}
|
}
|
conc_table_free ((gpointer)hash_table->table);
|
g_free (hash_table);
|
}
|
|
gpointer
|
mono_conc_hashtable_lookup (MonoConcurrentHashTable *hash_table, gpointer key)
|
{
|
MonoThreadHazardPointers* hp;
|
conc_table *table;
|
int hash, i, table_mask;
|
key_value_pair *kvs;
|
hash = mix_hash (hash_table->hash_func (key));
|
hp = mono_hazard_pointer_get ();
|
|
retry:
|
table = (conc_table *)mono_get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
|
table_mask = table->table_size - 1;
|
kvs = table->kvs;
|
i = hash & table_mask;
|
|
if (G_LIKELY (!hash_table->equal_func)) {
|
while (kvs [i].key) {
|
if (key == kvs [i].key) {
|
gpointer value;
|
/* The read of keys must happen before the read of values */
|
mono_memory_barrier ();
|
value = kvs [i].value;
|
/* FIXME check for NULL if we add suppport for removal */
|
mono_hazard_pointer_clear (hp, 0);
|
return value;
|
}
|
i = (i + 1) & table_mask;
|
}
|
} else {
|
GEqualFunc equal = hash_table->equal_func;
|
|
while (kvs [i].key) {
|
if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
|
gpointer value;
|
/* The read of keys must happen before the read of values */
|
mono_memory_barrier ();
|
value = kvs [i].value;
|
|
/* We just read a value been deleted, try again. */
|
if (G_UNLIKELY (!value))
|
goto retry;
|
|
mono_hazard_pointer_clear (hp, 0);
|
return value;
|
}
|
i = (i + 1) & table_mask;
|
}
|
}
|
|
/* The table might have expanded and the value is now on the newer table */
|
mono_memory_barrier ();
|
if (hash_table->table != table)
|
goto retry;
|
|
mono_hazard_pointer_clear (hp, 0);
|
return NULL;
|
}
|
|
/**
|
* mono_conc_hashtable_remove:
|
* Remove a value from the hashtable. Requires external locking
|
* \returns the old value if \p key is already present or NULL
|
*/
|
gpointer
|
mono_conc_hashtable_remove (MonoConcurrentHashTable *hash_table, gpointer key)
|
{
|
conc_table *table;
|
key_value_pair *kvs;
|
int hash, i, table_mask;
|
|
g_assert (key != NULL && key != TOMBSTONE);
|
|
hash = mix_hash (hash_table->hash_func (key));
|
|
table = (conc_table*)hash_table->table;
|
kvs = table->kvs;
|
table_mask = table->table_size - 1;
|
i = hash & table_mask;
|
|
if (!hash_table->equal_func) {
|
for (;;) {
|
if (!kvs [i].key) {
|
return NULL; /*key not found*/
|
}
|
|
if (key == kvs [i].key) {
|
gpointer value = kvs [i].value;
|
kvs [i].value = NULL;
|
mono_memory_barrier ();
|
kvs [i].key = TOMBSTONE;
|
--hash_table->element_count;
|
|
if (hash_table->key_destroy_func != NULL)
|
(*hash_table->key_destroy_func) (key);
|
if (hash_table->value_destroy_func != NULL)
|
(*hash_table->value_destroy_func) (value);
|
|
return value;
|
}
|
i = (i + 1) & table_mask;
|
}
|
} else {
|
GEqualFunc equal = hash_table->equal_func;
|
for (;;) {
|
if (!kvs [i].key) {
|
return NULL; /*key not found*/
|
}
|
|
if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
|
gpointer old_key = kvs [i].key;
|
gpointer value = kvs [i].value;
|
kvs [i].value = NULL;
|
mono_memory_barrier ();
|
kvs [i].key = TOMBSTONE;
|
|
if (hash_table->key_destroy_func != NULL)
|
(*hash_table->key_destroy_func) (old_key);
|
if (hash_table->value_destroy_func != NULL)
|
(*hash_table->value_destroy_func) (value);
|
return value;
|
}
|
|
i = (i + 1) & table_mask;
|
}
|
}
|
}
|
/**
|
* mono_conc_hashtable_insert:
|
* Insert a value into the hashtable. Requires external locking.
|
* \returns the old value if \p key is already present or NULL
|
*/
|
gpointer
|
mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
|
{
|
conc_table *table;
|
key_value_pair *kvs;
|
int hash, i, table_mask;
|
|
g_assert (key != NULL && key != TOMBSTONE);
|
g_assert (value != NULL);
|
|
hash = mix_hash (hash_table->hash_func (key));
|
|
if (hash_table->element_count >= hash_table->overflow_count)
|
expand_table (hash_table);
|
|
table = (conc_table*)hash_table->table;
|
kvs = table->kvs;
|
table_mask = table->table_size - 1;
|
i = hash & table_mask;
|
|
if (!hash_table->equal_func) {
|
for (;;) {
|
if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
|
kvs [i].value = value;
|
/* The write to values must happen after the write to keys */
|
mono_memory_barrier ();
|
kvs [i].key = key;
|
++hash_table->element_count;
|
return NULL;
|
}
|
if (key == kvs [i].key) {
|
gpointer value = kvs [i].value;
|
return value;
|
}
|
i = (i + 1) & table_mask;
|
}
|
} else {
|
GEqualFunc equal = hash_table->equal_func;
|
for (;;) {
|
if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
|
kvs [i].value = value;
|
/* The write to values must happen after the write to keys */
|
mono_memory_barrier ();
|
kvs [i].key = key;
|
++hash_table->element_count;
|
return NULL;
|
}
|
if (equal (key, kvs [i].key)) {
|
gpointer value = kvs [i].value;
|
return value;
|
}
|
i = (i + 1) & table_mask;
|
}
|
}
|
}
|
|
/**
|
* mono_conc_hashtable_foreach:
|
* Calls \p func for each value in the hashtable. Requires external locking.
|
*/
|
void
|
mono_conc_hashtable_foreach (MonoConcurrentHashTable *hash_table, GHFunc func, gpointer userdata)
|
{
|
int i;
|
conc_table *table = (conc_table*)hash_table->table;
|
key_value_pair *kvs = table->kvs;
|
|
for (i = 0; i < table->table_size; ++i) {
|
if (kvs [i].key && kvs [i].key != TOMBSTONE) {
|
func (kvs [i].key, kvs [i].value, userdata);
|
}
|
}
|
}
|
|
/**
|
* mono_conc_hashtable_foreach_steal:
|
*
|
* Calls @func for each entry in the hashtable, if @func returns true, remove from the hashtable. Requires external locking.
|
* Same semantics as g_hash_table_foreach_steal.
|
*/
|
void
|
mono_conc_hashtable_foreach_steal (MonoConcurrentHashTable *hash_table, GHRFunc func, gpointer userdata)
|
{
|
int i;
|
conc_table *table = (conc_table*)hash_table->table;
|
key_value_pair *kvs = table->kvs;
|
|
for (i = 0; i < table->table_size; ++i) {
|
if (kvs [i].key && kvs [i].key != TOMBSTONE) {
|
if (func (kvs [i].key, kvs [i].value, userdata)) {
|
kvs [i].value = NULL;
|
mono_memory_barrier ();
|
kvs [i].key = TOMBSTONE;
|
--hash_table->element_count;
|
}
|
}
|
}
|
}
|
