/*

 * 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 java.util.Arrays;

import java.util.Collection;

import java.util.HashSet;

import java.util.concurrent.CountDownLatch;

import java.util.concurrent.atomic.AtomicBoolean;

import java.util.concurrent.locks.Condition;

import java.util.concurrent.locks.Lock;

import java.util.concurrent.locks.ReentrantReadWriteLock;

import junit.framework.Test;

import junit.framework.TestSuite;

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

public class ReentrantReadWriteLockTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(ReentrantReadWriteLockTest.class);

    }

    /**

     * A runnable calling lockInterruptibly

     */

    class InterruptibleLockRunnable extends CheckedRunnable {

        final ReentrantReadWriteLock lock;

        InterruptibleLockRunnable(ReentrantReadWriteLock l) { lock = l; }

        public void realRun() throws InterruptedException {

            lock.writeLock().lockInterruptibly();

        }

    }

    /**

     * A runnable calling lockInterruptibly that expects to be

     * interrupted

     */

    class InterruptedLockRunnable extends CheckedInterruptedRunnable {

        final ReentrantReadWriteLock lock;

        InterruptedLockRunnable(ReentrantReadWriteLock l) { lock = l; }

        public void realRun() throws InterruptedException {

            lock.writeLock().lockInterruptibly();

        }

    }

    /**

     * Subclass to expose protected methods

     */

    static class PublicReentrantReadWriteLock extends ReentrantReadWriteLock {

        PublicReentrantReadWriteLock() { super(); }

        PublicReentrantReadWriteLock(boolean fair) { super(fair); }

        public Thread getOwner() {

            return super.getOwner();

        }

        public Collection<Thread> getQueuedThreads() {

            return super.getQueuedThreads();

        }

        public Collection<Thread> getWaitingThreads(Condition c) {

            return super.getWaitingThreads(c);

        }

    }

    /**

     * Releases write lock, checking that it had a hold count of 1.

     */

    void releaseWriteLock(PublicReentrantReadWriteLock lock) {

        ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock();

        assertWriteLockedByMoi(lock);

        assertEquals(1, lock.getWriteHoldCount());

        writeLock.unlock();

        assertNotWriteLocked(lock);

    }

    /**

     * Spin-waits until lock.hasQueuedThread(t) becomes true.

     */

    void waitForQueuedThread(PublicReentrantReadWriteLock lock, Thread t) {

        long startTime = System.nanoTime();

        while (!lock.hasQueuedThread(t)) {

            if (millisElapsedSince(startTime) > LONG_DELAY_MS)

                throw new AssertionError("timed out");

            Thread.yield();

        }

        assertTrue(t.isAlive());

        assertNotSame(t, lock.getOwner());

    }

    /**

     * Checks that lock is not write-locked.

     */

    void assertNotWriteLocked(PublicReentrantReadWriteLock lock) {

        assertFalse(lock.isWriteLocked());

        assertFalse(lock.isWriteLockedByCurrentThread());

        assertFalse(lock.writeLock().isHeldByCurrentThread());

        assertEquals(0, lock.getWriteHoldCount());

        assertEquals(0, lock.writeLock().getHoldCount());

        assertNull(lock.getOwner());

    }

    /**

     * Checks that lock is write-locked by the given thread.

     */

    void assertWriteLockedBy(PublicReentrantReadWriteLock lock, Thread t) {

        assertTrue(lock.isWriteLocked());

        assertSame(t, lock.getOwner());

        assertEquals(t == Thread.currentThread(),

                     lock.isWriteLockedByCurrentThread());

        assertEquals(t == Thread.currentThread(),

                     lock.writeLock().isHeldByCurrentThread());

        assertEquals(t == Thread.currentThread(),

                     lock.getWriteHoldCount() > 0);

        assertEquals(t == Thread.currentThread(),

                     lock.writeLock().getHoldCount() > 0);

        assertEquals(0, lock.getReadLockCount());

    }

    /**

     * Checks that lock is write-locked by the current thread.

     */

    void assertWriteLockedByMoi(PublicReentrantReadWriteLock lock) {

        assertWriteLockedBy(lock, Thread.currentThread());

    }

    /**

     * Checks that condition c has no waiters.

     */

    void assertHasNoWaiters(PublicReentrantReadWriteLock lock, Condition c) {

        assertHasWaiters(lock, c, new Thread[] {});

    }

    /**

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

     */

    void assertHasWaiters(PublicReentrantReadWriteLock lock, Condition c,

                          Thread... threads) {

        lock.writeLock().lock();

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

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

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

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

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

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

        lock.writeLock().unlock();

    }

    enum AwaitMethod { await, awaitTimed, awaitNanos, awaitUntil }

    /**

     * Awaits condition "indefinitely" using the specified AwaitMethod.

     */

    void await(Condition 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 timeoutNanos = MILLISECONDS.toNanos(timeoutMillis);

            long nanosRemaining = c.awaitNanos(timeoutNanos);

            assertTrue(nanosRemaining > timeoutNanos / 2);

            assertTrue(nanosRemaining <= timeoutNanos);

            break;

        case awaitUntil:

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

            break;

        default:

            throw new AssertionError();

        }

    }

    /**

     * Constructor sets given fairness, and is in unlocked state

     */

    public void testConstructor() {

        PublicReentrantReadWriteLock lock;

        lock = new PublicReentrantReadWriteLock();

        assertFalse(lock.isFair());

        assertNotWriteLocked(lock);

        assertEquals(0, lock.getReadLockCount());

        lock = new PublicReentrantReadWriteLock(true);

        assertTrue(lock.isFair());

        assertNotWriteLocked(lock);

        assertEquals(0, lock.getReadLockCount());

        lock = new PublicReentrantReadWriteLock(false);

        assertFalse(lock.isFair());

        assertNotWriteLocked(lock);

        assertEquals(0, lock.getReadLockCount());

    }

    /**

     * write-locking and read-locking an unlocked lock succeed

     */

    public void testLock()      { testLock(false); }

    public void testLock_fair() { testLock(true); }

    public void testLock(boolean fair) {

        PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        assertNotWriteLocked(lock);

        lock.writeLock().lock();

        assertWriteLockedByMoi(lock);

        lock.writeLock().unlock();

        assertNotWriteLocked(lock);

        assertEquals(0, lock.getReadLockCount());

        lock.readLock().lock();

        assertNotWriteLocked(lock);

        assertEquals(1, lock.getReadLockCount());

        lock.readLock().unlock();

        assertNotWriteLocked(lock);

        assertEquals(0, lock.getReadLockCount());

    }

    /**

     * getWriteHoldCount returns number of recursive holds

     */

    public void testGetWriteHoldCount()      { testGetWriteHoldCount(false); }

    public void testGetWriteHoldCount_fair() { testGetWriteHoldCount(true); }

    public void testGetWriteHoldCount(boolean fair) {

        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(fair);

        for (int i = 1; i <= SIZE; i++) {

            lock.writeLock().lock();

            assertEquals(i,lock.getWriteHoldCount());

        }

        for (int i = SIZE; i > 0; i--) {

            lock.writeLock().unlock();

            assertEquals(i - 1,lock.getWriteHoldCount());

        }

    }

    /**

     * writelock.getHoldCount returns number of recursive holds

     */

    public void testGetHoldCount()      { testGetHoldCount(false); }

    public void testGetHoldCount_fair() { testGetHoldCount(true); }

    public void testGetHoldCount(boolean fair) {

        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(fair);

        for (int i = 1; i <= SIZE; i++) {

            lock.writeLock().lock();

            assertEquals(i,lock.writeLock().getHoldCount());

        }

        for (int i = SIZE; i > 0; i--) {

            lock.writeLock().unlock();

            assertEquals(i - 1,lock.writeLock().getHoldCount());

        }

    }

    /**

     * getReadHoldCount returns number of recursive holds

     */

    public void testGetReadHoldCount()      { testGetReadHoldCount(false); }

    public void testGetReadHoldCount_fair() { testGetReadHoldCount(true); }

    public void testGetReadHoldCount(boolean fair) {

        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(fair);

        for (int i = 1; i <= SIZE; i++) {

            lock.readLock().lock();

            assertEquals(i,lock.getReadHoldCount());

        }

        for (int i = SIZE; i > 0; i--) {

            lock.readLock().unlock();

            assertEquals(i - 1,lock.getReadHoldCount());

        }

    }

    /**

     * write-unlocking an unlocked lock throws IllegalMonitorStateException

     */

    public void testWriteUnlock_IMSE()      { testWriteUnlock_IMSE(false); }

    public void testWriteUnlock_IMSE_fair() { testWriteUnlock_IMSE(true); }

    public void testWriteUnlock_IMSE(boolean fair) {

        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(fair);

        try {

            lock.writeLock().unlock();

            shouldThrow();

        } catch (IllegalMonitorStateException success) {}

    }

    /**

     * read-unlocking an unlocked lock throws IllegalMonitorStateException

     */

    public void testReadUnlock_IMSE()      { testReadUnlock_IMSE(false); }

    public void testReadUnlock_IMSE_fair() { testReadUnlock_IMSE(true); }

    public void testReadUnlock_IMSE(boolean fair) {

        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(fair);

        try {

            lock.readLock().unlock();

            shouldThrow();

        } catch (IllegalMonitorStateException success) {}

    }

    /**

     * write-lockInterruptibly is interruptible

     */

    public void testWriteLockInterruptibly_Interruptible()      { testWriteLockInterruptibly_Interruptible(false); }

    public void testWriteLockInterruptibly_Interruptible_fair() { testWriteLockInterruptibly_Interruptible(true); }

    public void testWriteLockInterruptibly_Interruptible(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.writeLock().lock();

        Thread t = newStartedThread(new CheckedInterruptedRunnable() {

            public void realRun() throws InterruptedException {

                lock.writeLock().lockInterruptibly();

            }});

        waitForQueuedThread(lock, t);

        t.interrupt();

        awaitTermination(t);

        releaseWriteLock(lock);

    }

    /**

     * timed write-tryLock is interruptible

     */

    public void testWriteTryLock_Interruptible()      { testWriteTryLock_Interruptible(false); }

    public void testWriteTryLock_Interruptible_fair() { testWriteTryLock_Interruptible(true); }

    public void testWriteTryLock_Interruptible(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.writeLock().lock();

        Thread t = newStartedThread(new CheckedInterruptedRunnable() {

            public void realRun() throws InterruptedException {

                lock.writeLock().tryLock(2 * LONG_DELAY_MS, MILLISECONDS);

            }});

        waitForQueuedThread(lock, t);

        t.interrupt();

        awaitTermination(t);

        releaseWriteLock(lock);

    }

    /**

     * read-lockInterruptibly is interruptible

     */

    public void testReadLockInterruptibly_Interruptible()      { testReadLockInterruptibly_Interruptible(false); }

    public void testReadLockInterruptibly_Interruptible_fair() { testReadLockInterruptibly_Interruptible(true); }

    public void testReadLockInterruptibly_Interruptible(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.writeLock().lock();

        Thread t = newStartedThread(new CheckedInterruptedRunnable() {

            public void realRun() throws InterruptedException {

                lock.readLock().lockInterruptibly();

            }});

        waitForQueuedThread(lock, t);

        t.interrupt();

        awaitTermination(t);

        releaseWriteLock(lock);

    }

    /**

     * timed read-tryLock is interruptible

     */

    public void testReadTryLock_Interruptible()      { testReadTryLock_Interruptible(false); }

    public void testReadTryLock_Interruptible_fair() { testReadTryLock_Interruptible(true); }

    public void testReadTryLock_Interruptible(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.writeLock().lock();

        Thread t = newStartedThread(new CheckedInterruptedRunnable() {

            public void realRun() throws InterruptedException {

                lock.readLock().tryLock(2 * LONG_DELAY_MS, MILLISECONDS);

            }});

        waitForQueuedThread(lock, t);

        t.interrupt();

        awaitTermination(t);

        releaseWriteLock(lock);

    }

    /**

     * write-tryLock on an unlocked lock succeeds

     */

    public void testWriteTryLock()      { testWriteTryLock(false); }

    public void testWriteTryLock_fair() { testWriteTryLock(true); }

    public void testWriteTryLock(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        assertTrue(lock.writeLock().tryLock());

        assertWriteLockedByMoi(lock);

        assertTrue(lock.writeLock().tryLock());

        assertWriteLockedByMoi(lock);

        lock.writeLock().unlock();

        releaseWriteLock(lock);

    }

    /**

     * write-tryLock fails if locked

     */

    public void testWriteTryLockWhenLocked()      { testWriteTryLockWhenLocked(false); }

    public void testWriteTryLockWhenLocked_fair() { testWriteTryLockWhenLocked(true); }

    public void testWriteTryLockWhenLocked(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.writeLock().lock();

        Thread t = newStartedThread(new CheckedRunnable() {

            public void realRun() {

                assertFalse(lock.writeLock().tryLock());

            }});

        awaitTermination(t);

        releaseWriteLock(lock);

    }

    /**

     * read-tryLock fails if locked

     */

    public void testReadTryLockWhenLocked()      { testReadTryLockWhenLocked(false); }

    public void testReadTryLockWhenLocked_fair() { testReadTryLockWhenLocked(true); }

    public void testReadTryLockWhenLocked(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.writeLock().lock();

        Thread t = newStartedThread(new CheckedRunnable() {

            public void realRun() {

                assertFalse(lock.readLock().tryLock());

            }});

        awaitTermination(t);

        releaseWriteLock(lock);

    }

    /**

     * Multiple threads can hold a read lock when not write-locked

     */

    public void testMultipleReadLocks()      { testMultipleReadLocks(false); }

    public void testMultipleReadLocks_fair() { testMultipleReadLocks(true); }

    public void testMultipleReadLocks(boolean fair) {

        final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(fair);

        lock.readLock().lock();

        Thread t = newStartedThread(new CheckedRunnable() {

            public void realRun() throws InterruptedException {

                assertTrue(lock.readLock().tryLock());

                lock.readLock().unlock();

                assertTrue(lock.readLock().tryLock(LONG_DELAY_MS, MILLISECONDS));

                lock.readLock().unlock();

                lock.readLock().lock();

                lock.readLock().unlock();

            }});

        awaitTermination(t);

        lock.readLock().unlock();

    }

    /**

     * A writelock succeeds only after a reading thread unlocks

     */

    public void testWriteAfterReadLock()      { testWriteAfterReadLock(false); }

    public void testWriteAfterReadLock_fair() { testWriteAfterReadLock(true); }

    public void testWriteAfterReadLock(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.readLock().lock();

        Thread t = newStartedThread(new CheckedRunnable() {

            public void realRun() {

                assertEquals(1, lock.getReadLockCount());

                lock.writeLock().lock();

                assertEquals(0, lock.getReadLockCount());

                lock.writeLock().unlock();

            }});

        waitForQueuedThread(lock, t);

        assertNotWriteLocked(lock);

        assertEquals(1, lock.getReadLockCount());

        lock.readLock().unlock();

        assertEquals(0, lock.getReadLockCount());

        awaitTermination(t);

        assertNotWriteLocked(lock);

    }

    /**

     * A writelock succeeds only after reading threads unlock

     */

    public void testWriteAfterMultipleReadLocks()      { testWriteAfterMultipleReadLocks(false); }

    public void testWriteAfterMultipleReadLocks_fair() { testWriteAfterMultipleReadLocks(true); }

    public void testWriteAfterMultipleReadLocks(boolean fair) {

        final PublicReentrantReadWriteLock lock =

            new PublicReentrantReadWriteLock(fair);

        lock.readLock().lock();

        lock.readLock().lock();

        Thread t1 = newStartedThread(new CheckedRunnable() {

            public void realRun() {

                lock.readLock().lock();

                assertEquals(3, lock.getReadLockCount());

                lock.readLock().unlock();

            }});