/*

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

        // Use putLongVolatile instead of ordinary volatile store when

        // using compareAndSwapLong, for sake of some 32bit systems.

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

        return U.compareAndSwapLong(this, STATE, 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) {

                U.putObject(node, Node.PREV, 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) {

                U.putObject(node, Node.PREV, 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.

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

        try {

            boolean interrupted = false;

            for (;;) {

                final Node p = node.predecessor();

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

                    setHead(node);

                    p.next = null; // help GC

                    return interrupted;

                }

                if (shouldParkAfterFailedAcquire(p, node) &&

                    parkAndCheckInterrupt())

                    interrupted = true;

            }

        } catch (Throwable t) {

            cancelAcquire(node);

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