This is an automated email from the git hooks/post-receive script.
firstyear pushed a commit to branch master
in repository 389-ds-base.
commit f1e5692b270d39c63de79d47e41a59ac55fec170
Author: William Brown <firstyear(a)redhat.com>
Date: Wed Apr 5 19:32:40 2017 +1000
Ticket 49214 - Implement htree concept
Bug Description: Implement the htree concept that was designed
by wibrown.
Fix Description: Implementation of siphash1-3 and htree. The htree
already shows improvements over the b+tree in many conditions,
and a COW implementation will come soon.
https://pagure.io/389-ds-base/issue/49214
Author: wibrown
Review by: mreynolds (Thanks!)
---
LICENSE | 3 +-
LICENSE.mit | 32 +++
Makefile.am | 11 +-
src/libsds/external/csiphash/csiphash.c | 129 ++++++++++++
src/libsds/include/sds.h | 77 +++++++
src/libsds/sds/core/utils.c | 5 +
src/libsds/sds/ht/ht.c | 71 +++++++
src/libsds/sds/ht/ht.h | 38 ++++
src/libsds/sds/ht/map.c | 60 ++++++
src/libsds/sds/ht/node.c | 65 ++++++
src/libsds/sds/ht/op.c | 359 ++++++++++++++++++++++++++++++++
src/libsds/sds/ht/verify.c | 138 ++++++++++++
src/libsds/test/benchmark.c | 67 +++++-
src/libsds/test/benchmark_par.c | 22 ++
src/libsds/test/benchmark_par.h | 10 +-
src/libsds/test/benchmark_parwrap.c | 52 +++++
src/libsds/test/test_fixtures.c | 23 ++
src/libsds/test/test_sds.c | 4 +
src/libsds/test/test_sds.h | 5 +
src/libsds/test/test_sds_csiphash.c | 47 +++++
src/libsds/test/test_sds_ht.c | 137 ++++++++++++
21 files changed, 1344 insertions(+), 11 deletions(-)
diff --git a/LICENSE b/LICENSE
index e75ac72..395a348 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,5 +1,6 @@
Copyright (C) 2015 Red Hat
-See files 'LICENSE.GPLv3+' and 'LICENSE.openssl' for more information.
+See files 'LICENSE.GPLv3+', 'LICENSE.openssl', and 'LICENSE.mit'
for
+more information.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
diff --git a/LICENSE.mit b/LICENSE.mit
new file mode 100644
index 0000000..9c78d66
--- /dev/null
+++ b/LICENSE.mit
@@ -0,0 +1,32 @@
+/* <MIT License>
+ Copyright (c) 2013 Marek Majkowski <marek(a)popcount.org>
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ </MIT License>
+
+ Original location:
+
https://github.com/majek/csiphash/
+
+ Solution inspired by code from:
+ Samuel Neves (supercop/crypto_auth/siphash24/little)
+ djb (supercop/crypto_auth/siphash24/little2)
+ Jean-Philippe Aumasson (
https://131002.net/siphash/siphash24.c)
+*/
+
+
diff --git a/Makefile.am b/Makefile.am
index 057da52..06217ff 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -531,6 +531,7 @@ dist_noinst_HEADERS = \
src/libsds/sds/bpt/bpt.h \
src/libsds/sds/bpt_cow/bpt_cow.h \
src/libsds/sds/queue/queue.h \
+ src/libsds/sds/ht/ht.h \
src/nunc-stans/ns/ns_event_fw.h \
src/nunc-stans/ns/ns_private.h
@@ -1031,7 +1032,13 @@ libsds_la_SOURCES = src/libsds/sds/core/utils.c \
src/libsds/sds/bpt_cow/verify.c \
src/libsds/sds/queue/queue.c \
src/libsds/sds/queue/tqueue.c \
- src/libsds/sds/queue/lqueue.c
+ src/libsds/sds/queue/lqueue.c \
+ src/libsds/external/csiphash/csiphash.c \
+ src/libsds/sds/ht/ht.c \
+ src/libsds/sds/ht/node.c \
+ src/libsds/sds/ht/map.c \
+ src/libsds/sds/ht/op.c \
+ src/libsds/sds/ht/verify.c
if ATOMIC_QUEUE_OPERATIONS
libsds_la_SOURCES += \
src/libsds/external/liblfds711/src/lfds711_queue_unbounded_manyproducer_manyconsumer/lfds711_queue_unbounded_manyproducer_manyconsumer_cleanup.c
\
@@ -2015,6 +2022,8 @@ test_libsds_SOURCES = src/libsds/test/test_sds.c \
src/libsds/test/test_sds_queue.c \
src/libsds/test/test_sds_tqueue.c \
src/libsds/test/test_sds_lqueue.c \
+ src/libsds/test/test_sds_csiphash.c \
+ src/libsds/test/test_sds_ht.c \
src/libsds/test/test_fixtures.c
test_libsds_LDFLAGS = $(ASAN_DEFINES) $(PROFILING_LINKS) $(CMOCKA_LINKS)
diff --git a/src/libsds/external/csiphash/csiphash.c
b/src/libsds/external/csiphash/csiphash.c
new file mode 100644
index 0000000..60066f9
--- /dev/null
+++ b/src/libsds/external/csiphash/csiphash.c
@@ -0,0 +1,129 @@
+/* <MIT License>
+ Copyright (c) 2013 Marek Majkowski <marek(a)popcount.org>
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ </MIT License>
+
+ Original location:
+
https://github.com/majek/csiphash/
+
+ Solution inspired by code from:
+ Samuel Neves (supercop/crypto_auth/siphash24/little)
+ djb (supercop/crypto_auth/siphash24/little2)
+ Jean-Philippe Aumasson (
https://131002.net/siphash/siphash24.c)
+*/
+
+#include <inttypes.h>
+#include <stddef.h> /* for size_t */
+
+#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \
+ __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+# define _le64toh(x) ((uint64_t)(x))
+#elif defined(_WIN32)
+/* Windows is always little endian, unless you're on xbox360
+
http://msdn.microsoft.com/en-us/library/b0084kay(v=vs.80).aspx */
+# define _le64toh(x) ((uint64_t)(x))
+#elif defined(__APPLE__)
+# include <libkern/OSByteOrder.h>
+# define _le64toh(x) OSSwapLittleToHostInt64(x)
+#else
+
+/* See:
http://sourceforge.net/p/predef/wiki/Endianness/ */
+# if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__)
+# include <sys/endian.h>
+# else
+# include <endian.h>
+# endif
+# if defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
+ __BYTE_ORDER == __LITTLE_ENDIAN
+# define _le64toh(x) ((uint64_t)(x))
+# else
+# define _le64toh(x) le64toh(x)
+# endif
+
+#endif
+
+
+#define ROTATE(x, b) (uint64_t)( ((x) << (b)) | ( (x) >> (64 - (b))) )
+
+#define HALF_ROUND(a,b,c,d,s,t) \
+ a += b; c += d; \
+ b = ROTATE(b, s) ^ a; \
+ d = ROTATE(d, t) ^ c; \
+ a = ROTATE(a, 32);
+
+#define ROUND(v0,v1,v2,v3) \
+ HALF_ROUND(v0,v1,v2,v3,13,16); \
+ HALF_ROUND(v2,v1,v0,v3,17,21) \
+
+#define cROUND(v0,v1,v2,v3) \
+ ROUND(v0,v1,v2,v3)
+
+#define dROUND(v0,v1,v2,v3) \
+ ROUND(v0,v1,v2,v3); \
+ ROUND(v0,v1,v2,v3); \
+ ROUND(v0,v1,v2,v3)
+
+
+uint64_t sds_siphash13(const void *src, size_t src_sz, const char key[16]) {
+ const uint64_t *_key = (uint64_t *)key;
+ uint64_t k0 = _le64toh(_key[0]);
+ uint64_t k1 = _le64toh(_key[1]);
+ uint64_t b = (uint64_t)src_sz << 56;
+ const uint64_t *in = (uint64_t*)src;
+
+ uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
+ uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
+ uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
+ uint64_t v3 = k1 ^ 0x7465646279746573ULL;
+
+ while (src_sz >= 8) {
+ uint64_t mi = _le64toh(*in);
+ in += 1; src_sz -= 8;
+ v3 ^= mi;
+ // cround
+ cROUND(v0,v1,v2,v3);
+ v0 ^= mi;
+ }
+
+ uint64_t t = 0;
+ uint8_t *pt = (uint8_t *)&t;
+ uint8_t *m = (uint8_t *)in;
+
+ switch (src_sz) {
+ case 7: pt[6] = m[6];
+ case 6: pt[5] = m[5];
+ case 5: pt[4] = m[4];
+ case 4: *((uint32_t*)&pt[0]) = *((uint32_t*)&m[0]); break;
+ case 3: pt[2] = m[2];
+ case 2: pt[1] = m[1];
+ case 1: pt[0] = m[0];
+ }
+ b |= _le64toh(t);
+
+ v3 ^= b;
+ // cround
+ cROUND(v0,v1,v2,v3);
+ v0 ^= b;
+ v2 ^= 0xff;
+ // dround
+ dROUND(v0,v1,v2,v3);
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
diff --git a/src/libsds/include/sds.h b/src/libsds/include/sds.h
index d8d3089..c3bae8d 100644
--- a/src/libsds/include/sds.h
+++ b/src/libsds/include/sds.h
@@ -233,6 +233,19 @@ void sds_free(void *ptr);
uint32_t sds_crc32c(uint32_t crc, const unsigned char *data, size_t length);
/**
+ * sds_siphash13 provides an implementation of the siphash algorithm for use in
+ * hash based datastructures. It is chosen due to is resilance against hash
+ * attacks, such that it makes it higly secure as a choice for a hashmap.
+ *
+ * \param src The data to hash
+ * \param src_sz The size of the data to hash
+ * \param key The security key to mix with the hash. This should be randomised once
+ * at startup and stored for use with further operations.
+ * \retval The uint64_t representing the hash of the data.
+ */
+uint64_t sds_siphash13(const void *src, size_t src_sz, const char key[16]);
+
+/**
* sds_uint64_t_compare takes two void *, and treats them as uint64_t *.
*
* \param a The first uint64_t *.
@@ -1327,3 +1340,67 @@ sds_result sds_bptree_cow_insert_atomic(sds_bptree_cow_instance
*binst, void *ke
*/
/* end sds_bptree_cow */
+#define HT_SLOTS 16
+
+typedef enum _sds_ht_slot_state {
+ SDS_HT_EMPTY = 0,
+ SDS_HT_VALUE = 1,
+ SDS_HT_BRANCH = 2,
+} sds_ht_slot_state;
+
+typedef struct _sds_ht_value {
+ uint32_t checksum;
+ void *key;
+ void *value;
+ // may make this a LL of values later for collisions
+} sds_ht_value;
+
+typedef struct _sds_ht_slot {
+ sds_ht_slot_state state;
+ union {
+ sds_ht_value *value;
+ struct _sds_ht_node *node;
+ } slot;
+} sds_ht_slot;
+
+typedef struct _sds_ht_node {
+ uint32_t checksum;
+ uint64_t txn_id;
+ uint_fast32_t count;
+#ifdef DEBUG
+ uint64_t depth;
+#endif
+ struct _sds_ht_node *parent;
+ size_t parent_slot;
+ sds_ht_slot slots[HT_SLOTS];
+} sds_ht_node;
+
+typedef struct _sds_ht_instance {
+ uint32_t checksum;
+ char hkey[16];
+ sds_ht_node *root;
+ int64_t (*key_cmp_fn)(void *a, void *b);
+ uint64_t (*key_size_fn)(void *key);
+ void *(*key_dup_fn)(void *key);
+ void (*key_free_fn)(void *key);
+ void *(*value_dup_fn)(void *value);
+ void (*value_free_fn)(void *value);
+} sds_ht_instance;
+
+uint64_t sds_uint64_t_size(void *key);
+
+sds_result
+sds_ht_init(sds_ht_instance **ht_ptr,
+ int64_t (*key_cmp_fn)(void *a, void *b),
+ void (*value_free_fn)(void *value),
+ void *(*key_dup_fn)(void *key),
+ void (*key_free_fn)(void *key),
+ uint64_t (*key_size_fn)(void *key)
+ );
+
+sds_result sds_ht_insert(sds_ht_instance *ht_ptr, void *key, void *value);
+sds_result sds_ht_search(sds_ht_instance *ht_ptr, void *key, void **value);
+sds_result sds_ht_delete(sds_ht_instance *ht_ptr, void *key);
+sds_result sds_ht_verify(sds_ht_instance *ht_ptr);
+sds_result sds_ht_destroy(sds_ht_instance *ht_ptr);
+
diff --git a/src/libsds/sds/core/utils.c b/src/libsds/sds/core/utils.c
index 80368d8..ee6cfcb 100644
--- a/src/libsds/sds/core/utils.c
+++ b/src/libsds/sds/core/utils.c
@@ -44,6 +44,11 @@ sds_uint64_t_free(void *key) {
return;
}
+uint64_t
+sds_uint64_t_size(void *key __attribute__((unused))) {
+ return sizeof(uint64_t);
+}
+
/* We have to provide some wrappers to strcmp and such for casting */
int64_t
sds_strcmp(void *a, void *b) {
diff --git a/src/libsds/sds/ht/ht.c b/src/libsds/sds/ht/ht.c
new file mode 100644
index 0000000..edfd032
--- /dev/null
+++ b/src/libsds/sds/ht/ht.c
@@ -0,0 +1,71 @@
+/* BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#include "ht.h"
+
+sds_result
+sds_ht_init(sds_ht_instance **ht_ptr,
+ int64_t (*key_cmp_fn)(void *a, void *b),
+ void (*value_free_fn)(void *value),
+ void *(*key_dup_fn)(void *key),
+ void (*key_free_fn)(void *key),
+ uint64_t (*key_size_fn)(void *key)
+ )
+{
+ if (ht_ptr == NULL ) {
+#ifdef DEBUG
+ sds_log("sds_ht_init", "Invalid pointer");
+#endif
+ return SDS_NULL_POINTER;
+ }
+
+ *ht_ptr = sds_calloc(sizeof(sds_ht_instance));
+ (*ht_ptr)->key_cmp_fn = key_cmp_fn;
+ (*ht_ptr)->key_size_fn = key_size_fn;
+ (*ht_ptr)->key_dup_fn = key_dup_fn;
+ (*ht_ptr)->key_free_fn = key_free_fn;
+ (*ht_ptr)->value_free_fn = value_free_fn;
+ // Need value dup also?
+
+ (*ht_ptr)->root = sds_ht_node_create();
+
+#ifdef DEBUG
+ (*ht_ptr)->root->depth = 15;
+ sds_ht_crc32c_update_node((*ht_ptr)->root);
+ sds_ht_crc32c_update_instance(*ht_ptr);
+#endif
+
+ return SDS_SUCCESS;
+}
+
+sds_result
+sds_ht_destroy(sds_ht_instance *ht_ptr)
+{
+ if (ht_ptr == NULL) {
+ return SDS_NULL_POINTER;
+ }
+
+#ifdef DEBUG
+ if (sds_ht_crc32c_verify_instance(ht_ptr) != SDS_SUCCESS) {
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+ // Free the tree
+ sds_result result = sds_ht_map_nodes(ht_ptr, sds_ht_node_destroy);
+ if (result != SDS_SUCCESS) {
+#ifdef DEBUG
+ sds_log("sds_ht_destroy", "Failed to destroy instance %d\n",
result);
+#endif
+ return result;
+ }
+ // Free the instance
+ sds_free(ht_ptr);
+ // Done!
+ return SDS_SUCCESS;
+}
+
diff --git a/src/libsds/sds/ht/ht.h b/src/libsds/sds/ht/ht.h
new file mode 100644
index 0000000..0f25774
--- /dev/null
+++ b/src/libsds/sds/ht/ht.h
@@ -0,0 +1,38 @@
+/* BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#pragma once
+
+#include "../sds_internal.h"
+#include <sds.h>
+
+/* Internal tree functions */
+
+/* Node manipulations */
+
+sds_ht_node *sds_ht_node_create(void);
+sds_result sds_ht_node_destroy(sds_ht_instance *ht_ptr, sds_ht_node *node);
+sds_result sds_ht_verify_node(sds_ht_instance *ht_ptr, sds_ht_node *node);
+
+sds_result sds_ht_map_nodes(sds_ht_instance *ht_ptr, sds_result (*map_fn)(sds_ht_instance
*ht_ptr, sds_ht_node *node));
+
+sds_ht_value *sds_ht_value_create(void *key, void *value);
+
+void sds_ht_value_destroy(sds_ht_instance *ht_ptr, sds_ht_value *value);
+
+/* verification */
+void sds_ht_crc32c_update_node(sds_ht_node *node);
+void sds_ht_crc32c_update_instance(sds_ht_instance *inst);
+void sds_ht_crc32c_update_value(sds_ht_value *value);
+
+
+sds_result sds_ht_crc32c_verify_node(sds_ht_node *node);
+sds_result sds_ht_crc32c_verify_instance(sds_ht_instance *inst);
+
+
+
diff --git a/src/libsds/sds/ht/map.c b/src/libsds/sds/ht/map.c
new file mode 100644
index 0000000..58ea060
--- /dev/null
+++ b/src/libsds/sds/ht/map.c
@@ -0,0 +1,60 @@
+/* BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#include "ht.h"
+
+sds_result
+sds_ht_map_nodes(sds_ht_instance *ht_ptr, sds_result (*map_fn)(sds_ht_instance *ht_ptr,
sds_ht_node *node))
+{
+#ifdef DEBUG
+ //verify instance
+ if (sds_ht_crc32c_verify_instance(ht_ptr) != SDS_SUCCESS) {
+ sds_log("sds_ht_map_nodes", "ht_ptr failed verification");
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+ // Create a queue
+ sds_result result = SDS_SUCCESS;
+ sds_queue *node_q = NULL;
+ sds_queue_init(&node_q, NULL);
+ sds_ht_node *work_node = ht_ptr->root;
+ // while node is true
+ while (work_node != NULL) {
+#ifdef DEBUG
+ if (sds_ht_crc32c_verify_node(work_node) != SDS_SUCCESS) {
+ sds_log("sds_ht_map_nodes", "ht_node_%p failed
verification", work_node);
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+ // add nodes to the list
+ for (size_t i = 0; i < HT_SLOTS; i++) {
+ // * should this be a pointer? I think this copies ....
+ sds_ht_slot *slot = &(work_node->slots[i]);
+ if (slot->state == SDS_HT_BRANCH) {
+ sds_queue_enqueue(node_q, slot->slot.node);
+ }
+ }
+ // once done, apply to our node.
+ sds_result internal_result = map_fn(ht_ptr, work_node);
+ if (internal_result != SDS_SUCCESS) {
+ result = internal_result;
+#ifdef DEBUG
+ sds_log("sds_ht_map_nodes", "Encountered an issue with
ht_node_%p: %d\n", work_node, internal_result);
+ return result;
+#endif
+ }
+ // And get the next node for us to work on.
+ if (sds_queue_dequeue(node_q, (void **)&work_node) != SDS_SUCCESS) {
+ // Queue is empty.
+ work_node = NULL;
+ }
+ }
+ return result;
+
+}
+
diff --git a/src/libsds/sds/ht/node.c b/src/libsds/sds/ht/node.c
new file mode 100644
index 0000000..3ce9c23
--- /dev/null
+++ b/src/libsds/sds/ht/node.c
@@ -0,0 +1,65 @@
+/* BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#include "ht.h"
+
+sds_ht_node *
+sds_ht_node_create(void)
+{
+ sds_ht_node *node = sds_calloc(sizeof(sds_ht_node));
+#ifdef DEBUG
+ sds_log("sds_ht_node_create", "Creating ht_node_%p", node);
+#endif
+ return node;
+}
+
+sds_ht_value *
+sds_ht_value_create(void *key, void *value)
+{
+ sds_ht_value *ht_value = sds_calloc(sizeof(sds_ht_value));
+#ifdef DEBUG
+ sds_log("sds_ht_value_create", "Creating ht_value_%p",
ht_value);
+#endif
+ ht_value->key = key;
+ ht_value->value = value;
+#ifdef DEBUG
+ sds_ht_crc32c_update_value(ht_value);
+#endif
+ return ht_value;
+}
+
+void
+sds_ht_value_destroy(sds_ht_instance *ht_ptr, sds_ht_value *value) {
+#ifdef DEBUG
+ sds_log("sds_ht_value_destroy", "Destroying ht_value_%p",
value);
+#endif
+ ht_ptr->key_free_fn(value->key);
+ if (value->value) {
+ ht_ptr->value_free_fn(value->value);
+ }
+ sds_free(value);
+}
+
+sds_result
+sds_ht_node_destroy(sds_ht_instance *ht_ptr, sds_ht_node *node)
+{
+#ifdef DEBUG
+ sds_log("sds_ht_node_destroy", "Destroying ht_node_%p", node);
+#endif
+ for (size_t i = 0; i < HT_SLOTS; i++) {
+ sds_ht_slot slot = node->slots[i];
+ if (slot.state == SDS_HT_VALUE) {
+ sds_ht_value_destroy(ht_ptr, slot.slot.value);
+ }
+ }
+ sds_free(node);
+ return SDS_SUCCESS;
+}
+
+
+
diff --git a/src/libsds/sds/ht/op.c b/src/libsds/sds/ht/op.c
new file mode 100644
index 0000000..f636f42
--- /dev/null
+++ b/src/libsds/sds/ht/op.c
@@ -0,0 +1,359 @@
+/** BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#include "ht.h"
+#include <assert.h>
+
+inline static size_t __attribute__((always_inline))
+sds_ht_hash_slot(int64_t depth, uint64_t hash)
+{
+#ifdef DEBUG
+ assert(depth <= 15 && depth >= 0);
+#endif
+ size_t c_slot = (hash >> (depth * 4)) & 0xF;
+#ifdef DEBUG
+ assert(c_slot < 16);
+#endif
+ return c_slot;
+}
+
+sds_result
+sds_ht_insert(sds_ht_instance *ht_ptr, void *key, void *value)
+{
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "==> begin");
+ if (sds_ht_crc32c_verify_instance(ht_ptr) != SDS_SUCCESS) {
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+
+ if (key == NULL) {
+ return SDS_INVALID_KEY;
+ }
+
+ size_t key_size = ht_ptr->key_size_fn(key);
+ if (key_size == 0) {
+ return SDS_INVALID_KEY;
+ }
+
+ // Use an internal search to find the node and slot we need to occupy
+ uint64_t hashout = sds_siphash13(key, ht_ptr->key_size_fn(key), ht_ptr->hkey);
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "hash key %p -> 0x%"PRIx64, key,
hashout);
+#endif
+ int64_t depth = 15;
+ size_t c_slot = 0;
+ sds_ht_node *work_node = ht_ptr->root;
+ sds_ht_slot *slot = NULL;
+
+ while (depth >= 0) {
+ c_slot = sds_ht_hash_slot(depth, hashout);
+#ifdef DEBUG
+ if (sds_ht_crc32c_verify_node(work_node) != SDS_SUCCESS) {
+ sds_log("sds_ht_insert", "ht_node_%p failed
verification", work_node);
+ return SDS_CHECKSUM_FAILURE;
+ }
+
+ sds_log("sds_ht_insert", "at ht_node_%p depth %"PRIu64"
c_slot 0x%"PRIx64, work_node, depth, c_slot);
+#endif
+ slot = &(work_node->slots[c_slot]);
+ // Now look at the slot, and see if it's full, empty or branch.
+ if (slot->state == SDS_HT_EMPTY) {
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "c_slot 0x%"PRIx64"
state=EMPTY", c_slot);
+#endif
+ // This is where we can insert.
+ work_node->count += 1;
+ slot->state = SDS_HT_VALUE;
+ // Remember to dup the key.
+ slot->slot.value = sds_ht_value_create(ht_ptr->key_dup_fn(key),
value);
+#ifdef DEBUG
+ sds_ht_crc32c_update_node(work_node);
+ sds_log("sds_ht_insert", "<== complete");
+#endif
+ return SDS_SUCCESS;
+ } else if (slot->state == SDS_HT_BRANCH) {
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "c_slot 0x%"PRIx64"
state=BRANCH", c_slot);
+#endif
+ depth--;
+ work_node = slot->slot.node;
+ // Keep looping!
+ } else {
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "ht_node_%p at c_slot
0x%"PRIx64" state=VALUE", work_node, c_slot);
+#endif
+ // Must be a value, let's break out and process it.
+ if (ht_ptr->key_cmp_fn(key, slot->slot.value->key) == 0) {
+ // Yep, it's a dup.
+ return SDS_KEY_PRESENT;
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "<== complete");
+#endif
+ }
+ // Must be a new key. Lets make a new node, put it into the chain.
+ if (depth > 0) {
+ depth--;
+ sds_ht_node *new_node = sds_ht_node_create();
+ // Move our existing value to the new node.
+ uint64_t ex_hashout = sds_siphash13(slot->slot.value->key,
ht_ptr->key_size_fn(slot->slot.value->key), ht_ptr->hkey);
+ size_t ex_c_slot = sds_ht_hash_slot(depth, ex_hashout);
+ sds_ht_slot *ex_slot = &(new_node->slots[ex_c_slot]);
+ ex_slot->state = SDS_HT_VALUE;
+ ex_slot->slot.value = slot->slot.value;
+#ifdef DEBUG
+ sds_log("sds_ht_insert", "existing c_slot
0x%"PRIx64" to new ht_node_%p c_slot 0x%"PRIx64, c_slot, new_node,
ex_c_slot);
+ new_node->depth = depth;
+#endif
+ new_node->parent = work_node;
+ new_node->parent_slot = c_slot;
+ new_node->count = 1;
+ // Now make the existing worknode slot point to our new leaf..
+ slot->state = SDS_HT_BRANCH;
+ slot->slot.node = new_node;
+#ifdef DEBUG
+ sds_ht_crc32c_update_node(work_node);
+ sds_ht_crc32c_update_node(new_node);
+#endif
+ // The next work node is the new_node.
+ work_node = new_node;
+ // That's it!
+ } else {
+ // We are at the end of the tree, and have a hash collision.
+ // append to the value chain.
+ assert(1 == 0);
+ }
+ }
+ }
+ return SDS_UNKNOWN_ERROR;
+}
+
+sds_result
+sds_ht_search(sds_ht_instance *ht_ptr, void *key, void **value)
+{
+ // Search the tree. if key is found, SDS_KEY_PRESENT and *value is set.
+ // Else, SDS_KEY_NOT_PRESENT
+#ifdef DEBUG
+ sds_log("sds_ht_search", "==> begin");
+ if (sds_ht_crc32c_verify_instance(ht_ptr) != SDS_SUCCESS) {
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+
+ if (key == NULL) {
+ return SDS_INVALID_KEY;
+ }
+
+ if (value == NULL) {
+ return SDS_INVALID_POINTER;
+ }
+
+ size_t key_size = ht_ptr->key_size_fn(key);
+ if (key_size == 0) {
+ return SDS_INVALID_KEY;
+ }
+
+ // Use an internal search to find the node and slot we need to occupy
+ uint64_t hashout = sds_siphash13(key, ht_ptr->key_size_fn(key), ht_ptr->hkey);
+#ifdef DEBUG
+ sds_log("sds_ht_search", "hash key %p -> 0x%"PRIx64, key,
hashout);
+#endif
+ int64_t depth = 15;
+ size_t c_slot = 0;
+ sds_ht_node *work_node = ht_ptr->root;
+ sds_ht_slot *slot = NULL;
+
+ while (depth >= 0) {
+ c_slot = sds_ht_hash_slot(depth, hashout);
+#ifdef DEBUG
+ if (sds_ht_crc32c_verify_node(work_node) != SDS_SUCCESS) {
+ sds_log("sds_ht_search", "ht_node_%p failed
verification", work_node);
+ sds_log("sds_ht_search", "==> complete");
+ return SDS_CHECKSUM_FAILURE;
+ }
+ sds_log("sds_ht_search", "depth %"PRIu64" c_slot
0x%"PRIx64, depth, c_slot);
+#endif
+ slot = &(work_node->slots[c_slot]);
+
+ if (slot->state == SDS_HT_BRANCH) {
+ // Keep going ....
+ work_node = slot->slot.node;
+ depth--;
+ } else if (slot->state == SDS_HT_VALUE) {
+ // Check the key realy does match .....
+ if (ht_ptr->key_cmp_fn(key, slot->slot.value->key) == 0) {
+ // WARNING: If depth == 0, check for LL
+ *value = slot->slot.value->value;
+#ifdef DEBUG
+ sds_log("sds_ht_search", "<== complete");
+#endif
+ return SDS_KEY_PRESENT;
+ } else {
+#ifdef DEBUG
+ sds_log("sds_ht_search", "<== complete");
+#endif
+ return SDS_KEY_NOT_PRESENT;
+ }
+ } else {
+ // We got to the hash point where this should be but it's not here ....
+#ifdef DEBUG
+ sds_log("sds_ht_search", "==> complete");
+#endif
+ return SDS_KEY_NOT_PRESENT;
+ }
+ }
+ return SDS_UNKNOWN_ERROR;
+}
+
+
+inline static void __attribute__((always_inline))
+sds_ht_node_cleanup(sds_ht_instance *ht_ptr, sds_ht_node *node)
+{
+ // Okay, we start at *node, and it only has 1 value left.
+ sds_ht_node *work_node = node;
+ sds_ht_node *parent_node = node->parent;
+ while (work_node->count <= 1 && parent_node != NULL) {
+#ifdef DEBUG
+ sds_log("sds_ht_node_cleanup", "Cleaning ht_node_%p into parent
ht_node_%p", node, parent_node);
+ sds_result post_result = sds_ht_verify_node(ht_ptr, work_node);
+ if (post_result != SDS_SUCCESS) {
+ sds_log("sds_ht_delete", "ht_node_%p failed verification post
delete!", work_node);
+ sds_log("sds_ht_delete", "==> complete");
+ assert(1 == 0);
+ }
+#endif
+ // We need to know where we are in the parent.
+ sds_ht_slot *ex_p_slot =
&(parent_node->slots[work_node->parent_slot]);
+#ifdef DEBUG
+ sds_log("sds_ht_node_cleanup", "Slot %p of parent
ht_node_%p", work_node->parent_slot, parent_node);
+#endif
+
+ // Get our remaining slot out. We don't know where it is though ...
+ sds_ht_slot *ex_r_slot = NULL;
+ size_t r_slot = 0;
+ for (; r_slot < HT_SLOTS; r_slot++) {
+ ex_r_slot = &(work_node->slots[r_slot]);
+ if (ex_r_slot->state == SDS_HT_VALUE) {
+ break;
+ } else if (ex_r_slot->state == SDS_HT_BRANCH) {
+ // We can't do anything to this, just bail.
+ return;
+ }
+ }
+ assert (r_slot < HT_SLOTS);
+
+#ifdef DEBUG
+ sds_log("sds_ht_node_cleanup", "Remaining slot %p of
ht_node_%p", r_slot, work_node);
+#endif
+
+ // Now, put our remaining slot into the parent.
+ ex_p_slot->state = SDS_HT_VALUE;
+#ifdef DEBUG
+ sds_log("sds_ht_node_cleanup", "Move slot %p of ht_node_%p to %p
of ht_node_%p", r_slot, work_node, work_node->parent_slot, parent_node);
+#endif
+ ex_p_slot->slot.value = ex_r_slot->slot.value;
+ // And clean the old node.
+ ex_r_slot->slot.value = NULL;
+ ex_r_slot->state = SDS_HT_EMPTY;
+ // Now we can free our node.
+ sds_ht_node_destroy(ht_ptr, work_node);
+
+ work_node = parent_node;
+ parent_node = work_node->parent;
+#ifdef DEBUG
+ sds_ht_crc32c_update_node(work_node);
+#endif
+ }
+}
+
+
+sds_result
+sds_ht_delete(sds_ht_instance *ht_ptr, void *key)
+{
+ // Search the tree. if key is found, SDS_KEY_PRESENT and *value is set.
+ // Else, SDS_KEY_NOT_PRESENT
+#ifdef DEBUG
+ sds_log("sds_ht_delete", "==> begin");
+ if (sds_ht_crc32c_verify_instance(ht_ptr) != SDS_SUCCESS) {
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+
+ if (key == NULL) {
+ return SDS_INVALID_KEY;
+ }
+
+ size_t key_size = ht_ptr->key_size_fn(key);
+ if (key_size == 0) {
+ return SDS_INVALID_KEY;
+ }
+
+ // Use an internal search to find the node and slot we need to occupy
+ uint64_t hashout = sds_siphash13(key, ht_ptr->key_size_fn(key), ht_ptr->hkey);
+#ifdef DEBUG
+ sds_log("sds_ht_delete", "hash key %p -> 0x%"PRIx64, key,
hashout);
+#endif
+ int64_t depth = 15;
+ size_t c_slot = 0;
+ sds_ht_node *work_node = ht_ptr->root;
+ sds_ht_slot *slot = NULL;
+
+ while (depth >= 0) {
+ c_slot = sds_ht_hash_slot(depth, hashout);
+#ifdef DEBUG
+ sds_result result = sds_ht_verify_node(ht_ptr, work_node);
+ if (result != SDS_SUCCESS) {
+ sds_log("sds_ht_delete", "ht_node_%p failed
verification", work_node);
+ sds_log("sds_ht_delete", "==> complete");
+ return result;
+ }
+ sds_log("sds_ht_delete", "depth %"PRIu64" c_slot
0x%"PRIx64, depth, c_slot);
+#endif
+ slot = &(work_node->slots[c_slot]);
+
+ if (slot->state == SDS_HT_BRANCH) {
+ // Keep going ....
+ work_node = slot->slot.node;
+ depth--;
+ } else if (slot->state == SDS_HT_EMPTY) {
+ // We got to the hash point where this should be but it's not here ....
+#ifdef DEBUG
+ sds_log("sds_ht_delete", "==> complete");
+#endif
+ return SDS_KEY_NOT_PRESENT;
+ } else {
+ if (ht_ptr->key_cmp_fn(key, slot->slot.value->key) == 0) {
+ // WARNING: If depth == 0, check for LL
+#ifdef DEBUG
+ sds_log("sds_ht_delete", "deleting from ht_node_%p",
work_node);
+#endif
+ // Free the value, this frees the key + value.
+ sds_ht_value_destroy(ht_ptr, slot->slot.value);
+ slot->slot.value = NULL;
+ slot->state = SDS_HT_EMPTY;
+ work_node->count--;
+#ifdef DEBUG
+ sds_ht_crc32c_update_node(work_node);
+#endif
+ // How much left in this node? if <= 1, need to start merging up.
+ sds_ht_node_cleanup(ht_ptr, work_node);
+#ifdef DEBUG
+ sds_log("sds_ht_delete", "<== complete");
+#endif
+ return SDS_KEY_PRESENT;
+ } else {
+#ifdef DEBUG
+ sds_log("sds_ht_delete", "<== complete");
+#endif
+ return SDS_KEY_NOT_PRESENT;
+ }
+ }
+ }
+ return SDS_UNKNOWN_ERROR;
+}
+
diff --git a/src/libsds/sds/ht/verify.c b/src/libsds/sds/ht/verify.c
new file mode 100644
index 0000000..2934fd1
--- /dev/null
+++ b/src/libsds/sds/ht/verify.c
@@ -0,0 +1,138 @@
+/* BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#include "ht.h"
+
+#ifdef DEBUG
+
+void
+sds_ht_crc32c_update_node(sds_ht_node *node)
+{
+ node->checksum = sds_crc32c(0, (const unsigned char *)node + sizeof(uint32_t),
sizeof(sds_ht_node) - sizeof(uint32_t));
+}
+
+sds_result
+sds_ht_crc32c_verify_node(sds_ht_node *node) {
+ if (sds_crc32c(0, (const unsigned char *)node + sizeof(uint32_t), sizeof(sds_ht_node)
- sizeof(uint32_t)) == node->checksum) {
+ return SDS_SUCCESS;
+ } else {
+ return SDS_CHECKSUM_FAILURE;
+ }
+}
+
+void
+sds_ht_crc32c_update_instance(sds_ht_instance *inst)
+{
+ inst->checksum = sds_crc32c(0, (const unsigned char *)inst + sizeof(uint32_t),
sizeof(sds_ht_instance) - sizeof(uint32_t));
+}
+
+sds_result
+sds_ht_crc32c_verify_instance(sds_ht_instance *inst) {
+ if (sds_crc32c(0, (const unsigned char *)inst + sizeof(uint32_t),
sizeof(sds_ht_instance) - sizeof(uint32_t)) == inst->checksum) {
+ return SDS_SUCCESS;
+ } else {
+ return SDS_CHECKSUM_FAILURE;
+ }
+}
+
+void
+sds_ht_crc32c_update_value(sds_ht_value *value) {
+ value->checksum = sds_crc32c(0, (const unsigned char *)value + sizeof(uint32_t),
sizeof(sds_ht_value) - sizeof(uint32_t));
+}
+
+sds_result
+sds_ht_crc32c_verify_value(sds_ht_value *value) {
+ if (sds_crc32c(0, (const unsigned char *)value + sizeof(uint32_t),
sizeof(sds_ht_value) - sizeof(uint32_t)) == value->checksum) {
+ return SDS_SUCCESS;
+ } else {
+ return SDS_CHECKSUM_FAILURE;
+ }
+}
+
+#endif
+
+sds_result
+sds_ht_verify_node(sds_ht_instance *ht_ptr, sds_ht_node *node)
+{
+ // Do we need our depth so we can check the hashes?
+ // Count that all the counts match slots.
+ size_t count = 0;
+ for (size_t i = 0; i < HT_SLOTS; i++) {
+ sds_ht_slot *slot = &(node->slots[i]);
+ if (slot->state != SDS_HT_EMPTY) {
+ count++;
+ }
+
+ if (slot->state == SDS_HT_EMPTY) {
+ if (slot->slot.value != NULL) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p -
invalid empty node c_slot 0x%"PRIu64, node, i);
+ return SDS_INVALID_NODE;
+ }
+ } else if (slot->state == SDS_HT_VALUE) {
+ if (slot->slot.value == NULL) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p -
invalid value pointer of NULL c_slot 0x%"PRIu64, node);
+ return SDS_INVALID_POINTER;
+ }
+#ifdef DEBUG
+ if (sds_ht_crc32c_verify_value(slot->slot.value) != SDS_SUCCESS) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p -
invalid value checksum", node);
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+ // Check the value is sane.
+ } else {
+ // It's a branch
+ if (slot->slot.node == NULL ) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p -
invalid branch, can not be NULL", node);
+ return SDS_INVALID_POINTER;
+ }
+ }
+
+ }
+ if (count != node->count) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p - invalid item
count, doesn't match", node);
+ return SDS_INVALID_NODE;
+ }
+
+ // Check that our parent and parent slot match
+ if (node->parent != NULL || node->parent_slot != 0) {
+ if (node->count == 0) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p - invalid
item count of 0", node);
+ return SDS_INVALID_NODE;
+ }
+ sds_ht_slot *ex_p_slot = &(node->parent->slots[node->parent_slot]);
+ if (ex_p_slot->state != SDS_HT_BRANCH) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p - invalid
parent, slot state is not branch", node);
+ return SDS_INVALID_POINTER;
+ }
+ if (ex_p_slot->slot.node != node) {
+ sds_log("sds_ht_verify_node", "Failing ht_node_%p - invalid
parent, slot node pointer is not to us", node);
+ return SDS_INVALID_POINTER;
+ }
+ }
+
+#ifdef DEBUG
+ sds_log("sds_ht_verify_node", "ht_node_%p depth= %"PRIu64"
count=%"PRIu64, node, node->depth, node->count);
+#endif
+ return SDS_SUCCESS;
+}
+
+sds_result
+sds_ht_verify(sds_ht_instance *ht_ptr)
+{
+#ifdef DEBUG
+ //verify instance
+ if (sds_ht_crc32c_verify_instance(ht_ptr) != SDS_SUCCESS) {
+ return SDS_CHECKSUM_FAILURE;
+ }
+#endif
+ // Check instance properties
+ // Map all our nodes
+ return sds_ht_map_nodes(ht_ptr, sds_ht_verify_node);
+}
+
diff --git a/src/libsds/test/benchmark.c b/src/libsds/test/benchmark.c
index 1c351f6..83c4d89 100644
--- a/src/libsds/test/benchmark.c
+++ b/src/libsds/test/benchmark.c
@@ -274,6 +274,44 @@ int64_t bptree_cow_destroy_wrapper(void **inst) {
return 0;
}
+/* sds HTree wrapper */
+
+int64_t ht_init_wrapper(void **inst) {
+ sds_ht_instance **ht = (sds_ht_instance **)inst;
+ sds_ht_init(ht, sds_uint64_t_compare, sds_uint64_t_free, sds_uint64_t_dup,
sds_uint64_t_free, sds_uint64_t_size);
+ return 0;
+}
+
+int64_t ht_add_wrapper(void** inst, uint64_t *key, void *value) {
+ sds_ht_instance **ht = (sds_ht_instance **)inst;
+ sds_ht_insert(*ht, key, NULL);
+ return 0;
+}
+
+int64_t ht_search_wrapper(void **inst, uint64_t *key, void **value_out
__attribute__((unused))){
+ sds_ht_instance **ht = (sds_ht_instance **)inst;
+ sds_result result = sds_ht_search(*ht, key, value_out);
+ if (result != SDS_KEY_PRESENT) {
+ return 1;
+ }
+ return 0;
+}
+
+int64_t ht_delete_wrapper(void **inst, uint64_t *key) {
+ sds_ht_instance **ht = (sds_ht_instance **)inst;
+ sds_result result = sds_ht_delete(*ht, key);
+ if (result != SDS_KEY_PRESENT) {
+ return 1;
+ }
+ return 0;
+}
+
+int64_t ht_destroy_wrapper(void **inst) {
+ sds_ht_instance **ht = (sds_ht_instance **)inst;
+ sds_ht_destroy(*ht);
+ return 0;
+}
+
/* The benchmarks */
void
@@ -536,25 +574,38 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bptree_cow_test.delete = bptree_cow_delete_wrapper;
bptree_cow_test.destroy = bptree_cow_destroy_wrapper;
+ struct b_tree_cb htree_test = {0};
+ htree_test.name = "sds htree";
+ htree_test.inst = NULL;
+ htree_test.init = ht_init_wrapper;
+ htree_test.add = ht_add_wrapper;
+ htree_test.search = ht_search_wrapper;
+ htree_test.delete = ht_delete_wrapper;
+ htree_test.destroy = ht_destroy_wrapper;
+
uint64_t test_arrays[] = {5000, 10000, 100000, 500000, 1000000, 2500000, 5000000,
10000000};
- for (size_t i = 0; i < 3; i++) {
+ for (size_t i = 0; i < 5; i++) {
bench_1_insert_seq(&avl_test, test_arrays[i]);
bench_1_insert_seq(&hash_small_test, test_arrays[i]);
bench_1_insert_seq(&hash_med_test, test_arrays[i]);
bench_1_insert_seq(&hash_large_test, test_arrays[i]);
bench_1_insert_seq(&bptree_test, test_arrays[i]);
bench_1_insert_seq(&bptree_cow_test, test_arrays[i]);
+ bench_1_insert_seq(&htree_test, test_arrays[i]);
printf("---\n");
bench_2_search_seq(&avl_test, test_arrays[i]);
- if (test_arrays[i] < 5000000) {
+ if (test_arrays[i] < 500000) {
bench_2_search_seq(&hash_small_test, test_arrays[i]);
}
- bench_2_search_seq(&hash_med_test, test_arrays[i]);
+ if (test_arrays[i] < 1000000) {
+ bench_2_search_seq(&hash_med_test, test_arrays[i]);
+ }
bench_2_search_seq(&hash_large_test, test_arrays[i]);
bench_2_search_seq(&bptree_test, test_arrays[i]);
bench_2_search_seq(&bptree_cow_test, test_arrays[i]);
+ bench_2_search_seq(&htree_test, test_arrays[i]);
printf("---\n");
bench_3_delete_seq(&avl_test, test_arrays[i]);
@@ -563,14 +614,20 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_3_delete_seq(&hash_large_test, test_arrays[i]);
bench_3_delete_seq(&bptree_test, test_arrays[i]);
bench_3_delete_seq(&bptree_cow_test, test_arrays[i]);
+ bench_3_delete_seq(&htree_test, test_arrays[i]);
printf("---\n");
bench_4_insert_search_delete_random(&avl_test, test_arrays[i]);
- bench_4_insert_search_delete_random(&hash_small_test, test_arrays[i]);
- bench_4_insert_search_delete_random(&hash_med_test, test_arrays[i]);
+ if (test_arrays[i] < 500000) {
+ bench_4_insert_search_delete_random(&hash_small_test, test_arrays[i]);
+ }
+ if (test_arrays[i] < 1000000) {
+ bench_4_insert_search_delete_random(&hash_med_test, test_arrays[i]);
+ }
bench_4_insert_search_delete_random(&hash_large_test, test_arrays[i]);
bench_4_insert_search_delete_random(&bptree_test, test_arrays[i]);
bench_4_insert_search_delete_random(&bptree_cow_test, test_arrays[i]);
+ bench_4_insert_search_delete_random(&htree_test, test_arrays[i]);
printf("---\n");
printf("======\n");
diff --git a/src/libsds/test/benchmark_par.c b/src/libsds/test/benchmark_par.c
index 2a43317..d5e70b7 100644
--- a/src/libsds/test/benchmark_par.c
+++ b/src/libsds/test/benchmark_par.c
@@ -29,6 +29,20 @@ struct b_tree_cow_cb bptree_test = {
bptree_destroy_wrapper, /* destroy inst */
};
+struct b_tree_cow_cb htree_test = {
+ "sds htree", /* name */
+ NULL, /* inst */
+ htree_init_wrapper, /* init */
+ generic_read_begin, /* read_begin */
+ generic_read_complete, /* read_complete */
+ generic_write_begin, /* write_begin */
+ generic_write_commit, /* write commit */
+ htree_add_wrapper, /* add */
+ htree_search_wrapper, /* search */
+ htree_delete_wrapper, /* delete */
+ htree_destroy_wrapper, /* destroy inst */
+};
+
struct b_tree_cow_cb bptree_cow_test = {
"sds b+tree with copy on write", /* name */
NULL, /* inst */
@@ -577,6 +591,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_insert_search_delete_batch(&hash_large_cb_test, test_arrays[i]);
bench_insert_search_delete_batch(&bptree_test, test_arrays[i]);
bench_insert_search_delete_batch(&bptree_cow_test, test_arrays[i]);
+ bench_insert_search_delete_batch(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -586,6 +601,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_isd_write_delay(&hash_large_cb_test, test_arrays[i]);
bench_isd_write_delay(&bptree_test, test_arrays[i]);
bench_isd_write_delay(&bptree_cow_test, test_arrays[i]);
+ bench_isd_write_delay(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -595,6 +611,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_isd_read_delay(&hash_large_cb_test, test_arrays[i]);
bench_isd_read_delay(&bptree_test, test_arrays[i]);
bench_isd_read_delay(&bptree_cow_test, test_arrays[i]);
+ bench_isd_read_delay(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -604,6 +621,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_high_thread_small_batch_read(&hash_large_cb_test, test_arrays[i]);
bench_high_thread_small_batch_read(&bptree_test, test_arrays[i]);
bench_high_thread_small_batch_read(&bptree_cow_test, test_arrays[i]);
+ bench_high_thread_small_batch_read(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -613,6 +631,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_high_thread_large_batch_read(&hash_large_cb_test, test_arrays[i]);
bench_high_thread_large_batch_read(&bptree_test, test_arrays[i]);
bench_high_thread_large_batch_read(&bptree_cow_test, test_arrays[i]);
+ bench_high_thread_large_batch_read(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -622,6 +641,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_high_thread_small_batch_write(&hash_large_cb_test, test_arrays[i]);
bench_high_thread_small_batch_write(&bptree_test, test_arrays[i]);
bench_high_thread_small_batch_write(&bptree_cow_test, test_arrays[i]);
+ bench_high_thread_small_batch_write(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -631,6 +651,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_high_thread_large_batch_write(&hash_large_cb_test, test_arrays[i]);
bench_high_thread_large_batch_write(&bptree_test, test_arrays[i]);
bench_high_thread_large_batch_write(&bptree_cow_test, test_arrays[i]);
+ bench_high_thread_large_batch_write(&htree_test, test_arrays[i]);
printf("---\n");
/*
@@ -640,6 +661,7 @@ main (int argc __attribute__((unused)), char **argv
__attribute__((unused))) {
bench_insert_search_delete_random(&hash_large_cb_test, test_arrays[i]);
bench_insert_search_delete_random(&bptree_test, test_arrays[i]);
bench_insert_search_delete_random(&bptree_cow_test, test_arrays[i]);
+ bench_insert_search_delete_random(&htree_test, test_arrays[i]);
printf("---\n");
}
diff --git a/src/libsds/test/benchmark_par.h b/src/libsds/test/benchmark_par.h
index 2507c3b..a16b96c 100644
--- a/src/libsds/test/benchmark_par.h
+++ b/src/libsds/test/benchmark_par.h
@@ -45,15 +45,17 @@ int64_t generic_write_begin(void **inst, void **txn);
int64_t generic_write_commit(void **inst, void *txn);
int64_t bptree_init_wrapper(void **inst);
-int64_t bptree_read_begin(void **inst, void **txn);
-int64_t bptree_read_complete(void **inst, void *txn);
-int64_t bptree_write_begin(void **inst, void **txn);
-int64_t bptree_write_commit(void **inst, void *txn);
int64_t bptree_add_wrapper(void **inst, void *txn, uint64_t *key, void *value);
int64_t bptree_search_wrapper(void **inst, void *txn, uint64_t *key, void **value_out);
int64_t bptree_delete_wrapper(void **inst, void *txn, uint64_t *key);
int64_t bptree_destroy_wrapper(void **inst);
+int64_t htree_init_wrapper(void **inst);
+int64_t htree_add_wrapper(void **inst, void *txn, uint64_t *key, void *value);
+int64_t htree_search_wrapper(void **inst, void *txn, uint64_t *key, void **value_out);
+int64_t htree_delete_wrapper(void **inst, void *txn, uint64_t *key);
+int64_t htree_destroy_wrapper(void **inst);
+
int64_t bptree_cow_init_wrapper(void **inst);
int64_t bptree_cow_read_begin(void **inst, void **read_txn);
int64_t bptree_cow_read_complete(void **inst, void *read_txn);
diff --git a/src/libsds/test/benchmark_parwrap.c b/src/libsds/test/benchmark_parwrap.c
index 747bc1c..c617fff 100644
--- a/src/libsds/test/benchmark_parwrap.c
+++ b/src/libsds/test/benchmark_parwrap.c
@@ -184,6 +184,58 @@ int64_t bptree_cow_destroy_wrapper(void **inst) {
/* Hashmap structures */
+int64_t htree_init_wrapper(void **inst) {
+#ifdef WITH_RWLOCK
+ pthread_rwlock_init(&the_lock, NULL);
+#else
+ pthread_mutex_init(&the_lock, NULL);
+#endif
+ sds_ht_instance **binst = (sds_ht_instance **)inst;
+ sds_ht_init(binst, sds_uint64_t_compare, sds_uint64_t_free, sds_uint64_t_dup,
sds_uint64_t_free, sds_uint64_t_size);
+ return 0;
+}
+
+int64_t htree_add_wrapper(void **inst, void *txn __attribute__((unused)), uint64_t *key,
void *value) {
+ // THIS WILL BREAK SOMETIME!
+ sds_ht_instance **binst = (sds_ht_instance **)inst;
+ sds_ht_insert(*binst, (void*)key, value);
+ return 0;
+}
+
+int64_t htree_search_wrapper(void **inst, void *txn __attribute__((unused)), uint64_t
*key, void **value_out __attribute__((unused))) {
+ sds_ht_instance **binst = (sds_ht_instance **)inst;
+ void *value;
+ sds_result result = sds_ht_search(*binst, (void *)key, &value);
+ if (result != SDS_KEY_PRESENT) {
+ // printf("search result is %d\n", result);
+ return 1;
+ }
+ return 0;
+}
+
+int64_t htree_delete_wrapper(void **inst, void *txn __attribute__((unused)), uint64_t
*key) {
+ sds_ht_instance **binst = (sds_ht_instance **)inst;
+ sds_result result = sds_ht_delete(*binst, (void *)key);
+
+ if (result != SDS_KEY_PRESENT) {
+ // printf("delete result is %d\n", result);
+ return 1;
+ }
+ return 0;
+}
+
+int64_t htree_destroy_wrapper(void **inst) {
+ sds_ht_instance **binst = (sds_ht_instance **)inst;
+ // sds_bptree_display(*binst);
+ sds_ht_destroy(*binst);
+#ifdef WITH_RWLOCK
+ pthread_rwlock_destroy(&the_lock);
+#else
+ pthread_mutex_destroy(&the_lock);
+#endif
+ return 0;
+}
+
/* NSPR PLHash wrappers */
/*
diff --git a/src/libsds/test/test_fixtures.c b/src/libsds/test/test_fixtures.c
index 49bce57..10ad596 100644
--- a/src/libsds/test/test_fixtures.c
+++ b/src/libsds/test/test_fixtures.c
@@ -200,3 +200,26 @@ lqueue_test_teardown(void **state) {
assert_int_equal(result, SDS_SUCCESS);
return 0;
}
+
+int
+ht_test_setup(void **state)
+{
+ sds_ht_instance *ht = NULL;
+ sds_result result = SDS_SUCCESS;
+ result = sds_ht_init(&ht, sds_uint64_t_compare, sds_uint64_t_free,
sds_uint64_t_dup, sds_uint64_t_free, sds_uint64_t_size);
+ assert_true(result == SDS_SUCCESS);
+ *state = ht;
+ return 0;
+}
+
+int
+ht_test_teardown(void **state)
+{
+ sds_ht_instance *ht = *state;
+ sds_result result = SDS_SUCCESS;
+ result = sds_ht_verify(ht);
+ assert_true(result == SDS_SUCCESS);
+ result = sds_ht_destroy(ht);
+ assert_true(result == SDS_SUCCESS);
+ return 0;
+}
diff --git a/src/libsds/test/test_sds.c b/src/libsds/test/test_sds.c
index dff5b8b..0d29f22 100644
--- a/src/libsds/test/test_sds.c
+++ b/src/libsds/test/test_sds.c
@@ -12,12 +12,16 @@
int
main ( int argc __attribute__((unused)), char **argv __attribute__((unused))) {
int result = 0;
+ /*
result += run_bpt_tests();
result += run_set_tests();
result += run_cow_tests();
result += run_queue_tests();
result += run_tqueue_tests();
result += run_lqueue_tests();
+ */
+ result += run_siphash_tests();
+ result += run_ht_tests();
return result;
}
diff --git a/src/libsds/test/test_sds.h b/src/libsds/test/test_sds.h
index 4755d5e..b1cbada 100644
--- a/src/libsds/test/test_sds.h
+++ b/src/libsds/test/test_sds.h
@@ -239,6 +239,8 @@ int run_cow_tests(void);
int run_queue_tests (void);
int run_tqueue_tests (void);
int run_lqueue_tests (void);
+int run_siphash_tests (void);
+int run_ht_tests (void);
/* fixtures */
int bptree_test_setup(void **state);
@@ -260,4 +262,7 @@ int tqueue_test_teardown(void **state);
int lqueue_test_setup(void **state);
int lqueue_test_teardown(void **state);
+int ht_test_setup(void **state);
+int ht_test_teardown(void **state);
+
diff --git a/src/libsds/test/test_sds_csiphash.c b/src/libsds/test/test_sds_csiphash.c
new file mode 100644
index 0000000..c4cc12c
--- /dev/null
+++ b/src/libsds/test/test_sds_csiphash.c
@@ -0,0 +1,47 @@
+/** BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2016, William Brown <william at blackhats dot net dot au>
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+/*
+ * test_sds_csiphash validates that siphash operates correctly
+ * on this platform.
+ */
+
+#include "test_sds.h"
+
+static void
+test_siphash(void **state __attribute__((unused))) {
+
+ //
+ uint64_t value = 0;
+ uint64_t hashout = 0;
+ char key[16] = {0};
+
+ uint64_t test_a = 15794382300316794652;
+ uint64_t test_b = 13042610424265326907;
+
+ // Initial simple test
+ value = 5;
+ hashout = sds_siphash13(&value, sizeof(uint64_t), key);
+ assert_true(hashout == test_a);
+
+ char *test = "abc";
+ hashout = sds_siphash13(test, 4, key);
+ assert_true(hashout == test_b);
+}
+
+int
+run_siphash_tests (void) {
+ const struct CMUnitTest tests[] = {
+ cmocka_unit_test(test_siphash),
+ };
+ return cmocka_run_group_tests_name("siphash", tests, NULL, NULL);
+}
+
+
+
diff --git a/src/libsds/test/test_sds_ht.c b/src/libsds/test/test_sds_ht.c
new file mode 100644
index 0000000..cfe60ce
--- /dev/null
+++ b/src/libsds/test/test_sds_ht.c
@@ -0,0 +1,137 @@
+/** BEGIN COPYRIGHT BLOCK
+ * Copyright (c) 2017, Red Hat, Inc
+ * All rights reserved.
+ *
+ * License: GPL (version 3 or any later version).
+ * See LICENSE for details.
+ * END COPYRIGHT BLOCK **/
+
+#include "test_sds.h"
+
+void
+test_ht_null_init(void **state __attribute__((unused)))
+{
+ assert_true(SDS_NULL_POINTER == sds_ht_init(NULL, NULL, NULL, NULL, NULL, NULL));
+}
+
+void
+test_ht_null_insert(void **state)
+{
+ sds_ht_instance *ht = *state;
+ assert_true(sds_ht_insert(ht, NULL, NULL) == SDS_INVALID_KEY);
+}
+
+void
+test_ht_simple_insert(void **state)
+{
+ sds_ht_instance *ht = *state;
+ uint64_t key = 1;
+
+ assert_true(sds_ht_insert(ht, &key, NULL) == SDS_SUCCESS);
+}
+
+void
+test_ht_simple_search(void **state)
+{
+ sds_ht_instance *ht = *state;
+ uint64_t key = 1;
+ uint64_t key_missing = 2;
+ void *value = NULL;
+
+ assert_true(sds_ht_insert(ht, &key, NULL) == SDS_SUCCESS);
+ assert_true(sds_ht_search(ht, &key, &value) == SDS_KEY_PRESENT);
+ assert_true(sds_ht_search(ht, &key_missing, &value) == SDS_KEY_NOT_PRESENT);
+}
+
+void
+test_ht_medium_insert(void **state)
+{
+ sds_ht_instance *ht = *state;
+ void *value = NULL;
+ for (uint64_t i = 0; i < 256; i++) {
+ assert_true(sds_ht_insert(ht, &i, NULL) == SDS_SUCCESS);
+ }
+ for (uint64_t i = 0; i < 256; i++) {
+ assert_true(sds_ht_search(ht, &i, &value) == SDS_KEY_PRESENT);
+ }
+}
+
+void
+test_ht_large_insert(void **state)
+{
+ sds_ht_instance *ht = *state;
+ void *value = NULL;
+ for (uint64_t i = 0; i < 8192; i++) {
+ assert_true(sds_ht_insert(ht, &i, NULL) == SDS_SUCCESS);
+ }
+ assert_true(sds_ht_verify(ht) == SDS_SUCCESS);
+ for (uint64_t i = 0; i < 8192; i++) {
+ assert_true(sds_ht_search(ht, &i, &value) == SDS_KEY_PRESENT);
+ }
+}
+
+void
+test_ht_small_delete(void **state)
+{
+ sds_ht_instance *ht = *state;
+ uint64_t key = 1;
+ uint64_t key_missing = 2;
+ void *value = NULL;
+
+ assert_true(sds_ht_insert(ht, &key, NULL) == SDS_SUCCESS);
+ assert_true(sds_ht_search(ht, &key, &value) == SDS_KEY_PRESENT);
+ assert_true(sds_ht_delete(ht, &key_missing) == SDS_KEY_NOT_PRESENT);
+ assert_true(sds_ht_delete(ht, &key) == SDS_KEY_PRESENT);
+ assert_true(sds_ht_search(ht, &key, &value) == SDS_KEY_NOT_PRESENT);
+}
+
+void
+test_ht_medium_delete(void **state)
+{
+ sds_ht_instance *ht = *state;
+ void *value = NULL;
+ for (uint64_t i = 0; i < 256; i++) {
+ assert_true(sds_ht_insert(ht, &i, NULL) == SDS_SUCCESS);
+ assert_true(sds_ht_verify(ht) == SDS_SUCCESS);
+ }
+ for (uint64_t i = 0; i < 256; i++) {
+ assert_true(sds_ht_search(ht, &i, &value) == SDS_KEY_PRESENT);
+ }
+ for (uint64_t i = 0; i < 256; i++) {
+ assert_true(sds_ht_delete(ht, &i) == SDS_KEY_PRESENT);
+ assert_true(sds_ht_verify(ht) == SDS_SUCCESS);
+ }
+ for (uint64_t i = 0; i < 256; i++) {
+ assert_true(sds_ht_search(ht, &i, &value) == SDS_KEY_NOT_PRESENT);
+ }
+}
+
+
+int
+run_ht_tests (void) {
+ const struct CMUnitTest tests[] = {
+ cmocka_unit_test(test_ht_null_init),
+ cmocka_unit_test_setup_teardown(test_ht_null_insert,
+ ht_test_setup,
+ ht_test_teardown),
+ cmocka_unit_test_setup_teardown(test_ht_simple_insert,
+ ht_test_setup,
+ ht_test_teardown),
+ cmocka_unit_test_setup_teardown(test_ht_simple_search,
+ ht_test_setup,
+ ht_test_teardown),
+ cmocka_unit_test_setup_teardown(test_ht_medium_insert,
+ ht_test_setup,
+ ht_test_teardown),
+ cmocka_unit_test_setup_teardown(test_ht_large_insert,
+ ht_test_setup,
+ ht_test_teardown),
+ cmocka_unit_test_setup_teardown(test_ht_small_delete,
+ ht_test_setup,
+ ht_test_teardown),
+ cmocka_unit_test_setup_teardown(test_ht_medium_delete,
+ ht_test_setup,
+ ht_test_teardown),
+ };
+ return cmocka_run_group_tests_name("ht", tests, NULL, NULL);
+}
--
To stop receiving notification emails like this one, please contact
the administrator of this repository.