From f9edbc9bb6bcd4a0b7d2cf119200005fe754be5f Mon Sep 17 00:00:00 2001 From: Pablo de Lara Date: Sat, 11 Jul 2015 01:18:53 +0100 Subject: [PATCH] hash: add iterate function Since now rte_hash structure is private, a new function has been added to let the user iterate through the hash table, returning next key and data associated on each iteration, plus the position where they were stored. Signed-off-by: Pablo de Lara Acked-by: Bruce Richardson --- app/test/test_hash.c | 66 ++++++++++++++++++++++++++++ lib/librte_hash/rte_cuckoo_hash.c | 41 +++++++++++++++++ lib/librte_hash/rte_hash.h | 22 ++++++++++ lib/librte_hash/rte_hash_version.map | 1 + 4 files changed, 130 insertions(+) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 448586c830..7f8c0d3914 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -1149,6 +1149,70 @@ static int test_average_table_utilization(void) return 0; } +#define NUM_ENTRIES 1024 +static int test_hash_iteration(void) +{ + struct rte_hash *handle; + unsigned i; + uint8_t keys[NUM_ENTRIES][RTE_HASH_KEY_LENGTH_MAX]; + const void *next_key; + void *next_data; + void *data[NUM_ENTRIES]; + unsigned added_keys; + uint32_t iter = 0; + int ret = 0; + + ut_params.entries = NUM_ENTRIES; + ut_params.name = "test_hash_iteration"; + ut_params.hash_func = rte_jhash; + ut_params.key_len = 16; + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Add random entries until key cannot be added */ + for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) { + data[added_keys] = (void *) ((uintptr_t) rte_rand()); + for (i = 0; i < ut_params.key_len; i++) + keys[added_keys][i] = rte_rand() % 255; + ret = rte_hash_add_key_data(handle, keys[added_keys], data[added_keys]); + if (ret < 0) + break; + } + + /* Iterate through the hash table */ + while (rte_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) { + /* Search for the key in the list of keys added */ + for (i = 0; i < NUM_ENTRIES; i++) { + if (memcmp(next_key, keys[i], ut_params.key_len) == 0) { + if (next_data != data[i]) { + printf("Data found in the hash table is" + "not the data added with the key\n"); + goto err; + } + added_keys--; + break; + } + } + if (i == NUM_ENTRIES) { + printf("Key found in the hash table was not added\n"); + goto err; + } + } + + /* Check if all keys have been iterated */ + if (added_keys != 0) { + printf("There were still %u keys to iterate\n", added_keys); + goto err; + } + + rte_hash_free(handle); + return 0; + +err: + rte_hash_free(handle); + return -1; +} + static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, @@ -1408,6 +1472,8 @@ test_hash(void) return -1; if (test_average_table_utilization() < 0) return -1; + if (test_hash_iteration() < 0) + return -1; run_hash_func_tests(); diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 029b55be3b..39cafb700f 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -1081,6 +1081,47 @@ rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, return __builtin_popcountl(*hit_mask); } +int32_t +rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next) +{ + uint32_t bucket_idx, idx, position; + struct rte_hash_key *next_key; + + RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL); + + const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES; + /* Out of bounds */ + if (*next >= total_entries) + return -ENOENT; + + /* Calculate bucket and index of current iterator */ + bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES; + idx = *next % RTE_HASH_BUCKET_ENTRIES; + + /* If current position is empty, go to the next one */ + while (h->buckets[bucket_idx].signatures[idx].sig == NULL_SIGNATURE) { + (*next)++; + /* End of table */ + if (*next == total_entries) + return -ENOENT; + bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES; + idx = *next % RTE_HASH_BUCKET_ENTRIES; + } + + /* Get position of entry in key table */ + position = h->buckets[bucket_idx].key_idx[idx]; + next_key = (struct rte_hash_key *) ((char *)h->key_store + + position * h->key_entry_size); + /* Return key and data */ + *key = next_key->key; + *data = next_key->pdata; + + /* Increment iterator */ + (*next)++; + + return (position - 1); +} + /* Functions to compare multiple of 16 byte keys (up to 128 bytes) */ static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused) diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index ff75445651..68109d5182 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -393,6 +393,28 @@ rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, int rte_hash_lookup_bulk(const struct rte_hash *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 +rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next); #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index 40c927502b..906c8ad57c 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -25,6 +25,7 @@ DPDK_2.1 { rte_hash_add_key_data; rte_hash_add_key_with_hash_data; rte_hash_create; + rte_hash_iterate; rte_hash_lookup_bulk_data; rte_hash_lookup_data; rte_hash_lookup_with_hash_data; -- 2.20.1