In AbstractQueuedSynchronizer,

apparentlyFirstQueuedIsExclusive
should check for cancelled nodes.

Also, isFirst can rely on the improved reliability of Node fields
provided by the fixes for

6460501: Synchronizer timed acquire still leaks memory

to never have to traverse the sync queue and thus have a much simpler
implementation.

--- /tmp/geta7187	2007-06-26 11:29:35.530346000 -0700
+++ AbstractQueuedLongSynchronizer.java	2007-06-26 01:16:54.169925000 -0700
@@ -1161,44 +1161,33 @@
     /**
      * Return {@code true} if the apparent first queued thread, if one
      * exists, is waiting in exclusive mode. Used only as a heuristic
      * in ReentrantReadWriteLock.
      */
     final boolean apparentlyFirstQueuedIsExclusive() {
         Node h, s;
-        return (h = head) != null && (s = h.next) != null && ! s.isShared();
+        return (h = head) != null &&
+	    (s = h.next)  != null &&
+	    ! s.isShared()        &&
+	    s.thread != null;
     }
 
     /**
      * Return {@code true} if the queue is empty or if the given thread
      * is at the head of the queue. This is reliable only if
-     * <tt>current</tt> is actually Thread.currentThread() of caller.
+     * <tt>current</tt> is actually Thread.currentThread() of caller
+     * and if this method is called from within tryAcquire.
      */
     final boolean isFirst(Thread current) {
+	// The correctness of this depends on:
+	// - head being initialized before tail
+	// - head.next being accurate if current is first in queue
         Node h, s;
-        return ((h = head) == null ||
-                ((s = h.next) != null && s.thread == current) ||
-                fullIsFirst(current));
-    }
-
-    final boolean fullIsFirst(Thread current) {
-        // same idea as fullGetFirstQueuedThread
-        Node h, s;
-        Thread firstThread = null;
-        if (((h = head) != null && (s = h.next) != null &&
-             s.prev == head && (firstThread = s.thread) != null))
-            return firstThread == current;
-        Node t = tail;
-        while (t != null && t != head) {
-            Thread tt = t.thread;
-            if (tt != null)
-                firstThread = tt;
-            t = t.prev;
-        }
-        return firstThread == current || firstThread == null;
+        return (h = head) == tail ||
+	    ((s = h.next) != null && s.thread == current);
     }
 
 
     // Instrumentation and monitoring methods
 
     /**
      * Returns an estimate of the number of threads waiting to


Here's a program (admittedly highly doctored) that sees big speedups
(as measured by nanos/tryLock) with this change applied:

-------------------------------------------------
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import java.util.concurrent.atomic.*;
import java.io.*;

public class Hak2 {

    final static Queue<Writer> threads = new ConcurrentLinkedQueue<Writer>();
    final static AtomicLong acquires = new AtomicLong(0);

    static class Writer extends Thread {
	volatile boolean waiting = true;
	final Lock lock;
	Writer(Lock lock) { this.lock = lock; }
	public void run() {
	    try {
		lock.lockInterruptibly();
		lock.unlock();
		acquires.getAndIncrement();
	    } catch (InterruptedException _) {}
	    finally {
		waiting = false;
		for (;;) {
		    Writer thread = threads.poll();
		    if (thread == null) break;
		    if (! thread.waiting) continue;
		    thread.interrupt();
		    break;
		}
	    }
	}
    }

    public static void main(String[] args) throws Throwable {
	final ReentrantReadWriteLock rw = new ReentrantReadWriteLock(true);
	final Lock r = rw.readLock();
	final Lock w = rw.writeLock();
	r.lock();
	for (int i = 0; i < 1000; i++) {
	    Writer thread = new Writer(w);
	    threads.add(thread);
	    //thread.setPriority(Thread.MIN_PRIORITY);
	    thread.start();
	}
	Thread.sleep(2500);
	threads.remove().interrupt();
	//System.out.printf("acquires=%d%n", acquires.get());
	//for (Writer thread : threads) thread.interrupt();
	r.unlock();
	long successes = 0;
	long t0 = System.nanoTime();
	for (int i = 1; i < 1000000; i++) {
	    if (r.tryLock(1, TimeUnit.NANOSECONDS)) {
		// Writers are done
		r.unlock();
		long elapsed = System.nanoTime() - t0;
		//System.out.printf("elapsed=%d%n", elapsed);
		System.out.printf("i=%d%n", i);
		System.out.printf("nanos/tryLock=%d%n", elapsed/i);
		System.out.printf("acquires=%d%n", acquires.get());
		break;
	    }
	}
    }
}
-------------------------------------------------