From 4e9b9fbf56ad649395778b7385baaa44d8db032c Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 27 Sep 2011 17:24:55 -0400 Subject: [PATCH] Add cds_lfht_first/cds_lfht_next for hash table iteration Signed-off-by: Mathieu Desnoyers --- rculfhash.c | 38 ++++++++++++++++++++++++++++++++++++++ urcu/rculfhash.h | 17 +++++++++++++++++ 2 files changed, 55 insertions(+) diff --git a/rculfhash.c b/rculfhash.c index 50b7834..c7a429e 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -1391,6 +1391,44 @@ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter) iter->next = next; } +void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter) +{ + struct cds_lfht_node *node, *next; + + node = iter->node; + next = iter->next; + node = clear_flag(next); + + for (;;) { + if (unlikely(is_end(node))) { + node = next = NULL; + break; + } + next = rcu_dereference(node->p.next); + if (likely(!is_removed(next)) + && !is_dummy(next)) { + break; + } + node = clear_flag(next); + } + assert(!node || !is_dummy(rcu_dereference(node->p.next))); + iter->node = node; + iter->next = next; +} + +void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter) +{ + struct _cds_lfht_node *lookup; + + /* + * Get next after first dummy node. The first dummy node is the + * first node of the linked list. + */ + lookup = &ht->t.tbl[0]->nodes[0]; + iter->node = (struct cds_lfht_node *) lookup; + cds_lfht_next(ht, iter); +} + void cds_lfht_add(struct cds_lfht *ht, struct cds_lfht_node *node) { unsigned long hash, size; diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index 5e149ef..0a739ee 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -197,6 +197,23 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len, */ void cds_lfht_next_duplicate(struct cds_lfht *ht, struct cds_lfht_iter *iter); +/* + * cds_lfht_first - get the first node in the table. + * + * Output in "*iter". *iter->node set to NULL if table is empty. + * Call with rcu_read_lock held. + */ +void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter); + +/* + * cds_lfht_next - get the next node in the table. + * + * Input/Output in "*iter". *iter->node set to NULL if *iter was + * pointing to the last table node. + * Call with rcu_read_lock held. + */ +void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter); + /* * cds_lfht_add - add a node to the hash table. * -- 2.34.1