DPDK patches and discussions
 help / color / mirror / Atom feed
From: Pablo de Lara <pablo.de.lara.guarch@intel.com>
To: dev@dpdk.org
Subject: [dpdk-dev] [PATCH v5 4/7] hash: add iterate function
Date: Fri, 10 Jul 2015 22:57:44 +0100	[thread overview]
Message-ID: <1436565467-13328-5-git-send-email-pablo.de.lara.guarch@intel.com> (raw)
In-Reply-To: <1436565467-13328-1-git-send-email-pablo.de.lara.guarch@intel.com>

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 <pablo.de.lara.guarch@intel.com>
---
 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 448586c..f5277c9 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;
+	uintptr_t next_data;
+	uintptr_t 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] = 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 5777036..5796ef4 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, uintptr_t *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->idata;
+
+	/* 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 15f8b2f..a2e7f74 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, uintptr_t *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 a97eac1..5653cb7 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.4.3

  parent reply	other threads:[~2015-07-10 21:58 UTC|newest]

Thread overview: 92+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-06-05 14:33 [dpdk-dev] [PATCH 0/6] Cuckoo hash Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 1/6] eal: add const in prefetch functions Pablo de Lara
2015-06-16 15:10   ` Bruce Richardson
2015-06-05 14:33 ` [dpdk-dev] [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-17 15:31   ` Bruce Richardson
2015-06-18  9:50   ` Bruce Richardson
2015-06-05 14:33 ` [dpdk-dev] [PATCH 3/6] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 4/6] hash: add new functions rte_hash_rehash and rte_hash_reset Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 5/6] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 6/6] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-16 13:44 ` [dpdk-dev] [PATCH 0/6] Cuckoo hash Thomas Monjalon
2015-06-16 21:44   ` De Lara Guarch, Pablo
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 00/11] " Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-26 16:49     ` Stephen Hemminger
2015-06-28 22:23       ` De Lara Guarch, Pablo
2015-06-30  7:36         ` Stephen Hemminger
2015-07-10 10:39         ` Bruce Richardson
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 11/11] doc: update hash documentation Pablo de Lara
2015-06-28 22:25   ` [dpdk-dev] [PATCH v3 00/11] Cuckoo hash Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 11/11] doc: update hash documentation Pablo de Lara
2015-07-08 23:23     ` [dpdk-dev] [PATCH v3 00/11] Cuckoo hash Thomas Monjalon
2015-07-09  8:02       ` Bruce Richardson
2015-07-10 17:24     ` [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of " Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 4/7] hash: add iterate function Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 20:52       ` [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 21:57       ` [dpdk-dev] [PATCH v5 " Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 21:57         ` Pablo de Lara [this message]
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 22:52         ` [dpdk-dev] [PATCH v5 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 23:30         ` [dpdk-dev] [PATCH v6 " Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 4/7] hash: add iterate function Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 7/7] doc: update hash documentation Pablo de Lara
2015-07-11  0:18           ` [dpdk-dev] [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Pablo de Lara
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-12 22:29               ` Thomas Monjalon
2015-07-13 16:11                 ` Bruce Richardson
2015-07-13 16:14                   ` Bruce Richardson
2015-07-13 16:20                     ` Thomas Monjalon
2015-07-13 16:26                       ` Bruce Richardson
2015-07-16  9:39               ` Tony Lu
2015-07-16 20:42                 ` De Lara Guarch, Pablo
2015-07-17  3:34                   ` Tony Lu
2015-07-17  7:34                     ` De Lara Guarch, Pablo
2015-07-17  7:58                       ` Tony Lu
2015-07-17  9:06                         ` De Lara Guarch, Pablo
2015-07-17 14:39                           ` Tony Lu
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-12 22:16               ` Thomas Monjalon
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-12 22:00               ` Thomas Monjalon
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 4/7] hash: add iterate function Pablo de Lara
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-12 22:38               ` Thomas Monjalon
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 7/7] doc: update hash documentation Pablo de Lara
2015-07-12 22:46             ` [dpdk-dev] [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Thomas Monjalon

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1436565467-13328-5-git-send-email-pablo.de.lara.guarch@intel.com \
    --to=pablo.de.lara.guarch@intel.com \
    --cc=dev@dpdk.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).