lib/classpath/external/jsr166/java/util/concurrent/locks/ReentrantReadWriteLock.java

   1 /*
   2  * Written by Doug Lea with assistance from members of JCP JSR-166
   3  * Expert Group and released to the public domain, as explained at
   4  * http://creativecommons.org/licenses/publicdomain
   5  */
   6
   7 package java.util.concurrent.locks;
   8 import java.util.concurrent.*;
   9 import java.util.concurrent.atomic.*;
  10 import java.util.*;
  11
  12 /**
  13  * An implementation of {@link ReadWriteLock} supporting similar
  14  * semantics to {@link ReentrantLock}.
  15  * <p>This class has the following properties:
  16  *
  17  * <ul>
  18  * <li><b>Acquisition order</b>
  19  *
  20  * <p> This class does not impose a reader or writer preference
  21  * ordering for lock access.  However, it does support an optional
  22  * <em>fairness</em> policy.
  23  *
  24  * <dl>
  25  * <dt><b><i>Non-fair mode (default)</i></b>
  26  * <dd>When constructed as non-fair (the default), the order of entry
  27  * to the read and write lock is unspecified, subject to reentrancy
  28  * constraints.  A nonfair lock that is continously contended may
  29  * indefinitely postpone one or more reader or writer threads, but
  30  * will normally have higher throughput than a fair lock.
  31  * <p>
  32  *
  33  * <dt><b><i>Fair mode</i></b>
  34  * <dd> When constructed as fair, threads contend for entry using an
  35  * approximately arrival-order policy. When the currently held lock
  36  * is released either the longest-waiting single writer thread will
  37  * be assigned the write lock, or if there is a group of reader threads
  38  * waiting longer than all waiting writer threads, that group will be
  39  * assigned the read lock.
  40  *
  41  * <p>A thread that tries to acquire a fair read lock (non-reentrantly)
  42  * will block if either the write lock is held, or there is a waiting
  43  * writer thread. The thread will not acquire the read lock until
  44  * after the oldest currently waiting writer thread has acquired and
  45  * released the write lock. Of course, if a waiting writer abandons
  46  * its wait, leaving one or more reader threads as the longest waiters
  47  * in the queue with the write lock free, then those readers will be
  48  * assigned the read lock.
  49  *
  50  * <p>A thread that tries to acquire a fair write lock (non-reentrantly)
  51  * will block unless both the read lock and write lock are free (which
  52  * implies there are no waiting threads).  (Note that the non-blocking
  53  * {@link ReadLock#tryLock()} and {@link WriteLock#tryLock()} methods
  54  * do not honor this fair setting and will acquire the lock if it is
  55  * possible, regardless of waiting threads.)
  56  * <p>
  57  * </dl>
  58  *
  59  * <li><b>Reentrancy</b>
  60  *
  61  * <p>This lock allows both readers and writers to reacquire read or
  62  * write locks in the style of a {@link ReentrantLock}. Non-reentrant
  63  * readers are not allowed until all write locks held by the writing
  64  * thread have been released.
  65  *
  66  * <p>Additionally, a writer can acquire the read lock, but not
  67  * vice-versa.  Among other applications, reentrancy can be useful
  68  * when write locks are held during calls or callbacks to methods that
  69  * perform reads under read locks.  If a reader tries to acquire the
  70  * write lock it will never succeed.
  71  *
  72  * <li><b>Lock downgrading</b>
  73  * <p>Reentrancy also allows downgrading from the write lock to a read lock,
  74  * by acquiring the write lock, then the read lock and then releasing the
  75  * write lock. However, upgrading from a read lock to the write lock is
  76  * <b>not</b> possible.
  77  *
  78  * <li><b>Interruption of lock acquisition</b>
  79  * <p>The read lock and write lock both support interruption during lock
  80  * acquisition.
  81  *
  82  * <li><b>{@link Condition} support</b>
  83  * <p>The write lock provides a {@link Condition} implementation that
  84  * behaves in the same way, with respect to the write lock, as the
  85  * {@link Condition} implementation provided by
  86  * {@link ReentrantLock#newCondition} does for {@link ReentrantLock}.
  87  * This {@link Condition} can, of course, only be used with the write lock.
  88  *
  89  * <p>The read lock does not support a {@link Condition} and
  90  * {@code readLock().newCondition()} throws
  91  * {@code UnsupportedOperationException}.
  92  *
  93  * <li><b>Instrumentation</b>
  94  * <p>This class supports methods to determine whether locks
  95  * are held or contended. These methods are designed for monitoring
  96  * system state, not for synchronization control.
  97  * </ul>
  98  *
  99  * <p>Serialization of this class behaves in the same way as built-in
 100  * locks: a deserialized lock is in the unlocked state, regardless of
 101  * its state when serialized.
 102  *
 103  * <p><b>Sample usages</b>. Here is a code sketch showing how to exploit
 104  * reentrancy to perform lock downgrading after updating a cache (exception
 105  * handling is elided for simplicity):
 106  * <pre>
 107  * class CachedData {
 108  *   Object data;
 109  *   volatile boolean cacheValid;
 110  *   ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
 111  *
 112  *   void processCachedData() {
 113  *     rwl.readLock().lock();
 114  *     if (!cacheValid) {
 115  *        // Must release read lock before acquiring write lock
 116  *        rwl.readLock().unlock();
 117  *        rwl.writeLock().lock();
 118  *        // Recheck state because another thread might have acquired
 119  *        //   write lock and changed state before we did.
 120  *        if (!cacheValid) {
 121  *          data = ...
 122  *          cacheValid = true;
 123  *        }
 124  *        // Downgrade by acquiring read lock before releasing write lock
 125  *        rwl.readLock().lock();
 126  *        rwl.writeLock().unlock(); // Unlock write, still hold read
 127  *     }
 128  *
 129  *     use(data);
 130  *     rwl.readLock().unlock();
 131  *   }
 132  * }
 133  * </pre>
 134  *
 135  * ReentrantReadWriteLocks can be used to improve concurrency in some
 136  * uses of some kinds of Collections. This is typically worthwhile
 137  * only when the collections are expected to be large, accessed by
 138  * more reader threads than writer threads, and entail operations with
 139  * overhead that outweighs synchronization overhead. For example, here
 140  * is a class using a TreeMap that is expected to be large and
 141  * concurrently accessed.
 142  *
 143  * <pre>{@code
 144  * class RWDictionary {
 145  *    private final Map<String, Data> m = new TreeMap<String, Data>();
 146  *    private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
 147  *    private final Lock r = rwl.readLock();
 148  *    private final Lock w = rwl.writeLock();
 149  *
 150  *    public Data get(String key) {
 151  *        r.lock();
 152  *        try { return m.get(key); }
 153  *        finally { r.unlock(); }
 154  *    }
 155  *    public String[] allKeys() {
 156  *        r.lock();
 157  *        try { return m.keySet().toArray(); }
 158  *        finally { r.unlock(); }
 159  *    }
 160  *    public Data put(String key, Data value) {
 161  *        w.lock();
 162  *        try { return m.put(key, value); }
 163  *        finally { w.unlock(); }
 164  *    }
 165  *    public void clear() {
 166  *        w.lock();
 167  *        try { m.clear(); }
 168  *        finally { w.unlock(); }
 169  *    }
 170  * }}</pre>
 171  *
 172  * <h3>Implementation Notes</h3>
 173  *
 174  * <p>This lock supports a maximum of 65535 recursive write locks
 175  * and 65535 read locks. Attempts to exceed these limits result in
 176  * {@link Error} throws from locking methods.
 177  *
 178  * @since 1.5
 179  * @author Doug Lea
 180  *
 181  */
 182 public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable  {
 183     private static final long serialVersionUID = -6992448646407690164L;
 184     /** Inner class providing readlock */
 185     private final ReentrantReadWriteLock.ReadLock readerLock;
 186     /** Inner class providing writelock */
 187     private final ReentrantReadWriteLock.WriteLock writerLock;
 188     /** Performs all synchronization mechanics */
 189     private final Sync sync;
 190
 191     /**
 192      * Creates a new {@code ReentrantReadWriteLock} with
 193      * default (nonfair) ordering properties.
 194      */
 195     public ReentrantReadWriteLock() {
 196         this(false);
 197     }
 198
 199     /**
 200      * Creates a new {@code ReentrantReadWriteLock} with
 201      * the given fairness policy.
 202      *
 203      * @param fair {@code true} if this lock should use a fair ordering policy
 204      */
 205     public ReentrantReadWriteLock(boolean fair) {
 206         sync = (fair)? new FairSync() : new NonfairSync();
 207         readerLock = new ReadLock(this);
 208         writerLock = new WriteLock(this);
 209     }
 210
 211     public ReentrantReadWriteLock.WriteLock writeLock() { return writerLock; }
 212     public ReentrantReadWriteLock.ReadLock  readLock()  { return readerLock; }
 213
 214     /**
 215      * Synchronization implementation for ReentrantReadWriteLock.
 216      * Subclassed into fair and nonfair versions.
 217      */
 218     static abstract class Sync extends AbstractQueuedSynchronizer {
 219         private static final long serialVersionUID = 6317671515068378041L;
 220
 221         /*
 222          * Read vs write count extraction constants and functions.
 223          * Lock state is logically divided into two shorts: The lower
 224          * one representing the exclusive (writer) lock hold count,
 225          * and the upper the shared (reader) hold count.
 226          */
 227
 228         static final int SHARED_SHIFT   = 16;
 229         static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
 230         static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
 231         static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
 232
 233         /** Returns the number of shared holds represented in count  */
 234         static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
 235         /** Returns the number of exclusive holds represented in count  */
 236         static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
 237
 238         /**
 239          * A counter for per-thread read hold counts.
 240          * Maintained as a ThreadLocal; cached in cachedHoldCounter
 241          */
 242         static final class HoldCounter {
 243             int count;
 244             // Use id, not reference, to avoid garbage retention
 245             final long tid = Thread.currentThread().getId();
 246             /** Decrement if positive; return previous value */
 247             int tryDecrement() {
 248                 int c = count;
 249                 if (c > 0)
 250                     count = c - 1;
 251                 return c;
 252             }
 253         }
 254
 255         /**
 256          * ThreadLocal subclass. Easiest to explicitly define for sake
 257          * of deserialization mechanics.
 258          */
 259         static final class ThreadLocalHoldCounter
 260             extends ThreadLocal<HoldCounter> {
 261             public HoldCounter initialValue() {
 262                 return new HoldCounter();
 263             }
 264         }
 265
 266         /**
 267          * The number of read locks held by current thread.
 268          * Initialized only in constructor and readObject.
 269          */
 270         transient ThreadLocalHoldCounter readHolds;
 271
 272         /**
 273          * The hold count of the last thread to successfully acquire
 274          * readLock. This saves ThreadLocal lookup in the common case
 275          * where the next thread to release is the last one to
 276          * acquire. This is non-volatile since it is just used
 277          * as a heuristic, and would be great for threads to cache.
 278          */
 279         transient HoldCounter cachedHoldCounter;
 280
 281         Sync() {
 282             readHolds = new ThreadLocalHoldCounter();
 283             setState(getState()); // ensures visibility of readHolds
 284         }
 285
 286         /*
 287          * Acquires and releases use the same code for fair and
 288          * nonfair locks, but differ in whether/how they allow barging
 289          * when queues are non-empty.
 290          */
 291
 292         /**
 293          * Return true if a reader thread that is otherwise
 294          * eligible for lock should block because of policy
 295          * for overtaking other waiting threads.
 296          */
 297         abstract boolean readerShouldBlock(Thread current);
 298
 299         /**
 300          * Return true if a writer thread that is otherwise
 301          * eligible for lock should block because of policy
 302          * for overtaking other waiting threads.
 303          */
 304         abstract boolean writerShouldBlock(Thread current);
 305
 306         /*
 307          * Note that tryRelease and tryAcquire can be called by
 308          * Conditions. So it is possible that their arguments contain
 309          * both read and write holds that are all released during a
 310          * condition wait and re-established in tryAcquire.
 311          */
 312
 313         protected final boolean tryRelease(int releases) {
 314             int nextc = getState() - releases;
 315             if (Thread.currentThread() != getExclusiveOwnerThread())
 316                 throw new IllegalMonitorStateException();
 317             if (exclusiveCount(nextc) == 0) {
 318                 setExclusiveOwnerThread(null);
 319                 setState(nextc);
 320                 return true;
 321             } else {
 322                 setState(nextc);
 323                 return false;
 324             }
 325         }
 326
 327         protected final boolean tryAcquire(int acquires) {
 328             /*
 329              * Walkthrough:
 330              * 1. if read count nonzero or write count nonzero
 331              *     and owner is a different thread, fail.
 332              * 2. If count would saturate, fail. (This can only
 333              *    happen if count is already nonzero.)
 334              * 3. Otherwise, this thread is eligible for lock if
 335              *    it is either a reentrant acquire or
 336              *    queue policy allows it. If so, update state
 337              *    and set owner.
 338              */
 339             Thread current = Thread.currentThread();
 340             int c = getState();
 341             int w = exclusiveCount(c);
 342             if (c != 0) {
 343                 // (Note: if c != 0 and w == 0 then shared count != 0)
 344                 if (w == 0 || current != getExclusiveOwnerThread())
 345                     return false;
 346                 if (w + exclusiveCount(acquires) > MAX_COUNT)
 347                     throw new Error("Maximum lock count exceeded");
 348             }
 349             if ((w == 0 && writerShouldBlock(current)) ||
 350                 !compareAndSetState(c, c + acquires))
 351                 return false;
 352             setExclusiveOwnerThread(current);
 353             return true;
 354         }
 355
 356         protected final boolean tryReleaseShared(int unused) {
 357             HoldCounter rh = cachedHoldCounter;
 358             Thread current = Thread.currentThread();
 359             if (rh == null || rh.tid != current.getId())
 360                 rh = readHolds.get();
 361             if (rh.tryDecrement() <= 0)
 362                 throw new IllegalMonitorStateException();
 363             for (;;) {
 364                 int c = getState();
 365                 int nextc = c - SHARED_UNIT;
 366                 if (compareAndSetState(c, nextc))
 367                     return nextc == 0;
 368             }
 369         }
 370
 371         protected final int tryAcquireShared(int unused) {
 372             /*
 373              * Walkthrough:
 374              * 1. If write lock held by another thread, fail
 375              * 2. If count saturated, throw error
 376              * 3. Otherwise, this thread is eligible for
 377              *    lock wrt state, so ask if it should block
 378              *    because of queue policy. If not, try
 379              *    to grant by CASing state and updating count.
 380              *    Note that step does not check for reentrant
 381              *    acquires, which is postponed to full version
 382              *    to avoid having to check hold count in
 383              *    the more typical non-reentrant case.
 384              * 4. If step 3 fails either because thread
 385              *    apparently not eligible or CAS fails,
 386              *    chain to version with full retry loop.
 387              */
 388             Thread current = Thread.currentThread();
 389             int c = getState();
 390             if (exclusiveCount(c) != 0 &&
 391                 getExclusiveOwnerThread() != current)
 392                 return -1;
 393             if (sharedCount(c) == MAX_COUNT)
 394                 throw new Error("Maximum lock count exceeded");
 395             if (!readerShouldBlock(current) &&
 396                 compareAndSetState(c, c + SHARED_UNIT)) {
 397                 HoldCounter rh = cachedHoldCounter;
 398                 if (rh == null || rh.tid != current.getId())
 399                     cachedHoldCounter = rh = readHolds.get();
 400                 rh.count++;
 401                 return 1;
 402             }
 403             return fullTryAcquireShared(current);
 404         }
 405
 406         /**
 407          * Full version of acquire for reads, that handles CAS misses
 408          * and reentrant reads not dealt with in tryAcquireShared.
 409          */
 410         final int fullTryAcquireShared(Thread current) {
 411             /*
 412              * This code is in part redundant with that in
 413              * tryAcquireShared but is simpler overall by not
 414              * complicating tryAcquireShared with interactions between
 415              * retries and lazily reading hold counts.
 416              */
 417             HoldCounter rh = cachedHoldCounter;
 418             if (rh == null || rh.tid != current.getId())
 419                 rh = readHolds.get();
 420             for (;;) {
 421                 int c = getState();
 422                 int w = exclusiveCount(c);
 423                 if ((w != 0 && getExclusiveOwnerThread() != current) ||
 424                     ((rh.count | w) == 0 && readerShouldBlock(current)))
 425                     return -1;
 426                 if (sharedCount(c) == MAX_COUNT)
 427                     throw new Error("Maximum lock count exceeded");
 428                 if (compareAndSetState(c, c + SHARED_UNIT)) {
 429                     cachedHoldCounter = rh; // cache for release
 430                     rh.count++;
 431                     return 1;
 432                 }
 433             }
 434         }
 435
 436         /**
 437          * Performs tryLock for write, enabling barging in both modes.
 438          * This is identical in effect to tryAcquire except for lack
 439          * of calls to writerShouldBlock
 440          */
 441         final boolean tryWriteLock() {
 442             Thread current = Thread.currentThread();
 443             int c = getState();
 444             if (c != 0) {
 445                 int w = exclusiveCount(c);
 446                 if (w == 0 ||current != getExclusiveOwnerThread())
 447                     return false;
 448                 if (w == MAX_COUNT)
 449                     throw new Error("Maximum lock count exceeded");
 450             }
 451             if (!compareAndSetState(c, c + 1))
 452                 return false;
 453             setExclusiveOwnerThread(current);
 454             return true;
 455         }
 456
 457         /**
 458          * Performs tryLock for read, enabling barging in both modes.
 459          * This is identical in effect to tryAcquireShared except for
 460          * lack of calls to readerShouldBlock
 461          */
 462         final boolean tryReadLock() {
 463             Thread current = Thread.currentThread();
 464             for (;;) {
 465                 int c = getState();
 466                 if (exclusiveCount(c) != 0 &&
 467                     getExclusiveOwnerThread() != current)
 468                     return false;
 469                 if (sharedCount(c) == MAX_COUNT)
 470                     throw new Error("Maximum lock count exceeded");
 471                 if (compareAndSetState(c, c + SHARED_UNIT)) {
 472                     HoldCounter rh = cachedHoldCounter;
 473                     if (rh == null || rh.tid != current.getId())
 474                         cachedHoldCounter = rh = readHolds.get();
 475                     rh.count++;
 476                     return true;
 477                 }
 478             }
 479         }
 480
 481         protected final boolean isHeldExclusively() {
 482             // While we must in general read state before owner,
 483             // we don't need to do so to check if current thread is owner
 484             return getExclusiveOwnerThread() == Thread.currentThread();
 485         }
 486
 487         // Methods relayed to outer class
 488
 489         final ConditionObject newCondition() {
 490             return new ConditionObject();
 491         }
 492
 493         final Thread getOwner() {
 494             // Must read state before owner to ensure memory consistency
 495             return ((exclusiveCount(getState()) == 0)?
 496                     null :
 497                     getExclusiveOwnerThread());
 498         }
 499
 500         final int getReadLockCount() {
 501             return sharedCount(getState());
 502         }
 503
 504         final boolean isWriteLocked() {
 505             return exclusiveCount(getState()) != 0;
 506         }
 507
 508         final int getWriteHoldCount() {
 509             return isHeldExclusively() ? exclusiveCount(getState()) : 0;
 510         }
 511
 512         final int getReadHoldCount() {
 513             return getReadLockCount() == 0? 0 : readHolds.get().count;
 514         }
 515
 516         /**
 517          * Reconstitute this lock instance from a stream
 518          * @param s the stream
 519          */
 520         private void readObject(java.io.ObjectInputStream s)
 521             throws java.io.IOException, ClassNotFoundException {
 522             s.defaultReadObject();
 523             readHolds = new ThreadLocalHoldCounter();
 524             setState(0); // reset to unlocked state
 525         }
 526
 527         final int getCount() { return getState(); }
 528     }
 529
 530     /**
 531      * Nonfair version of Sync
 532      */
 533     final static class NonfairSync extends Sync {
 534         private static final long serialVersionUID = -8159625535654395037L;
 535         final boolean writerShouldBlock(Thread current) {
 536             return false; // writers can always barge
 537         }
 538         final boolean readerShouldBlock(Thread current) {
 539             /* As a heuristic to avoid indefinite writer starvation,
 540              * block if the thread that momentarily appears to be head
 541              * of queue, if one exists, is a waiting writer. This is
 542              * only a probablistic effect since a new reader will not
 543              * block if there is a waiting writer behind other enabled
 544              * readers that have not yet drained from the queue.
 545              */
 546             return apparentlyFirstQueuedIsExclusive();
 547         }
 548     }
 549
 550     /**
 551      * Fair version of Sync
 552      */
 553     final static class FairSync extends Sync {
 554         private static final long serialVersionUID = -2274990926593161451L;
 555         final boolean writerShouldBlock(Thread current) {
 556             // only proceed if queue is empty or current thread at head
 557             return !isFirst(current);
 558         }
 559         final boolean readerShouldBlock(Thread current) {
 560             // only proceed if queue is empty or current thread at head
 561             return !isFirst(current);
 562         }
 563     }
 564
 565     /**
 566      * The lock returned by method {@link ReentrantReadWriteLock#readLock}.
 567      */
 568     public static class ReadLock implements Lock, java.io.Serializable  {
 569         private static final long serialVersionUID = -5992448646407690164L;
 570         private final Sync sync;
 571
 572         /**
 573          * Constructor for use by subclasses
 574          *
 575          * @param lock the outer lock object
 576          * @throws NullPointerException if the lock is null
 577          */
 578         protected ReadLock(ReentrantReadWriteLock lock) {
 579             sync = lock.sync;
 580         }
 581
 582         /**
 583          * Acquires the read lock.
 584          *
 585          * <p>Acquires the read lock if the write lock is not held by
 586          * another thread and returns immediately.
 587          *
 588          * <p>If the write lock is held by another thread then
 589          * the current thread becomes disabled for thread scheduling
 590          * purposes and lies dormant until the read lock has been acquired.
 591          */
 592         public void lock() {
 593             sync.acquireShared(1);
 594         }
 595
 596         /**
 597          * Acquires the read lock unless the current thread is
 598          * {@linkplain Thread#interrupt interrupted}.
 599          *
 600          * <p>Acquires the read lock if the write lock is not held
 601          * by another thread and returns immediately.
 602          *
 603          * <p>If the write lock is held by another thread then the
 604          * current thread becomes disabled for thread scheduling
 605          * purposes and lies dormant until one of two things happens:
 606          *
 607          * <ul>
 608          *
 609          * <li>The read lock is acquired by the current thread; or
 610          *
 611          * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 612          * the current thread.
 613          *
 614          * </ul>
 615          *
 616          * <p>If the current thread:
 617          *
 618          * <ul>
 619          *
 620          * <li>has its interrupted status set on entry to this method; or
 621          *
 622          * <li>is {@linkplain Thread#interrupt interrupted} while
 623          * acquiring the read lock,
 624          *
 625          * </ul>
 626          *
 627          * then {@link InterruptedException} is thrown and the current
 628          * thread's interrupted status is cleared.
 629          *
 630          * <p>In this implementation, as this method is an explicit
 631          * interruption point, preference is given to responding to
 632          * the interrupt over normal or reentrant acquisition of the
 633          * lock.
 634          *
 635          * @throws InterruptedException if the current thread is interrupted
 636          */
 637         public void lockInterruptibly() throws InterruptedException {
 638             sync.acquireSharedInterruptibly(1);
 639         }
 640
 641         /**
 642          * Acquires the read lock only if the write lock is not held by
 643          * another thread at the time of invocation.
 644          *
 645          * <p>Acquires the read lock if the write lock is not held by
 646          * another thread and returns immediately with the value
 647          * {@code true}. Even when this lock has been set to use a
 648          * fair ordering policy, a call to {@code tryLock()}
 649          * <em>will</em> immediately acquire the read lock if it is
 650          * available, whether or not other threads are currently
 651          * waiting for the read lock.  This &quot;barging&quot; behavior
 652          * can be useful in certain circumstances, even though it
 653          * breaks fairness. If you want to honor the fairness setting
 654          * for this lock, then use {@link #tryLock(long, TimeUnit)
 655          * tryLock(0, TimeUnit.SECONDS) } which is almost equivalent
 656          * (it also detects interruption).
 657          *
 658          * <p>If the write lock is held by another thread then
 659          * this method will return immediately with the value
 660          * {@code false}.
 661          *
 662          * @return {@code true} if the read lock was acquired
 663          */
 664         public  boolean tryLock() {
 665             return sync.tryReadLock();
 666         }
 667
 668         /**
 669          * Acquires the read lock if the write lock is not held by
 670          * another thread within the given waiting time and the
 671          * current thread has not been {@linkplain Thread#interrupt
 672          * interrupted}.
 673          *
 674          * <p>Acquires the read lock if the write lock is not held by
 675          * another thread and returns immediately with the value
 676          * {@code true}. If this lock has been set to use a fair
 677          * ordering policy then an available lock <em>will not</em> be
 678          * acquired if any other threads are waiting for the
 679          * lock. This is in contrast to the {@link #tryLock()}
 680          * method. If you want a timed {@code tryLock} that does
 681          * permit barging on a fair lock then combine the timed and
 682          * un-timed forms together:
 683          *
 684          * <pre>if (lock.tryLock() || lock.tryLock(timeout, unit) ) { ... }
 685          * </pre>
 686          *
 687          * <p>If the write lock is held by another thread then the
 688          * current thread becomes disabled for thread scheduling
 689          * purposes and lies dormant until one of three things happens:
 690          *
 691          * <ul>
 692          *
 693          * <li>The read lock is acquired by the current thread; or
 694          *
 695          * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 696          * the current thread; or
 697          *
 698          * <li>The specified waiting time elapses.
 699          *
 700          * </ul>
 701          *
 702          * <p>If the read lock is acquired then the value {@code true} is
 703          * returned.
 704          *
 705          * <p>If the current thread:
 706          *
 707          * <ul>
 708          *
 709          * <li>has its interrupted status set on entry to this method; or
 710          *
 711          * <li>is {@linkplain Thread#interrupt interrupted} while
 712          * acquiring the read lock,
 713          *
 714          * </ul> then {@link InterruptedException} is thrown and the
 715          * current thread's interrupted status is cleared.
 716          *
 717          * <p>If the specified waiting time elapses then the value
 718          * {@code false} is returned.  If the time is less than or
 719          * equal to zero, the method will not wait at all.
 720          *
 721          * <p>In this implementation, as this method is an explicit
 722          * interruption point, preference is given to responding to
 723          * the interrupt over normal or reentrant acquisition of the
 724          * lock, and over reporting the elapse of the waiting time.
 725          *
 726          * @param timeout the time to wait for the read lock
 727          * @param unit the time unit of the timeout argument
 728          * @return {@code true} if the read lock was acquired
 729          * @throws InterruptedException if the current thread is interrupted
 730          * @throws NullPointerException if the time unit is null
 731          *
 732          */
 733         public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
 734             return sync.tryAcquireSharedNanos(1, unit.toNanos(timeout));
 735         }
 736
 737         /**
 738          * Attempts to release this lock.
 739          *
 740          * <p> If the number of readers is now zero then the lock
 741          * is made available for write lock attempts.
 742          */
 743         public  void unlock() {
 744             sync.releaseShared(1);
 745         }
 746
 747         /**
 748          * Throws {@code UnsupportedOperationException} because
 749          * {@code ReadLocks} do not support conditions.
 750          *
 751          * @throws UnsupportedOperationException always
 752          */
 753         public Condition newCondition() {
 754             throw new UnsupportedOperationException();
 755         }
 756
 757         /**
 758          * Returns a string identifying this lock, as well as its lock state.
 759          * The state, in brackets, includes the String {@code "Read locks ="}
 760          * followed by the number of held read locks.
 761          *
 762          * @return a string identifying this lock, as well as its lock state
 763          */
 764         public String toString() {
 765             int r = sync.getReadLockCount();
 766             return super.toString() +
 767                 "[Read locks = " + r + "]";
 768         }
 769     }
 770
 771     /**
 772      * The lock returned by method {@link ReentrantReadWriteLock#writeLock}.
 773      */
 774     public static class WriteLock implements Lock, java.io.Serializable  {
 775         private static final long serialVersionUID = -4992448646407690164L;
 776         private final Sync sync;
 777
 778         /**
 779          * Constructor for use by subclasses
 780          *
 781          * @param lock the outer lock object
 782          * @throws NullPointerException if the lock is null
 783          */
 784         protected WriteLock(ReentrantReadWriteLock lock) {
 785             sync = lock.sync;
 786         }
 787
 788         /**
 789          * Acquires the write lock.
 790          *
 791          * <p>Acquires the write lock if neither the read nor write lock
 792          * are held by another thread
 793          * and returns immediately, setting the write lock hold count to
 794          * one.
 795          *
 796          * <p>If the current thread already holds the write lock then the
 797          * hold count is incremented by one and the method returns
 798          * immediately.
 799          *
 800          * <p>If the lock is held by another thread then the current
 801          * thread becomes disabled for thread scheduling purposes and
 802          * lies dormant until the write lock has been acquired, at which
 803          * time the write lock hold count is set to one.
 804          */
 805         public void lock() {
 806             sync.acquire(1);
 807         }
 808
 809         /**
 810          * Acquires the write lock unless the current thread is
 811          * {@linkplain Thread#interrupt interrupted}.
 812          *
 813          * <p>Acquires the write lock if neither the read nor write lock
 814          * are held by another thread
 815          * and returns immediately, setting the write lock hold count to
 816          * one.
 817          *
 818          * <p>If the current thread already holds this lock then the
 819          * hold count is incremented by one and the method returns
 820          * immediately.
 821          *
 822          * <p>If the lock is held by another thread then the current
 823          * thread becomes disabled for thread scheduling purposes and
 824          * lies dormant until one of two things happens:
 825          *
 826          * <ul>
 827          *
 828          * <li>The write lock is acquired by the current thread; or
 829          *
 830          * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 831          * the current thread.
 832          *
 833          * </ul>
 834          *
 835          * <p>If the write lock is acquired by the current thread then the
 836          * lock hold count is set to one.
 837          *
 838          * <p>If the current thread:
 839          *
 840          * <ul>
 841          *
 842          * <li>has its interrupted status set on entry to this method;
 843          * or
 844          *
 845          * <li>is {@linkplain Thread#interrupt interrupted} while
 846          * acquiring the write lock,
 847          *
 848          * </ul>
 849          *
 850          * then {@link InterruptedException} is thrown and the current
 851          * thread's interrupted status is cleared.
 852          *
 853          * <p>In this implementation, as this method is an explicit
 854          * interruption point, preference is given to responding to
 855          * the interrupt over normal or reentrant acquisition of the
 856          * lock.
 857          *
 858          * @throws InterruptedException if the current thread is interrupted
 859          */
 860         public void lockInterruptibly() throws InterruptedException {
 861             sync.acquireInterruptibly(1);
 862         }
 863
 864         /**
 865          * Acquires the write lock only if it is not held by another thread
 866          * at the time of invocation.
 867          *
 868          * <p>Acquires the write lock if neither the read nor write lock
 869          * are held by another thread
 870          * and returns immediately with the value {@code true},
 871          * setting the write lock hold count to one. Even when this lock has
 872          * been set to use a fair ordering policy, a call to
 873          * {@code tryLock()} <em>will</em> immediately acquire the
 874          * lock if it is available, whether or not other threads are
 875          * currently waiting for the write lock.  This &quot;barging&quot;
 876          * behavior can be useful in certain circumstances, even
 877          * though it breaks fairness. If you want to honor the
 878          * fairness setting for this lock, then use {@link
 879          * #tryLock(long, TimeUnit) tryLock(0, TimeUnit.SECONDS) }
 880          * which is almost equivalent (it also detects interruption).
 881          *
 882          * <p> If the current thread already holds this lock then the
 883          * hold count is incremented by one and the method returns
 884          * {@code true}.
 885          *
 886          * <p>If the lock is held by another thread then this method
 887          * will return immediately with the value {@code false}.
 888          *
 889          * @return {@code true} if the lock was free and was acquired
 890          * by the current thread, or the write lock was already held
 891          * by the current thread; and {@code false} otherwise.
 892          */
 893         public boolean tryLock( ) {
 894             return sync.tryWriteLock();
 895         }
 896
 897         /**
 898          * Acquires the write lock if it is not held by another thread
 899          * within the given waiting time and the current thread has
 900          * not been {@linkplain Thread#interrupt interrupted}.
 901          *
 902          * <p>Acquires the write lock if neither the read nor write lock
 903          * are held by another thread
 904          * and returns immediately with the value {@code true},
 905          * setting the write lock hold count to one. If this lock has been
 906          * set to use a fair ordering policy then an available lock
 907          * <em>will not</em> be acquired if any other threads are
 908          * waiting for the write lock. This is in contrast to the {@link
 909          * #tryLock()} method. If you want a timed {@code tryLock}
 910          * that does permit barging on a fair lock then combine the
 911          * timed and un-timed forms together:
 912          *
 913          * <pre>if (lock.tryLock() || lock.tryLock(timeout, unit) ) { ... }
 914          * </pre>
 915          *
 916          * <p>If the current thread already holds this lock then the
 917          * hold count is incremented by one and the method returns
 918          * {@code true}.
 919          *
 920          * <p>If the lock is held by another thread then the current
 921          * thread becomes disabled for thread scheduling purposes and
 922          * lies dormant until one of three things happens:
 923          *
 924          * <ul>
 925          *
 926          * <li>The write lock is acquired by the current thread; or
 927          *
 928          * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 929          * the current thread; or
 930          *
 931          * <li>The specified waiting time elapses
 932          *
 933          * </ul>
 934          *
 935          * <p>If the write lock is acquired then the value {@code true} is
 936          * returned and the write lock hold count is set to one.
 937          *
 938          * <p>If the current thread:
 939          *
 940          * <ul>
 941          *
 942          * <li>has its interrupted status set on entry to this method;
 943          * or
 944          *
 945          * <li>is {@linkplain Thread#interrupt interrupted} while
 946          * acquiring the write lock,
 947          *
 948          * </ul>
 949          *
 950          * then {@link InterruptedException} is thrown and the current
 951          * thread's interrupted status is cleared.
 952          *
 953          * <p>If the specified waiting time elapses then the value
 954          * {@code false} is returned.  If the time is less than or
 955          * equal to zero, the method will not wait at all.
 956          *
 957          * <p>In this implementation, as this method is an explicit
 958          * interruption point, preference is given to responding to
 959          * the interrupt over normal or reentrant acquisition of the
 960          * lock, and over reporting the elapse of the waiting time.
 961          *
 962          * @param timeout the time to wait for the write lock
 963          * @param unit the time unit of the timeout argument
 964          *
 965          * @return {@code true} if the lock was free and was acquired
 966          * by the current thread, or the write lock was already held by the
 967          * current thread; and {@code false} if the waiting time
 968          * elapsed before the lock could be acquired.
 969          *
 970          * @throws InterruptedException if the current thread is interrupted
 971          * @throws NullPointerException if the time unit is null
 972          *
 973          */
 974         public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
 975             return sync.tryAcquireNanos(1, unit.toNanos(timeout));
 976         }
 977
 978         /**
 979          * Attempts to release this lock.
 980          *
 981          * <p>If the current thread is the holder of this lock then
 982          * the hold count is decremented. If the hold count is now
 983          * zero then the lock is released.  If the current thread is
 984          * not the holder of this lock then {@link
 985          * IllegalMonitorStateException} is thrown.
 986          *
 987          * @throws IllegalMonitorStateException if the current thread does not
 988          * hold this lock.
 989          */
 990         public void unlock() {
 991             sync.release(1);
 992         }
 993
 994         /**
 995          * Returns a {@link Condition} instance for use with this
 996          * {@link Lock} instance.
 997          * <p>The returned {@link Condition} instance supports the same
 998          * usages as do the {@link Object} monitor methods ({@link
 999          * Object#wait() wait}, {@link Object#notify notify}, and {@link
1000          * Object#notifyAll notifyAll}) when used with the built-in
1001          * monitor lock.
1002          *
1003          * <ul>
1004          *
1005          * <li>If this write lock is not held when any {@link
1006          * Condition} method is called then an {@link
1007          * IllegalMonitorStateException} is thrown.  (Read locks are
1008          * held independently of write locks, so are not checked or
1009          * affected. However it is essentially always an error to
1010          * invoke a condition waiting method when the current thread
1011          * has also acquired read locks, since other threads that
1012          * could unblock it will not be able to acquire the write
1013          * lock.)
1014          *
1015          * <li>When the condition {@linkplain Condition#await() waiting}
1016          * methods are called the write lock is released and, before
1017          * they return, the write lock is reacquired and the lock hold
1018          * count restored to what it was when the method was called.
1019          *
1020          * <li>If a thread is {@linkplain Thread#interrupt interrupted} while
1021          * waiting then the wait will terminate, an {@link
1022          * InterruptedException} will be thrown, and the thread's
1023          * interrupted status will be cleared.
1024          *
1025          * <li> Waiting threads are signalled in FIFO order.
1026          *
1027          * <li>The ordering of lock reacquisition for threads returning
1028          * from waiting methods is the same as for threads initially
1029          * acquiring the lock, which is in the default case not specified,
1030          * but for <em>fair</em> locks favors those threads that have been
1031          * waiting the longest.
1032          *
1033          * </ul>
1034          *
1035          * @return the Condition object
1036          */
1037         public Condition newCondition() {
1038             return sync.newCondition();
1039         }
1040
1041         /**
1042          * Returns a string identifying this lock, as well as its lock
1043          * state.  The state, in brackets includes either the String
1044          * {@code "Unlocked"} or the String {@code "Locked by"}
1045          * followed by the {@linkplain Thread#getName name} of the owning thread.
1046          *
1047          * @return a string identifying this lock, as well as its lock state
1048          */
1049         public String toString() {
1050             Thread o = sync.getOwner();
1051             return super.toString() + ((o == null) ?
1052                                        "[Unlocked]" :
1053                                        "[Locked by thread " + o.getName() + "]");
1054         }
1055
1056         /**
1057          * Queries if this write lock is held by the current thread.
1058          * Identical in effect to {@link
1059          * ReentrantReadWriteLock#isWriteLockedByCurrentThread}.
1060          *
1061          * @return {@code true} if the current thread holds this lock and
1062          *         {@code false} otherwise
1063          * @since 1.6
1064          */
1065         public boolean isHeldByCurrentThread() {
1066             return sync.isHeldExclusively();
1067         }
1068
1069         /**
1070          * Queries the number of holds on this write lock by the current
1071          * thread.  A thread has a hold on a lock for each lock action
1072          * that is not matched by an unlock action.  Identical in effect
1073          * to {@link ReentrantReadWriteLock#getWriteHoldCount}.
1074          *
1075          * @return the number of holds on this lock by the current thread,
1076          *         or zero if this lock is not held by the current thread
1077          * @since 1.6
1078          */
1079         public int getHoldCount() {
1080             return sync.getWriteHoldCount();
1081         }
1082     }
1083
1084     // Instrumentation and status
1085
1086     /**
1087      * Returns {@code true} if this lock has fairness set true.
1088      *
1089      * @return {@code true} if this lock has fairness set true
1090      */
1091     public final boolean isFair() {
1092         return sync instanceof FairSync;
1093     }
1094
1095     /**
1096      * Returns the thread that currently owns the write lock, or
1097      * {@code null} if not owned. When this method is called by a
1098      * thread that is not the owner, the return value reflects a
1099      * best-effort approximation of current lock status. For example,
1100      * the owner may be momentarily {@code null} even if there are
1101      * threads trying to acquire the lock but have not yet done so.
1102      * This method is designed to facilitate construction of
1103      * subclasses that provide more extensive lock monitoring
1104      * facilities.
1105      *
1106      * @return the owner, or {@code null} if not owned
1107      */
1108     protected Thread getOwner() {
1109         return sync.getOwner();
1110     }
1111
1112     /**
1113      * Queries the number of read locks held for this lock. This
1114      * method is designed for use in monitoring system state, not for
1115      * synchronization control.
1116      * @return the number of read locks held.
1117      */
1118     public int getReadLockCount() {
1119         return sync.getReadLockCount();
1120     }
1121
1122     /**
1123      * Queries if the write lock is held by any thread. This method is
1124      * designed for use in monitoring system state, not for
1125      * synchronization control.
1126      *
1127      * @return {@code true} if any thread holds the write lock and
1128      *         {@code false} otherwise
1129      */
1130     public boolean isWriteLocked() {
1131         return sync.isWriteLocked();
1132     }
1133
1134     /**
1135      * Queries if the write lock is held by the current thread.
1136      *
1137      * @return {@code true} if the current thread holds the write lock and
1138      *         {@code false} otherwise
1139      */
1140     public boolean isWriteLockedByCurrentThread() {
1141         return sync.isHeldExclusively();
1142     }
1143
1144     /**
1145      * Queries the number of reentrant write holds on this lock by the
1146      * current thread.  A writer thread has a hold on a lock for
1147      * each lock action that is not matched by an unlock action.
1148      *
1149      * @return the number of holds on the write lock by the current thread,
1150      *         or zero if the write lock is not held by the current thread
1151      */
1152     public int getWriteHoldCount() {
1153         return sync.getWriteHoldCount();
1154     }
1155
1156     /**
1157      * Queries the number of reentrant read holds on this lock by the
1158      * current thread.  A reader thread has a hold on a lock for
1159      * each lock action that is not matched by an unlock action.
1160      *
1161      * @return the number of holds on the read lock by the current thread,
1162      *         or zero if the read lock is not held by the current thread
1163      * @since 1.6
1164      */
1165     public int getReadHoldCount() {
1166         return sync.getReadHoldCount();
1167     }
1168
1169     /**
1170      * Returns a collection containing threads that may be waiting to
1171      * acquire the write lock.  Because the actual set of threads may
1172      * change dynamically while constructing this result, the returned
1173      * collection is only a best-effort estimate.  The elements of the
1174      * returned collection are in no particular order.  This method is
1175      * designed to facilitate construction of subclasses that provide
1176      * more extensive lock monitoring facilities.
1177      *
1178      * @return the collection of threads
1179      */
1180     protected Collection<Thread> getQueuedWriterThreads() {
1181         return sync.getExclusiveQueuedThreads();
1182     }
1183
1184     /**
1185      * Returns a collection containing threads that may be waiting to
1186      * acquire the read lock.  Because the actual set of threads may
1187      * change dynamically while constructing this result, the returned
1188      * collection is only a best-effort estimate.  The elements of the
1189      * returned collection are in no particular order.  This method is
1190      * designed to facilitate construction of subclasses that provide
1191      * more extensive lock monitoring facilities.
1192      *
1193      * @return the collection of threads
1194      */
1195     protected Collection<Thread> getQueuedReaderThreads() {
1196         return sync.getSharedQueuedThreads();
1197     }
1198
1199     /**
1200      * Queries whether any threads are waiting to acquire the read or
1201      * write lock. Note that because cancellations may occur at any
1202      * time, a {@code true} return does not guarantee that any other
1203      * thread will ever acquire a lock.  This method is designed
1204      * primarily for use in monitoring of the system state.
1205      *
1206      * @return {@code true} if there may be other threads waiting to
1207      *         acquire the lock
1208      */
1209     public final boolean hasQueuedThreads() {
1210         return sync.hasQueuedThreads();
1211     }
1212
1213     /**
1214      * Queries whether the given thread is waiting to acquire either
1215      * the read or write lock. Note that because cancellations may
1216      * occur at any time, a {@code true} return does not guarantee
1217      * that this thread will ever acquire a lock.  This method is
1218      * designed primarily for use in monitoring of the system state.
1219      *
1220      * @param thread the thread
1221      * @return {@code true} if the given thread is queued waiting for this lock
1222      * @throws NullPointerException if the thread is null
1223      */
1224     public final boolean hasQueuedThread(Thread thread) {
1225         return sync.isQueued(thread);
1226     }
1227
1228     /**
1229      * Returns an estimate of the number of threads waiting to acquire
1230      * either the read or write lock.  The value is only an estimate
1231      * because the number of threads may change dynamically while this
1232      * method traverses internal data structures.  This method is
1233      * designed for use in monitoring of the system state, not for
1234      * synchronization control.
1235      *
1236      * @return the estimated number of threads waiting for this lock
1237      */
1238     public final int getQueueLength() {
1239         return sync.getQueueLength();
1240     }
1241
1242     /**
1243      * Returns a collection containing threads that may be waiting to
1244      * acquire either the read or write lock.  Because the actual set
1245      * of threads may change dynamically while constructing this
1246      * result, the returned collection is only a best-effort estimate.
1247      * The elements of the returned collection are in no particular
1248      * order.  This method is designed to facilitate construction of
1249      * subclasses that provide more extensive monitoring facilities.
1250      *
1251      * @return the collection of threads
1252      */
1253     protected Collection<Thread> getQueuedThreads() {
1254         return sync.getQueuedThreads();
1255     }
1256
1257     /**
1258      * Queries whether any threads are waiting on the given condition
1259      * associated with the write lock. Note that because timeouts and
1260      * interrupts may occur at any time, a {@code true} return does
1261      * not guarantee that a future {@code signal} will awaken any
1262      * threads.  This method is designed primarily for use in
1263      * monitoring of the system state.
1264      *
1265      * @param condition the condition
1266      * @return {@code true} if there are any waiting threads
1267      * @throws IllegalMonitorStateException if this lock is not held
1268      * @throws IllegalArgumentException if the given condition is
1269      *         not associated with this lock
1270      * @throws NullPointerException if the condition is null
1271      */
1272     public boolean hasWaiters(Condition condition) {
1273         if (condition == null)
1274             throw new NullPointerException();
1275         if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
1276             throw new IllegalArgumentException("not owner");
1277         return sync.hasWaiters((AbstractQueuedSynchronizer.ConditionObject)condition);
1278     }
1279
1280     /**
1281      * Returns an estimate of the number of threads waiting on the
1282      * given condition associated with the write lock. Note that because
1283      * timeouts and interrupts may occur at any time, the estimate
1284      * serves only as an upper bound on the actual number of waiters.
1285      * This method is designed for use in monitoring of the system
1286      * state, not for synchronization control.
1287      *
1288      * @param condition the condition
1289      * @return the estimated number of waiting threads
1290      * @throws IllegalMonitorStateException if this lock is not held
1291      * @throws IllegalArgumentException if the given condition is
1292      *         not associated with this lock
1293      * @throws NullPointerException if the condition is null
1294      */
1295     public int getWaitQueueLength(Condition condition) {
1296         if (condition == null)
1297             throw new NullPointerException();
1298         if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
1299             throw new IllegalArgumentException("not owner");
1300         return sync.getWaitQueueLength((AbstractQueuedSynchronizer.ConditionObject)condition);
1301     }
1302
1303     /**
1304      * Returns a collection containing those threads that may be
1305      * waiting on the given condition associated with the write lock.
1306      * Because the actual set of threads may change dynamically while
1307      * constructing this result, the returned collection is only a
1308      * best-effort estimate. The elements of the returned collection
1309      * are in no particular order.  This method is designed to
1310      * facilitate construction of subclasses that provide more
1311      * extensive condition monitoring facilities.
1312      *
1313      * @param condition the condition
1314      * @return the collection of threads
1315      * @throws IllegalMonitorStateException if this lock is not held
1316      * @throws IllegalArgumentException if the given condition is
1317      *         not associated with this lock
1318      * @throws NullPointerException if the condition is null
1319      */
1320     protected Collection<Thread> getWaitingThreads(Condition condition) {
1321         if (condition == null)
1322             throw new NullPointerException();
1323         if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
1324             throw new IllegalArgumentException("not owner");
1325         return sync.getWaitingThreads((AbstractQueuedSynchronizer.ConditionObject)condition);
1326     }
1327
1328     /**
1329      * Returns a string identifying this lock, as well as its lock state.
1330      * The state, in brackets, includes the String {@code "Write locks ="}
1331      * followed by the number of reentrantly held write locks, and the
1332      * String {@code "Read locks ="} followed by the number of held
1333      * read locks.
1334      *
1335      * @return a string identifying this lock, as well as its lock state
1336      */
1337     public String toString() {
1338         int c = sync.getCount();
1339         int w = Sync.exclusiveCount(c);
1340         int r = Sync.sharedCount(c);
1341
1342         return super.toString() +
1343             "[Write locks = " + w + ", Read locks = " + r + "]";
1344     }
1345
1346 }