/*

 * Copyright (c) 1997, 2015, 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;

import java.util.function.Consumer;

/**

 * 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 ReferenceQueue<Object> NULL = new Null<>();

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

    private Lock lock = new Lock();

    private volatile Reference<? extends T> head = null;

    private long queueLength = 0;

    boolean enqueue(Reference<? extends T> r) { /* Called only by Reference class */

        synchronized (lock) {

            // Check that since getting the lock this reference hasn't already been

            // enqueued (and even then removed)

            ReferenceQueue<?> queue = r.queue;

            if ((queue == NULL) || (queue == ENQUEUED)) {

                return false;

            }

            assert queue == this;

            r.next = (head == null) ? r : head;

            head = r;

            queueLength++;

            // Update r.queue *after* adding to list, to avoid race

            // with concurrent enqueued checks and fast-path poll().

            // Volatiles ensure ordering.

            r.queue = ENQUEUED;

            if (r instanceof FinalReference) {

                sun.misc.VM.addFinalRefCount(1);

            }

            lock.notifyAll();

            return true;

        }

    }

    private Reference<? extends T> reallyPoll() {       /* Must hold lock */

        Reference<? extends T> r = head;

        if (r != null) {

            r.queue = NULL;

            // Update r.queue *before* removing from list, to avoid

            // race with concurrent enqueued checks and fast-path

            // poll().  Volatiles ensure ordering.

            @SuppressWarnings("unchecked")

            Reference<? extends T> rn = r.next;

            head = (rn == r) ? null : rn;

            r.next = r;

            queueLength--;

            if (r instanceof FinalReference) {

                sun.misc.VM.addFinalRefCount(-1);

            }

            return r;

        }

        return null;

    }

    /**

     * 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 {@code null}.

     *

     * @return  A reference object, if one was immediately available,

     *          otherwise {@code null}

     */

    public Reference<? extends T> poll() {

        if (head == null)

            return null;

        synchronized (lock) {

            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}

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

     *

     * @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");

        }

        synchronized (lock) {

            Reference<? extends T> r = reallyPoll();

            if (r != null) return r;

            long start = (timeout == 0) ? 0 : System.nanoTime();

            for (;;) {

                lock.wait(timeout);

                r = reallyPoll();

                if (r != null) return r;

                if (timeout != 0) {

                    long end = System.nanoTime();

                    timeout -= (end - start) / 1000_000;

                    if (timeout <= 0) return null;

                    start = end;

                }

            }

        }

    }

    /**

     * 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);

    }

    /**

     * Iterate queue and invoke given action with each Reference.

     * Suitable for diagnostic purposes.

     * WARNING: any use of this method should make sure to not

     * retain the referents of iterated references (in case of

     * FinalReference(s)) so that their life is not prolonged more

     * than necessary.

     */

    void forEach(Consumer<? super Reference<? extends T>> action) {

        for (Reference<? extends T> r = head; r != null;) {

            action.accept(r);

            @SuppressWarnings("unchecked")

            Reference<? extends T> rn = r.next;

            if (rn == r) {

                if (r.queue == ENQUEUED) {

                    // still enqueued -> we reached end of chain

                    r = null;

                } else {

                    // already dequeued: r.queue == NULL; ->

                    // restart from head when overtaken by queue poller(s)

                    r = head;

                }

            } else {

                // next in chain

                r = rn;

            }

        }

    }

}