Print this page
Split |
Close |
Expand all |
Collapse all |
--- old/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java
+++ new/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java
1 1 /*
2 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 3 *
4 4 * This code is free software; you can redistribute it and/or modify it
5 5 * under the terms of the GNU General Public License version 2 only, as
6 6 * published by the Free Software Foundation. Oracle designates this
7 7 * particular file as subject to the "Classpath" exception as provided
8 8 * by Oracle in the LICENSE file that accompanied this code.
9 9 *
10 10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 13 * version 2 for more details (a copy is included in the LICENSE file that
14 14 * accompanied this code).
15 15 *
16 16 * You should have received a copy of the GNU General Public License version
17 17 * 2 along with this work; if not, write to the Free Software Foundation,
18 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 19 *
20 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 21 * or visit www.oracle.com if you need additional information or have any
22 22 * questions.
23 23 */
24 24
25 25 /*
26 26 * This file is available under and governed by the GNU General Public
27 27 * License version 2 only, as published by the Free Software Foundation.
28 28 * However, the following notice accompanied the original version of this
29 29 * file:
30 30 *
31 31 * Written by Doug Lea and Martin Buchholz with assistance from members of
32 32 * JCP JSR-166 Expert Group and released to the public domain, as explained
33 33 * at http://creativecommons.org/licenses/publicdomain
34 34 */
35 35
36 36 package java.util.concurrent;
37 37
38 38 import java.util.AbstractQueue;
39 39 import java.util.ArrayList;
40 40 import java.util.Collection;
41 41 import java.util.Iterator;
42 42 import java.util.NoSuchElementException;
43 43 import java.util.Queue;
44 44
45 45 /**
46 46 * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.
47 47 * This queue orders elements FIFO (first-in-first-out).
48 48 * The <em>head</em> of the queue is that element that has been on the
49 49 * queue the longest time.
50 50 * The <em>tail</em> of the queue is that element that has been on the
51 51 * queue the shortest time. New elements
52 52 * are inserted at the tail of the queue, and the queue retrieval
53 53 * operations obtain elements at the head of the queue.
54 54 * A {@code ConcurrentLinkedQueue} is an appropriate choice when
55 55 * many threads will share access to a common collection.
56 56 * Like most other concurrent collection implementations, this class
57 57 * does not permit the use of {@code null} elements.
↓ open down ↓ |
57 lines elided |
↑ open up ↑ |
58 58 *
59 59 * <p>This implementation employs an efficient "wait-free"
60 60 * algorithm based on one described in <a
61 61 * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
62 62 * Fast, and Practical Non-Blocking and Blocking Concurrent Queue
63 63 * Algorithms</a> by Maged M. Michael and Michael L. Scott.
64 64 *
65 65 * <p>Iterators are <i>weakly consistent</i>, returning elements
66 66 * reflecting the state of the queue at some point at or since the
67 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
68 + * java.util.ConcurrentModificationException}, and may proceed concurrently
69 + * with other operations. Elements contained in the queue since the creation
70 70 * of the iterator will be returned exactly once.
71 71 *
72 72 * <p>Beware that, unlike in most collections, the {@code size} method
73 73 * is <em>NOT</em> a constant-time operation. Because of the
74 74 * asynchronous nature of these queues, determining the current number
75 75 * of elements requires a traversal of the elements.
76 76 *
77 77 * <p>This class and its iterator implement all of the <em>optional</em>
78 78 * methods of the {@link Queue} and {@link Iterator} interfaces.
79 79 *
80 80 * <p>Memory consistency effects: As with other concurrent
81 81 * collections, actions in a thread prior to placing an object into a
82 82 * {@code ConcurrentLinkedQueue}
83 83 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
84 84 * actions subsequent to the access or removal of that element from
85 85 * the {@code ConcurrentLinkedQueue} in another thread.
86 86 *
87 87 * <p>This class is a member of the
88 88 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
89 89 * Java Collections Framework</a>.
90 90 *
91 91 * @since 1.5
92 92 * @author Doug Lea
93 93 * @param <E> the type of elements held in this collection
94 94 *
95 95 */
96 96 public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
97 97 implements Queue<E>, java.io.Serializable {
98 98 private static final long serialVersionUID = 196745693267521676L;
99 99
100 100 /*
101 101 * This is a modification of the Michael & Scott algorithm,
102 102 * adapted for a garbage-collected environment, with support for
103 103 * interior node deletion (to support remove(Object)). For
104 104 * explanation, read the paper.
105 105 *
106 106 * Note that like most non-blocking algorithms in this package,
107 107 * this implementation relies on the fact that in garbage
108 108 * collected systems, there is no possibility of ABA problems due
109 109 * to recycled nodes, so there is no need to use "counted
110 110 * pointers" or related techniques seen in versions used in
111 111 * non-GC'ed settings.
112 112 *
113 113 * The fundamental invariants are:
114 114 * - There is exactly one (last) Node with a null next reference,
115 115 * which is CASed when enqueueing. This last Node can be
116 116 * reached in O(1) time from tail, but tail is merely an
117 117 * optimization - it can always be reached in O(N) time from
118 118 * head as well.
119 119 * - The elements contained in the queue are the non-null items in
120 120 * Nodes that are reachable from head. CASing the item
121 121 * reference of a Node to null atomically removes it from the
122 122 * queue. Reachability of all elements from head must remain
123 123 * true even in the case of concurrent modifications that cause
124 124 * head to advance. A dequeued Node may remain in use
125 125 * indefinitely due to creation of an Iterator or simply a
126 126 * poll() that has lost its time slice.
127 127 *
128 128 * The above might appear to imply that all Nodes are GC-reachable
129 129 * from a predecessor dequeued Node. That would cause two problems:
130 130 * - allow a rogue Iterator to cause unbounded memory retention
131 131 * - cause cross-generational linking of old Nodes to new Nodes if
132 132 * a Node was tenured while live, which generational GCs have a
133 133 * hard time dealing with, causing repeated major collections.
134 134 * However, only non-deleted Nodes need to be reachable from
135 135 * dequeued Nodes, and reachability does not necessarily have to
136 136 * be of the kind understood by the GC. We use the trick of
137 137 * linking a Node that has just been dequeued to itself. Such a
138 138 * self-link implicitly means to advance to head.
139 139 *
140 140 * Both head and tail are permitted to lag. In fact, failing to
141 141 * update them every time one could is a significant optimization
142 142 * (fewer CASes). As with LinkedTransferQueue (see the internal
143 143 * documentation for that class), we use a slack threshold of two;
144 144 * that is, we update head/tail when the current pointer appears
145 145 * to be two or more steps away from the first/last node.
146 146 *
147 147 * Since head and tail are updated concurrently and independently,
148 148 * it is possible for tail to lag behind head (why not)?
149 149 *
150 150 * CASing a Node's item reference to null atomically removes the
151 151 * element from the queue. Iterators skip over Nodes with null
152 152 * items. Prior implementations of this class had a race between
153 153 * poll() and remove(Object) where the same element would appear
154 154 * to be successfully removed by two concurrent operations. The
155 155 * method remove(Object) also lazily unlinks deleted Nodes, but
156 156 * this is merely an optimization.
157 157 *
158 158 * When constructing a Node (before enqueuing it) we avoid paying
159 159 * for a volatile write to item by using Unsafe.putObject instead
160 160 * of a normal write. This allows the cost of enqueue to be
161 161 * "one-and-a-half" CASes.
162 162 *
163 163 * Both head and tail may or may not point to a Node with a
164 164 * non-null item. If the queue is empty, all items must of course
165 165 * be null. Upon creation, both head and tail refer to a dummy
166 166 * Node with null item. Both head and tail are only updated using
167 167 * CAS, so they never regress, although again this is merely an
168 168 * optimization.
169 169 */
170 170
171 171 private static class Node<E> {
172 172 volatile E item;
173 173 volatile Node<E> next;
174 174
175 175 /**
176 176 * Constructs a new node. Uses relaxed write because item can
177 177 * only be seen after publication via casNext.
178 178 */
179 179 Node(E item) {
180 180 UNSAFE.putObject(this, itemOffset, item);
181 181 }
182 182
183 183 boolean casItem(E cmp, E val) {
184 184 return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
185 185 }
186 186
187 187 void lazySetNext(Node<E> val) {
188 188 UNSAFE.putOrderedObject(this, nextOffset, val);
189 189 }
190 190
191 191 boolean casNext(Node<E> cmp, Node<E> val) {
192 192 return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
193 193 }
194 194
195 195 // Unsafe mechanics
196 196
197 197 private static final sun.misc.Unsafe UNSAFE =
198 198 sun.misc.Unsafe.getUnsafe();
199 199 private static final long nextOffset =
200 200 objectFieldOffset(UNSAFE, "next", Node.class);
201 201 private static final long itemOffset =
202 202 objectFieldOffset(UNSAFE, "item", Node.class);
203 203 }
204 204
205 205 /**
206 206 * A node from which the first live (non-deleted) node (if any)
207 207 * can be reached in O(1) time.
208 208 * Invariants:
209 209 * - all live nodes are reachable from head via succ()
210 210 * - head != null
211 211 * - (tmp = head).next != tmp || tmp != head
212 212 * Non-invariants:
213 213 * - head.item may or may not be null.
214 214 * - it is permitted for tail to lag behind head, that is, for tail
215 215 * to not be reachable from head!
216 216 */
217 217 private transient volatile Node<E> head;
218 218
219 219 /**
220 220 * A node from which the last node on list (that is, the unique
221 221 * node with node.next == null) can be reached in O(1) time.
222 222 * Invariants:
223 223 * - the last node is always reachable from tail via succ()
224 224 * - tail != null
225 225 * Non-invariants:
226 226 * - tail.item may or may not be null.
227 227 * - it is permitted for tail to lag behind head, that is, for tail
228 228 * to not be reachable from head!
229 229 * - tail.next may or may not be self-pointing to tail.
230 230 */
231 231 private transient volatile Node<E> tail;
232 232
233 233
234 234 /**
235 235 * Creates a {@code ConcurrentLinkedQueue} that is initially empty.
236 236 */
237 237 public ConcurrentLinkedQueue() {
238 238 head = tail = new Node<E>(null);
239 239 }
240 240
241 241 /**
242 242 * Creates a {@code ConcurrentLinkedQueue}
243 243 * initially containing the elements of the given collection,
244 244 * added in traversal order of the collection's iterator.
245 245 *
246 246 * @param c the collection of elements to initially contain
247 247 * @throws NullPointerException if the specified collection or any
248 248 * of its elements are null
249 249 */
250 250 public ConcurrentLinkedQueue(Collection<? extends E> c) {
251 251 Node<E> h = null, t = null;
252 252 for (E e : c) {
253 253 checkNotNull(e);
254 254 Node<E> newNode = new Node<E>(e);
255 255 if (h == null)
256 256 h = t = newNode;
257 257 else {
258 258 t.lazySetNext(newNode);
259 259 t = newNode;
260 260 }
261 261 }
↓ open down ↓ |
182 lines elided |
↑ open up ↑ |
262 262 if (h == null)
263 263 h = t = new Node<E>(null);
264 264 head = h;
265 265 tail = t;
266 266 }
267 267
268 268 // Have to override just to update the javadoc
269 269
270 270 /**
271 271 * Inserts the specified element at the tail of this queue.
272 + * As the queue is unbounded, this method will never throw
273 + * {@link IllegalStateException} or return {@code false}.
272 274 *
273 275 * @return {@code true} (as specified by {@link Collection#add})
274 276 * @throws NullPointerException if the specified element is null
275 277 */
276 278 public boolean add(E e) {
277 279 return offer(e);
278 280 }
279 281
280 282 /**
281 283 * Try to CAS head to p. If successful, repoint old head to itself
282 284 * as sentinel for succ(), below.
283 285 */
284 286 final void updateHead(Node<E> h, Node<E> p) {
285 287 if (h != p && casHead(h, p))
286 288 h.lazySetNext(h);
287 289 }
288 290
289 291 /**
290 292 * Returns the successor of p, or the head node if p.next has been
↓ open down ↓ |
9 lines elided |
↑ open up ↑ |
291 293 * linked to self, which will only be true if traversing with a
292 294 * stale pointer that is now off the list.
293 295 */
294 296 final Node<E> succ(Node<E> p) {
295 297 Node<E> next = p.next;
296 298 return (p == next) ? head : next;
297 299 }
298 300
299 301 /**
300 302 * Inserts the specified element at the tail of this queue.
303 + * As the queue is unbounded, this method will never return {@code false}.
301 304 *
302 305 * @return {@code true} (as specified by {@link Queue#offer})
303 306 * @throws NullPointerException if the specified element is null
304 307 */
305 308 public boolean offer(E e) {
306 309 checkNotNull(e);
307 310 final Node<E> newNode = new Node<E>(e);
308 311
309 312 for (Node<E> t = tail, p = t;;) {
310 313 Node<E> q = p.next;
311 314 if (q == null) {
312 315 // p is last node
313 316 if (p.casNext(null, newNode)) {
314 317 // Successful CAS is the linearization point
315 318 // for e to become an element of this queue,
316 319 // and for newNode to become "live".
317 320 if (p != t) // hop two nodes at a time
318 321 casTail(t, newNode); // Failure is OK.
319 322 return true;
320 323 }
321 324 // Lost CAS race to another thread; re-read next
322 325 }
323 326 else if (p == q)
324 327 // We have fallen off list. If tail is unchanged, it
325 328 // will also be off-list, in which case we need to
326 329 // jump to head, from which all live nodes are always
327 330 // reachable. Else the new tail is a better bet.
328 331 p = (t != (t = tail)) ? t : head;
329 332 else
330 333 // Check for tail updates after two hops.
331 334 p = (p != t && t != (t = tail)) ? t : q;
332 335 }
333 336 }
334 337
335 338 public E poll() {
336 339 restartFromHead:
337 340 for (;;) {
338 341 for (Node<E> h = head, p = h, q;;) {
339 342 E item = p.item;
340 343
341 344 if (item != null && p.casItem(item, null)) {
342 345 // Successful CAS is the linearization point
343 346 // for item to be removed from this queue.
344 347 if (p != h) // hop two nodes at a time
345 348 updateHead(h, ((q = p.next) != null) ? q : p);
346 349 return item;
347 350 }
348 351 else if ((q = p.next) == null) {
349 352 updateHead(h, p);
350 353 return null;
351 354 }
352 355 else if (p == q)
353 356 continue restartFromHead;
354 357 else
355 358 p = q;
356 359 }
357 360 }
358 361 }
359 362
360 363 public E peek() {
361 364 restartFromHead:
362 365 for (;;) {
363 366 for (Node<E> h = head, p = h, q;;) {
364 367 E item = p.item;
365 368 if (item != null || (q = p.next) == null) {
366 369 updateHead(h, p);
367 370 return item;
368 371 }
369 372 else if (p == q)
370 373 continue restartFromHead;
371 374 else
372 375 p = q;
373 376 }
374 377 }
375 378 }
376 379
377 380 /**
378 381 * Returns the first live (non-deleted) node on list, or null if none.
379 382 * This is yet another variant of poll/peek; here returning the
380 383 * first node, not element. We could make peek() a wrapper around
381 384 * first(), but that would cost an extra volatile read of item,
382 385 * and the need to add a retry loop to deal with the possibility
383 386 * of losing a race to a concurrent poll().
384 387 */
385 388 Node<E> first() {
386 389 restartFromHead:
387 390 for (;;) {
388 391 for (Node<E> h = head, p = h, q;;) {
389 392 boolean hasItem = (p.item != null);
390 393 if (hasItem || (q = p.next) == null) {
391 394 updateHead(h, p);
392 395 return hasItem ? p : null;
393 396 }
394 397 else if (p == q)
395 398 continue restartFromHead;
396 399 else
397 400 p = q;
398 401 }
399 402 }
400 403 }
401 404
402 405 /**
403 406 * Returns {@code true} if this queue contains no elements.
404 407 *
405 408 * @return {@code true} if this queue contains no elements
406 409 */
407 410 public boolean isEmpty() {
408 411 return first() == null;
409 412 }
410 413
411 414 /**
412 415 * Returns the number of elements in this queue. If this queue
413 416 * contains more than {@code Integer.MAX_VALUE} elements, returns
414 417 * {@code Integer.MAX_VALUE}.
415 418 *
416 419 * <p>Beware that, unlike in most collections, this method is
417 420 * <em>NOT</em> a constant-time operation. Because of the
418 421 * asynchronous nature of these queues, determining the current
419 422 * number of elements requires an O(n) traversal.
420 423 * Additionally, if elements are added or removed during execution
421 424 * of this method, the returned result may be inaccurate. Thus,
422 425 * this method is typically not very useful in concurrent
423 426 * applications.
424 427 *
425 428 * @return the number of elements in this queue
426 429 */
427 430 public int size() {
428 431 int count = 0;
429 432 for (Node<E> p = first(); p != null; p = succ(p))
430 433 if (p.item != null)
431 434 // Collection.size() spec says to max out
432 435 if (++count == Integer.MAX_VALUE)
433 436 break;
434 437 return count;
435 438 }
436 439
437 440 /**
438 441 * Returns {@code true} if this queue contains the specified element.
439 442 * More formally, returns {@code true} if and only if this queue contains
440 443 * at least one element {@code e} such that {@code o.equals(e)}.
441 444 *
442 445 * @param o object to be checked for containment in this queue
443 446 * @return {@code true} if this queue contains the specified element
444 447 */
445 448 public boolean contains(Object o) {
446 449 if (o == null) return false;
447 450 for (Node<E> p = first(); p != null; p = succ(p)) {
448 451 E item = p.item;
449 452 if (item != null && o.equals(item))
450 453 return true;
451 454 }
452 455 return false;
453 456 }
454 457
455 458 /**
456 459 * Removes a single instance of the specified element from this queue,
457 460 * if it is present. More formally, removes an element {@code e} such
458 461 * that {@code o.equals(e)}, if this queue contains one or more such
459 462 * elements.
460 463 * Returns {@code true} if this queue contained the specified element
461 464 * (or equivalently, if this queue changed as a result of the call).
462 465 *
463 466 * @param o element to be removed from this queue, if present
464 467 * @return {@code true} if this queue changed as a result of the call
465 468 */
466 469 public boolean remove(Object o) {
467 470 if (o == null) return false;
468 471 Node<E> pred = null;
469 472 for (Node<E> p = first(); p != null; p = succ(p)) {
470 473 E item = p.item;
471 474 if (item != null &&
472 475 o.equals(item) &&
473 476 p.casItem(item, null)) {
474 477 Node<E> next = succ(p);
475 478 if (pred != null && next != null)
476 479 pred.casNext(p, next);
477 480 return true;
478 481 }
479 482 pred = p;
480 483 }
481 484 return false;
482 485 }
483 486
484 487 /**
485 488 * Appends all of the elements in the specified collection to the end of
486 489 * this queue, in the order that they are returned by the specified
487 490 * collection's iterator. Attempts to {@code addAll} of a queue to
488 491 * itself result in {@code IllegalArgumentException}.
489 492 *
490 493 * @param c the elements to be inserted into this queue
491 494 * @return {@code true} if this queue changed as a result of the call
492 495 * @throws NullPointerException if the specified collection or any
493 496 * of its elements are null
494 497 * @throws IllegalArgumentException if the collection is this queue
495 498 */
496 499 public boolean addAll(Collection<? extends E> c) {
497 500 if (c == this)
498 501 // As historically specified in AbstractQueue#addAll
499 502 throw new IllegalArgumentException();
500 503
501 504 // Copy c into a private chain of Nodes
502 505 Node<E> beginningOfTheEnd = null, last = null;
503 506 for (E e : c) {
504 507 checkNotNull(e);
505 508 Node<E> newNode = new Node<E>(e);
506 509 if (beginningOfTheEnd == null)
507 510 beginningOfTheEnd = last = newNode;
508 511 else {
509 512 last.lazySetNext(newNode);
510 513 last = newNode;
511 514 }
512 515 }
513 516 if (beginningOfTheEnd == null)
514 517 return false;
515 518
516 519 // Atomically append the chain at the tail of this collection
517 520 for (Node<E> t = tail, p = t;;) {
518 521 Node<E> q = p.next;
519 522 if (q == null) {
520 523 // p is last node
521 524 if (p.casNext(null, beginningOfTheEnd)) {
522 525 // Successful CAS is the linearization point
523 526 // for all elements to be added to this queue.
524 527 if (!casTail(t, last)) {
525 528 // Try a little harder to update tail,
526 529 // since we may be adding many elements.
527 530 t = tail;
528 531 if (last.next == null)
529 532 casTail(t, last);
530 533 }
531 534 return true;
532 535 }
533 536 // Lost CAS race to another thread; re-read next
534 537 }
535 538 else if (p == q)
536 539 // We have fallen off list. If tail is unchanged, it
537 540 // will also be off-list, in which case we need to
538 541 // jump to head, from which all live nodes are always
539 542 // reachable. Else the new tail is a better bet.
540 543 p = (t != (t = tail)) ? t : head;
541 544 else
542 545 // Check for tail updates after two hops.
543 546 p = (p != t && t != (t = tail)) ? t : q;
544 547 }
545 548 }
546 549
547 550 /**
548 551 * Returns an array containing all of the elements in this queue, in
549 552 * proper sequence.
550 553 *
551 554 * <p>The returned array will be "safe" in that no references to it are
552 555 * maintained by this queue. (In other words, this method must allocate
553 556 * a new array). The caller is thus free to modify the returned array.
554 557 *
555 558 * <p>This method acts as bridge between array-based and collection-based
556 559 * APIs.
557 560 *
558 561 * @return an array containing all of the elements in this queue
559 562 */
560 563 public Object[] toArray() {
561 564 // Use ArrayList to deal with resizing.
562 565 ArrayList<E> al = new ArrayList<E>();
563 566 for (Node<E> p = first(); p != null; p = succ(p)) {
564 567 E item = p.item;
565 568 if (item != null)
566 569 al.add(item);
567 570 }
568 571 return al.toArray();
569 572 }
570 573
571 574 /**
572 575 * Returns an array containing all of the elements in this queue, in
573 576 * proper sequence; the runtime type of the returned array is that of
574 577 * the specified array. If the queue fits in the specified array, it
575 578 * is returned therein. Otherwise, a new array is allocated with the
576 579 * runtime type of the specified array and the size of this queue.
577 580 *
578 581 * <p>If this queue fits in the specified array with room to spare
579 582 * (i.e., the array has more elements than this queue), the element in
580 583 * the array immediately following the end of the queue is set to
581 584 * {@code null}.
582 585 *
583 586 * <p>Like the {@link #toArray()} method, this method acts as bridge between
584 587 * array-based and collection-based APIs. Further, this method allows
585 588 * precise control over the runtime type of the output array, and may,
586 589 * under certain circumstances, be used to save allocation costs.
587 590 *
588 591 * <p>Suppose {@code x} is a queue known to contain only strings.
589 592 * The following code can be used to dump the queue into a newly
590 593 * allocated array of {@code String}:
591 594 *
592 595 * <pre>
593 596 * String[] y = x.toArray(new String[0]);</pre>
594 597 *
595 598 * Note that {@code toArray(new Object[0])} is identical in function to
596 599 * {@code toArray()}.
597 600 *
598 601 * @param a the array into which the elements of the queue are to
599 602 * be stored, if it is big enough; otherwise, a new array of the
600 603 * same runtime type is allocated for this purpose
601 604 * @return an array containing all of the elements in this queue
602 605 * @throws ArrayStoreException if the runtime type of the specified array
603 606 * is not a supertype of the runtime type of every element in
604 607 * this queue
605 608 * @throws NullPointerException if the specified array is null
606 609 */
607 610 @SuppressWarnings("unchecked")
608 611 public <T> T[] toArray(T[] a) {
609 612 // try to use sent-in array
610 613 int k = 0;
611 614 Node<E> p;
612 615 for (p = first(); p != null && k < a.length; p = succ(p)) {
613 616 E item = p.item;
614 617 if (item != null)
615 618 a[k++] = (T)item;
616 619 }
617 620 if (p == null) {
618 621 if (k < a.length)
619 622 a[k] = null;
620 623 return a;
621 624 }
622 625
623 626 // If won't fit, use ArrayList version
624 627 ArrayList<E> al = new ArrayList<E>();
625 628 for (Node<E> q = first(); q != null; q = succ(q)) {
626 629 E item = q.item;
↓ open down ↓ |
316 lines elided |
↑ open up ↑ |
627 630 if (item != null)
628 631 al.add(item);
629 632 }
630 633 return al.toArray(a);
631 634 }
632 635
633 636 /**
634 637 * Returns an iterator over the elements in this queue in proper sequence.
635 638 * The elements will be returned in order from first (head) to last (tail).
636 639 *
637 - * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
640 + * <p>The returned iterator is a "weakly consistent" iterator that
638 641 * will never throw {@link java.util.ConcurrentModificationException
639 - * ConcurrentModificationException},
640 - * and guarantees to traverse elements as they existed upon
641 - * construction of the iterator, and may (but is not guaranteed to)
642 - * reflect any modifications subsequent to construction.
642 + * ConcurrentModificationException}, and guarantees to traverse
643 + * elements as they existed upon construction of the iterator, and
644 + * may (but is not guaranteed to) reflect any modifications
645 + * subsequent to construction.
643 646 *
644 647 * @return an iterator over the elements in this queue in proper sequence
645 648 */
646 649 public Iterator<E> iterator() {
647 650 return new Itr();
648 651 }
649 652
650 653 private class Itr implements Iterator<E> {
651 654 /**
652 655 * Next node to return item for.
653 656 */
654 657 private Node<E> nextNode;
655 658
656 659 /**
657 660 * nextItem holds on to item fields because once we claim
658 661 * that an element exists in hasNext(), we must return it in
659 662 * the following next() call even if it was in the process of
660 663 * being removed when hasNext() was called.
661 664 */
662 665 private E nextItem;
663 666
664 667 /**
665 668 * Node of the last returned item, to support remove.
666 669 */
667 670 private Node<E> lastRet;
668 671
669 672 Itr() {
670 673 advance();
671 674 }
672 675
673 676 /**
674 677 * Moves to next valid node and returns item to return for
675 678 * next(), or null if no such.
676 679 */
677 680 private E advance() {
678 681 lastRet = nextNode;
679 682 E x = nextItem;
680 683
681 684 Node<E> pred, p;
682 685 if (nextNode == null) {
683 686 p = first();
684 687 pred = null;
685 688 } else {
686 689 pred = nextNode;
687 690 p = succ(nextNode);
688 691 }
689 692
690 693 for (;;) {
691 694 if (p == null) {
692 695 nextNode = null;
693 696 nextItem = null;
694 697 return x;
695 698 }
696 699 E item = p.item;
697 700 if (item != null) {
698 701 nextNode = p;
699 702 nextItem = item;
700 703 return x;
701 704 } else {
702 705 // skip over nulls
703 706 Node<E> next = succ(p);
704 707 if (pred != null && next != null)
705 708 pred.casNext(p, next);
706 709 p = next;
707 710 }
708 711 }
709 712 }
710 713
711 714 public boolean hasNext() {
712 715 return nextNode != null;
713 716 }
714 717
715 718 public E next() {
716 719 if (nextNode == null) throw new NoSuchElementException();
717 720 return advance();
718 721 }
719 722
720 723 public void remove() {
721 724 Node<E> l = lastRet;
722 725 if (l == null) throw new IllegalStateException();
723 726 // rely on a future traversal to relink.
724 727 l.item = null;
725 728 lastRet = null;
726 729 }
727 730 }
728 731
729 732 /**
730 733 * Saves the state to a stream (that is, serializes it).
731 734 *
732 735 * @serialData All of the elements (each an {@code E}) in
733 736 * the proper order, followed by a null
734 737 * @param s the stream
735 738 */
736 739 private void writeObject(java.io.ObjectOutputStream s)
737 740 throws java.io.IOException {
738 741
739 742 // Write out any hidden stuff
740 743 s.defaultWriteObject();
741 744
742 745 // Write out all elements in the proper order.
743 746 for (Node<E> p = first(); p != null; p = succ(p)) {
744 747 Object item = p.item;
745 748 if (item != null)
746 749 s.writeObject(item);
747 750 }
748 751
749 752 // Use trailing null as sentinel
750 753 s.writeObject(null);
751 754 }
752 755
753 756 /**
754 757 * Reconstitutes the instance from a stream (that is, deserializes it).
755 758 * @param s the stream
756 759 */
757 760 private void readObject(java.io.ObjectInputStream s)
758 761 throws java.io.IOException, ClassNotFoundException {
759 762 s.defaultReadObject();
760 763
761 764 // Read in elements until trailing null sentinel found
762 765 Node<E> h = null, t = null;
763 766 Object item;
764 767 while ((item = s.readObject()) != null) {
765 768 @SuppressWarnings("unchecked")
766 769 Node<E> newNode = new Node<E>((E) item);
767 770 if (h == null)
768 771 h = t = newNode;
769 772 else {
770 773 t.lazySetNext(newNode);
771 774 t = newNode;
772 775 }
773 776 }
774 777 if (h == null)
775 778 h = t = new Node<E>(null);
776 779 head = h;
777 780 tail = t;
778 781 }
779 782
780 783 /**
781 784 * Throws NullPointerException if argument is null.
782 785 *
783 786 * @param v the element
784 787 */
785 788 private static void checkNotNull(Object v) {
786 789 if (v == null)
787 790 throw new NullPointerException();
788 791 }
789 792
790 793 // Unsafe mechanics
791 794
792 795 private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
793 796 private static final long headOffset =
794 797 objectFieldOffset(UNSAFE, "head", ConcurrentLinkedQueue.class);
795 798 private static final long tailOffset =
796 799 objectFieldOffset(UNSAFE, "tail", ConcurrentLinkedQueue.class);
797 800
798 801 private boolean casTail(Node<E> cmp, Node<E> val) {
799 802 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
800 803 }
801 804
802 805 private boolean casHead(Node<E> cmp, Node<E> val) {
803 806 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
804 807 }
805 808
806 809 static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
807 810 String field, Class<?> klazz) {
808 811 try {
809 812 return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
810 813 } catch (NoSuchFieldException e) {
811 814 // Convert Exception to corresponding Error
812 815 NoSuchFieldError error = new NoSuchFieldError(field);
813 816 error.initCause(e);
814 817 throw error;
815 818 }
816 819 }
817 820 }
↓ open down ↓ |
165 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX