26 * This file is available under and governed by the GNU General Public |
26 * This file is available under and governed by the GNU General Public |
27 * License version 2 only, as published by the Free Software Foundation. |
27 * License version 2 only, as published by the Free Software Foundation. |
28 * However, the following notice accompanied the original version of this |
28 * However, the following notice accompanied the original version of this |
29 * file: |
29 * file: |
30 * |
30 * |
31 * Written by Doug Lea with assistance from members of JCP JSR-166 |
31 * Written by Doug Lea and Martin Buchholz with assistance from members of |
32 * Expert Group and released to the public domain, as explained at |
32 * JCP JSR-166 Expert Group and released to the public domain, as explained |
33 * http://creativecommons.org/licenses/publicdomain |
33 * at http://creativecommons.org/licenses/publicdomain |
34 */ |
34 */ |
35 |
35 |
36 package java.util.concurrent; |
36 package java.util.concurrent; |
37 |
37 |
38 import java.util.AbstractQueue; |
38 import java.util.AbstractQueue; |
51 * queue the shortest time. New elements |
51 * queue the shortest time. New elements |
52 * are inserted at the tail of the queue, and the queue retrieval |
52 * are inserted at the tail of the queue, and the queue retrieval |
53 * operations obtain elements at the head of the queue. |
53 * operations obtain elements at the head of the queue. |
54 * A {@code ConcurrentLinkedQueue} is an appropriate choice when |
54 * A {@code ConcurrentLinkedQueue} is an appropriate choice when |
55 * many threads will share access to a common collection. |
55 * many threads will share access to a common collection. |
56 * This queue does not permit {@code null} elements. |
56 * Like most other concurrent collection implementations, this class |
|
57 * does not permit the use of {@code null} elements. |
57 * |
58 * |
58 * <p>This implementation employs an efficient "wait-free" |
59 * <p>This implementation employs an efficient "wait-free" |
59 * algorithm based on one described in <a |
60 * algorithm based on one described in <a |
60 * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple, |
61 * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple, |
61 * Fast, and Practical Non-Blocking and Blocking Concurrent Queue |
62 * Fast, and Practical Non-Blocking and Blocking Concurrent Queue |
62 * Algorithms</a> by Maged M. Michael and Michael L. Scott. |
63 * Algorithms</a> by Maged M. Michael and Michael L. Scott. |
63 * |
64 * |
|
65 * <p>Iterators are <i>weakly consistent</i>, returning elements |
|
66 * reflecting the state of the queue at some point at or since the |
|
67 * creation of the iterator. They do <em>not</em> throw {@link |
|
68 * ConcurrentModificationException}, and may proceed concurrently with |
|
69 * other operations. Elements contained in the queue since the creation |
|
70 * of the iterator will be returned exactly once. |
|
71 * |
64 * <p>Beware that, unlike in most collections, the {@code size} method |
72 * <p>Beware that, unlike in most collections, the {@code size} method |
65 * is <em>NOT</em> a constant-time operation. Because of the |
73 * is <em>NOT</em> a constant-time operation. Because of the |
66 * asynchronous nature of these queues, determining the current number |
74 * asynchronous nature of these queues, determining the current number |
67 * of elements requires a traversal of the elements. |
75 * of elements requires a traversal of the elements. |
68 * |
76 * |
69 * <p>This class and its iterator implement all of the |
77 * <p>This class and its iterator implement all of the <em>optional</em> |
70 * <em>optional</em> methods of the {@link Collection} and {@link |
78 * methods of the {@link Queue} and {@link Iterator} interfaces. |
71 * Iterator} interfaces. |
|
72 * |
79 * |
73 * <p>Memory consistency effects: As with other concurrent |
80 * <p>Memory consistency effects: As with other concurrent |
74 * collections, actions in a thread prior to placing an object into a |
81 * collections, actions in a thread prior to placing an object into a |
75 * {@code ConcurrentLinkedQueue} |
82 * {@code ConcurrentLinkedQueue} |
76 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> |
83 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> |
130 * linking a Node that has just been dequeued to itself. Such a |
137 * linking a Node that has just been dequeued to itself. Such a |
131 * self-link implicitly means to advance to head. |
138 * self-link implicitly means to advance to head. |
132 * |
139 * |
133 * Both head and tail are permitted to lag. In fact, failing to |
140 * Both head and tail are permitted to lag. In fact, failing to |
134 * update them every time one could is a significant optimization |
141 * update them every time one could is a significant optimization |
135 * (fewer CASes). This is controlled by local "hops" variables |
142 * (fewer CASes). As with LinkedTransferQueue (see the internal |
136 * that only trigger helping-CASes after experiencing multiple |
143 * documentation for that class), we use a slack threshold of two; |
137 * lags. |
144 * that is, we update head/tail when the current pointer appears |
|
145 * to be two or more steps away from the first/last node. |
138 * |
146 * |
139 * Since head and tail are updated concurrently and independently, |
147 * Since head and tail are updated concurrently and independently, |
140 * it is possible for tail to lag behind head (why not)? |
148 * it is possible for tail to lag behind head (why not)? |
141 * |
149 * |
142 * CASing a Node's item reference to null atomically removes the |
150 * CASing a Node's item reference to null atomically removes the |
146 * to be successfully removed by two concurrent operations. The |
154 * to be successfully removed by two concurrent operations. The |
147 * method remove(Object) also lazily unlinks deleted Nodes, but |
155 * method remove(Object) also lazily unlinks deleted Nodes, but |
148 * this is merely an optimization. |
156 * this is merely an optimization. |
149 * |
157 * |
150 * When constructing a Node (before enqueuing it) we avoid paying |
158 * When constructing a Node (before enqueuing it) we avoid paying |
151 * for a volatile write to item by using lazySet instead of a |
159 * for a volatile write to item by using Unsafe.putObject instead |
152 * normal write. This allows the cost of enqueue to be |
160 * of a normal write. This allows the cost of enqueue to be |
153 * "one-and-a-half" CASes. |
161 * "one-and-a-half" CASes. |
154 * |
162 * |
155 * Both head and tail may or may not point to a Node with a |
163 * Both head and tail may or may not point to a Node with a |
156 * non-null item. If the queue is empty, all items must of course |
164 * non-null item. If the queue is empty, all items must of course |
157 * be null. Upon creation, both head and tail refer to a dummy |
165 * be null. Upon creation, both head and tail refer to a dummy |
159 * CAS, so they never regress, although again this is merely an |
167 * CAS, so they never regress, although again this is merely an |
160 * optimization. |
168 * optimization. |
161 */ |
169 */ |
162 |
170 |
163 private static class Node<E> { |
171 private static class Node<E> { |
164 private volatile E item; |
172 volatile E item; |
165 private volatile Node<E> next; |
173 volatile Node<E> next; |
166 |
174 |
|
175 /** |
|
176 * Constructs a new node. Uses relaxed write because item can |
|
177 * only be seen after publication via casNext. |
|
178 */ |
167 Node(E item) { |
179 Node(E item) { |
168 // Piggyback on imminent casNext() |
180 UNSAFE.putObject(this, itemOffset, item); |
169 lazySetItem(item); |
|
170 } |
|
171 |
|
172 E getItem() { |
|
173 return item; |
|
174 } |
181 } |
175 |
182 |
176 boolean casItem(E cmp, E val) { |
183 boolean casItem(E cmp, E val) { |
177 return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); |
184 return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); |
178 } |
185 } |
179 |
186 |
180 void setItem(E val) { |
|
181 item = val; |
|
182 } |
|
183 |
|
184 void lazySetItem(E val) { |
|
185 UNSAFE.putOrderedObject(this, itemOffset, val); |
|
186 } |
|
187 |
|
188 void lazySetNext(Node<E> val) { |
187 void lazySetNext(Node<E> val) { |
189 UNSAFE.putOrderedObject(this, nextOffset, val); |
188 UNSAFE.putOrderedObject(this, nextOffset, val); |
190 } |
|
191 |
|
192 Node<E> getNext() { |
|
193 return next; |
|
194 } |
189 } |
195 |
190 |
196 boolean casNext(Node<E> cmp, Node<E> val) { |
191 boolean casNext(Node<E> cmp, Node<E> val) { |
197 return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); |
192 return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); |
198 } |
193 } |
217 * Non-invariants: |
212 * Non-invariants: |
218 * - head.item may or may not be null. |
213 * - head.item may or may not be null. |
219 * - it is permitted for tail to lag behind head, that is, for tail |
214 * - it is permitted for tail to lag behind head, that is, for tail |
220 * to not be reachable from head! |
215 * to not be reachable from head! |
221 */ |
216 */ |
222 private transient volatile Node<E> head = new Node<E>(null); |
217 private transient volatile Node<E> head; |
223 |
218 |
224 /** |
219 /** |
225 * A node from which the last node on list (that is, the unique |
220 * A node from which the last node on list (that is, the unique |
226 * node with node.next == null) can be reached in O(1) time. |
221 * node with node.next == null) can be reached in O(1) time. |
227 * Invariants: |
222 * Invariants: |
231 * - tail.item may or may not be null. |
226 * - tail.item may or may not be null. |
232 * - it is permitted for tail to lag behind head, that is, for tail |
227 * - it is permitted for tail to lag behind head, that is, for tail |
233 * to not be reachable from head! |
228 * to not be reachable from head! |
234 * - tail.next may or may not be self-pointing to tail. |
229 * - tail.next may or may not be self-pointing to tail. |
235 */ |
230 */ |
236 private transient volatile Node<E> tail = head; |
231 private transient volatile Node<E> tail; |
237 |
232 |
238 |
233 |
239 /** |
234 /** |
240 * Creates a {@code ConcurrentLinkedQueue} that is initially empty. |
235 * Creates a {@code ConcurrentLinkedQueue} that is initially empty. |
241 */ |
236 */ |
242 public ConcurrentLinkedQueue() {} |
237 public ConcurrentLinkedQueue() { |
|
238 head = tail = new Node<E>(null); |
|
239 } |
243 |
240 |
244 /** |
241 /** |
245 * Creates a {@code ConcurrentLinkedQueue} |
242 * Creates a {@code ConcurrentLinkedQueue} |
246 * initially containing the elements of the given collection, |
243 * initially containing the elements of the given collection, |
247 * added in traversal order of the collection's iterator. |
244 * added in traversal order of the collection's iterator. |
|
245 * |
248 * @param c the collection of elements to initially contain |
246 * @param c the collection of elements to initially contain |
249 * @throws NullPointerException if the specified collection or any |
247 * @throws NullPointerException if the specified collection or any |
250 * of its elements are null |
248 * of its elements are null |
251 */ |
249 */ |
252 public ConcurrentLinkedQueue(Collection<? extends E> c) { |
250 public ConcurrentLinkedQueue(Collection<? extends E> c) { |
253 for (E e : c) |
251 Node<E> h = null, t = null; |
254 add(e); |
252 for (E e : c) { |
|
253 checkNotNull(e); |
|
254 Node<E> newNode = new Node<E>(e); |
|
255 if (h == null) |
|
256 h = t = newNode; |
|
257 else { |
|
258 t.lazySetNext(newNode); |
|
259 t = newNode; |
|
260 } |
|
261 } |
|
262 if (h == null) |
|
263 h = t = new Node<E>(null); |
|
264 head = h; |
|
265 tail = t; |
255 } |
266 } |
256 |
267 |
257 // Have to override just to update the javadoc |
268 // Have to override just to update the javadoc |
258 |
269 |
259 /** |
270 /** |
286 * Returns the successor of p, or the head node if p.next has been |
290 * Returns the successor of p, or the head node if p.next has been |
287 * linked to self, which will only be true if traversing with a |
291 * linked to self, which will only be true if traversing with a |
288 * stale pointer that is now off the list. |
292 * stale pointer that is now off the list. |
289 */ |
293 */ |
290 final Node<E> succ(Node<E> p) { |
294 final Node<E> succ(Node<E> p) { |
291 Node<E> next = p.getNext(); |
295 Node<E> next = p.next; |
292 return (p == next) ? head : next; |
296 return (p == next) ? head : next; |
293 } |
297 } |
294 |
298 |
295 /** |
299 /** |
296 * Inserts the specified element at the tail of this queue. |
300 * Inserts the specified element at the tail of this queue. |
297 * |
301 * |
298 * @return {@code true} (as specified by {@link Queue#offer}) |
302 * @return {@code true} (as specified by {@link Queue#offer}) |
299 * @throws NullPointerException if the specified element is null |
303 * @throws NullPointerException if the specified element is null |
300 */ |
304 */ |
301 public boolean offer(E e) { |
305 public boolean offer(E e) { |
302 if (e == null) throw new NullPointerException(); |
306 checkNotNull(e); |
303 Node<E> n = new Node<E>(e); |
307 final Node<E> newNode = new Node<E>(e); |
304 retry: |
308 |
|
309 for (Node<E> t = tail, p = t;;) { |
|
310 Node<E> q = p.next; |
|
311 if (q == null) { |
|
312 // p is last node |
|
313 if (p.casNext(null, newNode)) { |
|
314 // Successful CAS is the linearization point |
|
315 // for e to become an element of this queue, |
|
316 // and for newNode to become "live". |
|
317 if (p != t) // hop two nodes at a time |
|
318 casTail(t, newNode); // Failure is OK. |
|
319 return true; |
|
320 } |
|
321 // Lost CAS race to another thread; re-read next |
|
322 } |
|
323 else if (p == q) |
|
324 // We have fallen off list. If tail is unchanged, it |
|
325 // will also be off-list, in which case we need to |
|
326 // jump to head, from which all live nodes are always |
|
327 // reachable. Else the new tail is a better bet. |
|
328 p = (t != (t = tail)) ? t : head; |
|
329 else |
|
330 // Check for tail updates after two hops. |
|
331 p = (p != t && t != (t = tail)) ? t : q; |
|
332 } |
|
333 } |
|
334 |
|
335 public E poll() { |
|
336 restartFromHead: |
305 for (;;) { |
337 for (;;) { |
306 Node<E> t = tail; |
338 for (Node<E> h = head, p = h, q;;) { |
307 Node<E> p = t; |
339 E item = p.item; |
308 for (int hops = 0; ; hops++) { |
340 |
309 Node<E> next = succ(p); |
341 if (item != null && p.casItem(item, null)) { |
310 if (next != null) { |
342 // Successful CAS is the linearization point |
311 if (hops > HOPS && t != tail) |
343 // for item to be removed from this queue. |
312 continue retry; |
344 if (p != h) // hop two nodes at a time |
313 p = next; |
345 updateHead(h, ((q = p.next) != null) ? q : p); |
314 } else if (p.casNext(null, n)) { |
346 return item; |
315 if (hops >= HOPS) |
|
316 casTail(t, n); // Failure is OK. |
|
317 return true; |
|
318 } else { |
|
319 p = succ(p); |
|
320 } |
347 } |
321 } |
348 else if ((q = p.next) == null) { |
322 } |
349 updateHead(h, p); |
323 } |
350 return null; |
324 |
|
325 public E poll() { |
|
326 Node<E> h = head; |
|
327 Node<E> p = h; |
|
328 for (int hops = 0; ; hops++) { |
|
329 E item = p.getItem(); |
|
330 |
|
331 if (item != null && p.casItem(item, null)) { |
|
332 if (hops >= HOPS) { |
|
333 Node<E> q = p.getNext(); |
|
334 updateHead(h, (q != null) ? q : p); |
|
335 } |
351 } |
336 return item; |
352 else if (p == q) |
337 } |
353 continue restartFromHead; |
338 Node<E> next = succ(p); |
354 else |
339 if (next == null) { |
355 p = q; |
340 updateHead(h, p); |
356 } |
341 break; |
357 } |
342 } |
|
343 p = next; |
|
344 } |
|
345 return null; |
|
346 } |
358 } |
347 |
359 |
348 public E peek() { |
360 public E peek() { |
349 Node<E> h = head; |
361 restartFromHead: |
350 Node<E> p = h; |
|
351 E item; |
|
352 for (;;) { |
362 for (;;) { |
353 item = p.getItem(); |
363 for (Node<E> h = head, p = h, q;;) { |
354 if (item != null) |
364 E item = p.item; |
355 break; |
365 if (item != null || (q = p.next) == null) { |
356 Node<E> next = succ(p); |
366 updateHead(h, p); |
357 if (next == null) { |
367 return item; |
358 break; |
368 } |
359 } |
369 else if (p == q) |
360 p = next; |
370 continue restartFromHead; |
361 } |
371 else |
362 updateHead(h, p); |
372 p = q; |
363 return item; |
373 } |
|
374 } |
364 } |
375 } |
365 |
376 |
366 /** |
377 /** |
367 * Returns the first live (non-deleted) node on list, or null if none. |
378 * Returns the first live (non-deleted) node on list, or null if none. |
368 * This is yet another variant of poll/peek; here returning the |
379 * This is yet another variant of poll/peek; here returning the |
370 * first(), but that would cost an extra volatile read of item, |
381 * first(), but that would cost an extra volatile read of item, |
371 * and the need to add a retry loop to deal with the possibility |
382 * and the need to add a retry loop to deal with the possibility |
372 * of losing a race to a concurrent poll(). |
383 * of losing a race to a concurrent poll(). |
373 */ |
384 */ |
374 Node<E> first() { |
385 Node<E> first() { |
375 Node<E> h = head; |
386 restartFromHead: |
376 Node<E> p = h; |
|
377 Node<E> result; |
|
378 for (;;) { |
387 for (;;) { |
379 E item = p.getItem(); |
388 for (Node<E> h = head, p = h, q;;) { |
380 if (item != null) { |
389 boolean hasItem = (p.item != null); |
381 result = p; |
390 if (hasItem || (q = p.next) == null) { |
382 break; |
391 updateHead(h, p); |
383 } |
392 return hasItem ? p : null; |
384 Node<E> next = succ(p); |
393 } |
385 if (next == null) { |
394 else if (p == q) |
386 result = null; |
395 continue restartFromHead; |
387 break; |
396 else |
388 } |
397 p = q; |
389 p = next; |
398 } |
390 } |
399 } |
391 updateHead(h, p); |
|
392 return result; |
|
393 } |
400 } |
394 |
401 |
395 /** |
402 /** |
396 * Returns {@code true} if this queue contains no elements. |
403 * Returns {@code true} if this queue contains no elements. |
397 * |
404 * |
408 * |
415 * |
409 * <p>Beware that, unlike in most collections, this method is |
416 * <p>Beware that, unlike in most collections, this method is |
410 * <em>NOT</em> a constant-time operation. Because of the |
417 * <em>NOT</em> a constant-time operation. Because of the |
411 * asynchronous nature of these queues, determining the current |
418 * asynchronous nature of these queues, determining the current |
412 * number of elements requires an O(n) traversal. |
419 * number of elements requires an O(n) traversal. |
|
420 * Additionally, if elements are added or removed during execution |
|
421 * of this method, the returned result may be inaccurate. Thus, |
|
422 * this method is typically not very useful in concurrent |
|
423 * applications. |
413 * |
424 * |
414 * @return the number of elements in this queue |
425 * @return the number of elements in this queue |
415 */ |
426 */ |
416 public int size() { |
427 public int size() { |
417 int count = 0; |
428 int count = 0; |
418 for (Node<E> p = first(); p != null; p = succ(p)) { |
429 for (Node<E> p = first(); p != null; p = succ(p)) |
419 if (p.getItem() != null) { |
430 if (p.item != null) |
420 // Collections.size() spec says to max out |
431 // Collection.size() spec says to max out |
421 if (++count == Integer.MAX_VALUE) |
432 if (++count == Integer.MAX_VALUE) |
422 break; |
433 break; |
423 } |
|
424 } |
|
425 return count; |
434 return count; |
426 } |
435 } |
427 |
436 |
428 /** |
437 /** |
429 * Returns {@code true} if this queue contains the specified element. |
438 * Returns {@code true} if this queue contains the specified element. |
472 } |
480 } |
473 return false; |
481 return false; |
474 } |
482 } |
475 |
483 |
476 /** |
484 /** |
|
485 * Appends all of the elements in the specified collection to the end of |
|
486 * this queue, in the order that they are returned by the specified |
|
487 * collection's iterator. Attempts to {@code addAll} of a queue to |
|
488 * itself result in {@code IllegalArgumentException}. |
|
489 * |
|
490 * @param c the elements to be inserted into this queue |
|
491 * @return {@code true} if this queue changed as a result of the call |
|
492 * @throws NullPointerException if the specified collection or any |
|
493 * of its elements are null |
|
494 * @throws IllegalArgumentException if the collection is this queue |
|
495 */ |
|
496 public boolean addAll(Collection<? extends E> c) { |
|
497 if (c == this) |
|
498 // As historically specified in AbstractQueue#addAll |
|
499 throw new IllegalArgumentException(); |
|
500 |
|
501 // Copy c into a private chain of Nodes |
|
502 Node<E> beginningOfTheEnd = null, last = null; |
|
503 for (E e : c) { |
|
504 checkNotNull(e); |
|
505 Node<E> newNode = new Node<E>(e); |
|
506 if (beginningOfTheEnd == null) |
|
507 beginningOfTheEnd = last = newNode; |
|
508 else { |
|
509 last.lazySetNext(newNode); |
|
510 last = newNode; |
|
511 } |
|
512 } |
|
513 if (beginningOfTheEnd == null) |
|
514 return false; |
|
515 |
|
516 // Atomically append the chain at the tail of this collection |
|
517 for (Node<E> t = tail, p = t;;) { |
|
518 Node<E> q = p.next; |
|
519 if (q == null) { |
|
520 // p is last node |
|
521 if (p.casNext(null, beginningOfTheEnd)) { |
|
522 // Successful CAS is the linearization point |
|
523 // for all elements to be added to this queue. |
|
524 if (!casTail(t, last)) { |
|
525 // Try a little harder to update tail, |
|
526 // since we may be adding many elements. |
|
527 t = tail; |
|
528 if (last.next == null) |
|
529 casTail(t, last); |
|
530 } |
|
531 return true; |
|
532 } |
|
533 // Lost CAS race to another thread; re-read next |
|
534 } |
|
535 else if (p == q) |
|
536 // We have fallen off list. If tail is unchanged, it |
|
537 // will also be off-list, in which case we need to |
|
538 // jump to head, from which all live nodes are always |
|
539 // reachable. Else the new tail is a better bet. |
|
540 p = (t != (t = tail)) ? t : head; |
|
541 else |
|
542 // Check for tail updates after two hops. |
|
543 p = (p != t && t != (t = tail)) ? t : q; |
|
544 } |
|
545 } |
|
546 |
|
547 /** |
477 * Returns an array containing all of the elements in this queue, in |
548 * Returns an array containing all of the elements in this queue, in |
478 * proper sequence. |
549 * proper sequence. |
479 * |
550 * |
480 * <p>The returned array will be "safe" in that no references to it are |
551 * <p>The returned array will be "safe" in that no references to it are |
481 * maintained by this queue. (In other words, this method must allocate |
552 * maintained by this queue. (In other words, this method must allocate |
550 } |
621 } |
551 |
622 |
552 // If won't fit, use ArrayList version |
623 // If won't fit, use ArrayList version |
553 ArrayList<E> al = new ArrayList<E>(); |
624 ArrayList<E> al = new ArrayList<E>(); |
554 for (Node<E> q = first(); q != null; q = succ(q)) { |
625 for (Node<E> q = first(); q != null; q = succ(q)) { |
555 E item = q.getItem(); |
626 E item = q.item; |
556 if (item != null) |
627 if (item != null) |
557 al.add(item); |
628 al.add(item); |
558 } |
629 } |
559 return al.toArray(a); |
630 return al.toArray(a); |
560 } |
631 } |
561 |
632 |
562 /** |
633 /** |
563 * Returns an iterator over the elements in this queue in proper sequence. |
634 * Returns an iterator over the elements in this queue in proper sequence. |
564 * The returned iterator is a "weakly consistent" iterator that |
635 * The elements will be returned in order from first (head) to last (tail). |
|
636 * |
|
637 * <p>The returned {@code Iterator} is a "weakly consistent" iterator that |
565 * will never throw {@link java.util.ConcurrentModificationException |
638 * will never throw {@link java.util.ConcurrentModificationException |
566 * ConcurrentModificationException}, |
639 * ConcurrentModificationException}, |
567 * and guarantees to traverse elements as they existed upon |
640 * and guarantees to traverse elements as they existed upon |
568 * construction of the iterator, and may (but is not guaranteed to) |
641 * construction of the iterator, and may (but is not guaranteed to) |
569 * reflect any modifications subsequent to construction. |
642 * reflect any modifications subsequent to construction. |
646 |
719 |
647 public void remove() { |
720 public void remove() { |
648 Node<E> l = lastRet; |
721 Node<E> l = lastRet; |
649 if (l == null) throw new IllegalStateException(); |
722 if (l == null) throw new IllegalStateException(); |
650 // rely on a future traversal to relink. |
723 // rely on a future traversal to relink. |
651 l.setItem(null); |
724 l.item = null; |
652 lastRet = null; |
725 lastRet = null; |
653 } |
726 } |
654 } |
727 } |
655 |
728 |
656 /** |
729 /** |
657 * Save the state to a stream (that is, serialize it). |
730 * Saves the state to a stream (that is, serializes it). |
658 * |
731 * |
659 * @serialData All of the elements (each an {@code E}) in |
732 * @serialData All of the elements (each an {@code E}) in |
660 * the proper order, followed by a null |
733 * the proper order, followed by a null |
661 * @param s the stream |
734 * @param s the stream |
662 */ |
735 */ |
666 // Write out any hidden stuff |
739 // Write out any hidden stuff |
667 s.defaultWriteObject(); |
740 s.defaultWriteObject(); |
668 |
741 |
669 // Write out all elements in the proper order. |
742 // Write out all elements in the proper order. |
670 for (Node<E> p = first(); p != null; p = succ(p)) { |
743 for (Node<E> p = first(); p != null; p = succ(p)) { |
671 Object item = p.getItem(); |
744 Object item = p.item; |
672 if (item != null) |
745 if (item != null) |
673 s.writeObject(item); |
746 s.writeObject(item); |
674 } |
747 } |
675 |
748 |
676 // Use trailing null as sentinel |
749 // Use trailing null as sentinel |
677 s.writeObject(null); |
750 s.writeObject(null); |
678 } |
751 } |
679 |
752 |
680 /** |
753 /** |
681 * Reconstitute the Queue instance from a stream (that is, |
754 * Reconstitutes the instance from a stream (that is, deserializes it). |
682 * deserialize it). |
|
683 * @param s the stream |
755 * @param s the stream |
684 */ |
756 */ |
685 private void readObject(java.io.ObjectInputStream s) |
757 private void readObject(java.io.ObjectInputStream s) |
686 throws java.io.IOException, ClassNotFoundException { |
758 throws java.io.IOException, ClassNotFoundException { |
687 // Read in capacity, and any hidden stuff |
|
688 s.defaultReadObject(); |
759 s.defaultReadObject(); |
689 head = new Node<E>(null); |
760 |
690 tail = head; |
761 // Read in elements until trailing null sentinel found |
691 // Read in all elements and place in queue |
762 Node<E> h = null, t = null; |
692 for (;;) { |
763 Object item; |
|
764 while ((item = s.readObject()) != null) { |
693 @SuppressWarnings("unchecked") |
765 @SuppressWarnings("unchecked") |
694 E item = (E)s.readObject(); |
766 Node<E> newNode = new Node<E>((E) item); |
695 if (item == null) |
767 if (h == null) |
696 break; |
768 h = t = newNode; |
697 else |
769 else { |
698 offer(item); |
770 t.lazySetNext(newNode); |
699 } |
771 t = newNode; |
|
772 } |
|
773 } |
|
774 if (h == null) |
|
775 h = t = new Node<E>(null); |
|
776 head = h; |
|
777 tail = t; |
|
778 } |
|
779 |
|
780 /** |
|
781 * Throws NullPointerException if argument is null. |
|
782 * |
|
783 * @param v the element |
|
784 */ |
|
785 private static void checkNotNull(Object v) { |
|
786 if (v == null) |
|
787 throw new NullPointerException(); |
700 } |
788 } |
701 |
789 |
702 // Unsafe mechanics |
790 // Unsafe mechanics |
703 |
791 |
704 private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe(); |
792 private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe(); |
711 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); |
799 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); |
712 } |
800 } |
713 |
801 |
714 private boolean casHead(Node<E> cmp, Node<E> val) { |
802 private boolean casHead(Node<E> cmp, Node<E> val) { |
715 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); |
803 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); |
716 } |
|
717 |
|
718 private void lazySetHead(Node<E> val) { |
|
719 UNSAFE.putOrderedObject(this, headOffset, val); |
|
720 } |
804 } |
721 |
805 |
722 static long objectFieldOffset(sun.misc.Unsafe UNSAFE, |
806 static long objectFieldOffset(sun.misc.Unsafe UNSAFE, |
723 String field, Class<?> klazz) { |
807 String field, Class<?> klazz) { |
724 try { |
808 try { |