1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 28eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Written by Doug Lea and Martin Buchholz with assistance from members of 38eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * JCP JSR-166 Expert Group and released to the public domain, as explained 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * at http://creativecommons.org/publicdomain/zero/1.0/ 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent; 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 96232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.AbstractQueue; 106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.ArrayList; 116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Collection; 126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Iterator; 136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.NoSuchElementException; 146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Queue; 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// BEGIN android-note 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// removed link to collections framework docs 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// END android-note 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 21bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes. 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This queue orders elements FIFO (first-in-first-out). 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The <em>head</em> of the queue is that element that has been on the 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the longest time. 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The <em>tail</em> of the queue is that element that has been on the 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue the shortest time. New elements 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * are inserted at the tail of the queue, and the queue retrieval 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operations obtain elements at the head of the queue. 29bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * A {@code ConcurrentLinkedQueue} is an appropriate choice when 30adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * many threads will share access to a common collection. 318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Like most other concurrent collection implementations, this class 328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * does not permit the use of {@code null} elements. 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 34bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This implementation employs an efficient "wait-free" 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * algorithm based on one described in <a 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple, 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Fast, and Practical Non-Blocking and Blocking Concurrent Queue 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Algorithms</a> by Maged M. Michael and Michael L. Scott. 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Iterators are <i>weakly consistent</i>, returning elements 418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * reflecting the state of the queue at some point at or since the 428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * creation of the iterator. They do <em>not</em> throw {@link 438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * java.util.ConcurrentModificationException}, and may proceed concurrently 448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * with other operations. Elements contained in the queue since the creation 458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of the iterator will be returned exactly once. 468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 47bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Beware that, unlike in most collections, the {@code size} method 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is <em>NOT</em> a constant-time operation. Because of the 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * asynchronous nature of these queues, determining the current number 50a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of elements requires a traversal of the elements, and so may report 51a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * inaccurate results if this collection is modified during traversal. 52a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Additionally, the bulk operations {@code addAll}, 53a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code removeAll}, {@code retainAll}, {@code containsAll}, 54a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code equals}, and {@code toArray} are <em>not</em> guaranteed 55a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to be performed atomically. For example, an iterator operating 56a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * concurrently with an {@code addAll} operation might view only some 57a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of the added elements. 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>This class and its iterator implement all of the <em>optional</em> 608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * methods of the {@link Queue} and {@link Iterator} interfaces. 61bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 62bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Memory consistency effects: As with other concurrent 63bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * collections, actions in a thread prior to placing an object into a 64bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code ConcurrentLinkedQueue} 65bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 66bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * actions subsequent to the access or removal of that element from 67bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the {@code ConcurrentLinkedQueue} in another thread. 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param <E> the type of elements held in this collection 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class ConcurrentLinkedQueue<E> extends AbstractQueue<E> 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements Queue<E>, java.io.Serializable { 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 196745693267521676L; 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 79bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * This is a modification of the Michael & Scott algorithm, 80bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * adapted for a garbage-collected environment, with support for 81bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * interior node deletion (to support remove(Object)). For 82bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * explanation, read the paper. 83bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 84bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Note that like most non-blocking algorithms in this package, 85bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this implementation relies on the fact that in garbage 86bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * collected systems, there is no possibility of ABA problems due 87bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to recycled nodes, so there is no need to use "counted 88bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * pointers" or related techniques seen in versions used in 89bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * non-GC'ed settings. 90bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 91bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The fundamental invariants are: 92bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - There is exactly one (last) Node with a null next reference, 93bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * which is CASed when enqueueing. This last Node can be 94bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * reached in O(1) time from tail, but tail is merely an 95bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * optimization - it can always be reached in O(N) time from 96bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * head as well. 97bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - The elements contained in the queue are the non-null items in 98bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Nodes that are reachable from head. CASing the item 99bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * reference of a Node to null atomically removes it from the 100bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * queue. Reachability of all elements from head must remain 101bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * true even in the case of concurrent modifications that cause 102bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * head to advance. A dequeued Node may remain in use 103bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * indefinitely due to creation of an Iterator or simply a 104bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * poll() that has lost its time slice. 105bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 106bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The above might appear to imply that all Nodes are GC-reachable 107bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * from a predecessor dequeued Node. That would cause two problems: 108bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 109bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 110bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a Node was tenured while live, which generational GCs have a 111bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * hard time dealing with, causing repeated major collections. 112bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * However, only non-deleted Nodes need to be reachable from 113bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 114bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be of the kind understood by the GC. We use the trick of 115bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * linking a Node that has just been dequeued to itself. Such a 116bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * self-link implicitly means to advance to head. 117bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 118bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Both head and tail are permitted to lag. In fact, failing to 119bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * update them every time one could is a significant optimization 1208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (fewer CASes). As with LinkedTransferQueue (see the internal 1218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * documentation for that class), we use a slack threshold of two; 1228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * that is, we update head/tail when the current pointer appears 1238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * to be two or more steps away from the first/last node. 124bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 125bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Since head and tail are updated concurrently and independently, 126bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * it is possible for tail to lag behind head (why not)? 127bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 128bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CASing a Node's item reference to null atomically removes the 129bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * element from the queue. Iterators skip over Nodes with null 130bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * items. Prior implementations of this class had a race between 131bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * poll() and remove(Object) where the same element would appear 132bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to be successfully removed by two concurrent operations. The 133bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * method remove(Object) also lazily unlinks deleted Nodes, but 134bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this is merely an optimization. 135bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 136bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * When constructing a Node (before enqueuing it) we avoid paying 1378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * for a volatile write to item by using Unsafe.putObject instead 1388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of a normal write. This allows the cost of enqueue to be 139bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * "one-and-a-half" CASes. 140bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 141bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Both head and tail may or may not point to a Node with a 142bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * non-null item. If the queue is empty, all items must of course 143bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be null. Upon creation, both head and tail refer to a dummy 144bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Node with null item. Both head and tail are only updated using 145bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CAS, so they never regress, although again this is merely an 146bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * optimization. 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static class Node<E> { 1508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson volatile E item; 1518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson volatile Node<E> next; 152bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Constructs a new node. Uses relaxed write because item can 1558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * only be seen after publication via casNext. 1568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node(E item) { 1588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson UNSAFE.putObject(this, itemOffset, item); 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 160bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean casItem(E cmp, E val) { 1626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 164bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void lazySetNext(Node<E> val) { 1666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson UNSAFE.putOrderedObject(this, nextOffset, val); 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 168bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean casNext(Node<E> cmp, Node<E> val) { 1706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 172bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Unsafe mechanics 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final sun.misc.Unsafe UNSAFE; 176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long itemOffset; 177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long nextOffset; 178a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson UNSAFE = sun.misc.Unsafe.getUnsafe(); 182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Class<?> k = Node.class; 183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itemOffset = UNSAFE.objectFieldOffset 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("item")); 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextOffset = UNSAFE.objectFieldOffset 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("next")); 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } catch (Exception e) { 188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 191bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 192bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * A node from which the first live (non-deleted) node (if any) 1956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * can be reached in O(1) time. 1966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariants: 1976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - all live nodes are reachable from head via succ() 1986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - head != null 1996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - (tmp = head).next != tmp || tmp != head 2006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Non-invariants: 2016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - head.item may or may not be null. 2026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - it is permitted for tail to lag behind head, that is, for tail 2036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * to not be reachable from head! 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient volatile Node<E> head; 206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * A node from which the last node on list (that is, the unique 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * node with node.next == null) can be reached in O(1) time. 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariants: 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the last node is always reachable from tail via succ() 2126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - tail != null 2136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Non-invariants: 2146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - tail.item may or may not be null. 2156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - it is permitted for tail to lag behind head, that is, for tail 2166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * to not be reachable from head! 2176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - tail.next may or may not be self-pointing to tail. 2186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient volatile Node<E> tail; 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 223bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates a {@code ConcurrentLinkedQueue} that is initially empty. 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public ConcurrentLinkedQueue() { 2268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson head = tail = new Node<E>(null); 2278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 230bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates a {@code ConcurrentLinkedQueue} 231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * initially containing the elements of the given collection, 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 2338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 235bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 236bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ConcurrentLinkedQueue(Collection<? extends E> c) { 2398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> h = null, t = null; 2408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (E e : c) { 2418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 2428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> newNode = new Node<E>(e); 2438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 2448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = newNode; 2458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 2468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t.lazySetNext(newNode); 2478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t = newNode; 2488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 2518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = new Node<E>(null); 2528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson head = h; 2538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson tail = t; 254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 256bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Have to override just to update the javadoc 257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 258adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 259bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue. 2608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never throw 2618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@link IllegalStateException} or return {@code false}. 262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 263bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 264bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 266bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean add(E e) { 267bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return offer(e); 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 271bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Try to CAS head to p. If successful, repoint old head to itself 272bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * as sentinel for succ(), below. 273bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 274bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final void updateHead(Node<E> h, Node<E> p) { 275bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (h != p && casHead(h, p)) 2766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.lazySetNext(h); 277bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 278bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 279bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 280bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the successor of p, or the head node if p.next has been 281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * linked to self, which will only be true if traversing with a 282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * stale pointer that is now off the list. 283bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 284bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final Node<E> succ(Node<E> p) { 2858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> next = p.next; 286bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return (p == next) ? head : next; 287bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 288bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 289bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 290bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue. 2918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never return {@code false}. 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 293bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} (as specified by {@link Queue#offer}) 294bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 296bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 2978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 2988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Node<E> newNode = new Node<E>(e); 2998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> t = tail, p = t;;) { 3018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> q = p.next; 3028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (q == null) { 3038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // p is last node 3048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p.casNext(null, newNode)) { 3058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Successful CAS is the linearization point 3068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // for e to become an element of this queue, 3078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // and for newNode to become "live". 3088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p != t) // hop two nodes at a time 3098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casTail(t, newNode); // Failure is OK. 310bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return true; 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Lost CAS race to another thread; re-read next 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // We have fallen off list. If tail is unchanged, it 3168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // will also be off-list, in which case we need to 3178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // jump to head, from which all live nodes are always 3188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // reachable. Else the new tail is a better bet. 3198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (t != (t = tail)) ? t : head; 3208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Check for tail updates after two hops. 3228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (p != t && t != (t = tail)) ? t : q; 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 3278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson restartFromHead: 3288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 3298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> h = head, p = h, q;;) { 3308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 3318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (item != null && p.casItem(item, null)) { 3338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Successful CAS is the linearization point 3348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // for item to be removed from this queue. 3358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p != h) // hop two nodes at a time 3368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, ((q = p.next) != null) ? q : p); 3378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return item; 338adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if ((q = p.next) == null) { 3408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, p); 3418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return null; 3428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson continue restartFromHead; 3458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = q; 347bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 350adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 351bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public E peek() { 3528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson restartFromHead: 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 3548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> h = head, p = h, q;;) { 3558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 3568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (item != null || (q = p.next) == null) { 3578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, p); 3588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return item; 3598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson continue restartFromHead; 3628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = q; 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 3696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the first live (non-deleted) node on list, or null if none. 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * This is yet another variant of poll/peek; here returning the 3716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * first node, not element. We could make peek() a wrapper around 3726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * first(), but that would cost an extra volatile read of item, 3736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * and the need to add a retry loop to deal with the possibility 3746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * of losing a race to a concurrent poll(). 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> first() { 3778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson restartFromHead: 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 3798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> h = head, p = h, q;;) { 3808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson boolean hasItem = (p.item != null); 3818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (hasItem || (q = p.next) == null) { 3828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, p); 3838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return hasItem ? p : null; 3848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson continue restartFromHead; 3878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = q; 389bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 393bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 394bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contains no elements. 395bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 396bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this queue contains no elements 397bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isEmpty() { 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first() == null; 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. If this queue 404bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * contains more than {@code Integer.MAX_VALUE} elements, returns 405bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code Integer.MAX_VALUE}. 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Beware that, unlike in most collections, this method is 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>NOT</em> a constant-time operation. Because of the 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * asynchronous nature of these queues, determining the current 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * number of elements requires an O(n) traversal. 4118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Additionally, if elements are added or removed during execution 4128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of this method, the returned result may be inaccurate. Thus, 4138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * this method is typically not very useful in concurrent 4148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * applications. 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 416bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int count = 0; 4208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) 4218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p.item != null) 4228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Collection.size() spec says to max out 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (++count == Integer.MAX_VALUE) 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count; 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 428bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 429bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contains the specified element. 430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * More formally, returns {@code true} if and only if this queue contains 431bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 432bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 433bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o object to be checked for containment in this queue 434bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this queue contains the specified element 435bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object o) { 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 438bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 4398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 4408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (item != null && o.equals(item)) 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 446bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 447bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 448bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if it is present. More formally, removes an element {@code e} such 449bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 450bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 451bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contained the specified element 452bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 453bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 454bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 455bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this queue changed as a result of the call 456bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 459bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> pred = null; 460bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 4618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 4626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (item != null && 4636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson o.equals(item) && 4646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.casItem(item, null)) { 465bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> next = succ(p); 466bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (pred != null && next != null) 467bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred.casNext(p, next); 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 469bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 470bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred = p; 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 475bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 4768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Appends all of the elements in the specified collection to the end of 4778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * this queue, in the order that they are returned by the specified 4788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * collection's iterator. Attempts to {@code addAll} of a queue to 4798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * itself result in {@code IllegalArgumentException}. 4808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 4818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param c the elements to be inserted into this queue 4828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue changed as a result of the call 4838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws NullPointerException if the specified collection or any 4848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of its elements are null 4858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if the collection is this queue 4868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 4878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public boolean addAll(Collection<? extends E> c) { 4888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (c == this) 4898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // As historically specified in AbstractQueue#addAll 4908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new IllegalArgumentException(); 4918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 4928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Copy c into a private chain of Nodes 4938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> beginningOfTheEnd = null, last = null; 4948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (E e : c) { 4958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 4968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> newNode = new Node<E>(e); 4978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (beginningOfTheEnd == null) 4988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson beginningOfTheEnd = last = newNode; 4998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 5008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last.lazySetNext(newNode); 5018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = newNode; 5028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (beginningOfTheEnd == null) 5058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 5068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Atomically append the chain at the tail of this collection 5088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> t = tail, p = t;;) { 5098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> q = p.next; 5108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (q == null) { 5118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // p is last node 5128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p.casNext(null, beginningOfTheEnd)) { 5138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Successful CAS is the linearization point 5148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // for all elements to be added to this queue. 5158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (!casTail(t, last)) { 5168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Try a little harder to update tail, 5178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // since we may be adding many elements. 5188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t = tail; 5198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (last.next == null) 5208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casTail(t, last); 5218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 5238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Lost CAS race to another thread; re-read next 5258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 5278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // We have fallen off list. If tail is unchanged, it 5288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // will also be off-list, in which case we need to 5298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // jump to head, from which all live nodes are always 5308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // reachable. Else the new tail is a better bet. 5318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (t != (t = tail)) ? t : head; 5328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 5338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Check for tail updates after two hops. 5348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (p != t && t != (t = tail)) ? t : q; 5358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 539bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 540bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 541bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 542bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 543bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 544bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 545bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 546bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 547bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 548bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 549bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 550bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use ArrayList to deal with resizing. 553adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ArrayList<E> al = new ArrayList<E>(); 554bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 5558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project al.add(item); 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return al.toArray(); 560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 563bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 565bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 566bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 567bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 568bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 569bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 570bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 571bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 572bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code null}. 573bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 574bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 575bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 576bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 577bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 578bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 579bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 580bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 581bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * allocated array of {@code String}: 582bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 583a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 584bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 585bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 586bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code toArray()}. 587bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 588bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 589bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 590bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 591bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 592bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 593bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 594bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 595bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 596bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 597bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson @SuppressWarnings("unchecked") 598adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // try to use sent-in array 600adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> p; 602bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (p = first(); p != null && k < a.length; p = succ(p)) { 6038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = (T)item; 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == null) { 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (k < a.length) 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k] = null; 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 612adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // If won't fit, use ArrayList version 614adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ArrayList<E> al = new ArrayList<E>(); 615bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> q = first(); q != null; q = succ(q)) { 6168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = q.item; 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project al.add(item); 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 620bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return al.toArray(a); 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 6258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 6268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 6278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 6286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 6298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 6308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements as they existed upon construction of the iterator, and 6318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * may (but is not guaranteed to) reflect any modifications 6328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * subsequent to construction. 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 634bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new Itr(); 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 639adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 641adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Next node to return item for. 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> nextNode; 645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * nextItem holds on to item fields because once we claim 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * that an element exists in hasNext(), we must return it in 649adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the following next() call even if it was in the process of 650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * being removed when hasNext() was called. 651bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E nextItem; 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Node of the last returned item, to support remove. 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> lastRet; 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project advance(); 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Moves to next valid node and returns item to return for 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * next(), or null if no such. 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E advance() { 668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = nextNode; 669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = nextItem; 670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 671bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> pred, p; 672bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (nextNode == null) { 673bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson p = first(); 674bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred = null; 675bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 676bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred = nextNode; 677bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson p = succ(nextNode); 678bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 679bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == null) { 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextNode = null; 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextItem = null; 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 6868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) { 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextNode = p; 689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextItem = item; 690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 691bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 692bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // skip over nulls 693bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> next = succ(p); 694bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (pred != null && next != null) 695bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred.casNext(p, next); 696bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson p = next; 697bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 698adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 699adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 701adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return nextNode != null; 703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nextNode == null) throw new NoSuchElementException(); 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return advance(); 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> l = lastRet; 712adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (l == null) throw new IllegalStateException(); 713adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // rely on a future traversal to relink. 7148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson l.item = null; 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = null; 716adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 718adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 719adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 7208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Saves the state to a stream (that is, serializes it). 721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 722bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @serialData All of the elements (each an {@code E}) in 723adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the proper order, followed by a null 724adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param s the stream 725adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 727adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out any hidden stuff 730adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out all elements in the proper order. 733bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 7348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object item = p.item; 735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 736adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(item); 737adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 739adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use trailing null as sentinel 740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(null); 741adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 742adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 7448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Reconstitutes the instance from a stream (that is, deserializes it). 745adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param s the stream 746adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 747adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(java.io.ObjectInputStream s) 748adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException, ClassNotFoundException { 749adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultReadObject(); 7508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 7518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Read in elements until trailing null sentinel found 7528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> h = null, t = null; 7538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object item; 7548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while ((item = s.readObject()) != null) { 755bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson @SuppressWarnings("unchecked") 7568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> newNode = new Node<E>((E) item); 7578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 7588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = newNode; 7598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 7608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t.lazySetNext(newNode); 7618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t = newNode; 7628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 763adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 7648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 7658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = new Node<E>(null); 7668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson head = h; 7678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson tail = t; 7688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 7698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 7708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 7718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Throws NullPointerException if argument is null. 7728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 7738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param v the element 7748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 7758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static void checkNotNull(Object v) { 7768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (v == null) 7778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 778adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 779adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private boolean casTail(Node<E> cmp, Node<E> val) { 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private boolean casHead(Node<E> cmp, Node<E> val) { 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); 7866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 788a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Unsafe mechanics 789a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 790a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final sun.misc.Unsafe UNSAFE; 791a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long headOffset; 792a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long tailOffset; 793a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 7946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 795a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson UNSAFE = sun.misc.Unsafe.getUnsafe(); 796a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Class<?> k = ConcurrentLinkedQueue.class; 797a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson headOffset = UNSAFE.objectFieldOffset 798a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("head")); 799a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson tailOffset = UNSAFE.objectFieldOffset 800a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("tail")); 801a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } catch (Exception e) { 802a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 8036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 805adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 806