/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * 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.
 */

package java.lang.ref;

/**
 * Reference queues, to which registered reference objects are appended by the
 * garbage collector after the appropriate reachability changes are detected.
 *
 * @author   Mark Reinhold
 * @since    1.2
 */

public class ReferenceQueue<T> {

    /**
     * Constructs a new reference-object queue.
     */
    public ReferenceQueue() { }

    private static class Null<S> extends ReferenceQueue<S> {
        boolean enqueue(Reference<? extends S> r) {
            return false;
        }
    }

    static final ReferenceQueue<Object> NULL = new Null<>();
    static final ReferenceQueue<Object> ENQUEUED = new Null<>();

    static private class Lock { }
    private final Lock lock = new Lock();
    private volatile int waiters;

    @SuppressWarnings("unused")
    private volatile Reference<? extends T> head; // we assign using Unsafe CAS

    boolean enqueue(Reference<? extends T> r) { /* Called only by Reference class */
        if (markEnqueued(r)) {
            addChunk(r, r);
            return true;
        } else {
            return false;
        }
    }

    boolean markEnqueued(Reference<?> r) {
        ReferenceQueue<?> queue;
        do {
            // Check that this reference hasn't already been
            // enqueued (and even then removed)
            queue = r.queue;
            if ((queue == NULL) || (queue == ENQUEUED)) {
                return false;
            }
        } while (!r.casQueue(queue, ENQUEUED));
        assert queue == this;
        return true;
    }

    @SuppressWarnings("unchecked")
    void addChunk(Reference<?> chunkHead, Reference<?> chunkTail) {
        Reference<? extends T> h;
        do {
            h = head;
            chunkTail.next = (h == null) ? chunkTail : h;
        } while (!casHead(h, (Reference) chunkHead));
        // notify waiters
        if (waiters > 0) {
            synchronized (lock) {
                if (waiters > 0) {
                    lock.notifyAll();
                }
            }
        }
    }

    private Reference<? extends T> reallyPoll() {
        Reference<? extends T> r;
        while ((r = head) != null) {
            @SuppressWarnings("unchecked") // due to cast to raw type
            Reference<? extends T> nh = (r.next == r)
                ? null : (Reference) r.next;
            if (casHead(r, nh)) {
                r.lazySetQueue(NULL);
                UNSAFE.storeFence();
                r.next = r;
                break;
            }
        }
        return r;
    }

    /**
     * Polls this queue to see if a reference object is available.  If one is
     * available without further delay then it is removed from the queue and
     * returned.  Otherwise this method immediately returns <tt>null</tt>.
     *
     * @return  A reference object, if one was immediately available,
     *          otherwise <code>null</code>
     */
    public Reference<? extends T> poll() {
        return reallyPoll();
    }

    /**
     * Removes the next reference object in this queue, blocking until either
     * one becomes available or the given timeout period expires.
     *
     * <p> This method does not offer real-time guarantees: It schedules the
     * timeout as if by invoking the {@link Object#wait(long)} method.
     *
     * @param  timeout  If positive, block for up to <code>timeout</code>
     *                  milliseconds while waiting for a reference to be
     *                  added to this queue.  If zero, block indefinitely.
     *
     * @return  A reference object, if one was available within the specified
     *          timeout period, otherwise <code>null</code>
     *
     * @throws  IllegalArgumentException
     *          If the value of the timeout argument is negative
     *
     * @throws  InterruptedException
     *          If the timeout wait is interrupted
     */
    public Reference<? extends T> remove(long timeout)
        throws IllegalArgumentException, InterruptedException
    {
        if (timeout < 0) {
            throw new IllegalArgumentException("Negative timeout value");
        }
        Reference<? extends T> r = reallyPoll();
        if (r != null) return r;
        return reallyRemove(timeout);
    }

    private Reference<? extends T> reallyRemove(long timeout) throws InterruptedException {
        long deadline = (timeout == 0)
                ? 0 : System.nanoTime() + timeout * 1000_000L;

        synchronized (lock) {
            int w = waiters;
            waiters = w + 1;
            try {
                for (; ; ) {
                    Reference<? extends T> r = reallyPoll();
                    if (r != null) return r;
                    if (timeout == 0) {
                        lock.wait(0);
                    } else {
                        long timeoutNanos = deadline - System.nanoTime();
                        if (timeoutNanos <= 0) return null;
                        lock.wait(timeoutNanos / 1000_000L, (int) (timeoutNanos % 1000_000L));
                    }
                }
            } finally {
                waiters = w;
            }
        }
    }

    /**
     * Removes the next reference object in this queue, blocking until one
     * becomes available.
     *
     * @return A reference object, blocking until one becomes available
     * @throws  InterruptedException  If the wait is interrupted
     */
    public Reference<? extends T> remove() throws InterruptedException {
        return remove(0);
    }

    // Unsafe machinery

    private boolean casHead(Reference<?> cmp, Reference<? extends T> val) {
        return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
    }

    private static final sun.misc.Unsafe UNSAFE;
    private static final long headOffset;

    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<ReferenceQueue> rqc = ReferenceQueue.class;
            headOffset = UNSAFE.objectFieldOffset(rqc.getDeclaredField("head"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}