This patch adds an initial implementation of a hash table to libqb. The hash table implementation is somewhat unique in that I plan to add graph functionality to allow hash entries to be linked between other hash entries to provide a mechanism to structure data within a hash table.
To have a look at the current libqb source tree, reference www.libqb.org maintained by Angus. The long term goal of this work is to enable a replicated structured memory-based key-value storage that maintains consistency after a merge from a network partition. This allows IPC speed reads, and network speed writes of key/value pairs with full availability of key/value data on all nodes in the network. Regards -steve
>From 079312e84f2c1629c9802ce3a5c379f2241a05ec Mon Sep 17 00:00:00 2001 From: root <[email protected]> Date: Wed, 14 Apr 2010 11:54:13 -0700 Subject: [PATCH] Adds a hashing implementation to libqb. The hash table also contains a model for representing graphs within a hash table although that code is not implemented. e concept of the hashing is to allow the generation of --- include/qb/qbhash.h | 99 +++++++++++++++ lib/hash/Makefile.am | 95 ++++++++++++++ lib/hash/hash.c | 286 +++++++++++++++++++++++++++++++++++++++++++ lib/hash/libqbhash.versions | 15 +++ 4 files changed, 495 insertions(+), 0 deletions(-) create mode 100644 include/qb/qbhash.h create mode 100644 lib/hash/Makefile.am create mode 100644 lib/hash/hash.c create mode 100644 lib/hash/libqbhash.versions diff --git a/include/qb/qbhash.h b/include/qb/qbhash.h new file mode 100644 index 0000000..e3fca15 --- /dev/null +++ b/include/qb/qbhash.h @@ -0,0 +1,99 @@ +/* + * Copyright (c) 2010 Red Hat, Inc. + * + * Author: Steven Dake ([email protected]) + * + * This software licensed under BSD license, the text of which follows: + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * - Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * - Neither the name of Red Hat nor the names of its contributors may be used + * to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef QB_HASH_H_DEFINED +#define QB_HASH_H_DEFINED + +#include <stdlib.h> +#include <qb/qbhdb.h> + +extern int32_t qb_hash_initialize ( + qb_hdb_handle_t *handle, + uint32_t order, + uint32_t context_size); + +extern int32_t qb_hash_key_set ( + qb_hdb_handle_t handle, + const char *key, + const void *value, + uint32_t value_len); + +extern int32_t qb_hash_key_get ( + qb_hdb_handle_t handle, + const char *key, + void **value, + uint64_t *value_len); + +extern int32_t qb_hash_key_context_get ( + qb_hdb_handle_t handle, + const char *key, + void **context); + +extern int32_t qb_hash_key_delete ( + qb_hdb_handle_t handle, + const char *key); + +extern int32_t qb_hash_edge_create ( + qb_hdb_handle_t handle, + const char *source_key, + const char *dest_key, + const char *edge_name); + +extern int32_t qb_hash_edge_destroy ( + qb_hdb_handle_t handle, + const char *source_key, + const char *dest_key, + const char *edge_name); + +extern int32_t qb_hash_edge_follow ( + qb_hdb_handle_t handle, + const char *source_key, + const char *edge_name, + char **dest_key); + +extern int32_t qb_hash_edge_value_set ( + qb_hdb_handle_t handle, + const char *source_key, + const char *dest_key, + const char *edge_name, + const void *edge_value, + uint64_t edge_value_len); + +extern int32_t qb_hash_edge_value_get ( + qb_hdb_handle_t handle, + const char *source_key, + const char *dest_key, + const char *edge_name, + const void **edge_value, + uint64_t *edge_value_len); + +#endif /* QB_HASH_H_DEFINED */ diff --git a/lib/hash/Makefile.am b/lib/hash/Makefile.am new file mode 100644 index 0000000..d1309e2 --- /dev/null +++ b/lib/hash/Makefile.am @@ -0,0 +1,95 @@ +# +# Copyright (c) 2010 Red Hat, Inc. +# +# Authors: Andrew Beekhof +# Steven Dake ([email protected]) +# Angus Salkeld <[email protected]> +# +# This software licensed under BSD license, the text of which follows: +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions are met: +# +# - Redistributions of source code must retain the above copyright notice, +# this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# - Neither the name of the MontaVista Software, Inc. nor the names of its +# contributors may be used to endorse or promote products derived from this +# software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF +# THE POSSIBILITY OF SUCH DAMAGE. + +MAINTAINERCLEANFILES = Makefile.in + +AM_CFLAGS = -fPIC + +AM_LDFLAGS = -lpthread + +INCLUDES = -I$(top_builddir)/include -I$(top_srcdir)/include + +lib_LIBRARIES = libqbhash.a +SHARED_LIBS = $(lib_LIBRARIES:%.a=%.so.$(SONAME)) +SHARED_LIBS_SO = $(lib_LIBRARIES:%.a=%.so) +SHARED_LIBS_SO_TWO = $(lib_LIBRARIES:%.a=%.so.$(SOMAJOR)) + +libqbhash_a_SOURCES = hash.c + +noinst_HEADERS = libqbhash.versions + +if BUILD_DARWIN + +lib%.so.$(SONAME): %.o + $(CC) $(DARWIN_OPTS) $^ -o $@ + ln -sf lib$*.so.$(SONAME) lib$*.so + ln -sf lib$*.so.$(SONAME) lib$*.so.$(SOMAJOR) + +else + +if BUILD_SOLARIS + +lib%.so.$(SONAME): %.o + $(LD) $(SOLARIS_OPTS) -G $^ -o $@ + ln -sf lib$*.so.$(SONAME) lib$*.so + ln -sf lib$*.so.$(SONAME) lib$*.so.$(SOMAJOR) + +else + +libqb%.so.$(SONAME): %.o + $(CC) -shared -o $@ \ + -Wl,-soname=libqb$*.so.$(SOMAJOR) \ + -Wl,-version-script=$(srcdir)/libqb$*.versions \ + $^ $(LDFLAGS) $(AM_LDFLAGS) + ln -sf libqb$*.so.$(SONAME) libqb$*.so + ln -sf libqb$*.so.$(SONAME) libqb$*.so.$(SOMAJOR) + +endif + +endif + +all-local: $(SHARED_LIBS) + @echo Built shared libs + +install-exec-local: + $(INSTALL) -d $(DESTDIR)/$(libdir) + $(INSTALL) -m 755 $(SHARED_LIBS) $(DESTDIR)/$(libdir) + $(CP) -a $(SHARED_LIBS_SO) $(SHARED_LIBS_SO_TWO) $(DESTDIR)/$(libdir) + +uninstall-local: + cd $(DESTDIR)/$(libdir)/ && \ + rm -f $(SHARED_LIBS) $(SHARED_LIBS_SO) $(SHARED_LIBS_SO_TWO) + +clean-local: + rm -f *.o *.a *.so* *.da *.bb *.bbg + diff --git a/lib/hash/hash.c b/lib/hash/hash.c new file mode 100644 index 0000000..83938e3 --- /dev/null +++ b/lib/hash/hash.c @@ -0,0 +1,286 @@ +/* + * Copyright (c) 2010 Red Hat, Inc. + * + * Author: Steven Dake ([email protected]) + * + * This software licensed under BSD license, the text of which follows: + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * - Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * - Neither the name of Red Hat nor the names of its contributors may be used + * to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ +#include <stdint.h> +#include <qb/qbhdb.h> + +#include <config.h> + +#include "os_base.h" + +#include <qb/qbhdb.h> +#include <qb/qblist.h> +#include <qb/qbhash.h> + +#define FNV_32_PRIME ((uint32_t)0x01000193) + +DECLARE_HDB_DATABASE(qb_hash_handle_db,NULL); + +struct hash_node { + struct qb_list_head list; + void *value; + uint32_t value_len; + char key[0]; +}; + +struct hash_bucket { + pthread_mutex_t mutex; + struct qb_list_head list_head; +}; + +struct hash_table { + uint64_t memory_data; + uint64_t memory_overhead; + uint32_t order; + uint32_t hash_buckets_len; + struct hash_bucket hash_buckets[0]; +}; + +static uint32_t hash_fnv ( + const void *value, + uint32_t valuelen, + uint32_t order) +{ + uint8_t *cd = (uint8_t *)value; + uint8_t *ed = (uint8_t *)value + valuelen; + uint32_t hash_result = 0x811c9dc5; + int res; + + while (cd < ed) { + hash_result ^= *cd; + hash_result *= FNV_32_PRIME; + cd++; + } + res = ((hash_result >> order) ^ hash_result) & ((1 << order) - 1); + return (res); +} + +int32_t qb_hash_initialize ( + qb_hdb_handle_t *handle, + uint32_t order, + uint32_t context_size) +{ + struct hash_table *hash_table; + int i; + uint64_t size; + int32_t res; + + size = sizeof (struct hash_table) + + (sizeof (struct hash_bucket) * (1 << order)); + + res = qb_hdb_handle_create (&qb_hash_handle_db, size, handle); + if (res != 0) { + return (res); + } + res = qb_hdb_handle_get (&qb_hash_handle_db, *handle, (void *)&hash_table); + if (res != 0) { + goto hash_destroy; + } + + hash_table->memory_data = 0; + hash_table->memory_overhead = size; + + hash_table->order = order; + hash_table->hash_buckets_len = 1 << order; + for (i = 0; i < hash_table->hash_buckets_len; i++) { + qb_list_init (&hash_table->hash_buckets[i].list_head); + pthread_mutex_init (&hash_table->hash_buckets[i].mutex, NULL); + } + + qb_hdb_handle_put (&qb_hash_handle_db, *handle); + return (0); + +hash_destroy: + res = qb_hdb_handle_destroy (&qb_hash_handle_db, *handle); + return (-1); +} + +int32_t qb_hash_key_set ( + qb_hdb_handle_t handle, + const char *key, + const void *value, + uint32_t value_len) +{ + struct hash_table *hash_table; + uint32_t hash_entry; + struct qb_list_head *list; + int found = 0; + struct hash_node *hash_node; + int res; + + res = qb_hdb_handle_get (&qb_hash_handle_db, handle, (void *)&hash_table); + if (res != 0) { + return (res); + } + hash_entry = hash_fnv (key, strlen (key), hash_table->order); + pthread_mutex_lock (&hash_table->hash_buckets[hash_entry].mutex); + for (list = hash_table->hash_buckets[hash_entry].list_head.next; + list != &hash_table->hash_buckets[hash_entry].list_head; + list = list->next) { + + hash_node = qb_list_entry (list, struct hash_node, list); + + if (strcmp (hash_node->key, key) == 0) { + hash_table->memory_data -= value_len; + free (hash_node->value); + found = 1; + break; + } + } + if (found == 0) { + hash_node = malloc (sizeof (struct hash_node) + strlen (key) + 1); + if (hash_node == 0) { + goto error_exit; + } + + hash_table->memory_overhead += sizeof (struct hash_node); + hash_table->memory_data += strlen (key) + 1; + + memcpy (&hash_node->key, key, strlen (key) + 1); + qb_list_add_tail (&hash_node->list, + &hash_table->hash_buckets[hash_entry].list_head); + } + if (value_len) { + hash_node->value = malloc (value_len); + hash_table->memory_data += value_len; + } else { + hash_node->value = NULL; + } + hash_node->value_len = value_len; + if (value) { + memcpy (hash_node->value, value, value_len); + } + +error_exit: + pthread_mutex_unlock (&hash_table->hash_buckets[hash_entry].mutex); + qb_hdb_handle_put (&qb_hash_handle_db, handle); + + return (0); +} + + +int32_t qb_hash_key_get ( + qb_hdb_handle_t handle, + const char *key, + void **value, + uint64_t *value_len) +{ + struct hash_table *hash_table; + uint32_t hash_entry; + uint32_t res = -1; + struct qb_list_head *list; + struct hash_node *hash_node; + + res = qb_hdb_handle_get (&qb_hash_handle_db, handle, (void *)&hash_table); + if (res != 0) { + return (res); + } + res = -1; + + hash_entry = hash_fnv (key, strlen (key), hash_table->order); + + pthread_mutex_lock (&hash_table->hash_buckets[hash_entry].mutex); + for (list = hash_table->hash_buckets[hash_entry].list_head.next; + list != &hash_table->hash_buckets[hash_entry].list_head; + list = list->next) { + + hash_node = qb_list_entry (list, struct hash_node, list); + if (strcmp (hash_node->key, key) == 0) { + *value = hash_node->value; + *value_len = hash_node->value_len; + res = 0; + goto unlock_exit; + } + } + +unlock_exit: + pthread_mutex_unlock (&hash_table->hash_buckets[hash_entry].mutex); + qb_hdb_handle_put (&qb_hash_handle_db, handle); + if (res == -1) { + errno = ENOENT; + } + return (res); +} + +int32_t qb_hash_key_delete ( + qb_hdb_handle_t handle, + const char *key) +{ + struct hash_table *hash_table; + struct qb_list_head *list; + uint32_t hash_entry; + uint32_t res = ENOENT; + struct hash_node *hash_node; + + res = qb_hdb_handle_get (&qb_hash_handle_db, handle, (void *)&hash_table); + if (res != 0) { + return (res); + } + res = -1; + + hash_entry = hash_fnv (key, strlen (key), hash_table->order); + pthread_mutex_lock (&hash_table->hash_buckets[hash_entry].mutex); + for (list = hash_table->hash_buckets[hash_entry].list_head.next; + list != &hash_table->hash_buckets[hash_entry].list_head; + list = list->next) { + + hash_node = qb_list_entry (list, struct hash_node, list); + if (strcmp (hash_node->key, key) == 0) { + free (hash_node->value); + qb_list_del (&hash_node->list); + free (hash_node); + res = 0; + goto unlock_exit; + } + } + +unlock_exit: + pthread_mutex_unlock (&hash_table->hash_buckets[hash_entry].mutex); + qb_hdb_handle_put (&qb_hash_handle_db, handle); + if (res == -1) { + errno = ENOENT; + } + return (res); +} + +extern int32_t qb_hash_key_context_get ( + qb_hdb_handle_t handle, + const char *key, + void **context) +{ + struct hash_table *hash_table; + int res = 0; + + qb_hdb_handle_get (&qb_hash_handle_db, handle, (void *)&hash_table); + qb_hdb_handle_put (&qb_hash_handle_db, handle); + return (res); +} + diff --git a/lib/hash/libqbhash.versions b/lib/hash/libqbhash.versions new file mode 100644 index 0000000..0fbbcae --- /dev/null +++ b/lib/hash/libqbhash.versions @@ -0,0 +1,15 @@ +QB_HASH_0.1 { + global: + qb_hash_initialize; + qb_hash_key_set; + qb_hash_key_get; + qb_hash_key_delete; + qb_hash_key_context_get; + qb_hash_edge_create; + qb_hash_edge_destroy; + qb_hash_edge_follow; + qb_hash_edge_value_set; + qb_hash_edge_value_get; + + local: *; +}; -- 1.6.2.5
_______________________________________________ Openais mailing list [email protected] https://lists.linux-foundation.org/mailman/listinfo/openais
