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 * 3475a06e56a4cc4599946e21422513e4bafa759509Calin Juravle * <p>This implementation employs an efficient <em>non-blocking</em> 35edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * algorithm based on one described in 36edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * <a href="http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf"> 37edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * Simple, 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 Projectpublic class ConcurrentLinkedQueue<E> extends AbstractQueue<E> 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements Queue<E>, java.io.Serializable { 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 196745693267521676L; 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 78bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * This is a modification of the Michael & Scott algorithm, 79bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * adapted for a garbage-collected environment, with support for 80bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * interior node deletion (to support remove(Object)). For 81bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * explanation, read the paper. 82bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 83bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Note that like most non-blocking algorithms in this package, 84bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this implementation relies on the fact that in garbage 85bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * collected systems, there is no possibility of ABA problems due 86bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to recycled nodes, so there is no need to use "counted 87bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * pointers" or related techniques seen in versions used in 88bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * non-GC'ed settings. 89bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 90bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The fundamental invariants are: 91bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - There is exactly one (last) Node with a null next reference, 92bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * which is CASed when enqueueing. This last Node can be 93bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * reached in O(1) time from tail, but tail is merely an 94bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * optimization - it can always be reached in O(N) time from 95bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * head as well. 96bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - The elements contained in the queue are the non-null items in 97bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Nodes that are reachable from head. CASing the item 98bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * reference of a Node to null atomically removes it from the 99bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * queue. Reachability of all elements from head must remain 100bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * true even in the case of concurrent modifications that cause 101bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * head to advance. A dequeued Node may remain in use 102bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * indefinitely due to creation of an Iterator or simply a 103bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * poll() that has lost its time slice. 104bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 105bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The above might appear to imply that all Nodes are GC-reachable 106bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * from a predecessor dequeued Node. That would cause two problems: 107bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 108bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 109bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a Node was tenured while live, which generational GCs have a 110bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * hard time dealing with, causing repeated major collections. 111bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * However, only non-deleted Nodes need to be reachable from 112bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 113bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be of the kind understood by the GC. We use the trick of 114bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * linking a Node that has just been dequeued to itself. Such a 115bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * self-link implicitly means to advance to head. 116bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 117bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Both head and tail are permitted to lag. In fact, failing to 118bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * update them every time one could is a significant optimization 1198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (fewer CASes). As with LinkedTransferQueue (see the internal 1208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * documentation for that class), we use a slack threshold of two; 1218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * that is, we update head/tail when the current pointer appears 1228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * to be two or more steps away from the first/last node. 123bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 124bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Since head and tail are updated concurrently and independently, 125bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * it is possible for tail to lag behind head (why not)? 126bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 127bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CASing a Node's item reference to null atomically removes the 128bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * element from the queue. Iterators skip over Nodes with null 129bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * items. Prior implementations of this class had a race between 130bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * poll() and remove(Object) where the same element would appear 131bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to be successfully removed by two concurrent operations. The 132bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * method remove(Object) also lazily unlinks deleted Nodes, but 133bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this is merely an optimization. 134bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 135bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * When constructing a Node (before enqueuing it) we avoid paying 1368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * for a volatile write to item by using Unsafe.putObject instead 1378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of a normal write. This allows the cost of enqueue to be 138bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * "one-and-a-half" CASes. 139bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 140bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Both head and tail may or may not point to a Node with a 141bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * non-null item. If the queue is empty, all items must of course 142bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be null. Upon creation, both head and tail refer to a dummy 143bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Node with null item. Both head and tail are only updated using 144bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CAS, so they never regress, although again this is merely an 145bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * optimization. 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static class Node<E> { 1498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson volatile E item; 1508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson volatile Node<E> next; 151bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Constructs a new node. Uses relaxed write because item can 1548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * only be seen after publication via casNext. 1558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node(E item) { 1578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson UNSAFE.putObject(this, itemOffset, item); 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 159bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean casItem(E cmp, E val) { 1616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 163bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void lazySetNext(Node<E> val) { 1656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson UNSAFE.putOrderedObject(this, nextOffset, val); 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 167bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean casNext(Node<E> cmp, Node<E> val) { 1696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 171bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Unsafe mechanics 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final sun.misc.Unsafe UNSAFE; 175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long itemOffset; 176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long nextOffset; 177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 178a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson UNSAFE = sun.misc.Unsafe.getUnsafe(); 181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Class<?> k = Node.class; 182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson itemOffset = UNSAFE.objectFieldOffset 183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("item")); 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextOffset = UNSAFE.objectFieldOffset 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("next")); 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } catch (Exception e) { 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 190bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 191bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * A node from which the first live (non-deleted) node (if any) 1946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * can be reached in O(1) time. 1956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariants: 1966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - all live nodes are reachable from head via succ() 1976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - head != null 1986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - (tmp = head).next != tmp || tmp != head 1996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Non-invariants: 2006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - head.item may or may not be null. 2016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - it is permitted for tail to lag behind head, that is, for tail 2026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * to not be reachable from head! 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient volatile Node<E> head; 205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * A node from which the last node on list (that is, the unique 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * node with node.next == null) can be reached in O(1) time. 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariants: 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the last node is always reachable from tail via succ() 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - tail != null 2126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Non-invariants: 2136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - tail.item may or may not be null. 2146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - it is permitted for tail to lag behind head, that is, for tail 2156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * to not be reachable from head! 2166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - tail.next may or may not be self-pointing to tail. 2176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient volatile Node<E> tail; 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 221bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates a {@code ConcurrentLinkedQueue} that is initially empty. 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public ConcurrentLinkedQueue() { 2248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson head = tail = new Node<E>(null); 2258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 228bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates a {@code ConcurrentLinkedQueue} 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * initially containing the elements of the given collection, 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * added in traversal order of the collection's iterator. 2318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param c the collection of elements to initially contain 233bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 234bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 236adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ConcurrentLinkedQueue(Collection<? extends E> c) { 2378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> h = null, t = null; 2388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (E e : c) { 2398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 2408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> newNode = new Node<E>(e); 2418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 2428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = newNode; 2438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 2448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t.lazySetNext(newNode); 2458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t = newNode; 2468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 2498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = new Node<E>(null); 2508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson head = h; 2518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson tail = t; 252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 254bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Have to override just to update the javadoc 255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 256adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 257bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue. 2588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never throw 2598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@link IllegalStateException} or return {@code false}. 260adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 261bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 262bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 264bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean add(E e) { 265bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return offer(e); 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 26991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Tries to CAS head to p. If successful, repoint old head to itself 270bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * as sentinel for succ(), below. 271bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 272bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final void updateHead(Node<E> h, Node<E> p) { 273bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (h != p && casHead(h, p)) 2746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson h.lazySetNext(h); 275bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 276bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 277bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 278bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the successor of p, or the head node if p.next has been 279bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * linked to self, which will only be true if traversing with a 280bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * stale pointer that is now off the list. 281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final Node<E> succ(Node<E> p) { 2838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> next = p.next; 284bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return (p == next) ? head : next; 285bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 286bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 287bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 288bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element at the tail of this queue. 2898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never return {@code false}. 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 291bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} (as specified by {@link Queue#offer}) 292bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 294bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 2958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 2968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final Node<E> newNode = new Node<E>(e); 2978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 2988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> t = tail, p = t;;) { 2998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> q = p.next; 3008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (q == null) { 3018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // p is last node 3028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p.casNext(null, newNode)) { 3038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Successful CAS is the linearization point 3048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // for e to become an element of this queue, 3058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // and for newNode to become "live". 3068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p != t) // hop two nodes at a time 3078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casTail(t, newNode); // Failure is OK. 308bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return true; 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Lost CAS race to another thread; re-read next 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // We have fallen off list. If tail is unchanged, it 3148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // will also be off-list, in which case we need to 3158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // jump to head, from which all live nodes are always 3168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // reachable. Else the new tail is a better bet. 3178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (t != (t = tail)) ? t : head; 3188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Check for tail updates after two hops. 3208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (p != t && t != (t = tail)) ? t : q; 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll() { 3258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson restartFromHead: 3268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 3278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> h = head, p = h, q;;) { 3288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 3298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (item != null && p.casItem(item, null)) { 3318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Successful CAS is the linearization point 3328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // for item to be removed from this queue. 3338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p != h) // hop two nodes at a time 3348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, ((q = p.next) != null) ? q : p); 3358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return item; 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 3378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if ((q = p.next) == null) { 3388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, p); 3398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return null; 3408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson continue restartFromHead; 3438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = q; 345bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 349bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public E peek() { 3508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson restartFromHead: 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 3528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> h = head, p = h, q;;) { 3538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 3548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (item != null || (q = p.next) == null) { 3558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, p); 3568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return item; 3578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson continue restartFromHead; 3608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = q; 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 3676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the first live (non-deleted) node on list, or null if none. 3686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * This is yet another variant of poll/peek; here returning the 3696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * first node, not element. We could make peek() a wrapper around 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * first(), but that would cost an extra volatile read of item, 3716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * and the need to add a retry loop to deal with the possibility 3726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * of losing a race to a concurrent poll(). 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> first() { 3758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson restartFromHead: 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 3778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> h = head, p = h, q;;) { 3788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson boolean hasItem = (p.item != null); 3798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (hasItem || (q = p.next) == null) { 3808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson updateHead(h, p); 3818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return hasItem ? p : null; 3828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 3848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson continue restartFromHead; 3858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = q; 387bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 391bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 392bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contains no elements. 393bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 394bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this queue contains no elements 395bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isEmpty() { 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return first() == null; 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this queue. If this queue 402bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * contains more than {@code Integer.MAX_VALUE} elements, returns 403bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code Integer.MAX_VALUE}. 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Beware that, unlike in most collections, this method is 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>NOT</em> a constant-time operation. Because of the 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * asynchronous nature of these queues, determining the current 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * number of elements requires an O(n) traversal. 4098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Additionally, if elements are added or removed during execution 4108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of this method, the returned result may be inaccurate. Thus, 4118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * this method is typically not very useful in concurrent 4128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * applications. 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 414bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the number of elements in this queue 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int count = 0; 4188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) 4198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p.item != null) 4208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Collection.size() spec says to max out 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (++count == Integer.MAX_VALUE) 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return count; 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 426bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 427bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contains the specified element. 428bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * More formally, returns {@code true} if and only if this queue contains 429bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 431bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o object to be checked for containment in this queue 432bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this queue contains the specified element 433bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object o) { 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 436bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 4378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 4388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (item != null && o.equals(item)) 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 440adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 444bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 445bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 446bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if it is present. More formally, removes an element {@code e} such 447bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 448bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. 449bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contained the specified element 450bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or equivalently, if this queue changed as a result of the call). 451bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 452bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 453bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this queue changed as a result of the call 454bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (o == null) return false; 457bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> pred = null; 458bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 4598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 4606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (item != null && 4616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson o.equals(item) && 4626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.casItem(item, null)) { 463bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> next = succ(p); 464bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (pred != null && next != null) 465bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred.casNext(p, next); 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 467bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 468bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred = p; 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 473bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 4748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Appends all of the elements in the specified collection to the end of 4758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * this queue, in the order that they are returned by the specified 4768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * collection's iterator. Attempts to {@code addAll} of a queue to 4778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * itself result in {@code IllegalArgumentException}. 4788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 4798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param c the elements to be inserted into this queue 4808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue changed as a result of the call 4818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws NullPointerException if the specified collection or any 4828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of its elements are null 4838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if the collection is this queue 4848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 4858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public boolean addAll(Collection<? extends E> c) { 4868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (c == this) 4878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // As historically specified in AbstractQueue#addAll 4888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new IllegalArgumentException(); 4898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 4908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Copy c into a private chain of Nodes 4918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> beginningOfTheEnd = null, last = null; 4928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (E e : c) { 4938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson checkNotNull(e); 4948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> newNode = new Node<E>(e); 4958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (beginningOfTheEnd == null) 4968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson beginningOfTheEnd = last = newNode; 4978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 4988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last.lazySetNext(newNode); 4998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = newNode; 5008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (beginningOfTheEnd == null) 5038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return false; 5048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Atomically append the chain at the tail of this collection 5068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (Node<E> t = tail, p = t;;) { 5078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> q = p.next; 5088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (q == null) { 5098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // p is last node 5108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p.casNext(null, beginningOfTheEnd)) { 5118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Successful CAS is the linearization point 5128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // for all elements to be added to this queue. 5138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (!casTail(t, last)) { 5148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Try a little harder to update tail, 5158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // since we may be adding many elements. 5168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t = tail; 5178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (last.next == null) 5188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casTail(t, last); 5198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 5218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Lost CAS race to another thread; re-read next 5238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (p == q) 5258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // We have fallen off list. If tail is unchanged, it 5268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // will also be off-list, in which case we need to 5278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // jump to head, from which all live nodes are always 5288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // reachable. Else the new tail is a better bet. 5298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (t != (t = tail)) ? t : head; 5308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 5318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Check for tail updates after two hops. 5328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = (p != t && t != (t = tail)) ? t : q; 5338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 537bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 538bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence. 539bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 540bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The returned array will be "safe" in that no references to it are 541bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * maintained by this queue. (In other words, this method must allocate 542bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new array). The caller is thus free to modify the returned array. 543bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 544bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method acts as bridge between array-based and collection-based 545bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * APIs. 546bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 547bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 548bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Object[] toArray() { 550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use ArrayList to deal with resizing. 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ArrayList<E> al = new ArrayList<E>(); 552bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 5538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project al.add(item); 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return al.toArray(); 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue, in 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * proper sequence; the runtime type of the returned array is that of 563bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified array. If the queue fits in the specified array, it 564bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 565bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the specified array and the size of this queue. 566bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 567bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 568bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 569bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 570bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code null}. 571bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 572bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 573bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 574bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 575bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 576bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 577bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 578bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 579bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * allocated array of {@code String}: 580bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 581a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 582bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 583bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 584bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code toArray()}. 585bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 586bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 587bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 588bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 589bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 590bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 591bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 592bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 593bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 594bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 595bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson @SuppressWarnings("unchecked") 596adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 597adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // try to use sent-in array 598adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int k = 0; 599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> p; 600bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (p = first(); p != null && k < a.length; p = succ(p)) { 6018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 603adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k++] = (T)item; 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == null) { 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (k < a.length) 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[k] = null; 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return a; 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // If won't fit, use ArrayList version 612adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ArrayList<E> al = new ArrayList<E>(); 613bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> q = first(); q != null; q = succ(q)) { 6148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = q.item; 615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project al.add(item); 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 618bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return al.toArray(a); 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue in proper sequence. 6238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The elements will be returned in order from first (head) to last (tail). 6248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 6258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 6266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 6278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 6288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements as they existed upon construction of the iterator, and 6298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * may (but is not guaranteed to) reflect any modifications 6308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * subsequent to construction. 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 632bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue in proper sequence 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new Itr(); 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private class Itr implements Iterator<E> { 639adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Next node to return item for. 641adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> nextNode; 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * nextItem holds on to item fields because once we claim 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * that an element exists in hasNext(), we must return it in 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the following next() call even if it was in the process of 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * being removed when hasNext() was called. 649bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E nextItem; 651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Node of the last returned item, to support remove. 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node<E> lastRet; 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Itr() { 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project advance(); 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Moves to next valid node and returns item to return for 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * next(), or null if no such. 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private E advance() { 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = nextNode; 667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project E x = nextItem; 668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 669bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> pred, p; 670bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (nextNode == null) { 671bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson p = first(); 672bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred = null; 673bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 674bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred = nextNode; 675bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson p = succ(nextNode); 676bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 677bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 679adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == null) { 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextNode = null; 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextItem = null; 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 6848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E item = p.item; 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) { 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextNode = p; 687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextItem = item; 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return x; 689bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 690bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // skip over nulls 691bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node<E> next = succ(p); 692bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (pred != null && next != null) 693bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred.casNext(p, next); 694bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson p = next; 695bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 698adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 699adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return nextNode != null; 701adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nextNode == null) throw new NoSuchElementException(); 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return advance(); 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node<E> l = lastRet; 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (l == null) throw new IllegalStateException(); 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // rely on a future traversal to relink. 7128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson l.item = null; 713adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastRet = null; 714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 716adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 71891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Saves this queue to a stream (that is, serializes it). 719adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 720bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @serialData All of the elements (each an {@code E}) in 721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the proper order, followed by a null 722adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 723adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 724adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 725adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out any hidden stuff 727adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Write out all elements in the proper order. 730bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (Node<E> p = first(); p != null; p = succ(p)) { 7318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object item = p.item; 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (item != null) 733adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(item); 734adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 736adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Use trailing null as sentinel 737adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.writeObject(null); 738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 739adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 74191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Reconstitutes this queue from a stream (that is, deserializes it). 742adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(java.io.ObjectInputStream s) 744adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException, ClassNotFoundException { 745adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultReadObject(); 7468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 7478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Read in elements until trailing null sentinel found 7488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> h = null, t = null; 7498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object item; 7508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while ((item = s.readObject()) != null) { 751bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson @SuppressWarnings("unchecked") 7528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> newNode = new Node<E>((E) item); 7538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 7548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = newNode; 7558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 7568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t.lazySetNext(newNode); 7578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson t = newNode; 7588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 759adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 7608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (h == null) 7618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson h = t = new Node<E>(null); 7628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson head = h; 7638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson tail = t; 7648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 7658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 7668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 7678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Throws NullPointerException if argument is null. 7688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 7698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param v the element 7708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 7718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static void checkNotNull(Object v) { 7728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (v == null) 7738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 774adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 775adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private boolean casTail(Node<E> cmp, Node<E> val) { 7776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); 7786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private boolean casHead(Node<E> cmp, Node<E> val) { 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 784a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Unsafe mechanics 785a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 786a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final sun.misc.Unsafe UNSAFE; 787a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long headOffset; 788a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long tailOffset; 789a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 7906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 791a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson UNSAFE = sun.misc.Unsafe.getUnsafe(); 792a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Class<?> k = ConcurrentLinkedQueue.class; 793a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson headOffset = UNSAFE.objectFieldOffset 794a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("head")); 795a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson tailOffset = UNSAFE.objectFieldOffset 796a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (k.getDeclaredField("tail")); 797a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } catch (Exception e) { 798a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 7996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 801adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 802