X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=4abf27a9a5dd5e9f56f97d669de88e58705e741d;hp=497a9eacdebd764771d1e6e2e88a95c019f83724;hb=98f969fc5e7fcd7dcc260dde0ef788e8df50775a;hpb=732ad076c182b3ad706cd62f8a6694f921e1bb7c

diff --git a/rculfhash.c b/rculfhash.c
index 497a9ea..4abf27a 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -46,7 +46,8 @@
 #define dbg_printf(args...)
 #endif
 
-#define BUCKET_SIZE_RESIZE_THRESHOLD	4
+#define CHAIN_LEN_TARGET		4
+#define CHAIN_LEN_RESIZE_THRESHOLD	16
 
 #ifndef max
 #define max(a, b)	((a) > (b) ? (a) : (b))
@@ -165,8 +166,9 @@ static
 void check_resize(struct rcu_ht *ht, struct rcu_table *t,
 		  uint32_t chain_len)
 {
-	if (chain_len >= BUCKET_SIZE_RESIZE_THRESHOLD)
-		ht_resize_lazy(ht, t, log2_u32(chain_len));
+	if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
+		ht_resize_lazy(ht, t,
+			log2_u32(chain_len - CHAIN_LEN_TARGET));
 }
 
 static
@@ -218,12 +220,15 @@ void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 			iter = clear_flag(rcu_dereference(iter_prev->next));
 			if (unlikely(!iter))
 				break;
-			if (iter->reverse_hash < node->reverse_hash)
+			if (iter->reverse_hash > node->reverse_hash)
 				break;
 			iter_prev = iter;
 			check_resize(ht, t, ++chain_len);
 		}
-		/* add in iter_prev->next */
+		/*
+		 * add in iter_prev->next: TODO: check for helping
+		 * delete, for lock-freedom...
+		 */
 		if (is_removed(iter))
 			continue;
 		assert(node != iter);
@@ -253,7 +258,7 @@ retry:
 		iter = clear_flag(rcu_dereference(iter_prev->next));
 		if (unlikely(!iter))
 			break;
-		if (iter->reverse_hash < node->reverse_hash)
+		if (unlikely(iter->reverse_hash > node->reverse_hash))
 			break;
 		if (iter == node) {
 			found = 1;
@@ -284,9 +289,13 @@ retry:
 		flagged = 1;
 	}
 	/*
-	 * Remove the element from the list. Retry if there has been a
-	 * concurrent add (there cannot be a concurrent delete, because
-	 * we won the deletion flag cmpxchg).
+	 * Remove the element from the list.
+	 * Retry if there has been a concurrent add before us.
+	 * Retry if the prev node has been deleted.
+	 * There cannot be a concurrent delete for our position, because
+	 * we won the deletion flag cmpxchg.
+	 * If there is a concurrent add after us, our deletion flag
+	 * makes it busy-loop (FIXME: not lock-free).
 	 */
 	if (uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next)) != iter)
 		goto retry;
@@ -353,12 +362,12 @@ struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
 	for (;;) {
 		if (unlikely(!node))
 			break;
-		if (node->reverse_hash > reverse_hash) {
+		if (unlikely(node->reverse_hash > reverse_hash)) {
 			node = NULL;
 			break;
 		}
 		if (!ht->compare_fct(node->key, node->key_len, key, key_len)) {
-			if (is_removed(rcu_dereference(node->next)))
+			if (unlikely(is_removed(rcu_dereference(node->next))))
 				node = NULL;
 			break;
 		}