#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))
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
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);
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;
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;
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;
}