/*
 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.lang.ref;

import java.util.function.Consumer;
import jdk.internal.misc.VM;

/**
 * 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<Object> {
 boolean enqueue(Reference<?> r) {
 return false;
 }
 }

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

 private static class Lock { };
 private final Lock lock = new Lock();
 private volatile Reference<? extends T> head;
 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;
 // Self-loop end, so if a FinalReference it remains inactive.
 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) {
 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;
 // Handle self-looped next as end of list designator.
 head = (rn == r) ? null : rn;
 // Self-loop next rather than setting to null, so if a
 // FinalReference it remains inactive.
 r.next = r;
 queueLength--;
 if (r instanceof FinalReference) {
 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;
 }
 }
 }
}