/*

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

 *

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

 * Other contributors include Andrew Wright, Jeffrey Hayes,

 * Pat Fisher, Mike Judd.

 */

import static java.util.concurrent.TimeUnit.MILLISECONDS;

import static java.util.concurrent.TimeUnit.NANOSECONDS;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.HashSet;

import java.util.concurrent.ThreadLocalRandom;

import java.util.concurrent.locks.AbstractQueuedSynchronizer;

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

import junit.framework.Test;

import junit.framework.TestSuite;

@SuppressWarnings("WaitNotInLoop") // we implement spurious-wakeup freedom

public class AbstractQueuedSynchronizerTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(AbstractQueuedSynchronizerTest.class);

    }

    /**

     * A simple mutex class, adapted from the class javadoc.  Exclusive

     * acquire tests exercise this as a sample user extension.  Other

     * methods/features of AbstractQueuedSynchronizer are tested via

     * other test classes, including those for ReentrantLock,

     * ReentrantReadWriteLock, and Semaphore.

     *

     * Unlike the javadoc sample, we don't track owner thread via

     * AbstractOwnableSynchronizer methods.

     */

    static class Mutex extends AbstractQueuedSynchronizer {

        /** An eccentric value for locked synchronizer state. */

        static final int LOCKED = (1 << 31) | (1 << 15);

        static final int UNLOCKED = 0;

        /** Owner thread is untracked, so this is really just isLocked(). */

        @Override public boolean isHeldExclusively() {

            int state = getState();

            assertTrue(state == UNLOCKED || state == LOCKED);

            return state == LOCKED;

        }

        @Override protected boolean tryAcquire(int acquires) {

            assertEquals(LOCKED, acquires);

            return compareAndSetState(UNLOCKED, LOCKED);

        }

        @Override protected boolean tryRelease(int releases) {

            if (getState() != LOCKED) throw new IllegalMonitorStateException();

            assertEquals(LOCKED, releases);

            setState(UNLOCKED);

            return true;

        }

        public boolean tryAcquireNanos(long nanos) throws InterruptedException {

            return tryAcquireNanos(LOCKED, nanos);

        }

        public boolean tryAcquire() {

            return tryAcquire(LOCKED);

        }

        public boolean tryRelease() {

            return tryRelease(LOCKED);

        }

        public void acquire() {

            acquire(LOCKED);

        }

        public void acquireInterruptibly() throws InterruptedException {

            acquireInterruptibly(LOCKED);

        }

        public void release() {

            release(LOCKED);

        }

        /** Faux-Implements Lock.newCondition(). */

        public ConditionObject newCondition() {

            return new ConditionObject();

        }

    }

    /**

     * A minimal latch class, to test shared mode.

     */

    static class BooleanLatch extends AbstractQueuedSynchronizer {

        public boolean isSignalled() { return getState() != 0; }

        public int tryAcquireShared(int ignore) {

            return isSignalled() ? 1 : -1;

        }

        public boolean tryReleaseShared(int ignore) {

            setState(1);

            return true;

        }

    }

    /**

     * A runnable calling acquireInterruptibly that does not expect to

     * be interrupted.

     */

    class InterruptibleSyncRunnable extends CheckedRunnable {

        final Mutex sync;

        InterruptibleSyncRunnable(Mutex sync) { this.sync = sync; }

        public void realRun() throws InterruptedException {

            sync.acquireInterruptibly();

        }

    }

    /**

     * A runnable calling acquireInterruptibly that expects to be

     * interrupted.

     */

    class InterruptedSyncRunnable extends CheckedInterruptedRunnable {

        final Mutex sync;

        InterruptedSyncRunnable(Mutex sync) { this.sync = sync; }

        public void realRun() throws InterruptedException {

            sync.acquireInterruptibly();

        }

    }

    /** A constant to clarify calls to checking methods below. */

    static final Thread[] NO_THREADS = new Thread[0];

    /**

     * Spin-waits until sync.isQueued(t) becomes true.

     */

    void waitForQueuedThread(AbstractQueuedSynchronizer sync, Thread t) {

        long startTime = System.nanoTime();

        while (!sync.isQueued(t)) {

            if (millisElapsedSince(startTime) > LONG_DELAY_MS)

            Thread.yield();

        }

        assertTrue(t.isAlive());

    }

    /**

     * Checks that sync has exactly the given queued threads.

     */

    void assertHasQueuedThreads(AbstractQueuedSynchronizer sync,

                                Thread... expected) {

        Collection<Thread> actual = sync.getQueuedThreads();

        assertEquals(expected.length > 0, sync.hasQueuedThreads());

        assertEquals(expected.length, sync.getQueueLength());

        assertEquals(expected.length, actual.size());

        assertEquals(expected.length == 0, actual.isEmpty());

        assertEquals(new HashSet<Thread>(actual),

                     new HashSet<Thread>(Arrays.asList(expected)));

    }

    /**

     * Checks that sync has exactly the given (exclusive) queued threads.

     */

    void assertHasExclusiveQueuedThreads(AbstractQueuedSynchronizer sync,

                                         Thread... expected) {

        assertHasQueuedThreads(sync, expected);

        assertEquals(new HashSet<Thread>(sync.getExclusiveQueuedThreads()),

                     new HashSet<Thread>(sync.getQueuedThreads()));

        assertEquals(0, sync.getSharedQueuedThreads().size());

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

    }

    /**

     * Checks that sync has exactly the given (shared) queued threads.

     */

    void assertHasSharedQueuedThreads(AbstractQueuedSynchronizer sync,

                                      Thread... expected) {

        assertHasQueuedThreads(sync, expected);

        assertEquals(new HashSet<Thread>(sync.getSharedQueuedThreads()),

                     new HashSet<Thread>(sync.getQueuedThreads()));

        assertEquals(0, sync.getExclusiveQueuedThreads().size());

        assertTrue(sync.getExclusiveQueuedThreads().isEmpty());

    }

    /**

     * Checks that condition c has exactly the given waiter threads,

     * after acquiring mutex.

     */

    void assertHasWaitersUnlocked(Mutex sync, ConditionObject c,

                                 Thread... threads) {

        sync.acquire();

        assertHasWaitersLocked(sync, c, threads);

        sync.release();

    }

    /**

     * Checks that condition c has exactly the given waiter threads.

     */

    void assertHasWaitersLocked(Mutex sync, ConditionObject c,

                                Thread... threads) {

        assertEquals(threads.length > 0, sync.hasWaiters(c));

        assertEquals(threads.length, sync.getWaitQueueLength(c));

        assertEquals(threads.length == 0, sync.getWaitingThreads(c).isEmpty());

        assertEquals(threads.length, sync.getWaitingThreads(c).size());

        assertEquals(new HashSet<Thread>(sync.getWaitingThreads(c)),

                     new HashSet<Thread>(Arrays.asList(threads)));

    }

    enum AwaitMethod { await, awaitTimed, awaitNanos, awaitUntil }

    /**

     * Awaits condition using the specified AwaitMethod.

     */

    void await(ConditionObject c, AwaitMethod awaitMethod)

            throws InterruptedException {

        long timeoutMillis = 2 * LONG_DELAY_MS;

        switch (awaitMethod) {

        case await:

            c.await();

            break;

        case awaitTimed:

            assertTrue(c.await(timeoutMillis, MILLISECONDS));

            break;

        case awaitNanos:

            long nanosTimeout = MILLISECONDS.toNanos(timeoutMillis);

            long nanosRemaining = c.awaitNanos(nanosTimeout);

            assertTrue(nanosRemaining > 0);

            break;

        case awaitUntil:

            assertTrue(c.awaitUntil(delayedDate(timeoutMillis)));

            break;

        default:

            throw new AssertionError();

        }

    }

    /**

     * Checks that awaiting the given condition times out (using the

     * default timeout duration).

     */

    void assertAwaitTimesOut(ConditionObject c, AwaitMethod awaitMethod) {

        final long timeoutMillis = timeoutMillis();

        final long startTime;

        try {

            switch (awaitMethod) {

            case awaitTimed:

                startTime = System.nanoTime();

                assertFalse(c.await(timeoutMillis, MILLISECONDS));

                assertTrue(millisElapsedSince(startTime) >= timeoutMillis);

                break;

            case awaitNanos:

                startTime = System.nanoTime();

                long nanosTimeout = MILLISECONDS.toNanos(timeoutMillis);

                long nanosRemaining = c.awaitNanos(nanosTimeout);

                assertTrue(nanosRemaining <= 0);

                assertTrue(nanosRemaining > -MILLISECONDS.toNanos(LONG_DELAY_MS));

                assertTrue(millisElapsedSince(startTime) >= timeoutMillis);

                break;

            case awaitUntil:

                // We shouldn't assume that nanoTime and currentTimeMillis

                // use the same time source, so don't use nanoTime here.

                java.util.Date delayedDate = delayedDate(timeoutMillis);

                assertFalse(c.awaitUntil(delayedDate(timeoutMillis)));

                assertTrue(new java.util.Date().getTime() >= delayedDate.getTime());

                break;

            default:

                throw new UnsupportedOperationException();

            }

        } catch (InterruptedException ie) { threadUnexpectedException(ie); }

    }

    /**

     * isHeldExclusively is false upon construction

     */

    public void testIsHeldExclusively() {

        Mutex sync = new Mutex();

        assertFalse(sync.isHeldExclusively());

    }

    /**

     * acquiring released sync succeeds

     */

    public void testAcquire() {

        Mutex sync = new Mutex();

        sync.acquire();

        assertTrue(sync.isHeldExclusively());

        sync.release();

        assertFalse(sync.isHeldExclusively());

    }

    /**

     * tryAcquire on a released sync succeeds

     */

    public void testTryAcquire() {

        Mutex sync = new Mutex();

        assertTrue(sync.tryAcquire());

        assertTrue(sync.isHeldExclusively());

        sync.release();

        assertFalse(sync.isHeldExclusively());

    }

    /**

     * hasQueuedThreads reports whether there are waiting threads

     */

    public void testHasQueuedThreads() {

        final Mutex sync = new Mutex();

        assertFalse(sync.hasQueuedThreads());

        sync.acquire();

        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));

        waitForQueuedThread(sync, t1);

        assertTrue(sync.hasQueuedThreads());

        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));

        waitForQueuedThread(sync, t2);

        assertTrue(sync.hasQueuedThreads());

        t1.interrupt();

        awaitTermination(t1);

        assertTrue(sync.hasQueuedThreads());

        sync.release();

        awaitTermination(t2);

        assertFalse(sync.hasQueuedThreads());

    }

    /**

     * isQueued(null) throws NullPointerException

     */

    public void testIsQueuedNPE() {

        final Mutex sync = new Mutex();

        try {

            sync.isQueued(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * isQueued reports whether a thread is queued

     */

    public void testIsQueued() {

        final Mutex sync = new Mutex();

        Thread t1 = new Thread(new InterruptedSyncRunnable(sync));

        Thread t2 = new Thread(new InterruptibleSyncRunnable(sync));

        assertFalse(sync.isQueued(t1));

        assertFalse(sync.isQueued(t2));

        sync.acquire();

        t1.start();

        waitForQueuedThread(sync, t1);

        assertTrue(sync.isQueued(t1));

        assertFalse(sync.isQueued(t2));

        t2.start();

        waitForQueuedThread(sync, t2);

        assertTrue(sync.isQueued(t1));

        assertTrue(sync.isQueued(t2));

        t1.interrupt();

        awaitTermination(t1);

        assertFalse(sync.isQueued(t1));

        assertTrue(sync.isQueued(t2));

        sync.release();

        awaitTermination(t2);

        assertFalse(sync.isQueued(t1));

        assertFalse(sync.isQueued(t2));

    }

    /**

     * getFirstQueuedThread returns first waiting thread or null if none

     */

    public void testGetFirstQueuedThread() {

        final Mutex sync = new Mutex();

        assertNull(sync.getFirstQueuedThread());

        sync.acquire();

        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));

        waitForQueuedThread(sync, t1);

        assertEquals(t1, sync.getFirstQueuedThread());

        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));

        waitForQueuedThread(sync, t2);

        assertEquals(t1, sync.getFirstQueuedThread());

        t1.interrupt();

        awaitTermination(t1);

        assertEquals(t2, sync.getFirstQueuedThread());

        sync.release();

        awaitTermination(t2);

        assertNull(sync.getFirstQueuedThread());

    }

    /**

     * hasContended reports false if no thread has ever blocked, else true

     */

    public void testHasContended() {

        final Mutex sync = new Mutex();

        assertFalse(sync.hasContended());

        sync.acquire();

        assertFalse(sync.hasContended());

        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));

        waitForQueuedThread(sync, t1);

        assertTrue(sync.hasContended());

        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));

        waitForQueuedThread(sync, t2);

        assertTrue(sync.hasContended());

        t1.interrupt();

        awaitTermination(t1);

        assertTrue(sync.hasContended());

        sync.release();

        awaitTermination(t2);

        assertTrue(sync.hasContended());

    }

    /**

     * getQueuedThreads returns all waiting threads

     */

    public void testGetQueuedThreads() {

        final Mutex sync = new Mutex();

        Thread t1 = new Thread(new InterruptedSyncRunnable(sync));

        Thread t2 = new Thread(new InterruptibleSyncRunnable(sync));

        assertHasExclusiveQueuedThreads(sync, NO_THREADS);

        sync.acquire();

        assertHasExclusiveQueuedThreads(sync, NO_THREADS);

        t1.start();

        waitForQueuedThread(sync, t1);

        assertHasExclusiveQueuedThreads(sync, t1);

        assertTrue(sync.getQueuedThreads().contains(t1));

        assertFalse(sync.getQueuedThreads().contains(t2));

        t2.start();

        waitForQueuedThread(sync, t2);

        assertHasExclusiveQueuedThreads(sync, t1, t2);

        assertTrue(sync.getQueuedThreads().contains(t1));

        assertTrue(sync.getQueuedThreads().contains(t2));

        t1.interrupt();

        awaitTermination(t1);

        assertHasExclusiveQueuedThreads(sync, t2);

        sync.release();

        awaitTermination(t2);

        assertHasExclusiveQueuedThreads(sync, NO_THREADS);

    }

    /**

     * getExclusiveQueuedThreads returns all exclusive waiting threads

     */

    public void testGetExclusiveQueuedThreads() {

        final Mutex sync = new Mutex();

        Thread t1 = new Thread(new InterruptedSyncRunnable(sync));

        Thread t2 = new Thread(new InterruptibleSyncRunnable(sync));

        assertHasExclusiveQueuedThreads(sync, NO_THREADS);

        sync.acquire();

        assertHasExclusiveQueuedThreads(sync, NO_THREADS);

        t1.start();

        waitForQueuedThread(sync, t1);

        assertHasExclusiveQueuedThreads(sync, t1);

        assertTrue(sync.getExclusiveQueuedThreads().contains(t1));

        assertFalse(sync.getExclusiveQueuedThreads().contains(t2));

        t2.start();

        waitForQueuedThread(sync, t2);

        assertHasExclusiveQueuedThreads(sync, t1, t2);

        assertTrue(sync.getExclusiveQueuedThreads().contains(t1));

        assertTrue(sync.getExclusiveQueuedThreads().contains(t2));

        t1.interrupt();

        awaitTermination(t1);

        assertHasExclusiveQueuedThreads(sync, t2);

        sync.release();

        awaitTermination(t2);

        assertHasExclusiveQueuedThreads(sync, NO_THREADS);

    }

    /**

     * getSharedQueuedThreads does not include exclusively waiting threads

     */

    public void testGetSharedQueuedThreads_Exclusive() {

        final Mutex sync = new Mutex();

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

        sync.acquire();

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

        Thread t1 = newStartedThread(new InterruptedSyncRunnable(sync));

        waitForQueuedThread(sync, t1);

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

        Thread t2 = newStartedThread(new InterruptibleSyncRunnable(sync));

        waitForQueuedThread(sync, t2);

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

        t1.interrupt();

        awaitTermination(t1);

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

        sync.release();

        awaitTermination(t2);

        assertTrue(sync.getSharedQueuedThreads().isEmpty());

    }

    /**

     * getSharedQueuedThreads returns all shared waiting threads

     */

    public void testGetSharedQueuedThreads_Shared() {

        final BooleanLatch l = new BooleanLatch();

        assertHasSharedQueuedThreads(l, NO_THREADS);

        Thread t1 = newStartedThread(new CheckedInterruptedRunnable() {

            public void realRun() throws InterruptedException {

                l.acquireSharedInterruptibly(0);

            }});

        waitForQueuedThread(l, t1);