/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/publicdomain/zero/1.0/

 */

package java.util.concurrent.locks;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Date;

import java.util.concurrent.TimeUnit;

import java.util.concurrent.ForkJoinPool;

import jdk.internal.misc.Unsafe;

/**

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

     */

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

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

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

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

    /** CLH Nodes */

    abstract static class Node {

        volatile Node prev;       // initially attached via casTail

        volatile Node next;       // visibly nonnull when signallable

        Thread waiter;            // visibly nonnull when enqueued

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

        // methods for atomic operations

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

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

        }

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

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

        }

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

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

        }

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

            U.putReference(this, PREV, p);

        }

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

            U.putInt(this, STATUS, s);

        }

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

            U.putIntOpaque(this, STATUS, 0);

        }

        private static final long STATUS

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

        private static final long NEXT

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

        private static final long PREV

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

    }

    // Concrete classes tagged by type

    static final class ExclusiveNode extends Node { }

    static final class SharedNode extends Node { }

    static final class ConditionNode extends Node

        implements ForkJoinPool.ManagedBlocker {

        ConditionNode nextWaiter;            // link to next waiting node

        /**

         * Allows Conditions to be used in ForkJoinPools without

         * risking fixed pool exhaustion. This is usable only for

         * untimed Condition waits, not timed versions.

         */

        public final boolean isReleasable() {

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

        }

        public final boolean block() {

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

            return true;

        }

    }

    /**

     * Head of the wait queue, lazily initialized.

     */

    private transient volatile Node head;

    /**

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

     */

    private transient volatile Node tail;

    /**

     * The synchronization state.

     */

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

        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.compareAndSetLong(this, STATE, expect, update);

    }

    // Queuing utilities

    private boolean casTail(Node c, Node v) {

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

    }

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

    private void tryInitializeHead() {

        Node h = new ExclusiveNode();

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

            tail = h;

    }

    /**

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

     * ConditionNodes; other cases are interleaved with acquires.)

     */

    final void enqueue(Node node) {

        if (node != null) {

            for (;;) {

                Node t = tail;

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

                if (t == null)                 // initialize

                    tryInitializeHead();

                else if (casTail(t, node)) {

                    t.next = node;

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

                        LockSupport.unpark(node.waiter);

                    break;

                }

            }

        }

    }

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

    final boolean isEnqueued(Node node) {

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

            if (t == node)

                return true;

        return false;

    }

    /**

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

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

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

     * cancelAcquire ensures liveness.

     */

    private static void signalNext(Node h) {

        Node s;

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

            s.getAndUnsetStatus(WAITING);

            LockSupport.unpark(s.waiter);

        }

    }

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

    private static void signalNextIfShared(Node h) {

        Node s;

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

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

            s.getAndUnsetStatus(WAITING);

            LockSupport.unpark(s.waiter);

        }

    }

    /**

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

     *

     * @param node null unless a reacquiring Condition

     * @param arg the acquire argument

     * @param shared true if shared mode else exclusive

     * @param interruptible if abort and return negative on interrupt

     * @param timed if true use timed waits

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

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

     */

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

                      boolean interruptible, boolean timed, long time) {

        Thread current = Thread.currentThread();

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

        boolean interrupted = false, first = false;

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

        /*

         * Repeatedly:

         *  Check if node now first

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

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

         *  else if node not yet created, create it

         *  else if not yet enqueued, try once to enqueue

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

         *  else if WAITING status not set, set and retry

         *  else park and clear WAITING status, and check cancellation

         */

        for (;;) {

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

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

                if (pred.status < 0) {

                    cleanQueue();           // predecessor cancelled

                    continue;

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

                    Thread.onSpinWait();    // ensure serialization

                    continue;

                }

            }

            if (first || pred == null) {

                boolean acquired;

                try {

                    if (shared)

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

                    else

                        acquired = tryAcquire(arg);

                } catch (Throwable ex) {

                    cancelAcquire(node, interrupted, false);

                    throw ex;

                }

                if (acquired) {

                    if (first) {

                        node.prev = null;

                        head = node;

                        pred.next = null;

                        node.waiter = null;

                        if (shared)

                            signalNextIfShared(node);

                        if (interrupted)

                            current.interrupt();

                    }

                    return 1;

                }

            }

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

                if (shared)

                    node = new SharedNode();

                else

                    node = new ExclusiveNode();

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

                node.waiter = current;

                Node t = tail;

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

                if (t == null)

                    tryInitializeHead();

                else if (!casTail(t, node))

                    node.setPrevRelaxed(null);  // back out

                else

                    t.next = node;

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

                --spins;                        // reduce unfairness on rewaits

                Thread.onSpinWait();

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

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

            } else {

                long nanos;

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

                if (!timed)

                    LockSupport.park(this);

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

                    LockSupport.parkNanos(this, nanos);

                else

                    break;

                node.clearStatus();

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

                    break;

            }

        }

        return cancelAcquire(node, interrupted, interruptible);

    }

    /**

     * Possibly repeatedly traverses from tail, unsplicing cancelled

     * nodes until none are found.

     */

    private void cleanQueue() {

        for (;;) {                               // restart point

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

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

                    return;                      // end of list

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

                    break;                       // inconsistent

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

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

                        q.prev == p) {

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

                        if (p.prev == null)

                            signalNext(p);

                    }

                    break;

                }

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

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

                        p.casNext(n, q);

                        if (p.prev == null)

                            signalNext(p);

                    }

                    break;

                }

                s = q;

                q = q.prev;

            }

        }

    }

    /**

     * Cancels an ongoing attempt to acquire.

     *

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

     * @param interrupted true if thread interrupted

     * @param interruptible if should report interruption vs reset

     */

    private int cancelAcquire(Node node, boolean interrupted,

                              boolean interruptible) {

        if (node != null) {

            node.waiter = null;

            node.status = CANCELLED;

            if (node.prev != null)

                cleanQueue();

        }

        if (interrupted) {

            if (interruptible)

                return CANCELLED;

            else

                Thread.currentThread().interrupt();

        }

        return 0;

    }

    // Main exported methods

    /**

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

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

     * exclusive mode, and if so to acquire it.

     *

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

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

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

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

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

     *

     * <p>The default

     * implementation throws {@link UnsupportedOperationException}.

     *

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

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

     *        to a condition wait.  The value is otherwise uninterpreted

     *        and can represent anything you like.

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

     *         been acquired.

     * @throws IllegalMonitorStateException if acquiring would place this

     *         synchronizer in an illegal state. This exception must be

     *         thrown in a consistent fashion for synchronization to work

     *         correctly.

     * @throws UnsupportedOperationException if exclusive mode is not supported

     */

    protected boolean tryAcquire(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();