/*
* %CopyrightBegin%
*
* Copyright Ericsson AB 2008-2009. All Rights Reserved.
*
* The contents of this file are subject to the Erlang Public License,
* Version 1.1, (the "License"); you may not use this file except in
* compliance with the License. You should have received a copy of the
* Erlang Public License along with this software. If not, it can be
* retrieved online at http://www.erlang.org/.
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
* the License for the specific language governing rights and limitations
* under the License.
*
* %CopyrightEnd%
*/
/*
** General thread safe hash table. Simular interface as hash.h
**
** Author: Sverker Eriksson
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#include "safe_hash.h"
/* Currently only used by erl_check_io on Windows */
#ifndef ERTS_SYS_CONTINOUS_FD_NUMBERS
static ERTS_INLINE void set_size(SafeHash* h, int size)
{
ASSERT(size % SAFE_HASH_LOCK_CNT == 0);
/* This important property allows us to lock the right mutex
** without reading the table size (that can change without the lock) */
h->size_mask = size - 1;
ASSERT((size & h->size_mask) == 0);
/* An even power of 2 is just for fast bit masking */
h->grow_limit = size; /* grow table at 100% load */
}
static ERTS_INLINE int align_up_pow2(int val)
{
int x = val & (val-1);
if (x==0) return val ? val : 1;
do {
val = x;
x &= x - 1;
}while (x);
return val << 1;
}
/*
** Rehash all objects
*/
static void rehash(SafeHash* h, int grow_limit)
{
if (erts_smp_atomic_xchg(&h->is_rehashing, 1) != 0) {
return; /* already in progress */
}
if (h->grow_limit == grow_limit) {
int i, size, bytes;
SafeHashBucket** new_tab;
SafeHashBucket** old_tab = h->tab;
int old_size = h->size_mask + 1;
size = old_size * 2; /* double table size */
bytes = size * sizeof(SafeHashBucket*);
new_tab = (SafeHashBucket **) erts_alloc(h->type, bytes);
sys_memzero(new_tab, bytes);
for (i=0; i<SAFE_HASH_LOCK_CNT; i++) { /* stop all traffic */
erts_smp_mtx_lock(&h->lock_vec[i].mtx);
}
h->tab = new_tab;
set_size(h, size);
for (i = 0; i < old_size; i++) {
SafeHashBucket* b = old_tab[i];
while (b != NULL) {
SafeHashBucket* b_next = b->next;
int ix = b->hvalue & h->size_mask;
b->next = new_tab[ix];
new_tab[ix] = b;
b = b_next;
}
}
for (i=0; i<SAFE_HASH_LOCK_CNT; i++) {
erts_smp_mtx_unlock(&h->lock_vec[i].mtx);
}
erts_free(h->type, (void *) old_tab);
}
/*else already done */
erts_smp_atomic_set(&h->is_rehashing, 0);
}
/*
** Get info about hash
*/
void safe_hash_get_info(SafeHashInfo *hi, SafeHash *h)
{
int size;
int i, lock_ix;
int max_depth = 0;
int objects = 0;
for (lock_ix=0; lock_ix<SAFE_HASH_LOCK_CNT; lock_ix++) {
erts_smp_mtx_lock(&h->lock_vec[lock_ix].mtx);
size = h->size_mask + 1;
for (i = lock_ix; i < size; i += SAFE_HASH_LOCK_CNT) {
int depth = 0;
SafeHashBucket* b = h->tab[i];
while (b != NULL) {
objects++;
depth++;
b = b->next;
}
if (depth > max_depth)
max_depth = depth;
}
erts_smp_mtx_unlock(&h->lock_vec[lock_ix].mtx);
}
hi->name = h->name;
hi->size = size;
hi->objs = objects;
hi->depth = max_depth;
}
/*
** Returns size of table in bytes. Stored objects not included.
**/
int safe_hash_table_sz(SafeHash *h)
{
int i, size;
for(i=0; h->name[i]; i++);
i++;
erts_smp_mtx_lock(&h->lock_vec[0].mtx); /* any lock will do to read size */
size = h->size_mask + 1;
erts_smp_mtx_unlock(&h->lock_vec[0].mtx);
return sizeof(SafeHash) + size*sizeof(SafeHashBucket*) + i;
}
/*
** Init a pre allocated or static hash structure
** and allocate buckets. NOT SAFE
*/
SafeHash* safe_hash_init(ErtsAlcType_t type, SafeHash* h, char* name, int size, SafeHashFunctions fun)
{
int i, bytes;
size = align_up_pow2(size);
bytes = size * sizeof(SafeHashBucket*);
h->type = type;
h->tab = (SafeHashBucket**) erts_alloc(h->type, bytes);
sys_memzero(h->tab, bytes);
h->name = name;
h->fun = fun;
set_size(h,size);
erts_smp_atomic_init(&h->is_rehashing, 0);
erts_smp_atomic_init(&h->nitems, 0);
for (i=0; i<SAFE_HASH_LOCK_CNT; i++) {
erts_smp_mtx_init(&h->lock_vec[i].mtx,"safe_hash");
}
return h;
}
/*
** Find an object in the hash table
*/
void* safe_hash_get(SafeHash* h, void* tmpl)
{
SafeHashValue hval = h->fun.hash(tmpl);
SafeHashBucket* b;
erts_smp_mtx_t* lock = &h->lock_vec[hval % SAFE_HASH_LOCK_CNT].mtx;
erts_smp_mtx_lock(lock);
b = h->tab[hval & h->size_mask];
while(b != NULL) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0))
break;
b = b->next;
}
erts_smp_mtx_unlock(lock);
return (void*) b;
}
/*
** Find or insert an object in the hash table
*/
void* safe_hash_put(SafeHash* h, void* tmpl)
{
int grow_limit;
SafeHashValue hval = h->fun.hash(tmpl);
SafeHashBucket* b;
SafeHashBucket** head;
erts_smp_mtx_t* lock = &h->lock_vec[hval % SAFE_HASH_LOCK_CNT].mtx;
erts_smp_mtx_lock(lock);
head = &h->tab[hval & h->size_mask];
b = *head;
while(b != NULL) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0)) {
erts_smp_mtx_unlock(lock);
return b;
}
b = b->next;
}
b = (SafeHashBucket*) h->fun.alloc(tmpl);
b->hvalue = hval;
b->next = *head;
*head = b;
grow_limit = h->grow_limit;
erts_smp_mtx_unlock(lock);
if (erts_smp_atomic_inctest(&h->nitems) > grow_limit) {
rehash(h, grow_limit);
}
return (void*) b;
}
/*
** Erase hash entry return template if erased
** return 0 if not erased
*/
void* safe_hash_erase(SafeHash* h, void* tmpl)
{
SafeHashValue hval = h->fun.hash(tmpl);
SafeHashBucket* b;
SafeHashBucket** prevp;
erts_smp_mtx_t* lock = &h->lock_vec[hval % SAFE_HASH_LOCK_CNT].mtx;
erts_smp_mtx_lock(lock);
prevp = &h->tab[hval & h->size_mask];
b = *prevp;
while(b != NULL) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0)) {
*prevp = b->next;
erts_smp_mtx_unlock(lock);
erts_smp_atomic_dec(&h->nitems);
h->fun.free((void*)b);
return tmpl;
}
prevp = &b->next;
b = b->next;
}
erts_smp_mtx_unlock(lock);
return NULL;
}
/*
** Call 'func(obj,func_arg2)' for all objects in table. NOT SAFE!!!
*/
void safe_hash_for_each(SafeHash* h, void (*func)(void *, void *), void *func_arg2)
{
int i;
for (i = 0; i <= h->size_mask; i++) {
SafeHashBucket* b = h->tab[i];
while (b != NULL) {
(*func)((void *) b, func_arg2);
b = b->next;
}
}
}
#endif /* !ERTS_SYS_CONTINOUS_FD_NUMBERS */
