ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166y/LinkedTransferQueue.java

Comparing jsr166/src/jsr166y/LinkedTransferQueue.java (file contents):
Revision 1.36 by jsr166, Fri Jul 31 07:30:29 2009 UTC vs.
Revision 1.94 by jsr166, Sat Oct 3 18:17:51 2015 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package jsr166y;
8
9	–	import java.util.concurrent.*;
10	–
9		import java.util.AbstractQueue;
10		import java.util.Collection;
13	–	import java.util.ConcurrentModificationException;
11		import java.util.Iterator;
12		import java.util.NoSuchElementException;
13		import java.util.Queue;
14	+	import java.util.concurrent.TimeUnit;
15		import java.util.concurrent.locks.LockSupport;
18	–	import java.util.concurrent.atomic.AtomicReference;
16
17		/**
18	<	* An unbounded {@linkplain TransferQueue} based on linked nodes.
18	>	* An unbounded {@link TransferQueue} based on linked nodes.
19		* This queue orders elements FIFO (first-in-first-out) with respect
20		* to any given producer.  The <em>head</em> of the queue is that
21		* element that has been on the queue the longest time for some
22		* producer.  The <em>tail</em> of the queue is that element that has
23		* been on the queue the shortest time for some producer.
24		*
25	<	* <p>Beware that, unlike in most collections, the {@code size}
26	<	* method is <em>NOT</em> a constant-time operation. Because of the
25	>	* <p>Beware that, unlike in most collections, the {@code size} method
26	>	* is <em>NOT</em> a constant-time operation. Because of the
27		* asynchronous nature of these queues, determining the current number
28	<	* of elements requires a traversal of the elements.
28	>	* of elements requires a traversal of the elements, and so may report
29	>	* inaccurate results if this collection is modified during traversal.
30	>	* Additionally, the bulk operations {@code addAll},
31	>	* {@code removeAll}, {@code retainAll}, {@code containsAll},
32	>	* {@code equals}, and {@code toArray} are <em>not</em> guaranteed
33	>	* to be performed atomically. For example, an iterator operating
34	>	* concurrently with an {@code addAll} operation might view only some
35	>	* of the added elements.
36		*
37		* <p>This class and its iterator implement all of the
38		* <em>optional</em> methods of the {@link Collection} and {@link
#	Line 54 | Line 58 | public class LinkedTransferQueue<E> exte
58		private static final long serialVersionUID = -3223113410248163686L;
59
60		/*
61	<	* This class extends the approach used in FIFO-mode
58	<	* SynchronousQueues. See the internal documentation, as well as
59	<	* the PPoPP 2006 paper "Scalable Synchronous Queues" by Scherer,
60	<	* Lea & Scott
61	<	* (http://www.cs.rice.edu/~wns1/papers/2006-PPoPP-SQ.pdf)
61	>	* *** Overview of Dual Queues with Slack ***
62		*
63	<	* The main extension is to provide different Wait modes for the
64	<	* main "xfer" method that puts or takes items.  These don't
65	<	* impact the basic dual-queue logic, but instead control whether
66	<	* or how threads block upon insertion of request or data nodes
67	<	* into the dual queue. It also uses slightly different
68	<	* conventions for tracking whether nodes are off-list or
69	<	* cancelled.
70	<	*/
71	<
72	<	// Wait modes for xfer method
73	<	static final int NOWAIT  = 0;
74	<	static final int TIMEOUT = 1;
75	<	static final int WAIT    = 2;
76	<
77	<	/** The number of CPUs, for spin control */
78	<	static final int NCPUS = Runtime.getRuntime().availableProcessors();
79	<
80	<	/**
81	<	* The number of times to spin before blocking in timed waits.
82	<	* The value is empirically derived -- it works well across a
83	<	* variety of processors and OSes. Empirically, the best value
84	<	* seems not to vary with number of CPUs (beyond 2) so is just
85	<	* a constant.
86	<	*/
87	<	static final int maxTimedSpins = (NCPUS < 2) ? 0 : 32;
88	<
89	<	/**
90	<	* The number of times to spin before blocking in untimed waits.
91	<	* This is greater than timed value because untimed waits spin
92	<	* faster since they don't need to check times on each spin.
93	<	*/
94	<	static final int maxUntimedSpins = maxTimedSpins * 16;
63	>	* Dual Queues, introduced by Scherer and Scott
64	>	* (http://www.cs.rice.edu/~wns1/papers/2004-DISC-DDS.pdf) are
65	>	* (linked) queues in which nodes may represent either data or
66	>	* requests.  When a thread tries to enqueue a data node, but
67	>	* encounters a request node, it instead "matches" and removes it;
68	>	* and vice versa for enqueuing requests. Blocking Dual Queues
69	>	* arrange that threads enqueuing unmatched requests block until
70	>	* other threads provide the match. Dual Synchronous Queues (see
71	>	* Scherer, Lea, & Scott
72	>	* http://www.cs.rochester.edu/u/scott/papers/2009_Scherer_CACM_SSQ.pdf)
73	>	* additionally arrange that threads enqueuing unmatched data also
74	>	* block.  Dual Transfer Queues support all of these modes, as
75	>	* dictated by callers.
76	>	*
77	>	* A FIFO dual queue may be implemented using a variation of the
78	>	* Michael & Scott (M&S) lock-free queue algorithm
79	>	* (http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf).
80	>	* It maintains two pointer fields, "head", pointing to a
81	>	* (matched) node that in turn points to the first actual
82	>	* (unmatched) queue node (or null if empty); and "tail" that
83	>	* points to the last node on the queue (or again null if
84	>	* empty). For example, here is a possible queue with four data
85	>	* elements:
86	>	*
87	>	*  head                tail
88	>	*    |                   |
89	>	*    v                   v
90	>	*    M -> U -> U -> U -> U
91	>	*
92	>	* The M&S queue algorithm is known to be prone to scalability and
93	>	* overhead limitations when maintaining (via CAS) these head and
94	>	* tail pointers. This has led to the development of
95	>	* contention-reducing variants such as elimination arrays (see
96	>	* Moir et al http://portal.acm.org/citation.cfm?id=1074013) and
97	>	* optimistic back pointers (see Ladan-Mozes & Shavit
98	>	* http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf).
99	>	* However, the nature of dual queues enables a simpler tactic for
100	>	* improving M&S-style implementations when dual-ness is needed.
101	>	*
102	>	* In a dual queue, each node must atomically maintain its match
103	>	* status. While there are other possible variants, we implement
104	>	* this here as: for a data-mode node, matching entails CASing an
105	>	* "item" field from a non-null data value to null upon match, and
106	>	* vice-versa for request nodes, CASing from null to a data
107	>	* value. (Note that the linearization properties of this style of
108	>	* queue are easy to verify -- elements are made available by
109	>	* linking, and unavailable by matching.) Compared to plain M&S
110	>	* queues, this property of dual queues requires one additional
111	>	* successful atomic operation per enq/deq pair. But it also
112	>	* enables lower cost variants of queue maintenance mechanics. (A
113	>	* variation of this idea applies even for non-dual queues that
114	>	* support deletion of interior elements, such as
115	>	* j.u.c.ConcurrentLinkedQueue.)
116	>	*
117	>	* Once a node is matched, its match status can never again
118	>	* change.  We may thus arrange that the linked list of them
119	>	* contain a prefix of zero or more matched nodes, followed by a
120	>	* suffix of zero or more unmatched nodes. (Note that we allow
121	>	* both the prefix and suffix to be zero length, which in turn
122	>	* means that we do not use a dummy header.)  If we were not
123	>	* concerned with either time or space efficiency, we could
124	>	* correctly perform enqueue and dequeue operations by traversing
125	>	* from a pointer to the initial node; CASing the item of the
126	>	* first unmatched node on match and CASing the next field of the
127	>	* trailing node on appends. (Plus some special-casing when
128	>	* initially empty).  While this would be a terrible idea in
129	>	* itself, it does have the benefit of not requiring ANY atomic
130	>	* updates on head/tail fields.
131	>	*
132	>	* We introduce here an approach that lies between the extremes of
133	>	* never versus always updating queue (head and tail) pointers.
134	>	* This offers a tradeoff between sometimes requiring extra
135	>	* traversal steps to locate the first and/or last unmatched
136	>	* nodes, versus the reduced overhead and contention of fewer
137	>	* updates to queue pointers. For example, a possible snapshot of
138	>	* a queue is:
139	>	*
140	>	*  head           tail
141	>	*    |              |
142	>	*    v              v
143	>	*    M -> M -> U -> U -> U -> U
144	>	*
145	>	* The best value for this "slack" (the targeted maximum distance
146	>	* between the value of "head" and the first unmatched node, and
147	>	* similarly for "tail") is an empirical matter. We have found
148	>	* that using very small constants in the range of 1-3 work best
149	>	* over a range of platforms. Larger values introduce increasing
150	>	* costs of cache misses and risks of long traversal chains, while
151	>	* smaller values increase CAS contention and overhead.
152	>	*
153	>	* Dual queues with slack differ from plain M&S dual queues by
154	>	* virtue of only sometimes updating head or tail pointers when
155	>	* matching, appending, or even traversing nodes; in order to
156	>	* maintain a targeted slack.  The idea of "sometimes" may be
157	>	* operationalized in several ways. The simplest is to use a
158	>	* per-operation counter incremented on each traversal step, and
159	>	* to try (via CAS) to update the associated queue pointer
160	>	* whenever the count exceeds a threshold. Another, that requires
161	>	* more overhead, is to use random number generators to update
162	>	* with a given probability per traversal step.
163	>	*
164	>	* In any strategy along these lines, because CASes updating
165	>	* fields may fail, the actual slack may exceed targeted
166	>	* slack. However, they may be retried at any time to maintain
167	>	* targets.  Even when using very small slack values, this
168	>	* approach works well for dual queues because it allows all
169	>	* operations up to the point of matching or appending an item
170	>	* (hence potentially allowing progress by another thread) to be
171	>	* read-only, thus not introducing any further contention. As
172	>	* described below, we implement this by performing slack
173	>	* maintenance retries only after these points.
174	>	*
175	>	* As an accompaniment to such techniques, traversal overhead can
176	>	* be further reduced without increasing contention of head
177	>	* pointer updates: Threads may sometimes shortcut the "next" link
178	>	* path from the current "head" node to be closer to the currently
179	>	* known first unmatched node, and similarly for tail. Again, this
180	>	* may be triggered with using thresholds or randomization.
181	>	*
182	>	* These ideas must be further extended to avoid unbounded amounts
183	>	* of costly-to-reclaim garbage caused by the sequential "next"
184	>	* links of nodes starting at old forgotten head nodes: As first
185	>	* described in detail by Boehm
186	>	* (http://portal.acm.org/citation.cfm?doid=503272.503282) if a GC
187	>	* delays noticing that any arbitrarily old node has become
188	>	* garbage, all newer dead nodes will also be unreclaimed.
189	>	* (Similar issues arise in non-GC environments.)  To cope with
190	>	* this in our implementation, upon CASing to advance the head
191	>	* pointer, we set the "next" link of the previous head to point
192	>	* only to itself; thus limiting the length of connected dead lists.
193	>	* (We also take similar care to wipe out possibly garbage
194	>	* retaining values held in other Node fields.)  However, doing so
195	>	* adds some further complexity to traversal: If any "next"
196	>	* pointer links to itself, it indicates that the current thread
197	>	* has lagged behind a head-update, and so the traversal must
198	>	* continue from the "head".  Traversals trying to find the
199	>	* current tail starting from "tail" may also encounter
200	>	* self-links, in which case they also continue at "head".
201	>	*
202	>	* It is tempting in slack-based scheme to not even use CAS for
203	>	* updates (similarly to Ladan-Mozes & Shavit). However, this
204	>	* cannot be done for head updates under the above link-forgetting
205	>	* mechanics because an update may leave head at a detached node.
206	>	* And while direct writes are possible for tail updates, they
207	>	* increase the risk of long retraversals, and hence long garbage
208	>	* chains, which can be much more costly than is worthwhile
209	>	* considering that the cost difference of performing a CAS vs
210	>	* write is smaller when they are not triggered on each operation
211	>	* (especially considering that writes and CASes equally require
212	>	* additional GC bookkeeping ("write barriers") that are sometimes
213	>	* more costly than the writes themselves because of contention).
214	>	*
215	>	* *** Overview of implementation ***
216	>	*
217	>	* We use a threshold-based approach to updates, with a slack
218	>	* threshold of two -- that is, we update head/tail when the
219	>	* current pointer appears to be two or more steps away from the
220	>	* first/last node. The slack value is hard-wired: a path greater
221	>	* than one is naturally implemented by checking equality of
222	>	* traversal pointers except when the list has only one element,
223	>	* in which case we keep slack threshold at one. Avoiding tracking
224	>	* explicit counts across method calls slightly simplifies an
225	>	* already-messy implementation. Using randomization would
226	>	* probably work better if there were a low-quality dirt-cheap
227	>	* per-thread one available, but even ThreadLocalRandom is too
228	>	* heavy for these purposes.
229	>	*
230	>	* With such a small slack threshold value, it is not worthwhile
231	>	* to augment this with path short-circuiting (i.e., unsplicing
232	>	* interior nodes) except in the case of cancellation/removal (see
233	>	* below).
234	>	*
235	>	* We allow both the head and tail fields to be null before any
236	>	* nodes are enqueued; initializing upon first append.  This
237	>	* simplifies some other logic, as well as providing more
238	>	* efficient explicit control paths instead of letting JVMs insert
239	>	* implicit NullPointerExceptions when they are null.  While not
240	>	* currently fully implemented, we also leave open the possibility
241	>	* of re-nulling these fields when empty (which is complicated to
242	>	* arrange, for little benefit.)
243	>	*
244	>	* All enqueue/dequeue operations are handled by the single method
245	>	* "xfer" with parameters indicating whether to act as some form
246	>	* of offer, put, poll, take, or transfer (each possibly with
247	>	* timeout). The relative complexity of using one monolithic
248	>	* method outweighs the code bulk and maintenance problems of
249	>	* using separate methods for each case.
250	>	*
251	>	* Operation consists of up to three phases. The first is
252	>	* implemented within method xfer, the second in tryAppend, and
253	>	* the third in method awaitMatch.
254	>	*
255	>	* 1. Try to match an existing node
256	>	*
257	>	*    Starting at head, skip already-matched nodes until finding
258	>	*    an unmatched node of opposite mode, if one exists, in which
259	>	*    case matching it and returning, also if necessary updating
260	>	*    head to one past the matched node (or the node itself if the
261	>	*    list has no other unmatched nodes). If the CAS misses, then
262	>	*    a loop retries advancing head by two steps until either
263	>	*    success or the slack is at most two. By requiring that each
264	>	*    attempt advances head by two (if applicable), we ensure that
265	>	*    the slack does not grow without bound. Traversals also check
266	>	*    if the initial head is now off-list, in which case they
267	>	*    start at the new head.
268	>	*
269	>	*    If no candidates are found and the call was untimed
270	>	*    poll/offer, (argument "how" is NOW) return.
271	>	*
272	>	* 2. Try to append a new node (method tryAppend)
273	>	*
274	>	*    Starting at current tail pointer, find the actual last node
275	>	*    and try to append a new node (or if head was null, establish
276	>	*    the first node). Nodes can be appended only if their
277	>	*    predecessors are either already matched or are of the same
278	>	*    mode. If we detect otherwise, then a new node with opposite
279	>	*    mode must have been appended during traversal, so we must
280	>	*    restart at phase 1. The traversal and update steps are
281	>	*    otherwise similar to phase 1: Retrying upon CAS misses and
282	>	*    checking for staleness.  In particular, if a self-link is
283	>	*    encountered, then we can safely jump to a node on the list
284	>	*    by continuing the traversal at current head.
285	>	*
286	>	*    On successful append, if the call was ASYNC, return.
287	>	*
288	>	* 3. Await match or cancellation (method awaitMatch)
289	>	*
290	>	*    Wait for another thread to match node; instead cancelling if
291	>	*    the current thread was interrupted or the wait timed out. On
292	>	*    multiprocessors, we use front-of-queue spinning: If a node
293	>	*    appears to be the first unmatched node in the queue, it
294	>	*    spins a bit before blocking. In either case, before blocking
295	>	*    it tries to unsplice any nodes between the current "head"
296	>	*    and the first unmatched node.
297	>	*
298	>	*    Front-of-queue spinning vastly improves performance of
299	>	*    heavily contended queues. And so long as it is relatively
300	>	*    brief and "quiet", spinning does not much impact performance
301	>	*    of less-contended queues.  During spins threads check their
302	>	*    interrupt status and generate a thread-local random number
303	>	*    to decide to occasionally perform a Thread.yield. While
304	>	*    yield has underdefined specs, we assume that it might help,
305	>	*    and will not hurt, in limiting impact of spinning on busy
306	>	*    systems.  We also use smaller (1/2) spins for nodes that are
307	>	*    not known to be front but whose predecessors have not
308	>	*    blocked -- these "chained" spins avoid artifacts of
309	>	*    front-of-queue rules which otherwise lead to alternating
310	>	*    nodes spinning vs blocking. Further, front threads that
311	>	*    represent phase changes (from data to request node or vice
312	>	*    versa) compared to their predecessors receive additional
313	>	*    chained spins, reflecting longer paths typically required to
314	>	*    unblock threads during phase changes.
315	>	*
316	>	*
317	>	* ** Unlinking removed interior nodes **
318	>	*
319	>	* In addition to minimizing garbage retention via self-linking
320	>	* described above, we also unlink removed interior nodes. These
321	>	* may arise due to timed out or interrupted waits, or calls to
322	>	* remove(x) or Iterator.remove.  Normally, given a node that was
323	>	* at one time known to be the predecessor of some node s that is
324	>	* to be removed, we can unsplice s by CASing the next field of
325	>	* its predecessor if it still points to s (otherwise s must
326	>	* already have been removed or is now offlist). But there are two
327	>	* situations in which we cannot guarantee to make node s
328	>	* unreachable in this way: (1) If s is the trailing node of list
329	>	* (i.e., with null next), then it is pinned as the target node
330	>	* for appends, so can only be removed later after other nodes are
331	>	* appended. (2) We cannot necessarily unlink s given a
332	>	* predecessor node that is matched (including the case of being
333	>	* cancelled): the predecessor may already be unspliced, in which
334	>	* case some previous reachable node may still point to s.
335	>	* (For further explanation see Herlihy & Shavit "The Art of
336	>	* Multiprocessor Programming" chapter 9).  Although, in both
337	>	* cases, we can rule out the need for further action if either s
338	>	* or its predecessor are (or can be made to be) at, or fall off
339	>	* from, the head of list.
340	>	*
341	>	* Without taking these into account, it would be possible for an
342	>	* unbounded number of supposedly removed nodes to remain
343	>	* reachable.  Situations leading to such buildup are uncommon but
344	>	* can occur in practice; for example when a series of short timed
345	>	* calls to poll repeatedly time out but never otherwise fall off
346	>	* the list because of an untimed call to take at the front of the
347	>	* queue.
348	>	*
349	>	* When these cases arise, rather than always retraversing the
350	>	* entire list to find an actual predecessor to unlink (which
351	>	* won't help for case (1) anyway), we record a conservative
352	>	* estimate of possible unsplice failures (in "sweepVotes").
353	>	* We trigger a full sweep when the estimate exceeds a threshold
354	>	* ("SWEEP_THRESHOLD") indicating the maximum number of estimated
355	>	* removal failures to tolerate before sweeping through, unlinking
356	>	* cancelled nodes that were not unlinked upon initial removal.
357	>	* We perform sweeps by the thread hitting threshold (rather than
358	>	* background threads or by spreading work to other threads)
359	>	* because in the main contexts in which removal occurs, the
360	>	* caller is already timed-out, cancelled, or performing a
361	>	* potentially O(n) operation (e.g. remove(x)), none of which are
362	>	* time-critical enough to warrant the overhead that alternatives
363	>	* would impose on other threads.
364	>	*
365	>	* Because the sweepVotes estimate is conservative, and because
366	>	* nodes become unlinked "naturally" as they fall off the head of
367	>	* the queue, and because we allow votes to accumulate even while
368	>	* sweeps are in progress, there are typically significantly fewer
369	>	* such nodes than estimated.  Choice of a threshold value
370	>	* balances the likelihood of wasted effort and contention, versus
371	>	* providing a worst-case bound on retention of interior nodes in
372	>	* quiescent queues. The value defined below was chosen
373	>	* empirically to balance these under various timeout scenarios.
374	>	*
375	>	* Note that we cannot self-link unlinked interior nodes during
376	>	* sweeps. However, the associated garbage chains terminate when
377	>	* some successor ultimately falls off the head of the list and is
378	>	* self-linked.
379	>	*/
380	>
381	>	/** True if on multiprocessor */
382	>	private static final boolean MP =
383	>	Runtime.getRuntime().availableProcessors() > 1;
384	>
385	>	/**
386	>	* The number of times to spin (with randomly interspersed calls
387	>	* to Thread.yield) on multiprocessor before blocking when a node
388	>	* is apparently the first waiter in the queue.  See above for
389	>	* explanation. Must be a power of two. The value is empirically
390	>	* derived -- it works pretty well across a variety of processors,
391	>	* numbers of CPUs, and OSes.
392	>	*/
393	>	private static final int FRONT_SPINS   = 1 << 7;
394	>
395	>	/**
396	>	* The number of times to spin before blocking when a node is
397	>	* preceded by another node that is apparently spinning.  Also
398	>	* serves as an increment to FRONT_SPINS on phase changes, and as
399	>	* base average frequency for yielding during spins. Must be a
400	>	* power of two.
401	>	*/
402	>	private static final int CHAINED_SPINS = FRONT_SPINS >>> 1;
403	>
404	>	/**
405	>	* The maximum number of estimated removal failures (sweepVotes)
406	>	* to tolerate before sweeping through the queue unlinking
407	>	* cancelled nodes that were not unlinked upon initial
408	>	* removal. See above for explanation. The value must be at least
409	>	* two to avoid useless sweeps when removing trailing nodes.
410	>	*/
411	>	static final int SWEEP_THRESHOLD = 32;
412	>
413	>	/**
414	>	* Queue nodes. Uses Object, not E, for items to allow forgetting
415	>	* them after use.  Relies heavily on Unsafe mechanics to minimize
416	>	* unnecessary ordering constraints: Writes that are intrinsically
417	>	* ordered wrt other accesses or CASes use simple relaxed forms.
418	>	*/
419	>	static final class Node {
420	>	final boolean isData;   // false if this is a request node
421	>	volatile Object item;   // initially non-null if isData; CASed to match
422	>	volatile Node next;
423	>	volatile Thread waiter; // null until waiting
424
425	<	/**
426	<	* The number of nanoseconds for which it is faster to spin
427	<	* rather than to use timed park. A rough estimate suffices.
428	<	*/
100	<	static final long spinForTimeoutThreshold = 1000L;
425	>	// CAS methods for fields
426	>	final boolean casNext(Node cmp, Node val) {
427	>	return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
428	>	}
429
430	<	/**
431	<	* Node class for LinkedTransferQueue. Opportunistically
432	<	* subclasses from AtomicReference to represent item. Uses Object,
433	<	* not E, to allow setting item to "this" after use, to avoid
106	<	* garbage retention. Similarly, setting the next field to this is
107	<	* used as sentinel that node is off list.
108	<	*/
109	<	static final class Node<E> extends AtomicReference<Object> {
110	<	volatile Node<E> next;
111	<	volatile Thread waiter;       // to control park/unpark
112	<	final boolean isData;
430	>	final boolean casItem(Object cmp, Object val) {
431	>	// assert cmp == null || cmp.getClass() != Node.class;
432	>	return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
433	>	}
434
435	<	Node(E item, boolean isData) {
436	<	super(item);
435	>	/**
436	>	* Constructs a new node.  Uses relaxed write because item can
437	>	* only be seen after publication via casNext.
438	>	*/
439	>	Node(Object item, boolean isData) {
440	>	UNSAFE.putObject(this, itemOffset, item); // relaxed write
441		this.isData = isData;
442		}
443
444	<	// Unsafe mechanics
444	>	/**
445	>	* Links node to itself to avoid garbage retention.  Called
446	>	* only after CASing head field, so uses relaxed write.
447	>	*/
448	>	final void forgetNext() {
449	>	UNSAFE.putObject(this, nextOffset, this);
450	>	}
451
452	<	private static final sun.misc.Unsafe UNSAFE = getUnsafe();
453	<	private static final long nextOffset =
454	<	objectFieldOffset(UNSAFE, "next", Node.class);
452	>	/**
453	>	* Sets item to self and waiter to null, to avoid garbage
454	>	* retention after matching or cancelling. Uses relaxed writes
455	>	* because order is already constrained in the only calling
456	>	* contexts: item is forgotten only after volatile/atomic
457	>	* mechanics that extract items.  Similarly, clearing waiter
458	>	* follows either CAS or return from park (if ever parked;
459	>	* else we don't care).
460	>	*/
461	>	final void forgetContents() {
462	>	UNSAFE.putObject(this, itemOffset, this);
463	>	UNSAFE.putObject(this, waiterOffset, null);
464	>	}
465
466	<	final boolean casNext(Node<E> cmp, Node<E> val) {
467	<	return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
466	>	/**
467	>	* Returns true if this node has been matched, including the
468	>	* case of artificial matches due to cancellation.
469	>	*/
470	>	final boolean isMatched() {
471	>	Object x = item;
472	>	return (x == this) || ((x == null) == isData);
473	>	}
474	>
475	>	/**
476	>	* Returns true if this is an unmatched request node.
477	>	*/
478	>	final boolean isUnmatchedRequest() {
479	>	return !isData && item == null;
480		}
481
482	<	final void clearNext() {
483	<	UNSAFE.putOrderedObject(this, nextOffset, this);
482	>	/**
483	>	* Returns true if a node with the given mode cannot be
484	>	* appended to this node because this node is unmatched and
485	>	* has opposite data mode.
486	>	*/
487	>	final boolean cannotPrecede(boolean haveData) {
488	>	boolean d = isData;
489	>	Object x;
490	>	return d != haveData && (x = item) != this && (x != null) == d;
491		}
492
493		/**
494	<	* Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
135	<	* Replace with a simple call to Unsafe.getUnsafe when integrating
136	<	* into a jdk.
137	<	*
138	<	* @return a sun.misc.Unsafe
494	>	* Tries to artificially match a data node -- used by remove.
495		*/
496	<	private static sun.misc.Unsafe getUnsafe() {
497	<	try {
498	<	return sun.misc.Unsafe.getUnsafe();
499	<	} catch (SecurityException se) {
500	<	try {
501	<	return java.security.AccessController.doPrivileged
146	<	(new java.security
147	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
148	<	public sun.misc.Unsafe run() throws Exception {
149	<	java.lang.reflect.Field f = sun.misc
150	<	.Unsafe.class.getDeclaredField("theUnsafe");
151	<	f.setAccessible(true);
152	<	return (sun.misc.Unsafe) f.get(null);
153	<	}});
154	<	} catch (java.security.PrivilegedActionException e) {
155	<	throw new RuntimeException("Could not initialize intrinsics",
156	<	e.getCause());
157	<	}
496	>	final boolean tryMatchData() {
497	>	// assert isData;
498	>	Object x = item;
499	>	if (x != null && x != this && casItem(x, null)) {
500	>	LockSupport.unpark(waiter);
501	>	return true;
502		}
503	+	return false;
504		}
505
506		private static final long serialVersionUID = -3375979862319811754L;
162	–	}
507
508	<	/**
509	<	* Padded version of AtomicReference used for head, tail and
510	<	* cleanMe, to alleviate contention across threads CASing one vs
511	<	* the other.
512	<	*/
513	<	static final class PaddedAtomicReference<T> extends AtomicReference<T> {
514	<	// enough padding for 64bytes with 4byte refs
515	<	Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
516	<	PaddedAtomicReference(T r) { super(r); }
517	<	private static final long serialVersionUID = 8170090609809740854L;
508	>	// Unsafe mechanics
509	>	private static final sun.misc.Unsafe UNSAFE;
510	>	private static final long itemOffset;
511	>	private static final long nextOffset;
512	>	private static final long waiterOffset;
513	>	static {
514	>	try {
515	>	UNSAFE = getUnsafe();
516	>	Class<?> k = Node.class;
517	>	itemOffset = UNSAFE.objectFieldOffset
518	>	(k.getDeclaredField("item"));
519	>	nextOffset = UNSAFE.objectFieldOffset
520	>	(k.getDeclaredField("next"));
521	>	waiterOffset = UNSAFE.objectFieldOffset
522	>	(k.getDeclaredField("waiter"));
523	>	} catch (Exception e) {
524	>	throw new Error(e);
525	>	}
526	>	}
527		}
528
529	+	/** head of the queue; null until first enqueue */
530	+	transient volatile Node head;
531
532	<	/** head of the queue */
533	<	private transient final PaddedAtomicReference<Node<E>> head;
532	>	/** tail of the queue; null until first append */
533	>	private transient volatile Node tail;
534
535	<	/** tail of the queue */
536	<	private transient final PaddedAtomicReference<Node<E>> tail;
535	>	/** The number of apparent failures to unsplice removed nodes */
536	>	private transient volatile int sweepVotes;
537
538	<	/**
539	<	* Reference to a cancelled node that might not yet have been
540	<	* unlinked from queue because it was the last inserted node
541	<	* when it cancelled.
187	<	*/
188	<	private transient final PaddedAtomicReference<Node<E>> cleanMe;
538	>	// CAS methods for fields
539	>	private boolean casTail(Node cmp, Node val) {
540	>	return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
541	>	}
542
543	<	/**
544	<	* Tries to cas nh as new head; if successful, unlink
545	<	* old head's next node to avoid garbage retention.
543	>	private boolean casHead(Node cmp, Node val) {
544	>	return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
545	>	}
546	>
547	>	private boolean casSweepVotes(int cmp, int val) {
548	>	return UNSAFE.compareAndSwapInt(this, sweepVotesOffset, cmp, val);
549	>	}
550	>
551	>	/*
552	>	* Possible values for "how" argument in xfer method.
553		*/
554	<	private boolean advanceHead(Node<E> h, Node<E> nh) {
555	<	if (h == head.get() && head.compareAndSet(h, nh)) {
556	<	h.clearNext(); // forget old next
557	<	return true;
558	<	}
559	<	return false;
554	>	private static final int NOW   = 0; // for untimed poll, tryTransfer
555	>	private static final int ASYNC = 1; // for offer, put, add
556	>	private static final int SYNC  = 2; // for transfer, take
557	>	private static final int TIMED = 3; // for timed poll, tryTransfer
558	>
559	>	@SuppressWarnings("unchecked")
560	>	static <E> E cast(Object item) {
561	>	// assert item == null || item.getClass() != Node.class;
562	>	return (E) item;
563		}
564
565		/**
566	<	* Puts or takes an item. Used for most queue operations (except
567	<	* poll() and tryTransfer()). See the similar code in
568	<	* SynchronousQueue for detailed explanation.
569	<	*
570	<	* @param e the item or if null, signifies that this is a take
571	<	* @param mode the wait mode: NOWAIT, TIMEOUT, WAIT
572	<	* @param nanos timeout in nanosecs, used only if mode is TIMEOUT
573	<	* @return an item, or null on failure
574	<	*/
575	<	private E xfer(E e, int mode, long nanos) {
576	<	boolean isData = (e != null);
577	<	Node<E> s = null;
578	<	final PaddedAtomicReference<Node<E>> head = this.head;
216	<	final PaddedAtomicReference<Node<E>> tail = this.tail;
217	<
218	<	for (;;) {
219	<	Node<E> t = tail.get();
220	<	Node<E> h = head.get();
566	>	* Implements all queuing methods. See above for explanation.
567	>	*
568	>	* @param e the item or null for take
569	>	* @param haveData true if this is a put, else a take
570	>	* @param how NOW, ASYNC, SYNC, or TIMED
571	>	* @param nanos timeout in nanosecs, used only if mode is TIMED
572	>	* @return an item if matched, else e
573	>	* @throws NullPointerException if haveData mode but e is null
574	>	*/
575	>	private E xfer(E e, boolean haveData, int how, long nanos) {
576	>	if (haveData && (e == null))
577	>	throw new NullPointerException();
578	>	Node s = null;                        // the node to append, if needed
579
580	<	if (t != null && (t == h || t.isData == isData)) {
581	<	if (s == null)
224	<	s = new Node<E>(e, isData);
225	<	Node<E> last = t.next;
226	<	if (last != null) {
227	<	if (t == tail.get())
228	<	tail.compareAndSet(t, last);
229	<	}
230	<	else if (t.casNext(null, s)) {
231	<	tail.compareAndSet(t, s);
232	<	return awaitFulfill(t, s, e, mode, nanos);
233	<	}
234	<	}
580	>	retry:
581	>	for (;;) {                            // restart on append race
582
583	<	else if (h != null) {
584	<	Node<E> first = h.next;
585	<	if (t == tail.get() && first != null &&
586	<	advanceHead(h, first)) {
587	<	Object x = first.get();
588	<	if (x != first && first.compareAndSet(x, e)) {
589	<	LockSupport.unpark(first.waiter);
590	<	return isData ? e : (E) x;
583	>	for (Node h = head, p = h; p != null;) { // find & match first node
584	>	boolean isData = p.isData;
585	>	Object item = p.item;
586	>	if (item != p && (item != null) == isData) { // unmatched
587	>	if (isData == haveData)   // can't match
588	>	break;
589	>	if (p.casItem(item, e)) { // match
590	>	for (Node q = p; q != h;) {
591	>	Node n = q.next;  // update by 2 unless singleton
592	>	if (head == h && casHead(h, n == null ? q : n)) {
593	>	h.forgetNext();
594	>	break;
595	>	}                 // advance and retry
596	>	if ((h = head)   == null ||
597	>	(q = h.next) == null || !q.isMatched())
598	>	break;        // unless slack < 2
599	>	}
600	>	LockSupport.unpark(p.waiter);
601	>	return LinkedTransferQueue.<E>cast(item);
602		}
603		}
604	+	Node n = p.next;
605	+	p = (p != n) ? n : (h = head); // Use head if p offlist
606		}
607	+
608	+	if (how != NOW) {                 // No matches available
609	+	if (s == null)
610	+	s = new Node(e, haveData);
611	+	Node pred = tryAppend(s, haveData);
612	+	if (pred == null)
613	+	continue retry;           // lost race vs opposite mode
614	+	if (how != ASYNC)
615	+	return awaitMatch(s, pred, e, (how == TIMED), nanos);
616	+	}
617	+	return e; // not waiting
618		}
619		}
620
250	–
621		/**
622	<	* Version of xfer for poll() and tryTransfer, which
623	<	* simplifies control paths both here and in xfer.
624	<	*/
625	<	private E fulfill(E e) {
626	<	boolean isData = (e != null);
627	<	final PaddedAtomicReference<Node<E>> head = this.head;
628	<	final PaddedAtomicReference<Node<E>> tail = this.tail;
629	<
630	<	for (;;) {
631	<	Node<E> t = tail.get();
632	<	Node<E> h = head.get();
633	<
634	<	if (t != null && (t == h || t.isData == isData)) {
635	<	Node<E> last = t.next;
636	<	if (t == tail.get()) {
637	<	if (last != null)
638	<	tail.compareAndSet(t, last);
639	<	else
640	<	return null;
641	<	}
642	<	}
643	<	else if (h != null) {
644	<	Node<E> first = h.next;
645	<	if (t == tail.get() &&
646	<	first != null &&
647	<	advanceHead(h, first)) {
648	<	Object x = first.get();
649	<	if (x != first && first.compareAndSet(x, e)) {
280	<	LockSupport.unpark(first.waiter);
281	<	return isData ? e : (E) x;
282	<	}
622	>	* Tries to append node s as tail.
623	>	*
624	>	* @param s the node to append
625	>	* @param haveData true if appending in data mode
626	>	* @return null on failure due to losing race with append in
627	>	* different mode, else s's predecessor, or s itself if no
628	>	* predecessor
629	>	*/
630	>	private Node tryAppend(Node s, boolean haveData) {
631	>	for (Node t = tail, p = t;;) {        // move p to last node and append
632	>	Node n, u;                        // temps for reads of next & tail
633	>	if (p == null && (p = head) == null) {
634	>	if (casHead(null, s))
635	>	return s;                 // initialize
636	>	}
637	>	else if (p.cannotPrecede(haveData))
638	>	return null;                  // lost race vs opposite mode
639	>	else if ((n = p.next) != null)    // not last; keep traversing
640	>	p = p != t && t != (u = tail) ? (t = u) : // stale tail
641	>	(p != n) ? n : null;      // restart if off list
642	>	else if (!p.casNext(null, s))
643	>	p = p.next;                   // re-read on CAS failure
644	>	else {
645	>	if (p != t) {                 // update if slack now >= 2
646	>	while ((tail != t || !casTail(t, s)) &&
647	>	(t = tail)   != null &&
648	>	(s = t.next) != null && // advance and retry
649	>	(s = s.next) != null && s != t);
650		}
651	+	return p;
652		}
653		}
654		}
655
656		/**
657	<	* Spins/blocks until node s is fulfilled or caller gives up,
290	<	* depending on wait mode.
657	>	* Spins/yields/blocks until node s is matched or caller gives up.
658		*
292	–	* @param pred the predecessor of waiting node
659		* @param s the waiting node
660	+	* @param pred the predecessor of s, or s itself if it has no
661	+	* predecessor, or null if unknown (the null case does not occur
662	+	* in any current calls but may in possible future extensions)
663		* @param e the comparison value for checking match
664	<	* @param mode mode
665	<	* @param nanos timeout value
666	<	* @return matched item, or s if cancelled
667	<	*/
668	<	private E awaitFulfill(Node<E> pred, Node<E> s, E e,
669	<	int mode, long nanos) {
301	<	if (mode == NOWAIT)
302	<	return null;
303	<
304	<	long lastTime = (mode == TIMEOUT) ? System.nanoTime() : 0;
664	>	* @param timed if true, wait only until timeout elapses
665	>	* @param nanos timeout in nanosecs, used only if timed is true
666	>	* @return matched item, or e if unmatched on interrupt or timeout
667	>	*/
668	>	private E awaitMatch(Node s, Node pred, E e, boolean timed, long nanos) {
669	>	long lastTime = timed ? System.nanoTime() : 0L;
670		Thread w = Thread.currentThread();
671	<	int spins = -1; // set to desired spin count below
671	>	int spins = -1; // initialized after first item and cancel checks
672	>	ThreadLocalRandom randomYields = null; // bound if needed
673	>
674		for (;;) {
675	<	if (w.isInterrupted())
676	<	s.compareAndSet(e, s);
677	<	Object x = s.get();
678	<	if (x != e) {                 // Node was matched or cancelled
679	<	advanceHead(pred, s);     // unlink if head
680	<	if (x == s) {             // was cancelled
681	<	clean(pred, s);
682	<	return null;
683	<	}
684	<	else if (x != null) {
685	<	s.set(s);             // avoid garbage retention
686	<	return (E) x;
687	<	}
688	<	else
689	<	return e;
675	>	Object item = s.item;
676	>	if (item != e) {                  // matched
677	>	// assert item != s;
678	>	s.forgetContents();           // avoid garbage
679	>	return LinkedTransferQueue.<E>cast(item);
680	>	}
681	>	if ((w.isInterrupted() || (timed && nanos <= 0L)) &&
682	>	s.casItem(e, s)) {        // cancel
683	>	unsplice(pred, s);
684	>	return e;
685	>	}
686	>
687	>	if (spins < 0) {                  // establish spins at/near front
688	>	if ((spins = spinsFor(pred, s.isData)) > 0)
689	>	randomYields = ThreadLocalRandom.current();
690	>	}
691	>	else if (spins > 0) {             // spin
692	>	--spins;
693	>	if (randomYields.nextInt(CHAINED_SPINS) == 0)
694	>	Thread.yield();           // occasionally yield
695		}
696	<	if (mode == TIMEOUT) {
696	>	else if (s.waiter == null) {
697	>	s.waiter = w;                 // request unpark then recheck
698	>	}
699	>	else if (timed) {
700		long now = System.nanoTime();
701	<	nanos -= now - lastTime;
701	>	if ((nanos -= now - lastTime) > 0)
702	>	LockSupport.parkNanos(this, nanos);
703		lastTime = now;
328	–	if (nanos <= 0) {
329	–	s.compareAndSet(e, s); // try to cancel
330	–	continue;
331	–	}
332	–	}
333	–	if (spins < 0) {
334	–	Node<E> h = head.get(); // only spin if at head
335	–	spins = ((h != null && h.next == s) ?
336	–	((mode == TIMEOUT) ?
337	–	maxTimedSpins : maxUntimedSpins) : 0);
704		}
705	<	if (spins > 0)
340	<	--spins;
341	<	else if (s.waiter == null)
342	<	s.waiter = w;
343	<	else if (mode != TIMEOUT) {
705	>	else {
706		LockSupport.park(this);
345	–	s.waiter = null;
346	–	spins = -1;
347	–	}
348	–	else if (nanos > spinForTimeoutThreshold) {
349	–	LockSupport.parkNanos(this, nanos);
350	–	s.waiter = null;
351	–	spins = -1;
707		}
708		}
709		}
710
711		/**
712	<	* Returns validated tail for use in cleaning methods.
712	>	* Returns spin/yield value for a node with given predecessor and
713	>	* data mode. See above for explanation.
714		*/
715	<	private Node<E> getValidatedTail() {
716	<	for (;;) {
717	<	Node<E> h = head.get();
718	<	Node<E> first = h.next;
719	<	if (first != null && first.next == first) { // help advance
720	<	advanceHead(h, first);
721	<	continue;
722	<	}
367	<	Node<E> t = tail.get();
368	<	Node<E> last = t.next;
369	<	if (t == tail.get()) {
370	<	if (last != null)
371	<	tail.compareAndSet(t, last); // help advance
372	<	else
373	<	return t;
374	<	}
715	>	private static int spinsFor(Node pred, boolean haveData) {
716	>	if (MP && pred != null) {
717	>	if (pred.isData != haveData)      // phase change
718	>	return FRONT_SPINS + CHAINED_SPINS;
719	>	if (pred.isMatched())             // probably at front
720	>	return FRONT_SPINS;
721	>	if (pred.waiter == null)          // pred apparently spinning
722	>	return CHAINED_SPINS;
723		}
724	+	return 0;
725		}
726
727	+	/* -------------- Traversal methods -------------- */
728	+
729		/**
730	<	* Gets rid of cancelled node s with original predecessor pred.
731	<	*
732	<	* @param pred predecessor of cancelled node
733	<	* @param s the cancelled node
730	>	* Returns the successor of p, or the head node if p.next has been
731	>	* linked to self, which will only be true if traversing with a
732	>	* stale pointer that is now off the list.
733	>	*/
734	>	final Node succ(Node p) {
735	>	Node next = p.next;
736	>	return (p == next) ? head : next;
737	>	}
738	>
739	>	/**
740	>	* Returns the first unmatched node of the given mode, or null if
741	>	* none.  Used by methods isEmpty, hasWaitingConsumer.
742		*/
743	<	private void clean(Node<E> pred, Node<E> s) {
744	<	Thread w = s.waiter;
745	<	if (w != null) {             // Wake up thread
746	<	s.waiter = null;
747	<	if (w != Thread.currentThread())
748	<	LockSupport.unpark(w);
743	>	private Node firstOfMode(boolean isData) {
744	>	for (Node p = head; p != null; p = succ(p)) {
745	>	if (!p.isMatched())
746	>	return (p.isData == isData) ? p : null;
747	>	}
748	>	return null;
749	>	}
750	>
751	>	/**
752	>	* Returns the item in the first unmatched node with isData; or
753	>	* null if none.  Used by peek.
754	>	*/
755	>	private E firstDataItem() {
756	>	for (Node p = head; p != null; p = succ(p)) {
757	>	Object item = p.item;
758	>	if (p.isData) {
759	>	if (item != null && item != p)
760	>	return LinkedTransferQueue.<E>cast(item);
761	>	}
762	>	else if (item == null)
763	>	return null;
764		}
765	+	return null;
766	+	}
767
768	<	if (pred == null)
769	<	return;
768	>	/**
769	>	* Traverses and counts unmatched nodes of the given mode.
770	>	* Used by methods size and getWaitingConsumerCount.
771	>	*/
772	>	private int countOfMode(boolean data) {
773	>	int count = 0;
774	>	for (Node p = head; p != null; ) {
775	>	if (!p.isMatched()) {
776	>	if (p.isData != data)
777	>	return 0;
778	>	if (++count == Integer.MAX_VALUE) // saturated
779	>	break;
780	>	}
781	>	Node n = p.next;
782	>	if (n != p)
783	>	p = n;
784	>	else {
785	>	count = 0;
786	>	p = head;
787	>	}
788	>	}
789	>	return count;
790	>	}
791	>
792	>	final class Itr implements Iterator<E> {
793	>	private Node nextNode;   // next node to return item for
794	>	private E nextItem;      // the corresponding item
795	>	private Node lastRet;    // last returned node, to support remove
796	>	private Node lastPred;   // predecessor to unlink lastRet
797
798	<	/*
799	<	* At any given time, exactly one node on list cannot be
397	<	* deleted -- the last inserted node. To accommodate this, if
398	<	* we cannot delete s, we save its predecessor as "cleanMe",
399	<	* processing the previously saved version first. At least one
400	<	* of node s or the node previously saved can always be
401	<	* processed, so this always terminates.
798	>	/**
799	>	* Moves to next node after prev, or first node if prev null.
800		*/
801	<	while (pred.next == s) {
802	<	Node<E> oldpred = reclean();  // First, help get rid of cleanMe
803	<	Node<E> t = getValidatedTail();
804	<	if (s != t) {               // If not tail, try to unsplice
805	<	Node<E> sn = s.next;      // s.next == s means s already off list
806	<	if (sn == s || pred.casNext(s, sn))
801	>	private void advance(Node prev) {
802	>	/*
803	>	* To track and avoid buildup of deleted nodes in the face
804	>	* of calls to both Queue.remove and Itr.remove, we must
805	>	* include variants of unsplice and sweep upon each
806	>	* advance: Upon Itr.remove, we may need to catch up links
807	>	* from lastPred, and upon other removes, we might need to
808	>	* skip ahead from stale nodes and unsplice deleted ones
809	>	* found while advancing.
810	>	*/
811	>
812	>	Node r, b; // reset lastPred upon possible deletion of lastRet
813	>	if ((r = lastRet) != null && !r.isMatched())
814	>	lastPred = r;    // next lastPred is old lastRet
815	>	else if ((b = lastPred) == null || b.isMatched())
816	>	lastPred = null; // at start of list
817	>	else {
818	>	Node s, n;       // help with removal of lastPred.next
819	>	while ((s = b.next) != null &&
820	>	s != b && s.isMatched() &&
821	>	(n = s.next) != null && n != s)
822	>	b.casNext(s, n);
823	>	}
824	>
825	>	this.lastRet = prev;
826	>
827	>	for (Node p = prev, s, n;;) {
828	>	s = (p == null) ? head : p.next;
829	>	if (s == null)
830		break;
831	+	else if (s == p) {
832	+	p = null;
833	+	continue;
834	+	}
835	+	Object item = s.item;
836	+	if (s.isData) {
837	+	if (item != null && item != s) {
838	+	nextItem = LinkedTransferQueue.<E>cast(item);
839	+	nextNode = s;
840	+	return;
841	+	}
842	+	}
843	+	else if (item == null)
844	+	break;
845	+	// assert s.isMatched();
846	+	if (p == null)
847	+	p = s;
848	+	else if ((n = s.next) == null)
849	+	break;
850	+	else if (s == n)
851	+	p = null;
852	+	else
853	+	p.casNext(s, n);
854		}
855	<	else if (oldpred == pred || // Already saved
856	<	(oldpred == null && cleanMe.compareAndSet(null, pred)))
857	<	break;                  // Postpone cleaning
855	>	nextNode = null;
856	>	nextItem = null;
857	>	}
858	>
859	>	Itr() {
860	>	advance(null);
861	>	}
862	>
863	>	public final boolean hasNext() {
864	>	return nextNode != null;
865	>	}
866	>
867	>	public final E next() {
868	>	Node p = nextNode;
869	>	if (p == null) throw new NoSuchElementException();
870	>	E e = nextItem;
871	>	advance(p);
872	>	return e;
873	>	}
874	>
875	>	public final void remove() {
876	>	final Node lastRet = this.lastRet;
877	>	if (lastRet == null)
878	>	throw new IllegalStateException();
879	>	this.lastRet = null;
880	>	if (lastRet.tryMatchData())
881	>	unsplice(lastPred, lastRet);
882		}
883		}
884
885	+	/* -------------- Removal methods -------------- */
886	+
887		/**
888	<	* Tries to unsplice the cancelled node held in cleanMe that was
889	<	* previously uncleanable because it was at tail.
888	>	* Unsplices (now or later) the given deleted/cancelled node with
889	>	* the given predecessor.
890		*
891	<	* @return current cleanMe node (or null)
891	>	* @param pred a node that was at one time known to be the
892	>	* predecessor of s, or null or s itself if s is/was at head
893	>	* @param s the node to be unspliced
894		*/
895	<	private Node<E> reclean() {
895	>	final void unsplice(Node pred, Node s) {
896	>	s.forgetContents(); // forget unneeded fields
897		/*
898	<	* cleanMe is, or at one time was, predecessor of cancelled
899	<	* node s that was the tail so could not be unspliced.  If s
900	<	* is no longer the tail, try to unsplice if necessary and
901	<	* make cleanMe slot available.  This differs from similar
902	<	* code in clean() because we must check that pred still
430	<	* points to a cancelled node that must be unspliced -- if
431	<	* not, we can (must) clear cleanMe without unsplicing.
432	<	* This can loop only due to contention on casNext or
433	<	* clearing cleanMe.
898	>	* See above for rationale. Briefly: if pred still points to
899	>	* s, try to unlink s.  If s cannot be unlinked, because it is
900	>	* trailing node or pred might be unlinked, and neither pred
901	>	* nor s are head or offlist, add to sweepVotes, and if enough
902	>	* votes have accumulated, sweep.
903		*/
904	<	Node<E> pred;
905	<	while ((pred = cleanMe.get()) != null) {
906	<	Node<E> t = getValidatedTail();
907	<	Node<E> s = pred.next;
908	<	if (s != t) {
909	<	Node<E> sn;
910	<	if (s == null || s == pred || s.get() != s ||
911	<	(sn = s.next) == s || pred.casNext(s, sn))
912	<	cleanMe.compareAndSet(pred, null);
904	>	if (pred != null && pred != s && pred.next == s) {
905	>	Node n = s.next;
906	>	if (n == null ||
907	>	(n != s && pred.casNext(s, n) && pred.isMatched())) {
908	>	for (;;) {               // check if at, or could be, head
909	>	Node h = head;
910	>	if (h == pred || h == s || h == null)
911	>	return;          // at head or list empty
912	>	if (!h.isMatched())
913	>	break;
914	>	Node hn = h.next;
915	>	if (hn == null)
916	>	return;          // now empty
917	>	if (hn != h && casHead(h, hn))
918	>	h.forgetNext();  // advance head
919	>	}
920	>	if (pred.next != pred && s.next != s) { // recheck if offlist
921	>	for (;;) {           // sweep now if enough votes
922	>	int v = sweepVotes;
923	>	if (v < SWEEP_THRESHOLD) {
924	>	if (casSweepVotes(v, v + 1))
925	>	break;
926	>	}
927	>	else if (casSweepVotes(v, 0)) {
928	>	sweep();
929	>	break;
930	>	}
931	>	}
932	>	}
933		}
934	<	else // s is still tail; cannot clean
934	>	}
935	>	}
936	>
937	>	/**
938	>	* Unlinks matched (typically cancelled) nodes encountered in a
939	>	* traversal from head.
940	>	*/
941	>	private void sweep() {
942	>	for (Node p = head, s, n; p != null && (s = p.next) != null; ) {
943	>	if (!s.isMatched())
944	>	// Unmatched nodes are never self-linked
945	>	p = s;
946	>	else if ((n = s.next) == null) // trailing node is pinned
947		break;
948	+	else if (s == n)    // stale
949	+	// No need to also check for p == s, since that implies s == n
950	+	p = head;
951	+	else
952	+	p.casNext(s, n);
953		}
448	–	return pred;
954		}
955
956		/**
957	+	* Main implementation of remove(Object)
958	+	*/
959	+	private boolean findAndRemove(Object e) {
960	+	if (e != null) {
961	+	for (Node pred = null, p = head; p != null; ) {
962	+	Object item = p.item;
963	+	if (p.isData) {
964	+	if (item != null && item != p && e.equals(item) &&
965	+	p.tryMatchData()) {
966	+	unsplice(pred, p);
967	+	return true;
968	+	}
969	+	}
970	+	else if (item == null)
971	+	break;
972	+	pred = p;
973	+	if ((p = p.next) == pred) { // stale
974	+	pred = null;
975	+	p = head;
976	+	}
977	+	}
978	+	}
979	+	return false;
980	+	}
981	+
982	+
983	+	/**
984		* Creates an initially empty {@code LinkedTransferQueue}.
985		*/
986		public LinkedTransferQueue() {
455	–	Node<E> dummy = new Node<E>(null, false);
456	–	head = new PaddedAtomicReference<Node<E>>(dummy);
457	–	tail = new PaddedAtomicReference<Node<E>>(dummy);
458	–	cleanMe = new PaddedAtomicReference<Node<E>>(null);
987		}
988
989		/**
#	Line 479 | Line 1007 | public class LinkedTransferQueue<E> exte
1007		* @throws NullPointerException if the specified element is null
1008		*/
1009		public void put(E e) {
1010	<	offer(e);
1010	>	xfer(e, true, ASYNC, 0);
1011		}
1012
1013		/**
#	Line 488 | Line 1016 | public class LinkedTransferQueue<E> exte
1016		* return {@code false}.
1017		*
1018		* @return {@code true} (as specified by
1019	<	*  {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer})
1019	>	*  {@link java.util.concurrent.BlockingQueue#offer(Object,long,TimeUnit)
1020	>	*  BlockingQueue.offer})
1021		* @throws NullPointerException if the specified element is null
1022		*/
1023		public boolean offer(E e, long timeout, TimeUnit unit) {
1024	<	return offer(e);
1024	>	xfer(e, true, ASYNC, 0);
1025	>	return true;
1026		}
1027
1028		/**
1029		* Inserts the specified element at the tail of this queue.
1030		* As the queue is unbounded, this method will never return {@code false}.
1031		*
1032	<	* @return {@code true} (as specified by
503	<	*         {@link BlockingQueue#offer(Object) BlockingQueue.offer})
1032	>	* @return {@code true} (as specified by {@link Queue#offer})
1033		* @throws NullPointerException if the specified element is null
1034		*/
1035		public boolean offer(E e) {
1036	<	if (e == null) throw new NullPointerException();
508	<	xfer(e, NOWAIT, 0);
1036	>	xfer(e, true, ASYNC, 0);
1037		return true;
1038		}
1039
1040		/**
1041		* Inserts the specified element at the tail of this queue.
1042	<	* As the queue is unbounded this method will never throw
1042	>	* As the queue is unbounded, this method will never throw
1043		* {@link IllegalStateException} or return {@code false}.
1044		*
1045		* @return {@code true} (as specified by {@link Collection#add})
1046		* @throws NullPointerException if the specified element is null
1047		*/
1048		public boolean add(E e) {
1049	<	return offer(e);
1049	>	xfer(e, true, ASYNC, 0);
1050	>	return true;
1051		}
1052
1053		/**
1054	<	* Transfers the specified element immediately if there exists a
1055	<	* consumer already waiting to receive it (in {@link #take} or
1056	<	* timed {@link #poll(long,TimeUnit) poll}), otherwise
1057	<	* returning {@code false} without enqueuing the element.
1054	>	* Transfers the element to a waiting consumer immediately, if possible.
1055	>	*
1056	>	* <p>More precisely, transfers the specified element immediately
1057	>	* if there exists a consumer already waiting to receive it (in
1058	>	* {@link #take} or timed {@link #poll(long,TimeUnit) poll}),
1059	>	* otherwise returning {@code false} without enqueuing the element.
1060		*
1061		* @throws NullPointerException if the specified element is null
1062		*/
1063		public boolean tryTransfer(E e) {
1064	<	if (e == null) throw new NullPointerException();
534	<	return fulfill(e) != null;
1064	>	return xfer(e, true, NOW, 0) == null;
1065		}
1066
1067		/**
1068	<	* Inserts the specified element at the tail of this queue,
1069	<	* waiting if necessary for the element to be received by a
1070	<	* consumer invoking {@code take} or {@code poll}.
1068	>	* Transfers the element to a consumer, waiting if necessary to do so.
1069	>	*
1070	>	* <p>More precisely, transfers the specified element immediately
1071	>	* if there exists a consumer already waiting to receive it (in
1072	>	* {@link #take} or timed {@link #poll(long,TimeUnit) poll}),
1073	>	* else inserts the specified element at the tail of this queue
1074	>	* and waits until the element is received by a consumer.
1075		*
1076		* @throws NullPointerException if the specified element is null
1077		*/
1078		public void transfer(E e) throws InterruptedException {
1079	<	if (e == null) throw new NullPointerException();
1080	<	if (xfer(e, WAIT, 0) == null) {
547	<	Thread.interrupted();
1079	>	if (xfer(e, true, SYNC, 0) != null) {
1080	>	Thread.interrupted(); // failure possible only due to interrupt
1081		throw new InterruptedException();
1082		}
1083		}
1084
1085		/**
1086	<	* Inserts the specified element at the tail of this queue,
1087	<	* waiting up to the specified wait time for the element to be
1088	<	* received by a consumer invoking {@code take} or {@code poll}.
1086	>	* Transfers the element to a consumer if it is possible to do so
1087	>	* before the timeout elapses.
1088	>	*
1089	>	* <p>More precisely, transfers the specified element immediately
1090	>	* if there exists a consumer already waiting to receive it (in
1091	>	* {@link #take} or timed {@link #poll(long,TimeUnit) poll}),
1092	>	* else inserts the specified element at the tail of this queue
1093	>	* and waits until the element is received by a consumer,
1094	>	* returning {@code false} if the specified wait time elapses
1095	>	* before the element can be transferred.
1096		*
1097		* @throws NullPointerException if the specified element is null
1098		*/
1099		public boolean tryTransfer(E e, long timeout, TimeUnit unit)
1100		throws InterruptedException {
1101	<	if (e == null) throw new NullPointerException();
562	<	if (xfer(e, TIMEOUT, unit.toNanos(timeout)) != null)
1101	>	if (xfer(e, true, TIMED, unit.toNanos(timeout)) == null)
1102		return true;
1103		if (!Thread.interrupted())
1104		return false;
#	Line 567 | Line 1106 | public class LinkedTransferQueue<E> exte
1106		}
1107
1108		public E take() throws InterruptedException {
1109	<	E e = xfer(null, WAIT, 0);
1109	>	E e = xfer(null, false, SYNC, 0);
1110		if (e != null)
1111		return e;
1112		Thread.interrupted();
#	Line 575 | Line 1114 | public class LinkedTransferQueue<E> exte
1114		}
1115
1116		public E poll(long timeout, TimeUnit unit) throws InterruptedException {
1117	<	E e = xfer(null, TIMEOUT, unit.toNanos(timeout));
1117	>	E e = xfer(null, false, TIMED, unit.toNanos(timeout));
1118		if (e != null || !Thread.interrupted())
1119		return e;
1120		throw new InterruptedException();
1121		}
1122
1123		public E poll() {
1124	<	return fulfill(null);
1124	>	return xfer(null, false, NOW, 0);
1125		}
1126
1127		/**
#	Line 595 | Line 1134 | public class LinkedTransferQueue<E> exte
1134		if (c == this)
1135		throw new IllegalArgumentException();
1136		int n = 0;
1137	<	E e;
599	<	while ( (e = poll()) != null) {
1137	>	for (E e; (e = poll()) != null;) {
1138		c.add(e);
1139		++n;
1140		}
#	Line 613 | Line 1151 | public class LinkedTransferQueue<E> exte
1151		if (c == this)
1152		throw new IllegalArgumentException();
1153		int n = 0;
1154	<	E e;
617	<	while (n < maxElements && (e = poll()) != null) {
1154	>	for (E e; n < maxElements && (e = poll()) != null;) {
1155		c.add(e);
1156		++n;
1157		}
1158		return n;
1159		}
1160
624	–	// Traversal-based methods
625	–
626	–	/**
627	–	* Returns head after performing any outstanding helping steps.
628	–	*/
629	–	private Node<E> traversalHead() {
630	–	for (;;) {
631	–	Node<E> t = tail.get();
632	–	Node<E> h = head.get();
633	–	if (h != null && t != null) {
634	–	Node<E> last = t.next;
635	–	Node<E> first = h.next;
636	–	if (t == tail.get()) {
637	–	if (last != null)
638	–	tail.compareAndSet(t, last);
639	–	else if (first != null) {
640	–	Object x = first.get();
641	–	if (x == first)
642	–	advanceHead(h, first);
643	–	else
644	–	return h;
645	–	}
646	–	else
647	–	return h;
648	–	}
649	–	}
650	–	reclean();
651	–	}
652	–	}
653	–
1161		/**
1162	<	* Returns an iterator over the elements in this queue in proper
1163	<	* sequence, from head to tail.
1162	>	* Returns an iterator over the elements in this queue in proper sequence.
1163	>	* The elements will be returned in order from first (head) to last (tail).
1164		*
1165		* <p>The returned iterator is a "weakly consistent" iterator that
1166	<	* will never throw
1167	<	* {@link ConcurrentModificationException ConcurrentModificationException},
1168	<	* and guarantees to traverse elements as they existed upon
1169	<	* construction of the iterator, and may (but is not guaranteed
1170	<	* to) reflect any modifications subsequent to construction.
1166	>	* will never throw {@link java.util.ConcurrentModificationException
1167	>	* ConcurrentModificationException}, and guarantees to traverse
1168	>	* elements as they existed upon construction of the iterator, and
1169	>	* may (but is not guaranteed to) reflect any modifications
1170	>	* subsequent to construction.
1171		*
1172		* @return an iterator over the elements in this queue in proper sequence
1173		*/
#	Line 668 | Line 1175 | public class LinkedTransferQueue<E> exte
1175		return new Itr();
1176		}
1177
671	–	/**
672	–	* Iterators. Basic strategy is to traverse list, treating
673	–	* non-data (i.e., request) nodes as terminating list.
674	–	* Once a valid data node is found, the item is cached
675	–	* so that the next call to next() will return it even
676	–	* if subsequently removed.
677	–	*/
678	–	class Itr implements Iterator<E> {
679	–	Node<E> next;        // node to return next
680	–	Node<E> pnext;       // predecessor of next
681	–	Node<E> curr;        // last returned node, for remove()
682	–	Node<E> pcurr;       // predecessor of curr, for remove()
683	–	E nextItem;          // Cache of next item, once committed to in next
684	–
685	–	Itr() {
686	–	advance();
687	–	}
688	–
689	–	/**
690	–	* Moves to next valid node and returns item to return for
691	–	* next(), or null if no such.
692	–	*/
693	–	private E advance() {
694	–	pcurr = pnext;
695	–	curr = next;
696	–	E item = nextItem;
697	–
698	–	for (;;) {
699	–	pnext = (next == null) ? traversalHead() : next;
700	–	next = pnext.next;
701	–	if (next == pnext) {
702	–	next = null;
703	–	continue;  // restart
704	–	}
705	–	if (next == null)
706	–	break;
707	–	Object x = next.get();
708	–	if (x != null && x != next) {
709	–	nextItem = (E) x;
710	–	break;
711	–	}
712	–	}
713	–	return item;
714	–	}
715	–
716	–	public boolean hasNext() {
717	–	return next != null;
718	–	}
719	–
720	–	public E next() {
721	–	if (next == null)
722	–	throw new NoSuchElementException();
723	–	return advance();
724	–	}
725	–
726	–	public void remove() {
727	–	Node<E> p = curr;
728	–	if (p == null)
729	–	throw new IllegalStateException();
730	–	Object x = p.get();
731	–	if (x != null && x != p && p.compareAndSet(x, p))
732	–	clean(pcurr, p);
733	–	}
734	–	}
735	–
1178		public E peek() {
1179	<	for (;;) {
738	<	Node<E> h = traversalHead();
739	<	Node<E> p = h.next;
740	<	if (p == null)
741	<	return null;
742	<	Object x = p.get();
743	<	if (p != x) {
744	<	if (!p.isData)
745	<	return null;
746	<	if (x != null)
747	<	return (E) x;
748	<	}
749	<	}
1179	>	return firstDataItem();
1180		}
1181
1182	+	/**
1183	+	* Returns {@code true} if this queue contains no elements.
1184	+	*
1185	+	* @return {@code true} if this queue contains no elements
1186	+	*/
1187		public boolean isEmpty() {
1188	<	for (;;) {
1189	<	Node<E> h = traversalHead();
1190	<	Node<E> p = h.next;
756	<	if (p == null)
757	<	return true;
758	<	Object x = p.get();
759	<	if (p != x) {
760	<	if (!p.isData)
761	<	return true;
762	<	if (x != null)
763	<	return false;
764	<	}
1188	>	for (Node p = head; p != null; p = succ(p)) {
1189	>	if (!p.isMatched())
1190	>	return !p.isData;
1191		}
1192	+	return true;
1193		}
1194
1195		public boolean hasWaitingConsumer() {
1196	<	for (;;) {
770	<	Node<E> h = traversalHead();
771	<	Node<E> p = h.next;
772	<	if (p == null)
773	<	return false;
774	<	Object x = p.get();
775	<	if (p != x)
776	<	return !p.isData;
777	<	}
1196	>	return firstOfMode(false) != null;
1197		}
1198
1199		/**
#	Line 790 | Line 1209 | public class LinkedTransferQueue<E> exte
1209		* @return the number of elements in this queue
1210		*/
1211		public int size() {
1212	<	for (;;) {
794	<	int count = 0;
795	<	Node<E> pred = traversalHead();
796	<	for (;;) {
797	<	Node<E> q = pred.next;
798	<	if (q == pred) // restart
799	<	break;
800	<	if (q == null || !q.isData)
801	<	return count;
802	<	Object x = q.get();
803	<	if (x != null && x != q) {
804	<	if (++count == Integer.MAX_VALUE) // saturated
805	<	return count;
806	<	}
807	<	pred = q;
808	<	}
809	<	}
1212	>	return countOfMode(true);
1213		}
1214
1215		public int getWaitingConsumerCount() {
1216	<	// converse of size -- count valid non-data nodes
814	<	for (;;) {
815	<	int count = 0;
816	<	Node<E> pred = traversalHead();
817	<	for (;;) {
818	<	Node<E> q = pred.next;
819	<	if (q == pred) // restart
820	<	break;
821	<	if (q == null || q.isData)
822	<	return count;
823	<	Object x = q.get();
824	<	if (x == null) {
825	<	if (++count == Integer.MAX_VALUE) // saturated
826	<	return count;
827	<	}
828	<	pred = q;
829	<	}
830	<	}
1216	>	return countOfMode(false);
1217		}
1218
1219	+	/**
1220	+	* Removes a single instance of the specified element from this queue,
1221	+	* if it is present.  More formally, removes an element {@code e} such
1222	+	* that {@code o.equals(e)}, if this queue contains one or more such
1223	+	* elements.
1224	+	* Returns {@code true} if this queue contained the specified element
1225	+	* (or equivalently, if this queue changed as a result of the call).
1226	+	*
1227	+	* @param o element to be removed from this queue, if present
1228	+	* @return {@code true} if this queue changed as a result of the call
1229	+	*/
1230		public boolean remove(Object o) {
1231	<	if (o == null)
1232	<	return false;
1233	<	for (;;) {
1234	<	Node<E> pred = traversalHead();
1235	<	for (;;) {
1236	<	Node<E> q = pred.next;
1237	<	if (q == pred) // restart
1238	<	break;
1239	<	if (q == null || !q.isData)
1240	<	return false;
1241	<	Object x = q.get();
1242	<	if (x != null && x != q && o.equals(x) &&
1243	<	q.compareAndSet(x, q)) {
1244	<	clean(pred, q);
1231	>	return findAndRemove(o);
1232	>	}
1233	>
1234	>	/**
1235	>	* Returns {@code true} if this queue contains the specified element.
1236	>	* More formally, returns {@code true} if and only if this queue contains
1237	>	* at least one element {@code e} such that {@code o.equals(e)}.
1238	>	*
1239	>	* @param o object to be checked for containment in this queue
1240	>	* @return {@code true} if this queue contains the specified element
1241	>	*/
1242	>	public boolean contains(Object o) {
1243	>	if (o == null) return false;
1244	>	for (Node p = head; p != null; p = succ(p)) {
1245	>	Object item = p.item;
1246	>	if (p.isData) {
1247	>	if (item != null && item != p && o.equals(item))
1248		return true;
849	–	}
850	–	pred = q;
1249		}
1250	+	else if (item == null)
1251	+	break;
1252		}
1253	+	return false;
1254		}
1255
1256		/**
#	Line 857 | Line 1258 | public class LinkedTransferQueue<E> exte
1258		* {@code LinkedTransferQueue} is not capacity constrained.
1259		*
1260		* @return {@code Integer.MAX_VALUE} (as specified by
1261	<	*         {@link BlockingQueue#remainingCapacity()})
1261	>	*         {@link java.util.concurrent.BlockingQueue#remainingCapacity()
1262	>	*         BlockingQueue.remainingCapacity})
1263		*/
1264		public int remainingCapacity() {
1265		return Integer.MAX_VALUE;
1266		}
1267
1268		/**
1269	<	* Save the state to a stream (that is, serialize it).
1269	>	* Saves the state to a stream (that is, serializes it).
1270		*
1271		* @serialData All of the elements (each an {@code E}) in
1272		* the proper order, followed by a null
#	Line 880 | Line 1282 | public class LinkedTransferQueue<E> exte
1282		}
1283
1284		/**
1285	<	* Reconstitute the Queue instance from a stream (that is,
1286	<	* deserialize it).
1285	>	* Reconstitutes the Queue instance from a stream (that is,
1286	>	* deserializes it).
1287		*
1288		* @param s the stream
1289		*/
1290		private void readObject(java.io.ObjectInputStream s)
1291		throws java.io.IOException, ClassNotFoundException {
1292		s.defaultReadObject();
891	–	resetHeadAndTail();
1293		for (;;) {
1294	<	@SuppressWarnings("unchecked") E item = (E) s.readObject();
1294	>	@SuppressWarnings("unchecked")
1295	>	E item = (E) s.readObject();
1296		if (item == null)
1297		break;
1298		else
#	Line 898 | Line 1300 | public class LinkedTransferQueue<E> exte
1300		}
1301		}
1302
901	–	// Support for resetting head/tail while deserializing
902	–	private void resetHeadAndTail() {
903	–	Node<E> dummy = new Node<E>(null, false);
904	–	UNSAFE.putObjectVolatile(this, headOffset,
905	–	new PaddedAtomicReference<Node<E>>(dummy));
906	–	UNSAFE.putObjectVolatile(this, tailOffset,
907	–	new PaddedAtomicReference<Node<E>>(dummy));
908	–	UNSAFE.putObjectVolatile(this, cleanMeOffset,
909	–	new PaddedAtomicReference<Node<E>>(null));
910	–	}
911	–
1303		// Unsafe mechanics
1304
1305	<	private static final sun.misc.Unsafe UNSAFE = getUnsafe();
1306	<	private static final long headOffset =
1307	<	objectFieldOffset(UNSAFE, "head", LinkedTransferQueue.class);
1308	<	private static final long tailOffset =
1309	<	objectFieldOffset(UNSAFE, "tail", LinkedTransferQueue.class);
919	<	private static final long cleanMeOffset =
920	<	objectFieldOffset(UNSAFE, "cleanMe", LinkedTransferQueue.class);
921	<
922	<
923	<	static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
924	<	String field, Class<?> klazz) {
1305	>	private static final sun.misc.Unsafe UNSAFE;
1306	>	private static final long headOffset;
1307	>	private static final long tailOffset;
1308	>	private static final long sweepVotesOffset;
1309	>	static {
1310		try {
1311	<	return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
1312	<	} catch (NoSuchFieldException e) {
1313	<	// Convert Exception to corresponding Error
1314	<	NoSuchFieldError error = new NoSuchFieldError(field);
1315	<	error.initCause(e);
1316	<	throw error;
1311	>	UNSAFE = getUnsafe();
1312	>	Class<?> k = LinkedTransferQueue.class;
1313	>	headOffset = UNSAFE.objectFieldOffset
1314	>	(k.getDeclaredField("head"));
1315	>	tailOffset = UNSAFE.objectFieldOffset
1316	>	(k.getDeclaredField("tail"));
1317	>	sweepVotesOffset = UNSAFE.objectFieldOffset
1318	>	(k.getDeclaredField("sweepVotes"));
1319	>	} catch (Exception e) {
1320	>	throw new Error(e);
1321		}
1322		}
1323
#	Line 939 | Line 1328 | public class LinkedTransferQueue<E> exte
1328		*
1329		* @return a sun.misc.Unsafe
1330		*/
1331	<	private static sun.misc.Unsafe getUnsafe() {
1331	>	static sun.misc.Unsafe getUnsafe() {
1332		try {
1333		return sun.misc.Unsafe.getUnsafe();
1334	<	} catch (SecurityException se) {
1335	<	try {
1336	<	return java.security.AccessController.doPrivileged
1337	<	(new java.security
1338	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1339	<	public sun.misc.Unsafe run() throws Exception {
1340	<	java.lang.reflect.Field f = sun.misc
1341	<	.Unsafe.class.getDeclaredField("theUnsafe");
1342	<	f.setAccessible(true);
1343	<	return (sun.misc.Unsafe) f.get(null);
1344	<	}});
1345	<	} catch (java.security.PrivilegedActionException e) {
1346	<	throw new RuntimeException("Could not initialize intrinsics",
1347	<	e.getCause());
1348	<	}
1334	>	} catch (SecurityException tryReflectionInstead) {}
1335	>	try {
1336	>	return java.security.AccessController.doPrivileged
1337	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1338	>	public sun.misc.Unsafe run() throws Exception {
1339	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1340	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1341	>	f.setAccessible(true);
1342	>	Object x = f.get(null);
1343	>	if (k.isInstance(x))
1344	>	return k.cast(x);
1345	>	}
1346	>	throw new NoSuchFieldError("the Unsafe");
1347	>	}});
1348	>	} catch (java.security.PrivilegedActionException e) {
1349	>	throw new RuntimeException("Could not initialize intrinsics",
1350	>	e.getCause());
1351		}
1352		}
1353		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines