X-Git-Url: https://git.liburcu.org/?a=blobdiff_plain;f=rculfhash.c;h=556ec36ddab261625d3c3b412496718c790d0c0b;hb=18117871130163ec2b2fc73fda288b9ba26cd435;hp=5baa2d415b34483486ece296cb9c511ae2cf0714;hpb=479c8a32f3a1c319e9e1a18692b47992d393ee38;p=urcu.git

diff --git a/rculfhash.c b/rculfhash.c
index 5baa2d4..556ec36 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -234,13 +234,17 @@ void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
 }
 
 static
-int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
-	     int unique)
+struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t,
+			    struct rcu_ht_node *node, int unique)
 {
 	struct rcu_ht_node *iter_prev, *dummy, *iter, *next;
+	unsigned long hash;
 
-	if (!t->size)
-		return 0;
+	if (!t->size) {
+		assert(node->dummy);
+		return node;	/* Initial first add (head) */
+	}
+	hash = bit_reverse_ulong(node->reverse_hash);
 	for (;;) {
 		uint32_t chain_len = 0;
 
@@ -248,7 +252,7 @@ int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
 		 * iter_prev points to the non-removed node prior to the
 		 * insert location.
 		 */
-		iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
+		iter_prev = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 		/* We can always skip the dummy node initially */
 		iter = rcu_dereference(iter_prev->next);
 		assert(iter_prev->reverse_hash <= node->reverse_hash);
@@ -259,7 +263,13 @@ int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
 				goto insert;
 			next = rcu_dereference(clear_flag(iter)->next);
 			if (is_removed(next))
-				goto gc;
+				goto gc_node;
+			if (unique
+			    && !clear_flag(iter)->dummy
+			    && !ht->compare_fct(node->key, node->key_len,
+						clear_flag(iter)->key,
+						clear_flag(iter)->key_len))
+				return clear_flag(iter);
 			/* Only account for identical reverse hash once */
 			if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash)
 				check_resize(ht, t, ++chain_len);
@@ -276,17 +286,16 @@ int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
 			continue;	/* retry */
 		else
 			goto gc_end;
-	gc:
-		/* Garbage collect logically removed nodes in the bucket */
-		dummy = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
-		_ht_gc_bucket(dummy, node);
+	gc_node:
+		assert(!is_removed(iter));
+		(void) uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next));
 		/* retry */
 	}
 gc_end:
 	/* Garbage collect logically removed nodes in the bucket */
-	dummy = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
+	dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 	_ht_gc_bucket(dummy, node);
-	return 0;
+	return node;
 }
 
 static
@@ -294,6 +303,7 @@ int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 {
 	struct rcu_ht_node *dummy, *next, *old;
 	int flagged = 0;
+	unsigned long hash;
 
 	/* logically delete the node */
 	old = rcu_dereference(node->next);
@@ -314,7 +324,8 @@ int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 	 * the node, and remove it (along with any other logically removed node)
 	 * if found.
 	 */
-	dummy = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
+	hash = bit_reverse_ulong(node->reverse_hash);
+	dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 	_ht_gc_bucket(dummy, node);
 end:
 	/*
@@ -341,7 +352,6 @@ void init_table(struct rcu_ht *ht, struct rcu_table *t,
 			t->size = i;
 		t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
 		t->tbl[i]->dummy = 1;
-		t->tbl[i]->hash = i;
 		t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
 		(void) _ht_add(ht, t, t->tbl[i], 0);
 	}
@@ -392,9 +402,9 @@ struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
 			node = NULL;
 			break;
 		}
-		if (!ht->compare_fct(node->key, node->key_len, key, key_len)) {
-			if (likely(!is_removed(rcu_dereference(node->next)))
-			    && likely(!node->dummy))
+		if (likely(!is_removed(rcu_dereference(node->next)))
+		    && !node->dummy
+		    && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
 				break;
 		}
 		node = clear_flag(rcu_dereference(node->next));
@@ -406,20 +416,22 @@ struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
 void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
 {
 	struct rcu_table *t;
+	unsigned long hash;
 
-	node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
-	node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
+	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	t = rcu_dereference(ht->t);
 	(void) _ht_add(ht, t, node, 0);
 }
 
-int ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
+struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
 {
 	struct rcu_table *t;
+	unsigned long hash;
 
-	node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
-	node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
+	hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
+	node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 
 	t = rcu_dereference(ht->t);
 	return _ht_add(ht, t, node, 1);