+int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size,
+ struct cds_lfht_node *old_node,
+ struct cds_lfht_node *ret_next,
+ struct cds_lfht_node *new_node)
+{
+ struct cds_lfht_node *dummy, *old_next;
+ struct _cds_lfht_node *lookup;
+ int flagged = 0;
+ unsigned long hash, index, order;
+
+ if (!old_node) /* Return -ENOENT if asked to replace NULL node */
+ goto end;
+
+ assert(!is_removed(old_node));
+ assert(!is_dummy(old_node));
+ assert(!is_removed(new_node));
+ assert(!is_dummy(new_node));
+ assert(new_node != old_node);
+ do {
+ /* Insert after node to be replaced */
+ old_next = ret_next;
+ if (is_removed(old_next)) {
+ /*
+ * Too late, the old node has been removed under us
+ * between lookup and replace. Fail.
+ */
+ goto end;
+ }
+ assert(!is_dummy(old_next));
+ assert(new_node != clear_flag(old_next));
+ new_node->p.next = clear_flag(old_next);
+ /*
+ * Here is the whole trick for lock-free replace: we add
+ * the replacement node _after_ the node we want to
+ * replace by atomically setting its next pointer at the
+ * same time we set its removal flag. Given that
+ * the lookups/get next use an iterator aware of the
+ * next pointer, they will either skip the old node due
+ * to the removal flag and see the new node, or use
+ * the old node, but will not see the new one.
+ */
+ ret_next = uatomic_cmpxchg(&old_node->p.next,
+ old_next, flag_removed(new_node));
+ } while (ret_next != old_next);
+
+ /* We performed the replacement. */
+ flagged = 1;
+
+ /*
+ * Ensure that the old node is not visible to readers anymore:
+ * lookup for the node, and remove it (along with any other
+ * logically removed node) if found.
+ */
+ hash = bit_reverse_ulong(old_node->p.reverse_hash);
+ assert(size > 0);
+ index = hash & (size - 1);
+ order = get_count_order_ulong(index + 1);
+ lookup = &ht->t.tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))];
+ dummy = (struct cds_lfht_node *) lookup;
+ _cds_lfht_gc_bucket(dummy, new_node);
+end:
+ /*
+ * Only the flagging action indicated that we (and no other)
+ * replaced the node from the hash table.
+ */
+ if (flagged) {
+ assert(is_removed(rcu_dereference(old_node->p.next)));
+ return 0;
+ } else {
+ return -ENOENT;
+ }
+}
+
+static
+struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
+ unsigned long size,
+ struct cds_lfht_node *node,
+ enum add_mode mode, int dummy)