Added cuckoo hash api, which is an efficient hash table. It could
be used for many algorithms.
Signed-off-by: Ru Jia <ji...@ict.ac.cn>
---
include/odp/api/spec/cuckoo_hash.h | 463 +++++++++++++++++++++
include/odp_api.h | 1 +
.../linux-generic/include/odp/api/cuckoo_hash.h | 34 ++
3 files changed, 498 insertions(+)
create mode 100644 include/odp/api/spec/cuckoo_hash.h
create mode 100644 platform/linux-generic/include/odp/api/cuckoo_hash.h
diff --git a/include/odp/api/spec/cuckoo_hash.h
b/include/odp/api/spec/cuckoo_hash.h
new file mode 100644
index 0000000..ca147ce
--- /dev/null
+++ b/include/odp/api/spec/cuckoo_hash.h
@@ -0,0 +1,463 @@
+/* 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 ODP_API_CUCKOO_HASH_H_
+#define ODP_API_CUCKOO_HASH_H_
+
+#include <odp/api/shared_memory.h>
+#include <odp/api/hash.h>
+#include <odp/api/align.h>
+#include <odp/api/std_types.h>
+
+/**
+ * @file
+ *
+ * ODP Cuckoo Hash Table Implementation
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** Maximum number of characters in hash name.*/
+#define ODP_CUCKOO_HASH_NAMESIZE 32
+
+/* 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)))
+
+typedef struct _ring _ring_t;
+
+/**
+ * @typedef odp_hash_function
+ * odp hash function
+ */
+typedef uint32_t (*odp_cuckoo_hash_func_t)(
+ const void *key, uint32_t data_len,
+ uint32_t init_val);
+
+/**
+ * @typedef odp_hash_cmp_eq_t
+ * odp hash compare function
+ */
+typedef int (*odp_cuckoo_hash_cmp_eq_t)(
+ const void *key1,
+ const void *key2, size_t data_len);
+
+/** A hash table structure. */
+typedef struct odp_cuckoo_hash_tbl {
+ /**< Name of the hash. */
+ char name[ODP_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 by hash_func */
+ odp_cuckoo_hash_func_t hash_func;
+ /**< Init value used by hash_func. */
+ uint32_t hash_func_init_val;
+ /**< Function used to compare keys. */
+ odp_cuckoo_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 */
+ _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;
+} odp_cuckoo_hash_tbl_t ODP_ALIGNED_CACHE;
+
+/**
+ * Parameters used when creating the cuckoo hash table.
+ */
+typedef struct odp_cuckoo_hash_param {
+ /**< 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_cuckoo_hash_func_t hash_func;
+ /**< Init value used by hash_func. */
+ uint32_t hash_func_init_val;
+ /**< Indicate if additional parameters are present. */
+ uint8_t extra_flag;
+} odp_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
+odp_cuckoo_hash_create(
+ odp_cuckoo_hash_tbl_t **ht,
+ const odp_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 odp_hash_create()
+ * @return
+ * Pointer to hash table or NULL if object not found
+ */
+odp_cuckoo_hash_tbl_t *
+odp_cuckoo_hash_find_existing(const char *name);
+
+/**
+ * De-allocate all memory used by hash table.
+ * @param h
+ * Hash table to free
+ */
+void
+odp_cuckoo_hash_destroy(odp_cuckoo_hash_tbl_t *h);
+
+/**
+ * Reset all hash structure, by zeroing all entries
+ * @param h
+ * Hash table to reset
+ */
+void
+odp_cuckoo_hash_reset(odp_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
+odp_cuckoo_hash_add_key_data(
+ const odp_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
+odp_cuckoo_hash_add_key_with_hash_data(
+ const odp_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
+odp_cuckoo_hash_add_key(const odp_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
+odp_cuckoo_hash_add_key_with_hash(
+ const odp_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
+odp_cuckoo_hash_del_key(
+ const odp_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
+odp_cuckoo_hash_del_key_with_hash(
+ const odp_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
+odp_cukoo_hash_lookup_data(
+ const odp_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
+odp_cuckoo_hash_lookup_with_hash_data(
+ const odp_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
+odp_cuckoo_hash_lookup(const odp_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
+odp_cuckoo_hash_lookup_with_hash(
+ const odp_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 odp_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
+odp_cuckoo_hash_lookup_bulk_data(
+ const odp_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
+odp_cuckoo_hash_lookup_bulk(
+ const odp_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
+odp_cuckoo_hash_iterate(
+ const odp_cuckoo_hash_tbl_t *h,
+ const void **key, void **data, uint32_t *next);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* ODP_API_HASH_H_ */
diff --git a/include/odp_api.h b/include/odp_api.h
index 44b67ee..721c852 100644
--- a/include/odp_api.h
+++ b/include/odp_api.h
@@ -59,6 +59,7 @@ extern "C" {
#include <odp/api/spinlock_recursive.h>
#include <odp/api/rwlock_recursive.h>
#include <odp/api/std_clib.h>
+#include <odp/api/cuckoo_hash.h>
#ifdef __cplusplus
}
diff --git a/platform/linux-generic/include/odp/api/cuckoo_hash.h
b/platform/linux-generic/include/odp/api/cuckoo_hash.h
new file mode 100644
index 0000000..b4dfd78
--- /dev/null
+++ b/platform/linux-generic/include/odp/api/cuckoo_hash.h
@@ -0,0 +1,34 @@
+/* Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+/**
+ * @file
+ *
+ * ODP Cuckoo Hash Table
+ */
+
+#ifndef ODP_PLAT_CUCKOO_HASH_H_
+#define ODP_PLAT_CUCKOO_HASH_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** @ingroup odp_cuckoo_hash
+ * @{
+ */
+
+/**
+ * @}
+ */
+
+#include <odp/api/spec/cuckoo_hash.h>
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
