1a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson/* 229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is free software; you can redistribute it and/or modify it 529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * published by the Free Software Foundation. Oracle designates this 729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * particular file as subject to the "Classpath" exception as provided 829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 1129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 1429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * accompanied this code). 1529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * You should have received a copy of the GNU General Public License version 1729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 1829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * or visit www.oracle.com if you need additional information or have any 2229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * questions. 2329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer */ 2429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer 2529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer/* 2629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This file is available under and governed by the GNU General Public 2729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 2829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * However, the following notice accompanied the original version of this 2929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * file: 3029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 31a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 32a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Expert Group and released to the public domain, as explained at 33a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 34a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 35a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 36a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonpackage java.util.concurrent; 37a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 38a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.AbstractQueue; 39b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Arrays; 40a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Collection; 41a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Iterator; 42a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.NoSuchElementException; 43a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.Queue; 44b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Spliterator; 45b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Spliterators; 46a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.concurrent.locks.LockSupport; 47b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.Consumer; 48a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 49a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// BEGIN android-note 50a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// removed link to collections framework docs 51a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// END android-note 52a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 53a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson/** 54a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * An unbounded {@link TransferQueue} based on linked nodes. 55a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * This queue orders elements FIFO (first-in-first-out) with respect 56a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to any given producer. The <em>head</em> of the queue is that 57a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * element that has been on the queue the longest time for some 58a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * producer. The <em>tail</em> of the queue is that element that has 59a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * been on the queue the shortest time for some producer. 60a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 61a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>Beware that, unlike in most collections, the {@code size} method 62a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * is <em>NOT</em> a constant-time operation. Because of the 63a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * asynchronous nature of these queues, determining the current number 64a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of elements requires a traversal of the elements, and so may report 65a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * inaccurate results if this collection is modified during traversal. 66a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Additionally, the bulk operations {@code addAll}, 67a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code removeAll}, {@code retainAll}, {@code containsAll}, 68a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code equals}, and {@code toArray} are <em>not</em> guaranteed 69a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to be performed atomically. For example, an iterator operating 70a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * concurrently with an {@code addAll} operation might view only some 71a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of the added elements. 72a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 73a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>This class and its iterator implement all of the 74a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 75a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Iterator} interfaces. 76a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 77a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>Memory consistency effects: As with other concurrent 78a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * collections, actions in a thread prior to placing an object into a 79a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code LinkedTransferQueue} 80a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 81a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * actions subsequent to the access or removal of that element from 82a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the {@code LinkedTransferQueue} in another thread. 83a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 84a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @since 1.7 85a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @author Doug Lea 86b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param <E> the type of elements held in this queue 87a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 88a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonpublic class LinkedTransferQueue<E> extends AbstractQueue<E> 89a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson implements TransferQueue<E>, java.io.Serializable { 90a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long serialVersionUID = -3223113410248163686L; 91a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 92a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* 93a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * *** Overview of Dual Queues with Slack *** 94a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 95a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Dual Queues, introduced by Scherer and Scott 96a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (http://www.cs.rice.edu/~wns1/papers/2004-DISC-DDS.pdf) are 97a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (linked) queues in which nodes may represent either data or 98a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * requests. When a thread tries to enqueue a data node, but 99a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * encounters a request node, it instead "matches" and removes it; 100a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and vice versa for enqueuing requests. Blocking Dual Queues 101a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * arrange that threads enqueuing unmatched requests block until 102a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * other threads provide the match. Dual Synchronous Queues (see 103a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Scherer, Lea, & Scott 104a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://www.cs.rochester.edu/u/scott/papers/2009_Scherer_CACM_SSQ.pdf) 105a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * additionally arrange that threads enqueuing unmatched data also 106a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * block. Dual Transfer Queues support all of these modes, as 107a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * dictated by callers. 108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * A FIFO dual queue may be implemented using a variation of the 110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Michael & Scott (M&S) lock-free queue algorithm 111edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * (http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf). 112a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * It maintains two pointer fields, "head", pointing to a 113a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (matched) node that in turn points to the first actual 114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (unmatched) queue node (or null if empty); and "tail" that 115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * points to the last node on the queue (or again null if 116a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * empty). For example, here is a possible queue with four data 117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * elements: 118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 119a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * head tail 120a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * | | 121a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * v v 122a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * M -> U -> U -> U -> U 123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The M&S queue algorithm is known to be prone to scalability and 125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * overhead limitations when maintaining (via CAS) these head and 126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * tail pointers. This has led to the development of 127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * contention-reducing variants such as elimination arrays (see 128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Moir et al http://portal.acm.org/citation.cfm?id=1074013) and 129a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * optimistic back pointers (see Ladan-Mozes & Shavit 130a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf). 131a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * However, the nature of dual queues enables a simpler tactic for 132a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * improving M&S-style implementations when dual-ness is needed. 133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * In a dual queue, each node must atomically maintain its match 135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * status. While there are other possible variants, we implement 136a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this here as: for a data-mode node, matching entails CASing an 137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * "item" field from a non-null data value to null upon match, and 138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * vice-versa for request nodes, CASing from null to a data 139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * value. (Note that the linearization properties of this style of 140a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * queue are easy to verify -- elements are made available by 141a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * linking, and unavailable by matching.) Compared to plain M&S 142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * queues, this property of dual queues requires one additional 143a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * successful atomic operation per enq/deq pair. But it also 144a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * enables lower cost variants of queue maintenance mechanics. (A 145a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * variation of this idea applies even for non-dual queues that 146a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * support deletion of interior elements, such as 147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * j.u.c.ConcurrentLinkedQueue.) 148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 149a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Once a node is matched, its match status can never again 150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * change. We may thus arrange that the linked list of them 151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * contain a prefix of zero or more matched nodes, followed by a 152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * suffix of zero or more unmatched nodes. (Note that we allow 153a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * both the prefix and suffix to be zero length, which in turn 154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * means that we do not use a dummy header.) If we were not 155a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * concerned with either time or space efficiency, we could 156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * correctly perform enqueue and dequeue operations by traversing 157a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * from a pointer to the initial node; CASing the item of the 158a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * first unmatched node on match and CASing the next field of the 159a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * trailing node on appends. (Plus some special-casing when 160a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * initially empty). While this would be a terrible idea in 161a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * itself, it does have the benefit of not requiring ANY atomic 162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * updates on head/tail fields. 163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We introduce here an approach that lies between the extremes of 165a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * never versus always updating queue (head and tail) pointers. 166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * This offers a tradeoff between sometimes requiring extra 167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * traversal steps to locate the first and/or last unmatched 168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nodes, versus the reduced overhead and contention of fewer 169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * updates to queue pointers. For example, a possible snapshot of 170a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * a queue is: 171a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * head tail 173a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * | | 174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * v v 175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * M -> M -> U -> U -> U -> U 176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The best value for this "slack" (the targeted maximum distance 178a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * between the value of "head" and the first unmatched node, and 179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * similarly for "tail") is an empirical matter. We have found 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that using very small constants in the range of 1-3 work best 181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * over a range of platforms. Larger values introduce increasing 182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * costs of cache misses and risks of long traversal chains, while 183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * smaller values increase CAS contention and overhead. 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Dual queues with slack differ from plain M&S dual queues by 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * virtue of only sometimes updating head or tail pointers when 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * matching, appending, or even traversing nodes; in order to 188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * maintain a targeted slack. The idea of "sometimes" may be 189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * operationalized in several ways. The simplest is to use a 190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * per-operation counter incremented on each traversal step, and 191a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to try (via CAS) to update the associated queue pointer 192a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * whenever the count exceeds a threshold. Another, that requires 193a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * more overhead, is to use random number generators to update 194a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * with a given probability per traversal step. 195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 196a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * In any strategy along these lines, because CASes updating 197a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * fields may fail, the actual slack may exceed targeted 198a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * slack. However, they may be retried at any time to maintain 199a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * targets. Even when using very small slack values, this 200a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * approach works well for dual queues because it allows all 201a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * operations up to the point of matching or appending an item 202a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (hence potentially allowing progress by another thread) to be 203a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * read-only, thus not introducing any further contention. As 204a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * described below, we implement this by performing slack 205a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * maintenance retries only after these points. 206a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 207a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * As an accompaniment to such techniques, traversal overhead can 208a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * be further reduced without increasing contention of head 209a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * pointer updates: Threads may sometimes shortcut the "next" link 210a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * path from the current "head" node to be closer to the currently 211a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * known first unmatched node, and similarly for tail. Again, this 212a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may be triggered with using thresholds or randomization. 213a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 214a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * These ideas must be further extended to avoid unbounded amounts 215a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of costly-to-reclaim garbage caused by the sequential "next" 216a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * links of nodes starting at old forgotten head nodes: As first 217a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * described in detail by Boehm 218b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * (http://portal.acm.org/citation.cfm?doid=503272.503282), if a GC 219a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * delays noticing that any arbitrarily old node has become 220a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * garbage, all newer dead nodes will also be unreclaimed. 221a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (Similar issues arise in non-GC environments.) To cope with 222a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this in our implementation, upon CASing to advance the head 223a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * pointer, we set the "next" link of the previous head to point 224a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * only to itself; thus limiting the length of connected dead lists. 225a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (We also take similar care to wipe out possibly garbage 226a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * retaining values held in other Node fields.) However, doing so 227a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * adds some further complexity to traversal: If any "next" 228a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * pointer links to itself, it indicates that the current thread 229a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * has lagged behind a head-update, and so the traversal must 230a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * continue from the "head". Traversals trying to find the 231a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * current tail starting from "tail" may also encounter 232a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * self-links, in which case they also continue at "head". 233a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 234a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * It is tempting in slack-based scheme to not even use CAS for 235a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * updates (similarly to Ladan-Mozes & Shavit). However, this 236a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * cannot be done for head updates under the above link-forgetting 237a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * mechanics because an update may leave head at a detached node. 238a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * And while direct writes are possible for tail updates, they 239a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * increase the risk of long retraversals, and hence long garbage 240a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * chains, which can be much more costly than is worthwhile 241a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * considering that the cost difference of performing a CAS vs 242a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * write is smaller when they are not triggered on each operation 243a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (especially considering that writes and CASes equally require 244a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * additional GC bookkeeping ("write barriers") that are sometimes 245a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * more costly than the writes themselves because of contention). 246a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 247a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * *** Overview of implementation *** 248a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 249a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We use a threshold-based approach to updates, with a slack 250a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * threshold of two -- that is, we update head/tail when the 251a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * current pointer appears to be two or more steps away from the 252a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * first/last node. The slack value is hard-wired: a path greater 253a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * than one is naturally implemented by checking equality of 254a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * traversal pointers except when the list has only one element, 255a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * in which case we keep slack threshold at one. Avoiding tracking 256a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * explicit counts across method calls slightly simplifies an 257a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * already-messy implementation. Using randomization would 258a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * probably work better if there were a low-quality dirt-cheap 259a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * per-thread one available, but even ThreadLocalRandom is too 260a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * heavy for these purposes. 261a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 262a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * With such a small slack threshold value, it is not worthwhile 263a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to augment this with path short-circuiting (i.e., unsplicing 264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * interior nodes) except in the case of cancellation/removal (see 265a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * below). 266a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 267a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We allow both the head and tail fields to be null before any 268a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nodes are enqueued; initializing upon first append. This 269a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * simplifies some other logic, as well as providing more 270a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * efficient explicit control paths instead of letting JVMs insert 271a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * implicit NullPointerExceptions when they are null. While not 272a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * currently fully implemented, we also leave open the possibility 273a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of re-nulling these fields when empty (which is complicated to 274a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * arrange, for little benefit.) 275a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 276a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * All enqueue/dequeue operations are handled by the single method 277a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * "xfer" with parameters indicating whether to act as some form 278a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of offer, put, poll, take, or transfer (each possibly with 279a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * timeout). The relative complexity of using one monolithic 280a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method outweighs the code bulk and maintenance problems of 281a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * using separate methods for each case. 282a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 283a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Operation consists of up to three phases. The first is 284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * implemented within method xfer, the second in tryAppend, and 285a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the third in method awaitMatch. 286a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1. Try to match an existing node 288a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 289a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Starting at head, skip already-matched nodes until finding 290a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * an unmatched node of opposite mode, if one exists, in which 291a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * case matching it and returning, also if necessary updating 292a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * head to one past the matched node (or the node itself if the 293a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * list has no other unmatched nodes). If the CAS misses, then 294a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * a loop retries advancing head by two steps until either 295a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * success or the slack is at most two. By requiring that each 296a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * attempt advances head by two (if applicable), we ensure that 297a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the slack does not grow without bound. Traversals also check 298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if the initial head is now off-list, in which case they 299a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * start at the new head. 300a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 301a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * If no candidates are found and the call was untimed 302a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * poll/offer, (argument "how" is NOW) return. 303a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 304a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 2. Try to append a new node (method tryAppend) 305a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Starting at current tail pointer, find the actual last node 307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and try to append a new node (or if head was null, establish 308a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the first node). Nodes can be appended only if their 309a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * predecessors are either already matched or are of the same 310a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * mode. If we detect otherwise, then a new node with opposite 311a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * mode must have been appended during traversal, so we must 312a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * restart at phase 1. The traversal and update steps are 313a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * otherwise similar to phase 1: Retrying upon CAS misses and 314a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * checking for staleness. In particular, if a self-link is 315a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * encountered, then we can safely jump to a node on the list 316a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * by continuing the traversal at current head. 317a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 318a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * On successful append, if the call was ASYNC, return. 319a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 320a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 3. Await match or cancellation (method awaitMatch) 321a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 322a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Wait for another thread to match node; instead cancelling if 323a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the current thread was interrupted or the wait timed out. On 324a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * multiprocessors, we use front-of-queue spinning: If a node 325a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * appears to be the first unmatched node in the queue, it 326a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * spins a bit before blocking. In either case, before blocking 327a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * it tries to unsplice any nodes between the current "head" 328a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and the first unmatched node. 329a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 330a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Front-of-queue spinning vastly improves performance of 331a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * heavily contended queues. And so long as it is relatively 332a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * brief and "quiet", spinning does not much impact performance 333a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of less-contended queues. During spins threads check their 334a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * interrupt status and generate a thread-local random number 335a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to decide to occasionally perform a Thread.yield. While 336a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * yield has underdefined specs, we assume that it might help, 337a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and will not hurt, in limiting impact of spinning on busy 338a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * systems. We also use smaller (1/2) spins for nodes that are 339a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * not known to be front but whose predecessors have not 340a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * blocked -- these "chained" spins avoid artifacts of 341a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * front-of-queue rules which otherwise lead to alternating 342a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nodes spinning vs blocking. Further, front threads that 343a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * represent phase changes (from data to request node or vice 344a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * versa) compared to their predecessors receive additional 345a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * chained spins, reflecting longer paths typically required to 346a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unblock threads during phase changes. 347a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 348a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 349a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ** Unlinking removed interior nodes ** 350a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 351a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * In addition to minimizing garbage retention via self-linking 352a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * described above, we also unlink removed interior nodes. These 353a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may arise due to timed out or interrupted waits, or calls to 354a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * remove(x) or Iterator.remove. Normally, given a node that was 355a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * at one time known to be the predecessor of some node s that is 356a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to be removed, we can unsplice s by CASing the next field of 357a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * its predecessor if it still points to s (otherwise s must 358a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * already have been removed or is now offlist). But there are two 359a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * situations in which we cannot guarantee to make node s 360a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unreachable in this way: (1) If s is the trailing node of list 361a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (i.e., with null next), then it is pinned as the target node 362a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for appends, so can only be removed later after other nodes are 363a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * appended. (2) We cannot necessarily unlink s given a 364a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * predecessor node that is matched (including the case of being 365a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * cancelled): the predecessor may already be unspliced, in which 366a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * case some previous reachable node may still point to s. 367a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (For further explanation see Herlihy & Shavit "The Art of 368a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Multiprocessor Programming" chapter 9). Although, in both 369a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * cases, we can rule out the need for further action if either s 370a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * or its predecessor are (or can be made to be) at, or fall off 371a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * from, the head of list. 372a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 373a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Without taking these into account, it would be possible for an 374a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unbounded number of supposedly removed nodes to remain 375a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * reachable. Situations leading to such buildup are uncommon but 376a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * can occur in practice; for example when a series of short timed 377a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * calls to poll repeatedly time out but never otherwise fall off 378a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the list because of an untimed call to take at the front of the 379a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * queue. 380a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 381a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * When these cases arise, rather than always retraversing the 382a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * entire list to find an actual predecessor to unlink (which 383a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * won't help for case (1) anyway), we record a conservative 384a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * estimate of possible unsplice failures (in "sweepVotes"). 385a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We trigger a full sweep when the estimate exceeds a threshold 386a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ("SWEEP_THRESHOLD") indicating the maximum number of estimated 387a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * removal failures to tolerate before sweeping through, unlinking 388a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * cancelled nodes that were not unlinked upon initial removal. 389a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * We perform sweeps by the thread hitting threshold (rather than 390a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * background threads or by spreading work to other threads) 391a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * because in the main contexts in which removal occurs, the 392a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * caller is already timed-out, cancelled, or performing a 393a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * potentially O(n) operation (e.g. remove(x)), none of which are 394a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * time-critical enough to warrant the overhead that alternatives 395a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * would impose on other threads. 396a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 397a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Because the sweepVotes estimate is conservative, and because 398a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nodes become unlinked "naturally" as they fall off the head of 399a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the queue, and because we allow votes to accumulate even while 400a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * sweeps are in progress, there are typically significantly fewer 401a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * such nodes than estimated. Choice of a threshold value 402a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * balances the likelihood of wasted effort and contention, versus 403a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * providing a worst-case bound on retention of interior nodes in 404a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * quiescent queues. The value defined below was chosen 405a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * empirically to balance these under various timeout scenarios. 406a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 407a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Note that we cannot self-link unlinked interior nodes during 408a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * sweeps. However, the associated garbage chains terminate when 409a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * some successor ultimately falls off the head of the list and is 410a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * self-linked. 411a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 412a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 413a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** True if on multiprocessor */ 414a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final boolean MP = 415a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Runtime.getRuntime().availableProcessors() > 1; 416a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 417a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 418a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The number of times to spin (with randomly interspersed calls 419a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to Thread.yield) on multiprocessor before blocking when a node 420a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * is apparently the first waiter in the queue. See above for 421a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * explanation. Must be a power of two. The value is empirically 422a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * derived -- it works pretty well across a variety of processors, 423a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * numbers of CPUs, and OSes. 424a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 425a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int FRONT_SPINS = 1 << 7; 426a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 427a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 428a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The number of times to spin before blocking when a node is 429a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * preceded by another node that is apparently spinning. Also 430a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * serves as an increment to FRONT_SPINS on phase changes, and as 431a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * base average frequency for yielding during spins. Must be a 432a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * power of two. 433a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 434a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int CHAINED_SPINS = FRONT_SPINS >>> 1; 435a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 436a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 437a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The maximum number of estimated removal failures (sweepVotes) 438a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to tolerate before sweeping through the queue unlinking 439a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * cancelled nodes that were not unlinked upon initial 440a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * removal. See above for explanation. The value must be at least 441a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * two to avoid useless sweeps when removing trailing nodes. 442a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 443a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static final int SWEEP_THRESHOLD = 32; 444a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 445a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 446a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Queue nodes. Uses Object, not E, for items to allow forgetting 447a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * them after use. Relies heavily on Unsafe mechanics to minimize 448a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unnecessary ordering constraints: Writes that are intrinsically 449a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ordered wrt other accesses or CASes use simple relaxed forms. 450a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 451a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static final class Node { 452a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean isData; // false if this is a request node 453a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson volatile Object item; // initially non-null if isData; CASed to match 454a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson volatile Node next; 455a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson volatile Thread waiter; // null until waiting 456a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 457a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // CAS methods for fields 458a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean casNext(Node cmp, Node val) { 459b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, NEXT, cmp, val); 460a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 461a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 462a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean casItem(Object cmp, Object val) { 463a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert cmp == null || cmp.getClass() != Node.class; 464b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, ITEM, cmp, val); 465a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 466a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 467a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 468a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Constructs a new node. Uses relaxed write because item can 469a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * only be seen after publication via casNext. 470a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 471a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node(Object item, boolean isData) { 472b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(this, ITEM, item); // relaxed write 473a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.isData = isData; 474a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 475a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 476a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 477a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Links node to itself to avoid garbage retention. Called 478a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * only after CASing head field, so uses relaxed write. 479a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 480a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final void forgetNext() { 481b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(this, NEXT, this); 482a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 483a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 484a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 485a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Sets item to self and waiter to null, to avoid garbage 486a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * retention after matching or cancelling. Uses relaxed writes 487a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * because order is already constrained in the only calling 488a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * contexts: item is forgotten only after volatile/atomic 489a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * mechanics that extract items. Similarly, clearing waiter 490a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * follows either CAS or return from park (if ever parked; 491a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else we don't care). 492a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 493a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final void forgetContents() { 494b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(this, ITEM, this); 495b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(this, WAITER, null); 496a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 497a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 498a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 499a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns true if this node has been matched, including the 500a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * case of artificial matches due to cancellation. 501a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 502a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean isMatched() { 503a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object x = item; 504a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (x == this) || ((x == null) == isData); 505a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 506a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 507a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 508a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns true if this is an unmatched request node. 509a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 510a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean isUnmatchedRequest() { 511a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return !isData && item == null; 512a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 513a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 514a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 515a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns true if a node with the given mode cannot be 516a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * appended to this node because this node is unmatched and 517a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * has opposite data mode. 518a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 519a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean cannotPrecede(boolean haveData) { 520a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean d = isData; 521a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object x; 522a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return d != haveData && (x = item) != this && (x != null) == d; 523a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 524a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 525a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 526a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Tries to artificially match a data node -- used by remove. 527a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 528a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean tryMatchData() { 529a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert isData; 530a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object x = item; 531a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (x != null && x != this && casItem(x, null)) { 532a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson LockSupport.unpark(waiter); 533a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 534a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 535a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 536a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 537a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 538a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long serialVersionUID = -3375979862319811754L; 539a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 540a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Unsafe mechanics 541b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 542b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long ITEM; 543b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long NEXT; 544b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long WAITER; 545a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 546a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 547b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ITEM = U.objectFieldOffset 548b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("item")); 549b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak NEXT = U.objectFieldOffset 550b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("next")); 551b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak WAITER = U.objectFieldOffset 552b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("waiter")); 553b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 554a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 555a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 556a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 557a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 558a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 559a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** head of the queue; null until first enqueue */ 560a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson transient volatile Node head; 561a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 562a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** tail of the queue; null until first append */ 563a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private transient volatile Node tail; 564a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 565a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** The number of apparent failures to unsplice removed nodes */ 566a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private transient volatile int sweepVotes; 567a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 568a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // CAS methods for fields 569a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private boolean casTail(Node cmp, Node val) { 570b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, TAIL, cmp, val); 571a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 572a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 573a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private boolean casHead(Node cmp, Node val) { 574b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, HEAD, cmp, val); 575a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 576a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 577a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private boolean casSweepVotes(int cmp, int val) { 578b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapInt(this, SWEEPVOTES, cmp, val); 579a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 580a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 581a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* 582a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Possible values for "how" argument in xfer method. 583a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 584a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int NOW = 0; // for untimed poll, tryTransfer 585a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int ASYNC = 1; // for offer, put, add 586a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int SYNC = 2; // for transfer, take 587a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int TIMED = 3; // for timed poll, tryTransfer 588a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 589a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 590a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Implements all queuing methods. See above for explanation. 591a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 592a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param e the item or null for take 593a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param haveData true if this is a put, else a take 594a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param how NOW, ASYNC, SYNC, or TIMED 595a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param nanos timeout in nanosecs, used only if mode is TIMED 596a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return an item if matched, else e 597a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if haveData mode but e is null 598a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 599a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E xfer(E e, boolean haveData, int how, long nanos) { 600a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (haveData && (e == null)) 601a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new NullPointerException(); 602a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node s = null; // the node to append, if needed 603a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 604a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson retry: 605a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { // restart on append race 606a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 607a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node h = head, p = h; p != null;) { // find & match first node 608a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean isData = p.isData; 609a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object item = p.item; 610a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (item != p && (item != null) == isData) { // unmatched 611a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (isData == haveData) // can't match 612a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 613a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p.casItem(item, e)) { // match 614a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node q = p; q != h;) { 615a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node n = q.next; // update by 2 unless singleton 616a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head == h && casHead(h, n == null ? q : n)) { 617a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson h.forgetNext(); 618a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 619a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } // advance and retry 620a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if ((h = head) == null || 621a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (q = h.next) == null || !q.isMatched()) 622a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; // unless slack < 2 623a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 624a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson LockSupport.unpark(p.waiter); 625b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") E itemE = (E) item; 626b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return itemE; 627a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 628a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 629a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node n = p.next; 630a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = (p != n) ? n : (h = head); // Use head if p offlist 631a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 632a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 633a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (how != NOW) { // No matches available 634a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (s == null) 635a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s = new Node(e, haveData); 636a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node pred = tryAppend(s, haveData); 637a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (pred == null) 638a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson continue retry; // lost race vs opposite mode 639a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (how != ASYNC) 640a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return awaitMatch(s, pred, e, (how == TIMED), nanos); 641a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 642a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return e; // not waiting 643a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 644a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 645a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 646a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 647a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Tries to append node s as tail. 648a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 649a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param s the node to append 650a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param haveData true if appending in data mode 651a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return null on failure due to losing race with append in 652a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * different mode, else s's predecessor, or s itself if no 653a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * predecessor 654a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 655a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node tryAppend(Node s, boolean haveData) { 656a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node t = tail, p = t;;) { // move p to last node and append 657a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node n, u; // temps for reads of next & tail 658a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == null && (p = head) == null) { 659a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (casHead(null, s)) 660a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return s; // initialize 661a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 662a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (p.cannotPrecede(haveData)) 663a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return null; // lost race vs opposite mode 664a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if ((n = p.next) != null) // not last; keep traversing 665a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = p != t && t != (u = tail) ? (t = u) : // stale tail 666a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (p != n) ? n : null; // restart if off list 667a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (!p.casNext(null, s)) 668a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = p.next; // re-read on CAS failure 669a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 670a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p != t) { // update if slack now >= 2 671a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ((tail != t || !casTail(t, s)) && 672a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (t = tail) != null && 673a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (s = t.next) != null && // advance and retry 674a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (s = s.next) != null && s != t); 675a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 676a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return p; 677a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 678a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 679a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 680a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 681a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 682a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Spins/yields/blocks until node s is matched or caller gives up. 683a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 684a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param s the waiting node 685a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param pred the predecessor of s, or s itself if it has no 686a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * predecessor, or null if unknown (the null case does not occur 687a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * in any current calls but may in possible future extensions) 688a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param e the comparison value for checking match 689a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param timed if true, wait only until timeout elapses 690a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param nanos timeout in nanosecs, used only if timed is true 691a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return matched item, or e if unmatched on interrupt or timeout 692a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 693a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E awaitMatch(Node s, Node pred, E e, boolean timed, long nanos) { 69491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle final long deadline = timed ? System.nanoTime() + nanos : 0L; 695a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread w = Thread.currentThread(); 696a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int spins = -1; // initialized after first item and cancel checks 697a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ThreadLocalRandom randomYields = null; // bound if needed 698a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 699a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { 700a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object item = s.item; 701a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (item != e) { // matched 702a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert item != s; 703a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s.forgetContents(); // avoid garbage 704b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") E itemE = (E) item; 705b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return itemE; 706a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 707b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (w.isInterrupted() || (timed && nanos <= 0L)) { 708b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak unsplice(pred, s); // try to unlink and cancel 709b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (s.casItem(e, s)) // return normally if lost CAS 710b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return e; 711a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 712b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (spins < 0) { // establish spins at/near front 713a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if ((spins = spinsFor(pred, s.isData)) > 0) 714a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson randomYields = ThreadLocalRandom.current(); 715a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 716a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (spins > 0) { // spin 717a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson --spins; 718a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (randomYields.nextInt(CHAINED_SPINS) == 0) 719a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread.yield(); // occasionally yield 720a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 721a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (s.waiter == null) { 722a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s.waiter = w; // request unpark then recheck 723a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 724a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (timed) { 72591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle nanos = deadline - System.nanoTime(); 72691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (nanos > 0L) 727a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson LockSupport.parkNanos(this, nanos); 728a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 729a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 730a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson LockSupport.park(this); 731a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 732a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 733a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 734a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 735a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 736a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns spin/yield value for a node with given predecessor and 737a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * data mode. See above for explanation. 738a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 739a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static int spinsFor(Node pred, boolean haveData) { 740a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (MP && pred != null) { 741a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (pred.isData != haveData) // phase change 742a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return FRONT_SPINS + CHAINED_SPINS; 743a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (pred.isMatched()) // probably at front 744a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return FRONT_SPINS; 745a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (pred.waiter == null) // pred apparently spinning 746a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return CHAINED_SPINS; 747a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 748a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return 0; 749a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 750a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 751a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* -------------- Traversal methods -------------- */ 752a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 753a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 754a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the successor of p, or the head node if p.next has been 755a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * linked to self, which will only be true if traversing with a 756a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * stale pointer that is now off the list. 757a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 758a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node succ(Node p) { 759a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node next = p.next; 760a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (p == next) ? head : next; 761a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 762a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 763a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 764b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Returns the first unmatched data node, or null if none. 765b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Callers must recheck if the returned node's item field is null 766b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * or self-linked before using. 767a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 768b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final Node firstDataNode() { 769b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak restartFromHead: for (;;) { 770b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null;) { 771b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object item = p.item; 772b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData) { 773b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (item != null && item != p) 774b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return p; 775b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 776b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (item == null) 777b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 778b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 779b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue restartFromHead; 7805328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak } 781b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return null; 7825328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak } 7835328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak } 7845328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak 785ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak /** 786ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak * Traverses and counts unmatched nodes of the given mode. 787ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak * Used by methods size and getWaitingConsumerCount. 788ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak */ 789ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak private int countOfMode(boolean data) { 790b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak restartFromHead: for (;;) { 791b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int count = 0; 792b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null;) { 793b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!p.isMatched()) { 794b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData != data) 795b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return 0; 796b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (++count == Integer.MAX_VALUE) 797b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; // @see Collection.size() 798b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 799b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 800b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue restartFromHead; 801b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 802b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return count; 803b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 804b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 805b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 806b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public String toString() { 807b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak String[] a = null; 808b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak restartFromHead: for (;;) { 809b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int charLength = 0; 810b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int size = 0; 811b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null;) { 812b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object item = p.item; 813b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData) { 814b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (item != null && item != p) { 815b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (a == null) 816b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a = new String[4]; 817b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (size == a.length) 818b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a = Arrays.copyOf(a, 2 * size); 819b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak String s = item.toString(); 820b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a[size++] = s; 821b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak charLength += s.length(); 822b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 823b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } else if (item == null) 8245328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak break; 825b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 826b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue restartFromHead; 827a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 828b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 829b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (size == 0) 830b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return "[]"; 831b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 832b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return Helpers.toString(a, size, charLength); 833b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 834b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 835b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 836b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private Object[] toArrayInternal(Object[] a) { 837b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object[] x = a; 838b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak restartFromHead: for (;;) { 839b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int size = 0; 840b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null;) { 841b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object item = p.item; 842b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData) { 843b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (item != null && item != p) { 844b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (x == null) 845b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak x = new Object[4]; 846b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (size == x.length) 847b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak x = Arrays.copyOf(x, 2 * (size + 4)); 848b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak x[size++] = item; 849b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 850b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } else if (item == null) 851b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 852b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 853b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue restartFromHead; 8545328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak } 855b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (x == null) 856b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return new Object[0]; 857b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (a != null && size <= a.length) { 858b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (a != x) 859b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak System.arraycopy(x, 0, a, 0, size); 860b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (size < a.length) 861b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak a[size] = null; 862b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return a; 863b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 864b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return (size == x.length) ? x : Arrays.copyOf(x, size); 865a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 866b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 867b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 868b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 869b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Returns an array containing all of the elements in this queue, in 870b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * proper sequence. 871b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 872b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>The returned array will be "safe" in that no references to it are 873b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * maintained by this queue. (In other words, this method must allocate 874b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * a new array). The caller is thus free to modify the returned array. 875b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 876b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>This method acts as bridge between array-based and collection-based 877b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * APIs. 878b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 879b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return an array containing all of the elements in this queue 880b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 881b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public Object[] toArray() { 882b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return toArrayInternal(null); 883b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 884b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 885b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 886b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Returns an array containing all of the elements in this queue, in 887b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * proper sequence; the runtime type of the returned array is that of 888b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * the specified array. If the queue fits in the specified array, it 889b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * is returned therein. Otherwise, a new array is allocated with the 890b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * runtime type of the specified array and the size of this queue. 891b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 892b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>If this queue fits in the specified array with room to spare 893b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * (i.e., the array has more elements than this queue), the element in 894b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * the array immediately following the end of the queue is set to 895b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@code null}. 896b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 897b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>Like the {@link #toArray()} method, this method acts as bridge between 898b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * array-based and collection-based APIs. Further, this method allows 899b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * precise control over the runtime type of the output array, and may, 900b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * under certain circumstances, be used to save allocation costs. 901b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 902b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>Suppose {@code x} is a queue known to contain only strings. 903b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The following code can be used to dump the queue into a newly 904b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * allocated array of {@code String}: 905b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 906b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 907b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 908b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Note that {@code toArray(new Object[0])} is identical in function to 909b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@code toArray()}. 910b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 911b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param a the array into which the elements of the queue are to 912b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * be stored, if it is big enough; otherwise, a new array of the 913b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * same runtime type is allocated for this purpose 914b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return an array containing all of the elements in this queue 915b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @throws ArrayStoreException if the runtime type of the specified array 916b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * is not a supertype of the runtime type of every element in 917b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * this queue 918b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @throws NullPointerException if the specified array is null 919b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 920b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") 921b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public <T> T[] toArray(T[] a) { 922b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (a == null) throw new NullPointerException(); 923b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return (T[]) toArrayInternal(a); 924a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 925a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 926a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final class Itr implements Iterator<E> { 927a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node nextNode; // next node to return item for 928a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E nextItem; // the corresponding item 929a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node lastRet; // last returned node, to support remove 930a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private Node lastPred; // predecessor to unlink lastRet 931a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 932a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 933a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Moves to next node after prev, or first node if prev null. 934a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 935a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void advance(Node prev) { 936a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* 937a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * To track and avoid buildup of deleted nodes in the face 938a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of calls to both Queue.remove and Itr.remove, we must 939a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * include variants of unsplice and sweep upon each 940a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * advance: Upon Itr.remove, we may need to catch up links 941a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * from lastPred, and upon other removes, we might need to 942a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * skip ahead from stale nodes and unsplice deleted ones 943a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * found while advancing. 944a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 945a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 946a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node r, b; // reset lastPred upon possible deletion of lastRet 947a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if ((r = lastRet) != null && !r.isMatched()) 948a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastPred = r; // next lastPred is old lastRet 949a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if ((b = lastPred) == null || b.isMatched()) 950a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson lastPred = null; // at start of list 951a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 952a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node s, n; // help with removal of lastPred.next 953a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ((s = b.next) != null && 954a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s != b && s.isMatched() && 955a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (n = s.next) != null && n != s) 956a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson b.casNext(s, n); 957a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 958a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 959a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = prev; 960a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 961a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node p = prev, s, n;;) { 962a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s = (p == null) ? head : p.next; 963a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (s == null) 964a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 965a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (s == p) { 966a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = null; 967a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson continue; 968a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 969a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object item = s.item; 970a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (s.isData) { 971a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (item != null && item != s) { 972b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") E itemE = (E) item; 973b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak nextItem = itemE; 974a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextNode = s; 975a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return; 976a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 977a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 978a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (item == null) 979a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 980a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert s.isMatched(); 981a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == null) 982a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = s; 983a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if ((n = s.next) == null) 984a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 985a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (s == n) 986a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = null; 987a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 988a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.casNext(s, n); 989a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 990a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextNode = null; 991a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson nextItem = null; 992a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 993a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 994a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Itr() { 995a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson advance(null); 996a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 997a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 998a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public final boolean hasNext() { 999a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return nextNode != null; 1000a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1001a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1002a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public final E next() { 1003a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node p = nextNode; 1004a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == null) throw new NoSuchElementException(); 1005a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E e = nextItem; 1006a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson advance(p); 1007a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return e; 1008a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1009a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1010a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public final void remove() { 1011a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Node lastRet = this.lastRet; 1012a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet == null) 1013a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalStateException(); 1014a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.lastRet = null; 1015a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (lastRet.tryMatchData()) 1016a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson unsplice(lastPred, lastRet); 1017a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1018a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1019a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1020b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** A customized variant of Spliterators.IteratorSpliterator */ 1021b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final class LTQSpliterator<E> implements Spliterator<E> { 1022b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int MAX_BATCH = 1 << 25; // max batch array size; 1023b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node current; // current node; null until initialized 1024b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int batch; // batch size for splits 1025b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak boolean exhausted; // true when no more nodes 1026b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LTQSpliterator() {} 1027b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1028b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public Spliterator<E> trySplit() { 1029b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node p; 1030b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int b = batch; 1031b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; 1032b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!exhausted && 1033b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ((p = current) != null || (p = firstDataNode()) != null) && 1034b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak p.next != null) { 1035b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object[] a = new Object[n]; 1036b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int i = 0; 1037b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak do { 1038b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object e = p.item; 1039b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (e != p && (a[i] = e) != null) 1040b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ++i; 1041b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 1042b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak p = firstDataNode(); 1043b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } while (p != null && i < n && p.isData); 1044b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((current = p) == null) 1045b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak exhausted = true; 1046b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (i > 0) { 1047b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak batch = i; 1048b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return Spliterators.spliterator 1049b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (a, 0, i, (Spliterator.ORDERED | 1050b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Spliterator.NONNULL | 1051b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Spliterator.CONCURRENT)); 1052b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1053b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1054b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return null; 1055b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1056b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1057b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") 1058b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public void forEachRemaining(Consumer<? super E> action) { 1059b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node p; 1060b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (action == null) throw new NullPointerException(); 1061b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!exhausted && 1062b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ((p = current) != null || (p = firstDataNode()) != null)) { 1063b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak exhausted = true; 1064b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak do { 1065b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object e = p.item; 1066b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (e != null && e != p) 1067b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak action.accept((E)e); 1068b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 1069b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak p = firstDataNode(); 1070b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } while (p != null && p.isData); 1071b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1072b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1073b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1074b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") 1075b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public boolean tryAdvance(Consumer<? super E> action) { 1076b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node p; 1077b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (action == null) throw new NullPointerException(); 1078b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!exhausted && 1079b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ((p = current) != null || (p = firstDataNode()) != null)) { 1080b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object e; 1081b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak do { 1082b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((e = p.item) == p) 1083b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak e = null; 1084b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 1085b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak p = firstDataNode(); 1086b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } while (e == null && p != null && p.isData); 1087b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((current = p) == null) 1088b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak exhausted = true; 1089b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (e != null) { 1090b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak action.accept((E)e); 1091b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return true; 1092b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1093b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1094b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return false; 1095b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1096b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1097b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public long estimateSize() { return Long.MAX_VALUE; } 1098b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1099b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public int characteristics() { 1100b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return Spliterator.ORDERED | Spliterator.NONNULL | 1101b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Spliterator.CONCURRENT; 1102b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1103b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1104b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1105b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 1106b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Returns a {@link Spliterator} over the elements in this queue. 1107b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1108b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>The returned spliterator is 1109b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1110b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1111b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 1112b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. 1113b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1114b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @implNote 1115b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The {@code Spliterator} implements {@code trySplit} to permit limited 1116b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * parallelism. 1117b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 1118b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return a {@code Spliterator} over the elements in this queue 1119b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @since 1.8 1120b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 1121b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak public Spliterator<E> spliterator() { 1122b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return new LTQSpliterator<E>(); 1123b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1124b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* -------------- Removal methods -------------- */ 1126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Unsplices (now or later) the given deleted/cancelled node with 1129a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the given predecessor. 1130a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1131a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param pred a node that was at one time known to be the 1132a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * predecessor of s, or null or s itself if s is/was at head 1133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param s the node to be unspliced 1134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final void unsplice(Node pred, Node s) { 1136b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak s.waiter = null; // disable signals 1137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* 1138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * See above for rationale. Briefly: if pred still points to 1139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * s, try to unlink s. If s cannot be unlinked, because it is 1140a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * trailing node or pred might be unlinked, and neither pred 1141a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nor s are head or offlist, add to sweepVotes, and if enough 1142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * votes have accumulated, sweep. 1143a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1144a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (pred != null && pred != s && pred.next == s) { 1145a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node n = s.next; 1146a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (n == null || 1147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (n != s && pred.casNext(s, n) && pred.isMatched())) { 1148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { // check if at, or could be, head 1149a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node h = head; 1150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (h == pred || h == s || h == null) 1151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return; // at head or list empty 1152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!h.isMatched()) 1153a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node hn = h.next; 1155a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (hn == null) 1156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return; // now empty 1157a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (hn != h && casHead(h, hn)) 1158a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson h.forgetNext(); // advance head 1159a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1160a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (pred.next != pred && s.next != s) { // recheck if offlist 1161a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { // sweep now if enough votes 1162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int v = sweepVotes; 1163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (v < SWEEP_THRESHOLD) { 1164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (casSweepVotes(v, v + 1)) 1165a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (casSweepVotes(v, 0)) { 1168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson sweep(); 1169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1170a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1171a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1173a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1178a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Unlinks matched (typically cancelled) nodes encountered in a 1179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * traversal from head. 1180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void sweep() { 1182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node p = head, s, n; p != null && (s = p.next) != null; ) { 1183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!s.isMatched()) 1184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Unmatched nodes are never self-linked 1185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = s; 1186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if ((n = s.next) == null) // trailing node is pinned 1187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (s == n) // stale 1189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // No need to also check for p == s, since that implies s == n 1190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = head; 1191a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 1192a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.casNext(s, n); 1193a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1194a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1196a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1197a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Main implementation of remove(Object) 1198a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1199a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private boolean findAndRemove(Object e) { 1200a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (e != null) { 1201a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (Node pred = null, p = head; p != null; ) { 1202a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object item = p.item; 1203a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p.isData) { 1204a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (item != null && item != p && e.equals(item) && 1205a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p.tryMatchData()) { 1206a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson unsplice(pred, p); 1207a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1208a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1209a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1210a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (item == null) 1211a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1212a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson pred = p; 1213a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if ((p = p.next) == pred) { // stale 1214a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson pred = null; 1215a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = head; 1216a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1217a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1218a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1219a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1220a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1221a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1222a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1223a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Creates an initially empty {@code LinkedTransferQueue}. 1224a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1225a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public LinkedTransferQueue() { 1226a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1227a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1228a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1229a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Creates a {@code LinkedTransferQueue} 1230a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * initially containing the elements of the given collection, 1231a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * added in traversal order of the collection's iterator. 1232a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1233a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param c the collection of elements to initially contain 1234a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified collection or any 1235a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of its elements are null 1236a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1237a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public LinkedTransferQueue(Collection<? extends E> c) { 1238a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this(); 1239a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson addAll(c); 1240a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1241a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1242a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1243a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Inserts the specified element at the tail of this queue. 1244a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * As the queue is unbounded, this method will never block. 1245a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1246a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1247a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1248a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public void put(E e) { 1249a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson xfer(e, true, ASYNC, 0); 1250a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1251a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1252a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1253a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Inserts the specified element at the tail of this queue. 1254a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * As the queue is unbounded, this method will never block or 1255a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * return {@code false}. 1256a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1257a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} (as specified by 1258a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link java.util.concurrent.BlockingQueue#offer(Object,long,TimeUnit) 1259a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * BlockingQueue.offer}) 1260a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1261a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1262a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) { 1263a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson xfer(e, true, ASYNC, 0); 1264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1265a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1266a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1267a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1268a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Inserts the specified element at the tail of this queue. 1269a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * As the queue is unbounded, this method will never return {@code false}. 1270a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1271a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} (as specified by {@link Queue#offer}) 1272a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1273a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1274a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean offer(E e) { 1275a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson xfer(e, true, ASYNC, 0); 1276a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1277a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1278a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1279a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1280a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Inserts the specified element at the tail of this queue. 1281a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * As the queue is unbounded, this method will never throw 1282a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link IllegalStateException} or return {@code false}. 1283a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 1285a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1286a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean add(E e) { 1288a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson xfer(e, true, ASYNC, 0); 1289a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1290a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1291a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1292a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1293a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Transfers the element to a waiting consumer immediately, if possible. 1294a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1295a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>More precisely, transfers the specified element immediately 1296a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if there exists a consumer already waiting to receive it (in 1297a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link #take} or timed {@link #poll(long,TimeUnit) poll}), 1298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * otherwise returning {@code false} without enqueuing the element. 1299a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1300a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1301a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1302a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean tryTransfer(E e) { 1303a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return xfer(e, true, NOW, 0) == null; 1304a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1305a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Transfers the element to a consumer, waiting if necessary to do so. 1308a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1309a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>More precisely, transfers the specified element immediately 1310a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if there exists a consumer already waiting to receive it (in 1311a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link #take} or timed {@link #poll(long,TimeUnit) poll}), 1312a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else inserts the specified element at the tail of this queue 1313a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and waits until the element is received by a consumer. 1314a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1315a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1316a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1317a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public void transfer(E e) throws InterruptedException { 1318a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (xfer(e, true, SYNC, 0) != null) { 1319a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread.interrupted(); // failure possible only due to interrupt 1320a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new InterruptedException(); 1321a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1322a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1323a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1324a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1325a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Transfers the element to a consumer if it is possible to do so 1326a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * before the timeout elapses. 1327a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1328a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>More precisely, transfers the specified element immediately 1329a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if there exists a consumer already waiting to receive it (in 1330a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link #take} or timed {@link #poll(long,TimeUnit) poll}), 1331a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else inserts the specified element at the tail of this queue 1332a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and waits until the element is received by a consumer, 1333a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * returning {@code false} if the specified wait time elapses 1334a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * before the element can be transferred. 1335a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1336a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException if the specified element is null 1337a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1338a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean tryTransfer(E e, long timeout, TimeUnit unit) 1339a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws InterruptedException { 1340a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (xfer(e, true, TIMED, unit.toNanos(timeout)) == null) 1341a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1342a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (!Thread.interrupted()) 1343a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1344a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new InterruptedException(); 1345a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1346a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1347a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public E take() throws InterruptedException { 1348a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E e = xfer(null, false, SYNC, 0); 1349a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (e != null) 1350a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return e; 1351a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread.interrupted(); 1352a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new InterruptedException(); 1353a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1354a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1355a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public E poll(long timeout, TimeUnit unit) throws InterruptedException { 1356a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E e = xfer(null, false, TIMED, unit.toNanos(timeout)); 1357a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (e != null || !Thread.interrupted()) 1358a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return e; 1359a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new InterruptedException(); 1360a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1361a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1362a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public E poll() { 1363a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return xfer(null, false, NOW, 0); 1364a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1365a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1366a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1367a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException {@inheritDoc} 1368a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalArgumentException {@inheritDoc} 1369a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1370a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int drainTo(Collection<? super E> c) { 1371a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (c == null) 1372a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new NullPointerException(); 1373a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (c == this) 1374a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalArgumentException(); 1375a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int n = 0; 1376a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (E e; (e = poll()) != null;) { 1377a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson c.add(e); 1378a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ++n; 1379a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1380a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return n; 1381a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1382a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1383a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1384a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws NullPointerException {@inheritDoc} 1385a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalArgumentException {@inheritDoc} 1386a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1387a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int drainTo(Collection<? super E> c, int maxElements) { 1388a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (c == null) 1389a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new NullPointerException(); 1390a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (c == this) 1391a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalArgumentException(); 1392a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int n = 0; 1393a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (E e; n < maxElements && (e = poll()) != null;) { 1394a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson c.add(e); 1395a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ++n; 1396a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1397a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return n; 1398a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1399a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1400a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1401a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns an iterator over the elements in this queue in proper sequence. 1402a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The elements will be returned in order from first (head) to last (tail). 1403a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1404b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <p>The returned iterator is 1405b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1406a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1407a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return an iterator over the elements in this queue in proper sequence 1408a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1409a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Iterator<E> iterator() { 1410a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return new Itr(); 1411a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1412a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1413a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public E peek() { 1414b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak restartFromHead: for (;;) { 1415b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null;) { 1416b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object item = p.item; 1417b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData) { 1418b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (item != null && item != p) { 1419b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak @SuppressWarnings("unchecked") E e = (E) item; 1420b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return e; 1421b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1422b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1423b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (item == null) 1424b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 1425b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 1426b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue restartFromHead; 1427b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1428b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return null; 1429b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1430a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1431a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1432a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1433a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns {@code true} if this queue contains no elements. 1434a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1435a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} if this queue contains no elements 1436a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1437a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean isEmpty() { 1438b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return firstDataNode() == null; 1439a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1440a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1441a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean hasWaitingConsumer() { 1442b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak restartFromHead: for (;;) { 1443b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null;) { 1444b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object item = p.item; 1445b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData) { 1446b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (item != null && item != p) 1447b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 1448b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1449b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (item == null) 1450b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return true; 1451b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == (p = p.next)) 1452b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue restartFromHead; 1453b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1454b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return false; 1455b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1456a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1457a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1458a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1459a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the number of elements in this queue. If this queue 1460a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * contains more than {@code Integer.MAX_VALUE} elements, returns 1461a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code Integer.MAX_VALUE}. 1462a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1463a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>Beware that, unlike in most collections, this method is 1464a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <em>NOT</em> a constant-time operation. Because of the 1465a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * asynchronous nature of these queues, determining the current 1466a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number of elements requires an O(n) traversal. 1467a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1468a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the number of elements in this queue 1469a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1470a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int size() { 1471a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return countOfMode(true); 1472a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1473a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1474a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int getWaitingConsumerCount() { 1475a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return countOfMode(false); 1476a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1477a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1478a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1479a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Removes a single instance of the specified element from this queue, 1480a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if it is present. More formally, removes an element {@code e} such 1481a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 1482a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * elements. 1483a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns {@code true} if this queue contained the specified element 1484a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (or equivalently, if this queue changed as a result of the call). 1485a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1486a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param o element to be removed from this queue, if present 1487a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} if this queue changed as a result of the call 1488a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1489a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean remove(Object o) { 1490a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return findAndRemove(o); 1491a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1492a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1493a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1494a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns {@code true} if this queue contains the specified element. 1495a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * More formally, returns {@code true} if and only if this queue contains 1496a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 1497a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1498a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param o object to be checked for containment in this queue 1499a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} if this queue contains the specified element 1500a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1501a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean contains(Object o) { 1502b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (o != null) { 1503b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = head; p != null; p = succ(p)) { 1504b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Object item = p.item; 1505b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.isData) { 1506b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (item != null && item != p && o.equals(item)) 1507b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return true; 1508b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1509b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (item == null) 1510b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 1511a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1512a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1513a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1514a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1515a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1516a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1517a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Always returns {@code Integer.MAX_VALUE} because a 1518a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code LinkedTransferQueue} is not capacity constrained. 1519a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1520a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code Integer.MAX_VALUE} (as specified by 1521a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link java.util.concurrent.BlockingQueue#remainingCapacity() 1522a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * BlockingQueue.remainingCapacity}) 1523a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1524a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int remainingCapacity() { 1525a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return Integer.MAX_VALUE; 1526a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1527a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1528a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 152991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Saves this queue to a stream (that is, serializes it). 1530a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1531b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param s the stream 1532b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 1533a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @serialData All of the elements (each an {@code E}) in 1534a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the proper order, followed by a null 1535a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1536a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void writeObject(java.io.ObjectOutputStream s) 1537a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws java.io.IOException { 1538a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s.defaultWriteObject(); 1539a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (E e : this) 1540a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s.writeObject(e); 1541a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Use trailing null as sentinel 1542a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s.writeObject(null); 1543a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1544a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1545a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 154691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Reconstitutes this queue from a stream (that is, deserializes it). 1547b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param s the stream 1548b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @throws ClassNotFoundException if the class of a serialized object 1549b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * could not be found 1550b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 1551a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1552a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void readObject(java.io.ObjectInputStream s) 1553a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws java.io.IOException, ClassNotFoundException { 1554a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s.defaultReadObject(); 1555a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { 155691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle @SuppressWarnings("unchecked") 155791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle E item = (E) s.readObject(); 1558a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (item == null) 1559a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1560a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 1561a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson offer(item); 1562a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1563a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1564a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1565a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Unsafe mechanics 1566a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1567b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 1568b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long HEAD; 1569b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long TAIL; 1570b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long SWEEPVOTES; 1571a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 1572a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 1573b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak HEAD = U.objectFieldOffset 1574b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (LinkedTransferQueue.class.getDeclaredField("head")); 1575b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak TAIL = U.objectFieldOffset 1576b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (LinkedTransferQueue.class.getDeclaredField("tail")); 1577b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak SWEEPVOTES = U.objectFieldOffset 1578b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (LinkedTransferQueue.class.getDeclaredField("sweepVotes")); 1579b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 1580a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 1581a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1582edf43d27e240d82106f39ae91404963c23987234Narayan Kamath 1583edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // Reduce the risk of rare disastrous classloading in first call to 1584edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773 1585edf43d27e240d82106f39ae91404963c23987234Narayan Kamath Class<?> ensureLoaded = LockSupport.class; 1586a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1587a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson} 1588