author | alanb |
Fri, 22 Feb 2013 14:04:06 +0000 | |
changeset 16023 | 58ecc1b8327b |
parent 14342 | 8435a30053c1 |
permissions | -rw-r--r-- |
2 | 1 |
/* |
14342
8435a30053c1
7197491: update copyright year to match last edit in jdk8 jdk repository
alanb
parents:
11131
diff
changeset
|
2 |
* Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved. |
2 | 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 |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 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 |
* |
|
5506 | 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. |
|
2 | 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 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
38 |
public class Queue<T> { |
2 | 39 |
|
40 |
int length = 0; |
|
41 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
42 |
QueueElement<T> head = null; |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
43 |
QueueElement<T> tail = null; |
2 | 44 |
|
45 |
public Queue() { |
|
46 |
} |
|
47 |
||
48 |
/** |
|
49 |
* Enqueue an object. |
|
50 |
*/ |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
51 |
public synchronized void enqueue(T obj) { |
2 | 52 |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
53 |
QueueElement<T> newElt = new QueueElement<>(obj); |
2 | 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 |
*/ |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
75 |
public T dequeue() throws InterruptedException { |
2 | 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 |
*/ |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
88 |
public synchronized T dequeue(long timeOut) |
2 | 89 |
throws InterruptedException { |
90 |
||
91 |
while (tail == null) { |
|
92 |
wait(timeOut); |
|
93 |
} |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
94 |
QueueElement<T> elt = tail; |
2 | 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 |
*/ |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
118 |
public final synchronized Enumeration<T> elements() { |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
119 |
return new LIFOQueueEnumerator<>(this); |
2 | 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 |
*/ |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
127 |
public final synchronized Enumeration<T> reverseElements() { |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
128 |
return new FIFOQueueEnumerator<>(this); |
2 | 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)+"")); |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
136 |
QueueElement<T> cursor = head; |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
137 |
QueueElement<T> last = null; |
2 | 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 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
150 |
final class FIFOQueueEnumerator<T> implements Enumeration<T> { |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
151 |
Queue<T> queue; |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
152 |
QueueElement<T> cursor; |
2 | 153 |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
154 |
FIFOQueueEnumerator(Queue<T> q) { |
2 | 155 |
queue = q; |
156 |
cursor = q.tail; |
|
157 |
} |
|
158 |
||
159 |
public boolean hasMoreElements() { |
|
160 |
return (cursor != null); |
|
161 |
} |
|
162 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
163 |
public T nextElement() { |
2 | 164 |
synchronized (queue) { |
165 |
if (cursor != null) { |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
166 |
QueueElement<T> result = cursor; |
2 | 167 |
cursor = cursor.prev; |
168 |
return result.obj; |
|
169 |
} |
|
170 |
} |
|
171 |
throw new NoSuchElementException("FIFOQueueEnumerator"); |
|
172 |
} |
|
173 |
} |
|
174 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
175 |
final class LIFOQueueEnumerator<T> implements Enumeration<T> { |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
176 |
Queue<T> queue; |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
177 |
QueueElement<T> cursor; |
2 | 178 |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
179 |
LIFOQueueEnumerator(Queue<T> q) { |
2 | 180 |
queue = q; |
181 |
cursor = q.head; |
|
182 |
} |
|
183 |
||
184 |
public boolean hasMoreElements() { |
|
185 |
return (cursor != null); |
|
186 |
} |
|
187 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
188 |
public T nextElement() { |
2 | 189 |
synchronized (queue) { |
190 |
if (cursor != null) { |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
191 |
QueueElement<T> result = cursor; |
2 | 192 |
cursor = cursor.next; |
193 |
return result.obj; |
|
194 |
} |
|
195 |
} |
|
196 |
throw new NoSuchElementException("LIFOQueueEnumerator"); |
|
197 |
} |
|
198 |
} |
|
199 |
||
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
200 |
class QueueElement<T> { |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
201 |
QueueElement<T> next = null; |
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
202 |
QueueElement<T> prev = null; |
2 | 203 |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
204 |
T obj = null; |
2 | 205 |
|
11131
27747ee5a62a
7116857: Warnings in javax.security and some sun.misc
weijun
parents:
5506
diff
changeset
|
206 |
QueueElement(T obj) { |
2 | 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 |
} |