/*

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

        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 {

            for (;;) {

                final Node p = node.predecessor();

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

                    setHead(node);

                    p.next = null; // help GC

                    return interrupted;

                }

            }

        } 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.