Please ignore this patch, it contains a silly mistake on hash.h
which modifies its comments causing a typo.
sorry.
> 在 2015年11月26日，上午10:20，Peng <xnhp0...@icloud.com> 写道：
>
> Signed-off-by: Peng <xnhp0...@icloud.com>
> ---
> helper/Makefile.am | 2 +
> helper/cuckoo_hash.c | 1117 +++++++++++++++++++++++++++++++
> helper/include/odp/helper/cuckoo_hash.h | 435 ++++++++++++
> helper/include/odp/helper/ring.h | 43 ++
> helper/ring.c | 28 +
> helper/test/Makefile.am | 4 +-
> helper/test/odp_cuckoo_hash.c | 779 +++++++++++++++++++++
> include/odp/api/hash.h | 16 +-
> 8 files changed, 2422 insertions(+), 2 deletions(-)
> create mode 100644 helper/cuckoo_hash.c
> create mode 100644 helper/include/odp/helper/cuckoo_hash.h
> create mode 100644 helper/test/odp_cuckoo_hash.c
>
> diff --git a/helper/Makefile.am b/helper/Makefile.am
> index e72507e..e923aa8 100644
> --- a/helper/Makefile.am
> +++ b/helper/Makefile.am
> @@ -18,6 +18,7 @@ helperinclude_HEADERS = \
> $(srcdir)/include/odp/helper/ipsec.h\
> $(srcdir)/include/odp/helper/tcp.h\
> $(srcdir)/include/odp/helper/table.h\
> + $(srcdir)/include/odp/helper/cuckoo_hash.h\
> $(srcdir)/include/odp/helper/udp.h
>
> noinst_HEADERS = \
> @@ -30,6 +31,7 @@ noinst_HEADERS = \
> __LIB__libodphelper_la_SOURCES = \
> linux.c \
> ring.c \
> + cuckoo_hash.c \
> hashtable.c \
> lineartable.c
>
> diff --git a/helper/cuckoo_hash.c b/helper/cuckoo_hash.c
> new file mode 100644
> index 0000000..4a4b56b
> --- /dev/null
> +++ b/helper/cuckoo_hash.c
> @@ -0,0 +1,1117 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/*-
> + * BSD LICENSE
> + *
> + * Copyright(c) 2010-2015 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 <stdarg.h>
> +#include <sys/queue.h>
> +
> +#include <odp/helper/cuckoo_hash.h>
> +#include <odp/shared_memory.h>
> +#include <odp/spinlock.h>
> +#include <odp/align.h>
> +#include <odp/api/errno.h>
> +#include <odp/rwlock.h>
> +#include <odp/hints.h>
> +#include <odp/helper/ring.h>
> +#include "odph_debug.h"
> +
> +/* Macro to enable/disable run-time checking of function parameters */
> +#define RETURN_IF_TRUE(cond, retval) do { \
> + if (cond) \
> + return retval; \
> +} while (0)
> +
> +/* Hash function used if none is specified */
> +#include <odp/hash.h>
> +
> +/** 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
> +
> +/** Maximum number of keys that can be
> + * searched for using odph_hash_lookup_bulk. */
> +#define HASH_LOOKUP_BULK_MAX 64
> +#define HASH_LOOKUP_MULTI_MAX HASH_LOOKUP_BULK_MAX
> +
> +/* Structure storing both primary and secondary hashes */
> +struct cuckoo_hash_signatures {
> + union {
> + struct {
> + uint32_t current;
> + uint32_t alt;
> + };
> + uint64_t sig;
> + };
> +};
> +
> +/* Structure that stores key-value pair */
> +struct cuckoo_hash_key {
> + union {
> + uintptr_t idata;
> + void *pdata;
> + };
> + /* Variable key size */
> + char key[0];
> +} ODP_ALIGNED(KEY_ALIGNMENT);
> +
> +/** Bucket structure */
> +struct cuckoo_hash_bucket {
> + struct cuckoo_hash_signatures signatures[HASH_BUCKET_ENTRIES];
> + /* Includes dummy key index that always contains index 0 */
> + uint32_t key_idx[HASH_BUCKET_ENTRIES + 1];
> + uint8_t flag[HASH_BUCKET_ENTRIES];
> +} 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_cuckoo_hash_tbl_t *
> +odph_cuckoo_hash_find_existing(const char *name)
> +{
> + odph_cuckoo_hash_tbl_t *h = NULL;
> + odp_shm_t shm = odp_shm_lookup(name);
> +
> + if (shm == ODP_SHM_INVALID)
> + return NULL;
> +
> + h = (odph_cuckoo_hash_tbl_t *)odp_shm_addr(shm);
> + return h;
> +}
> +
> +int
> +odph_cuckoo_hash_create(odph_cuckoo_hash_tbl_t **ht,
> + const odph_cuckoo_hash_param_t *params)
> +{
> + odph_cuckoo_hash_tbl_t *h;
> + odph_ring_t *r = NULL;
> + odp_shm_t shm_h, shm_b, shm_k;
> +
> + char bucket_name[ODPH_CUCKOO_HASH_NAMESIZE + 2],
> + key_name[ODPH_CUCKOO_HASH_NAMESIZE + 2];
> +
> + void *ptr, *k = NULL;
> + void *buckets = NULL;
> + char ring_name[ODPH_RING_NAMESIZE];
> + unsigned i;
> +
> + if (params == NULL) {
> + ODPH_ERR("no parameters\n");
> + *ht = NULL;
> + return -EINVAL;
> + }
> +
> + /* Check for valid parameters */
> + if (
> + (params->entries > HASH_ENTRIES_MAX) ||
> + (params->entries < HASH_BUCKET_ENTRIES) ||
> + (params->key_len == 0) ||
> + (strlen(params->name) == 0)) {
> + ODPH_ERR("invalid parameters\n");
> + *ht = NULL;
> + return -EINVAL;
> + }
> +
> + /* Guarantee there's no existing */
> + h = odph_cuckoo_hash_find_existing(params->name);
> + if (h != NULL) {
> + ODPH_ERR("cuckoo hash table %s already exists\n", params->name);
> + *ht = h;
> + return -EEXIST;
> + }
> +
> + shm_h = odp_shm_reserve(
> + params->name, sizeof(odph_cuckoo_hash_tbl_t),
> + ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY);
> +
> + if (shm_h == ODP_SHM_INVALID) {
> + ODPH_ERR("shm allocation failed for odph_cuckoo_hash_tbl %s\n",
> + params->name);
> + *ht = NULL;
> + return -ENOMEM;
> + }
> + h = odp_shm_addr(shm_h);
> +
> + snprintf(bucket_name, sizeof(bucket_name), "B_%s", params->name);
> + const uint32_t num_buckets =
> + align32pow2(params->entries) / HASH_BUCKET_ENTRIES;
> +
> + shm_b = odp_shm_reserve(
> + bucket_name,
> + num_buckets * sizeof(struct cuckoo_hash_bucket),
> + ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY);
> +
> + if (shm_b == ODP_SHM_INVALID) {
> + ODPH_ERR("shm allocation failed for cuckoo_hash_bucket\n");
> + odp_shm_free(shm_h);
> + *ht = NULL;
> + return -ENOMEM;
> + }
> +
> + buckets = odp_shm_addr(shm_b);
> +
> + snprintf(key_name, sizeof(key_name), "K_%s", params->name);
> + const uint32_t key_entry_size =
> + sizeof(struct cuckoo_hash_key) + params->key_len;
> + /* Store all keys and leave the first entry
> + as a dummy entry for lookup_bulk */
> + const uint64_t key_tbl_size = key_entry_size * (params->entries + 1);
> +
> + shm_k = odp_shm_reserve(key_name, key_tbl_size, ODP_CACHE_LINE_SIZE,
> + ODP_SHM_SW_ONLY);
> + if (shm_k == ODP_SHM_INVALID) {
> + ODPH_ERR("shm allocation failed for key_store\n");
> + odp_shm_free(shm_b);
> + odp_shm_free(shm_h);
> + *ht = NULL;
> + return -ENOMEM;
> + }
> + k = odp_shm_addr(shm_k);
> +
> + snprintf(ring_name, sizeof(ring_name), "RI_%s", params->name);
> + r = odph_ring_lookup(ring_name);
> + if (r != NULL) {
> + /* clear the free ring */
> + while (odph_ring_sc_dequeue(r, ptr) == 0) {
> + /* empty */
> + }
> + } else {
> + r = odph_ring_create(ring_name,
> + align32pow2(params->entries + 1), 0);
> + }
> +
> + if (r == NULL) {
> + odp_shm_free(shm_k);
> + odp_shm_free(shm_b);
> + odp_shm_free(shm_h);
> + *ht = NULL;
> + return -ENOMEM;
> + }
> +
> + /* Setup hash context */
> + snprintf(h->name, sizeof(h->name), "%s", params->name);
> + h->entries = params->entries;
> + h->key_len = params->key_len;
> + h->key_entry_size = key_entry_size;
> + h->hash_func_init_val = params->hash_func_init_val;
> + h->hash_cmp_eq = memcmp;
> +
> + h->num_buckets = num_buckets;
> + h->bucket_bitmask = h->num_buckets - 1;
> + h->buckets = buckets;
> +
> + /*default hash function is CRC 32*/
> + h->hash_func = (params->hash_func == NULL) ?
> + odp_hash_crc32c : params->hash_func;
> +
> + h->key_store = k;
> + h->free_slots = r;
> +
> + h->shm_bucket = shm_b;
> + h->shm_key = shm_k;
> +
> + /* populate the free slots ring.
> + * Entry zero is reserved for key misses
> + */
> + for (i = 1; i < params->entries + 1; i++)
> + odph_ring_sp_enqueue(r, (void *)((uintptr_t)i));
> + *ht = h;
> + return 0;
> +}
> +
> +void
> +odph_cuckoo_hash_destroy(odph_cuckoo_hash_tbl_t *h)
> +{
> + if (h == NULL)
> + return;
> +
> + odph_ring_free(h->free_slots);
> + odp_shm_free(h->shm_key);
> + odp_shm_free(h->shm_bucket);
> + odp_shm_free(odp_shm_lookup(h->name));
> +}
> +
> +static uint32_t hash(const odph_cuckoo_hash_tbl_t *h, const void *key)
> +{
> + /* calc hash result by key */
> + return h->hash_func(key, h->key_len, h->hash_func_init_val);
> +}
> +
> +/* 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));
> +}
> +
> +void
> +odph_cuckoo_hash_reset(odph_cuckoo_hash_tbl_t *h)
> +{
> + void *ptr;
> + unsigned i;
> +
> + if (h == NULL)
> + return;
> +
> + memset(h->buckets, 0,
> + h->num_buckets * sizeof(struct cuckoo_hash_bucket));
> + memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
> +
> + /* clear the free ring */
> + while (odph_ring_sc_dequeue(h->free_slots, ptr) == 0) {
> + /* empty */
> + }
> +
> + /* Repopulate the free slots ring.
> + * Entry zero is reserved for key misses */
> + for (i = 1; i < h->entries + 1; i++)
> + odph_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)i));
> +}
> +
> +/* Search for an entry that can be pushed to its alternative location */
> +static inline int
> +make_space_bucket(const odph_cuckoo_hash_tbl_t *h,
> + struct cuckoo_hash_bucket *bkt)
> +{
> + unsigned i, j;
> + int ret;
> + uint32_t next_bucket_idx;
> + struct cuckoo_hash_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 & h->bucket_bitmask;
> + next_bkt[i] = &h->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_idx[j] = bkt->key_idx[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(h, 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_idx[ret] = bkt->key_idx[i];
> + return i;
> + }
> +
> + return ret;
> +}
> +
> +static inline int32_t
> +cuckoo_hash_add_key_with_hash(
> + const odph_cuckoo_hash_tbl_t *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_hash_bucket *prim_bkt, *sec_bkt;
> + struct cuckoo_hash_key *new_k, *k, *keys = h->key_store;
> + void *slot_id;
> + uint32_t new_idx;
> + 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 */
> + if (odph_ring_sc_dequeue_bulk(h->free_slots, &slot_id, 1) != 0)
> + return -ENOSPC;
> + new_k = (void *)((uintptr_t)(keys)
> + + ((uintptr_t)slot_id * h->key_entry_size));
> + __builtin_prefetch((const void *)(uintptr_t)new_k, 0, 3);
> + new_idx = (uint32_t)((uintptr_t)slot_id);
> +
> + /* Check if key is already inseodpd 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) {
> + k = (struct cuckoo_hash_key *)((char *)keys +
> + prim_bkt->key_idx[i] * h->key_entry_size);
> + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) {
> + odph_ring_sp_enqueue(h->free_slots, slot_id);
> + /* Update data */
> + k->pdata = data;
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + return (prim_bkt->key_idx[i] - 1);
> + }
> + }
> + }
> +
> + /* Check if key is already inseodpd 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) {
> + k = (struct cuckoo_hash_key *)((char *)keys +
> + sec_bkt->key_idx[i] * h->key_entry_size);
> + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) {
> + odph_ring_sp_enqueue(h->free_slots, slot_id);
> + /* Update data */
> + k->pdata = data;
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + return (sec_bkt->key_idx[i] - 1);
> + }
> + }
> + }
> +
> + /* Copy key */
> + memcpy(new_k->key, key, h->key_len);
> + new_k->pdata = data;
> +
> + /* 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_idx[i] = new_idx;
> + return new_idx - 1;
> + }
> + }
> +
> + /* 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 ring
> + */
> + if (ret >= 0) {
> + prim_bkt->signatures[ret].current = sig;
> + prim_bkt->signatures[ret].alt = alt_hash;
> + prim_bkt->key_idx[ret] = new_idx;
> + return (new_idx - 1);
> + }
> +
> + /* Error in addition, store new slot back in the ring */
> + odph_ring_sp_enqueue(
> + h->free_slots, (void *)((uintptr_t)new_idx));
> + return ret;
> +}
> +
> +int32_t
> +odph_cuckoo_hash_add_key_with_hash(
> + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_add_key_with_hash(h, key, sig, 0);
> +}
> +
> +int32_t
> +odph_cuckoo_hash_add_key(const odph_cuckoo_hash_tbl_t *h, const void *key)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_add_key_with_hash(
> + h, key, hash(h, key), 0);
> +}
> +
> +int
> +odph_cuckoo_hash_add_key_with_hash_data(
> + const odph_cuckoo_hash_tbl_t *h,
> + const void *key, uint32_t sig, void *data)
> +{
> + int ret;
> +
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + ret = cuckoo_hash_add_key_with_hash(h, key, sig, data);
> + if (ret >= 0)
> + return 0;
> + return ret;
> +}
> +
> +int
> +odph_cuckoo_hash_add_key_data(const odph_cuckoo_hash_tbl_t *h,
> + const void *key, void *data)
> +{
> + int ret;
> +
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> +
> + ret = cuckoo_hash_add_key_with_hash(
> + h, key, hash(h, key), data);
> + if (ret >= 0)
> + return 0;
> + return ret;
> +}
> +
> +static inline int32_t
> +cuckoo_hash_lookup_with_hash(
> + const odph_cuckoo_hash_tbl_t *h, const void *key,
> + uint32_t sig, void **data)
> +{
> + uint32_t bucket_idx;
> + uint32_t alt_hash;
> + unsigned i;
> + struct cuckoo_hash_bucket *bkt;
> + struct cuckoo_hash_key *k, *keys = h->key_store;
> +
> + 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) {
> + k = (void *)((uintptr_t)keys +
> + (bkt->key_idx[i] * h->key_entry_size));
> + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) {
> + if (data != NULL)
> + *data = k->pdata;
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + return (bkt->key_idx[i] - 1);
> + }
> + }
> + }
> +
> + /* 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) {
> + k = (struct cuckoo_hash_key *)((char *)keys +
> + bkt->key_idx[i] * h->key_entry_size);
> + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) {
> + if (data != NULL)
> + *data = k->pdata;
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + return (bkt->key_idx[i] - 1);
> + }
> + }
> + }
> +
> + return -ENOENT;
> +}
> +
> +int32_t
> +odph_cuckoo_hash_lookup_with_hash(
> + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_lookup_with_hash(h, key, sig, NULL);
> +}
> +
> +int32_t
> +odph_cuckoo_hash_lookup(const odph_cuckoo_hash_tbl_t *h, const void *key)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_lookup_with_hash(
> + h, key, hash(h, key), NULL);
> +}
> +
> +int
> +odph_cuckoo_hash_lookup_with_hash_data(
> + const odph_cuckoo_hash_tbl_t *h,
> + const void *key, uint32_t sig, void **data)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_lookup_with_hash(h, key, sig, data);
> +}
> +
> +int
> +odph_cuckoo_hash_lookup_data(
> + const odph_cuckoo_hash_tbl_t *h,
> + const void *key, void **data)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_lookup_with_hash(
> + h, key, hash(h, key), data);
> +}
> +
> +static inline int32_t
> +cuckoo_hash_del_key_with_hash(
> + const odph_cuckoo_hash_tbl_t *h,
> + const void *key, uint32_t sig)
> +{
> + uint32_t bucket_idx;
> + uint32_t alt_hash;
> + unsigned i;
> + struct cuckoo_hash_bucket *bkt;
> + struct cuckoo_hash_key *k, *keys = h->key_store;
> +
> + 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) {
> + k = (struct cuckoo_hash_key *)((char *)keys +
> + bkt->key_idx[i] * h->key_entry_size);
> + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) {
> + bkt->signatures[i].sig = NULL_SIGNATURE;
> + odph_ring_sp_enqueue(
> + h->free_slots,
> + (void *)((uintptr_t)bkt->key_idx[i]));
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + return (bkt->key_idx[i] - 1);
> + }
> + }
> + }
> +
> + /* 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) {
> + k = (struct cuckoo_hash_key *)((char *)keys +
> + bkt->key_idx[i] * h->key_entry_size);
> + if (h->hash_cmp_eq(key, k->key, h->key_len) == 0) {
> + bkt->signatures[i].sig = NULL_SIGNATURE;
> + odph_ring_sp_enqueue(
> + h->free_slots,
> + (void *)((uintptr_t)bkt->key_idx[i]));
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + return (bkt->key_idx[i] - 1);
> + }
> + }
> + }
> +
> + return -ENOENT;
> +}
> +
> +int32_t
> +odph_cuckoo_hash_del_key_with_hash(
> + const odph_cuckoo_hash_tbl_t *h,
> + const void *key, uint32_t sig)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_del_key_with_hash(h, key, sig);
> +}
> +
> +int32_t
> +odph_cuckoo_hash_del_key(const odph_cuckoo_hash_tbl_t *h, const void *key)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> + return cuckoo_hash_del_key_with_hash(
> + h, key, hash(h, key));
> +}
> +
> +/* Lookup bulk stage 0: Prefetch input key */
> +static inline void
> +lookup_stage0(
> + unsigned *idx, uint64_t *lookup_mask,
> + const void * const *keys)
> +{
> + *idx = __builtin_ctzl(*lookup_mask);
> + if (*lookup_mask == 0)
> + *idx = 0;
> +
> + __builtin_prefetch((const void *)(uintptr_t)(keys[*idx]), 0, 3);
> + *lookup_mask &= ~(1llu << *idx);
> +}
> +
> +/*
> + * Lookup bulk stage 1: Calculate primary/secondary hashes
> + * and prefetch primary/secondary buckets
> + */
> +static inline void
> +lookup_stage1(
> + unsigned idx, uint32_t *prim_hash, uint32_t *sec_hash,
> + const struct cuckoo_hash_bucket **primary_bkt,
> + const struct cuckoo_hash_bucket **secondary_bkt,
> + uint32_t *hash_vals, const void * const *keys,
> + const odph_cuckoo_hash_tbl_t *h)
> +{
> + *prim_hash = hash(h, keys[idx]);
> + hash_vals[idx] = *prim_hash;
> + *sec_hash = hash_secondary(*prim_hash);
> +
> + *primary_bkt = &h->buckets[*prim_hash & h->bucket_bitmask];
> + *secondary_bkt = &h->buckets[*sec_hash & h->bucket_bitmask];
> +
> + __builtin_prefetch((const void *)(uintptr_t)(*primary_bkt), 0, 3);
> + __builtin_prefetch((const void *)(uintptr_t)(*secondary_bkt), 0, 3);
> +}
> +
> +/*
> + * Lookup bulk stage 2: Search for match hashes in primary/secondary
> locations
> + * and prefetch first key slot
> + */
> +static inline void
> +lookup_stage2(
> + unsigned idx, uint32_t prim_hash, uint32_t sec_hash,
> + const struct cuckoo_hash_bucket *prim_bkt,
> + const struct cuckoo_hash_bucket *sec_bkt,
> + const struct cuckoo_hash_key **key_slot, int32_t *positions,
> + uint64_t *extra_hits_mask, const void *keys,
> + const odph_cuckoo_hash_tbl_t *h)
> +{
> + unsigned prim_hash_matches, sec_hash_matches, key_idx, i;
> + unsigned total_hash_matches;
> +
> + prim_hash_matches = 1 << HASH_BUCKET_ENTRIES;
> + sec_hash_matches = 1 << HASH_BUCKET_ENTRIES;
> + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) {
> + prim_hash_matches |=
> + ((prim_hash == prim_bkt->signatures[i].current) << i);
> + sec_hash_matches |=
> + ((sec_hash == sec_bkt->signatures[i].current) << i);
> + }
> +
> + key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];
> + if (key_idx == 0)
> + key_idx = sec_bkt->key_idx[__builtin_ctzl(sec_hash_matches)];
> +
> + total_hash_matches = (prim_hash_matches |
> + (sec_hash_matches <<
> + (HASH_BUCKET_ENTRIES + 1)));
> + *key_slot = (const struct cuckoo_hash_key *)((const char *)keys +
> + key_idx * h->key_entry_size);
> +
> + __builtin_prefetch((const void *)(uintptr_t)(*key_slot), 0, 3);
> + /*
> + * Return index where key is stored,
> + * substracting the first dummy index
> + */
> + positions[idx] = (key_idx - 1);
> +
> + *extra_hits_mask |= (uint64_t)
> + (__builtin_popcount(total_hash_matches) > 3) << idx;
> +}
> +
> +/* Lookup bulk stage 3: Check if key matches, update hit mask and return
> data */
> +static inline void
> +lookup_stage3(
> + unsigned idx, const struct cuckoo_hash_key *key_slot,
> + const void * const *keys,
> + void *data[], uint64_t *hits, const odph_cuckoo_hash_tbl_t *h)
> +{
> + unsigned hit;
> +
> + hit = !h->hash_cmp_eq(key_slot->key, keys[idx], h->key_len);
> + if (data != NULL)
> + data[idx] = key_slot->pdata;
> +
> + *hits |= (uint64_t)(hit) << idx;
> +}
> +
> +static inline void
> +cuckoo_hash_lookup_bulk(
> + const odph_cuckoo_hash_tbl_t *h, const void **keys,
> + uint32_t num_keys, int32_t *positions,
> + uint64_t *hit_mask, void *data[])
> +{
> + uint64_t hits = 0;
> + uint64_t extra_hits_mask = 0;
> + uint64_t lookup_mask, miss_mask;
> + unsigned idx;
> + const void *key_store = h->key_store;
> + int ret;
> + uint32_t hash_vals[HASH_LOOKUP_BULK_MAX];
> +
> + unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
> + const struct cuckoo_hash_bucket *primary_bkt10, *primary_bkt11;
> + const struct cuckoo_hash_bucket *secondary_bkt10, *secondary_bkt11;
> + const struct cuckoo_hash_bucket *primary_bkt20, *primary_bkt21;
> + const struct cuckoo_hash_bucket *secondary_bkt20, *secondary_bkt21;
> + const struct cuckoo_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
> + uint32_t primary_hash10, primary_hash11;
> + uint32_t secondary_hash10, secondary_hash11;
> + uint32_t primary_hash20, primary_hash21;
> + uint32_t secondary_hash20, secondary_hash21;
> +
> + lookup_mask = (uint64_t)-1 >> (64 - num_keys);
> + miss_mask = lookup_mask;
> +
> + lookup_stage0(&idx00, &lookup_mask, keys);
> + lookup_stage0(&idx01, &lookup_mask, keys);
> +
> + idx10 = idx00, idx11 = idx01;
> +
> + lookup_stage0(&idx00, &lookup_mask, keys);
> + lookup_stage0(&idx01, &lookup_mask, keys);
> + lookup_stage1(
> + idx10, &primary_hash10, &secondary_hash10,
> + &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
> + lookup_stage1(
> + idx11, &primary_hash11, &secondary_hash11,
> + &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
> +
> + primary_bkt20 = primary_bkt10;
> + primary_bkt21 = primary_bkt11;
> + secondary_bkt20 = secondary_bkt10;
> + secondary_bkt21 = secondary_bkt11;
> + primary_hash20 = primary_hash10;
> + primary_hash21 = primary_hash11;
> + secondary_hash20 = secondary_hash10;
> + secondary_hash21 = secondary_hash11;
> + idx20 = idx10, idx21 = idx11;
> + idx10 = idx00, idx11 = idx01;
> +
> + lookup_stage0(&idx00, &lookup_mask, keys);
> + lookup_stage0(&idx01, &lookup_mask, keys);
> + lookup_stage1(
> + idx10, &primary_hash10, &secondary_hash10,
> + &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
> + lookup_stage1(
> + idx11, &primary_hash11, &secondary_hash11,
> + &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
> + lookup_stage2(
> + idx20, primary_hash20, secondary_hash20, primary_bkt20,
> + secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
> + key_store, h);
> + lookup_stage2(
> + idx21, primary_hash21, secondary_hash21, primary_bkt21,
> + secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
> + key_store, h);
> +
> + while (lookup_mask) {
> + k_slot30 = k_slot20, k_slot31 = k_slot21;
> + idx30 = idx20, idx31 = idx21;
> + primary_bkt20 = primary_bkt10;
> + primary_bkt21 = primary_bkt11;
> + secondary_bkt20 = secondary_bkt10;
> + secondary_bkt21 = secondary_bkt11;
> + primary_hash20 = primary_hash10;
> + primary_hash21 = primary_hash11;
> + secondary_hash20 = secondary_hash10;
> + secondary_hash21 = secondary_hash11;
> + idx20 = idx10, idx21 = idx11;
> + idx10 = idx00, idx11 = idx01;
> +
> + lookup_stage0(&idx00, &lookup_mask, keys);
> + lookup_stage0(&idx01, &lookup_mask, keys);
> + lookup_stage1(
> + idx10, &primary_hash10, &secondary_hash10,
> + &primary_bkt10, &secondary_bkt10, hash_vals,
> + keys, h);
> + lookup_stage1(
> + idx11, &primary_hash11, &secondary_hash11,
> + &primary_bkt11, &secondary_bkt11, hash_vals,
> + keys, h);
> + lookup_stage2(
> + idx20, primary_hash20, secondary_hash20,
> + primary_bkt20, secondary_bkt20, &k_slot20,
> + positions, &extra_hits_mask, key_store, h);
> + lookup_stage2(
> + idx21, primary_hash21, secondary_hash21,
> + primary_bkt21, secondary_bkt21, &k_slot21,
> + positions, &extra_hits_mask, key_store, h);
> + lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
> + lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
> + }
> +
> + k_slot30 = k_slot20, k_slot31 = k_slot21;
> + idx30 = idx20, idx31 = idx21;
> + primary_bkt20 = primary_bkt10;
> + primary_bkt21 = primary_bkt11;
> + secondary_bkt20 = secondary_bkt10;
> + secondary_bkt21 = secondary_bkt11;
> + primary_hash20 = primary_hash10;
> + primary_hash21 = primary_hash11;
> + secondary_hash20 = secondary_hash10;
> + secondary_hash21 = secondary_hash11;
> + idx20 = idx10, idx21 = idx11;
> + idx10 = idx00, idx11 = idx01;
> +
> + lookup_stage1(
> + idx10, &primary_hash10, &secondary_hash10,
> + &primary_bkt10, &secondary_bkt10, hash_vals, keys, h);
> + lookup_stage1(
> + idx11, &primary_hash11, &secondary_hash11,
> + &primary_bkt11, &secondary_bkt11, hash_vals, keys, h);
> + lookup_stage2(
> + idx20, primary_hash20, secondary_hash20, primary_bkt20,
> + secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
> + key_store, h);
> + lookup_stage2(
> + idx21, primary_hash21, secondary_hash21, primary_bkt21,
> + secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
> + key_store, h);
> + lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
> + lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
> +
> + k_slot30 = k_slot20, k_slot31 = k_slot21;
> + idx30 = idx20, idx31 = idx21;
> + primary_bkt20 = primary_bkt10;
> + primary_bkt21 = primary_bkt11;
> + secondary_bkt20 = secondary_bkt10;
> + secondary_bkt21 = secondary_bkt11;
> + primary_hash20 = primary_hash10;
> + primary_hash21 = primary_hash11;
> + secondary_hash20 = secondary_hash10;
> + secondary_hash21 = secondary_hash11;
> + idx20 = idx10, idx21 = idx11;
> +
> + lookup_stage2(
> + idx20, primary_hash20, secondary_hash20, primary_bkt20,
> + secondary_bkt20, &k_slot20, positions, &extra_hits_mask,
> + key_store, h);
> + lookup_stage2(
> + idx21, primary_hash21, secondary_hash21, primary_bkt21,
> + secondary_bkt21, &k_slot21, positions, &extra_hits_mask,
> + key_store, h);
> + lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
> + lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
> +
> + k_slot30 = k_slot20, k_slot31 = k_slot21;
> + idx30 = idx20, idx31 = idx21;
> +
> + lookup_stage3(idx30, k_slot30, keys, data, &hits, h);
> + lookup_stage3(idx31, k_slot31, keys, data, &hits, h);
> +
> + /* ignore any items we have already found */
> + extra_hits_mask &= ~hits;
> +
> + if (odp_unlikely(extra_hits_mask)) {
> + /* run a single search for each remaining item */
> + do {
> + idx = __builtin_ctzl(extra_hits_mask);
> + if (data != NULL) {
> + ret = odph_cuckoo_hash_lookup_with_hash_data(
> + h, keys[idx], hash_vals[idx],
> + &data[idx]);
> + if (ret >= 0)
> + hits |= 1ULL << idx;
> + } else {
> + positions[idx] =
> + odph_cuckoo_hash_lookup_with_hash(
> + h, keys[idx], hash_vals[idx]);
> + if (positions[idx] >= 0)
> + hits |= 1llu << idx;
> + }
> + extra_hits_mask &= ~(1llu << idx);
> + } while (extra_hits_mask);
> + }
> +
> + miss_mask &= ~hits;
> + if (odp_unlikely(miss_mask)) {
> + do {
> + idx = __builtin_ctzl(miss_mask);
> + positions[idx] = -ENOENT;
> + miss_mask &= ~(1llu << idx);
> + } while (miss_mask);
> + }
> +
> + if (hit_mask != NULL)
> + *hit_mask = hits;
> +}
> +
> +int
> +odph_cuckoo_hash_lookup_bulk(
> + const odph_cuckoo_hash_tbl_t *h, const void **keys,
> + uint32_t num_keys, int32_t *positions)
> +{
> + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
> + (num_keys > HASH_LOOKUP_BULK_MAX) ||
> + (positions == NULL)), -EINVAL);
> +
> + cuckoo_hash_lookup_bulk(
> + h, keys, num_keys, positions, NULL, NULL);
> + return 0;
> +}
> +
> +int
> +odph_cuckoo_hash_lookup_bulk_data(
> + const odph_cuckoo_hash_tbl_t *h, const void **keys,
> + uint32_t num_keys, uint64_t *hit_mask, void *data[])
> +{
> + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
> + (num_keys > HASH_LOOKUP_BULK_MAX) ||
> + (hit_mask == NULL)), -EINVAL);
> +
> + int32_t positions[num_keys];
> +
> + cuckoo_hash_lookup_bulk(
> + h, keys, num_keys, positions, hit_mask, data);
> +
> + /* Return number of hits */
> + return __builtin_popcountl(*hit_mask);
> +}
> +
> +int32_t
> +odph_cuckoo_hash_iterate(
> + const odph_cuckoo_hash_tbl_t *h, const void **key,
> + void **data, uint32_t *next)
> +{
> + uint32_t bucket_idx, idx, position;
> + struct cuckoo_hash_key *next_key;
> +
> + RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
> +
> + const uint32_t total_entries =
> + h->num_buckets * HASH_BUCKET_ENTRIES;
> + /* Out of bounds */
> + if (*next >= total_entries)
> + return -ENOENT;
> +
> + /* Calculate bucket and index of current iterator */
> + bucket_idx = *next / HASH_BUCKET_ENTRIES;
> + idx = *next % HASH_BUCKET_ENTRIES;
> +
> + /* If current position is empty, go to the next one */
> + while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) {
> + (*next)++;
> + /* End of table */
> + if (*next == total_entries)
> + return -ENOENT;
> + bucket_idx = *next / HASH_BUCKET_ENTRIES;
> + idx = *next % HASH_BUCKET_ENTRIES;
> + }
> +
> + /* Get position of entry in key table */
> + position = h->buckets[bucket_idx].key_idx[idx];
> + next_key = (struct cuckoo_hash_key *)((char *)h->key_store +
> + position * h->key_entry_size);
> + /* Return key and data */
> + *key = next_key->key;
> + *data = next_key->pdata;
> +
> + /* Increment iterator */
> + (*next)++;
> +
> + return (position - 1);
> +}
> diff --git a/helper/include/odp/helper/cuckoo_hash.h
> b/helper/include/odp/helper/cuckoo_hash.h
> new file mode 100644
> index 0000000..f21b8a2
> --- /dev/null
> +++ b/helper/include/odp/helper/cuckoo_hash.h
> @@ -0,0 +1,435 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/*-
> + * BSD LICENSE
> + *
> + * Copyright(c) 2010-2015 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_HASH_H_
> +#define ODPH_CUCKOO_HASH_H_
> +
> +#include <odp/shared_memory.h>
> +#include <odp/helper/ring.h>
> +#include <odp/hash.h>
> +#include <stdint.h>
> +
> +/**
> + * @file
> + *
> + * ODP Cuckoo Hash Table Implementation
> + */
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +/** Maximum number of characters in hash name.*/
> +#define ODPH_CUCKOO_HASH_NAMESIZE 32
> +
> +/** A hash table structure. */
> +typedef struct odph_cuckoo_hash_tbl {
> + /**< Name of the hash. */
> + char name[ODPH_CUCKOO_HASH_NAMESIZE];
> + /**< Total table entries. */
> + uint32_t entries;
> + /**< Number of buckets in table. */
> + uint32_t num_buckets;
> + /**< Length of hash key. */
> + uint32_t key_len;
> + /**< Function used to calculate hash. */
> + odp_hash_function hash_func;
> + /**< Init value used by hash_func. */
> + uint32_t hash_func_init_val;
> + /**< Function used to compare keys. */
> + odp_hash_cmp_eq_t hash_cmp_eq;
> + /**< Bitmask for getting bucket index from hash signature. */
> + uint32_t bucket_bitmask;
> + /**< Size of each key entry. */
> + uint32_t key_entry_size;
> + /**< Ring that stores all indexes of the free slots in the key table */
> + odph_ring_t *free_slots;
> + /**< Table storing all keys and data */
> + void *key_store;
> + /** Table with buckets storing all the hash values and key indexes
> + to the key table*/
> + struct cuckoo_hash_bucket *buckets;
> + /** memory used to store keys*/
> + odp_shm_t shm_key;
> + /** memory used to store buckets*/
> + odp_shm_t shm_bucket;
> +} odph_cuckoo_hash_tbl_t ODP_ALIGNED_CACHE;
> +
> +/**
> + * Parameters used when creating the cuckoo hash table.
> + */
> +typedef struct odph_cuckoo_hash_param_t {
> + /**< Name of the hash table. */
> + const char *name;
> + /**< Total hash table entries. */
> + uint32_t entries;
> + /**< Length of hash key. */
> + uint32_t key_len;
> + /**< Primary Hash function used to calculate hash. */
> + odp_hash_function hash_func;
> + /**< Init value used by hash_func. */
> + uint32_t hash_func_init_val;
> + /**< Indicate if additional parameters are present. */
> + uint8_t extra_flag;
> +} odph_cuckoo_hash_param_t;
> +
> +/**
> + * Create a new cuckoo hash table.
> + *
> + * @param ht
> + * hash table if successful
> + * @param params
> + * Parameters used to create and initialise the hash table.
> + * @return
> + * 0 on success
> + * negative value on errors including:
> + * - -EINVAL - invalid parameter passed to function
> + * - -EEXIST - a hash table with the same name already exists
> + * - -ENOMEM - no appropriate memory area found in which to create memzone
> + */
> +int
> +odph_cuckoo_hash_create(odph_cuckoo_hash_tbl_t **ht,
> + const odph_cuckoo_hash_param_t *params);
> +
> +/**
> + * Find an existing hash table object and return a pointer to it.
> + *
> + * @param name
> + * Name of the hash table as passed to odph_hash_create()
> + * @return
> + * Pointer to hash table or NULL if object not found
> + */
> +odph_cuckoo_hash_tbl_t *
> +odph_cuckoo_hash_find_existing(const char *name);
> +
> +/**
> + * De-allocate all memory used by hash table.
> + * @param h
> + * Hash table to free
> + */
> +void
> +odph_cuckoo_hash_destroy(odph_cuckoo_hash_tbl_t *h);
> +
> +/**
> + * Reset all hash structure, by zeroing all entries
> + * @param h
> + * Hash table to reset
> + */
> +void
> +odph_cuckoo_hash_reset(odph_cuckoo_hash_tbl_t *h);
> +
> +/**
> + * Add a key-value pair to an existing hash table.
> + * This operation is not multi-thread safe
> + * and should only be called from one thread.
> + *
> + * @param h
> + * Hash table to add the key to.
> + * @param key
> + * Key to add to the hash table.
> + * @param data
> + * Data to add to the hash table.
> + * @return
> + * - 0 if added successfully
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOSPC if there is no space in the hash for this key.
> + */
> +int
> +odph_cuckoo_hash_add_key_data(const odph_cuckoo_hash_tbl_t *h,
> + const void *key, void *data);
> +
> +/**
> + * Add a key-value pair with a pre-computed hash value
> + * to an existing hash table.
> + * This operation is not multi-thread safe
> + * and should only be called from one thread.
> + *
> + * @param h
> + * Hash table to add the key to.
> + * @param key
> + * Key to add to the hash table.
> + * @param sig
> + * Precomputed hash value for 'key'
> + * @param data
> + * Data to add to the hash table.
> + * @return
> + * - 0 if added successfully
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOSPC if there is no space in the hash for this key.
> + */
> +int32_t
> +odph_cuckoo_hash_add_key_with_hash_data(
> + const odph_cuckoo_hash_tbl_t *h, const void *key,
> + uint32_t sig, void *data);
> +
> +/**
> + * Add a key to an existing hash table. This operation is not multi-thread
> + * safe and should only be called from one thread.
> + *
> + * @param h
> + * Hash table to add the key to.
> + * @param key
> + * Key to add to the hash table.
> + * @return
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOSPC if there is no space in the hash for this key.
> + * - A positive value that can be used by the caller as an offset into an
> + * array of user data. This value is unique for this key.
> + */
> +int32_t
> +odph_cuckoo_hash_add_key(const odph_cuckoo_hash_tbl_t *h, const void *key);
> +
> +/**
> + * Add a key to an existing hash table.
> + * This operation is not multi-thread safe
> + * and should only be called from one thread.
> + *
> + * @param h
> + * Hash table to add the key to.
> + * @param key
> + * Key to add to the hash table.
> + * @param sig
> + * Precomputed hash value for 'key'.
> + * @return
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOSPC if there is no space in the hash for this key.
> + * - A positive value that can be used by the caller as an offset into an
> + * array of user data. This value is unique for this key.
> + */
> +int32_t
> +odph_cuckoo_hash_add_key_with_hash(
> + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig);
> +
> +/**
> + * Remove a key from an existing hash table.
> + * This operation is not multi-thread safe
> + * and should only be called from one thread.
> + *
> + * @param h
> + * Hash table to remove the key from.
> + * @param key
> + * Key to remove from the hash table.
> + * @return
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOENT if the key is not found.
> + * - A positive value that can be used by the caller as an offset into an
> + * array of user data. This value is unique for this key, and is the same
> + * value that was returned when the key was added.
> + */
> +int32_t
> +odph_cuckoo_hash_del_key(const odph_cuckoo_hash_tbl_t *h, const void *key);
> +
> +/**
> + * Remove a key from an existing hash table.
> + * This operation is not multi-thread safe
> + * and should only be called from one thread.
> + *
> + * @param h
> + * Hash table to remove the key from.
> + * @param key
> + * Key to remove from the hash table.
> + * @param sig
> + * Precomputed hash value for 'key'.
> + * @return
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOENT if the key is not found.
> + * - A positive value that can be used by the caller as an offset into an
> + * array of user data. This value is unique for this key, and is the same
> + * value that was returned when the key was added.
> + */
> +int32_t
> +odph_cuckoo_hash_del_key_with_hash(
> + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig);
> +
> +/**
> + * Find a key-value pair in the hash table.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + * Hash table to look in.
> + * @param key
> + * Key to find.
> + * @param data
> + * Output with pointer to data returned from the hash table.
> + * @return
> + * 0 if successful lookup
> + * - EINVAL if the parameters are invalid.
> + * - ENOENT if the key is not found.
> + */
> +int
> +odph_cukoo_hash_lookup_data(
> + const odph_cuckoo_hash_tbl_t *h, const void *key, void **data);
> +
> +/**
> + * Find a key-value pair with a pre-computed hash value
> + * to an existing hash table.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + * Hash table to look in.
> + * @param key
> + * Key to find.
> + * @param sig
> + * Precomputed hash value for 'key'
> + * @param data
> + * Output with pointer to data returned from the hash table.
> + * @return
> + * 0 if successful lookup
> + * - EINVAL if the parameters are invalid.
> + * - ENOENT if the key is not found.
> + */
> +int
> +odph_cuckoo_hash_lookup_with_hash_data(
> + const odph_cuckoo_hash_tbl_t *h, const void *key,
> + uint32_t sig, void **data);
> +
> +/**
> + * Find a key in the hash table.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + * Hash table to look in.
> + * @param key
> + * Key to find.
> + * @return
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOENT if the key is not found.
> + * - A positive value that can be used by the caller as an offset into an
> + * array of user data. This value is unique for this key, and is the same
> + * value that was returned when the key was added.
> + */
> +int32_t
> +odph_cuckoo_hash_lookup(const odph_cuckoo_hash_tbl_t *h, const void *key);
> +
> +/**
> + * Find a key in the hash table.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + * Hash table to look in.
> + * @param key
> + * Key to find.
> + * @param sig
> + * Hash value to remove from the hash table.
> + * @return
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOENT if the key is not found.
> + * - A positive value that can be used by the caller as an offset into an
> + * array of user data. This value is unique for this key, and is the same
> + * value that was returned when the key was added.
> + */
> +int32_t
> +odph_cuckoo_hash_lookup_with_hash(
> + const odph_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig);
> +
> +/**
> + * Find multiple keys in the hash table.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + * Hash table to look in.
> + * @param keys
> + * A pointer to a list of keys to look for.
> + * @param num_keys
> + * How many keys are in the keys list (less than
> ODPH_HASH_LOOKUP_BULK_MAX).
> + * @param hit_mask
> + * Output containing a bitmask with all successful lookups.
> + * @param data
> + * Output containing array of data returned from all the successful
> lookups.
> + * @return
> + * -EINVAL if there's an error, otherwise number of successful lookups.
> + */
> +int
> +odph_cuckoo_hash_lookup_bulk_data(
> + const odph_cuckoo_hash_tbl_t *h, const void **keys,
> + uint32_t num_keys, uint64_t *hit_mask, void *data[]);
> +
> +/**
> + * Find multiple keys in the hash table.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + * Hash table to look in.
> + * @param keys
> + * A pointer to a list of keys to look for.
> + * @param num_keys
> + * How many keys are in the keys list (less than HASH_LOOKUP_BULK_MAX).
> + * @param positions
> + * Output containing a list of values, corresponding to the list of keys
> that
> + * can be used by the caller as an offset into an array of user data. These
> + * values are unique for each key, and are the same values that were
> returned
> + * when each key was added. If a key in the list was not found, then
> -ENOENT
> + * will be the value.
> + * @return
> + * -EINVAL if there's an error, otherwise 0.
> + */
> +int
> +odph_cuckoo_hash_lookup_bulk(
> + const odph_cuckoo_hash_tbl_t *h, const void **keys,
> + uint32_t num_keys, int32_t *positions);
> +
> +/**
> + * Iterate through the hash table, returning key-value pairs.
> + *
> + * @param h
> + * Hash table to iterate
> + * @param key
> + * Output containing the key where current iterator
> + * was pointing at
> + * @param data
> + * Output containing the data associated with key.
> + * Returns NULL if data was not stored.
> + * @param next
> + * Pointer to iterator. Should be 0 to start iterating the hash table.
> + * Iterator is incremented after each call of this function.
> + * @return
> + * Position where key was stored, if successful.
> + * - -EINVAL if the parameters are invalid.
> + * - -ENOENT if end of the hash table.
> + */
> +int32_t
> +odph_cuckoo_hash_iterate(
> + const odph_cuckoo_hash_tbl_t *h,
> + const void **key, void **data, uint32_t *next);
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* ODPH_HASH_H_ */
> diff --git a/helper/include/odp/helper/ring.h
> b/helper/include/odp/helper/ring.h
> index 65c32ad..3c1a3bf 100644
> --- a/helper/include/odp/helper/ring.h
> +++ b/helper/include/odp/helper/ring.h
> @@ -132,6 +132,8 @@ typedef struct odph_ring {
> /** @private Flags supplied at creation. */
> int flags;
>
> + odp_shm_t shm;
> +
> /** @private Producer */
> struct prod {
> uint32_t watermark; /* Maximum items */
> @@ -194,6 +196,18 @@ typedef struct odph_ring {
> odph_ring_t *odph_ring_create(const char *name, unsigned count,
> unsigned flags);
>
> +/**
> + * Free a ring in memory.
> + *
> + * This function uses odp_shm_reserve() to allocate memory. Its size is
> + * set to *count*, which must be a power of two. Water marking is
> + * disabled by default. Note that the real usable ring size is count-1
> + * instead of count.
> + *
> + * @param r
> + * The pointer to the ring need to be free.
> + */
> +void odph_ring_free(odph_ring_t *r);
>
> /**
> * Change the high water mark.
> @@ -372,6 +386,21 @@ int odph_ring_sp_enqueue_bulk(odph_ring_t *r, void *
> const *obj_table,
> unsigned n);
>
> /**
> + * Enqueue one object on a ring (NOT multi-producers safe).
> + *
> + * @param r
> + * A pointer to the ring structure.
> + * @param obj
> + * A pointer to the object to be added.
> + * @return
> + * - 0: Success; objects enqueued.
> + * - -EDQUOT: Quota exceeded. The objects have been enqueued, but the
> + * high water mark is exceeded.
> + * - -ENOBUFS: Not enough room in the ring to enqueue; no object is
> enqueued.
> + */
> +int odph_ring_sp_enqueue(odph_ring_t *r, void *obj);
> +
> +/**
> * Dequeue several objects from a ring (multi-consumers safe).
> *
> * This function uses a "compare and set" instruction to move the
> @@ -408,6 +437,20 @@ int odph_ring_mc_dequeue_bulk(odph_ring_t *r, void
> **obj_table, unsigned n);
> int odph_ring_sc_dequeue_bulk(odph_ring_t *r, void **obj_table, unsigned n);
>
> /**
> + * Dequeue one object from a ring (NOT multi-consumers safe).
> + *
> + * @param r
> + * A pointer to the ring structure.
> + * @param obj_p
> + * A pointer to a void * pointer (object) that will be filled.
> + * @return
> + * - 0: Success; objects dequeued.
> + * - -ENOENT: Not enough entries in the ring to dequeue, no object is
> + * dequeued.
> + */
> +int odph_ring_sc_dequeue(odph_ring_t *r, void *obj);
> +
> +/**
> * Test if a ring is full.
> *
> * @param r
> diff --git a/helper/ring.c b/helper/ring.c
> index 3122173..afd7244 100644
> --- a/helper/ring.c
> +++ b/helper/ring.c
> @@ -174,12 +174,18 @@ odph_ring_create(const char *name, unsigned count,
> unsigned flags)
> /* reserve a memory zone for this ring.*/
> shm = odp_shm_reserve(ring_name, ring_size, ODP_CACHE_LINE_SIZE, 0);
>
> + if (shm == ODP_SHM_INVALID) {
> + ODPH_ERR("shm allocation failed for ring %s\n", ring_name);
> + return NULL;
> + }
> +
> r = odp_shm_addr(shm);
>
> if (r != NULL) {
> /* init the ring structure */
> snprintf(r->name, sizeof(r->name), "%s", name);
> r->flags = flags;
> + r->shm = shm;
> r->prod.watermark = count;
> r->prod.sp_enqueue = !!(flags & ODPH_RING_F_SP_ENQ);
> r->cons.sc_dequeue = !!(flags & ODPH_RING_F_SC_DEQ);
> @@ -201,6 +207,18 @@ odph_ring_create(const char *name, unsigned count,
> unsigned flags)
> return r;
> }
>
> +/* free a ring */
> +void
> +odph_ring_free(odph_ring_t *r)
> +{
> + odp_rwlock_write_lock(&qlock);
> + TAILQ_REMOVE(&odp_ring_list, r, next);
> + odp_rwlock_write_unlock(&qlock);
> +
> + if (r->shm != ODP_SHM_INVALID)
> + odp_shm_free(r->shm);
> +}
> +
> /*
> * change the high water mark. If *count* is 0, water marking is
> * disabled
> @@ -471,6 +489,11 @@ int odph_ring_sp_enqueue_bulk(odph_ring_t *r, void *
> const *obj_table,
> ODPH_RING_QUEUE_FIXED);
> }
>
> +int odph_ring_sp_enqueue(odph_ring_t *r, void *obj)
> +{
> + return odph_ring_sp_enqueue_bulk(r, &obj, 1);
> +}
> +
> /**
> * Dequeue several objects from a ring (multi-consumers safe).
> */
> @@ -489,6 +512,11 @@ int odph_ring_sc_dequeue_bulk(odph_ring_t *r, void
> **obj_table, unsigned n)
> ODPH_RING_QUEUE_FIXED);
> }
>
> +int odph_ring_sc_dequeue(odph_ring_t *r, void *obj)
> +{
> + return odph_ring_sc_dequeue_bulk(r, &obj, 1);
> +}
> +
> /**
> * Test if a ring is full.
> */
> diff --git a/helper/test/Makefile.am b/helper/test/Makefile.am
> index d6820e1..e358a87 100644
> --- a/helper/test/Makefile.am
> +++ b/helper/test/Makefile.am
> @@ -9,7 +9,8 @@ EXECUTABLES = odp_chksum$(EXEEXT) \
> odp_thread$(EXEEXT) \
> odp_process$(EXEEXT)\
> odph_pause$(EXEEXT)\
> - odp_table$(EXEEXT)
> + odp_table$(EXEEXT)\
> + odp_cuckoo_hash$(EXEEXT)
>
> COMPILE_ONLY =
>
> @@ -31,3 +32,4 @@ dist_odp_process_SOURCES = odp_process.c
> odp_process_LDADD = $(LIB)/libodphelper.la $(LIB)/libodp.la
> odph_pause_SOURCES = odph_pause.c
> dist_odp_table_SOURCES = odp_table.c
> +dist_odp_cuckoo_hash_SOURCES = odp_cuckoo_hash.c
> diff --git a/helper/test/odp_cuckoo_hash.c b/helper/test/odp_cuckoo_hash.c
> new file mode 100644
> index 0000000..c51ba0a
> --- /dev/null
> +++ b/helper/test/odp_cuckoo_hash.c
> @@ -0,0 +1,779 @@
> +/* Copyright (c) 2015, Linaro Limited
> + * All rights reserved.
> + *
> + * SPDX-License-Identifier: BSD-3-Clause
> + */
> +
> +/*-
> + * BSD LICENSE
> + *
> + * Copyright(c) 2010-2015 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 <stdio.h>
> +#include <stdint.h>
> +#include <string.h>
> +#include <stdlib.h>
> +#include <stdarg.h>
> +#include <errno.h>
> +#include <sys/queue.h>
> +#include <sys/time.h>
> +#include <time.h>
> +
> +#include <test_debug.h>
> +#include <odp.h>
> +#include <odp/helper/ring.h>
> +#include <odp/helper/cuckoo_hash.h>
> +
> +/*******************************************************************************
> + * Hash function performance test configuration section. Each performance
> test
> + * will be performed HASHTEST_ITERATIONS times.
> + *
> + * The five arrays below control what tests are performed. Every combination
> + * from the array entries is tested.
> + */
> +odp_hash_function hashtest_funcs[] = {odp_hash_crc32c};
> +/******************************************************************************/
> +
> +/*
> + * Check condition and return an error if true. Assumes that "handle" is the
> + * name of the hash structure pointer to be freed.
> + */
> +#define RETURN_IF_ERROR(cond, str, ...) do { \
> + if (cond) { \
> + printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
> + if (handle) \
> + odph_cuckoo_hash_destroy(handle); \
> + return -1; \
> + } \
> +} while (0)
> +
> +/* 5-tuple key type */
> +struct flow_key {
> + uint32_t ip_src;
> + uint32_t ip_dst;
> + uint16_t port_src;
> + uint16_t port_dst;
> + uint8_t proto;
> +} __packed;
> +
> +/*
> + * Print out result of unit test hash operation.
> + */
> +static void print_key_info(
> + const char *msg, const struct flow_key *key,
> + int32_t pos)
> +{
> + const uint8_t *p = (const uint8_t *)key;
> + unsigned i;
> +
> + printf("%s key:0x", msg);
> + for (i = 0; i < sizeof(struct flow_key); i++)
> + printf("%02X", p[i]);
> + printf(" @ pos %d\n", pos);
> +}
> +
> +static double get_time_diff(struct timeval *start, struct timeval *end)
> +{
> + int sec = end->tv_sec - start->tv_sec;
> + int usec = end->tv_usec - start->tv_usec;
> +
> + if (usec < 0) {
> + sec--;
> + usec += 1000000;
> + }
> + double diff = sec + (double)usec / 1000000;
> +
> + return diff;
> +}
> +
> +/** Create IPv4 address */
> +#define IPv4(a, b, c, d) ((uint32_t)(((a) & 0xff) << 24) | \
> + (((b) & 0xff) << 16) | \
> + (((c) & 0xff) << 8) | \
> + ((d) & 0xff))
> +
> +/* Keys used by unit test functions */
> +static struct flow_key keys[5] = { {
> + .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
> + .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
> + .port_src = 0x0908,
> + .port_dst = 0x0b0a,
> + .proto = 0x0c,
> +}, {
> + .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
> + .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
> + .port_src = 0x1918,
> + .port_dst = 0x1b1a,
> + .proto = 0x1c,
> +}, {
> + .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
> + .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
> + .port_src = 0x2928,
> + .port_dst = 0x2b2a,
> + .proto = 0x2c,
> +}, {
> + .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
> + .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
> + .port_src = 0x3938,
> + .port_dst = 0x3b3a,
> + .proto = 0x3c,
> +}, {
> + .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
> + .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
> + .port_src = 0x4948,
> + .port_dst = 0x4b4a,
> + .proto = 0x4c,
> +} };
> +
> +/* Parameters used for hash table in unit test functions. Name set later. */
> +static odph_cuckoo_hash_param_t ut_params = {
> + .entries = 64,
> + .key_len = sizeof(struct flow_key), /* 13 */
> + .hash_func = odp_hash_crc32c,
> + .hash_func_init_val = 0,
> +};
> +
> +#define CRC32_ITERATIONS 1048576
> +#define CRC32_DWORDS 64
> +
> +static uint32_t hash(const odph_cuckoo_hash_tbl_t *h, const void *key)
> +{
> + /* calc hash result by key */
> + return h->hash_func(key, h->key_len, h->hash_func_init_val);
> +}
> +
> +/*
> + * Basic sequence of operations for a single key:
> + * - add
> + * - lookup (hit)
> + * - delete
> + * - lookup (miss)
> + */
> +static int test_add_delete(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle;
> + /* test with standard add/lookup/delete functions */
> + int pos0, expected_pos0;
> + int ret;
> +
> + ut_params.name = "test1";
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(ret < 0, "cuckoo hash creation failed");
> +
> + pos0 = odph_cuckoo_hash_add_key(handle, &keys[0]);
> + print_key_info("Add", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
> + expected_pos0 = pos0;
> +
> + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]);
> + print_key_info("Lkp", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != expected_pos0,
> + "failed to find key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]);
> + print_key_info("Del", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != expected_pos0,
> + "failed to delete key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]);
> + print_key_info("Lkp", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != -ENOENT,
> + "fail: found key after deleting! (pos0=%d)", pos0);
> +
> + odph_cuckoo_hash_destroy(handle);
> +
> + /* repeat test with precomputed hash functions */
> + uint32_t hash_value;
> + int pos1, expected_pos1;
> +
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(handle == NULL, "hash creation failed");
> +
> + hash_value = hash(handle, &keys[0]);
> + pos1 = odph_cuckoo_hash_add_key_with_hash(handle, &keys[0], hash_value);
> + print_key_info("Add", &keys[0], pos1);
> + RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
> + expected_pos1 = pos1;
> +
> + pos1 = odph_cuckoo_hash_lookup_with_hash(handle, &keys[0], hash_value);
> + print_key_info("Lkp", &keys[0], pos1);
> + RETURN_IF_ERROR(pos1 != expected_pos1,
> + "failed to find key (pos1=%d)", pos1);
> +
> + pos1 = odph_cuckoo_hash_del_key_with_hash(handle, &keys[0], hash_value);
> + print_key_info("Del", &keys[0], pos1);
> + RETURN_IF_ERROR(pos1 != expected_pos1,
> + "failed to delete key (pos1=%d)", pos1);
> +
> + pos1 = odph_cuckoo_hash_lookup_with_hash(handle, &keys[0], hash_value);
> + print_key_info("Lkp", &keys[0], pos1);
> + RETURN_IF_ERROR(pos1 != -ENOENT,
> + "fail: found key after deleting! (pos1=%d)", pos1);
> +
> + odph_cuckoo_hash_destroy(handle);
> +
> + return 0;
> +}
> +
> +/*
> + * Sequence of operations for a single key:
> + * - delete: miss
> + * - add
> + * - lookup: hit
> + * - add: update
> + * - lookup: hit (updated data)
> + * - delete: hit
> + * - delete: miss
> + * - lookup: miss
> + */
> +static int test_add_update_delete(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle;
> + int pos0, expected_pos0;
> + int ret;
> +
> + ut_params.name = "test2";
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(ret < 0, "hash creation failed");
> +
> + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]);
> + print_key_info("Del", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != -ENOENT,
> + "fail: found non-existent key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_add_key(handle, &keys[0]);
> + print_key_info("Add", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
> + expected_pos0 = pos0;
> +
> + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]);
> + print_key_info("Lkp", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != expected_pos0,
> + "failed to find key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_add_key(handle, &keys[0]);
> + print_key_info("Add", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != expected_pos0,
> + "failed to re-add key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]);
> + print_key_info("Lkp", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != expected_pos0,
> + "failed to find key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]);
> + print_key_info("Del", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != expected_pos0,
> + "failed to delete key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_del_key(handle, &keys[0]);
> + print_key_info("Del", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != -ENOENT,
> + "fail: deleted already deleted key (pos0=%d)", pos0);
> +
> + pos0 = odph_cuckoo_hash_lookup(handle, &keys[0]);
> + print_key_info("Lkp", &keys[0], pos0);
> + RETURN_IF_ERROR(pos0 != -ENOENT,
> + "fail: found key after deleting! (pos0=%d)", pos0);
> +
> + odph_cuckoo_hash_destroy(handle);
> + return 0;
> +}
> +
> +/*
> + * Sequence of operations for find existing hash table
> + *
> + * - create table
> + * - find existing table: hit
> + * - find non-existing table: miss
> + *
> + */
> +static int test_hash_find_existing(void)
> +{
> + int ret;
> + odph_cuckoo_hash_tbl_t *handle = NULL, *result = NULL;
> +
> + /* Create hash table. */
> + ut_params.name = "hash_find_existing";
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(ret < 0, "hash creation failed");
> +
> + /* Try to find existing hash table */
> + result = odph_cuckoo_hash_find_existing("hash_find_existing");
> + RETURN_IF_ERROR(result != handle, "could not find existing hash table");
> +
> + /* Try to find non-existing hash table */
> + result = odph_cuckoo_hash_find_existing("hash_find_non_existing");
> + RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
> +
> + /* Cleanup. */
> + odph_cuckoo_hash_destroy(handle);
> +
> + return 0;
> +}
> +
> +/*
> + * Sequence of operations for 5 keys
> + * - add keys
> + * - lookup keys: hit
> + * - add keys (update)
> + * - lookup keys: hit (updated data)
> + * - delete keys : hit
> + * - lookup keys: miss
> + */
> +static int test_five_keys(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle;
> + const void *key_array[5] = {0};
> + int pos[5];
> + int expected_pos[5];
> + unsigned i;
> + int ret;
> +
> + ut_params.name = "test3";
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(ret < 0, "hash creation failed");
> +
> + /* Add */
> + for (i = 0; i < 5; i++) {
> + pos[i] = odph_cuckoo_hash_add_key(handle, &keys[i]);
> + print_key_info("Add", &keys[i], pos[i]);
> + RETURN_IF_ERROR(pos[i] < 0,
> + "failed to add key (pos[%u]=%d)", i, pos[i]);
> + expected_pos[i] = pos[i];
> + }
> +
> + /* Lookup */
> + for (i = 0; i < 5; i++)
> + key_array[i] = &keys[i];
> +
> + ret = odph_cuckoo_hash_lookup_bulk(handle, &key_array[0], 5,
> + (int32_t *)pos);
> + if (ret == 0)
> + for (i = 0; i < 5; i++) {
> + print_key_info("Lkp", key_array[i], pos[i]);
> + RETURN_IF_ERROR(
> + pos[i] != expected_pos[i],
> + "failed to find key (pos[%u]=%d)",
> + i, pos[i]);
> + }
> +
> + /* Add - update */
> + for (i = 0; i < 5; i++) {
> + pos[i] = odph_cuckoo_hash_add_key(handle, &keys[i]);
> + print_key_info("Add", &keys[i], pos[i]);
> + RETURN_IF_ERROR(
> + pos[i] != expected_pos[i],
> + "failed to add key (pos[%u]=%d)", i, pos[i]);
> + }
> +
> + /* Lookup */
> + for (i = 0; i < 5; i++) {
> + pos[i] = odph_cuckoo_hash_lookup(handle, &keys[i]);
> + print_key_info("Lkp", &keys[i], pos[i]);
> + RETURN_IF_ERROR(
> + pos[i] != expected_pos[i],
> + "failed to find key (pos[%u]=%d)", i, pos[i]);
> + }
> +
> + /* Delete */
> + for (i = 0; i < 5; i++) {
> + pos[i] = odph_cuckoo_hash_del_key(handle, &keys[i]);
> + print_key_info("Del", &keys[i], pos[i]);
> + RETURN_IF_ERROR(
> + pos[i] != expected_pos[i],
> + "failed to delete key (pos[%u]=%d)", i, pos[i]);
> + }
> +
> + /* Lookup */
> + for (i = 0; i < 5; i++) {
> + pos[i] = odph_cuckoo_hash_lookup(handle, &keys[i]);
> + print_key_info("Lkp", &keys[i], pos[i]);
> + RETURN_IF_ERROR(
> + pos[i] != -ENOENT,
> + "found non-existent key (pos[%u]=%d)",
> + i, pos[i]);
> + }
> +
> + /* Lookup multi */
> + ret = odph_cuckoo_hash_lookup_bulk(handle, &key_array[0], 5,
> + (int32_t *)pos);
> + if (ret == 0)
> + for (i = 0; i < 5; i++) {
> + print_key_info("Lkp", key_array[i], pos[i]);
> + RETURN_IF_ERROR(
> + pos[i] != -ENOENT,
> + "found not-existent key (pos[%u]=%d)",
> + i, pos[i]);
> + }
> +
> + odph_cuckoo_hash_destroy(handle);
> + return 0;
> +}
> +
> +#define BUCKET_ENTRIES 4
> +#define HASH_ENTRIES_MAX 1048576
> +/*
> + * Do tests for hash creation with bad parameters.
> + */
> +static int test_hash_creation_with_bad_parameters(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle;
> + odph_cuckoo_hash_param_t params;
> + int ret;
> +
> + ret = odph_cuckoo_hash_create(&handle, NULL);
> + if (handle != NULL) {
> + odph_cuckoo_hash_destroy(handle);
> + printf("Impossible creating hash successfully without any
> parameter\n");
> + return -1;
> + }
> +
> + memcpy(¶ms, &ut_params, sizeof(params));
> + params.name = "creation_with_bad_parameters_0";
> + params.entries = HASH_ENTRIES_MAX + 1;
> + ret = odph_cuckoo_hash_create(&handle, ¶ms);
> + if (handle != NULL) {
> + odph_cuckoo_hash_destroy(handle);
> + printf("Impossible creating hash successfully with entries in
> parameter exceeded\n");
> + return -1;
> + }
> +
> + memcpy(¶ms, &ut_params, sizeof(params));
> + params.name = "creation_with_bad_parameters_2";
> + params.entries = BUCKET_ENTRIES - 1;
> + ret = odph_cuckoo_hash_create(&handle, ¶ms);
> + if (handle != NULL || ret == 0) {
> + odph_cuckoo_hash_destroy(handle);
> + printf("Impossible creating hash successfully if entries less
> than bucket_entries in parameter\n");
> + return -1;
> + }
> +
> + memcpy(¶ms, &ut_params, sizeof(params));
> + params.name = "creation_with_bad_parameters_3";
> + params.key_len = 0;
> + ret = odph_cuckoo_hash_create(&handle, ¶ms);
> + if (handle != NULL) {
> + odph_cuckoo_hash_destroy(handle);
> + printf("Impossible creating hash successfully if key_len in
> parameter is zero\n");
> + return -1;
> + }
> +
> + odph_cuckoo_hash_destroy(handle);
> + printf("# Test successful. No more errors expected\n");
> +
> + return 0;
> +}
> +
> +/*
> + * Do tests for hash creation with parameters that look incorrect
> + * but are actually valid.
> + */
> +static int
> +test_hash_creation_with_good_parameters(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle, *tmp;
> + odph_cuckoo_hash_param_t params;
> + int ret;
> +
> + /* create with null hash function - should choose DEFAULT_HASH_FUNC */
> + memcpy(¶ms, &ut_params, sizeof(params));
> + params.name = "same_name";
> + params.hash_func = NULL;
> + ret = odph_cuckoo_hash_create(&handle, ¶ms);
> + if (handle == NULL || ret < 0) {
> + printf("Creating hash with null hash_func failed\n");
> + return -1;
> + }
> +
> + /* this test is trying to create a hash with the same
> + * name as previous one. This should return a pointer
> + * to the hash we previously created. The previous hash
> + * isn't freed exactly for the purpose of it being in
> + * the hash list.
> + */
> + memcpy(¶ms, &ut_params, sizeof(params));
> + params.name = "same_name";
> + ret = odph_cuckoo_hash_create(&tmp, ¶ms);
> +
> + /* check if the returned handle is actually
> + equal to the previous hash */
> + if (handle != tmp) {
> + odph_cuckoo_hash_destroy(handle);
> + odph_cuckoo_hash_destroy(tmp);
> + printf("Creating hash with existing name was successful\n");
> + return -1;
> + }
> +
> + /* try creating hash when there already are hashes in
> + * the list. The previous hash is not freed to have a
> + * non-empty hash list. The other hash that's in the
> + * list is still pointed to by "handle" var.
> + */
> + memcpy(¶ms, &ut_params, sizeof(params));
> + params.name = "different_name";
> + ret = odph_cuckoo_hash_create(&tmp, ¶ms);
> + if (tmp == NULL) {
> + odph_cuckoo_hash_destroy(handle);
> + printf("Creating hash with valid parameters failed\n");
> + return -1;
> + }
> +
> + odph_cuckoo_hash_destroy(tmp);
> + odph_cuckoo_hash_destroy(handle);
> +
> + return 0;
> +}
> +
> +#define ITERATIONS 50
> +#define NUM_ENTRIES 1024
> +#define HASH_KEY_LENGTH_MAX 64
> +static int test_hash_iteration(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle;
> + unsigned i;
> + uint8_t keys[NUM_ENTRIES][HASH_KEY_LENGTH_MAX];
> + const void *next_key;
> + void *next_data;
> + void *data[NUM_ENTRIES];
> + unsigned added_keys;
> + uint32_t iter = 0;
> + int ret = 0;
> +
> + ut_params.entries = NUM_ENTRIES;
> + ut_params.name = "test_hash_iteration";
> + ut_params.hash_func = odp_hash_crc32c;
> + ut_params.key_len = 16;
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(handle == NULL, "hash creation failed");
> +
> + /* Add random entries until key cannot be added */
> + for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) {
> + data[added_keys] = (void *)((uintptr_t)rand());
> + for (i = 0; i < ut_params.key_len; i++)
> + keys[added_keys][i] = rand() % 255;
> + ret = odph_cuckoo_hash_add_key_data(
> + handle, keys[added_keys], data[added_keys]);
> + if (ret < 0)
> + break;
> + }
> +
> + /* Iterate through the hash table */
> + while (odph_cuckoo_hash_iterate(handle,
> + &next_key, &next_data, &iter) >= 0) {
> + /* Search for the key in the list of keys added */
> + for (i = 0; i < NUM_ENTRIES; i++) {
> + if (memcmp(next_key, keys[i], ut_params.key_len) == 0) {
> + if (next_data != data[i]) {
> + printf("Data found in the hash table is
> not");
> + printf("The data added with the key\n");
> + goto err;
> + }
> + added_keys--;
> + break;
> + }
> + }
> + if (i == NUM_ENTRIES) {
> + printf("Key found in the hash table was not added\n");
> + goto err;
> + }
> + }
> +
> + /* Check if all keys have been iterated */
> + if (added_keys != 0) {
> + printf("There were still %u keys to iterate\n", added_keys);
> + goto err;
> + }
> +
> + odph_cuckoo_hash_destroy(handle);
> + return 0;
> +
> +err:
> + odph_cuckoo_hash_destroy(handle);
> + return -1;
> +}
> +
> +#define ITERATIONS 50
> +#define LOOKUP_TIMES 1000
> +/*
> + * Test to see the average table utilization (entries added/max entries)
> + * before hitting a random entry that cannot be added
> + */
> +static int test_average_table_utilization(void)
> +{
> + odph_cuckoo_hash_tbl_t *handle;
> + uint8_t simple_key[HASH_KEY_LENGTH_MAX],
> + lookup_key[LOOKUP_TIMES][HASH_KEY_LENGTH_MAX];
> + unsigned i, j;
> + unsigned added_keys, average_keys_added = 0;
> + int ret, pos_arr[LOOKUP_TIMES];
> + struct timeval start, end;
> + const void *bulk_key[LOOKUP_TIMES] = {0};
> + double add_time = 0, lookup_time = 0, bulk_time = 0;
> +
> + printf("\n# Running test to determine average utilization\n");
> + printf(" before adding elements begins to fail\n");
> + printf("Measuring performance, please wait");
> + fflush(stdout);
> + ut_params.entries = 1 << 20;
> + ut_params.name = "test_average_utilization";
> + ut_params.hash_func = odp_hash_crc32c;
> + ret = odph_cuckoo_hash_create(&handle, &ut_params);
> + RETURN_IF_ERROR(handle == NULL, "hash creation failed");
> +
> + for (j = 0; j < ITERATIONS; j++) {
> + ret = 0;
> + unsigned added_one = 0;
> +
> + gettimeofday(&start, 0);
> + /* Add random entries until key cannot be added */
> + for (added_keys = 0; ret >= 0; added_keys++) {
> + for (i = 0; i < ut_params.key_len; i++) {
> + simple_key[i] = rand() % 255;
> + if (added_one < LOOKUP_TIMES) {
> + lookup_key[added_one][i]
> + = simple_key[i];
> + }
> + }
> + if (added_one < LOOKUP_TIMES)
> + bulk_key[added_one] = &lookup_key[added_one];
> + ret = odph_cuckoo_hash_add_key(handle, simple_key);
> + added_one++;
> + }
> + gettimeofday(&end, 0);
> + add_time += get_time_diff(&start, &end);
> + if (ret != -ENOSPC) {
> + printf("Unexpected error when adding keys\n");
> + odph_cuckoo_hash_destroy(handle);
> + return -1;
> + }
> +
> + gettimeofday(&start, 0);
> + for (i = 0; i < LOOKUP_TIMES; i++)
> + pos_arr[i] = odph_cuckoo_hash_lookup(handle,
> + lookup_key[i]);
> + gettimeofday(&end, 0);
> + lookup_time += get_time_diff(&start, &end);
> +
> + gettimeofday(&start, 0);
> + for (i = 0; i < LOOKUP_TIMES / 64; i++) {
> + odph_cuckoo_hash_lookup_bulk(
> + handle, &bulk_key[i * 64],
> + 64, &pos_arr[i * 64]);
> + }
> + gettimeofday(&end, 0);
> +
> + bulk_time += get_time_diff(&start, &end);
> +
> + average_keys_added += added_keys;
> +
> + odph_cuckoo_hash_reset(handle);
> +
> + /* Print a dot to show progress on operations */
> + printf(".");
> + fflush(stdout);
> + }
> +
> + average_keys_added /= ITERATIONS;
> +
> + printf(
> + "\nAverage table utilization = %.2f%% (%u/%u)\n",
> + ((double)average_keys_added / ut_params.entries * 100),
> + average_keys_added, ut_params.entries);
> + printf(
> + "Average insert time = %lf,", (add_time / ITERATIONS));
> + printf(
> + " lookup time = %lf, lookup_bulk time = %lf\n",
> + (lookup_time / ITERATIONS), (bulk_time / ITERATIONS));
> + odph_cuckoo_hash_destroy(handle);
> +
> + return 0;
> +}
> +
> +/*
> + * Do all unit and performance tests.
> + */
> +static int
> +test_cuckoo_hash_table(void)
> +{
> + odph_ring_tailq_init();
> + if (test_add_delete() < 0)
> + return -1;
> + if (test_hash_find_existing() < 0)
> + return -1;
> + if (test_add_update_delete() < 0)
> + return -1;
> + if (test_five_keys() < 0)
> + return -1;
> + if (test_hash_creation_with_bad_parameters() < 0)
> + return -1;
> + if (test_hash_creation_with_good_parameters() < 0)
> + return -1;
> + if (test_hash_iteration() < 0)
> + return -1;
> + if (test_average_table_utilization() < 0)
> + return -1;
> +
> + return 0;
> +}
> +
> +int main(int argc TEST_UNUSED, char *argv[] TEST_UNUSED)
> +{
> + if (odp_init_global(NULL, NULL)) {
> + LOG_ERR("Error: ODP global init failed.\n");
> + exit(EXIT_FAILURE);
> + }
> +
> + if (odp_init_local(ODP_THREAD_WORKER)) {
> + LOG_ERR("Error: ODP local init failed.\n");
> + exit(EXIT_FAILURE);
> + }
> +
> + int val = test_cuckoo_hash_table();
> +
> + if (val < 0)
> + printf("cuckoo hash test fail!!\n");
> + else
> + printf("All Tests pass!!\n");
> +
> + if (odp_term_local()) {
> + LOG_ERR("Error: ODP local term failed.\n");
> + exit(EXIT_FAILURE);
> + }
> +
> + if (odp_term_global()) {
> + LOG_ERR("Error: ODP global term failed.\n");
> + exit(EXIT_FAILURE);
> + }
> +
> + return val;
> +}
> +
> diff --git a/include/odp/api/hash.h b/include/odp/api/hash.h
> index 1b2a580..8fd826d 100644
> --- a/include/odp/api/hash.h
> +++ b/include/odp/api/hash.h
> @@ -25,6 +25,20 @@ extern "C" {
> */
>
> /**
> + * @typedef odp_hash_function
> + * odp hash function
> + */
> +typedef uint32_t (*odp_hash_function)(const void *key, uint32_t data_len,
> + uint32_t init_val);
> +
> +/**
> + * @typedef odp_hash_cmp_eq_t
> + * odp hash compare function
> + */
> +typedef int (*odp_hash_cmp_eq_t)(const void *key1,
> + const void *key2, size_t data_len);
> +
> +/**
> * Calculate CRC-32
> *
> * Calculates CRC-32 over the data. The polynomial is 0x04c11db7.
> @@ -45,7 +59,7 @@ uint32_t odp_hash_crc32(const void *data, uint32_t
> data_len, uint32_t init_val);
> *
> * @param data Pointer to data
> * @param data_len Data length in bytes
> -* @param init_val CRC generator initialization value
> +* @param init_val CRC generator initialization nvalue
> *
> * @return CRC32C value
> */
> --
> 1.9.1
>
_______________________________________________
lng-odp mailing list
lng-odp@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/lng-odp
