From f3e46f2cb44e95c453bfa20c870dca6e42fc9a7a Mon Sep 17 00:00:00 2001 From: Shehjar Tikoo Date: Mon, 5 Oct 2009 07:42:02 +0000 Subject: core: Add rbtree based hash table Signed-off-by: Anand V. Avati BUG: 145 (NFSv3 related additions to 2.1 task list) URL: http://bugs.gluster.com/cgi-bin/bugzilla3/show_bug.cgi?id=145 --- libglusterfs/src/Makefile.am | 6 +- libglusterfs/src/rbthash.c | 388 +++++++++++++++++++++++++++++++++++++++++++ libglusterfs/src/rbthash.h | 75 +++++++++ 3 files changed, 466 insertions(+), 3 deletions(-) create mode 100644 libglusterfs/src/rbthash.c create mode 100644 libglusterfs/src/rbthash.h (limited to 'libglusterfs/src') diff --git a/libglusterfs/src/Makefile.am b/libglusterfs/src/Makefile.am index 05d124aeea1..90f8b65d532 100644 --- a/libglusterfs/src/Makefile.am +++ b/libglusterfs/src/Makefile.am @@ -1,14 +1,14 @@ libglusterfs_la_CFLAGS = -fPIC -Wall -g -shared -nostartfiles $(GF_CFLAGS) $(GF_DARWIN_LIBGLUSTERFS_CFLAGS) -libglusterfs_la_CPPFLAGS = -D_FILE_OFFSET_BITS=64 -D__USE_FILE_OFFSET64 -D_GNU_SOURCE -DXLATORDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/xlator\" -DSCHEDULERDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/scheduler\" -DTRANSPORTDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/transport\" -D$(GF_HOST_OS) -DLIBDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/auth\" +libglusterfs_la_CPPFLAGS = -D_FILE_OFFSET_BITS=64 -D__USE_FILE_OFFSET64 -D_GNU_SOURCE -DXLATORDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/xlator\" -DSCHEDULERDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/scheduler\" -DTRANSPORTDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/transport\" -D$(GF_HOST_OS) -DLIBDIR=\"$(libdir)/glusterfs/$(PACKAGE_VERSION)/auth\" -I$(CONTRIBDIR)/rbtree libglusterfs_la_LIBADD = @LEXLIB@ lib_LTLIBRARIES = libglusterfs.la -libglusterfs_la_SOURCES = dict.c spec.lex.c y.tab.c xlator.c logging.c hashfn.c defaults.c scheduler.c common-utils.c transport.c timer.c inode.c call-stub.c compat.c authenticate.c fd.c compat-errno.c event.c mem-pool.c gf-dirent.c syscall.c iobuf.c globals.c statedump.c stack.c checksum.c md5.c +libglusterfs_la_SOURCES = dict.c spec.lex.c y.tab.c xlator.c logging.c hashfn.c defaults.c scheduler.c common-utils.c transport.c timer.c inode.c call-stub.c compat.c authenticate.c fd.c compat-errno.c event.c mem-pool.c gf-dirent.c syscall.c iobuf.c globals.c statedump.c stack.c checksum.c md5.c $(CONTRIBDIR)/rbtree/rb.c rbthash.c -noinst_HEADERS = common-utils.h defaults.h dict.h glusterfs.h hashfn.h logging.h protocol.h scheduler.h xlator.h transport.h stack.h timer.h list.h inode.h call-stub.h compat.h authenticate.h fd.h revision.h compat-errno.h event.h mem-pool.h byte-order.h gf-dirent.h locking.h syscall.h iobuf.h globals.h statedump.h checksum.h md5.h +noinst_HEADERS = common-utils.h defaults.h dict.h glusterfs.h hashfn.h logging.h protocol.h scheduler.h xlator.h transport.h stack.h timer.h list.h inode.h call-stub.h compat.h authenticate.h fd.h revision.h compat-errno.h event.h mem-pool.h byte-order.h gf-dirent.h locking.h syscall.h iobuf.h globals.h statedump.h checksum.h md5.h $(CONTRIBDIR)/rbtree/rb.h rbthash.h EXTRA_DIST = spec.l spec.y diff --git a/libglusterfs/src/rbthash.c b/libglusterfs/src/rbthash.c new file mode 100644 index 00000000000..829257448ea --- /dev/null +++ b/libglusterfs/src/rbthash.c @@ -0,0 +1,388 @@ +/* + Copyright (c) 2008-2009 Z RESEARCH, Inc. + This file is part of GlusterFS. + + GlusterFS is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3 of the License, + or (at your option) any later version. + + GlusterFS is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see + . +*/ + + +#include "rbthash.h" +#include "rb.h" +#include "locking.h" +#include "mem-pool.h" +#include "logging.h" + +#include +#include + + +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_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to create rb" + " table bucket"); + ret = -1; + goto err; + } + } + + ret = 0; +err: + return ret; +} + + +rbthash_table_t * +rbthash_table_init (int buckets, rbt_hasher_t hfunc, rbt_data_destroyer_t dfunc) +{ + rbthash_table_t *newtab = NULL; + int ret = -1; + + if (!hfunc) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Hash function not given"); + return NULL; + } + + newtab = CALLOC (1, sizeof (*newtab)); + if (!newtab) + return NULL; + + newtab->buckets = CALLOC (buckets, sizeof (struct rbthash_bucket)); + if (!newtab->buckets) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to allocate memory"); + goto free_newtab; + } + + newtab->entrypool = mem_pool_new (rbthash_entry_t, GF_RBTHASH_MEMPOOL); + if (!newtab->entrypool) { + gf_log (GF_RBTHASH, GF_LOG_ERROR,"Failed to allocate mem-pool"); + goto free_buckets; + } + + LOCK_INIT (&newtab->tablelock); + newtab->numbuckets = buckets; + ret = __rbthash_init_buckets (newtab, buckets); + + if (ret == -1) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to init buckets"); + mem_pool_destroy (newtab->entrypool); + } else + gf_log (GF_RBTHASH, GF_LOG_TRACE, "Inited hash table: buckets:" + " %d", buckets); + + newtab->hashfunc = hfunc; + newtab->dfunc = dfunc; +free_buckets: + if (ret == -1) + FREE (newtab->buckets); + +free_newtab: + if (ret == -1) { + 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_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to get entry from" + " mem-pool"); + goto ret; + } + + entry->data = data; + entry->key = CALLOC (keylen, sizeof (char)); + if (!entry->key) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Memory allocation failed"); + goto free_entry; + } + + memcpy (entry->key, key, keylen); + entry->keylen = keylen; + entry->keyhash = tbl->hashfunc (entry->key, entry->keylen); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "HASH: %u", entry->keyhash); + + ret = 0; +free_entry: + if (ret == -1) { + mem_put (tbl->entrypool, entry); + entry = NULL; + } + +ret: + return entry; +} + + +void +rbthash_deinit_entry (rbthash_table_t *tbl, rbthash_entry_t *entry) +{ + + if (!entry) + return; + + if (entry->key) + FREE (entry->key); + + if (tbl) { + if ((entry->data) && (tbl->dfunc)) + tbl->dfunc (entry->data); + mem_put (tbl->entrypool, entry); + } + + return; +} + + +inline struct rbthash_bucket * +rbthash_entry_bucket (rbthash_table_t *tbl, rbthash_entry_t * entry) +{ + int nbucket = 0; + + nbucket = (entry->keyhash % tbl->numbuckets); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "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_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to get bucket"); + goto err; + } + + ret = 0; + LOCK (&bucket->bucketlock); + { + if (!rb_probe (bucket->bucket, (void *)entry)) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to insert" + " entry"); + ret = -1; + } + } + 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_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to init entry"); + goto err; + } + + ret = rbthash_insert_entry (tbl, entry); + + if (ret == -1) { + gf_log (GF_RBTHASH, GF_LOG_ERROR, "Failed to insert entry"); + rbthash_deinit_entry (tbl, entry); + } + +err: + return ret; +} + +inline 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_log (GF_RBTHASH, GF_LOG_TRACE, "HASH: %u", keyhash); + nbucket = (keyhash % tbl->numbuckets); + gf_log (GF_RBTHASH, GF_LOG_TRACE, "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_log (GF_RBTHASH, GF_LOG_ERROR, "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_log (GF_RBTHASH, GF_LOG_ERROR, "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; + + FREE (entry->key); + dataref = entry->data; + mem_put (tbl->entrypool, 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); + mem_pool_destroy (tbl->entrypool); + + FREE (tbl->buckets); + FREE (tbl); +} + diff --git a/libglusterfs/src/rbthash.h b/libglusterfs/src/rbthash.h new file mode 100644 index 00000000000..5bfa6afd0ef --- /dev/null +++ b/libglusterfs/src/rbthash.h @@ -0,0 +1,75 @@ +/* + Copyright (c) 2008-2009 Z RESEARCH, Inc. + This file is part of GlusterFS. + + GlusterFS is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3 of the License, + or (at your option) any later version. + + GlusterFS is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see + . +*/ + +#ifndef __RBTHASH_TABLE_H_ +#define __RBTHASH_TABLE_H_ +#include "rb.h" +#include "locking.h" +#include "mem-pool.h" +#include "logging.h" + +#include + +#define GF_RBTHASH_MEMPOOL 1048576 +#define GF_RBTHASH "rbthash" + +struct rbthash_bucket { + struct rb_table *bucket; + gf_lock_t bucketlock; +}; + +typedef struct rbthash_entry { + void *data; + void *key; + int keylen; + uint32_t keyhash; +} rbthash_entry_t; + +typedef uint32_t (*rbt_hasher_t) (void *data, int len); +typedef void (*rbt_data_destroyer_t) (void *data); + +typedef struct rbthash_table { + int size; + int numbuckets; + struct mem_pool *entrypool; + gf_lock_t tablelock; + struct rbthash_bucket *buckets; + rbt_hasher_t hashfunc; + rbt_data_destroyer_t dfunc; +} rbthash_table_t; + +extern rbthash_table_t * +rbthash_table_init (int buckets, rbt_hasher_t hfunc, + rbt_data_destroyer_t dfunc); + +extern int +rbthash_insert (rbthash_table_t *tbl, void *data, void *key, int keylen); + +extern void * +rbthash_get (rbthash_table_t *tbl, void *key, int keylen); + +extern void * +rbthash_remove (rbthash_table_t *tbl, void *key, int keylen); + +extern void * +rbthash_replace (rbthash_table_t *tbl, void *key, int keylen, void *newdata); + +extern void +rbthash_table_destroy (rbthash_table_t *tbl); +#endif -- cgit