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 <[email protected]> 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 for some discussion of this topic. > > On Wed, Apr 27, 2016 at 4:06 AM, Maxim Uvarov <[email protected]> > wrote: > >> On 04/27/16 11:12, Ru Jia wrote: >> >>> Signed-off-by: Ru Jia <[email protected]> >>> --- >>> 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 >>> 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 >> [email protected] >> https://lists.linaro.org/mailman/listinfo/lng-odp >> > > > _______________________________________________ > lng-odp mailing list > [email protected] > https://lists.linaro.org/mailman/listinfo/lng-odp > >
_______________________________________________ lng-odp mailing list [email protected] https://lists.linaro.org/mailman/listinfo/lng-odp
