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