Usually hash tables not only store keys, but also data associated
to them. In order to maintain the existing API,
the key index will still be returned when
adding/looking up/deleting an entry, but user will be able
to store/look up data associated to a key.
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch at intel.com>
---
lib/librte_hash/rte_cuckoo_hash.c | 231 +++++++++++++++++++++++++----------
lib/librte_hash/rte_hash.h | 144 +++++++++++++++++++++-
lib/librte_hash/rte_hash_version.map | 6 +
3 files changed, 314 insertions(+), 67 deletions(-)
diff --git a/lib/librte_hash/rte_cuckoo_hash.c
b/lib/librte_hash/rte_cuckoo_hash.c
index 8e5b9a6..37e72ab 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -84,6 +84,8 @@ EAL_REGISTER_TAILQ(rte_hash_tailq)
#endif
#define NULL_SIGNATURE 0
+/* Stored key size is a multiple of this value */
+#define KEY_ALIGNMENT 16
typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t
key_len);
static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t
key_len);
@@ -133,6 +135,15 @@ struct rte_hash_bucket {
uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1];
} __rte_cache_aligned;
+struct rte_hash_key {
+ union {
+ uintptr_t idata;
+ void *pdata;
+ };
+ /* Variable key size */
+ char key[] __attribute__((aligned(KEY_ALIGNMENT)));
+};
+
struct rte_hash *
rte_hash_find_existing(const char *name)
{
@@ -200,7 +211,7 @@ rte_hash_create(const struct rte_hash_parameters *params)
/* Total memory required for hash context */
const uint32_t mem_size = sizeof(struct rte_hash) +
num_buckets * sizeof(struct rte_hash_bucket);
- const uint8_t key_entry_size = params->key_len;
+ const uint8_t key_entry_size = sizeof(struct rte_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);
@@ -396,7 +407,7 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket
*bkt,
const void *original_key)
{
static unsigned number_pushes;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
unsigned i, j;
hash_sig_t current_hash_stored, alt_hash_stored;
@@ -421,8 +432,8 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket
*bkt,
* we just entered in a loop and key cannot be added
*/
if (++number_pushes > 1 && current_hash == original_hash) {
- k = (char *)keys + key_idx * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(k, original_key, h->key_len)) {
+ k = (struct rte_hash_key *) ((char *)keys + key_idx *
h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(k->key, original_key, h->key_len)) {
rte_ring_sp_enqueue(h->free_slots,
(void *)((uintptr_t)key_idx));
number_pushes = 0;
@@ -436,6 +447,9 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket
*bkt,
*/
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
key_idx_stored = bkt->key_idx[i];
+ k = (struct rte_hash_key *) ((char *)keys +
+ key_idx_stored *
h->key_entry_size);
+
current_hash_stored = bkt->signatures[i].current;
alt_hash_stored = bkt->signatures[i].alt;
@@ -479,20 +493,21 @@ run_cuckoo(const struct rte_hash *h, struct
rte_hash_bucket *bkt,
static inline int32_t
__rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
- hash_sig_t sig)
+ hash_sig_t sig, uintptr_t data)
{
hash_sig_t hash0, hash1;
uint32_t bucket_idx0, bucket_idx1;
unsigned i;
struct rte_hash_bucket *bkt0, *bkt1;
- void *new_k, *k, *keys = h->key_store;
+ struct rte_hash_key *new_k, *k, *keys = h->key_store;
void *slot_id;
int ret;
/* Get a new slot for storing the new key */
if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)
return -ENOSPC;
- new_k = (char *)keys + (uintptr_t)slot_id * h->key_entry_size;
+ new_k = (struct rte_hash_key *) ((char *)keys +
+ (uintptr_t)slot_id * h->key_entry_size);
rte_prefetch0(new_k);
hash0 = sig;
@@ -508,9 +523,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h,
const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt0->signatures[i].current == hash0 &&
bkt0->signatures[i].alt == hash1) {
- k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(key, k, h->key_len)) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt0->key_idx[i] * h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) {
rte_ring_sp_enqueue(h->free_slots, &slot_id);
+ /* Update data */
+ k->idata = data;
/*
* Return index where key is stored,
* substracting the first dummy index
@@ -524,9 +542,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h,
const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt1->signatures[i].alt == hash0 &&
bkt1->signatures[i].current == hash1) {
- k = (char *)keys + bkt1->key_idx[i] * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(key, k, h->key_len)) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt1->key_idx[i] * h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) {
rte_ring_sp_enqueue(h->free_slots, &slot_id);
+ /* Update data */
+ k->idata = data;
/*
* Return index where key is stored,
* substracting the first dummy index
@@ -536,8 +557,9 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h,
const void *key,
}
}
- /* Copy key */
- rte_memcpy(new_k, key, h->key_len);
+ /* Copy key and data */
+ rte_memcpy(new_k->key, key, h->key_len);
+ new_k->idata = data;
/*
* Run cuckoo algorithm
@@ -568,25 +590,40 @@ rte_hash_add_key_with_hash(const struct rte_hash *h,
const void *key, hash_sig_t sig)
{
RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_add_key_with_hash(h, key, sig);
+ return __rte_hash_add_key_with_hash(h, key, sig, 0);
}
int32_t
rte_hash_add_key(const struct rte_hash *h, const void *key)
{
RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key));
+ return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
+}
+
+int32_t
+rte_hash_add_key_with_hash_data(const struct rte_hash *h,
+ const void *key, hash_sig_t sig, uintptr_t data)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_add_key_with_hash(h, key, sig, data);
+}
+
+int32_t
+rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t
data)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key),
data);
}
static inline int32_t
__rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
- hash_sig_t sig)
+ hash_sig_t sig, uintptr_t *data)
{
uint32_t bucket_idx;
hash_sig_t alt_hash;
unsigned i;
struct rte_hash_bucket *bkt;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
bucket_idx = sig & h->bucket_bitmask;
bkt = &h->buckets[bucket_idx];
@@ -595,13 +632,17 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i].current == sig &&
bkt->signatures[i].sig != NULL_SIGNATURE) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(key, k, h->key_len))
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) {
+ if (data != NULL)
+ *data = k->idata;
/*
* Return index where key is stored,
* substracting the first dummy index
*/
return (bkt->key_idx[i] - 1);
+ }
}
}
@@ -614,13 +655,17 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i].current == alt_hash &&
bkt->signatures[i].alt == sig) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(key, k, h->key_len))
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) {
+ if (data != NULL)
+ *data = k->idata;
/*
* Return index where key is stored,
* substracting the first dummy index
*/
return (bkt->key_idx[i] - 1);
+ }
}
}
@@ -628,29 +673,43 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key,
}
int32_t
+rte_hash_lookup_with_hash_data(const struct rte_hash *h,
+ const void *key, hash_sig_t sig, uintptr_t *data)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_lookup_with_hash(h, key, sig, data);
+}
+
+int32_t
+rte_hash_lookup_data(const struct rte_hash *h, const void *key, uintptr_t
*data)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
+}
+
+int32_t
rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key, hash_sig_t sig)
{
RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_lookup_with_hash(h, key, sig);
+ return __rte_hash_lookup_with_hash(h, key, sig, NULL);
}
int32_t
rte_hash_lookup(const struct rte_hash *h, const void *key)
{
RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key));
+ return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
}
static inline int32_t
-__rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
- hash_sig_t sig)
+__rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
hash_sig_t sig)
{
uint32_t bucket_idx;
hash_sig_t alt_hash;
unsigned i;
struct rte_hash_bucket *bkt;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
bucket_idx = sig & h->bucket_bitmask;
bkt = &h->buckets[bucket_idx];
@@ -659,8 +718,9 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h,
const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i].current == sig &&
bkt->signatures[i].sig != NULL_SIGNATURE) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(key, k, h->key_len)) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) {
bkt->signatures[i].sig = NULL_SIGNATURE;
rte_ring_sp_enqueue(h->free_slots,
(void
*)((uintptr_t)bkt->key_idx[i]));
@@ -682,8 +742,9 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h,
const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i].current == alt_hash &&
bkt->signatures[i].sig != NULL_SIGNATURE) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (!h->rte_hash_cmp_eq(key, k, h->key_len)) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) {
bkt->signatures[i].sig = NULL_SIGNATURE;
rte_ring_sp_enqueue(h->free_slots,
(void
*)((uintptr_t)bkt->key_idx[i]));
@@ -768,9 +829,9 @@ static inline void
lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
const struct rte_hash_bucket *prim_bkt,
const struct rte_hash_bucket *sec_bkt,
- const void **key_slot, int32_t *positions,
- uint64_t *extra_hits_mask, const void *keys,
- const struct rte_hash *h)
+ const struct rte_hash_key **key_slot,
+ int32_t *positions, uint64_t *extra_hits_mask,
+ const void *keys, const struct rte_hash *h)
{
unsigned prim_hash_matches, sec_hash_matches, key_idx, i;
unsigned total_hash_matches;
@@ -788,8 +849,8 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash,
hash_sig_t sec_hash,
total_hash_matches = (prim_hash_matches |
(sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES +
1)));
- *key_slot = (const char *)keys + key_idx * h->key_entry_size;
-
+ *key_slot = (const struct rte_hash_key *)((const char *)keys +
+ key_idx * h->key_entry_size);
rte_prefetch0(*key_slot);
/*
* Return index where key is stored,
@@ -804,15 +865,20 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash,
hash_sig_t sec_hash,
}
-/* Lookup bulk stage 3: Check if key matches, update hit mask */
+/*
+ * Lookup bulk stage 3: Check if key matches, update hit mask
+ * and store data in values[]
+ */
static inline void
-lookup_stage3(unsigned idx, const void *key_slot,
- const void * const *keys, int32_t *positions,
- uint64_t *hits, const struct rte_hash *h)
+lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot,
+ uintptr_t values[], const void * const *keys,
+ int32_t *positions, uint64_t *hits, const struct rte_hash *h)
{
unsigned hit;
- hit = !h->rte_hash_cmp_eq(key_slot, keys[idx], h->key_len);
+ if (values != NULL)
+ values[idx] = key_slot->idata;
+ hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len);
if (unlikely(hit == 0))
positions[idx] = -ENOENT;
*hits = (uint64_t)(hit) << idx;
@@ -820,21 +886,21 @@ lookup_stage3(unsigned idx, const void *key_slot,
static inline int
__rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
- uint32_t num_keys, int32_t *positions) {
+ uint32_t num_keys, int32_t *positions, uintptr_t data[]) {
uint64_t hits = 0;
uint64_t next_mask = 0;
uint64_t extra_hits_mask = 0;
uint64_t lookup_mask;
unsigned idx;
- const void *key_store = h->key_store;
+ const struct rte_hash_key *key_store = h->key_store;
unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
const struct rte_hash_bucket *primary_bkt10, *primary_bkt11;
const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;
const struct rte_hash_bucket *primary_bkt20, *primary_bkt21;
const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;
- const void *k_slot20, *k_slot21, *k_slot30, *k_slot31;
+ const struct rte_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
hash_sig_t primary_hash00, primary_hash01;
hash_sig_t secondary_hash00, secondary_hash01;
hash_sig_t primary_hash10, primary_hash11;
@@ -847,6 +913,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void
**keys,
else
lookup_mask = (1ULL << num_keys) - 1;
+
lookup_stage0(&idx00, &lookup_mask, &primary_hash00,
&secondary_hash00, keys, h);
lookup_stage0(&idx01, &lookup_mask, &primary_hash01,
@@ -929,8 +996,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void
**keys,
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, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
}
k_slot30 = k_slot20, k_slot31 = k_slot21;
@@ -959,8 +1026,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const
void **keys,
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, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
@@ -980,14 +1047,14 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const
void **keys,
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, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
- lookup_stage3(idx30, k_slot30, keys, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
/* handle extra_hits_mask */
next_mask |= extra_hits_mask;
@@ -999,7 +1066,11 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const
void **keys,
/* run a single search for each remaining item */
do {
idx = __builtin_ctzl(next_mask);
- positions[idx] = rte_hash_lookup(h, keys[idx]);
+ if (data != NULL)
+ positions[idx] = rte_hash_lookup_data(h,
keys[idx],
+ &data[idx]);
+ else
+ positions[idx] = rte_hash_lookup(h, keys[idx]);
next_mask &= ~(1llu << idx);
} while (next_mask);
}
@@ -1010,21 +1081,21 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const
void **keys,
static inline int
__rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys,
const hash_sig_t *hash_vals, uint32_t num_keys,
- int32_t *positions)
+ int32_t *positions, uintptr_t data[])
{
uint64_t hits = 0;
uint64_t next_mask = 0;
uint64_t extra_hits_mask = 0;
uint64_t lookup_mask;
unsigned idx;
- const void *key_store = h->key_store;
+ const struct rte_hash_key *key_store = h->key_store;
unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31;
const struct rte_hash_bucket *primary_bkt10, *primary_bkt11;
const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11;
const struct rte_hash_bucket *primary_bkt20, *primary_bkt21;
const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21;
- const void *k_slot20, *k_slot21, *k_slot30, *k_slot31;
+ const struct rte_hash_key *k_slot20, *k_slot21, *k_slot30, *k_slot31;
hash_sig_t primary_hash00, primary_hash01;
hash_sig_t secondary_hash00, secondary_hash01;
hash_sig_t primary_hash10, primary_hash11;
@@ -1119,8 +1190,8 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
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, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
}
k_slot30 = k_slot20, k_slot31 = k_slot21;
@@ -1150,8 +1221,8 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
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, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
@@ -1171,14 +1242,14 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
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, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
k_slot30 = k_slot20, k_slot31 = k_slot21;
idx30 = idx20, idx31 = idx21;
- lookup_stage3(idx30, k_slot30, keys, positions, &hits, h);
- lookup_stage3(idx31, k_slot31, keys, positions, &hits, h);
+ lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h);
+ lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h);
/* handle extra_hits_mask */
next_mask |= extra_hits_mask;
@@ -1190,7 +1261,11 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
/* run a single search for each remaining item */
do {
idx = __builtin_ctzl(next_mask);
- positions[idx] = rte_hash_lookup_with_hash(h, keys[idx],
+ if (data != NULL)
+ positions[idx] =
rte_hash_lookup_with_hash_data(h, keys[idx],
+ hash_vals[idx],
&data[idx]);
+ else
+ positions[idx] = rte_hash_lookup_with_hash(h,
keys[idx],
hash_vals[idx]);
next_mask &= ~(1llu << idx);
} while (next_mask);
@@ -1200,6 +1275,17 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
}
int
+rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
+ uint32_t num_keys, int32_t *positions, uintptr_t data[])
+{
+ RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
+ (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
+ (positions == NULL)), -EINVAL);
+
+ return __rte_hash_lookup_bulk(h, keys, num_keys, positions, data);
+}
+
+int
rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
uint32_t num_keys, int32_t *positions)
{
@@ -1207,7 +1293,20 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const
void **keys,
(num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
(positions == NULL)), -EINVAL);
- return __rte_hash_lookup_bulk(h, keys, num_keys, positions);
+ return __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL);
+}
+
+int
+rte_hash_lookup_bulk_with_hash_data(const struct rte_hash *h, const void
**keys,
+ const hash_sig_t *hash_vals, uint32_t num_keys,
+ int32_t *positions, uintptr_t data[])
+{
+ RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
+ (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
+ (positions == NULL)), -EINVAL);
+
+ return __rte_hash_lookup_bulk_with_hash(h, keys, hash_vals, num_keys,
+ positions, data);
}
int
@@ -1220,7 +1319,7 @@ rte_hash_lookup_bulk_with_hash(const struct rte_hash *h,
const void **keys,
(positions == NULL)), -EINVAL);
return __rte_hash_lookup_bulk_with_hash(h, keys, hash_vals, num_keys,
- positions);
+ positions, NULL);
}
/* Functions to compare multiple of 16 byte keys (up to 128 bytes) */
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index fa327c2..940e5db 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -89,7 +89,6 @@ struct rte_hash_parameters {
/** @internal A hash table structure. */
struct rte_hash;
-
/**
* Create a new hash table.
*
@@ -140,6 +139,50 @@ void
rte_hash_reset(struct rte_hash *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
+ * - -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
+rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t
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
+ * - -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
+rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key,
+ hash_sig_t sig, uintptr_t data);
+
+/**
* Add a key to an existing hash table. This operation is not multi-thread safe
* and should only be called from one thread.
*
@@ -216,6 +259,51 @@ rte_hash_del_key(const struct rte_hash *h, const void
*key);
int32_t
rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
hash_sig_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
+ * Data to return.
+ * @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
+rte_hash_lookup_data(const struct rte_hash *h, const void *key, uintptr_t
*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
+ * Pointer to data returned 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
+rte_hash_lookup_with_hash_data(const struct rte_hash *h, const void *key,
+ hash_sig_t sig, uintptr_t *data);
+
/**
* Find a key in the hash table.
* This operation is multi-thread safe.
@@ -270,7 +358,34 @@ hash_sig_t
rte_hash_hash(const struct rte_hash *h, const void *key);
#define rte_hash_lookup_multi rte_hash_lookup_bulk
+#define rte_hash_lookup_multi_data rte_hash_lookup_bulk_data
#define rte_hash_lookup_multi_with_hash rte_hash_lookup_bulk_with_hash
+#define rte_hash_lookup_multi_with_hash_data
rte_hash_lookup_bulk_with_hash_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 RTE_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.
+ * @param data
+ * Output containing array of data returned from all the successful lookups.
+ * @return
+ * -EINVAL if there's an error, otherwise 0.
+ */
+int
+rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
+ uint32_t num_keys, int32_t *positions, uintptr_t data[]);
+
/**
* Find multiple keys in the hash table.
* This operation is multi-thread safe.
@@ -303,6 +418,33 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void
**keys,
* @param keys
* A pointer to a list of keys to look for.
* @param hash_vals
+ * A pointer to a list of pre-calculated hash values for 'keys'.
+ * @param num_keys
+ * How many keys are in the keys list (less than RTE_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.
+ * @param data
+ * Output containing array of data returned from all the successful lookups.
+ * @return
+ * -EINVAL if there's an error, otherwise 0.
+ */
+int
+rte_hash_lookup_bulk_with_hash_data(const struct rte_hash *h, const void
**keys,
+ const hash_sig_t *hash_vals, uint32_t num_keys,
+ int32_t *positions, uintptr_t 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 hash_vals
* A pointer to a list of pre-calculated hash values.
* @param num_keys
* How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX).
diff --git a/lib/librte_hash/rte_hash_version.map
b/lib/librte_hash/rte_hash_version.map
index f011054..3a4e1a3 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -21,7 +21,13 @@ DPDK_2.0 {
DPDK_2.1 {
global:
+ rte_hash_add_key_data;
+ rte_hash_add_key_with_hash_data;
+ rte_hash_lookup_bulk_data;
rte_hash_lookup_bulk_with_hash;
+ rte_hash_lookup_bulk_with_hash_data;
+ rte_hash_lookup_data;
+ rte_hash_lookup_with_hash_data;
rte_hash_reset;
local: *;
--
2.4.2
