/*

 * Copyright 1997-2005 Sun Microsystems, Inc.  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.  Sun designates this

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

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.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 extends ReferenceQueue {

        boolean enqueue(Reference r) {

            return false;

        }

    }

    static ReferenceQueue NULL = new Null();

    static ReferenceQueue ENQUEUED = new Null();

    static private class Lock { };

    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 (r) {

            if (r.queue == ENQUEUED) return false;

            synchronized (lock) {

                r.queue = ENQUEUED;

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

                head = r;

                queueLength++;

                if (r instanceof FinalReference) {

                    sun.misc.VM.addFinalRefCount(1);

                }

                lock.notifyAll();

                return true;

            }

        }

    }

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

        if (head != null) {

            Reference<? extends T> r = head;

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

            r.queue = NULL;

            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 <tt>null</tt>.

     *

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

     *          otherwise <code>null</code>

     */

    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</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");

        }

        synchronized (lock) {

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

            if (r != null) return r;

            for (;;) {

                lock.wait(timeout);

                r = reallyPoll();

                if (r != null) return r;

                if (timeout != 0) return null;

            }

        }

    }

    /**

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

    }

}