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