From mboxrd@z Thu Jan 1 00:00:00 1970 From: laijs@cn.fujitsu.com (Lai Jiangshan) Date: Mon, 14 Nov 2011 12:50:52 +0800 Subject: [ltt-dev] [PATCH 2/9] keep the last position for failed lookup In-Reply-To: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> References: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> Message-ID: <1321246259-21223-3-git-send-email-laijs@cn.fujitsu.com> Signed-off-by: Lai Jiangshan --- 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 +#include #include #include @@ -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