[ltt-dev] [PATCH 2/9] keep the last position for failed lookup

[Lai Jiangshan]

Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
 rculfhash.c            |   19 +++++++++++--------
 tests/test_urcu_hash.c |    5 +++--
 urcu/rculfhash.h       |   17 +++++++++++------
 3 files changed, 25 insertions(+), 16 deletions(-)

diff --git a/rculfhash.c b/rculfhash.c
index bda3bd6..cbfc79e 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -1381,27 +1381,28 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
 	return ht;
 }
 
-void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+bool cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		cds_lfht_match_fct match, void *key,
 		struct cds_lfht_iter *iter)
 {
-	struct cds_lfht_node *node, *next, *bucket;
+	struct cds_lfht_node *prev, *node, *next;
 	unsigned long reverse_hash, size;
 
 	reverse_hash = bit_reverse_ulong(hash);
 
 	size = rcu_dereference(ht->t.size);
-	bucket = lookup_bucket(ht, size, hash);
+	node = lookup_bucket(ht, size, hash);
+	next = rcu_dereference(node->next);
+	prev = node;
 	/* We can always skip the bucket node initially */
-	node = rcu_dereference(bucket->next);
-	node = clear_flag(node);
+	node = clear_flag(next);
 	for (;;) {
 		if (caa_unlikely(is_end(node))) {
-			node = next = NULL;
+			node = prev;
 			break;
 		}
 		if (caa_unlikely(node->reverse_hash > reverse_hash)) {
-			node = next = NULL;
+			node = prev;
 			break;
 		}
 		next = rcu_dereference(node->next);
@@ -1412,11 +1413,13 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		    && caa_likely(match(node, key))) {
 				break;
 		}
+		prev = node;
 		node = clear_flag(next);
 	}
-	assert(!node || !is_bucket(rcu_dereference(node->next)));
+	assert(node == prev || !is_bucket(rcu_dereference(node->next)));
 	iter->node = node;
 	iter->next = next;
+	return node != prev;
 }
 
 void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match,
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 509767c..bae6ed2 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -440,8 +440,9 @@ void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 {
 	assert(key_len == sizeof(unsigned long));
 
-	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
-			test_match, key, iter);
+	if (!cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
+			test_match, key, iter))
+		iter->node = iter->next = NULL;
 }
 
 void *thr_count(void *arg)
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index c13d3df..7d919d0 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -26,6 +26,7 @@
  */
 
 #include <stdint.h>
+#include <stdbool.h>
 #include <urcu/compiler.h>
 #include <urcu-call-rcu.h>
 
@@ -180,12 +181,15 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
  * @hash: the key hash.
  * @match: the key match function.
  * @key: the current node key.
- * @iter: Node, if found (output). *iter->node set to NULL if not found.
+ * @iter: Node, if found (output).
+ *        The last lookup node(maybe a bucket/removed node), if not found.
  *
  * Call with rcu_read_lock held.
  * Threads calling this API need to be registered RCU read-side threads.
+ *
+ * Return true if a match node is found
  */
-void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
+bool cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
 		cds_lfht_match_fct match, void *key,
 		struct cds_lfht_iter *iter);
 
@@ -374,8 +378,8 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 			node = cds_lfht_iter_get_node(iter))
 
 #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node)	\
-	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
-			node = cds_lfht_iter_get_node(iter);		\
+	for (node = cds_lfht_lookup(ht, hash, match, key, iter) ?	\
+			cds_lfht_iter_get_node(iter) : NULL;		\
 		node != NULL;						\
 		cds_lfht_next_duplicate(ht, match, key, iter),		\
 			node = cds_lfht_iter_get_node(iter))
@@ -391,8 +395,9 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size);
 
 #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key,		\
 				iter, pos, member)			\
-	for (cds_lfht_lookup(ht, hash, match, key, iter),		\
-			pos = caa_container_of(cds_lfht_iter_get_node(iter), \
+	for (pos = caa_container_of(					\
+			cds_lfht_lookup(ht, hash, match, key, iter) ?	\
+			cds_lfht_iter_get_node(iter) : NULL,		\
 					typeof(*(pos)), member);	\
 		&(pos)->member != NULL;					\
 		cds_lfht_next_duplicate(ht, match, key, iter),		\
-- 
1.7.4.4