Add a graph hash table to libqb
by Steven Dake
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
14 years
[PATCH] add a unit test for hash & cleanup.
by Angus Salkeld
Hi
This adds a unit test for hash.
Add qbhash.h to the Makefiles
Fix make rpm.
Make sure the makefiles are generated for hash
Note to run the tests run "make check" you will
need to "yum install check-devel" to run the checks.
(but it is optional)
Steve this test fails on my machine, can you have a look at it?
-A
Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
Makefile.am | 2 +-
configure.ac | 9 ++-
include/qb/Makefile.am | 2 +-
lib/Makefile.am | 2 +-
man/Makefile.am | 5 +-
quarterback.spec.in | 6 ++
tests/.gitignore | 1 +
tests/Makefile.am | 41 +++++++++++++
tests/check_hash.c | 152 ++++++++++++++++++++++++++++++++++++++++++++++++
9 files changed, 212 insertions(+), 8 deletions(-)
create mode 100644 tests/.gitignore
create mode 100644 tests/Makefile.am
create mode 100644 tests/check_hash.c
diff --git a/Makefile.am b/Makefile.am
index 5a51521..2e825e1 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -44,7 +44,7 @@ MAINTAINERCLEANFILES = Makefile.in aclocal.m4 configure depcomp \
dist_doc_DATA = LICENSE INSTALL README TODO
-SUBDIRS = include lib man
+SUBDIRS = include lib man tests
#pkgconfig
install-exec-local:
diff --git a/configure.ac b/configure.ac
index 5bc51cd..83066e0 100644
--- a/configure.ac
+++ b/configure.ac
@@ -57,7 +57,6 @@ AC_PROG_INSTALL
AC_PROG_LN_S
AC_PROG_MAKE_SET
AC_PROG_RANLIB
-#AC_CHECK_PROGS([GROFF], [groff])
AC_CHECK_PROGS([PKGCONFIG], [pkg-config])
# Checks for libraries.
@@ -65,6 +64,9 @@ AC_CHECK_LIB([dl], [dlopen])
AC_CHECK_LIB([pthread], [pthread_create])
AC_CHECK_LIB([socket], [socket])
+PKG_CHECK_MODULES([CHECK], [check >= 0.9.4],[with_check=yes],[with_check=no])
+AM_CONDITIONAL(HAVE_CHECK, test "${with_check}" = "yes")
+
# Checks for header files.
AC_HEADER_DIRENT
AC_HEADER_STDC
@@ -121,7 +123,9 @@ AC_CONFIG_FILES([Makefile
lib/ipc/Makefile
lib/wthread/Makefile
lib/logsys/Makefile
- man/Makefile])
+ lib/hash/Makefile
+ man/Makefile
+ tests/Makefile])
### Local business
@@ -360,7 +364,6 @@ AM_CONDITIONAL(BUILD_DARWIN, test -n "${DARWIN_OPTS}")
AM_CONDITIONAL(BUILD_SOLARIS, test -n "${SOLARIS_OPTS}")
AC_SUBST([DARWIN_OPTS])
AC_SUBST([SOLARIS_OPTS])
-
AC_SUBST([LINT_FLAGS])
AC_DEFINE_UNQUOTED([PLUGINSODIR], "$(eval echo ${PLUGINSODIR})", [PLUGINSO directory])
diff --git a/include/qb/Makefile.am b/include/qb/Makefile.am
index 7cf0ef6..0f84113 100644
--- a/include/qb/Makefile.am
+++ b/include/qb/Makefile.am
@@ -33,5 +33,5 @@ instdir = $(includedir)/qb/
inst_HEADERS = qbtsafe.h qbhdb.h qblist.h qbpoll.h \
qbtimer.h qbplugin.h qbplugin_comp.h \
qbipcc.h qbipcs.h qbwthread.h qbqueue.h \
- qblogsys.h
+ qblogsys.h qbhash.h
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 18384cb..39c8f05 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -30,5 +30,5 @@
MAINTAINERCLEANFILES = Makefile.in
-SUBDIRS = tsafe poll timer plugin ipc wthread logsys
+SUBDIRS = tsafe poll timer plugin ipc wthread logsys hash
diff --git a/man/Makefile.am b/man/Makefile.am
index 2dacf22..898b666 100644
--- a/man/Makefile.am
+++ b/man/Makefile.am
@@ -37,7 +37,8 @@ EXTRA_DIST = Doxyfile
dist_man_MANS = man3/qbtsafe.h.3 man3/qbhdb.h.3 man3/qblist.h.3 \
man3/qbpoll.h.3 man3/qbtimer.h.3 man3/qbplugin.h.3 \
man3/qbplugin_comp.h.3 man3/qbipcc.h.3 man3/qbipcs.h.3 \
- man3/qbqueue.h.3 man3/qbwthread.h man3/qblogsys.h.3
+ man3/qbqueue.h.3 man3/qbwthread.h.3 man3/qblogsys.h.3 \
+ man3/qbhash.h.3
inc_dir = $(top_srcdir)/include/qb
@@ -45,7 +46,7 @@ dependant_headers = $(inc_dir)/qbtsafe.h $(inc_dir)/qbhdb.h $(inc_dir)/qblist.h
$(inc_dir)/qbpoll.h $(inc_dir)/qbtimer.h $(inc_dir)/qbplugin.h \
$(inc_dir)/qbplugin_comp.h $(inc_dir)/qbipcc.h \
$(inc_dir)/qbipcs.h $(inc_dir)/qbqueue.h $(inc_dir)/qbwthread.h \
- $(inc_dir)/qblogsys.h
+ $(inc_dir)/qblogsys.h $(inc_dir)/qbhash.h
$(dist_man_MANS): Doxyfile $(dependant_headers)
doxygen Doxyfile
diff --git a/quarterback.spec.in b/quarterback.spec.in
index a4445f6..046d815 100644
--- a/quarterback.spec.in
+++ b/quarterback.spec.in
@@ -49,6 +49,8 @@ This package contains quarterback libraries.
%{_libdir}/libqbipcc.so.*
%{_libdir}/libqbipcs.so.*
%{_libdir}/libqbwthread.so.*
+%{_libdir}/libqblogsys.so.*
+%{_libdir}/libqbhash.so.*
%post -n quarterback -p /sbin/ldconfig
@@ -75,6 +77,8 @@ The Quarterback APIs.
%{_libdir}/libqbipcc.so
%{_libdir}/libqbipcs.so
%{_libdir}/libqbwthread.so
+%{_libdir}/libqbhash.so
+%{_libdir}/libqblogsys.so
%{_includedir}/qb/qbtsafe.h
%{_includedir}/qb/qbpoll.h
%{_includedir}/qb/qbhdb.h
@@ -86,6 +90,8 @@ The Quarterback APIs.
%{_includedir}/qb/qbipcs.h
%{_includedir}/qb/qbqueue.h
%{_includedir}/qb/qbwthread.h
+%{_includedir}/qb/qblogsys.h
+%{_includedir}/qb/qbhash.h
%{_mandir}/man3/qb*3*
%changelog
diff --git a/tests/.gitignore b/tests/.gitignore
new file mode 100644
index 0000000..b27b9da
--- /dev/null
+++ b/tests/.gitignore
@@ -0,0 +1 @@
+check_hash
diff --git a/tests/Makefile.am b/tests/Makefile.am
new file mode 100644
index 0000000..28223fb
--- /dev/null
+++ b/tests/Makefile.am
@@ -0,0 +1,41 @@
+# Copyright (c) 2010 Red Hat, Inc.
+#
+# Authors: Angus Salkeld <asalkeld(a)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.
+
+if HAVE_CHECK
+TESTS = check_hash
+
+check_PROGRAMS = check_hash
+
+check_hash_SOURCES = check_hash.c $(top_builddir)/include/qb/qbhash.h
+check_hash_CFLAGS = @CHECK_CFLAGS@ -I$(top_srcdir)/include
+check_hash_LDADD = $(top_builddir)/lib/hash/libqbhash.a @CHECK_LIBS@
+
+endif
+
diff --git a/tests/check_hash.c b/tests/check_hash.c
new file mode 100644
index 0000000..19bc28d
--- /dev/null
+++ b/tests/check_hash.c
@@ -0,0 +1,152 @@
+/*
+ * Copyright (c) 2010 Red Hat, Inc.
+ *
+ * All rights reserved.
+ *
+ * Author: Angus Salkeld <asalkeld(a)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.
+ */
+
+#include <stdio.h>
+#include <check.h>
+#include <qb/qbhash.h>
+
+qb_hdb_handle_t handle;
+unsigned int distribution[65536];
+
+
+START_TEST (test_hash_init)
+{
+ int res;
+ handle = 0;
+
+ res = qb_hash_initialize (&handle, 3, 17);
+
+ ck_assert_int_ne (handle, 0);
+ ck_assert_int_eq (res, 0);
+
+ memset (distribution, 0, sizeof (distribution));
+}
+END_TEST
+
+START_TEST (test_hash_load)
+{
+ char word[1000];
+ FILE *fp;
+ int hashes_done = 0;
+
+ /*
+ * Load hash table with dictionary
+ */
+ fp = fopen ("/usr/share/dict/words", "r");
+ while (fgets (word, sizeof (word), fp)) {
+ word[strlen (word) - 1] = '\0';
+ qb_hash_key_set (handle, word, word, strlen (word) + 1);
+ hashes_done += 1;
+ }
+ fclose (fp);
+
+ fail_unless (1 == 1);
+}
+END_TEST
+
+START_TEST (test_hash_verify)
+{
+ char word[1000];
+ FILE *fp;
+ void *value;
+ uint64_t value_len;
+
+ /*
+ * Verify dictionary produces correct values
+ */
+ fp = fopen ("/usr/share/dict/words", "r");
+ while (fgets (word, sizeof (word), fp)) {
+ word[strlen (word) - 1] = '\0';
+ qb_hash_key_get (handle, word, &value, &value_len);
+ ck_assert_str_eq (word, value);
+ }
+ fclose (fp);
+}
+END_TEST
+
+START_TEST (test_hash_delete)
+{
+ char word[1000];
+ FILE *fp;
+ int res;
+
+ /*
+ * Delete all dictionary entries
+ */
+ fp = fopen ("/usr/share/dict/words", "r");
+ while (fgets (word, sizeof (word), fp)) {
+ word[strlen (word) - 1] = '\0';
+ res = qb_hash_key_delete (handle, word);
+ ck_assert_int_eq (res, 0);
+ }
+ fclose (fp);
+
+}
+END_TEST
+
+static Suite *hash_suite (void)
+{
+ TCase *tc_load;
+ TCase *tc_verify;
+ TCase *tc_delete;
+ Suite *s = suite_create ("hashtable");
+
+ tc_load = tcase_create ("load");
+ tcase_add_test (tc_load, test_hash_init);
+ tcase_add_test (tc_load, test_hash_load);
+ suite_add_tcase (s, tc_load);
+
+ tc_verify = tcase_create ("verify");
+ tcase_add_test (tc_verify, test_hash_verify);
+ suite_add_tcase (s, tc_verify);
+
+ tc_delete = tcase_create ("delete");
+ tcase_add_test (tc_delete, test_hash_delete);
+ suite_add_tcase (s, tc_delete);
+
+ return s;
+}
+
+int main (void)
+{
+ int number_failed;
+
+ Suite *s = hash_suite ();
+ SRunner *sr = srunner_create (s);
+ srunner_run_all (sr, CK_NORMAL);
+ number_failed = srunner_ntests_failed (sr);
+ srunner_free (sr);
+ return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
+
--
1.6.6.1
14 years