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
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_hash.c | 284 ++++++++++++++++++++++++-----------
lib/librte_hash/rte_hash.h | 180 ++++++++++++++++++++++
lib/librte_hash/rte_hash_version.map | 8 +
3 files changed, 385 insertions(+), 87 deletions(-)
diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c
index 0b7f543..c1be7b0 100644
--- a/lib/librte_hash/rte_hash.c
+++ b/lib/librte_hash/rte_hash.c
@@ -177,7 +177,7 @@ rte_hash_create(const struct rte_hash_parameters *params)
/* Total memory required for hash context */
mem_size = hash_struct_size + tbl_size;
- key_entry_size = params->key_len;
+ key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
@@ -335,7 +335,7 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket
*bkt, uint32_t key_i
/* idx = 0 if primary, 1 if secondary */
unsigned idx;
static unsigned number_pushes;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
unsigned i, j;
uint64_t hash_stored;
@@ -358,8 +358,8 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket
*bkt, uint32_t key_i
* is very likely that it has entered in a loop, need rehasing
*/
if (++number_pushes > 1 && hash == original_hash) {
- k = (char *)keys + key_idx * h->key_entry_size;
- if (!memcmp(k, original_key, h->key_len)) {
+ k = (struct rte_hash_key *) ((char *)keys + key_idx *
h->key_entry_size);
+ if (!memcmp(k->key, original_key, h->key_len)) {
rte_ring_sp_enqueue(h->free_slots, (void
*)((uintptr_t)key_idx));
number_pushes = 0;
/*
@@ -381,10 +381,11 @@ run_cuckoo(const struct rte_hash *h, struct
rte_hash_bucket *bkt, uint32_t key_i
*/
idx = !(bkt->signatures[i] & (h->sig_secondary));
key_idx_stored = bkt->key_idx[i];
- k = (char *)keys + key_idx_stored * h->key_entry_size;
+ k = (struct rte_hash_key *) ((char *)keys +
+ key_idx_stored *
h->key_entry_size);
if (idx == 0)
- hash_stored = rte_hash_hash(h, k);
+ hash_stored = rte_hash_hash(h, k->key);
else
hash_stored =
rte_hash_secondary_hash(bkt->signatures[i]);
@@ -430,7 +431,7 @@ rte_hash_rehash(struct rte_hash *h, rte_hash_function
hash_func,
uint32_t tbl_size, mem_size, bucket_size, hash_struct_size;
uint64_t hash;
struct rte_hash_bucket *bkt;
- void *k;
+ struct rte_hash_key *k;
struct rte_hash *sec_h;
uint32_t bucket_idx;
int32_t ret;
@@ -458,16 +459,16 @@ rte_hash_rehash(struct rte_hash *h, rte_hash_function
hash_func,
for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
/* Check if entry in bucket is not empty */
if (h->buckets[i].signatures[j] != NULL_SIGNATURE) {
- k = (char *)h->key_store +
- h->buckets[i].key_idx[j] *
h->key_entry_size;
+ k = (struct rte_hash_key *) ((char
*)h->key_store +
+ h->buckets[i].key_idx[j] *
h->key_entry_size);
/* Get new hash (with new initial value) */
- hash = rte_hash_hash(sec_h, k);
+ hash = rte_hash_hash(sec_h, k->key);
bucket_idx = hash & sec_h->bucket_bitmask;
hash |= sec_h->sig_msb;
bkt = &sec_h->buckets[bucket_idx];
/* Add entry on secondary hash table */
ret = run_cuckoo(sec_h, bkt,
h->buckets[i].key_idx[j],
- hash, hash, k);
+ hash, hash, k->key);
if (ret == -EAGAIN)
goto exit;
num_entries++;
@@ -489,12 +490,12 @@ exit:
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)
{
uint64_t hash0, bucket_idx0, hash1, bucket_idx1;
unsigned i;
struct rte_hash_bucket *bkt0, *bkt1;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
void *slot_id;
hash0 = sig;
@@ -515,28 +516,39 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h,
const void *key,
/* Check if key is already inserted in primary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt0->signatures[i] == hash0) {
- k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size;
- if (memcmp(key, k, h->key_len) == 0)
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt0->key_idx[i] * h->key_entry_size);
+ if (memcmp(key, k->key, h->key_len) == 0) {
+ /* Update data */
+ k->idata = data;
return bkt0->key_idx[i];
+ }
}
}
/* Check if key is already inserted in secondary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt1->signatures[i] == hash1) {
- k = (char *)keys + bkt1->key_idx[i] * h->key_entry_size;
- if (memcmp(key, k, h->key_len) == 0)
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt1->key_idx[i] * h->key_entry_size);
+ if (memcmp(key, k->key, h->key_len) == 0) {
+ /* Update data */
+ k->idata = data;
return bkt1->key_idx[i];
+ }
}
}
- k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size;
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt0->key_idx[i] * h->key_entry_size);
if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)
return -ENOSPC;
- /* Copy key*/
- k = (char *)keys + (uintptr_t)slot_id * h->key_entry_size;
- memcpy(k, key, h->key_len);
+ /* Copy key and data */
+ k = (struct rte_hash_key *)((char *)keys +
+ (uintptr_t)slot_id * h->key_entry_size);
+ memcpy(k->key, key, h->key_len);
+ k->idata = data;
/* Run cuckoo algorithm */
return run_cuckoo(h, bkt0, (uint32_t)((uintptr_t) slot_id), hash0,
hash0, key);
@@ -547,24 +559,39 @@ 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)
{
uint64_t hash, bucket_idx;
unsigned i;
struct rte_hash_bucket *bkt;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
hash = sig;
bucket_idx = hash & h->bucket_bitmask;
@@ -575,9 +602,13 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key,
/* Check if key is in primary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i] == hash) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (memcmp(key, k, h->key_len) == 0)
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (memcmp(key, k->key, h->key_len) == 0) {
+ if (data != NULL)
+ *data = k->idata;
return bkt->key_idx[i];
+ }
}
}
@@ -594,9 +625,13 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h,
const void *key,
/* Check if key is in secondary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i] == hash) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (memcmp(key, k, h->key_len) == 0)
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (memcmp(key, k->key, h->key_len) == 0) {
+ if (data != NULL)
+ *data = k->idata;
return bkt->key_idx[i];
+ }
}
}
@@ -604,28 +639,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)
+ hash_sig_t sig, uintptr_t *data)
{
uint64_t hash, bucket_idx;
unsigned i;
struct rte_hash_bucket *bkt;
- void *k, *keys = h->key_store;
+ struct rte_hash_key *k, *keys = h->key_store;
hash = sig;
bucket_idx = hash & h->bucket_bitmask;
@@ -636,8 +686,11 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h,
const void *key,
/* Check if key is in primary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i] == hash) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (memcmp(key, k, h->key_len) == 0) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (memcmp(key, k->key, h->key_len) == 0) {
+ if (data != NULL)
+ data[i] = k->idata;
bkt->signatures[i] = NULL_SIGNATURE;
rte_ring_sp_enqueue(h->free_slots,
(void
*)((uintptr_t)bkt->key_idx[i]));
@@ -657,8 +710,11 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h,
const void *key,
/* Check if key is in secondary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
if (bkt->signatures[i] == hash) {
- k = (char *)keys + bkt->key_idx[i] * h->key_entry_size;
- if (memcmp(key, k, h->key_len) == 0) {
+ k = (struct rte_hash_key *) ((char *)keys +
+ bkt->key_idx[i] * h->key_entry_size);
+ if (memcmp(key, k->key, h->key_len) == 0) {
+ if (data != NULL)
+ data[i] = k->idata;
bkt->signatures[i] = NULL_SIGNATURE;
rte_ring_sp_enqueue(h->free_slots,
(void
*)((uintptr_t)bkt->key_idx[i]));
@@ -671,18 +727,33 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h,
const void *key,
}
int32_t
+rte_hash_del_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_del_key_with_hash(h, key, sig, data);
+}
+
+int32_t
+rte_hash_del_key_data(const struct rte_hash *h, const void *key, uintptr_t
*data)
+{
+ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+ return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key),
data);
+}
+
+int32_t
rte_hash_del_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_del_key_with_hash(h, key, sig);
+ return __rte_hash_del_key_with_hash(h, key, sig, NULL);
}
int32_t
rte_hash_del_key(const struct rte_hash *h, const void *key)
{
RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
- return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
+ return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key),
NULL);
}
/* Lookup bulk stage 0: Calculate next primary/secondary hash value (from new
key) */
@@ -748,10 +819,10 @@ static inline void
lookup_stage2(unsigned idx, uint64_t primary_hash, uint64_t secondary_hash,
const struct rte_hash_bucket *primary_bkt,
const struct rte_hash_bucket *secondary_bkt,
- const void **key_slot,
+ const struct rte_hash_key **key_slot,
int32_t *positions,
uint64_t *extra_hits_mask,
- const void *keys, const struct rte_hash *h)
+ const struct rte_hash_key *keys, const struct rte_hash *h)
{
unsigned primary_hash_matches, secondary_hash_matches, key_idx, i;
unsigned total_hash_matches;
@@ -775,7 +846,8 @@ lookup_stage2(unsigned idx, uint64_t primary_hash, uint64_t
secondary_hash,
if (key_idx == 0)
key_idx =
secondary_bkt->key_idx[__builtin_ctzl(secondary_hash_matches)];
- *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);
positions[idx] = key_idx;
@@ -787,15 +859,20 @@ lookup_stage2(unsigned idx, uint64_t primary_hash,
uint64_t secondary_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 = !memcmp(key_slot, keys[idx], h->key_len);
+ if (values != NULL)
+ values[idx] = key_slot->idata;
+ hit = !memcmp(key_slot->key, keys[idx], h->key_len);
if (unlikely(hit == 0))
positions[idx] = -ENOENT;
*hits = (uint64_t)(hit) << idx;
@@ -803,21 +880,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;
uint64_t primary_hash00, primary_hash01;
uint64_t secondary_hash00, secondary_hash01;
uint64_t primary_hash10, primary_hash11;
@@ -830,6 +907,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void
**keys,
else
lookup_mask = (1 << num_keys) - 1;
+
lookup_stage0(&idx00, &lookup_mask, &primary_hash00,
&secondary_hash00, keys, h);
lookup_stage0(&idx01, &lookup_mask, &primary_hash01,
@@ -912,8 +990,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;
@@ -942,8 +1020,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;
@@ -963,14 +1041,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;
@@ -982,7 +1060,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);
}
@@ -993,21 +1075,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;
uint64_t primary_hash00, primary_hash01;
uint64_t secondary_hash00, secondary_hash01;
uint64_t primary_hash10, primary_hash11;
@@ -1020,10 +1102,10 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
else
lookup_mask = (1 << num_keys) - 1;
- lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
- &secondary_hash00, hash_vals, h);
- lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
- &secondary_hash01, hash_vals, h);
+ lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
&secondary_hash00,
+ hash_vals, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
&secondary_hash01,
+ hash_vals, h);
primary_hash10 = primary_hash00;
primary_hash11 = primary_hash01;
@@ -1031,10 +1113,10 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
secondary_hash11 = secondary_hash01;
idx10 = idx00, idx11 = idx01;
- lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
- &secondary_hash00, hash_vals, h);
- lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
- &secondary_hash01, hash_vals, h);
+ lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
&secondary_hash00,
+ hash_vals, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
&secondary_hash01,
+ hash_vals, h);
lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10,
&secondary_bkt10, h);
lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11,
@@ -1055,10 +1137,10 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
secondary_hash11 = secondary_hash01;
idx10 = idx00, idx11 = idx01;
- lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
- &secondary_hash00, hash_vals, h);
- lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
- &secondary_hash01, hash_vals, h);
+ lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
&secondary_hash00,
+ hash_vals, h);
+ lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
&secondary_hash01,
+ hash_vals, h);
lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10,
&secondary_bkt10, h);
lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11,
@@ -1089,9 +1171,9 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash
*h, const void **keys,
idx10 = idx00, idx11 = idx01;
lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00,
- &secondary_hash00, hash_vals, h);
+ &secondary_hash00, hash_vals, h);
lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01,
- &secondary_hash01, hash_vals, h);
+ &secondary_hash01, hash_vals, h);
lookup_stage1(primary_hash10, secondary_hash10,
&primary_bkt10, &secondary_bkt10, h);
lookup_stage1(primary_hash11, secondary_hash11,
@@ -1102,8 +1184,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;
@@ -1133,8 +1215,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;
@@ -1154,14 +1236,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;
@@ -1173,7 +1255,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);
@@ -1183,6 +1269,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)
{
@@ -1190,7 +1287,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
@@ -1203,5 +1313,5 @@ 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);
}
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index c92d935..d832b09 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -119,6 +119,15 @@ struct rte_hash {
to the key table*/
};
+struct rte_hash_key {
+ union {
+ uintptr_t idata;
+ void *pdata;
+ };
+ /* Variable key size */
+ char key[] __attribute__((aligned(KEY_ALIGNMENT)));
+};
+
/** Bucket structure */
struct rte_hash_bucket {
uint64_t signatures[RTE_HASH_BUCKET_ENTRIES];
@@ -194,6 +203,47 @@ void
rte_hash_reset(struct rte_hash *h);
/**
+ * Add a pair key/data 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.
+ * - -EAGAIN if key could not be added (table needs rehash)
+ * - -ENOSPC if there is no space in the hash for this key.
+ * - 0 if key was added successfully
+ */
+int32_t
+rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t
data);
+
+/**
+ * Add a pair key/data 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
+ * Hash value to add to the hash table.
+ * @param data
+ * Data to add to the hash table.
+ * @return
+ * - -EINVAL if the parameters are invalid.
+ * - -EAGAIN if key could not be added (table needs rehash)
+ * - -ENOSPC if there is no space in the hash for this key.
+ * - 0 if key was added successfully
+ */
+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.
*
@@ -237,6 +287,45 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const
void *key, hash_sig_t
* Hash table to remove the key from.
* @param key
* Key to remove from the hash table.
+ * @param data
+ * Pointer to data returned from the hash table.
+ * @return
+ * - -EINVAL if the parameters are invalid.
+ * - -ENOENT if the key is not found.
+ * - 0 if key was deleted successfully
+ */
+int32_t
+rte_hash_del_key_data(const struct rte_hash *h, const void *key, uintptr_t
*data);
+
+/**
+ * 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
+ * Hash value to remove from the hash table.
+ * @param data
+ * Pointer to data returned from the hash table.
+ * @return
+ * - -EINVAL if the parameters are invalid.
+ * - -ENOENT if the key is not found.
+ * - 0 if key was deleted successfully
+ */
+int32_t
+rte_hash_del_key_with_hash_data(const struct rte_hash *h, const void *key,
+ hash_sig_t sig, uintptr_t
*data);
+
+/**
+ * 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.
@@ -263,6 +352,44 @@ 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 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.
+ * - 0 if key was found successfully
+ */
+int32_t
+rte_hash_lookup_data(const struct rte_hash *h, const void *key, uintptr_t
*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.
+ * @param sig
+ * Hash value to find.
+ * @param data
+ * Pointer to data returned from the hash table.
+ * @return
+ * - -EINVAL if the parameters are invalid.
+ * - -ENOENT if the key is not found.
+ * - 0 if key was found successfully
+ */
+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.
*
@@ -296,7 +423,33 @@ int32_t
rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
hash_sig_t sig);
#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.
*
@@ -336,6 +489,33 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void
**keys,
* 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).
+ * @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 number of hits.
*/
diff --git a/lib/librte_hash/rte_hash_version.map
b/lib/librte_hash/rte_hash_version.map
index 0a78756..1b06e37 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -21,7 +21,15 @@ DPDK_2.0 {
DPDK_2.1 {
global:
+ rte_hash_add_key_data;
+ rte_hash_add_key_with_hash_data;
+ rte_hash_del_key_data;
+ rte_hash_del_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_rehash;
rte_hash_reset;
--
2.4.2
