Change Log:
1) Fix the whitespace error
2) Update the copyright to 2016
-----Original Message-----
From: Ru Jia [mailto:[email protected]]
Sent: Monday, June 13, 2016 2:42 PM
To: [email protected]
Cc: [email protected]; Ru Jia
Subject: [API-NEXT PATCH v5 1/2] helper: table: add impl of cuckoo hash
table
Signed-off-by: Ru Jia <[email protected]>
---
helper/Makefile.am | 4 +-
helper/cuckootable.c | 743
++++++++++++++++++++++++++++++++++++++++++++++
helper/odph_cuckootable.h | 82 +++++
3 files changed, 828 insertions(+), 1 deletion(-) create mode 100644
helper/cuckootable.c create mode 100644 helper/odph_cuckootable.h
diff --git a/helper/Makefile.am b/helper/Makefile.am index
aa58e8c..116a1f0 100644
--- a/helper/Makefile.am
+++ b/helper/Makefile.am
@@ -27,6 +27,7 @@ noinst_HEADERS = \
$(srcdir)/odph_debug.h \
$(srcdir)/odph_hashtable.h \
$(srcdir)/odph_lineartable.h \
+ $(srcdir)/odph_cuckootable.h \
$(srcdir)/odph_list_internal.h
__LIB__libodphelper_linux_la_SOURCES = \ @@ -35,6 +36,7 @@
__LIB__libodphelper_linux_la_SOURCES = \
chksum.c \
linux.c \
hashtable.c \
- lineartable.c
+ lineartable.c \
+ cuckootable.c
lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la diff --git
a/helper/cuckootable.c b/helper/cuckootable.c new file mode 100644 index
0000000..e463e81
--- /dev/null
+++ b/helper/cuckootable.c
@@ -0,0 +1,743 @@
+/* Copyright (c) 2016, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
+ * All rights reserved.
+ *
+ * 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 Intel Corporation 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 <string.h>
+#include <stdint.h>
+#include <errno.h>
+#include <stdio.h>
+
+#include "odph_cuckootable.h"
+#include "odph_debug.h"
+#include <odp_api.h>
+
+/* More efficient access to a map of single ullong */
+#define ULLONG_FOR_EACH_1(IDX, MAP) \
+ for (; MAP && (((IDX) = __builtin_ctzll(MAP)), true); \
+ MAP = (MAP & (MAP - 1)))
+
+/** @magic word, write to the first byte of the memory block
+ * to indicate this block is used by a cuckoo hash table
+ */
+#define ODPH_CUCKOO_TABLE_MAGIC_WORD 0xDFDFFDFD
+
+/** Number of items per bucket. */
+#define HASH_BUCKET_ENTRIES 4
+
+#define NULL_SIGNATURE 0
+#define KEY_ALIGNMENT 16
+
+/** Maximum size of hash table that can be created. */
+#define HASH_ENTRIES_MAX 1048576
+
+/** @internal signature struct
+ * Structure storing both primary and secondary hashes
+ */
+struct cuckoo_table_signatures {
+ union {
+ struct {
+ uint32_t current;
+ uint32_t alt;
+ };
+ uint64_t sig;
+ };
+};
+
+/** @internal kay-value struct
+ * Structure that stores key-value pair
+ */
+struct cuckoo_table_key_value {
+ uint8_t *key;
+ uint8_t *value;
+};
+
+/** @internal bucket structure
+ * Put the elements with defferent keys but a same signature
+ * into a bucket, and each bucket has at most HASH_BUCKET_ENTRIES
+ * elements.
+ */
+struct cuckoo_table_bucket {
+ struct cuckoo_table_signatures signatures[HASH_BUCKET_ENTRIES];
+ /* Includes dummy key index that always contains index 0 */
+ odp_buffer_t key_buf[HASH_BUCKET_ENTRIES + 1];
+ uint8_t flag[HASH_BUCKET_ENTRIES];
+} ODP_ALIGNED_CACHE;
+
+/* More efficient access to a map of single ullong */
+#define ULLONG_FOR_EACH_1(IDX, MAP) \
+ for (; MAP && (((IDX) = __builtin_ctzll(MAP)), true); \
+ MAP = (MAP & (MAP - 1)))
+
+/** A hash table structure. */
+typedef struct {
+ /**< for check */
+ uint32_t magicword;
+ /**< Name of the hash. */
+ char name[ODPH_TABLE_NAME_LEN];
+ /**< Total table entries. */
+ uint32_t entries;
+ /**< Number of buckets in table. */
+ uint32_t num_buckets;
+ /**< Length of hash key. */
+ uint32_t key_len;
+ /**< Length of value. */
+ uint32_t value_len;
+ /**< Bitmask for getting bucket index from hash signature. */
+ uint32_t bucket_bitmask;
+ /**< Queue that stores all free key-value slots*/
+ odp_queue_t free_slots;
+ /** Table with buckets storing all the hash values and key indexes
+ to the key table*/
+ struct cuckoo_table_bucket *buckets;
+} odph_cuckoo_table_impl ODP_ALIGNED_CACHE;
+
+/**
+ * Aligns input parameter to the next power of 2
+ *
+ * @param x
+ * The integer value to algin
+ *
+ * @return
+ * Input parameter aligned to the next power of 2
+ */
+static inline uint32_t
+align32pow2(uint32_t x)
+{
+ x--;
+ x |= x >> 1;
+ x |= x >> 2;
+ x |= x >> 4;
+ x |= x >> 8;
+ x |= x >> 16;
+
+ return x + 1;
+}
+
+/**
+ * Returns true if n is a power of 2
+ * @param n
+ * Number to check
+ * @return 1 if true, 0 otherwise
+ */
+static inline int
+is_power_of_2(uint32_t n)
+{
+ return n && !(n & (n - 1));
+}
+
+odph_table_t
+odph_cuckoo_table_lookup(const char *name) {
+ odph_cuckoo_table_impl *tbl = NULL;
+
+ if (name == NULL || strlen(name) >= ODPH_TABLE_NAME_LEN)
+ return NULL;
+
+ tbl = (odph_cuckoo_table_impl
*)odp_shm_addr(odp_shm_lookup(name));
+
+ if (
+ tbl != NULL &&
+ tbl->magicword == ODPH_CUCKOO_TABLE_MAGIC_WORD
&&
+ strcmp(tbl->name, name) == 0)
+ return (odph_table_t)tbl;
+}
+
+odph_table_t
+odph_cuckoo_table_create(
+ const char *name, uint32_t capacity, uint32_t key_size,
+ uint32_t value_size)
+{
+ odph_cuckoo_table_impl *tbl;
+ odp_shm_t shm_tbl;
+
+ odp_pool_t pool;
+ odp_pool_param_t param;
+
+ odp_queue_t queue;
+ odp_queue_param_t qparam;
+
+ char pool_name[ODPH_TABLE_NAME_LEN + 3],
+ queue_name[ODPH_TABLE_NAME_LEN + 3];
+ unsigned i;
+ uint32_t impl_size, kv_entry_size,
+ bucket_num, bucket_size;
+
+ /* Check for valid parameters */
+ if (
+ (capacity > HASH_ENTRIES_MAX) ||
+ (capacity < HASH_BUCKET_ENTRIES) ||
+ (key_size == 0) ||
+ (strlen(name) == 0)) {
+ ODPH_DBG("invalid parameters\n");
+ return NULL;
+ }
+
+ /* Guarantee there's no existing */
+ tbl = (odph_cuckoo_table_impl
*)odph_cuckoo_table_lookup(name);
+ if (tbl != NULL) {
+ ODPH_DBG("cuckoo hash table %s already exists\n", name);
+ return NULL;
+ }
+
+ /* Calculate the sizes of different parts of cuckoo hash table */
+ impl_size = sizeof(odph_cuckoo_table_impl);
+ kv_entry_size = sizeof(struct cuckoo_table_key_value)
+ + key_size + value_size;
+
+ bucket_num = align32pow2(capacity) / HASH_BUCKET_ENTRIES;
+ bucket_size = bucket_num * sizeof(struct cuckoo_table_bucket);
+
+ shm_tbl = odp_shm_reserve(
+ name, impl_size + bucket_size,
+ ODP_CACHE_LINE_SIZE,
ODP_SHM_SW_ONLY);
+
+ if (shm_tbl == ODP_SHM_INVALID) {
+ ODPH_DBG(
+ "shm allocation failed for
odph_cuckoo_table_impl %s\n",
+ name);
+ return NULL;
+ }
+
+ tbl = (odph_cuckoo_table_impl *)odp_shm_addr(shm_tbl);
+ memset(tbl, 0, impl_size + bucket_size);
+
+ /* header of this mem block is the table impl struct,
+ * then the bucket pool.
+ */
+ tbl->buckets = (struct cuckoo_table_bucket *)(
+ (char *)tbl + impl_size);
+
+ /* initialize key-value buffer pool */
+ snprintf(pool_name, sizeof(pool_name), "kv_%s", name);
+ pool = odp_pool_lookup(pool_name);
+
+ if (pool != ODP_POOL_INVALID)
+ odp_pool_destroy(pool);
+
+ param.type = ODP_POOL_BUFFER;
+ param.buf.size = kv_entry_size;
+ param.buf.align = ODP_CACHE_LINE_SIZE;
+ param.buf.num = capacity;
+
+ pool = odp_pool_create(pool_name, ¶m);
+
+ if (pool == ODP_POOL_INVALID) {
+ ODPH_DBG("failed to create key-value pool\n");
+ odp_shm_free(shm_tbl);
+ return NULL;
+ }
+
+ /* initialize free_slots queue */
+ odp_queue_param_init(&qparam);
+ qparam.type = ODP_QUEUE_TYPE_PLAIN;
+
+ snprintf(queue_name, sizeof(queue_name), "fs_%s", name);
+ queue = odp_queue_create(queue_name, &qparam);
+ if (queue == ODP_QUEUE_INVALID) {
+ ODPH_DBG("failed to create free_slots queue\n");
+ odp_pool_destroy(pool);
+ odp_shm_free(shm_tbl);
+ return NULL;
+ }
+
+ /* Setup hash context */
+ snprintf(tbl->name, sizeof(tbl->name), "%s", name);
+ tbl->magicword = ODPH_CUCKOO_TABLE_MAGIC_WORD;
+ tbl->entries = capacity;
+ tbl->key_len = key_size;
+ tbl->value_len = value_size;
+ tbl->num_buckets = bucket_num;
+ tbl->bucket_bitmask = bucket_num - 1;
+ tbl->free_slots = queue;
+
+ /* generate all free buffers, and put into queue */
+ for (i = 0; i < capacity; i++) {
+ odp_event_t ev = odp_buffer_to_event(
+ odp_buffer_alloc(pool));
+ if (ev == ODP_EVENT_INVALID) {
+ ODPH_DBG("failed to generate free slots\n");
+ odph_cuckoo_table_destroy((odph_table_t)tbl);
+ return NULL;
+ }
+
+ if (odp_queue_enq(queue, ev) < 0) {
+ ODPH_DBG("failed to enqueue free slots\n");
+ odph_cuckoo_table_destroy((odph_table_t)tbl);
+ return NULL;
+ }
+ }
+
+ return (odph_table_t)tbl;
+}
+
+int
+odph_cuckoo_table_destroy(odph_table_t tbl) {
+ int ret, i, j;
+ odph_cuckoo_table_impl *impl = NULL;
+ char pool_name[ODPH_TABLE_NAME_LEN + 3];
+
+ if (tbl == NULL)
+ return -1;
+
+ impl = (odph_cuckoo_table_impl *)tbl;
+
+ /* check magic word */
+ if (impl->magicword != ODPH_CUCKOO_TABLE_MAGIC_WORD) {
+ ODPH_DBG("wrong magicword for cuckoo table\n");
+ return -1;
+ }
+
+ /* free all used buffers*/
+ for (i = 0; i < impl->num_buckets; i++) {
+ for (j = 0; j < HASH_BUCKET_ENTRIES; j++) {
+ if (impl->buckets[i].signatures[j].current
+ != NULL_SIGNATURE)
+ odp_buffer_free(impl-
buckets[i].key_buf[j]);
+ }
+ }
+
+ /* free all free buffers */
+ odp_event_t ev;
+
+ while ((ev = odp_queue_deq(impl->free_slots))
+ != ODP_EVENT_INVALID) {
+ odp_buffer_free(odp_buffer_from_event(ev));
+ }
+
+ /* destroy free_slots queue */
+ ret = odp_queue_destroy(impl->free_slots);
+ if (ret < 0)
+ ODPH_DBG("failed to destroy free_slots queue\n");
+
+ /* destroy key-value pool */
+ snprintf(pool_name, sizeof(pool_name), "kv_%s", impl->name);
+ ret = odp_pool_destroy(odp_pool_lookup(pool_name));
+ if (ret != 0) {
+ ODPH_DBG("failed to destroy key-value buffer pool\n");
+ return ret;
+ }
+
+ /* free impl */
+ odp_shm_free(odp_shm_lookup(impl->name));
+}
+
+static uint32_t hash(const odph_cuckoo_table_impl *h, const void *key)
+{
+ /* calc hash result by key */
+ return odp_hash_crc32c(key, h->key_len, 0); }
+
+/* Calc the secondary hash value from the primary hash value of a given
+key */ static inline uint32_t hash_secondary(const uint32_t
+primary_hash) {
+ static const unsigned all_bits_shift = 12;
+ static const unsigned alt_bits_xor = 0x5bd1e995;
+
+ uint32_t tag = primary_hash >> all_bits_shift;
+
+ return (primary_hash ^ ((tag + 1) * alt_bits_xor)); }
+
+/* Search for an entry that can be pushed to its alternative location
+*/ static inline int make_space_bucket(
+ const odph_cuckoo_table_impl *impl,
+ struct cuckoo_table_bucket *bkt)
+{
+ unsigned i, j;
+ int ret;
+ uint32_t next_bucket_idx;
+ struct cuckoo_table_bucket *next_bkt[HASH_BUCKET_ENTRIES];
+
+ /*
+ * Push existing item (search for bucket with space in
+ * alternative locations) to its alternative location
+ */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ /* Search for space in alternative locations */
+ next_bucket_idx = bkt->signatures[i].alt & impl-
bucket_bitmask;
+ next_bkt[i] = &impl->buckets[next_bucket_idx];
+ for (j = 0; j < HASH_BUCKET_ENTRIES; j++) {
+ if (next_bkt[i]->signatures[j].sig ==
NULL_SIGNATURE)
+ break;
+ }
+
+ if (j != HASH_BUCKET_ENTRIES)
+ break;
+ }
+
+ /* Alternative location has spare room (end of recursive function)
*/
+ if (i != HASH_BUCKET_ENTRIES) {
+ next_bkt[i]->signatures[j].alt =
bkt->signatures[i].current;
+ next_bkt[i]->signatures[j].current =
bkt->signatures[i].alt;
+ next_bkt[i]->key_buf[j] = bkt->key_buf[i];
+ return i;
+ }
+
+ /* Pick entry that has not been pushed yet */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++)
+ if (bkt->flag[i] == 0)
+ break;
+
+ /* All entries have been pushed, so entry cannot be added */
+ if (i == HASH_BUCKET_ENTRIES)
+ return -ENOSPC;
+
+ /* Set flag to indicate that this entry is going to be pushed */
+ bkt->flag[i] = 1;
+ /* Need room in alternative bucket to insert the pushed entry */
+ ret = make_space_bucket(impl, next_bkt[i]);
+ /*
+ * After recursive function.
+ * Clear flags and insert the pushed entry
+ * in its alternative location if successful,
+ * or return error
+ */
+ bkt->flag[i] = 0;
+ if (ret >= 0) {
+ next_bkt[i]->signatures[ret].alt =
bkt->signatures[i].current;
+ next_bkt[i]->signatures[ret].current =
bkt->signatures[i].alt;
+ next_bkt[i]->key_buf[ret] = bkt->key_buf[i];
+ return i;
+ }
+
+ return ret;
+}
+
+static inline int32_t
+cuckoo_table_add_key_with_hash(
+ const odph_cuckoo_table_impl *h, const void *key,
+ uint32_t sig, void *data)
+{
+ uint32_t alt_hash;
+ uint32_t prim_bucket_idx, sec_bucket_idx;
+ unsigned i;
+ struct cuckoo_table_bucket *prim_bkt, *sec_bkt;
+ struct cuckoo_table_key_value *new_kv, *kv;
+
+ odp_buffer_t new_buf;
+ int ret;
+
+ prim_bucket_idx = sig & h->bucket_bitmask;
+ prim_bkt = &h->buckets[prim_bucket_idx];
+ __builtin_prefetch((const void *)(uintptr_t)prim_bkt, 0, 3);
+
+ alt_hash = hash_secondary(sig);
+ sec_bucket_idx = alt_hash & h->bucket_bitmask;
+ sec_bkt = &h->buckets[sec_bucket_idx];
+ __builtin_prefetch((const void *)(uintptr_t)sec_bkt, 0, 3);
+
+ /* Get a new slot for storing the new key */
+ new_buf = odp_buffer_from_event(odp_queue_deq(h-
free_slots));
+ if (new_buf == ODP_BUFFER_INVALID)
+ return -ENOSPC;
+
+ /* Check if key is already inserted in primary location */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ if (
+ prim_bkt->signatures[i].current == sig &&
+ prim_bkt->signatures[i].alt == alt_hash) {
+ kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(
+ prim_bkt->key_buf[i]);
+ if (memcmp(key, kv->key, h->key_len) == 0) {
+ odp_queue_enq(
+ h->free_slots,
+
odp_buffer_to_event(new_buf));
+ /* Update data */
+ if (kv->value != NULL)
+ memcpy(kv->value, data, h-
value_len);
+
+ /* Return bucket index */
+ return prim_bucket_idx;
+ }
+ }
+ }
+
+ /* Check if key is already inserted in secondary location */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ if (
+ sec_bkt->signatures[i].alt == sig &&
+ sec_bkt->signatures[i].current == alt_hash) {
+ kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(
+ sec_bkt->key_buf[i]);
+ if (memcmp(key, kv->key, h->key_len) == 0) {
+ odp_queue_enq(
+ h->free_slots,
+
odp_buffer_to_event(new_buf));
+ /* Update data */
+ if (kv->value != NULL)
+ memcpy(kv->value, data, h-
value_len);
+
+ /* Return bucket index */
+ return sec_bucket_idx;
+ }
+ }
+ }
+
+ new_kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(new_buf);
+ __builtin_prefetch((const void *)(uintptr_t)new_kv, 0, 3);
+
+ /* Copy key and value.
+ * key-value mem block : struct cuckoo_table_key_value
+ * + key (key_len) + value (value_len)
+ */
+ new_kv->key = (uint8_t *)new_kv
+ + sizeof(struct
cuckoo_table_key_value);
+ memcpy(new_kv->key, key, h->key_len);
+
+ if (h->value_len > 0) {
+ new_kv->value = new_kv->key + h->key_len;
+ memcpy(new_kv->value, data, h->value_len);
+ } else {
+ new_kv->value = NULL;
+ }
+
+ /* Insert new entry is there is room in the primary bucket */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ /* Check if slot is available */
+ if (odp_likely(prim_bkt->signatures[i].sig ==
NULL_SIGNATURE)) {
+ prim_bkt->signatures[i].current = sig;
+ prim_bkt->signatures[i].alt = alt_hash;
+ prim_bkt->key_buf[i] = new_buf;
+ return prim_bucket_idx;
+ }
+ }
+
+ /* Primary bucket is full, so we need to make space for new entry
*/
+ ret = make_space_bucket(h, prim_bkt);
+
+ /*
+ * After recursive function.
+ * Insert the new entry in the position of the pushed entry
+ * if successful or return error and
+ * store the new slot back in the pool
+ */
+ if (ret >= 0) {
+ prim_bkt->signatures[ret].current = sig;
+ prim_bkt->signatures[ret].alt = alt_hash;
+ prim_bkt->key_buf[ret] = new_buf;
+ return prim_bucket_idx;
+ }
+
+ /* Error in addition, store new slot back in the free_slots */
+ odp_queue_enq(h->free_slots, odp_buffer_to_event(new_buf));
+ return ret;
+}
+
+int
+odph_cuckoo_table_put_value(odph_table_t tbl, void *key, void *value) {
+ if ((tbl == NULL) || (key == NULL))
+ return -EINVAL;
+
+ odph_cuckoo_table_impl *impl = (odph_cuckoo_table_impl *)tbl;
+ int ret = cuckoo_table_add_key_with_hash(
+ impl, key, hash(impl, key), value);
+
+ if (ret < 0)
+ return -1;
+
+ return 0;
+}
+
+static inline int32_t
+cuckoo_table_lookup_with_hash(
+ const odph_cuckoo_table_impl *h, const void *key,
+ uint32_t sig, void **data_ptr)
+{
+ uint32_t bucket_idx;
+ uint32_t alt_hash;
+ unsigned i;
+ struct cuckoo_table_bucket *bkt;
+ struct cuckoo_table_key_value *kv;
+
+ bucket_idx = sig & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in primary location */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ if (
+ bkt->signatures[i].current == sig &&
+ bkt->signatures[i].sig != NULL_SIGNATURE) {
+ kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(
+ bkt->key_buf[i]);
+ if (memcmp(key, kv->key, h->key_len) == 0) {
+ if (data_ptr != NULL)
+ *data_ptr = kv->value;
+ /*
+ * Return index where key is stored,
+ * subtracting the first dummy index
+ */
+ return bucket_idx;
+ }
+ }
+ }
+
+ /* Calculate secondary hash */
+ alt_hash = hash_secondary(sig);
+ bucket_idx = alt_hash & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in secondary location */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ if (
+ bkt->signatures[i].current == alt_hash &&
+ bkt->signatures[i].alt == sig) {
+ kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(
+ bkt->key_buf[i]);
+ if (memcmp(key, kv->key, h->key_len) == 0) {
+ if (data_ptr != NULL)
+ *data_ptr = kv->value;
+ /*
+ * Return index where key is stored,
+ * subtracting the first dummy index
+ */
+ return bucket_idx;
+ }
+ }
+ }
+
+ return -ENOENT;
+}
+
+int
+odph_cuckoo_table_get_value(
+ odph_table_t tbl, void *key, void *buffer, uint32_t
buffer_size) {
+ if ((tbl == NULL) || (key == NULL))
+ return -EINVAL;
+
+ odph_cuckoo_table_impl *impl = (odph_cuckoo_table_impl *)tbl;
+ void *tmp = NULL;
+ int ret;
+
+ ret = cuckoo_table_lookup_with_hash(impl, key, hash(impl, key),
&tmp);
+
+ if (ret < 0)
+ return -1;
+
+ if (impl->value_len > 0)
+ memcpy(buffer, tmp, impl->value_len);
+
+ return 0;
+}
+
+static inline int32_t
+cuckoo_table_del_key_with_hash(
+ const odph_cuckoo_table_impl *h,
+ const void *key, uint32_t sig)
+{
+ uint32_t bucket_idx;
+ uint32_t alt_hash;
+ unsigned i;
+ struct cuckoo_table_bucket *bkt;
+ struct cuckoo_table_key_value *kv;
+
+ bucket_idx = sig & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in primary location */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ if (
+ bkt->signatures[i].current == sig &&
+ bkt->signatures[i].sig != NULL_SIGNATURE) {
+ kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(
+ bkt->key_buf[i]);
+ if (memcmp(key, kv->key, h->key_len) == 0) {
+ bkt->signatures[i].sig = NULL_SIGNATURE;
+ odp_queue_enq(
+ h->free_slots,
+ odp_buffer_to_event(
+ bkt->key_buf[i]));
+ return bucket_idx;
+ }
+ }
+ }
+
+ /* Calculate secondary hash */
+ alt_hash = hash_secondary(sig);
+ bucket_idx = alt_hash & h->bucket_bitmask;
+ bkt = &h->buckets[bucket_idx];
+
+ /* Check if key is in secondary location */
+ for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
+ if (
+ bkt->signatures[i].current == alt_hash &&
+ bkt->signatures[i].sig != NULL_SIGNATURE) {
+ kv = (struct cuckoo_table_key_value
*)odp_buffer_addr(
+ bkt->key_buf[i]);
+ if (memcmp(key, kv->key, h->key_len) == 0) {
+ bkt->signatures[i].sig = NULL_SIGNATURE;
+ odp_queue_enq(
+ h->free_slots,
+ odp_buffer_to_event(
+ bkt->key_buf[i]));
+ return bucket_idx;
+ }
+ }
+ }
+
+ return -ENOENT;
+}
+
+int
+odph_cuckoo_table_remove_value(odph_table_t tbl, void *key) {
+ if ((tbl == NULL) || (key == NULL))
+ return -EINVAL;
+
+ odph_cuckoo_table_impl *impl = (odph_cuckoo_table_impl *)tbl;
+ int ret = cuckoo_table_del_key_with_hash(
+ impl, key, hash(impl, key));
+
+ if (ret < 0)
+ return -1;
+
+ return 0;
+}
+
+odph_table_ops_t odph_cuckoo_table_ops = {
+ odph_cuckoo_table_create,
+ odph_cuckoo_table_lookup,
+ odph_cuckoo_table_destroy,
+ odph_cuckoo_table_put_value,
+ odph_cuckoo_table_get_value,
+ odph_cuckoo_table_remove_value
+};
diff --git a/helper/odph_cuckootable.h b/helper/odph_cuckootable.h new
file mode 100644 index 0000000..1a06492
--- /dev/null
+++ b/helper/odph_cuckootable.h
@@ -0,0 +1,82 @@
+/* Copyright (c) 2016, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2016 Intel Corporation. All rights reserved.
+ * All rights reserved.
+ *
+ * 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 Intel Corporation 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 ODPH_CUCKOO_TABLE_H_
+#define ODPH_CUCKOO_TABLE_H_
+
+#include <odp/helper/table.h>
+
+/**
+ * @file
+ *
+ * ODP Cuckoo Hash Table
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+odph_table_t odph_cuckoo_table_create(
+ const char *name,
+ uint32_t capacity,
+ uint32_t key_size,
+ uint32_t value_size);
+
+odph_table_t odph_cuckoo_table_lookup(const char *name);
+
+int odph_cuckoo_table_destroy(odph_table_t table);
+
+int odph_cuckoo_table_put_value(
+ odph_table_t table,
+ void *key, void *value);
+
+int odph_cuckoo_table_get_value(
+ odph_table_t table,
+ void *key, void *buffer,
+ uint32_t buffer_size);
+
+int odph_cuckoo_table_remove_value(odph_table_t table, void *key);
+
+extern odph_table_ops_t odph_cuckoo_table_ops;
