- * Try to delete to-be-replaced node. Don't gc yet. Not
- * performing gc here is important, because this lets
- * concurrent lookups see the old node until we
- * atomically swap the new node into its place.
- *
- * This algorithm is _not_ strictly lock-free between
- * _cds_lfht_del and the uatomic_cmpxchg of the
- * replacement operation, so a replacement should _not_
- * crash here (which means: don't do replacements if you
- * need strict lock-free guarantees).
- */
- if (!replace_pinned) {
- if (_cds_lfht_del(ht, size, clear_flag(iter), 0, 0))
- continue; /* concurrently removed. retry. */
- }
- /*
- * After _cds_lfht_del succeeds, we have pinned the
- * to-be-removed node in place by setting its removed
- * flag, but not its gc flag. If we fail to cmpxchg our
- * new node with this node, we need to retry everything
- * from the initial lookup, and only stop when we reach
- * the node we pinned into place.
+ * 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.