content: /*
   * Copyright (C) 2014 The Android Open Source Project
   * Copyright (c) 1997, 2005, 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 sun.misc.Cleaner;
  
  /**
   * 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
   */
  // BEGIN Android-changed: Reimplemented to accomodate a different GC and compiler.
  
  public class ReferenceQueue<T> {
  
      // Reference.queueNext will be set to sQueueNextUnenqueued to indicate
      // when a reference has been enqueued and removed from its queue.
      private static final Reference sQueueNextUnenqueued = new PhantomReference(null, null);
  
      // NOTE: This implementation of ReferenceQueue is FIFO (queue-like) whereas
      // the OpenJdk implementation is LIFO (stack-like).
      private Reference<? extends T> head = null;
      private Reference<? extends T> tail = null;
  
      private final Object lock = new Object();
  
      /**
       * Constructs a new reference-object queue.
       */
      public ReferenceQueue() { }
  
      /**
       * Enqueue the given reference onto this queue.
       * The caller is responsible for ensuring the lock is held on this queue,
       * and for calling notifyAll on this queue after the reference has been
       * enqueued. Returns true if the reference was enqueued successfully,
       * false if the reference had already been enqueued.
       * @GuardedBy("lock")
       */
      private boolean enqueueLocked(Reference<? extends T> r) {
          // Verify the reference has not already been enqueued.
          if (r.queueNext != null) {
              return false;
          }
  
          if (r instanceof Cleaner) {
              // If this reference is a Cleaner, then simply invoke the clean method instead
              // of enqueueing it in the queue. Cleaners are associated with dummy queues that
              // are never polled and objects are never enqueued on them.
              Cleaner cl = (sun.misc.Cleaner) r;
              cl.clean();
  
              // Update queueNext to indicate that the reference has been
              // enqueued, but is now removed from the queue.
              r.queueNext = sQueueNextUnenqueued;
              return true;
          }
  
          if (tail == null) {
              head = r;
          } else {
              tail.queueNext = r;
          }
          tail = r;
          tail.queueNext = r;
          return true;
      }
  
      /**
       * Test if the given reference object has been enqueued but not yet
       * removed from the queue, assuming this is the reference object's queue.
       */
      boolean isEnqueued(Reference<? extends T> reference) {
          synchronized (lock) {
              return reference.queueNext != null && reference.queueNext != sQueueNextUnenqueued;
          }
      }
  
      /**
       * Enqueue the reference object on the receiver.
       *
       * @param reference
       *            reference object to be enqueued.
       * @return true if the reference was enqueued.
       */
      boolean enqueue(Reference<? extends T> reference) {
          synchronized (lock) {
              if (enqueueLocked(reference)) {
                  lock.notifyAll();
                  return true;
              }
              return false;
          }
      }
  
      // @GuardedBy("lock")
      private Reference<? extends T> reallyPollLocked() {
          if (head != null) {
              Reference<? extends T> r = head;
              if (head == tail) {
                  tail = null;
                  head = null;
              } else {
                  head = head.queueNext;
              }
  
              // Update queueNext to indicate that the reference has been
              // enqueued, but is now removed from the queue.
              r.queueNext = sQueueNextUnenqueued;
              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() {
          synchronized (lock) {
              if (head == null)
                  return null;
  
              return reallyPollLocked();
          }
      }
  
      /**
       * 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 = reallyPollLocked();
              if (r != null) return r;
              long start = (timeout == 0) ? 0 : System.nanoTime();
              for (;;) {
                  lock.wait(timeout);
                  r = reallyPollLocked();
                  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);
      }
  
      /**
       * Enqueue the given list of currently pending (unenqueued) references.
       *
       * @hide
       */
      public static void enqueuePending(Reference<?> list) {
          Reference<?> start = list;
          do {
              ReferenceQueue queue = list.queue;
              if (queue == null) {
                  Reference<?> next = list.pendingNext;
  
                  // Make pendingNext a self-loop to preserve the invariant that
                  // once enqueued, pendingNext is non-null -- without leaking
                  // the object pendingNext was previously pointing to.
                  list.pendingNext = list;
                  list = next;
              } else {
                  // To improve performance, we try to avoid repeated
                  // synchronization on the same queue by batching enqueue of
                  // consecutive references in the list that have the same
                  // queue.
                  synchronized (queue.lock) {
                      do {
                          Reference<?> next = list.pendingNext;
  
                          // Make pendingNext a self-loop to preserve the
                          // invariant that once enqueued, pendingNext is
                          // non-null -- without leaking the object pendingNext
                          // was previously pointing to.
                          list.pendingNext = list;
                          queue.enqueueLocked(list);
                          list = next;
                      } while (list != start && list.queue == queue);
                      queue.lock.notifyAll();
                  }
              }
          } while (list != start);
      }
  
      /**
       * List of references that the GC says need to be enqueued.
       * Protected by ReferenceQueue.class lock.
       * @hide
       */
      public static Reference<?> unenqueued = null;
  
      static void add(Reference<?> list) {
          synchronized (ReferenceQueue.class) {
              if (unenqueued == null) {
                  unenqueued = list;
              } else {
                  // Find the last element in unenqueued.
                  Reference<?> last = unenqueued;
                  while (last.pendingNext != unenqueued) {
                    last = last.pendingNext;
                  }
                  // Add our list to the end. Update the pendingNext to point back to enqueued.
                  last.pendingNext = list;
                  last = list;
                  while (last.pendingNext != list) {
                      last = last.pendingNext;
                  }
                  last.pendingNext = unenqueued;
              }
              ReferenceQueue.class.notifyAll();
          }
      }
  }
  // END Android-changed: Reimplemented to accomodate a different GC and compiler.
  