/*

 * 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.ArrayList;

import java.util.Collection;

import java.util.Date;

import java.util.concurrent.TimeUnit;

import java.util.concurrent.ForkJoinPool;

import java.util.concurrent.RejectedExecutionException;

import jdk.internal.misc.Unsafe;

/**

 * Provides a framework for implementing blocking locks and related

 * synchronizers (semaphores, events, etc) that rely on

 * first-in-first-out (FIFO) wait queues.  This class is designed to

 * be a useful basis for most kinds of synchronizers that rely on a

 * single atomic {@code int} value to represent state. Subclasses

 * must define the protected methods that change this state, and which

 * define what that state means in terms of this object being acquired

 * or released.  Given these, the other methods in this class carry

 * out all queuing and blocking mechanics. Subclasses can maintain

 * other state fields, but only the atomically updated {@code int}

 * value manipulated using methods {@link #getState}, {@link

 * #setState} and {@link #compareAndSetState} is tracked with respect

 * to synchronization.

 *

 * <p>Subclasses should be defined as non-public internal helper

 * classes that are used to implement the synchronization properties

 * of their enclosing class.  Class

 * {@code AbstractQueuedSynchronizer} does not implement any

 * synchronization interface.  Instead it defines methods such as

 * {@link #acquireInterruptibly} that can be invoked as

 * appropriate by concrete locks and related synchronizers to

 * implement their public methods.

 *

 * <p>This class supports either or both a default <em>exclusive</em>

 * mode and a <em>shared</em> mode. When acquired in exclusive mode,

 * attempted acquires by other threads cannot succeed. Shared mode

 * acquires by multiple threads may (but need not) succeed. This class

 * does not "understand" these differences except in the

 * mechanical sense that when a shared mode acquire succeeds, the next

 * waiting thread (if one exists) must also determine whether it can

 * acquire as well. Threads waiting in the different modes share the

 * same FIFO queue. Usually, implementation subclasses support only

 * one of these modes, but both can come into play for example in a

 * {@link ReadWriteLock}. Subclasses that support only exclusive or

 * only shared modes need not define the methods supporting the unused mode.

 *

 * <p>This class defines a nested {@link ConditionObject} class that

 * can be used as a {@link Condition} implementation by subclasses

 * supporting exclusive mode for which method {@link

 * #isHeldExclusively} reports whether synchronization is exclusively

 * held with respect to the current thread, method {@link #release}

 * invoked with the current {@link #getState} value fully releases

 * this object, and {@link #acquire}, given this saved state value,

 * eventually restores this object to its previous acquired state.  No

 * {@code AbstractQueuedSynchronizer} method otherwise creates such a

 * condition, so if this constraint cannot be met, do not use it.  The

 * behavior of {@link ConditionObject} depends of course on the

 * semantics of its synchronizer implementation.

 *

 * <p>This class provides inspection, instrumentation, and monitoring

 * methods for the internal queue, as well as similar methods for

 * condition objects. These can be exported as desired into classes

 * using an {@code AbstractQueuedSynchronizer} for their

 * synchronization mechanics.

 *

 * <p>Serialization of this class stores only the underlying atomic

 * integer maintaining state, so deserialized objects have empty

 * thread queues. Typical subclasses requiring serializability will

 * define a {@code readObject} method that restores this to a known

 * initial state upon deserialization.

 *

 * <h2>Usage</h2>

 *

 * <p>To use this class as the basis of a synchronizer, redefine the

 * following methods, as applicable, by inspecting and/or modifying

 * the synchronization state using {@link #getState}, {@link

 * #setState} and/or {@link #compareAndSetState}:

 *

 * <ul>

 * <li>{@link #tryAcquire}

 * <li>{@link #tryRelease}

 * <li>{@link #tryAcquireShared}

 * <li>{@link #tryReleaseShared}

 * <li>{@link #isHeldExclusively}

 * </ul>

 *

 * Each of these methods by default throws {@link

 * UnsupportedOperationException}.  Implementations of these methods

 * must be internally thread-safe, and should in general be short and

 * not block. Defining these methods is the <em>only</em> supported

 * means of using this class. All other methods are declared

 * {@code final} because they cannot be independently varied.

 *

 * <p>You may also find the inherited methods from {@link

 * AbstractOwnableSynchronizer} useful to keep track of the thread

 * owning an exclusive synchronizer.  You are encouraged to use them

 * -- this enables monitoring and diagnostic tools to assist users in

 * determining which threads hold locks.

 *

 * <p>Even though this class is based on an internal FIFO queue, it

 * does not automatically enforce FIFO acquisition policies.  The core

 * of exclusive synchronization takes the form:

 *

 * <pre>

 * <em>Acquire:</em>

 *     while (!tryAcquire(arg)) {

 *        <em>enqueue thread if it is not already queued</em>;

 *        <em>possibly block current thread</em>;

 *     }

 *

 * <em>Release:</em>

 *     if (tryRelease(arg))

 *        <em>unblock the first queued thread</em>;

 * </pre>

 *

 * (Shared mode is similar but may involve cascading signals.)

 *

 * <p id="barging">Because checks in acquire are invoked before

 * enqueuing, a newly acquiring thread may <em>barge</em> ahead of

 * others that are blocked and queued.  However, you can, if desired,

 * define {@code tryAcquire} and/or {@code tryAcquireShared} to

 * disable barging by internally invoking one or more of the inspection

 * methods, thereby providing a <em>fair</em> FIFO acquisition order.

 * In particular, most fair synchronizers can define {@code tryAcquire}

 * to return {@code false} if {@link #hasQueuedPredecessors} (a method

 * specifically designed to be used by fair synchronizers) returns

 * {@code true}.  Other variations are possible.

 *

 * <p>Throughput and scalability are generally highest for the

 * default barging (also known as <em>greedy</em>,

 * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy.

 * While this is not guaranteed to be fair or starvation-free, earlier

 * queued threads are allowed to recontend before later queued

 * threads, and each recontention has an unbiased chance to succeed

 * against incoming threads.  Also, while acquires do not

 * "spin" in the usual sense, they may perform multiple

 * invocations of {@code tryAcquire} interspersed with other

 * computations before blocking.  This gives most of the benefits of

 * spins when exclusive synchronization is only briefly held, without

 * most of the liabilities when it isn't. If so desired, you can

 * augment this by preceding calls to acquire methods with

 * "fast-path" checks, possibly prechecking {@link #hasContended}

 * and/or {@link #hasQueuedThreads} to only do so if the synchronizer

 * is likely not to be contended.

 *

 * <p>This class provides an efficient and scalable basis for

 * synchronization in part by specializing its range of use to

 * synchronizers that can rely on {@code int} state, acquire, and

 * release parameters, and an internal FIFO wait queue. When this does

 * not suffice, you can build synchronizers from a lower level using

 * {@link java.util.concurrent.atomic atomic} classes, your own custom

 * {@link java.util.Queue} classes, and {@link LockSupport} blocking

 * support.

 *

 * <h2>Usage Examples</h2>

 *

 * <p>Here is a non-reentrant mutual exclusion lock class that uses

 * the value zero to represent the unlocked state, and one to

 * represent the locked state. While a non-reentrant lock

 * does not strictly require recording of the current owner

 * thread, this class does so anyway to make usage easier to monitor.

 * It also supports conditions and exposes some instrumentation methods:

 *

 * <pre> {@code

 * class Mutex implements Lock, java.io.Serializable {

 *

 *   // Our internal helper class

 *   private static class Sync extends AbstractQueuedSynchronizer {

 *     // Acquires the lock if state is zero

 *     public boolean tryAcquire(int acquires) {

 *       assert acquires == 1; // Otherwise unused

 *       if (compareAndSetState(0, 1)) {

 *         setExclusiveOwnerThread(Thread.currentThread());

 *         return true;

 *       }

 *       return false;

 *     }

 *

 *     // Releases the lock by setting state to zero

 *     protected boolean tryRelease(int releases) {

 *       assert releases == 1; // Otherwise unused

 *       if (!isHeldExclusively())

 *         throw new IllegalMonitorStateException();

 *       setExclusiveOwnerThread(null);

 *       setState(0);

 *       return true;

 *     }

 *

 *     // Reports whether in locked state

 *     public boolean isLocked() {

 *       return getState() != 0;

 *     }

 *

 *     public boolean isHeldExclusively() {

 *       // a data race, but safe due to out-of-thin-air guarantees

 *       return getExclusiveOwnerThread() == Thread.currentThread();

 *     }

 *

 *     // Provides a Condition

 *     public Condition newCondition() {

 *       return new ConditionObject();

 *     }

 *

 *     // Deserializes properly

 *     private void readObject(ObjectInputStream s)

 *         throws IOException, ClassNotFoundException {

 *       s.defaultReadObject();

 *       setState(0); // reset to unlocked state

 *     }

 *   }

 *

 *   // The sync object does all the hard work. We just forward to it.

 *   private final Sync sync = new Sync();

 *

 *   public void lock()              { sync.acquire(1); }

 *   public boolean tryLock()        { return sync.tryAcquire(1); }

 *   public void unlock()            { sync.release(1); }

 *   public Condition newCondition() { return sync.newCondition(); }

 *   public boolean isLocked()       { return sync.isLocked(); }

 *   public boolean isHeldByCurrentThread() {

 *     return sync.isHeldExclusively();

 *   }

 *   public boolean hasQueuedThreads() {

 *     return sync.hasQueuedThreads();

 *   }

 *   public void lockInterruptibly() throws InterruptedException {

 *     sync.acquireInterruptibly(1);

 *   }

 *   public boolean tryLock(long timeout, TimeUnit unit)

 *       throws InterruptedException {

 *     return sync.tryAcquireNanos(1, unit.toNanos(timeout));

 *   }

 * }}</pre>

 *

 * <p>Here is a latch class that is like a

 * {@link java.util.concurrent.CountDownLatch CountDownLatch}

 * except that it only requires a single {@code signal} to

 * fire. Because a latch is non-exclusive, it uses the {@code shared}

 * acquire and release methods.

 *

 * <pre> {@code

 * class BooleanLatch {

 *

 *   private static class Sync extends AbstractQueuedSynchronizer {

 *     boolean isSignalled() { return getState() != 0; }

 *

 *     protected int tryAcquireShared(int ignore) {

 *       return isSignalled() ? 1 : -1;

 *     }

 *

 *     protected boolean tryReleaseShared(int ignore) {

 *       setState(1);

 *       return true;

 *     }

 *   }

 *

 *   private final Sync sync = new Sync();

 *   public boolean isSignalled() { return sync.isSignalled(); }

 *   public void signal()         { sync.releaseShared(1); }

 *   public void await() throws InterruptedException {

 *     sync.acquireSharedInterruptibly(1);

 *   }

 * }}</pre>

 *

 * @since 1.5

 * @author Doug Lea

 */

public abstract class AbstractQueuedSynchronizer

    extends AbstractOwnableSynchronizer

    implements java.io.Serializable {

    private static final long serialVersionUID = 7373984972572414691L;

    /**

     * Creates a new {@code AbstractQueuedSynchronizer} instance

     * with initial synchronization state of zero.

     */

    protected AbstractQueuedSynchronizer() { }

    /*

     * Overview.

     *

     * The wait queue is a variant of a "CLH" (Craig, Landin, and

     * Hagersten) lock queue. CLH locks are normally used for

     * spinlocks.  We instead use them for blocking synchronizers by

     * including explicit ("prev" and "next") links plus a "status"

     * field that allow nodes to signal successors when releasing

     * locks, and handle cancellation due to interrupts and timeouts.

     * The status field includes bits that track whether a thread

     * needs a signal (using LockSupport.unpark). Despite these

     * additions, we maintain most CLH locality properties.

     *

     * To enqueue into a CLH lock, you atomically splice it in as new

     * tail. To dequeue, you set the head field, so the next eligible

     * waiter becomes first.

     *

     *  +------+  prev +-------+       +------+

     *  | head | <---- | first | <---- | tail |

     *  +------+       +-------+       +------+

     *

     * Insertion into a CLH queue requires only a single atomic

     * operation on "tail", so there is a simple point of demarcation

     * from unqueued to queued. The "next" link of the predecessor is

     * set by the enqueuing thread after successful CAS. Even though

     * non-atomic, this suffices to ensure that any blocked thread is

     * signalled by a predecessor when eligible (although in the case

     * of cancellation, possibly with the assistance of a signal in

     * method cleanQueue). Signalling is based in part on a

     * Dekker-like scheme in which the to-be waiting thread indicates

     * WAITING status, then retries acquiring, and then rechecks

     * status before blocking. The signaller atomically clears WAITING

     * status when unparking.

     *

     * Dequeuing on acquire involves detaching (nulling) a node's

     * "prev" node and then updating the "head". Other threads check

     * if a node is or was dequeued by checking "prev" rather than

     * head. We enforce the nulling then setting order by spin-waiting

     * if necessary. Because of this, the lock algorithm is not itself

     * strictly "lock-free" because an acquiring thread may need to

     * wait for a previous acquire to make progress. When used with

     * exclusive locks, such progress is required anyway. However

     * Shared mode may (uncommonly) require a spin-wait before

     * setting head field to ensure proper propagation. (Historical

     * note: This allows some simplifications and efficiencies

     * compared to previous versions of this class.)

     *

     * A node's predecessor can change due to cancellation while it is

     * waiting, until the node is first in queue, at which point it

     * cannot change. The acquire methods cope with this by rechecking

     * "prev" before waiting. The prev and next fields are modified

     * only via CAS by cancelled nodes in method cleanQueue. The

     * unsplice strategy is reminiscent of Michael-Scott queues in

     * that after a successful CAS to prev field, other threads help

     * fix next fields.  Because cancellation often occurs in bunches

     * that complicate decisions about necessary signals, each call to

     * cleanQueue traverses the queue until a clean sweep. Nodes that

     * become relinked as first are unconditionally unparked

     * (sometimes unnecessarily, but those cases are not worth

     * avoiding).

     *

     * A thread may try to acquire if it is first (frontmost) in the

     * queue, and sometimes before.  Being first does not guarantee

     * success; it only gives the right to contend. We balance

     * throughput, overhead, and fairness by allowing incoming threads

     * to "barge" and acquire the synchronizer while in the process of

     * enqueuing, in which case an awakened first thread may need to

     * rewait.  To counteract possible repeated unlucky rewaits, we

     * exponentially increase retries (up to 256) to acquire each time

     * a thread is unparked. Except in this case, AQS locks do not

     * spin; they instead interleave attempts to acquire with

     * bookkeeping steps. (Users who want spinlocks can use

     * tryAcquire.)

     *

     * To improve garbage collectibility, fields of nodes not yet on

     * list are null. (It is not rare to create and then throw away a

     * node without using it.) Fields of nodes coming off the list are

     * nulled out as soon as possible. This accentuates the challenge

     * of externally determining the first waiting thread (as in

     * method getFirstQueuedThread). This sometimes requires the

     * fallback of traversing backwards from the atomically updated

     * "tail" when fields appear null. (This is never needed in the

     * process of signalling though.)

     *

     * CLH queues need a dummy header node to get started. But

     * we don't create them on construction, because it would be wasted

     * effort if there is never contention. Instead, the node

     * is constructed and head and tail pointers are set upon first

     * contention.

     *

     * Shared mode operations differ from Exclusive in that an acquire

     * signals the next waiter to try to acquire if it is also

     * Shared. The tryAcquireShared API allows users to indicate the

     * degree of propagation, but in most applications, it is more

     * efficient to ignore this, allowing the successor to try

     * acquiring in any case.

     *

     * Threads waiting on Conditions use nodes with an additional

     * link to maintain the (FIFO) list of conditions. Conditions only

     * need to link nodes in simple (non-concurrent) linked queues

     * because they are only accessed when exclusively held.  Upon

     * await, a node is inserted into a condition queue.  Upon signal,

     * the node is enqueued on the main queue.  A special status field

     * value is used to track and atomically trigger this.

     *

     * Accesses to fields head, tail, and state use full Volatile

     * mode, along with CAS. Node fields status, prev and next also do

     * so while threads may be signallable, but sometimes use weaker

     * modes otherwise. Accesses to field "waiter" (the thread to be

     * signalled) are always sandwiched between other atomic accesses

     * so are used in Plain mode. We use jdk.internal Unsafe versions

     * of atomic access methods rather than VarHandles to avoid

     * potential VM bootstrap issues.

     *

     * Most of the above is performed by primary internal method

     * acquire, that is invoked in some way by all exported acquire

     * methods.  (It is usually easy for compilers to optimize

     * call-site specializations when heavily used.)

     *

     * There are several arbitrary decisions about when and how to

     * check interrupts in both acquire and await before and/or after

     * blocking. The decisions are less arbitrary in implementation

     * updates because some users appear to rely on original behaviors

     * in ways that are racy and so (rarely) wrong in general but hard

     * to justify changing.

     *

     * Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill

     * Scherer and Michael Scott, along with members of JSR-166

     * expert group, for helpful ideas, discussions, and critiques

     * on the design of this class.

     */

    // Node status bits, also used as argument and return values

    static final int WAITING   = 1;          // must be 1

    static final int CANCELLED = 0x80000000; // must be negative

    static final int COND      = 2;          // in a condition wait

    /** CLH Nodes */

    abstract static class Node {

        volatile Node prev;       // initially attached via casTail

        volatile Node next;       // visibly nonnull when signallable

        Thread waiter;            // visibly nonnull when enqueued

        volatile int status;      // written by owner, atomic bit ops by others

        // methods for atomic operations

        final boolean casPrev(Node c, Node v) {  // for cleanQueue

            return U.weakCompareAndSetReference(this, PREV, c, v);

        }

        final boolean casNext(Node c, Node v) {  // for cleanQueue

            return U.weakCompareAndSetReference(this, NEXT, c, v);

        }

        final int getAndUnsetStatus(int v) {     // for signalling

            return U.getAndBitwiseAndInt(this, STATUS, ~v);

        }

        final void setPrevRelaxed(Node p) {      // for off-queue assignment

            U.putReference(this, PREV, p);

        }

        final void setStatusRelaxed(int s) {     // for off-queue assignment

            U.putInt(this, STATUS, s);

        }

        final void clearStatus() {               // for reducing unneeded signals

            U.putIntOpaque(this, STATUS, 0);

        }

        private static final long STATUS

            = U.objectFieldOffset(Node.class, "status");

        private static final long NEXT

            = U.objectFieldOffset(Node.class, "next");

        private static final long PREV

            = U.objectFieldOffset(Node.class, "prev");

    }

    // Concrete classes tagged by type

    static final class ExclusiveNode extends Node { }

    static final class SharedNode extends Node { }

    static final class ConditionNode extends Node

        implements ForkJoinPool.ManagedBlocker {

        ConditionNode nextWaiter;            // link to next waiting node

        /**

         * Allows Conditions to be used in ForkJoinPools without

         * risking fixed pool exhaustion. This is usable only for

         * untimed Condition waits, not timed versions.

         */

        public final boolean isReleasable() {

            return status <= 1 || Thread.currentThread().isInterrupted();

        }

        public final boolean block() {

            while (!isReleasable()) LockSupport.park();

            return true;

        }

    }

    /**

     * Head of the wait queue, lazily initialized.

     */

    private transient volatile Node head;

    /**

     * Tail of the wait queue. After initialization, modified only via casTail.

     */

    private transient volatile Node tail;

    /**

     * The synchronization state.

     */

    private volatile int state;

    /**

     * Returns the current value of synchronization state.

     * This operation has memory semantics of a {@code volatile} read.

     * @return current state value

     */

    protected final int getState() {

        return state;

    }

    /**

     * Sets the value of synchronization state.

     * This operation has memory semantics of a {@code volatile} write.

     * @param newState the new state value

     */

    protected final void setState(int newState) {

        state = newState;

    }

    /**

     * Atomically sets synchronization state to the given updated

     * value if the current state value equals the expected value.

     * This operation has memory semantics of a {@code volatile} read

     * and write.

     *

     * @param expect the expected value

     * @param update the new value

     * @return {@code true} if successful. False return indicates that the actual

     *         value was not equal to the expected value.

     */

    protected final boolean compareAndSetState(int expect, int update) {

        return U.compareAndSetInt(this, STATE, expect, update);

    }

    // Queuing utilities

    private boolean casTail(Node c, Node v) {

        return U.compareAndSetReference(this, TAIL, c, v);

    }

    /** tries once to CAS a new dummy node for head */

    private void tryInitializeHead() {

        Node h = new ExclusiveNode();

        if (U.compareAndSetReference(this, HEAD, null, h))

            tail = h;

    }

    /**

     * Enqueues the node unless null. (Currently used only for

     * ConditionNodes; other cases are interleaved with acquires.)

     */

    final void enqueue(Node node) {

        if (node != null) {

            for (;;) {

                Node t = tail;

                node.setPrevRelaxed(t);        // avoid unnecessary fence

                if (t == null)                 // initialize

                    tryInitializeHead();

                else if (casTail(t, node)) {

                    t.next = node;

                    if (t.status < 0)          // wake up to clean link

                        LockSupport.unpark(node.waiter);

                    break;

                }

            }

        }

    }

    /** Returns true if node is found in traversal from tail */

    final boolean isEnqueued(Node node) {

        for (Node t = tail; t != null; t = t.prev)

            if (t == node)

                return true;

        return false;

    }

    /**

     * Wakes up the successor of given node, if one exists, and unsets its

     * WAITING status to avoid park race. This may fail to wake up an

     * eligible thread when one or more have been cancelled, but

     * cancelAcquire ensures liveness.

     */

    private static void signalNext(Node h) {

        Node s;

        if (h != null && (s = h.next) != null && s.status != 0) {

            s.getAndUnsetStatus(WAITING);

            LockSupport.unpark(s.waiter);

        }

    }

    /** Wakes up the given node if in shared mode */

    private static void signalNextIfShared(Node h) {

        Node s;

        if (h != null && (s = h.next) != null &&

            (s instanceof SharedNode) && s.status != 0) {

            s.getAndUnsetStatus(WAITING);

            LockSupport.unpark(s.waiter);

        }

    }

    /**

     * Main acquire method, invoked by all exported acquire methods.

     *

     * @param node null unless a reacquiring Condition

     * @param arg the acquire argument

     * @param shared true if shared mode else exclusive

     * @param interruptible if abort and return negative on interrupt

     * @param timed if true use timed waits

     * @param time if timed, the System.nanoTime value to timeout

     * @return positive if acquired, 0 if timed out, negative if interrupted

     */

    final int acquire(Node node, int arg, boolean shared,

                      boolean interruptible, boolean timed, long time) {

        Thread current = Thread.currentThread();

        byte spins = 0, postSpins = 0;   // retries upon unpark of first thread

        boolean interrupted = false, first = false;

        Node pred = null;                // predecessor of node when enqueued

        /*

         * Repeatedly:

         *  Check if node now first

         *    if so, ensure head stable, else ensure valid predecessor

         *  if node is first or not yet enqueued, try acquiring

         *  else if node not yet created, create it

         *  else if not yet enqueued, try once to enqueue

         *  else if woken from park, retry (up to postSpins times)

         *  else if WAITING status not set, set and retry

         *  else park and clear WAITING status, and check cancellation

         */

        for (;;) {

            if (!first && (pred = (node == null) ? null : node.prev) != null &&

                !(first = (head == pred))) {

                if (pred.status < 0) {

                    cleanQueue();           // predecessor cancelled

                    continue;

                } else if (pred.prev == null) {

                    Thread.onSpinWait();    // ensure serialization

                    continue;

                }

            }

            if (first || pred == null) {

                boolean acquired;

                try {

                    if (shared)

                        acquired = (tryAcquireShared(arg) >= 0);

                    else

                        acquired = tryAcquire(arg);

                } catch (Throwable ex) {

                    cancelAcquire(node, interrupted, false);

                    throw ex;

                }

                if (acquired) {

                    if (first) {

                        node.prev = null;

                        head = node;

                        pred.next = null;

                        node.waiter = null;

                        if (shared)

                            signalNextIfShared(node);

                        if (interrupted)

                            current.interrupt();

                    }

                    return 1;

                }

            }

            if (node == null) {                 // allocate; retry before enqueue

                if (shared)

                    node = new SharedNode();

                else

                    node = new ExclusiveNode();

            } else if (pred == null) {          // try to enqueue

                node.waiter = current;

                Node t = tail;

                node.setPrevRelaxed(t);         // avoid unnecessary fence

                if (t == null)

                    tryInitializeHead();

                else if (!casTail(t, node))

                    node.setPrevRelaxed(null);  // back out

                else

                    t.next = node;

            } else if (first && spins != 0) {

                --spins;                        // reduce unfairness on rewaits

                Thread.onSpinWait();

            } else if (node.status == 0) {

                node.status = WAITING;          // enable signal and recheck

            } else {

                long nanos;

                spins = postSpins = (byte)((postSpins << 1) | 1);

                if (!timed)

                    LockSupport.park(this);

                else if ((nanos = time - System.nanoTime()) > 0L)

                    LockSupport.parkNanos(this, nanos);

                else

                    break;

                node.clearStatus();

                if ((interrupted |= Thread.interrupted()) && interruptible)

                    break;

            }

        }

        return cancelAcquire(node, interrupted, interruptible);

    }

    /**

     * Possibly repeatedly traverses from tail, unsplicing cancelled

     * nodes until none are found. Unparks nodes that may have been

     * relinked to be next eligible acquirer.

     */

    private void cleanQueue() {

        for (;;) {                               // restart point

            for (Node q = tail, s = null, p, n;;) { // (p, q, s) triples

                if (q == null || (p = q.prev) == null)

                    return;                      // end of list

                if (s == null ? tail != q : (s.prev != q || s.status < 0))

                    break;                       // inconsistent

                if (q.status < 0) {              // cancelled

                    if ((s == null ? casTail(q, p) : s.casPrev(q, p)) &&

                        q.prev == p) {

                        p.casNext(q, s);         // OK if fails

                        if (p.prev == null)

                            signalNext(p);

                    }

                    break;

                }

                if ((n = p.next) != q) {         // help finish

                    if (n != null && q.prev == p) {

                        p.casNext(n, q);

                        if (p.prev == null)

                            signalNext(p);

                    }

                    break;

                }

                s = q;

                q = q.prev;

            }

        }

    }

    /**

     * Cancels an ongoing attempt to acquire.

     *

     * @param node the node (may be null if cancelled before enqueuing)

     * @param interrupted true if thread interrupted

     * @param interruptible if should report interruption vs reset

     */

    private int cancelAcquire(Node node, boolean interrupted,

                              boolean interruptible) {

        if (node != null) {

            node.waiter = null;

            node.status = CANCELLED;

            if (node.prev != null)

                cleanQueue();

        }

        if (interrupted) {

            if (interruptible)

                return CANCELLED;

            else

                Thread.currentThread().interrupt();

        }

        return 0;

    }

    // Main exported methods

    /**

     * Attempts to acquire in exclusive mode. This method should query

     * if the state of the object permits it to be acquired in the

     * exclusive mode, and if so to acquire it.

     *

     * <p>This method is always invoked by the thread performing

     * acquire.  If this method reports failure, the acquire method

     * may queue the thread, if it is not already queued, until it is

     * signalled by a release from some other thread. This can be used

     * to implement method {@link Lock#tryLock()}.

     *

     * <p>The default

     * implementation throws {@link UnsupportedOperationException}.

     *

     * @param arg the acquire argument. This value is always the one

     *        passed to an acquire method, or is the value saved on entry

     *        to a condition wait.  The value is otherwise uninterpreted

     *        and can represent anything you like.

     * @return {@code true} if successful. Upon success, this object has

     *         been acquired.

     * @throws IllegalMonitorStateException if acquiring would place this

     *         synchronizer in an illegal state. This exception must be

     *         thrown in a consistent fashion for synchronization to work

     *         correctly.

     * @throws UnsupportedOperationException if exclusive mode is not supported

     */

    protected boolean tryAcquire(int arg) {

        throw new UnsupportedOperationException();

    }

    /**

     * Attempts to set the state to reflect a release in exclusive

     * mode.

     *

     * <p>This method is always invoked by the thread performing release.

     *

     * <p>The default implementation throws

     * {@link UnsupportedOperationException}.

     *

     * @param arg the release argument. This value is always the one

     *        passed to a release method, or the current state value upon

     *        entry to a condition wait.  The value is otherwise

     *        uninterpreted and can represent anything you like.

     * @return {@code true} if this object is now in a fully released

     *         state, so that any waiting threads may attempt to acquire;

     *         and {@code false} otherwise.

     * @throws IllegalMonitorStateException if releasing would place this

     *         synchronizer in an illegal state. This exception must be

     *         thrown in a consistent fashion for synchronization to work

     *         correctly.

     * @throws UnsupportedOperationException if exclusive mode is not supported

     */

    protected boolean tryRelease(int arg) {

        throw new UnsupportedOperationException();

    }

    /**

     * Attempts to acquire in shared mode. This method should query if

     * the state of the object permits it to be acquired in the shared

     * mode, and if so to acquire it.

     *

     * <p>This method is always invoked by the thread performing

     * acquire.  If this method reports failure, the acquire method

     * may queue the thread, if it is not already queued, until it is

     * signalled by a release from some other thread.

     *

     * <p>The default implementation throws {@link

     * UnsupportedOperationException}.

     *

     * @param arg the acquire argument. This value is always the one

     *        passed to an acquire method, or is the value saved on entry

     *        to a condition wait.  The value is otherwise uninterpreted

     *        and can represent anything you like.

     * @return a negative value on failure; zero if acquisition in shared

     *         mode succeeded but no subsequent shared-mode acquire can

     *         succeed; and a positive value if acquisition in shared

     *         mode succeeded and subsequent shared-mode acquires might

     *         also succeed, in which case a subsequent waiting thread

     *         must check availability. (Support for three different

     *         return values enables this method to be used in contexts

     *         where acquires only sometimes act exclusively.)  Upon

     *         success, this object has been acquired.

     * @throws IllegalMonitorStateException if acquiring would place this

     *         synchronizer in an illegal state. This exception must be

     *         thrown in a consistent fashion for synchronization to work

     *         correctly.

     * @throws UnsupportedOperationException if shared mode is not supported

     */

    protected int tryAcquireShared(int arg) {

        throw new UnsupportedOperationException();

    }

    /**

     * Attempts to set the state to reflect a release in shared mode.

     *

     * <p>This method is always invoked by the thread performing release.

     *

     * <p>The default implementation throws

     * {@link UnsupportedOperationException}.

     *

     * @param arg the release argument. This value is always the one

     *        passed to a release method, or the current state value upon

     *        entry to a condition wait.  The value is otherwise

     *        uninterpreted and can represent anything you like.

     * @return {@code true} if this release of shared mode may permit a

     *         waiting acquire (shared or exclusive) to succeed; and

     *         {@code false} otherwise

     * @throws IllegalMonitorStateException if releasing would place this

     *         synchronizer in an illegal state. This exception must be

     *         thrown in a consistent fashion for synchronization to work

     *         correctly.

     * @throws UnsupportedOperationException if shared mode is not supported

     */

    protected boolean tryReleaseShared(int arg) {

        throw new UnsupportedOperationException();

    }

    /**

     * Returns {@code true} if synchronization is held exclusively with

     * respect to the current (calling) thread.  This method is invoked

     * upon each call to a {@link ConditionObject} method.

     *

     * <p>The default implementation throws {@link

     * UnsupportedOperationException}. This method is invoked

     * internally only within {@link ConditionObject} methods, so need

     * not be defined if conditions are not used.

     *

     * @return {@code true} if synchronization is held exclusively;

     *         {@code false} otherwise

     * @throws UnsupportedOperationException if conditions are not supported

     */

    protected boolean isHeldExclusively() {

        throw new UnsupportedOperationException();

    }

    /**

     * Acquires in exclusive mode, ignoring interrupts.  Implemented

     * by invoking at least once {@link #tryAcquire},

     * returning on success.  Otherwise the thread is queued, possibly

     * repeatedly blocking and unblocking, invoking {@link

     * #tryAcquire} until success.  This method can be used

     * to implement method {@link Lock#lock}.

     *

     * @param arg the acquire argument.  This value is conveyed to

     *        {@link #tryAcquire} but is otherwise uninterpreted and

     *        can represent anything you like.

     */

    public final void acquire(int arg) {

        if (!tryAcquire(arg))

            acquire(null, arg, false, false, false, 0L);

    }

    /**

     * Acquires in exclusive mode, aborting if interrupted.

     * Implemented by first checking interrupt status, then invoking

     * at least once {@link #tryAcquire}, returning on

     * success.  Otherwise the thread is queued, possibly repeatedly

     * blocking and unblocking, invoking {@link #tryAcquire}

     * until success or the thread is interrupted.  This method can be

     * used to implement method {@link Lock#lockInterruptibly}.

     *

     * @param arg the acquire argument.  This value is conveyed to

     *        {@link #tryAcquire} but is otherwise uninterpreted and

     *        can represent anything you like.

     * @throws InterruptedException if the current thread is interrupted

     */

    public final void acquireInterruptibly(int arg)

        throws InterruptedException {

        if (Thread.interrupted() ||

            (!tryAcquire(arg) && acquire(null, arg, false, true, false, 0L) < 0))

            throw new InterruptedException();

    }

    /**

     * Attempts to acquire in exclusive mode, aborting if interrupted,

     * and failing if the given timeout elapses.  Implemented by first

     * checking interrupt status, then invoking at least once {@link

     * #tryAcquire}, returning on success.  Otherwise, the thread is

     * queued, possibly repeatedly blocking and unblocking, invoking

     * {@link #tryAcquire} until success or the thread is interrupted

     * or the timeout elapses.  This method can be used to implement

     * method {@link Lock#tryLock(long, TimeUnit)}.

     *

     * @param arg the acquire argument.  This value is conveyed to

     *        {@link #tryAcquire} but is otherwise uninterpreted and

     *        can represent anything you like.

     * @param nanosTimeout the maximum number of nanoseconds to wait

     * @return {@code true} if acquired; {@code false} if timed out

     * @throws InterruptedException if the current thread is interrupted

     */

    public final boolean tryAcquireNanos(int arg, long nanosTimeout)

        throws InterruptedException {

        if (!Thread.interrupted()) {

            if (tryAcquire(arg))

                return true;

            if (nanosTimeout <= 0L)

                return false;

            int stat = acquire(null, arg, false, true, true,

                               System.nanoTime() + nanosTimeout);

            if (stat > 0)

                return true;

            if (stat == 0)

                return false;

        }

        throw new InterruptedException();

    }

    /**

     * Releases in exclusive mode.  Implemented by unblocking one or

     * more threads if {@link #tryRelease} returns true.

     * This method can be used to implement method {@link Lock#unlock}.

     *

     * @param arg the release argument.  This value is conveyed to

     *        {@link #tryRelease} but is otherwise uninterpreted and

     *        can represent anything you like.

     * @return the value returned from {@link #tryRelease}

     */

    public final boolean release(int arg) {

        if (tryRelease(arg)) {

            signalNext(head);

            return true;

        }

        return false;

    }

    /**

     * Acquires in shared mode, ignoring interrupts.  Implemented by

     * first invoking at least once {@link #tryAcquireShared},

     * returning on success.  Otherwise the thread is queued, possibly

     * repeatedly blocking and unblocking, invoking {@link

     * #tryAcquireShared} until success.

     *

     * @param arg the acquire argument.  This value is conveyed to

     *        {@link #tryAcquireShared} but is otherwise uninterpreted

     *        and can represent anything you like.

     */

    public final void acquireShared(int arg) {

        if (tryAcquireShared(arg) < 0)

            acquire(null, arg, true, false, false, 0L);

    }

    /**

     * Acquires in shared mode, aborting if interrupted.  Implemented

     * by first checking interrupt status, then invoking at least once

     * {@link #tryAcquireShared}, returning on success.  Otherwise the

     * thread is queued, possibly repeatedly blocking and unblocking,

     * invoking {@link #tryAcquireShared} until success or the thread

     * is interrupted.

     * @param arg the acquire argument.

     * This value is conveyed to {@link #tryAcquireShared} but is

     * otherwise uninterpreted and can represent anything

     * you like.

     * @throws InterruptedException if the current thread is interrupted

     */

    public final void acquireSharedInterruptibly(int arg)

        throws InterruptedException {

        if (Thread.interrupted() ||

            (tryAcquireShared(arg) < 0 &&

             acquire(null, arg, true, true, false, 0L) < 0))

            throw new InterruptedException();

    }

    /**

     * Attempts to acquire in shared mode, aborting if interrupted, and

     * failing if the given timeout elapses.  Implemented by first

     * checking interrupt status, then invoking at least once {@link

     * #tryAcquireShared}, returning on success.  Otherwise, the

     * thread is queued, possibly repeatedly blocking and unblocking,

     * invoking {@link #tryAcquireShared} until success or the thread

     * is interrupted or the timeout elapses.

     *

     * @param arg the acquire argument.  This value is conveyed to

     *        {@link #tryAcquireShared} but is otherwise uninterpreted

     *        and can represent anything you like.

     * @param nanosTimeout the maximum number of nanoseconds to wait

     * @return {@code true} if acquired; {@code false} if timed out

     * @throws InterruptedException if the current thread is interrupted

     */

    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)

            throws InterruptedException {

        if (!Thread.interrupted()) {

            if (tryAcquireShared(arg) >= 0)

                return true;

            if (nanosTimeout <= 0L)

                return false;

            int stat = acquire(null, arg, true, true, true,

                               System.nanoTime() + nanosTimeout);

            if (stat > 0)

                return true;

            if (stat == 0)

                return false;

        }

        throw new InterruptedException();

    }

    /**

     * Releases in shared mode.  Implemented by unblocking one or more

     * threads if {@link #tryReleaseShared} returns true.

     *

     * @param arg the release argument.  This value is conveyed to

     *        {@link #tryReleaseShared} but is otherwise uninterpreted

     *        and can represent anything you like.

     * @return the value returned from {@link #tryReleaseShared}

     */

    public final boolean releaseShared(int arg) {

        if (tryReleaseShared(arg)) {

            signalNext(head);

            return true;

        }

        return false;

    }

    // Queue inspection methods

    /**

     * Queries whether any threads are waiting to acquire. Note that

     * because cancellations due to interrupts and timeouts may occur

     * at any time, a {@code true} return does not guarantee that any

     * other thread will ever acquire.

     *

     * @return {@code true} if there may be other threads waiting to acquire

     */

    public final boolean hasQueuedThreads() {

        for (Node p = tail, h = head; p != h && p != null; p = p.prev)

            if (p.status >= 0)

                return true;

        return false;

    }

    /**

     * Queries whether any threads have ever contended to acquire this

     * synchronizer; that is, if an acquire method has ever blocked.

     *

     * <p>In this implementation, this operation returns in

     * constant time.

     *

     * @return {@code true} if there has ever been contention

     */

    public final boolean hasContended() {

        return head != null;

    }

    /**

     * Returns the first (longest-waiting) thread in the queue, or

     * {@code null} if no threads are currently queued.

     *

     * <p>In this implementation, this operation normally returns in

     * constant time, but may iterate upon contention if other threads are

     * concurrently modifying the queue.

     *

     * @return the first (longest-waiting) thread in the queue, or

     *         {@code null} if no threads are currently queued

     */

    public final Thread getFirstQueuedThread() {

        Thread first = null, w; Node h, s;

        if ((h = head) != null && ((s = h.next) == null ||

                                   (first = s.waiter) == null ||

                                   s.prev == null)) {

            // traverse from tail on stale reads

            for (Node p = tail, q; p != null && (q = p.prev) != null; p = q)

                if ((w = p.waiter) != null)

                    first = w;

        }

        return first;

    }

    /**

     * Returns true if the given thread is currently queued.

     *

     * <p>This implementation traverses the queue to determine

     * presence of the given thread.

     *

     * @param thread the thread

     * @return {@code true} if the given thread is on the queue

     * @throws NullPointerException if the thread is null

     */

    public final boolean isQueued(Thread thread) {

        if (thread == null)

            throw new NullPointerException();

        for (Node p = tail; p != null; p = p.prev)

            if (p.waiter == thread)

                return true;

        return false;

    }

    /**

     * Returns {@code true} if the apparent first queued thread, if one

     * exists, is waiting in exclusive mode.  If this method returns

     * {@code true}, and the current thread is attempting to acquire in

     * shared mode (that is, this method is invoked from {@link

     * #tryAcquireShared}) then it is guaranteed that the current thread

     * is not the first queued thread.  Used only as a heuristic in

     * ReentrantReadWriteLock.

     */

    final boolean apparentlyFirstQueuedIsExclusive() {

        Node h, s;

        return (h = head) != null && (s = h.next)  != null &&

            !(s instanceof SharedNode) && s.waiter != null;

    }

    /**

     * Queries whether any threads have been waiting to acquire longer

     * than the current thread.

     *

     * <p>An invocation of this method is equivalent to (but may be

     * more efficient than):

     * <pre> {@code

     * getFirstQueuedThread() != Thread.currentThread()

     *   && hasQueuedThreads()}</pre>

     *

     * <p>Note that because cancellations due to interrupts and

     * timeouts may occur at any time, a {@code true} return does not

     * guarantee that some other thread will acquire before the current

     * thread.  Likewise, it is possible for another thread to win a

     * race to enqueue after this method has returned {@code false},

     * due to the queue being empty.

     *

     * <p>This method is designed to be used by a fair synchronizer to

     * avoid <a href="AbstractQueuedSynchronizer.html#barging">barging</a>.

     * Such a synchronizer's {@link #tryAcquire} method should return

     * {@code false}, and its {@link #tryAcquireShared} method should

     * return a negative value, if this method returns {@code true}

     * (unless this is a reentrant acquire).  For example, the {@code

     * tryAcquire} method for a fair, reentrant, exclusive mode

     * synchronizer might look like this:

     *

     * <pre> {@code

     * protected boolean tryAcquire(int arg) {

     *   if (isHeldExclusively()) {

     *     // A reentrant acquire; increment hold count

     *     return true;

     *   } else if (hasQueuedPredecessors()) {

     *     return false;

     *   } else {

     *     // try to acquire normally

     *   }

     * }}</pre>

     *

     * @return {@code true} if there is a queued thread preceding the

     *         current thread, and {@code false} if the current thread

     *         is at the head of the queue or the queue is empty

     * @since 1.7

     */

    public final boolean hasQueuedPredecessors() {

        Thread first = null; Node h, s;

        if ((h = head) != null && ((s = h.next) == null ||

                                   (first = s.waiter) == null ||

                                   s.prev == null))

            first = getFirstQueuedThread(); // retry via getFirstQueuedThread

        return first != null && first != Thread.currentThread();

    }

    // Instrumentation and monitoring methods

    /**

     * Returns an estimate of the number of threads waiting to

     * acquire.  The value is only an estimate because the number of

     * threads may change dynamically while this method traverses

     * internal data structures.  This method is designed for use in

     * monitoring system state, not for synchronization control.

     *

     * @return the estimated number of threads waiting to acquire

     */

    public final int getQueueLength() {

        int n = 0;

        for (Node p = tail; p != null; p = p.prev) {

            if (p.waiter != null)

                ++n;

        }

        return n;

    }

    /**

     * Returns a collection containing threads that may be waiting to

     * acquire.  Because the actual set of threads may change

     * dynamically while constructing this result, the returned

     * collection is only a best-effort estimate.  The elements of the

     * returned collection are in no particular order.  This method is

     * designed to facilitate construction of subclasses that provide

     * more extensive monitoring facilities.

     *

     * @return the collection of threads

     */

    public final Collection<Thread> getQueuedThreads() {

        ArrayList<Thread> list = new ArrayList<>();

        for (Node p = tail; p != null; p = p.prev) {