/*

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

import java.util.concurrent.*;

import java.util.concurrent.atomic.*;

import sun.misc.Unsafe;

/**

 * A version of {@link AbstractQueuedSynchronizer} in

 * which synchronization state is maintained as a <tt>long</tt>.

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

 * as <tt>AbstractQueuedSynchronizer</tt> with the exception

 * that all state-related parameters and results are defined

 * as <tt>long</tt> rather than <tt>int</tt>. 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 <tt>AbstractQueuedLongSynchronizer</tt> instance

     * with initial synchronization state of zero.

     */

    protected AbstractQueuedLongSynchronizer() { }

    /**

     * Wait queue node class.

     *

     * <p>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, but

     * use the same basic tactic of holding some of the control

     * information about a thread in the predecessor of its node.  A

     * "status" field in each node keeps track of whether a thread

     * should block.  A node is signalled when its predecessor

     * releases.  Each node of the queue otherwise serves as a

     * specific-notification-style monitor holding a single waiting

     * thread. The status field does NOT control whether threads are

     * granted locks etc though.  A thread may try to acquire if it is

     * first in the queue. But being first does not guarantee success;

     * it only gives the right to contend.  So the currently released

     * contender thread may need to rewait.

     *

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

     * tail. To dequeue, you just set the head field.

     * <pre>

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

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

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

     * </pre>

     *

     * <p>Insertion into a CLH queue requires only a single atomic

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

     * demarcation from unqueued to queued. Similarly, dequeing

     * involves only updating the "head". However, it takes a bit

     * more work for nodes to determine who their successors are,

     * in part to deal with possible cancellation due to timeouts

     * and interrupts.

     *

     * <p>The "prev" links (not used in original CLH locks), are mainly

     * needed to handle cancellation. If a node is cancelled, its

     * successor is (normally) relinked to a non-cancelled

     * predecessor. For explanation of similar mechanics in the case

     * of spin locks, see the papers by Scott and Scherer at

     * http://www.cs.rochester.edu/u/scott/synchronization/

     *

     * <p>We also use "next" links to implement blocking mechanics.

     * The thread id for each node is kept in its own node, so a

     * predecessor signals the next node to wake up by traversing

     * next link to determine which thread it is.  Determination of

     * successor must avoid races with newly queued nodes to set

     * the "next" fields of their predecessors.  This is solved

     * when necessary by checking backwards from the atomically

     * updated "tail" when a node's successor appears to be null.

     * (Or, said differently, the next-links are an optimization

     * so that we don't usually need a backward scan.)

     *

     * <p>Cancellation introduces some conservatism to the basic

     * algorithms.  Since we must poll for cancellation of other

     * nodes, we can miss noticing whether a cancelled node is

     * ahead or behind us. This is dealt with by always unparking

     * successors upon cancellation, allowing them to stabilize on

     * a new predecessor, unless we can identify an uncancelled

     * predecessor who will carry this responsibility.

     *

     * <p>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.

     *

     * <p>Threads waiting on Conditions use the same nodes, but

     * use an additional link. 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

     * transferred to the main queue.  A special value of status

     * field is used to mark which queue a node is on.

     *

     * <p>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.

     */

    static final class Node {

        /** Marker to indicate a node is waiting in shared mode */

        static final Node SHARED = new Node();

        /** Marker to indicate a node is waiting in exclusive mode */

        static final Node EXCLUSIVE = null;

        /** waitStatus value to indicate thread has cancelled */

        static final int CANCELLED =  1;

        /** waitStatus value to indicate successor's thread needs unparking */

        static final int SIGNAL    = -1;

        /** waitStatus value to indicate thread is waiting on condition */

        static final int CONDITION = -2;

        /**

         * waitStatus value to indicate the next acquireShared should

         * unconditionally propagate

         */

        static final int PROPAGATE = -3;

        /**

         * Status field, taking on only the values:

         *   SIGNAL:     The successor of this node is (or will soon be)

         *               blocked (via park), so the current node must

         *               unpark its successor when it releases or

         *               cancels. To avoid races, acquire methods must

         *               first indicate they need a signal,

         *               then retry the atomic acquire, and then,

         *               on failure, block.

         *   CANCELLED:  This node is cancelled due to timeout or interrupt.

         *               Nodes never leave this state. In particular,

         *               a thread with cancelled node never again blocks.

         *   CONDITION:  This node is currently on a condition queue.

         *               It will not be used as a sync queue node

         *               until transferred, at which time the status

         *               will be set to 0. (Use of this value here has

         *               nothing to do with the other uses of the

         *               field, but simplifies mechanics.)

         *   PROPAGATE:  A releaseShared should be propagated to other

         *               nodes. This is set (for head node only) in

         *               doReleaseShared to ensure propagation

         *               continues, even if other operations have

         *               since intervened.

         *   0:          None of the above

         *

         * The values are arranged numerically to simplify use.

         * Non-negative values mean that a node doesn't need to

         * signal. So, most code doesn't need to check for particular

         * values, just for sign.

         *

         * The field is initialized to 0 for normal sync nodes, and

         * CONDITION for condition nodes.  It is modified using CAS

         * (or when possible, unconditional volatile writes).

         */

        volatile int waitStatus;

        /**

         * Link to predecessor node that current node/thread relies on

         * for checking waitStatus. Assigned during enqueing, and nulled

         * out (for sake of GC) only upon dequeuing.  Also, upon

         * cancellation of a predecessor, we short-circuit while

         * finding a non-cancelled one, which will always exist

         * because the head node is never cancelled: A node becomes

         * head only as a result of successful acquire. A

         * cancelled thread never succeeds in acquiring, and a thread only

         * cancels itself, not any other node.

         */

        volatile Node prev;

        /**

         * Link to the successor node that the current node/thread

         * unparks upon release. Assigned during enqueuing, adjusted

         * when bypassing cancelled predecessors, and nulled out (for

         * sake of GC) when dequeued.  The enq operation does not

         * assign next field of a predecessor until after attachment,

         * so seeing a null next field does not necessarily mean that

         * node is at end of queue. However, if a next field appears

         * to be null, we can scan prev's from the tail to

         * double-check.  The next field of cancelled nodes is set to

         * point to the node itself instead of null, to make life

         * easier for isOnSyncQueue.

         */

        volatile Node next;

        /**

         * The thread that enqueued this node.  Initialized on

         * construction and nulled out after use.

         */

        volatile Thread thread;

        /**

         * Link to next node waiting on condition, or the special

         * value SHARED.  Because condition queues are accessed only

         * when holding in exclusive mode, we just need a simple

         * linked queue to hold nodes while they are waiting on

         * conditions. They are then transferred to the queue to

         * re-acquire. And because conditions can only be exclusive,

         * we save a field by using special value to indicate shared

         * mode.

         */

        Node nextWaiter;

        /**

         * Returns true if node is waiting in shared mode

         */

        final boolean isShared() {

            return nextWaiter == SHARED;

        }

        /**

         * Returns previous node, or throws NullPointerException if null.

         * Use when predecessor cannot be null.  The null check could

         * be elided, but is present to help the VM.

         *

         * @return the predecessor of this node

         */

        final Node predecessor() throws NullPointerException {

            Node p = prev;

            if (p == null)

                throw new NullPointerException();

            else

                return p;

        }

        Node() {    // Used to establish initial head or SHARED marker

        }

        Node(Thread thread, Node mode) {     // Used by addWaiter

            this.nextWaiter = mode;

            this.thread = thread;

        }

        Node(Thread thread, int waitStatus) { // Used by Condition

            this.waitStatus = waitStatus;

            this.thread = thread;

        }

    }

    /**

     * 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 <tt>volatile</tt> read.

     * @return current state value

     */

    protected final long getState() {

        return state;

    }

    /**

     * Sets the value of synchronization state.

     * This operation has memory semantics of a <tt>volatile</tt> write.

     * @param newState the new state value

     */

    protected final void setState(long 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 <tt>volatile</tt> read

     * and write.

     *

     * @param expect the expected value

     * @param update the new value

     * @return 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) {

        // See below for intrinsics setup to support this

        return unsafe.compareAndSwapLong(this, stateOffset, 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 spinForTimeoutThreshold = 1000L;

    /**

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

     * @param node the node to insert

     * @return node's predecessor

     */

    private Node enq(final Node node) {

        for (;;) {

            Node t = tail;

            if (t == null) { // Must initialize

                if (compareAndSetHead(new Node()))

                    tail = head;

            } else {

                node.prev = t;

                if (compareAndSetTail(t, node)) {

                    t.next = node;

                    return t;

                }

            }

        }

    }

    /**

     * 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(Thread.currentThread(), mode);

        // Try the fast path of enq; backup to full enq on failure

        Node pred = tail;

        if (pred != null) {

            node.prev = pred;

            if (compareAndSetTail(pred, node)) {

                pred.next = node;

                return node;

            }

        }

        enq(node);

        return node;

    }

    /**

     * 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)

            compareAndSetWaitStatus(node, 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 t = tail; t != null && t != node; t = t.prev)

                if (t.waitStatus <= 0)

                    s = t;

        }

        if (s != null)

            LockSupport.unpark(s.thread);

    }

    /**

     * Release action for shared mode -- signal successor and ensure

     * 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 (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))

                        continue;            // loop to recheck cases

                    unparkSuccessor(h);

                }

                else if (ws == 0 &&

                         !compareAndSetWaitStatus(h, 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) 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) {

            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.

        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)) {

            compareAndSetNext(pred, 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 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&

                pred.thread != null) {

                Node next = node.next;

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

                    compareAndSetNext(pred, 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.

             */

            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);

        }

        return false;

    }

    /**

     * Convenience method to interrupt current thread.

     */

    private 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 failed = true;

        try {

            boolean interrupted = false;

            for (;;) {

                final Node p = node.predecessor();

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

                    setHead(node);

                    p.next = null; // help GC

                    failed = false;

                    return interrupted;

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    interrupted = true;

            }

        } finally {

            if (failed)

                cancelAcquire(node);

        }

    }

    /**

     * Acquires in exclusive interruptible mode.

     * @param arg the acquire argument

     */

    private void doAcquireInterruptibly(long arg)

        throws InterruptedException {

        final Node node = addWaiter(Node.EXCLUSIVE);

        boolean failed = true;

        try {

            for (;;) {

                final Node p = node.predecessor();

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

                    setHead(node);

                    p.next = null; // help GC

                    failed = false;

                    return;

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    throw new InterruptedException();

            }

        } finally {

            if (failed)

                cancelAcquire(node);

        }

    }

    /**

     * 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 {

        long lastTime = System.nanoTime();

        final Node node = addWaiter(Node.EXCLUSIVE);

        boolean failed = true;

        try {

            for (;;) {

                final Node p = node.predecessor();

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

                    setHead(node);

                    p.next = null; // help GC

                    failed = false;

                    return true;

                }

                if (nanosTimeout <= 0)

                    return false;

                if (shouldParkAfterFailedAcquire(p, node) &&

                    nanosTimeout > spinForTimeoutThreshold)

                    LockSupport.parkNanos(this, nanosTimeout);

                long now = System.nanoTime();

                nanosTimeout -= now - lastTime;

                lastTime = now;

                if (Thread.interrupted())

                    throw new InterruptedException();

            }

        } finally {

            if (failed)

                cancelAcquire(node);

        }

    }

    /**

     * Acquires in shared uninterruptible mode.

     * @param arg the acquire argument

     */

    private void doAcquireShared(long arg) {

        final Node node = addWaiter(Node.SHARED);

        boolean failed = true;

        try {

            boolean interrupted = false;

            for (;;) {

                final Node p = node.predecessor();

                if (p == head) {

                    long r = tryAcquireShared(arg);

                    if (r >= 0) {

                        setHeadAndPropagate(node, r);

                        p.next = null; // help GC

                        if (interrupted)

                            selfInterrupt();

                        failed = false;

                        return;

                    }

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    interrupted = true;

            }

        } finally {

            if (failed)

                cancelAcquire(node);

        }

    }

    /**

     * Acquires in shared interruptible mode.

     * @param arg the acquire argument

     */

    private void doAcquireSharedInterruptibly(long arg)

        throws InterruptedException {

        final Node node = addWaiter(Node.SHARED);

        boolean failed = true;

        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

                        failed = false;

                        return;

                    }

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    throw new InterruptedException();

            }

        } finally {

            if (failed)

                cancelAcquire(node);

        }

    }

    /**

     * 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 {

        long lastTime = System.nanoTime();

        final Node node = addWaiter(Node.SHARED);

        boolean failed = true;

        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

                        failed = false;

                        return true;

                    }

                }

                if (nanosTimeout <= 0)

                    return false;

                if (shouldParkAfterFailedAcquire(p, node) &&

                    nanosTimeout > spinForTimeoutThreshold)

                    LockSupport.parkNanos(this, nanosTimeout);

                long now = System.nanoTime();

                nanosTimeout -= now - lastTime;

                lastTime = now;

                if (Thread.interrupted())

                    throw new InterruptedException();

            }

        } finally {

            if (failed)

                cancelAcquire(node);

        }

    }

    // 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 non-waiting {@link ConditionObject} method.

     * (Waiting methods instead invoke {@link #release}.)

     *

     * <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)