/*
Copyright (c) 2008-2012 Red Hat, Inc. <http://www.redhat.com>
This file is part of GlusterFS.
This file is licensed to you under your choice of the GNU Lesser
General Public License, version 3 or any later version (LGPLv3 or
later), or the GNU General Public License, version 2 (GPLv2), in all
cases as published by the Free Software Foundation.
*/
#include "glusterfs/rbthash.h"
#include "rb.h"
#include "glusterfs/locking.h"
#include "glusterfs/mem-pool.h"
#include "glusterfs/logging.h"
#include "glusterfs/libglusterfs-messages.h"
#include <pthread.h>
#include <string.h>
int
rbthash_comparator(void *entry1, void *entry2, void *param)
{
int ret = 0;
rbthash_entry_t *e1 = NULL;
rbthash_entry_t *e2 = NULL;
if ((!entry1) || (!entry2) || (!param))
return -1;
e1 = (rbthash_entry_t *)entry1;
e2 = (rbthash_entry_t *)entry2;
if (e1->keylen != e2->keylen) {
if (e1->keylen < e2->keylen)
ret = -1;
else if (e1->keylen > e2->keylen)
ret = 1;
} else
ret = memcmp(e1->key, e2->key, e1->keylen);
return ret;
}
int
__rbthash_init_buckets(rbthash_table_t *tbl, int buckets)
{
int i = 0;
int ret = -1;
if (!tbl)
return -1;
for (; i < buckets; i++) {
LOCK_INIT(&tbl->buckets[i].bucketlock);
tbl->buckets[i].bucket = rb_create(
(rb_comparison_func *)rbthash_comparator, tbl, NULL);
if (!tbl->buckets[i].bucket) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RB_TABLE_CREATE_FAILED,
"Failed to "
"create rb table bucket");
ret = -1;
goto err;
}
}
ret = 0;
err:
return ret;
}
/*
* rbthash_table_init - Initialize a RBT based hash table
* @buckets - Number of buckets in the hash table
* @hfunc - hashing function
* @dfunc - destroyer for data in the RBT
* @expected_entries - Number of entries expected in RBT. Mutually exclusive
* with entrypool.
* @entrypool - Memory pool in lieu of expected_entries.
*/
rbthash_table_t *
rbthash_table_init(glusterfs_ctx_t *ctx, int buckets, rbt_hasher_t hfunc,
rbt_data_destroyer_t dfunc, unsigned long expected_entries,
struct mem_pool *entrypool)
{
rbthash_table_t *newtab = NULL;
int ret = -1;
if (!hfunc) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_HASH_FUNC_ERROR,
"Hash function not given");
return NULL;
}
if (!entrypool && !expected_entries) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_INVALID_ENTRY,
"Both mem-pool and expected entries not provided");
return NULL;
}
if (entrypool && expected_entries) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_INVALID_ENTRY,
"Both mem-pool and expected entries are provided");
return NULL;
}
newtab = GF_CALLOC(1, sizeof(*newtab), gf_common_mt_rbthash_table_t);
if (!newtab)
return NULL;
newtab->buckets = GF_CALLOC(buckets, sizeof(struct rbthash_bucket),
gf_common_mt_rbthash_bucket);
if (!newtab->buckets) {
goto free_newtab;
}
if (expected_entries) {
newtab->entrypool = mem_pool_new_ctx(ctx, rbthash_entry_t,
expected_entries);
if (!newtab->entrypool) {
goto free_buckets;
}
newtab->pool_alloced = _gf_true;
} else {
newtab->entrypool = entrypool;
}
LOCK_INIT(&newtab->tablelock);
INIT_LIST_HEAD(&newtab->list);
newtab->numbuckets = buckets;
ret = __rbthash_init_buckets(newtab, buckets);
if (ret == -1) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INIT_BUCKET_FAILED,
"Failed to init buckets");
if (newtab->pool_alloced)
mem_pool_destroy(newtab->entrypool);
} else {
gf_msg_trace(GF_RBTHASH, 0,
"Inited hash table: buckets:"
" %d",
buckets);
}
newtab->hashfunc = hfunc;
newtab->dfunc = dfunc;
free_buckets:
if (ret == -1)
GF_FREE(newtab->buckets);
free_newtab:
if (ret == -1) {
GF_FREE(newtab);
newtab = NULL;
}
return newtab;
}
rbthash_entry_t *
rbthash_init_entry(rbthash_table_t *tbl, void *data, void *key, int keylen)
{
int ret = -1;
rbthash_entry_t *entry = NULL;
if ((!tbl) || (!data) || (!key))
return NULL;
entry = mem_get(tbl->entrypool);
if (!entry) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_ENTRY_FAILED,
"Failed to get entry from mem-pool");
goto ret;
}
entry->data = data;
entry->key = GF_MALLOC(keylen, gf_common_mt_char);
if (!entry->key) {
goto free_entry;
}
INIT_LIST_HEAD(&entry->list);
memcpy(entry->key, key, keylen);
entry->keylen = keylen;
entry->keyhash = tbl->hashfunc(entry->key, entry->keylen);
gf_msg_trace(GF_RBTHASH, 0, "HASH: %u", entry->keyhash);
ret = 0;
free_entry:
if (ret == -1) {
mem_put(entry);
entry = NULL;
}
ret:
return entry;
}
void
rbthash_deinit_entry(rbthash_table_t *tbl, rbthash_entry_t *entry)
{
if (!entry)
return;
GF_FREE(entry->key);
if (tbl) {
if ((entry->data) && (tbl->dfunc))
tbl->dfunc(entry->data);
LOCK(&tbl->tablelock);
{
list_del_init(&entry->list);
}
UNLOCK(&tbl->tablelock);
mem_put(entry);
}
return;
}
static struct rbthash_bucket *
rbthash_entry_bucket(rbthash_table_t *tbl, rbthash_entry_t *entry)
{
int nbucket = 0;
nbucket = (entry->keyhash % tbl->numbuckets);
gf_msg_trace(GF_RBTHASH, 0, "BUCKET: %d", nbucket);
return &tbl->buckets[nbucket];
}
int
rbthash_insert_entry(rbthash_table_t *tbl, rbthash_entry_t *entry)
{
struct rbthash_bucket *bucket = NULL;
int ret = -1;
if ((!tbl) || (!entry))
return -1;
bucket = rbthash_entry_bucket(tbl, entry);
if (!bucket) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED,
"Failed to get bucket");
goto err;
}
ret = 0;
LOCK(&bucket->bucketlock);
{
if (!rb_probe(bucket->bucket, (void *)entry)) {
UNLOCK(&bucket->bucketlock);
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INSERT_FAILED,
"Failed to insert entry");
ret = -1;
goto err;
}
}
UNLOCK(&bucket->bucketlock);
err:
return ret;
}
int
rbthash_insert(rbthash_table_t *tbl, void *data, void *key, int keylen)
{
rbthash_entry_t *entry = NULL;
int ret = -1;
if ((!tbl) || (!data) || (!key))
return -1;
entry = rbthash_init_entry(tbl, data, key, keylen);
if (!entry) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INIT_ENTRY_FAILED,
"Failed to init entry");
goto err;
}
ret = rbthash_insert_entry(tbl, entry);
if (ret == -1) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INSERT_FAILED,
"Failed to insert entry");
rbthash_deinit_entry(tbl, entry);
goto err;
}
LOCK(&tbl->tablelock);
{
list_add_tail(&entry->list, &tbl->list);
}
UNLOCK(&tbl->tablelock);
err:
return ret;
}
static struct rbthash_bucket *
rbthash_key_bucket(rbthash_table_t *tbl, void *key, int keylen)
{
uint32_t keyhash = 0;
int nbucket = 0;
if ((!tbl) || (!key))
return NULL;
keyhash = tbl->hashfunc(key, keylen);
gf_msg_trace(GF_RBTHASH, 0, "HASH: %u", keyhash);
nbucket = (keyhash % tbl->numbuckets);
gf_msg_trace(GF_RBTHASH, 0, "BUCKET: %u", nbucket);
return &tbl->buckets[nbucket];
}
void *
rbthash_get(rbthash_table_t *tbl, void *key, int keylen)
{
struct rbthash_bucket *bucket = NULL;
rbthash_entry_t *entry = NULL;
rbthash_entry_t searchentry = {
0,
};
if ((!tbl) || (!key))
return NULL;
bucket = rbthash_key_bucket(tbl, key, keylen);
if (!bucket) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_GET_BUCKET_FAILED,
"Failed to get bucket");
return NULL;
}
searchentry.key = key;
searchentry.keylen = keylen;
LOCK(&bucket->bucketlock);
{
entry = rb_find(bucket->bucket, &searchentry);
}
UNLOCK(&bucket->bucketlock);
if (!entry)
return NULL;
return entry->data;
}
void *
rbthash_remove(rbthash_table_t *tbl, void *key, int keylen)
{
struct rbthash_bucket *bucket = NULL;
rbthash_entry_t *entry = NULL;
rbthash_entry_t searchentry = {
0,
};
void *dataref = NULL;
if ((!tbl) || (!key))
return NULL;
bucket = rbthash_key_bucket(tbl, key, keylen);
if (!bucket) {
gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED,
"Failed to get bucket");
return NULL;
}
searchentry.key = key;
searchentry.keylen = keylen;
LOCK(&bucket->bucketlock);
{
entry = rb_delete(bucket->bucket, &searchentry);
}
UNLOCK(&bucket->bucketlock);
if (!entry)
return NULL;
GF_FREE(entry->key);
dataref = entry->data;
LOCK(&tbl->tablelock);
{
list_del_init(&entry->list);
}
UNLOCK(&tbl->tablelock);
mem_put(entry);
return dataref;
}
void
rbthash_entry_deiniter(void *entry, void *rbparam)
{
if (!entry)
return;
rbthash_deinit_entry(rbparam, entry);
}
void
rbthash_table_destroy_buckets(rbthash_table_t *tbl)
{
int x = 0;
if (!tbl)
return;
for (; x < tbl->numbuckets; x++) {
LOCK_DESTROY(&tbl->buckets[x].bucketlock);
rb_destroy(tbl->buckets[x].bucket, rbthash_entry_deiniter);
}
return;
}
void
rbthash_table_destroy(rbthash_table_t *tbl)
{
if (!tbl)
return;
rbthash_table_destroy_buckets(tbl);
if (tbl->pool_alloced)
mem_pool_destroy(tbl->entrypool);
GF_FREE(tbl->buckets);
GF_FREE(tbl);
}
void
rbthash_table_traverse(rbthash_table_t *tbl, rbt_traverse_t traverse,
void *mydata)
{
rbthash_entry_t *entry = NULL;
if ((tbl == NULL) || (traverse == NULL)) {
goto out;
}
LOCK(&tbl->tablelock);
{
list_for_each_entry(entry, &tbl->list, list)
{
traverse(entry->data, mydata);
}
}
UNLOCK(&tbl->tablelock);
out:
return;
}