--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/EDU/oswego/cs/dl/util/concurrent/FIFOReadWriteLock.java	Sat Mar 21 11:00:06 2009 +0000
@@ -0,0 +1,186 @@
+/*
+  File: FIFOReadWriteLock.java
+
+  Originally written by Doug Lea and released into the public domain.
+  This may be used for any purposes whatsoever without acknowledgment.
+  Thanks for the assistance and support of Sun Microsystems Labs,
+  and everyone contributing, testing, and using this code.
+
+  History:
+  Date       Who                What
+  11Jun1998  dl               Create public version
+  23nov2001  dl               Replace main algorithm with fairer
+                              version based on one by Alexander Terekhov
+*/
+
+package EDU.oswego.cs.dl.util.concurrent;
+
+
+/**
+ * This class implements a policy for reader/writer locks in which
+ * threads contend in a First-in/First-out manner for access (modulo
+ * the limitations of FIFOSemaphore, which is used for queuing).  This
+ * policy does not particularly favor readers or writers.  As a
+ * byproduct of the FIFO policy, the <tt>attempt</tt> methods may
+ * return <tt>false</tt> even when the lock might logically be
+ * available, but, due to contention, cannot be accessed within the
+ * given time bound.  <p>
+ *
+ * This lock is <em>NOT</em> reentrant. Current readers and
+ * writers should not try to re-obtain locks while holding them.
+ * <p>
+ *
+ * [<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] <p>
+ *
+ * @see FIFOSemaphore
+**/
+
+public class FIFOReadWriteLock implements ReadWriteLock {
+
+  /** 
+   * Fair Semaphore serving as a kind of mutual exclusion lock.
+   * Writers acquire on entry, and hold until rwlock exit.
+   * Readers acquire and release only during entry (but are
+   * blocked from doing so if there is an active writer).
+   **/
+  protected final FIFOSemaphore entryLock = new FIFOSemaphore(1);
+
+  /** 
+   * Number of threads that have entered read lock.  Note that this is
+   * never reset to zero. Incremented only during acquisition of read
+   * lock while the "entryLock" is held, but read elsewhere, so is
+   * declared volatile.
+   **/
+  protected volatile int readers;
+
+  /** 
+   * Number of threads that have exited read lock.  Note that this is
+   * never reset to zero. Accessed only in code protected by
+   * synchronized(this). When exreaders != readers, the rwlock is
+   * being used for reading. Else if the entry lock is held, it is
+   * being used for writing (or in transition). Else it is free.
+   * Note: To distinguish these states, we assume that fewer than 2^32
+   * reader threads can simultaneously execute.
+   **/
+  protected int exreaders;
+
+  protected void acquireRead() throws InterruptedException {
+    entryLock.acquire();
+    ++readers; 
+    entryLock.release();
+  }
+
+  protected synchronized void releaseRead() {
+    /*
+      If this is the last reader, notify a possibly waiting writer.
+      Because waits occur only when entry lock is held, at most one
+      writer can be waiting for this notification.  Because increments
+      to "readers" aren't protected by "this" lock, the notification
+      may be spurious (when an incoming reader in in the process of
+      updating the field), but at the point tested in acquiring write
+      lock, both locks will be held, thus avoiding false alarms. And
+      we will never miss an opportunity to send a notification when it
+      is actually needed.
+    */
+
+    if (++exreaders == readers) 
+      notify(); 
+  }
+
+  protected void acquireWrite() throws InterruptedException {
+    // Acquiring entryLock first forces subsequent entering readers
+    // (as well as writers) to block.
+    entryLock.acquire();
+    
+    // Only read "readers" once now before loop.  We know it won't
+    // change because we hold the entry lock needed to update it.
+    int r = readers;
+    
+    try {
+      synchronized(this) {
+        while (exreaders != r) 
+          wait();
+      }
+    }
+    catch (InterruptedException ie) {
+      entryLock.release();
+      throw ie;
+    }
+  }
+
+  protected void releaseWrite() {
+    entryLock.release();
+  }
+
+  protected boolean attemptRead(long msecs) throws InterruptedException {
+    if (!entryLock.attempt(msecs)) 
+      return false;
+
+    ++readers; 
+    entryLock.release();
+    return true;
+  }
+
+  protected boolean attemptWrite(long msecs) throws InterruptedException {
+    long startTime = (msecs <= 0)? 0 : System.currentTimeMillis();
+
+    if (!entryLock.attempt(msecs)) 
+      return false;
+
+    int r = readers;
+
+    try {
+      synchronized(this) {
+        while (exreaders != r) {
+          long timeLeft = (msecs <= 0)? 0:
+            msecs - (System.currentTimeMillis() - startTime);
+          
+          if (timeLeft <= 0) {
+            entryLock.release();
+            return false;
+          }
+          
+          wait(timeLeft);
+        }
+        return true;
+      }
+    }
+    catch (InterruptedException ie) {
+      entryLock.release();
+      throw ie;
+    }
+  }
+
+  // support for ReadWriteLock interface
+
+  protected class ReaderSync implements Sync {
+    public void acquire() throws InterruptedException {
+      acquireRead();
+    }
+    public  void release()  { 
+      releaseRead();
+    }
+    public boolean attempt(long msecs) throws InterruptedException {
+      return attemptRead(msecs);
+    }
+  }
+
+  protected class WriterSync implements Sync {
+    public void acquire() throws InterruptedException {
+      acquireWrite();
+    }
+    public  void release()  { 
+      releaseWrite();
+    }
+    public boolean attempt(long msecs) throws InterruptedException {
+      return attemptWrite(msecs);
+    }
+  }
+
+  protected final Sync readerSync = new ReaderSync();
+  protected final Sync writerSync = new WriterSync();
+
+  public Sync writeLock() { return writerSync; }
+  public Sync readLock() { return readerSync; }
+
+}