1 files changed, 271 insertions, 0 deletions
diff --git a/include/ck_ht.h b/include/ck_ht.h
new file mode 100644
index 0000000..a949d30
--- /dev/null
+++ b/include/ck_ht.h
@@ -0,0 +1,271 @@
+/*
+ * Copyright 2012-2015 Samy Al Bahra.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 CK_HT_H
+#define CK_HT_H
+
+#include <ck_pr.h>
+
+#define CK_F_HT
+#if defined(CK_F_PR_LOAD_64) && defined(CK_F_PR_STORE_64)
+#define CK_HT_TYPE uint64_t
+#define CK_HT_TYPE_LOAD		ck_pr_load_64
+#define CK_HT_TYPE_STORE 	ck_pr_store_64
+#define CK_HT_TYPE_MAX		UINT64_MAX
+#else
+#define CK_HT_TYPE uint32_t
+#define CK_HT_TYPE_LOAD		ck_pr_load_32
+#define CK_HT_TYPE_STORE	ck_pr_store_32
+#define CK_HT_TYPE_MAX		UINT32_MAX
+#endif
+
+
+#include <ck_cc.h>
+#include <ck_malloc.h>
+#include <ck_md.h>
+#include <ck_stdint.h>
+#include <ck_stdbool.h>
+#include <ck_stddef.h>
+
+struct ck_ht_hash {
+	uint64_t value;
+};
+typedef struct ck_ht_hash ck_ht_hash_t;
+
+#define CK_HT_MODE_DIRECT	1U
+#define CK_HT_MODE_BYTESTRING	2U
+#define CK_HT_WORKLOAD_DELETE	4U
+
+#if defined(CK_MD_POINTER_PACK_ENABLE) && defined(CK_MD_VMA_BITS)
+#define CK_HT_PP
+#define CK_HT_KEY_LENGTH ((sizeof(void *) * 8) - CK_MD_VMA_BITS)
+#define CK_HT_KEY_MASK   ((1U << CK_HT_KEY_LENGTH) - 1)
+#else
+#define CK_HT_KEY_LENGTH 65535U
+#endif
+
+struct ck_ht_entry {
+#ifdef CK_HT_PP
+	uintptr_t key;
+	uintptr_t value CK_CC_PACKED;
+} CK_CC_ALIGN(16);
+#else
+	uintptr_t key;
+	uintptr_t value;
+	CK_HT_TYPE key_length;
+	CK_HT_TYPE hash;
+} CK_CC_ALIGN(32);
+#endif
+typedef struct ck_ht_entry ck_ht_entry_t;
+
+/*
+ * The user is free to define their own stub values.
+ */
+#ifndef CK_HT_KEY_EMPTY
+#define CK_HT_KEY_EMPTY		((uintptr_t)0)
+#endif
+
+#ifndef CK_HT_KEY_TOMBSTONE
+#define CK_HT_KEY_TOMBSTONE	(~CK_HT_KEY_EMPTY)
+#endif
+
+/*
+ * Hash callback function. First argument is updated to contain a hash value,
+ * second argument is the key, third argument is key length and final argument
+ * is the hash table seed value.
+ */
+typedef void ck_ht_hash_cb_t(ck_ht_hash_t *, const void *, size_t, uint64_t);
+
+struct ck_ht_map;
+struct ck_ht {
+	struct ck_malloc *m;
+	struct ck_ht_map *map;
+	unsigned int mode;
+	uint64_t seed;
+	ck_ht_hash_cb_t *h;
+};
+typedef struct ck_ht ck_ht_t;
+
+struct ck_ht_stat {
+	uint64_t probe_maximum;
+	uint64_t n_entries;
+};
+
+struct ck_ht_iterator {
+	struct ck_ht_entry *current;
+	uint64_t offset;
+};
+typedef struct ck_ht_iterator ck_ht_iterator_t;
+
+#define CK_HT_ITERATOR_INITIALIZER { NULL, 0 }
+
+CK_CC_INLINE static void
+ck_ht_iterator_init(struct ck_ht_iterator *iterator)
+{
+
+	iterator->current = NULL;
+	iterator->offset = 0;
+	return;
+}
+
+CK_CC_INLINE static bool
+ck_ht_entry_empty(ck_ht_entry_t *entry)
+{
+
+	return entry->key == CK_HT_KEY_EMPTY;
+}
+
+CK_CC_INLINE static void
+ck_ht_entry_key_set_direct(ck_ht_entry_t *entry, uintptr_t key)
+{
+
+	entry->key = key;
+	return;
+}
+
+CK_CC_INLINE static void
+ck_ht_entry_key_set(ck_ht_entry_t *entry, const void *key, uint16_t key_length)
+{
+
+#ifdef CK_HT_PP
+	entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS);
+#else
+	entry->key = (uintptr_t)key;
+	entry->key_length = key_length;
+#endif
+
+	return;
+}
+
+CK_CC_INLINE static void *
+ck_ht_entry_key(ck_ht_entry_t *entry)
+{
+
+#ifdef CK_HT_PP
+	return (void *)(entry->key & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1));
+#else
+	return (void *)entry->key;
+#endif
+}
+
+CK_CC_INLINE static uint16_t
+ck_ht_entry_key_length(ck_ht_entry_t *entry)
+{
+
+#ifdef CK_HT_PP
+	return entry->key >> CK_MD_VMA_BITS;
+#else
+	return entry->key_length;
+#endif
+}
+
+CK_CC_INLINE static void *
+ck_ht_entry_value(ck_ht_entry_t *entry)
+{
+
+#ifdef CK_HT_PP
+	return (void *)(entry->value & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1));
+#else
+	return (void *)entry->value;
+#endif
+}
+
+CK_CC_INLINE static void
+ck_ht_entry_set(struct ck_ht_entry *entry,
+		ck_ht_hash_t h,
+		const void *key,
+		uint16_t key_length,
+		const void *value)
+{
+
+#ifdef CK_HT_PP
+	entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS);
+	entry->value = (uintptr_t)value | ((uintptr_t)(h.value >> 32) << CK_MD_VMA_BITS);
+#else
+	entry->key = (uintptr_t)key;
+	entry->value = (uintptr_t)value;
+	entry->key_length = key_length;
+	entry->hash = h.value;
+#endif
+
+	return;
+}
+
+CK_CC_INLINE static void
+ck_ht_entry_set_direct(struct ck_ht_entry *entry,
+		       ck_ht_hash_t h,
+		       uintptr_t key,
+		       uintptr_t value)
+{
+
+	entry->key = key;
+	entry->value = value;
+
+#ifndef CK_HT_PP
+	entry->hash = h.value;
+#else
+	(void)h;
+#endif
+	return;
+}
+
+CK_CC_INLINE static uintptr_t
+ck_ht_entry_key_direct(ck_ht_entry_t *entry)
+{
+
+	return entry->key;
+}
+
+CK_CC_INLINE static uintptr_t
+ck_ht_entry_value_direct(ck_ht_entry_t *entry)
+{
+
+	return entry->value;
+}
+
+/*
+ * Iteration must occur without any concurrent mutations on
+ * the hash table.
+ */
+bool ck_ht_next(ck_ht_t *, ck_ht_iterator_t *, ck_ht_entry_t **entry);
+
+void ck_ht_stat(ck_ht_t *, struct ck_ht_stat *);
+void ck_ht_hash(ck_ht_hash_t *, ck_ht_t *, const void *, uint16_t);
+void ck_ht_hash_direct(ck_ht_hash_t *, ck_ht_t *, uintptr_t);
+bool ck_ht_init(ck_ht_t *, unsigned int, ck_ht_hash_cb_t *,
+    struct ck_malloc *, CK_HT_TYPE, uint64_t);
+void ck_ht_destroy(ck_ht_t *);
+bool ck_ht_set_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
+bool ck_ht_put_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
+bool ck_ht_get_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
+bool ck_ht_gc(struct ck_ht *, unsigned long, unsigned long);
+bool ck_ht_grow_spmc(ck_ht_t *, CK_HT_TYPE);
+bool ck_ht_remove_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
+bool ck_ht_reset_spmc(ck_ht_t *);
+bool ck_ht_reset_size_spmc(ck_ht_t *, CK_HT_TYPE);
+CK_HT_TYPE ck_ht_count(ck_ht_t *);
+
+#endif /* CK_HT_H */