content: /*
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  /*
   * This file is available under and governed by the GNU General Public
   * License version 2 only, as published by the Free Software Foundation.
   * However, the following notice accompanied the original version of this
   * file:
   *
   * Written by Doug Lea with assistance from members of JCP JSR-166
   * Expert Group and released to the public domain, as explained at
   * http://creativecommons.org/publicdomain/zero/1.0/
   */
  
  package java.util.concurrent.locks;
  
  import java.util.concurrent.TimeUnit;
  
  /**
   * A capability-based lock with three modes for controlling read/write
   * access.  The state of a StampedLock consists of a version and mode.
   * Lock acquisition methods return a stamp that represents and
   * controls access with respect to a lock state; "try" versions of
   * these methods may instead return the special value zero to
   * represent failure to acquire access. Lock release and conversion
   * methods require stamps as arguments, and fail if they do not match
   * the state of the lock. The three modes are:
   *
   * <ul>
   *
   *  <li><b>Writing.</b> Method {@link #writeLock} possibly blocks
   *   waiting for exclusive access, returning a stamp that can be used
   *   in method {@link #unlockWrite} to release the lock. Untimed and
   *   timed versions of {@code tryWriteLock} are also provided. When
   *   the lock is held in write mode, no read locks may be obtained,
   *   and all optimistic read validations will fail.
   *
   *  <li><b>Reading.</b> Method {@link #readLock} possibly blocks
   *   waiting for non-exclusive access, returning a stamp that can be
   *   used in method {@link #unlockRead} to release the lock. Untimed
   *   and timed versions of {@code tryReadLock} are also provided.
   *
   *  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
   *   returns a non-zero stamp only if the lock is not currently held
   *   in write mode. Method {@link #validate} returns true if the lock
   *   has not been acquired in write mode since obtaining a given
   *   stamp.  This mode can be thought of as an extremely weak version
   *   of a read-lock, that can be broken by a writer at any time.  The
   *   use of optimistic mode for short read-only code segments often
   *   reduces contention and improves throughput.  However, its use is
   *   inherently fragile.  Optimistic read sections should only read
   *   fields and hold them in local variables for later use after
   *   validation. Fields read while in optimistic mode may be wildly
   *   inconsistent, so usage applies only when you are familiar enough
   *   with data representations to check consistency and/or repeatedly
   *   invoke method {@code validate()}.  For example, such steps are
   *   typically required when first reading an object or array
   *   reference, and then accessing one of its fields, elements or
   *   methods.
   *
   * </ul>
   *
   * <p>This class also supports methods that conditionally provide
   * conversions across the three modes. For example, method {@link
   * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning
   * a valid write stamp if (1) already in writing mode (2) in reading
   * mode and there are no other readers or (3) in optimistic mode and
   * the lock is available. The forms of these methods are designed to
   * help reduce some of the code bloat that otherwise occurs in
   * retry-based designs.
   *
   * <p>StampedLocks are designed for use as internal utilities in the
   * development of thread-safe components. Their use relies on
   * knowledge of the internal properties of the data, objects, and
   * methods they are protecting.  They are not reentrant, so locked
   * bodies should not call other unknown methods that may try to
   * re-acquire locks (although you may pass a stamp to other methods
   * that can use or convert it).  The use of read lock modes relies on
   * the associated code sections being side-effect-free.  Unvalidated
   * optimistic read sections cannot call methods that are not known to
   * tolerate potential inconsistencies.  Stamps use finite
   * representations, and are not cryptographically secure (i.e., a
   * valid stamp may be guessable). Stamp values may recycle after (no
   * sooner than) one year of continuous operation. A stamp held without
   * use or validation for longer than this period may fail to validate
   * correctly.  StampedLocks are serializable, but always deserialize
   * into initial unlocked state, so they are not useful for remote
   * locking.
   *
   * <p>The scheduling policy of StampedLock does not consistently
   * prefer readers over writers or vice versa.  All "try" methods are
   * best-effort and do not necessarily conform to any scheduling or
   * fairness policy. A zero return from any "try" method for acquiring
   * or converting locks does not carry any information about the state
   * of the lock; a subsequent invocation may succeed.
   *
   * <p>Because it supports coordinated usage across multiple lock
   * modes, this class does not directly implement the {@link Lock} or
   * {@link ReadWriteLock} interfaces. However, a StampedLock may be
   * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link
   * #asReadWriteLock()} in applications requiring only the associated
   * set of functionality.
   *
   * <p><b>Sample Usage.</b> The following illustrates some usage idioms
   * in a class that maintains simple two-dimensional points. The sample
   * code illustrates some try/catch conventions even though they are
   * not strictly needed here because no exceptions can occur in their
   * bodies.<br>
   *
   * <pre> {@code
   * class Point {
   *   private double x, y;
   *   private final StampedLock sl = new StampedLock();
   *
   *   void move(double deltaX, double deltaY) { // an exclusively locked method
   *     long stamp = sl.writeLock();
   *     try {
   *       x += deltaX;
   *       y += deltaY;
   *     } finally {
   *       sl.unlockWrite(stamp);
   *     }
   *   }
   *
   *   double distanceFromOrigin() { // A read-only method
   *     long stamp = sl.tryOptimisticRead();
   *     double currentX = x, currentY = y;
   *     if (!sl.validate(stamp)) {
   *        stamp = sl.readLock();
   *        try {
   *          currentX = x;
   *          currentY = y;
   *        } finally {
   *           sl.unlockRead(stamp);
   *        }
   *     }
   *     return Math.sqrt(currentX * currentX + currentY * currentY);
   *   }
   *
   *   void moveIfAtOrigin(double newX, double newY) { // upgrade
   *     // Could instead start with optimistic, not read mode
   *     long stamp = sl.readLock();
   *     try {
   *       while (x == 0.0 && y == 0.0) {
   *         long ws = sl.tryConvertToWriteLock(stamp);
   *         if (ws != 0L) {
   *           stamp = ws;
   *           x = newX;
   *           y = newY;
   *           break;
   *         }
   *         else {
   *           sl.unlockRead(stamp);
   *           stamp = sl.writeLock();
   *         }
   *       }
   *     } finally {
   *       sl.unlock(stamp);
   *     }
   *   }
   * }}</pre>
   *
   * @since 1.8
   * @author Doug Lea
   */
  public class StampedLock implements java.io.Serializable {
      /*
       * Algorithmic notes:
       *
       * The design employs elements of Sequence locks
       * (as used in linux kernels; see Lameter's
       * http://www.lameter.com/gelato2005.pdf
       * and elsewhere; see
       * Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
       * and Ordered RW locks (see Shirako et al
       * http://dl.acm.org/citation.cfm?id=2312015)
       *
       * Conceptually, the primary state of the lock includes a sequence
       * number that is odd when write-locked and even otherwise.
       * However, this is offset by a reader count that is non-zero when
       * read-locked.  The read count is ignored when validating
       * "optimistic" seqlock-reader-style stamps.  Because we must use
       * a small finite number of bits (currently 7) for readers, a
       * supplementary reader overflow word is used when the number of
       * readers exceeds the count field. We do this by treating the max
       * reader count value (RBITS) as a spinlock protecting overflow
       * updates.
       *
       * Waiters use a modified form of CLH lock used in
       * AbstractQueuedSynchronizer (see its internal documentation for
       * a fuller account), where each node is tagged (field mode) as
       * either a reader or writer. Sets of waiting readers are grouped
       * (linked) under a common node (field cowait) so act as a single
       * node with respect to most CLH mechanics.  By virtue of the
       * queue structure, wait nodes need not actually carry sequence
       * numbers; we know each is greater than its predecessor.  This
       * simplifies the scheduling policy to a mainly-FIFO scheme that
       * incorporates elements of Phase-Fair locks (see Brandenburg &
       * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
       * particular, we use the phase-fair anti-barging rule: If an
       * incoming reader arrives while read lock is held but there is a
       * queued writer, this incoming reader is queued.  (This rule is
       * responsible for some of the complexity of method acquireRead,
       * but without it, the lock becomes highly unfair.) Method release
       * does not (and sometimes cannot) itself wake up cowaiters. This
       * is done by the primary thread, but helped by any other threads
       * with nothing better to do in methods acquireRead and
       * acquireWrite.
       *
       * These rules apply to threads actually queued. All tryLock forms
       * opportunistically try to acquire locks regardless of preference
       * rules, and so may "barge" their way in.  Randomized spinning is
       * used in the acquire methods to reduce (increasingly expensive)
       * context switching while also avoiding sustained memory
       * thrashing among many threads.  We limit spins to the head of
       * queue. A thread spin-waits up to SPINS times (where each
       * iteration decreases spin count with 50% probability) before
       * blocking. If, upon wakening it fails to obtain lock, and is
       * still (or becomes) the first waiting thread (which indicates
       * that some other thread barged and obtained lock), it escalates
       * spins (up to MAX_HEAD_SPINS) to reduce the likelihood of
       * continually losing to barging threads.
       *
       * Nearly all of these mechanics are carried out in methods
       * acquireWrite and acquireRead, that, as typical of such code,
       * sprawl out because actions and retries rely on consistent sets
       * of locally cached reads.
       *
       * As noted in Boehm's paper (above), sequence validation (mainly
       * method validate()) requires stricter ordering rules than apply
       * to normal volatile reads (of "state").  To force orderings of
       * reads before a validation and the validation itself in those
       * cases where this is not already forced, we use
       * Unsafe.loadFence.
       *
       * The memory layout keeps lock state and queue pointers together
       * (normally on the same cache line). This usually works well for
       * read-mostly loads. In most other cases, the natural tendency of
       * adaptive-spin CLH locks to reduce memory contention lessens
       * motivation to further spread out contended locations, but might
       * be subject to future improvements.
       */
  
      private static final long serialVersionUID = -6001602636862214147L;
  
      /** Number of processors, for spin control */
      private static final int NCPU = Runtime.getRuntime().availableProcessors();
  
      /** Maximum number of retries before enqueuing on acquisition */
      private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
  
      /** Maximum number of retries before blocking at head on acquisition */
      private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;
  
      /** Maximum number of retries before re-blocking */
      private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;
  
      /** The period for yielding when waiting for overflow spinlock */
      private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
  
      /** The number of bits to use for reader count before overflowing */
      private static final int LG_READERS = 7;
  
      // Values for lock state and stamp operations
      private static final long RUNIT = 1L;
      private static final long WBIT  = 1L << LG_READERS;
      private static final long RBITS = WBIT - 1L;
      private static final long RFULL = RBITS - 1L;
      private static final long ABITS = RBITS | WBIT;
      private static final long SBITS = ~RBITS; // note overlap with ABITS
  
      // Initial value for lock state; avoid failure value zero
      private static final long ORIGIN = WBIT << 1;
  
      // Special value from cancelled acquire methods so caller can throw IE
      private static final long INTERRUPTED = 1L;
  
      // Values for node status; order matters
      private static final int WAITING   = -1;
      private static final int CANCELLED =  1;
  
      // Modes for nodes (int not boolean to allow arithmetic)
      private static final int RMODE = 0;
      private static final int WMODE = 1;
  
      /** Wait nodes */
      static final class WNode {
          volatile WNode prev;
          volatile WNode next;
          volatile WNode cowait;    // list of linked readers
          volatile Thread thread;   // non-null while possibly parked
          volatile int status;      // 0, WAITING, or CANCELLED
          final int mode;           // RMODE or WMODE
          WNode(int m, WNode p) { mode = m; prev = p; }
      }
  
      /** Head of CLH queue */
      private transient volatile WNode whead;
      /** Tail (last) of CLH queue */
      private transient volatile WNode wtail;
  
      // views
      transient ReadLockView readLockView;
      transient WriteLockView writeLockView;
      transient ReadWriteLockView readWriteLockView;
  
      /** Lock sequence/state */
      private transient volatile long state;
      /** extra reader count when state read count saturated */
      private transient int readerOverflow;
  
      /**
       * Creates a new lock, initially in unlocked state.
       */
      public StampedLock() {
          state = ORIGIN;
      }
  
      /**
       * Exclusively acquires the lock, blocking if necessary
       * until available.
       *
       * @return a stamp that can be used to unlock or convert mode
       */
      public long writeLock() {
          long s, next;  // bypass acquireWrite in fully unlocked case only
          return ((((s = state) & ABITS) == 0L &&
                   U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
                  next : acquireWrite(false, 0L));
      }
  
      /**
       * Exclusively acquires the lock if it is immediately available.
       *
       * @return a stamp that can be used to unlock or convert mode,
       * or zero if the lock is not available
       */
      public long tryWriteLock() {
          long s, next;
          return ((((s = state) & ABITS) == 0L &&
                   U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
                  next : 0L);
      }
  
      /**
       * Exclusively acquires the lock if it is available within the
       * given time and the current thread has not been interrupted.
       * Behavior under timeout and interruption matches that specified
       * for method {@link Lock#tryLock(long,TimeUnit)}.
       *
       * @param time the maximum time to wait for the lock
       * @param unit the time unit of the {@code time} argument
       * @return a stamp that can be used to unlock or convert mode,
       * or zero if the lock is not available
       * @throws InterruptedException if the current thread is interrupted
       * before acquiring the lock
       */
      public long tryWriteLock(long time, TimeUnit unit)
          throws InterruptedException {
          long nanos = unit.toNanos(time);
          if (!Thread.interrupted()) {
              long next, deadline;
              if ((next = tryWriteLock()) != 0L)
                  return next;
              if (nanos <= 0L)
                  return 0L;
              if ((deadline = System.nanoTime() + nanos) == 0L)
                  deadline = 1L;
              if ((next = acquireWrite(true, deadline)) != INTERRUPTED)
                  return next;
          }
          throw new InterruptedException();
      }
  
      /**
       * Exclusively acquires the lock, blocking if necessary
       * until available or the current thread is interrupted.
       * Behavior under interruption matches that specified
       * for method {@link Lock#lockInterruptibly()}.
       *
       * @return a stamp that can be used to unlock or convert mode
       * @throws InterruptedException if the current thread is interrupted
       * before acquiring the lock
       */
      public long writeLockInterruptibly() throws InterruptedException {
          long next;
          if (!Thread.interrupted() &&
              (next = acquireWrite(true, 0L)) != INTERRUPTED)
              return next;
          throw new InterruptedException();
      }
  
      /**
       * Non-exclusively acquires the lock, blocking if necessary
       * until available.
       *
       * @return a stamp that can be used to unlock or convert mode
       */
      public long readLock() {
          long s = state, next;  // bypass acquireRead on common uncontended case
          return ((whead == wtail && (s & ABITS) < RFULL &&
                   U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
                  next : acquireRead(false, 0L));
      }
  
      /**
       * Non-exclusively acquires the lock if it is immediately available.
       *
       * @return a stamp that can be used to unlock or convert mode,
       * or zero if the lock is not available
       */
      public long tryReadLock() {
          for (;;) {
              long s, m, next;
              if ((m = (s = state) & ABITS) == WBIT)
                  return 0L;
              else if (m < RFULL) {
                  if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
                      return next;
              }
              else if ((next = tryIncReaderOverflow(s)) != 0L)
                  return next;
          }
      }
  
      /**
       * Non-exclusively acquires the lock if it is available within the
       * given time and the current thread has not been interrupted.
       * Behavior under timeout and interruption matches that specified
       * for method {@link Lock#tryLock(long,TimeUnit)}.
       *
       * @param time the maximum time to wait for the lock
       * @param unit the time unit of the {@code time} argument
       * @return a stamp that can be used to unlock or convert mode,
       * or zero if the lock is not available
       * @throws InterruptedException if the current thread is interrupted
       * before acquiring the lock
       */
      public long tryReadLock(long time, TimeUnit unit)
          throws InterruptedException {
          long s, m, next, deadline;
          long nanos = unit.toNanos(time);
          if (!Thread.interrupted()) {
              if ((m = (s = state) & ABITS) != WBIT) {
                  if (m < RFULL) {
                      if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
                          return next;
                  }
                  else if ((next = tryIncReaderOverflow(s)) != 0L)
                      return next;
              }
              if (nanos <= 0L)
                  return 0L;
              if ((deadline = System.nanoTime() + nanos) == 0L)
                  deadline = 1L;
              if ((next = acquireRead(true, deadline)) != INTERRUPTED)
                  return next;
          }
          throw new InterruptedException();
      }
  
      /**
       * Non-exclusively acquires the lock, blocking if necessary
       * until available or the current thread is interrupted.
       * Behavior under interruption matches that specified
       * for method {@link Lock#lockInterruptibly()}.
       *
       * @return a stamp that can be used to unlock or convert mode
       * @throws InterruptedException if the current thread is interrupted
       * before acquiring the lock
       */
      public long readLockInterruptibly() throws InterruptedException {
          long next;
          if (!Thread.interrupted() &&
              (next = acquireRead(true, 0L)) != INTERRUPTED)
              return next;
          throw new InterruptedException();
      }
  
      /**
       * Returns a stamp that can later be validated, or zero
       * if exclusively locked.
       *
       * @return a stamp, or zero if exclusively locked
       */
      public long tryOptimisticRead() {
          long s;
          return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;
      }
  
      /**
       * Returns true if the lock has not been exclusively acquired
       * since issuance of the given stamp. Always returns false if the
       * stamp is zero. Always returns true if the stamp represents a
       * currently held lock. Invoking this method with a value not
       * obtained from {@link #tryOptimisticRead} or a locking method
       * for this lock has no defined effect or result.
       *
       * @param stamp a stamp
       * @return {@code true} if the lock has not been exclusively acquired
       * since issuance of the given stamp; else false
       */
      public boolean validate(long stamp) {
          U.loadFence();
          return (stamp & SBITS) == (state & SBITS);
      }
  
      /**
       * If the lock state matches the given stamp, releases the
       * exclusive lock.
       *
       * @param stamp a stamp returned by a write-lock operation
       * @throws IllegalMonitorStateException if the stamp does
       * not match the current state of this lock
       */
      public void unlockWrite(long stamp) {
          WNode h;
          if (state != stamp || (stamp & WBIT) == 0L)
              throw new IllegalMonitorStateException();
          U.putLongVolatile(this, STATE, (stamp += WBIT) == 0L ? ORIGIN : stamp);
          if ((h = whead) != null && h.status != 0)
              release(h);
      }
  
      /**
       * If the lock state matches the given stamp, releases the
       * non-exclusive lock.
       *
       * @param stamp a stamp returned by a read-lock operation
       * @throws IllegalMonitorStateException if the stamp does
       * not match the current state of this lock
       */
      public void unlockRead(long stamp) {
          long s, m; WNode h;
          for (;;) {
              if (((s = state) & SBITS) != (stamp & SBITS) ||
                  (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
                  throw new IllegalMonitorStateException();
              if (m < RFULL) {
                  if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
                      if (m == RUNIT && (h = whead) != null && h.status != 0)
                          release(h);
                      break;
                  }
              }
              else if (tryDecReaderOverflow(s) != 0L)
                  break;
          }
      }
  
      /**
       * If the lock state matches the given stamp, releases the
       * corresponding mode of the lock.
       *
       * @param stamp a stamp returned by a lock operation
       * @throws IllegalMonitorStateException if the stamp does
       * not match the current state of this lock
       */
      public void unlock(long stamp) {
          long a = stamp & ABITS, m, s; WNode h;
          while (((s = state) & SBITS) == (stamp & SBITS)) {
              if ((m = s & ABITS) == 0L)
                  break;
              else if (m == WBIT) {
                  if (a != m)
                      break;
                  U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s);
                  if ((h = whead) != null && h.status != 0)
                      release(h);
                  return;
              }
              else if (a == 0L || a >= WBIT)
                  break;
              else if (m < RFULL) {
                  if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
                      if (m == RUNIT && (h = whead) != null && h.status != 0)
                          release(h);
                      return;
                  }
              }
              else if (tryDecReaderOverflow(s) != 0L)
                  return;
          }
          throw new IllegalMonitorStateException();
      }
  
      /**
       * If the lock state matches the given stamp, atomically performs one of
       * the following actions. If the stamp represents holding a write
       * lock, returns it.  Or, if a read lock, if the write lock is
       * available, releases the read lock and returns a write stamp.
       * Or, if an optimistic read, returns a write stamp only if
       * immediately available. This method returns zero in all other
       * cases.
       *
       * @param stamp a stamp
       * @return a valid write stamp, or zero on failure
       */
      public long tryConvertToWriteLock(long stamp) {
          long a = stamp & ABITS, m, s, next;
          while (((s = state) & SBITS) == (stamp & SBITS)) {
              if ((m = s & ABITS) == 0L) {
                  if (a != 0L)
                      break;
                  if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
                      return next;
              }
              else if (m == WBIT) {
                  if (a != m)
                      break;
                  return stamp;
              }
              else if (m == RUNIT && a != 0L) {
                  if (U.compareAndSwapLong(this, STATE, s,
                                           next = s - RUNIT + WBIT))
                      return next;
              }
              else
                  break;
          }
          return 0L;
      }
  
      /**
       * If the lock state matches the given stamp, atomically performs one of
       * the following actions. If the stamp represents holding a write
       * lock, releases it and obtains a read lock.  Or, if a read lock,
       * returns it. Or, if an optimistic read, acquires a read lock and
       * returns a read stamp only if immediately available. This method
       * returns zero in all other cases.
       *
       * @param stamp a stamp
       * @return a valid read stamp, or zero on failure
       */
      public long tryConvertToReadLock(long stamp) {
          long a = stamp & ABITS, m, s, next; WNode h;
          while (((s = state) & SBITS) == (stamp & SBITS)) {
              if ((m = s & ABITS) == 0L) {
                  if (a != 0L)
                      break;
                  else if (m < RFULL) {
                      if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
                          return next;
                  }
                  else if ((next = tryIncReaderOverflow(s)) != 0L)
                      return next;
              }
              else if (m == WBIT) {
                  if (a != m)
                      break;
                  U.putLongVolatile(this, STATE, next = s + (WBIT + RUNIT));
                  if ((h = whead) != null && h.status != 0)
                      release(h);
                  return next;
              }
              else if (a != 0L && a < WBIT)
                  return stamp;
              else
                  break;
          }
          return 0L;
      }
  
      /**
       * If the lock state matches the given stamp then, atomically, if the stamp
       * represents holding a lock, releases it and returns an
       * observation stamp.  Or, if an optimistic read, returns it if
       * validated. This method returns zero in all other cases, and so
       * may be useful as a form of "tryUnlock".
       *
       * @param stamp a stamp
       * @return a valid optimistic read stamp, or zero on failure
       */
      public long tryConvertToOptimisticRead(long stamp) {
          long a = stamp & ABITS, m, s, next; WNode h;
          U.loadFence();
          for (;;) {
              if (((s = state) & SBITS) != (stamp & SBITS))
                  break;
              if ((m = s & ABITS) == 0L) {
                  if (a != 0L)
                      break;
                  return s;
              }
              else if (m == WBIT) {
                  if (a != m)
                      break;
                  U.putLongVolatile(this, STATE,
                                    next = (s += WBIT) == 0L ? ORIGIN : s);
                  if ((h = whead) != null && h.status != 0)
                      release(h);
                  return next;
              }
              else if (a == 0L || a >= WBIT)
                  break;
              else if (m < RFULL) {
                  if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
                      if (m == RUNIT && (h = whead) != null && h.status != 0)
                          release(h);
                      return next & SBITS;
                  }
              }
              else if ((next = tryDecReaderOverflow(s)) != 0L)
                  return next & SBITS;
          }
          return 0L;
      }
  
      /**
       * Releases the write lock if it is held, without requiring a
       * stamp value. This method may be useful for recovery after
       * errors.
       *
       * @return {@code true} if the lock was held, else false
       */
      public boolean tryUnlockWrite() {
          long s; WNode h;
          if (((s = state) & WBIT) != 0L) {
              U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s);
              if ((h = whead) != null && h.status != 0)
                  release(h);
              return true;
          }
          return false;
      }
  
      /**
       * Releases one hold of the read lock if it is held, without
       * requiring a stamp value. This method may be useful for recovery
       * after errors.
       *
       * @return {@code true} if the read lock was held, else false
       */
      public boolean tryUnlockRead() {
          long s, m; WNode h;
          while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
              if (m < RFULL) {
                  if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
                      if (m == RUNIT && (h = whead) != null && h.status != 0)
                          release(h);
                      return true;
                  }
              }
              else if (tryDecReaderOverflow(s) != 0L)
                  return true;
          }
          return false;
      }
  
      // status monitoring methods
  
      /**
       * Returns combined state-held and overflow read count for given
       * state s.
       */
      private int getReadLockCount(long s) {
          long readers;
          if ((readers = s & RBITS) >= RFULL)
              readers = RFULL + readerOverflow;
          return (int) readers;
      }
  
      /**
       * Returns {@code true} if the lock is currently held exclusively.
       *
       * @return {@code true} if the lock is currently held exclusively
       */
      public boolean isWriteLocked() {
          return (state & WBIT) != 0L;
      }
  
      /**
       * Returns {@code true} if the lock is currently held non-exclusively.
       *
       * @return {@code true} if the lock is currently held non-exclusively
       */
      public boolean isReadLocked() {
          return (state & RBITS) != 0L;
      }
  
      /**
       * Queries the number of read locks held for this lock. This
       * method is designed for use in monitoring system state, not for
       * synchronization control.
       * @return the number of read locks held
       */
      public int getReadLockCount() {
          return getReadLockCount(state);
      }
  
      /**
       * Returns a string identifying this lock, as well as its lock
       * state.  The state, in brackets, includes the String {@code
       * "Unlocked"} or the String {@code "Write-locked"} or the String
       * {@code "Read-locks:"} followed by the current number of
       * read-locks held.
       *
       * @return a string identifying this lock, as well as its lock state
       */
      public String toString() {
          long s = state;
          return super.toString() +
              ((s & ABITS) == 0L ? "[Unlocked]" :
               (s & WBIT) != 0L ? "[Write-locked]" :
               "[Read-locks:" + getReadLockCount(s) + "]");
      }
  
      // views
  
      /**
       * Returns a plain {@link Lock} view of this StampedLock in which
       * the {@link Lock#lock} method is mapped to {@link #readLock},
       * and similarly for other methods. The returned Lock does not
       * support a {@link Condition}; method {@link
       * Lock#newCondition()} throws {@code
       * UnsupportedOperationException}.
       *
       * @return the lock
       */
      public Lock asReadLock() {
          ReadLockView v;
          return ((v = readLockView) != null ? v :
                  (readLockView = new ReadLockView()));
      }
  
      /**
       * Returns a plain {@link Lock} view of this StampedLock in which
       * the {@link Lock#lock} method is mapped to {@link #writeLock},
       * and similarly for other methods. The returned Lock does not
       * support a {@link Condition}; method {@link
       * Lock#newCondition()} throws {@code
       * UnsupportedOperationException}.
       *
       * @return the lock
       */
      public Lock asWriteLock() {
          WriteLockView v;
          return ((v = writeLockView) != null ? v :
                  (writeLockView = new WriteLockView()));
      }
  
      /**
       * Returns a {@link ReadWriteLock} view of this StampedLock in
       * which the {@link ReadWriteLock#readLock()} method is mapped to
       * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
       * {@link #asWriteLock()}.
       *
       * @return the lock
       */
      public ReadWriteLock asReadWriteLock() {
          ReadWriteLockView v;
          return ((v = readWriteLockView) != null ? v :
                  (readWriteLockView = new ReadWriteLockView()));
      }
  
      // view classes
  
      final class ReadLockView implements Lock {
          public void lock() { readLock(); }
          public void lockInterruptibly() throws InterruptedException {
              readLockInterruptibly();
          }
          public boolean tryLock() { return tryReadLock() != 0L; }
          public boolean tryLock(long time, TimeUnit unit)
              throws InterruptedException {
              return tryReadLock(time, unit) != 0L;
          }
          public void unlock() { unstampedUnlockRead(); }
          public Condition newCondition() {
              throw new UnsupportedOperationException();
          }
      }
  
      final class WriteLockView implements Lock {
          public void lock() { writeLock(); }
          public void lockInterruptibly() throws InterruptedException {
              writeLockInterruptibly();
          }
          public boolean tryLock() { return tryWriteLock() != 0L; }
          public boolean tryLock(long time, TimeUnit unit)
              throws InterruptedException {
              return tryWriteLock(time, unit) != 0L;
          }
          public void unlock() { unstampedUnlockWrite(); }
          public Condition newCondition() {
              throw new UnsupportedOperationException();
          }
      }
  
      final class ReadWriteLockView implements ReadWriteLock {
          public Lock readLock() { return asReadLock(); }
          public Lock writeLock() { return asWriteLock(); }
      }
  
      // Unlock methods without stamp argument checks for view classes.
      // Needed because view-class lock methods throw away stamps.
  
      final void unstampedUnlockWrite() {
          WNode h; long s;
          if (((s = state) & WBIT) == 0L)
              throw new IllegalMonitorStateException();
          U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s);
          if ((h = whead) != null && h.status != 0)
              release(h);
      }
  
      final void unstampedUnlockRead() {
          for (;;) {
              long s, m; WNode h;
              if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
                  throw new IllegalMonitorStateException();
              else if (m < RFULL) {
                  if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
                      if (m == RUNIT && (h = whead) != null && h.status != 0)
                          release(h);
                      break;
                  }
              }
              else if (tryDecReaderOverflow(s) != 0L)
                  break;
          }
      }
  
      private void readObject(java.io.ObjectInputStream s)
          throws java.io.IOException, ClassNotFoundException {
          s.defaultReadObject();
          U.putLongVolatile(this, STATE, ORIGIN); // reset to unlocked state
      }
  
      // internals
  
      /**
       * Tries to increment readerOverflow by first setting state
       * access bits value to RBITS, indicating hold of spinlock,
       * then updating, then releasing.
       *
       * @param s a reader overflow stamp: (s & ABITS) >= RFULL
       * @return new stamp on success, else zero
       */
      private long tryIncReaderOverflow(long s) {
          // assert (s & ABITS) >= RFULL;
          if ((s & ABITS) == RFULL) {
              if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
                  ++readerOverflow;
                  U.putLongVolatile(this, STATE, s);
                  return s;
              }
          }
          else if ((LockSupport.nextSecondarySeed() &
                    OVERFLOW_YIELD_RATE) == 0)
              Thread.yield();
          return 0L;
      }
  
      /**
       * Tries to decrement readerOverflow.
       *
       * @param s a reader overflow stamp: (s & ABITS) >= RFULL
       * @return new stamp on success, else zero
       */
      private long tryDecReaderOverflow(long s) {
          // assert (s & ABITS) >= RFULL;
          if ((s & ABITS) == RFULL) {
              if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
                  int r; long next;
                  if ((r = readerOverflow) > 0) {
                      readerOverflow = r - 1;
                      next = s;
                  }
                  else
                      next = s - RUNIT;
                  U.putLongVolatile(this, STATE, next);
                  return next;
              }
          }
          else if ((LockSupport.nextSecondarySeed() &
                    OVERFLOW_YIELD_RATE) == 0)
              Thread.yield();
          return 0L;
      }
  
      /**
       * Wakes up the successor of h (normally whead). This is normally
       * just h.next, but may require traversal from wtail if next
       * pointers are lagging. This may fail to wake up an acquiring
       * thread when one or more have been cancelled, but the cancel
       * methods themselves provide extra safeguards to ensure liveness.
       */
      private void release(WNode h) {
          if (h != null) {
              WNode q; Thread w;
              U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
              if ((q = h.next) == null || q.status == CANCELLED) {
                  for (WNode t = wtail; t != null && t != h; t = t.prev)
                      if (t.status <= 0)
                          q = t;
              }
              if (q != null && (w = q.thread) != null)
                  U.unpark(w);
          }
      }
  
      /**
       * See above for explanation.
       *
       * @param interruptible true if should check interrupts and if so
       * return INTERRUPTED
       * @param deadline if nonzero, the System.nanoTime value to timeout
       * at (and return zero)
       * @return next state, or INTERRUPTED
       */
      private long acquireWrite(boolean interruptible, long deadline) {
          WNode node = null, p;
          for (int spins = -1;;) { // spin while enqueuing
              long m, s, ns;
              if ((m = (s = state) & ABITS) == 0L) {
                  if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
                      return ns;
              }
              else if (spins < 0)
                  spins = (m == WBIT && wtail == whead) ? SPINS : 0;
              else if (spins > 0) {
                  if (LockSupport.nextSecondarySeed() >= 0)
                      --spins;
              }
              else if ((p = wtail) == null) { // initialize queue
                  WNode hd = new WNode(WMODE, null);
                  if (U.compareAndSwapObject(this, WHEAD, null, hd))
                      wtail = hd;
              }
              else if (node == null)
                  node = new WNode(WMODE, p);
              else if (node.prev != p)
                  node.prev = p;
              else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
                  p.next = node;
                  break;
              }
          }
  
          boolean wasInterrupted = false;
          for (int spins = -1;;) {
              WNode h, np, pp; int ps;
              if ((h = whead) == p) {
                  if (spins < 0)
                      spins = HEAD_SPINS;
                  else if (spins < MAX_HEAD_SPINS)
                      spins <<= 1;
                  for (int k = spins;;) { // spin at head
                      long s, ns;
                      if (((s = state) & ABITS) == 0L) {
                          if (U.compareAndSwapLong(this, STATE, s,
                                                   ns = s + WBIT)) {
                              whead = node;
                              node.prev = null;
                              if (wasInterrupted)
                                  Thread.currentThread().interrupt();
                              return ns;
                          }
                      }
                      else if (LockSupport.nextSecondarySeed() >= 0 &&
                               --k <= 0)
                          break;
                  }
              }
              else if (h != null) { // help release stale waiters
                  WNode c; Thread w;
                  while ((c = h.cowait) != null) {
                      if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
                          (w = c.thread) != null)
                          U.unpark(w);
                  }
              }
              if (whead == h) {
                  if ((np = node.prev) != p) {
                      if (np != null)
                          (p = np).next = node;   // stale
                  }
                  else if ((ps = p.status) == 0)
                      U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
                  else if (ps == CANCELLED) {
                      if ((pp = p.prev) != null) {
                          node.prev = pp;
                          pp.next = node;
                      }
                  }
                  else {
                      long time; // 0 argument to park means no timeout
                      if (deadline == 0L)
                          time = 0L;
                      else if ((time = deadline - System.nanoTime()) <= 0L)
                          return cancelWaiter(node, node, false);
                      Thread wt = Thread.currentThread();
                      U.putObject(wt, PARKBLOCKER, this);
                      node.thread = wt;
                      if (p.status < 0 && (p != h || (state & ABITS) != 0L) &&
                          whead == h && node.prev == p)
                          U.park(false, time);  // emulate LockSupport.park
                      node.thread = null;
                      U.putObject(wt, PARKBLOCKER, null);
                      if (Thread.interrupted()) {
                          if (interruptible)
                              return cancelWaiter(node, node, true);
                          wasInterrupted = true;
                      }
                  }
              }
          }
      }
  
      /**
       * See above for explanation.
       *
       * @param interruptible true if should check interrupts and if so
       * return INTERRUPTED
       * @param deadline if nonzero, the System.nanoTime value to timeout
       * at (and return zero)
       * @return next state, or INTERRUPTED
       */
      private long acquireRead(boolean interruptible, long deadline) {
          boolean wasInterrupted = false;
          WNode node = null, p;
          for (int spins = -1;;) {
              WNode h;
              if ((h = whead) == (p = wtail)) {
                  for (long m, s, ns;;) {
                      if ((m = (s = state) & ABITS) < RFULL ?
                          U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
                          (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
                          if (wasInterrupted)
                              Thread.currentThread().interrupt();
                          return ns;
                      }
                      else if (m >= WBIT) {
                          if (spins > 0) {
                              if (LockSupport.nextSecondarySeed() >= 0)
                                  --spins;
                          }
                          else {
                              if (spins == 0) {
                                  WNode nh = whead, np = wtail;
                                  if ((nh == h && np == p) || (h = nh) != (p = np))
                                      break;
                              }
                              spins = SPINS;
                          }
                      }
                  }
              }
              if (p == null) { // initialize queue
                  WNode hd = new WNode(WMODE, null);
                  if (U.compareAndSwapObject(this, WHEAD, null, hd))
                      wtail = hd;
              }
              else if (node == null)
                  node = new WNode(RMODE, p);
              else if (h == p || p.mode != RMODE) {
                  if (node.prev != p)
                      node.prev = p;
                  else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
                      p.next = node;
                      break;
                  }
              }
              else if (!U.compareAndSwapObject(p, WCOWAIT,
                                               node.cowait = p.cowait, node))
                  node.cowait = null;
              else {
                  for (;;) {
                      WNode pp, c; Thread w;
                      if ((h = whead) != null && (c = h.cowait) != null &&
                          U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
                          (w = c.thread) != null) // help release
                          U.unpark(w);
                      if (h == (pp = p.prev) || h == p || pp == null) {
                          long m, s, ns;
                          do {
                              if ((m = (s = state) & ABITS) < RFULL ?
                                  U.compareAndSwapLong(this, STATE, s,
                                                       ns = s + RUNIT) :
                                  (m < WBIT &&
                                   (ns = tryIncReaderOverflow(s)) != 0L)) {
                                  if (wasInterrupted)
                                      Thread.currentThread().interrupt();
                                  return ns;
                              }
                          } while (m < WBIT);
                      }
                      if (whead == h && p.prev == pp) {
                          long time;
                          if (pp == null || h == p || p.status > 0) {
                              node = null; // throw away
                              break;
                          }
                          if (deadline == 0L)
                              time = 0L;
                          else if ((time = deadline - System.nanoTime()) <= 0L) {
                              if (wasInterrupted)
                                  Thread.currentThread().interrupt();
                              return cancelWaiter(node, p, false);
                          }
                          Thread wt = Thread.currentThread();
                          U.putObject(wt, PARKBLOCKER, this);
                          node.thread = wt;
                          if ((h != pp || (state & ABITS) == WBIT) &&
                              whead == h && p.prev == pp)
                              U.park(false, time);
                          node.thread = null;
                          U.putObject(wt, PARKBLOCKER, null);
                          if (Thread.interrupted()) {
                              if (interruptible)
                                  return cancelWaiter(node, p, true);
                              wasInterrupted = true;
                          }
                      }
                  }
              }
          }
  
          for (int spins = -1;;) {
              WNode h, np, pp; int ps;
              if ((h = whead) == p) {
                  if (spins < 0)
                      spins = HEAD_SPINS;
                  else if (spins < MAX_HEAD_SPINS)
                      spins <<= 1;
                  for (int k = spins;;) { // spin at head
                      long m, s, ns;
                      if ((m = (s = state) & ABITS) < RFULL ?
                          U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
                          (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
                          WNode c; Thread w;
                          whead = node;
                          node.prev = null;
                          while ((c = node.cowait) != null) {
                              if (U.compareAndSwapObject(node, WCOWAIT,
                                                         c, c.cowait) &&
                                  (w = c.thread) != null)
                                  U.unpark(w);
                          }
                          if (wasInterrupted)
                              Thread.currentThread().interrupt();
                          return ns;
                      }
                      else if (m >= WBIT &&
                               LockSupport.nextSecondarySeed() >= 0 && --k <= 0)
                          break;
                  }
              }
              else if (h != null) {
                  WNode c; Thread w;
                  while ((c = h.cowait) != null) {
                      if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
                          (w = c.thread) != null)
                          U.unpark(w);
                  }
              }
              if (whead == h) {
                  if ((np = node.prev) != p) {
                      if (np != null)
                          (p = np).next = node;   // stale
                  }
                  else if ((ps = p.status) == 0)
                      U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
                  else if (ps == CANCELLED) {
                      if ((pp = p.prev) != null) {
                          node.prev = pp;
                          pp.next = node;
                      }
                  }
                  else {
                      long time;
                      if (deadline == 0L)
                          time = 0L;
                      else if ((time = deadline - System.nanoTime()) <= 0L)
                          return cancelWaiter(node, node, false);
                      Thread wt = Thread.currentThread();
                      U.putObject(wt, PARKBLOCKER, this);
                      node.thread = wt;
                      if (p.status < 0 &&
                          (p != h || (state & ABITS) == WBIT) &&
                          whead == h && node.prev == p)
                          U.park(false, time);
                      node.thread = null;
                      U.putObject(wt, PARKBLOCKER, null);
                      if (Thread.interrupted()) {
                          if (interruptible)
                              return cancelWaiter(node, node, true);
                          wasInterrupted = true;
                      }
                  }
              }
          }
      }
  
      /**
       * If node non-null, forces cancel status and unsplices it from
       * queue if possible and wakes up any cowaiters (of the node, or
       * group, as applicable), and in any case helps release current
       * first waiter if lock is free. (Calling with null arguments
       * serves as a conditional form of release, which is not currently
       * needed but may be needed under possible future cancellation
       * policies). This is a variant of cancellation methods in
       * AbstractQueuedSynchronizer (see its detailed explanation in AQS
       * internal documentation).
       *
       * @param node if nonnull, the waiter
       * @param group either node or the group node is cowaiting with
       * @param interrupted if already interrupted
       * @return INTERRUPTED if interrupted or Thread.interrupted, else zero
       */
      private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
          if (node != null && group != null) {
              Thread w;
              node.status = CANCELLED;
              // unsplice cancelled nodes from group
              for (WNode p = group, q; (q = p.cowait) != null;) {
                  if (q.status == CANCELLED) {
                      U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
                      p = group; // restart
                  }
                  else
                      p = q;
              }
              if (group == node) {
                  for (WNode r = group.cowait; r != null; r = r.cowait) {
                      if ((w = r.thread) != null)
                          U.unpark(w);       // wake up uncancelled co-waiters
                  }
                  for (WNode pred = node.prev; pred != null; ) { // unsplice
                      WNode succ, pp;        // find valid successor
                      while ((succ = node.next) == null ||
                             succ.status == CANCELLED) {
                          WNode q = null;    // find successor the slow way
                          for (WNode t = wtail; t != null && t != node; t = t.prev)
                              if (t.status != CANCELLED)
                                  q = t;     // don't link if succ cancelled
                          if (succ == q ||   // ensure accurate successor
                              U.compareAndSwapObject(node, WNEXT,
                                                     succ, succ = q)) {
                              if (succ == null && node == wtail)
                                  U.compareAndSwapObject(this, WTAIL, node, pred);
                              break;
                          }
                      }
                      if (pred.next == node) // unsplice pred link
                          U.compareAndSwapObject(pred, WNEXT, node, succ);
                      if (succ != null && (w = succ.thread) != null) {
                          succ.thread = null;
                          U.unpark(w);       // wake up succ to observe new pred
                      }
                      if (pred.status != CANCELLED || (pp = pred.prev) == null)
                          break;
                      node.prev = pp;        // repeat if new pred wrong/cancelled
                      U.compareAndSwapObject(pp, WNEXT, pred, succ);
                      pred = pp;
                  }
              }
          }
          WNode h; // Possibly release first waiter
          while ((h = whead) != null) {
              long s; WNode q; // similar to release() but check eligibility
              if ((q = h.next) == null || q.status == CANCELLED) {
                  for (WNode t = wtail; t != null && t != h; t = t.prev)
                      if (t.status <= 0)
                          q = t;
              }
              if (h == whead) {
                  if (q != null && h.status == 0 &&
                      ((s = state) & ABITS) != WBIT && // waiter is eligible
                      (s == 0L || q.mode == RMODE))
                      release(h);
                  break;
              }
          }
          return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
      }
  
      // Unsafe mechanics
      private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
      private static final long STATE;
      private static final long WHEAD;
      private static final long WTAIL;
      private static final long WNEXT;
      private static final long WSTATUS;
      private static final long WCOWAIT;
      private static final long PARKBLOCKER;
  
      static {
          try {
              STATE = U.objectFieldOffset
                  (StampedLock.class.getDeclaredField("state"));
              WHEAD = U.objectFieldOffset
                  (StampedLock.class.getDeclaredField("whead"));
              WTAIL = U.objectFieldOffset
                  (StampedLock.class.getDeclaredField("wtail"));
  
              WSTATUS = U.objectFieldOffset
                  (WNode.class.getDeclaredField("status"));
              WNEXT = U.objectFieldOffset
                  (WNode.class.getDeclaredField("next"));
              WCOWAIT = U.objectFieldOffset
                  (WNode.class.getDeclaredField("cowait"));
  
              PARKBLOCKER = U.objectFieldOffset
                  (Thread.class.getDeclaredField("parkBlocker"));
          } catch (ReflectiveOperationException e) {
              throw new Error(e);
          }
      }
  }
  