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;
}
}
    }
}
-------------------------------------------------