[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
root
root at localhost.localdomain
Wed Apr 14 11:54:13 PDT 2010
---
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 (sdake at redhat.com)
+ *
+ * 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 (sdake at redhat.com)
+# Angus Salkeld <asaslkeld at redhat.com>
+#
+# 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 (sdake at redhat.com)
+ *
+ * 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
--=-62Zup7l+jO8HDdCBIzA2--
More information about the Openais
mailing list