1 /*

     2  * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

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

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package sun.misc;

    27 

    28 import java.util.Enumeration;

    29 import java.util.NoSuchElementException;

    30 

    31 /**

    32  * Queue: implements a simple queue mechanism.  Allows for enumeration of the

    33  * elements.

    34  *

    35  * @author Herb Jellinek

    36  */

    37 

    38 public class Queue<T> {

    39 

    40     int length = 0;

    41 

    42     QueueElement<T> head = null;

    43     QueueElement<T> tail = null;

    44 

    45     public Queue() {

    46     }

    47 

    48     /**

    49      * Enqueue an object.

    50      */

    51     public synchronized void enqueue(T obj) {

    52 

    53         QueueElement<T> newElt = new QueueElement<>(obj);

    54 

    55         if (head == null) {

    56             head = newElt;

    57             tail = newElt;

    58             length = 1;

    59         } else {

    60             newElt.next = head;

    61             head.prev = newElt;

    62             head = newElt;

    63             length++;

    64         }

    65         notify();

    66     }

    67 

    68     /**

    69      * Dequeue the oldest object on the queue.  Will wait indefinitely.

    70      *

    71      * @return    the oldest object on the queue.

    72      * @exception java.lang.InterruptedException if any thread has

    73      *              interrupted this thread.

    74      */

    75     public T dequeue() throws InterruptedException {

    76         return dequeue(0L);

    77     }

    78 

    79     /**

    80      * Dequeue the oldest object on the queue.

    81      * @param timeOut the number of milliseconds to wait for something

    82      * to arrive.

    83      *

    84      * @return    the oldest object on the queue.

    85      * @exception java.lang.InterruptedException if any thread has

    86      *              interrupted this thread.

    87      */

    88     public synchronized T dequeue(long timeOut)

    89         throws InterruptedException {

    90 

    91         while (tail == null) {

    92             wait(timeOut);

    93         }

    94         QueueElement<T> elt = tail;

    95         tail = elt.prev;

    96         if (tail == null) {

    97             head = null;

    98         } else {

    99             tail.next = null;

   100         }

   101         length--;

   102         return elt.obj;

   103     }

   104 

   105     /**

   106      * Is the queue empty?

   107      * @return true if the queue is empty.

   108      */

   109     public synchronized boolean isEmpty() {

   110         return (tail == null);

   111     }

   112 

   113     /**

   114      * Returns an enumeration of the elements in Last-In, First-Out

   115      * order. Use the Enumeration methods on the returned object to

   116      * fetch the elements sequentially.

   117      */

   118     public final synchronized Enumeration<T> elements() {

   119         return new LIFOQueueEnumerator<>(this);

   120     }

   121 

   122     /**

   123      * Returns an enumeration of the elements in First-In, First-Out

   124      * order. Use the Enumeration methods on the returned object to

   125      * fetch the elements sequentially.

   126      */

   127     public final synchronized Enumeration<T> reverseElements() {

   128         return new FIFOQueueEnumerator<>(this);

   129     }

   130 

   131     public synchronized void dump(String msg) {

   132         System.err.println(">> "+msg);

   133         System.err.println("["+length+" elt(s); head = "+

   134                            (head == null ? "null" : (head.obj)+"")+

   135                            " tail = "+(tail == null ? "null" : (tail.obj)+""));

   136         QueueElement<T> cursor = head;

   137         QueueElement<T> last = null;

   138         while (cursor != null) {

   139             System.err.println("  "+cursor);

   140             last = cursor;

   141             cursor = cursor.next;

   142         }

   143         if (last != tail) {

   144             System.err.println("  tail != last: "+tail+", "+last);

   145         }

   146         System.err.println("]");

   147     }

   148 }

   149 

   150 final class FIFOQueueEnumerator<T> implements Enumeration<T> {

   151     Queue<T> queue;

   152     QueueElement<T> cursor;

   153 

   154     FIFOQueueEnumerator(Queue<T> q) {

   155         queue = q;

   156         cursor = q.tail;

   157     }

   158 

   159     public boolean hasMoreElements() {

   160         return (cursor != null);

   161     }

   162 

   163     public T nextElement() {

   164         synchronized (queue) {

   165             if (cursor != null) {

   166                 QueueElement<T> result = cursor;

   167                 cursor = cursor.prev;

   168                 return result.obj;

   169             }

   170         }

   171         throw new NoSuchElementException("FIFOQueueEnumerator");

   172     }

   173 }

   174 

   175 final class LIFOQueueEnumerator<T> implements Enumeration<T> {

   176     Queue<T> queue;

   177     QueueElement<T> cursor;

   178 

   179     LIFOQueueEnumerator(Queue<T> q) {

   180         queue = q;

   181         cursor = q.head;

   182     }

   183 

   184     public boolean hasMoreElements() {

   185         return (cursor != null);

   186     }

   187 

   188     public T nextElement() {

   189         synchronized (queue) {

   190             if (cursor != null) {

   191                 QueueElement<T> result = cursor;

   192                 cursor = cursor.next;

   193                 return result.obj;

   194             }

   195         }

   196         throw new NoSuchElementException("LIFOQueueEnumerator");

   197     }

   198 }

   199 

   200 class QueueElement<T> {

   201     QueueElement<T> next = null;

   202     QueueElement<T> prev = null;

   203 

   204     T obj = null;

   205 

   206     QueueElement(T obj) {

   207         this.obj = obj;

   208     }

   209 

   210     public String toString() {

   211         return "QueueElement[obj="+obj+(prev == null ? " null" : " prev")+

   212             (next == null ? " null" : " next")+"]";

   213     }

   214 }