The Harris-Michael linked list algorithm in Java for Set

SetImpl.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicMarkableReference;

public class SetImpl<T extends Comparable<T>> implements Set<T> {
    private static final class Node<V> {
        final V value;
        // ref to next node + soft deletion mark of current node
        final AtomicMarkableReference<Node<V>> next;

        Node(Node<V> next) {
            this(/* sentinel */ null, next);
        }

        Node(V value, Node<V> next) {
            this.value = value;
            this.next = new AtomicMarkableReference<>(next, /* not deleted */ false);
        }
    }

    private final Node<T> head;
    private final Node<T> tail;

    public SetImpl() {
        this.tail = new Node<>(null);
        this.head = new Node<>(tail);
    }

    private static final class Window<V> {
        final Node<V> prev;
        final Node<V> curr;

        Window(Node<V> prev, Node<V> curr) {
            this.prev = prev;
            this.curr = curr;
        }
    }

    private Window<T> find(T value) {
        Node<T> prev, curr, next;
        boolean[] currMarkedAsDeleted = {false};
        retry: // restart point: ah sh*t, here we go again
        while (true) {
            prev = head;
            curr = prev.next.getReference();
            while (true) {
                if (curr == tail) {
                    return new Window<>(prev, curr); // not found
                }
                next = curr.next.get(currMarkedAsDeleted);
                // cleanup
                while (currMarkedAsDeleted[0]) {
                    // HELPING! try hard deletion, delete curr: prev -> next
                    if (!prev.next.compareAndSet(curr, next, false, false)) {
                        continue retry; // restart
                    }
                    curr = next;
                    if (curr == tail) {
                        return new Window<>(prev, curr); // not found
                    }
                    next = curr.next.get(currMarkedAsDeleted);
                }
                // curr.value >= value
                if (curr.value.compareTo(value) >= 0) {
                    return new Window<>(prev, curr); // prev -> curr
                }
                prev = curr;
                curr = next;
            }
        }
    }

    @Override
    public boolean add(T value) {
        Objects.requireNonNull(value, "value is null");
        Node<T> prev, curr, node;
        Window<T> window;
        while (true) {
            window = find(value);
            prev = window.prev;
            curr = window.curr;
            if (curr != tail && curr.value.compareTo(value) == 0) {
                return false; // already present
            }
            // node -> curr
            node = new Node<>(value, curr);
            // prev -> node -> curr
            if (prev.next.compareAndSet(curr, node, false, false)) {
                return true; // added
            }
            // failure - repeat
        }
    }

    @Override
    public boolean remove(T value) {
        Objects.requireNonNull(value, "value is null");
        Node<T> prev, curr, next;
        Window<T> window;
        boolean[] currMarkedAsDeleted = {false};
        while (true) {
            window = find(value);
            prev = window.prev;
            curr = window.curr;
            if (curr == tail || curr.value.compareTo(value) != 0) {
                return false; // not found
            }
            next = curr.next.get(currMarkedAsDeleted);
            // soft deletion
            if (curr.next.compareAndSet(next, next, false, /* mark as deleted */ true)) {
                // try hard deletion, delete curr: prev -> next
                prev.next.compareAndSet(curr, next, false, false);
                return true; // marked as deleted and may be deleted
            }
            // failure - repeat
        }
    }

    // wait-free
    @Override
    public boolean contains(T value) {
        Objects.requireNonNull(value, "value is null");
        Node<T> curr = head.next.getReference();
        while (curr != tail && curr.value.compareTo(value) < 0) {
            curr = curr.next.getReference();
        }
        boolean[] currMarkedAsDeleted = {false};
        while (curr != tail && curr.value.compareTo(value) == 0) {
            curr = curr.next.get(currMarkedAsDeleted);
            if (!currMarkedAsDeleted[0]) {
                return true; // found and not marked
            }
        }
        return false; // not found
    }

    @Override
    public boolean isEmpty() {
        Node<T> prev, curr, next;
        boolean[] currMarkedAsDeleted = {false};
        retry: // restart point: ah sh*t, here we go again
        while (true) {
            prev = head;
            curr = prev.next.getReference();
            while (true) {
                if (curr == tail) {
                    return true; // not found
                }
                next = curr.next.get(currMarkedAsDeleted);
                if (!currMarkedAsDeleted[0]) {
                    return false; // found
                }
                // HELPING! try hard deletion, delete curr: prev -> next
                if (!prev.next.compareAndSet(curr, next, false, false)) {
                    continue retry; // restart
                }
                curr = next;
            }
        }
    }

    private List<Node<T>> collectSnapshot() {
        List<Node<T>> snapshot = new ArrayList<>();
        Node<T> curr = head.next.getReference(), next;
        boolean[] currMarkedAsDeleted = {false};
        while (curr != tail) {
            next = curr.next.get(currMarkedAsDeleted);
            if (!currMarkedAsDeleted[0]) {
                snapshot.add(curr);
            }
            curr = next;
        }
        return snapshot; // all non-deleted nodes
    }

    private boolean validateSnapshot(List<Node<T>> snapshot) {
        // check by mark
        boolean[] currMarkedAsDeleted = {false};
        for (Node<T> snap : snapshot) {
            snap.next.get(currMarkedAsDeleted);
            if (currMarkedAsDeleted[0]) {
                return false; // deleted
            }
        }
        // check by ref
        Node<T> curr = head.next.getReference(), next;
        for (Node<T> snap : snapshot) {
            while (true) {
                if (curr == tail) {
                    return false; // not found
                }
                next = curr.next.get(currMarkedAsDeleted);
                if (curr == snap) {
                    if (currMarkedAsDeleted[0]) {
                        return false; // deleted
                    }
                    curr = next;
                    break; // found
                }
                curr = next;
            }
        }
        return true; // valid
    }

    @Override
    public Iterator<T> iterator() {
        while (true) {
            List<Node<T>> snapshot = collectSnapshot();
            if (validateSnapshot(snapshot)) {
                int size = snapshot.size();
                List<T> values = new ArrayList<>(size);
                for (Node<T> snap : snapshot) {
                    values.add(snap.value);
                }
                return new SnapshotIterator<>(values);
            }
            // failure - repeat
        }
    }

    private static final class SnapshotIterator<E> implements Iterator<E> {
        private final List<E> values;

        private int index = 0;

        public SnapshotIterator(List<E> values) {
            this.values = Collections.unmodifiableList(values);
        }

        @Override
        public boolean hasNext() {
            return index < values.size();
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return values.get(index++);
        }
    }
}