Hi, We appreciate more comments on the patch. Thanks. > 在 2016年4月27日，下午7:35，Raj Murali <raj.mur...@linaro.org> 写道： > > Agree with Bill. > The original copyright statement should be retained and we need to add our's > over and above it. > > Raj Murali > > > Raj Murali > Director - Linaro Networking Group > Skype: rajmurali_s │ M: +91 98450 70135 > Linaro.org <http://www.linaro.org/> │ Open source software for ARM SoCs > > > On 27 April 2016 at 16:53, Bill Fischofer <bill.fischo...@linaro.org > <mailto:bill.fischo...@linaro.org>> wrote: > I believe the rule is you retain the original copyright from the base code > but can add your own copyright for any additions/changes. The point is not to > erase history but preserve acknowledgement and the record of the code's BSD > provenance. > > See http://www.openbsd.org/policy.html <http://www.openbsd.org/policy.html> > for some discussion of this topic. > > On Wed, Apr 27, 2016 at 4:06 AM, Maxim Uvarov <maxim.uva...@linaro.org > <mailto:maxim.uva...@linaro.org>> wrote: > On 04/27/16 11:12, Ru Jia wrote: > Signed-off-by: Ru Jia <ji...@ict.ac.cn <mailto:ji...@ict.ac.cn>> > --- > helper/Makefile.am | 6 +- > helper/cuckootable.c | 746 > ++++++++++++++++++++++++++++++++++++++++++++++ > helper/odph_cuckootable.h | 82 +++++ > 3 files changed, 832 insertions(+), 2 deletions(-) > create mode 100644 helper/cuckootable.c > create mode 100644 helper/odph_cuckootable.h > > diff --git a/helper/Makefile.am b/helper/Makefile.am > index 8a86eb7..1763b99 100644 > --- a/helper/Makefile.am > +++ b/helper/Makefile.am > @@ -27,13 +27,15 @@ noinst_HEADERS = \ > $(srcdir)/odph_debug.h \ > $(srcdir)/odph_hashtable.h \ > $(srcdir)/odph_lineartable.h \ > - $(srcdir)/odph_list_internal.h > + $(srcdir)/odph_list_internal.h \ > + $(srcdir)/odph_cuckootable.h > __LIB__libodphelper_linux_la_SOURCES = \ > eth.c \ > ip.c \ > linux.c \ > hashtable.c \ > - lineartable.c > + lineartable.c \ > + cuckootable.c > lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la > <http://libodphelper-linux.la/> > diff --git a/helper/cuckootable.c b/helper/cuckootable.c > new file mode 100644 > index 0000000..64bd894 > --- /dev/null > +++ b/helper/cuckootable.c > @@ -0,0 +1,746 @@ > +/* 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. > > Looks like this code was totally rewritten now to ODP. And I probably we > should > check does it make sense to keep Intels copyright here or not. Any ideas? > > Maxim. > > > + * > + * 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> > + > +/* Macro to enable/disable run-time checking of function parameters */ > +#define RETURN_IF_TRUE(cond, retval) do { \ > + if (cond) \ > + return retval; \ > +} while (0) > + > +/* 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) > +{ > + RETURN_IF_TRUE(((tbl == NULL) || (key == NULL)), -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) > +{ > + RETURN_IF_TRUE(((tbl == NULL) || (key == NULL)), -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) > +{ > + RETURN_IF_TRUE(((tbl == NULL) || (key == NULL)), -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) 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_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; > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* ODPH_CUCKOO_TABLE_H_ */ > > _______________________________________________ > lng-odp mailing list > lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org> > https://lists.linaro.org/mailman/listinfo/lng-odp > <https://lists.linaro.org/mailman/listinfo/lng-odp> > > > _______________________________________________ > lng-odp mailing list > lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org> > https://lists.linaro.org/mailman/listinfo/lng-odp > <https://lists.linaro.org/mailman/listinfo/lng-odp> > > > _______________________________________________ > lng-odp mailing list > lng-odp@lists.linaro.org > https://lists.linaro.org/mailman/listinfo/lng-odp
_______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp
