/*

 * 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.lang.invoke.MethodHandles;

import java.lang.invoke.VarHandle;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Date;

import java.util.concurrent.TimeUnit;

import java.util.concurrent.locks.AbstractQueuedSynchronizer.Node;

/**

 * A version of {@link AbstractQueuedSynchronizer} in

 * which synchronization state is maintained as a {@code long}.

 * This class has exactly the same structure, properties, and methods

 * as {@code AbstractQueuedSynchronizer} with the exception

 * that all state-related parameters and results are defined

 * as {@code long} rather than {@code int}. This class

 * may be useful when creating synchronizers such as

 * multilevel locks and barriers that require

 * 64 bits of state.

 *

 * <p>See {@link AbstractQueuedSynchronizer} for usage

 * notes and examples.

 *

 * @since 1.6

 * @author Doug Lea

 */

public abstract class AbstractQueuedLongSynchronizer

    extends AbstractOwnableSynchronizer

    implements java.io.Serializable {

    private static final long serialVersionUID = 7373984972572414692L;

    /*

     * To keep sources in sync, the remainder of this source file is

     * exactly cloned from AbstractQueuedSynchronizer, replacing class

     * name and changing ints related with sync state to longs. Please

     * keep it that way.

     */

    /**

     * Creates a new {@code AbstractQueuedLongSynchronizer} instance

     * with initial synchronization state of zero.

     */

    protected AbstractQueuedLongSynchronizer() { }

    /**

     * Head of the wait queue, lazily initialized.  Except for

     * initialization, it is modified only via method setHead.  Note:

     * If head exists, its waitStatus is guaranteed not to be

     * CANCELLED.

     */

    private transient volatile Node head;

    /**

     * Tail of the wait queue, lazily initialized.  Modified only via

     * method enq to add new wait node.

     */

    private transient volatile Node tail;

    /**

     * The synchronization state.

     */

    private volatile long state;

    /**

     * Returns the current value of synchronization state.

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

     * @return current state value

     */

    protected final long 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(long newState) {

        // See JDK-8180620: Clarify VarHandle mixed-access subtleties

        STATE.setVolatile(this, 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(long expect, long update) {

        return STATE.compareAndSet(this, expect, update);

    }

    // Queuing utilities

    /**

     * The number of nanoseconds for which it is faster to spin

     * rather than to use timed park. A rough estimate suffices

     * to improve responsiveness with very short timeouts.

     */

    static final long SPIN_FOR_TIMEOUT_THRESHOLD = 1000L;

    /**

     * Inserts node into queue, initializing if necessary. See picture above.

     * @param node the node to insert

     * @return node's predecessor

     */

    private Node enq(Node node) {

        for (;;) {

            Node oldTail = tail;

            if (oldTail != null) {

                node.setPrevRelaxed(oldTail);

                if (compareAndSetTail(oldTail, node)) {

                    oldTail.next = node;

                    return oldTail;

                }

            } else {

                initializeSyncQueue();

            }

        }

    }

    /**

     * Creates and enqueues node for current thread and given mode.

     *

     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared

     * @return the new node

     */

    private Node addWaiter(Node mode) {

        Node node = new Node(mode);

        for (;;) {

            Node oldTail = tail;

            if (oldTail != null) {

                node.setPrevRelaxed(oldTail);

                if (compareAndSetTail(oldTail, node)) {

                    oldTail.next = node;

                    return node;

                }

            } else {

                initializeSyncQueue();

            }

        }

    }

    /**

     * Sets head of queue to be node, thus dequeuing. Called only by

     * acquire methods.  Also nulls out unused fields for sake of GC

     * and to suppress unnecessary signals and traversals.

     *

     * @param node the node

     */

    private void setHead(Node node) {

        head = node;

        node.thread = null;

        node.prev = null;

    }

    /**

     * Wakes up node's successor, if one exists.

     *

     * @param node the node

     */

    private void unparkSuccessor(Node node) {

        /*

         * If status is negative (i.e., possibly needing signal) try

         * to clear in anticipation of signalling.  It is OK if this

         * fails or if status is changed by waiting thread.

         */

        int ws = node.waitStatus;

        if (ws < 0)

            node.compareAndSetWaitStatus(ws, 0);

        /*

         * Thread to unpark is held in successor, which is normally

         * just the next node.  But if cancelled or apparently null,

         * traverse backwards from tail to find the actual

         * non-cancelled successor.

         */

        Node s = node.next;

        if (s == null || s.waitStatus > 0) {

            s = null;

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

                if (p.waitStatus <= 0)

                    s = p;

        }

        if (s != null)

            LockSupport.unpark(s.thread);

    }

    /**

     * Release action for shared mode -- signals successor and ensures

     * propagation. (Note: For exclusive mode, release just amounts

     * to calling unparkSuccessor of head if it needs signal.)

     */

    private void doReleaseShared() {

        /*

         * Ensure that a release propagates, even if there are other

         * in-progress acquires/releases.  This proceeds in the usual

         * way of trying to unparkSuccessor of head if it needs

         * signal. But if it does not, status is set to PROPAGATE to

         * ensure that upon release, propagation continues.

         * Additionally, we must loop in case a new node is added

         * while we are doing this. Also, unlike other uses of

         * unparkSuccessor, we need to know if CAS to reset status

         * fails, if so rechecking.

         */

        for (;;) {

            Node h = head;

            if (h != null && h != tail) {

                int ws = h.waitStatus;

                if (ws == Node.SIGNAL) {

                    if (!h.compareAndSetWaitStatus(Node.SIGNAL, 0))

                        continue;            // loop to recheck cases

                    unparkSuccessor(h);

                }

                else if (ws == 0 &&

                         !h.compareAndSetWaitStatus(0, Node.PROPAGATE))

                    continue;                // loop on failed CAS

            }

            if (h == head)                   // loop if head changed

                break;

        }

    }

    /**

     * Sets head of queue, and checks if successor may be waiting

     * in shared mode, if so propagating if either propagate > 0 or

     * PROPAGATE status was set.

     *

     * @param node the node

     * @param propagate the return value from a tryAcquireShared

     */

    private void setHeadAndPropagate(Node node, long propagate) {

        Node h = head; // Record old head for check below

        setHead(node);

        /*

         * Try to signal next queued node if:

         *   Propagation was indicated by caller,

         *     or was recorded (as h.waitStatus either before

         *     or after setHead) by a previous operation

         *     (note: this uses sign-check of waitStatus because

         *      PROPAGATE status may transition to SIGNAL.)

         * and

         *   The next node is waiting in shared mode,

         *     or we don't know, because it appears null

         *

         * The conservatism in both of these checks may cause

         * unnecessary wake-ups, but only when there are multiple

         * racing acquires/releases, so most need signals now or soon

         * anyway.

         */

        if (propagate > 0 || h == null || h.waitStatus < 0 ||

            (h = head) == null || h.waitStatus < 0) {

            Node s = node.next;

            if (s == null || s.isShared())

                doReleaseShared();

        }

    }

    // Utilities for various versions of acquire

    /**

     * Cancels an ongoing attempt to acquire.

     *

     * @param node the node

     */

    private void cancelAcquire(Node node) {

        // Ignore if node doesn't exist

        if (node == null)

            return;

        node.thread = null;

        // Skip cancelled predecessors

        Node pred = node.prev;

        while (pred.waitStatus > 0)

            node.prev = pred = pred.prev;

        // predNext is the apparent node to unsplice. CASes below will

        // fail if not, in which case, we lost race vs another cancel

        // or signal, so no further action is necessary, although with

        // a possibility that a cancelled node may transiently remain

        // reachable.

        Node predNext = pred.next;

        // Can use unconditional write instead of CAS here.

        // After this atomic step, other Nodes can skip past us.

        // Before, we are free of interference from other threads.

        node.waitStatus = Node.CANCELLED;

        // If we are the tail, remove ourselves.

        if (node == tail && compareAndSetTail(node, pred)) {

            pred.compareAndSetNext(predNext, null);

        } else {

            // If successor needs signal, try to set pred's next-link

            // so it will get one. Otherwise wake it up to propagate.

            int ws;

            if (pred != head &&

                ((ws = pred.waitStatus) == Node.SIGNAL ||

                 (ws <= 0 && pred.compareAndSetWaitStatus(ws, Node.SIGNAL))) &&

                pred.thread != null) {

                Node next = node.next;

                if (next != null && next.waitStatus <= 0)

                    pred.compareAndSetNext(predNext, next);

            } else {

                unparkSuccessor(node);

            }

            node.next = node; // help GC

        }

    }

    /**

     * Checks and updates status for a node that failed to acquire.

     * Returns true if thread should block. This is the main signal

     * control in all acquire loops.  Requires that pred == node.prev.

     *

     * @param pred node's predecessor holding status

     * @param node the node

     * @return {@code true} if thread should block

     */

    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {

        int ws = pred.waitStatus;

        if (ws == Node.SIGNAL)

            /*

             * This node has already set status asking a release

             * to signal it, so it can safely park.

             */

            return true;

        if (ws > 0) {

            /*

             * Predecessor was cancelled. Skip over predecessors and

             * indicate retry.

             */

            do {

                node.prev = pred = pred.prev;

            } while (pred.waitStatus > 0);

            pred.next = node;

        } else {

            /*

             * waitStatus must be 0 or PROPAGATE.  Indicate that we

             * need a signal, but don't park yet.  Caller will need to

             * retry to make sure it cannot acquire before parking.

             */

            pred.compareAndSetWaitStatus(ws, Node.SIGNAL);

        }

        return false;

    }

    /**

     * Convenience method to interrupt current thread.

     */

    static void selfInterrupt() {

        Thread.currentThread().interrupt();

    }

    /**

     * Convenience method to park and then check if interrupted.

     *

     * @return {@code true} if interrupted

     */

    private final boolean parkAndCheckInterrupt() {

        LockSupport.park(this);

        return Thread.interrupted();

    }

    /*

     * Various flavors of acquire, varying in exclusive/shared and

     * control modes.  Each is mostly the same, but annoyingly

     * different.  Only a little bit of factoring is possible due to

     * interactions of exception mechanics (including ensuring that we

     * cancel if tryAcquire throws exception) and other control, at

     * least not without hurting performance too much.

     */

    /**

     * Acquires in exclusive uninterruptible mode for thread already in

     * queue. Used by condition wait methods as well as acquire.

     *

     * @param node the node

     * @param arg the acquire argument

     * @return {@code true} if interrupted while waiting

     */

    final boolean acquireQueued(final Node node, long arg) {

        boolean interrupted = false;

        try {

            for (;;) {

                final Node p = node.predecessor();

                if (p == head && tryAcquire(arg)) {

                    setHead(node);

                    p.next = null; // help GC

                    return interrupted;

                }

                if (shouldParkAfterFailedAcquire(p, node))

                    interrupted |= parkAndCheckInterrupt();

            }

        } catch (Throwable t) {

            cancelAcquire(node);

            if (interrupted)

                selfInterrupt();

            throw t;

        }

    }

    /**

     * Acquires in exclusive interruptible mode.

     * @param arg the acquire argument

     */

    private void doAcquireInterruptibly(long arg)

        throws InterruptedException {

        final Node node = addWaiter(Node.EXCLUSIVE);

        try {

            for (;;) {

                final Node p = node.predecessor();

                if (p == head && tryAcquire(arg)) {

                    setHead(node);

                    p.next = null; // help GC

                    return;

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    throw new InterruptedException();

            }

        } catch (Throwable t) {

            cancelAcquire(node);

            throw t;

        }

    }

    /**

     * Acquires in exclusive timed mode.

     *

     * @param arg the acquire argument

     * @param nanosTimeout max wait time

     * @return {@code true} if acquired

     */

    private boolean doAcquireNanos(long arg, long nanosTimeout)

            throws InterruptedException {

        if (nanosTimeout <= 0L)

            return false;

        final long deadline = System.nanoTime() + nanosTimeout;

        final Node node = addWaiter(Node.EXCLUSIVE);

        try {

            for (;;) {

                final Node p = node.predecessor();

                if (p == head && tryAcquire(arg)) {

                    setHead(node);

                    p.next = null; // help GC

                    return true;

                }

                nanosTimeout = deadline - System.nanoTime();

                if (nanosTimeout <= 0L) {

                    cancelAcquire(node);

                    return false;

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)

                    LockSupport.parkNanos(this, nanosTimeout);

                if (Thread.interrupted())

                    throw new InterruptedException();

            }

        } catch (Throwable t) {

            cancelAcquire(node);

            throw t;

        }

    }

    /**

     * Acquires in shared uninterruptible mode.

     * @param arg the acquire argument

     */

    private void doAcquireShared(long arg) {

        final Node node = addWaiter(Node.SHARED);

        boolean interrupted = false;

        try {

            for (;;) {

                final Node p = node.predecessor();

                if (p == head) {

                    long r = tryAcquireShared(arg);

                    if (r >= 0) {

                        setHeadAndPropagate(node, r);

                        p.next = null; // help GC

                        return;

                    }

                }

                if (shouldParkAfterFailedAcquire(p, node))

                    interrupted |= parkAndCheckInterrupt();

            }

        } catch (Throwable t) {

            cancelAcquire(node);

            throw t;

        } finally {

            if (interrupted)

                selfInterrupt();

        }

    }

    /**

     * Acquires in shared interruptible mode.

     * @param arg the acquire argument

     */

    private void doAcquireSharedInterruptibly(long arg)

        throws InterruptedException {

        final Node node = addWaiter(Node.SHARED);

        try {

            for (;;) {

                final Node p = node.predecessor();

                if (p == head) {

                    long r = tryAcquireShared(arg);

                    if (r >= 0) {

                        setHeadAndPropagate(node, r);

                        p.next = null; // help GC

                        return;

                    }

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    throw new InterruptedException();

            }

        } catch (Throwable t) {

            cancelAcquire(node);

            throw t;

        }

    }

    /**

     * Acquires in shared timed mode.

     *

     * @param arg the acquire argument

     * @param nanosTimeout max wait time

     * @return {@code true} if acquired

     */

    private boolean doAcquireSharedNanos(long arg, long nanosTimeout)

            throws InterruptedException {

        if (nanosTimeout <= 0L)

            return false;

        final long deadline = System.nanoTime() + nanosTimeout;

        final Node node = addWaiter(Node.SHARED);

        try {

            for (;;) {

                final Node p = node.predecessor();

                if (p == head) {

                    long r = tryAcquireShared(arg);

                    if (r >= 0) {

                        setHeadAndPropagate(node, r);

                        p.next = null; // help GC

                        return true;

                    }

                }

                nanosTimeout = deadline - System.nanoTime();

                if (nanosTimeout <= 0L) {

                    cancelAcquire(node);

                    return false;

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)

                    LockSupport.parkNanos(this, nanosTimeout);

                if (Thread.interrupted())

                    throw new InterruptedException();

            }

        } catch (Throwable t) {

            cancelAcquire(node);

            throw t;

        }

    }

    // 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(long 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(long 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 long tryAcquireShared(long 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(long 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(long arg) {

        if (!tryAcquire(arg) &&

            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))

            selfInterrupt();

    }

    /**

     * 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(long arg)

            throws InterruptedException {

        if (Thread.interrupted())

            throw new InterruptedException();

        if (!tryAcquire(arg))

            doAcquireInterruptibly(arg);

    }

    /**

     * 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(long arg, long nanosTimeout)

            throws InterruptedException {

        if (Thread.interrupted())

            throw new InterruptedException();

        return tryAcquire(arg) ||

            doAcquireNanos(arg, nanosTimeout);

    }

    /**

     * 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(long arg) {

        if (tryRelease(arg)) {

            Node h = head;

            if (h != null && h.waitStatus != 0)

                unparkSuccessor(h);

            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(long arg) {

        if (tryAcquireShared(arg) < 0)

            doAcquireShared(arg);

    }

    /**

     * 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(long arg)

            throws InterruptedException {

        if (Thread.interrupted())

            throw new InterruptedException();

        if (tryAcquireShared(arg) < 0)

            doAcquireSharedInterruptibly(arg);

    }

    /**

     * 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(long arg, long nanosTimeout)

            throws InterruptedException {

        if (Thread.interrupted())

            throw new InterruptedException();

        return tryAcquireShared(arg) >= 0 ||

            doAcquireSharedNanos(arg, nanosTimeout);

    }

    /**

     * 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(long arg) {

        if (tryReleaseShared(arg)) {

            doReleaseShared();

            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.waitStatus <= 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() {

        // handle only fast path, else relay

        return (head == tail) ? null : fullGetFirstQueuedThread();

    }

    /**

     * Version of getFirstQueuedThread called when fastpath fails.

     */

    private Thread fullGetFirstQueuedThread() {

        /*

         * The first node is normally head.next. Try to get its

         * thread field, ensuring consistent reads: If thread

         * field is nulled out or s.prev is no longer head, then

         * some other thread(s) concurrently performed setHead in

         * between some of our reads. We try this twice before

         * resorting to traversal.

         */

        Node h, s;

        Thread st;

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

             s.prev == head && (st = s.thread) != null) ||

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

             s.prev == head && (st = s.thread) != null))

            return st;

        /*

         * Head's next field might not have been set yet, or may have

         * been unset after setHead. So we must check to see if tail

         * is actually first node. If not, we continue on, safely

         * traversing from tail back to head to find first,

         * guaranteeing termination.

         */

        Thread firstThread = null;

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

            Thread t = p.thread;

            if (t != null)

                firstThread = t;

        }

        return firstThread;

    }

    /**

     * 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.thread == 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.isShared()         &&

            s.thread != 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() {

        Node h, s;

        if ((h = head) != null) {

            if ((s = h.next) == null || s.waitStatus > 0) {

                s = null; // traverse in case of concurrent cancellation

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

                    if (p.waitStatus <= 0)

                        s = p;

                }

            }

            if (s != null && s.thread != Thread.currentThread())

                return true;

        }

        return false;

    }

    // 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.thread != 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) {

            Thread t = p.thread;

            if (t != null)

                list.add(t);

        }

        return list;

    }

    /**

     * Returns a collection containing threads that may be waiting to

     * acquire in exclusive mode. This has the same properties

     * as {@link #getQueuedThreads} except that it only returns

     * those threads waiting due to an exclusive acquire.

     *

     * @return the collection of threads

     */

    public final Collection<Thread> getExclusiveQueuedThreads() {

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

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

            if (!p.isShared()) {

                Thread t = p.thread;

                if (t != null)

                    list.add(t);

            }

        }

        return list;

    }

    /**

     * Returns a collection containing threads that may be waiting to

     * acquire in shared mode. This has the same properties

     * as {@link #getQueuedThreads} except that it only returns

     * those threads waiting due to a shared acquire.

     *

     * @return the collection of threads

     */

    public final Collection<Thread> getSharedQueuedThreads() {

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

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

            if (p.isShared()) {

                Thread t = p.thread;

                if (t != null)

                    list.add(t);

            }

        }

        return list;

    }

    /**

     * Returns a string identifying this synchronizer, as well as its state.

     * The state, in brackets, includes the String {@code "State ="}

     * followed by the current value of {@link #getState}, and either

     * {@code "nonempty"} or {@code "empty"} depending on whether the

     * queue is empty.

     *

     * @return a string identifying this synchronizer, as well as its state

     */

    public String toString() {

        return super.toString()

            + "[State = " + getState() + ", "

            + (hasQueuedThreads() ? "non" : "") + "empty queue]";

    }

    // Internal support methods for Conditions

    /**

     * Returns true if a node, always one that was initially placed on

     * a condition queue, is now waiting to reacquire on sync queue.

     * @param node the node

     * @return true if is reacquiring

     */

    final boolean isOnSyncQueue(Node node) {

        if (node.waitStatus == Node.CONDITION || node.prev == null)

            return false;

        if (node.next != null) // If has successor, it must be on queue

            return true;

        /*

         * node.prev can be non-null, but not yet on queue because

         * the CAS to place it on queue can fail. So we have to

         * traverse from tail to make sure it actually made it.  It

         * will always be near the tail in calls to this method, and

         * unless the CAS failed (which is unlikely), it will be

         * there, so we hardly ever traverse much.

         */

        return findNodeFromTail(node);

    }

    /**

     * Returns true if node is on sync queue by searching backwards from tail.

     * Called only when needed by isOnSyncQueue.

     * @return true if present

     */

    private boolean findNodeFromTail(Node node) {

        // We check for node first, since it's likely to be at or near tail.

        // tail is known to be non-null, so we could re-order to "save"

        // one null check, but we leave it this way to help the VM.

        for (Node p = tail;;) {

            if (p == node)

                return true;

            if (p == null)

                return false;

            p = p.prev;

        }

    }

    /**

     * Transfers a node from a condition queue onto sync queue.

     * Returns true if successful.

     * @param node the node

     * @return true if successfully transferred (else the node was

     * cancelled before signal)

     */

    final boolean transferForSignal(Node node) {

        /*

         * If cannot change waitStatus, the node has been cancelled.

         */

        if (!node.compareAndSetWaitStatus(Node.CONDITION, 0))

            return false;

        /*

         * Splice onto queue and try to set waitStatus of predecessor to

         * indicate that thread is (probably) waiting. If cancelled or

         * attempt to set waitStatus fails, wake up to resync (in which

         * case the waitStatus can be transiently and harmlessly wrong).

         */

        Node p = enq(node);

        int ws = p.waitStatus;

        if (ws > 0 || !p.compareAndSetWaitStatus(ws, Node.SIGNAL))

            LockSupport.unpark(node.thread);

        return true;

    }

    /**

     * Transfers node, if necessary, to sync queue after a cancelled wait.

     * Returns true if thread was cancelled before being signalled.

     *

     * @param node the node

     * @return true if cancelled before the node was signalled

     */

    final boolean transferAfterCancelledWait(Node node) {

        if (node.compareAndSetWaitStatus(Node.CONDITION, 0)) {

            enq(node);

            return true;

        }

        /*

         * If we lost out to a signal(), then we can't proceed

         * until it finishes its enq().  Cancelling during an