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 * java.util.ConcurrentModificationException}, and may proceed concurrently 69 * with 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 * As the queue is unbounded, this method will never throw 273 * {@link IllegalStateException} or return {@code false}. 274 * 275 * @return {@code true} (as specified by {@link Collection#add}) 276 * @throws NullPointerException if the specified element is null 277 */ 278 public boolean add(E e) { 279 return offer(e); 280 } 281 282 /** 283 * Try to CAS head to p. If successful, repoint old head to itself 284 * as sentinel for succ(), below. 285 */ 286 final void updateHead(Node<E> h, Node<E> p) { 287 if (h != p && casHead(h, p)) 288 h.lazySetNext(h); 289 } 290 291 /** 292 * Returns the successor of p, or the head node if p.next has been 293 * linked to self, which will only be true if traversing with a 294 * stale pointer that is now off the list. 295 */ 296 final Node<E> succ(Node<E> p) { 297 Node<E> next = p.next; 298 return (p == next) ? head : next; 299 } 300 301 /** 302 * Inserts the specified element at the tail of this queue. 303 * As the queue is unbounded, this method will never return {@code false}. 304 * 305 * @return {@code true} (as specified by {@link Queue#offer}) 306 * @throws NullPointerException if the specified element is null 307 */ 308 public boolean offer(E e) { 309 checkNotNull(e); 310 final Node<E> newNode = new Node<E>(e); 311 312 for (Node<E> t = tail, p = t;;) { 313 Node<E> q = p.next; 314 if (q == null) { 315 // p is last node 316 if (p.casNext(null, newNode)) { 317 // Successful CAS is the linearization point 318 // for e to become an element of this queue, 319 // and for newNode to become "live". 320 if (p != t) // hop two nodes at a time 321 casTail(t, newNode); // Failure is OK. 322 return true; 323 } 324 // Lost CAS race to another thread; re-read next 325 } 326 else if (p == q) 327 // We have fallen off list. If tail is unchanged, it 328 // will also be off-list, in which case we need to 329 // jump to head, from which all live nodes are always 330 // reachable. Else the new tail is a better bet. 331 p = (t != (t = tail)) ? t : head; 332 else 333 // Check for tail updates after two hops. 334 p = (p != t && t != (t = tail)) ? t : q; 335 } 336 } 337 338 public E poll() { 339 restartFromHead: 340 for (;;) { 341 for (Node<E> h = head, p = h, q;;) { 342 E item = p.item; 343 344 if (item != null && p.casItem(item, null)) { 345 // Successful CAS is the linearization point 346 // for item to be removed from this queue. 347 if (p != h) // hop two nodes at a time 348 updateHead(h, ((q = p.next) != null) ? q : p); 349 return item; 350 } 351 else if ((q = p.next) == null) { 352 updateHead(h, p); 353 return null; 354 } 355 else if (p == q) 356 continue restartFromHead; 357 else 358 p = q; 359 } 360 } 361 } 362 363 public E peek() { 364 restartFromHead: 365 for (;;) { 366 for (Node<E> h = head, p = h, q;;) { 367 E item = p.item; 368 if (item != null || (q = p.next) == null) { 369 updateHead(h, p); 370 return item; 371 } 372 else if (p == q) 373 continue restartFromHead; 374 else 375 p = q; 376 } 377 } 378 } 379 380 /** 381 * Returns the first live (non-deleted) node on list, or null if none. 382 * This is yet another variant of poll/peek; here returning the 383 * first node, not element. We could make peek() a wrapper around 384 * first(), but that would cost an extra volatile read of item, 385 * and the need to add a retry loop to deal with the possibility 386 * of losing a race to a concurrent poll(). 387 */ 388 Node<E> first() { 389 restartFromHead: 390 for (;;) { 391 for (Node<E> h = head, p = h, q;;) { 392 boolean hasItem = (p.item != null); 393 if (hasItem || (q = p.next) == null) { 394 updateHead(h, p); 395 return hasItem ? p : null; 396 } 397 else if (p == q) 398 continue restartFromHead; 399 else 400 p = q; 401 } 402 } 403 } 404 405 /** 406 * Returns {@code true} if this queue contains no elements. 407 * 408 * @return {@code true} if this queue contains no elements 409 */ 410 public boolean isEmpty() { 411 return first() == null; 412 } 413 414 /** 415 * Returns the number of elements in this queue. If this queue 416 * contains more than {@code Integer.MAX_VALUE} elements, returns 417 * {@code Integer.MAX_VALUE}. 418 * 419 * <p>Beware that, unlike in most collections, this method is 420 * <em>NOT</em> a constant-time operation. Because of the 421 * asynchronous nature of these queues, determining the current 422 * number of elements requires an O(n) traversal. 423 * Additionally, if elements are added or removed during execution 424 * of this method, the returned result may be inaccurate. Thus, 425 * this method is typically not very useful in concurrent 426 * applications. 427 * 428 * @return the number of elements in this queue 429 */ 430 public int size() { 431 int count = 0; 432 for (Node<E> p = first(); p != null; p = succ(p)) 433 if (p.item != null) 434 // Collection.size() spec says to max out 435 if (++count == Integer.MAX_VALUE) 436 break; 437 return count; 438 } 439 440 /** 441 * Returns {@code true} if this queue contains the specified element. 442 * More formally, returns {@code true} if and only if this queue contains 443 * at least one element {@code e} such that {@code o.equals(e)}. 444 * 445 * @param o object to be checked for containment in this queue 446 * @return {@code true} if this queue contains the specified element 447 */ 448 public boolean contains(Object o) { 449 if (o == null) return false; 450 for (Node<E> p = first(); p != null; p = succ(p)) { 451 E item = p.item; 452 if (item != null && o.equals(item)) 453 return true; 454 } 455 return false; 456 } 457 458 /** 459 * Removes a single instance of the specified element from this queue, 460 * if it is present. More formally, removes an element {@code e} such 461 * that {@code o.equals(e)}, if this queue contains one or more such 462 * elements. 463 * Returns {@code true} if this queue contained the specified element 464 * (or equivalently, if this queue changed as a result of the call). 465 * 466 * @param o element to be removed from this queue, if present 467 * @return {@code true} if this queue changed as a result of the call 468 */ 469 public boolean remove(Object o) { 470 if (o == null) return false; 471 Node<E> pred = null; 472 for (Node<E> p = first(); p != null; p = succ(p)) { 473 E item = p.item; 474 if (item != null && 475 o.equals(item) && 476 p.casItem(item, null)) { 477 Node<E> next = succ(p); 478 if (pred != null && next != null) 479 pred.casNext(p, next); 480 return true; 481 } 482 pred = p; 483 } 484 return false; 485 } 486 487 /** 488 * Appends all of the elements in the specified collection to the end of 489 * this queue, in the order that they are returned by the specified 490 * collection's iterator. Attempts to {@code addAll} of a queue to 491 * itself result in {@code IllegalArgumentException}. 492 * 493 * @param c the elements to be inserted into this queue 494 * @return {@code true} if this queue changed as a result of the call 495 * @throws NullPointerException if the specified collection or any 496 * of its elements are null 497 * @throws IllegalArgumentException if the collection is this queue 498 */ 499 public boolean addAll(Collection<? extends E> c) { 500 if (c == this) 501 // As historically specified in AbstractQueue#addAll 502 throw new IllegalArgumentException(); 503 504 // Copy c into a private chain of Nodes 505 Node<E> beginningOfTheEnd = null, last = null; 506 for (E e : c) { 507 checkNotNull(e); 508 Node<E> newNode = new Node<E>(e); 509 if (beginningOfTheEnd == null) 510 beginningOfTheEnd = last = newNode; 511 else { 512 last.lazySetNext(newNode); 513 last = newNode; 514 } 515 } 516 if (beginningOfTheEnd == null) 517 return false; 518 519 // Atomically append the chain at the tail of this collection 520 for (Node<E> t = tail, p = t;;) { 521 Node<E> q = p.next; 522 if (q == null) { 523 // p is last node 524 if (p.casNext(null, beginningOfTheEnd)) { 525 // Successful CAS is the linearization point 526 // for all elements to be added to this queue. 527 if (!casTail(t, last)) { 528 // Try a little harder to update tail, 529 // since we may be adding many elements. 530 t = tail; 531 if (last.next == null) 532 casTail(t, last); 533 } 534 return true; 535 } 536 // Lost CAS race to another thread; re-read next 537 } 538 else if (p == q) 539 // We have fallen off list. If tail is unchanged, it 540 // will also be off-list, in which case we need to 541 // jump to head, from which all live nodes are always 542 // reachable. Else the new tail is a better bet. 543 p = (t != (t = tail)) ? t : head; 544 else 545 // Check for tail updates after two hops. 546 p = (p != t && t != (t = tail)) ? t : q; 547 } 548 } 549 550 /** 551 * Returns an array containing all of the elements in this queue, in 552 * proper sequence. 553 * 554 * <p>The returned array will be "safe" in that no references to it are 555 * maintained by this queue. (In other words, this method must allocate 556 * a new array). The caller is thus free to modify the returned array. 557 * 558 * <p>This method acts as bridge between array-based and collection-based 559 * APIs. 560 * 561 * @return an array containing all of the elements in this queue 562 */ 563 public Object[] toArray() { 564 // Use ArrayList to deal with resizing. 565 ArrayList<E> al = new ArrayList<E>(); 566 for (Node<E> p = first(); p != null; p = succ(p)) { 567 E item = p.item; 568 if (item != null) 569 al.add(item); 570 } 571 return al.toArray(); 572 } 573 574 /** 575 * Returns an array containing all of the elements in this queue, in 576 * proper sequence; the runtime type of the returned array is that of 577 * the specified array. If the queue fits in the specified array, it 578 * is returned therein. Otherwise, a new array is allocated with the 579 * runtime type of the specified array and the size of this queue. 580 * 581 * <p>If this queue fits in the specified array with room to spare 582 * (i.e., the array has more elements than this queue), the element in 583 * the array immediately following the end of the queue is set to 584 * {@code null}. 585 * 586 * <p>Like the {@link #toArray()} method, this method acts as bridge between 587 * array-based and collection-based APIs. Further, this method allows 588 * precise control over the runtime type of the output array, and may, 589 * under certain circumstances, be used to save allocation costs. 590 * 591 * <p>Suppose {@code x} is a queue known to contain only strings. 592 * The following code can be used to dump the queue into a newly 593 * allocated array of {@code String}: 594 * 595 * <pre> 596 * String[] y = x.toArray(new String[0]);</pre> 597 * 598 * Note that {@code toArray(new Object[0])} is identical in function to 599 * {@code toArray()}. 600 * 601 * @param a the array into which the elements of the queue are to 602 * be stored, if it is big enough; otherwise, a new array of the 603 * same runtime type is allocated for this purpose 604 * @return an array containing all of the elements in this queue 605 * @throws ArrayStoreException if the runtime type of the specified array 606 * is not a supertype of the runtime type of every element in 607 * this queue 608 * @throws NullPointerException if the specified array is null 609 */ 610 @SuppressWarnings("unchecked") 611 public <T> T[] toArray(T[] a) { 612 // try to use sent-in array 613 int k = 0; 614 Node<E> p; 615 for (p = first(); p != null && k < a.length; p = succ(p)) { 616 E item = p.item; 617 if (item != null) 618 a[k++] = (T)item; 619 } 620 if (p == null) { 621 if (k < a.length) 622 a[k] = null; 623 return a; 624 } 625 626 // If won't fit, use ArrayList version 627 ArrayList<E> al = new ArrayList<E>(); 628 for (Node<E> q = first(); q != null; q = succ(q)) { 629 E item = q.item; 630 if (item != null) 631 al.add(item); 632 } 633 return al.toArray(a); 634 } 635 636 /** 637 * Returns an iterator over the elements in this queue in proper sequence. 638 * The elements will be returned in order from first (head) to last (tail). 639 * 640 * <p>The returned iterator is a "weakly consistent" iterator that 641 * will never throw {@link java.util.ConcurrentModificationException 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. 646 * 647 * @return an iterator over the elements in this queue in proper sequence 648 */ 649 public Iterator<E> iterator() { 650 return new Itr(); 651 } 652 653 private class Itr implements Iterator<E> { 654 /** 655 * Next node to return item for. 656 */ 657 private Node<E> nextNode; 658 659 /** 660 * nextItem holds on to item fields because once we claim 661 * that an element exists in hasNext(), we must return it in 662 * the following next() call even if it was in the process of 663 * being removed when hasNext() was called. 664 */ 665 private E nextItem; 666 667 /** 668 * Node of the last returned item, to support remove. 669 */ 670 private Node<E> lastRet; 671 672 Itr() { 673 advance(); 674 } 675 676 /** 677 * Moves to next valid node and returns item to return for 678 * next(), or null if no such. 679 */ 680 private E advance() { 681 lastRet = nextNode; 682 E x = nextItem; 683 684 Node<E> pred, p; 685 if (nextNode == null) { 686 p = first(); 687 pred = null; 688 } else { 689 pred = nextNode; 690 p = succ(nextNode); 691 } 692 693 for (;;) { 694 if (p == null) { 695 nextNode = null; 696 nextItem = null; 697 return x; 698 } 699 E item = p.item; 700 if (item != null) { 701 nextNode = p; 702 nextItem = item; 703 return x; 704 } else { 705 // skip over nulls 706 Node<E> next = succ(p); 707 if (pred != null && next != null) 708 pred.casNext(p, next); 709 p = next; 710 } 711 } 712 } 713 714 public boolean hasNext() { 715 return nextNode != null; 716 } 717 718 public E next() { 719 if (nextNode == null) throw new NoSuchElementException(); 720 return advance(); 721 } 722 723 public void remove() { 724 Node<E> l = lastRet; 725 if (l == null) throw new IllegalStateException(); 726 // rely on a future traversal to relink. 727 l.item = null; 728 lastRet = null; 729 } 730 } 731 732 /** 733 * Saves the state to a stream (that is, serializes it). 734 * 735 * @serialData All of the elements (each an {@code E}) in 736 * the proper order, followed by a null 737 * @param s the stream 738 */ 739 private void writeObject(java.io.ObjectOutputStream s) 740 throws java.io.IOException { 741 742 // Write out any hidden stuff 743 s.defaultWriteObject(); 744 745 // Write out all elements in the proper order. 746 for (Node<E> p = first(); p != null; p = succ(p)) { 747 Object item = p.item; 748 if (item != null) 749 s.writeObject(item); 750 } 751 752 // Use trailing null as sentinel 753 s.writeObject(null); 754 } 755 756 /** 757 * Reconstitutes the instance from a stream (that is, deserializes it). 758 * @param s the stream 759 */ 760 private void readObject(java.io.ObjectInputStream s) 761 throws java.io.IOException, ClassNotFoundException { 762 s.defaultReadObject(); 763 764 // Read in elements until trailing null sentinel found 765 Node<E> h = null, t = null; 766 Object item; 767 while ((item = s.readObject()) != null) { 768 @SuppressWarnings("unchecked") 769 Node<E> newNode = new Node<E>((E) item); 770 if (h == null) 771 h = t = newNode; 772 else { 773 t.lazySetNext(newNode); 774 t = newNode; 775 } 776 } 777 if (h == null) 778 h = t = new Node<E>(null); 779 head = h; 780 tail = t; 781 } 782 783 /** 784 * Throws NullPointerException if argument is null. 785 * 786 * @param v the element 787 */ 788 private static void checkNotNull(Object v) { 789 if (v == null) 790 throw new NullPointerException(); 791 } 792 793 // Unsafe mechanics 794 795 private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe(); 796 private static final long headOffset = 797 objectFieldOffset(UNSAFE, "head", ConcurrentLinkedQueue.class); 798 private static final long tailOffset = 799 objectFieldOffset(UNSAFE, "tail", ConcurrentLinkedQueue.class); 800 801 private boolean casTail(Node<E> cmp, Node<E> val) { 802 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); 803 } 804 805 private boolean casHead(Node<E> cmp, Node<E> val) { 806 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); 807 } 808 809 static long objectFieldOffset(sun.misc.Unsafe UNSAFE, 810 String field, Class<?> klazz) { 811 try { 812 return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field)); 813 } catch (NoSuchFieldException e) { 814 // Convert Exception to corresponding Error 815 NoSuchFieldError error = new NoSuchFieldError(field); 816 error.initCause(e); 817 throw error; 818 } 819 } 820 }