[concurrency-interest] Canonical example of how to do hand-over-hand locking?

[Joe Bowbeer]

On 4/24/07, Aaron Greenhouse <aarong at cs.cmu.edu> wrote:
> The javadoc for the java.util.concurrent.locks package explicitly
> mentions that the locks can be used for hand-over-hand locking.  But it
> doesn't give an example.  How does this interact with the recommendation
> that unlocks occur in finally clauses so as to insure that all locks are
> always unlocked?
>

In case you're still interested, here's one more example.  (I really
like this question:)

The methods are in order of increasing complexity.  The 'remove'
method is the most complex, needing nested try-finally's to handle all
the possible exceptions.

public class List {

    /**
     * Holds one item in a singly-linked list.
     * It's convenient here to subclass ReentrantLock
     * rather than add one as a field.
     */
    private static class Node extends ReentrantLock {
        Object item;
        Node next;
        Node(Object item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    /**
     * Sentinel node. This node's next field points to
     * the first node in the list. Its item field is ignored.
     */
    private final Node sentinel = new Node(null, null);

    public void addFirst(Object x) {
        Node p = sentinel;
        p.lock();
        try {
            p.next = new Node(x, p.next);
        } finally {
            p.unlock();
        }
     }

    public void addLast(Object x) {
        Node p = sentinel;
        /* Acquire first lock. */
        p.lock();
        try {
            /* Find tail, using hand-over-hand locking. */
            while (p.next != null) {
                Node prevp = p;
                p.next.lock();
                p = p.next;
                prevp.unlock();
            }
            /* Attach new node. */
            p.next = new Node(x, null);
        } finally {
            /* Release final lock that was held. */
            p.unlock();
        }
     }

    public boolean contains(Object x) {
        Node p = sentinel;
        /* Acquire first lock. */
        p.lock();
        try {
            while (p.next != null) {
                /*
                 * Get next lock and release current.
                 * Sentinel is skipped on first iteration.
                 */
                Node prevp = p;
                p.next.lock();
                p = p.next;
                prevp.unlock();
                /* Found? */
                if (x == p.item || x != null && x.equals(p.item))
                    return true;
            }
            return false;
        } finally {
            /* Release final lock that was held. */
            p.unlock();
        }
    }

    public boolean remove(Object x) {
        Node p = sentinel;
        /* Acquire first lock. */
        p.lock();
        try {
            while (p.next != null) {
                /*
                 * Get next lock and release current.
                 * Sentinel is skipped on first iteration.
                 */
                Node prevp = p;
                p.next.lock();
                p = p.next;
                try {
                    /* Found? */
                    if (x == p.item || x != null && x.equals(p.item)) {
                        /* Remove node p. */
                        prevp.next = p.next;
                        return true;
                    }
                } finally {
                    prevp.unlock();
                }
            }
            return false;
        } finally {
            /* Release final lock that was held. */
            p.unlock();
        }
    }
}

--
Joe Bowbeer