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.8 by dl, Fri Oct 3 00:39:48 2008 UTC vs.
Revision 1.35 by jsr166, Thu Jul 30 22:45:39 2009 UTC

#	Line 5 | Line 5
5		*/
6
7		package jsr166y;
8	+
9		import java.util.concurrent.*;
10	<	import java.util.concurrent.locks.*;
11	<	import java.util.concurrent.atomic.*;
12	<	import java.util.*;
13	<	import java.io.*;
14	<	import sun.misc.Unsafe;
15	<	import java.lang.reflect.*;
10	>
11	>	import java.util.AbstractQueue;
12	>	import java.util.Collection;
13	>	import java.util.ConcurrentModificationException;
14	>	import java.util.Iterator;
15	>	import java.util.NoSuchElementException;
16	>	import java.util.Queue;
17	>	import java.util.concurrent.locks.LockSupport;
18	>	import java.util.concurrent.atomic.AtomicReference;
19
20		/**
21		* An unbounded {@linkplain TransferQueue} based on linked nodes.
#	Line 21 | Line 25 | import java.lang.reflect.*;
25		* producer.  The <em>tail</em> of the queue is that element that has
26		* been on the queue the shortest time for some producer.
27		*
28	<	* <p>Beware that, unlike in most collections, the <tt>size</tt>
28	>	* <p>Beware that, unlike in most collections, the {@code size}
29		* method is <em>NOT</em> a constant-time operation. Because of the
30		* asynchronous nature of these queues, determining the current number
31		* of elements requires a traversal of the elements.
#	Line 44 | Line 48 | import java.lang.reflect.*;
48		* @since 1.7
49		* @author Doug Lea
50		* @param <E> the type of elements held in this collection
47	–	*
51		*/
52		public class LinkedTransferQueue<E> extends AbstractQueue<E>
53		implements TransferQueue<E>, java.io.Serializable {
54		private static final long serialVersionUID = -3223113410248163686L;
55
56		/*
54	–	* This is still a work in progress...
55	–	*
57		* 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)
62		*
63	<	* The main extension is to provide different Wait modes
64	<	* for the main "xfer" method that puts or takes items.
65	<	* These don't impact the basic dual-queue logic, but instead
66	<	* control whether or how threads block upon insertion
67	<	* of request or data nodes into the dual queue.
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
#	Line 81 | Line 84 | public class LinkedTransferQueue<E> exte
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;
87	>	static final int maxTimedSpins = (NCPUS < 2) ? 0 : 32;
88
89		/**
90		* The number of times to spin before blocking in untimed waits.
#	Line 97 | Line 100 | public class LinkedTransferQueue<E> exte
100		static final long spinForTimeoutThreshold = 1000L;
101
102		/**
103	<	* Node class for LinkedTransferQueue. Opportunistically subclasses from
104	<	* AtomicReference to represent item. Uses Object, not E, to allow
105	<	* setting item to "this" after use, to avoid garbage
106	<	* retention. Similarly, setting the next field to this is used as
107	<	* sentinel that node is off list.
103	>	* Node class for LinkedTransferQueue. Opportunistically
104	>	* subclasses from AtomicReference to represent item. Uses Object,
105	>	* 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 QNode extends AtomicReference<Object> {
110	<	volatile QNode next;
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;
113	<	QNode(Object item, boolean isData) {
113	>
114	>	Node(E item, boolean isData) {
115		super(item);
116		this.isData = isData;
117		}
118
119	<	static final AtomicReferenceFieldUpdater<QNode, QNode>
116	<	nextUpdater = AtomicReferenceFieldUpdater.newUpdater
117	<	(QNode.class, QNode.class, "next");
119	>	// Unsafe mechanics
120
121	<	boolean casNext(QNode cmp, QNode val) {
122	<	return nextUpdater.compareAndSet(this, cmp, val);
121	>	private static final sun.misc.Unsafe UNSAFE = getUnsafe();
122	>	private static final long nextOffset =
123	>	objectFieldOffset(UNSAFE, "next", Node.class);
124	>
125	>	final boolean casNext(Node<E> cmp, Node<E> val) {
126	>	return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
127	>	}
128	>
129	>	final void clearNext() {
130	>	UNSAFE.putOrderedObject(this, nextOffset, this);
131	>	}
132	>
133	>	/**
134	>	* 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
139	>	*/
140	>	private static sun.misc.Unsafe getUnsafe() {
141	>	try {
142	>	return sun.misc.Unsafe.getUnsafe();
143	>	} catch (SecurityException se) {
144	>	try {
145	>	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	>	}
158	>	}
159		}
160	+
161	+	private static final long serialVersionUID = -3375979862319811754L;
162		}
163
164		/**
#	Line 130 | Line 170 | public class LinkedTransferQueue<E> exte
170		// enough padding for 64bytes with 4byte refs
171		Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
172		PaddedAtomicReference(T r) { super(r); }
173	+	private static final long serialVersionUID = 8170090609809740854L;
174		}
175
176
177		/** head of the queue */
178	<	private transient final PaddedAtomicReference<QNode> head;
178	>	private transient final PaddedAtomicReference<Node<E>> head;
179	>
180		/** tail of the queue */
181	<	private transient final PaddedAtomicReference<QNode> tail;
181	>	private transient final PaddedAtomicReference<Node<E>> tail;
182
183		/**
184		* Reference to a cancelled node that might not yet have been
185		* unlinked from queue because it was the last inserted node
186		* when it cancelled.
187		*/
188	<	private transient final PaddedAtomicReference<QNode> cleanMe;
188	>	private transient final PaddedAtomicReference<Node<E>> cleanMe;
189
190		/**
191		* Tries to cas nh as new head; if successful, unlink
192		* old head's next node to avoid garbage retention.
193		*/
194	<	private boolean advanceHead(QNode h, QNode nh) {
194	>	private boolean advanceHead(Node<E> h, Node<E> nh) {
195		if (h == head.get() && head.compareAndSet(h, nh)) {
196	<	h.next = h; // forget old next
196	>	h.clearNext(); // forget old next
197		return true;
198		}
199		return false;
#	Line 159 | Line 201 | public class LinkedTransferQueue<E> exte
201
202		/**
203		* Puts or takes an item. Used for most queue operations (except
204	<	* poll() and tryTransfer())
204	>	* poll() and tryTransfer()). See the similar code in
205	>	* SynchronousQueue for detailed explanation.
206	>	*
207		* @param e the item or if null, signifies that this is a take
208		* @param mode the wait mode: NOWAIT, TIMEOUT, WAIT
209		* @param nanos timeout in nanosecs, used only if mode is TIMEOUT
210		* @return an item, or null on failure
211		*/
212	<	private Object xfer(Object e, int mode, long nanos) {
212	>	private E xfer(E e, int mode, long nanos) {
213		boolean isData = (e != null);
214	<	QNode s = null;
215	<	final PaddedAtomicReference<QNode> head = this.head;
216	<	final PaddedAtomicReference<QNode> tail = this.tail;
214	>	Node<E> s = null;
215	>	final PaddedAtomicReference<Node<E>> head = this.head;
216	>	final PaddedAtomicReference<Node<E>> tail = this.tail;
217
218		for (;;) {
219	<	QNode t = tail.get();
220	<	QNode h = head.get();
219	>	Node<E> t = tail.get();
220	>	Node<E> h = head.get();
221
222		if (t != null && (t == h || t.isData == isData)) {
223		if (s == null)
224	<	s = new QNode(e, isData);
225	<	QNode last = t.next;
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);
#	Line 190 | Line 234 | public class LinkedTransferQueue<E> exte
234		}
235
236		else if (h != null) {
237	<	QNode first = h.next;
237	>	Node<E> first = h.next;
238		if (t == tail.get() && first != null &&
239		advanceHead(h, first)) {
240		Object x = first.get();
241		if (x != first && first.compareAndSet(x, e)) {
242		LockSupport.unpark(first.waiter);
243	<	return isData? e : x;
243	>	return isData ? e : (E) x;
244		}
245		}
246		}
#	Line 206 | Line 250 | public class LinkedTransferQueue<E> exte
250
251		/**
252		* Version of xfer for poll() and tryTransfer, which
253	<	* simplifies control paths both here and in xfer
253	>	* simplifies control paths both here and in xfer.
254		*/
255	<	private Object fulfill(Object e) {
255	>	private E fulfill(E e) {
256		boolean isData = (e != null);
257	<	final PaddedAtomicReference<QNode> head = this.head;
258	<	final PaddedAtomicReference<QNode> tail = this.tail;
257	>	final PaddedAtomicReference<Node<E>> head = this.head;
258	>	final PaddedAtomicReference<Node<E>> tail = this.tail;
259
260		for (;;) {
261	<	QNode t = tail.get();
262	<	QNode h = head.get();
261	>	Node<E> t = tail.get();
262	>	Node<E> h = head.get();
263
264		if (t != null && (t == h || t.isData == isData)) {
265	<	QNode last = t.next;
265	>	Node<E> last = t.next;
266		if (t == tail.get()) {
267		if (last != null)
268		tail.compareAndSet(t, last);
#	Line 227 | Line 271 | public class LinkedTransferQueue<E> exte
271		}
272		}
273		else if (h != null) {
274	<	QNode first = h.next;
274	>	Node<E> first = h.next;
275		if (t == tail.get() &&
276		first != null &&
277		advanceHead(h, first)) {
278		Object x = first.get();
279		if (x != first && first.compareAndSet(x, e)) {
280		LockSupport.unpark(first.waiter);
281	<	return isData? e : x;
281	>	return isData ? e : (E) x;
282		}
283		}
284		}
#	Line 252 | Line 296 | public class LinkedTransferQueue<E> exte
296		* @param nanos timeout value
297		* @return matched item, or s if cancelled
298		*/
299	<	private Object awaitFulfill(QNode pred, QNode s, Object e,
300	<	int mode, long nanos) {
299	>	private E awaitFulfill(Node<E> pred, Node<E> s, E e,
300	>	int mode, long nanos) {
301		if (mode == NOWAIT)
302		return null;
303
304	<	long lastTime = (mode == TIMEOUT)? System.nanoTime() : 0;
304	>	long lastTime = (mode == TIMEOUT) ? System.nanoTime() : 0;
305		Thread w = Thread.currentThread();
306		int spins = -1; // set to desired spin count below
307		for (;;) {
#	Line 266 | Line 310 | public class LinkedTransferQueue<E> exte
310		Object x = s.get();
311		if (x != e) {                 // Node was matched or cancelled
312		advanceHead(pred, s);     // unlink if head
313	<	if (x == s)               // was cancelled
314	<	return clean(pred, s);
313	>	if (x == s) {             // was cancelled
314	>	clean(pred, s);
315	>	return null;
316	>	}
317		else if (x != null) {
318		s.set(s);             // avoid garbage retention
319	<	return x;
319	>	return (E) x;
320		}
321		else
322		return e;
323		}
278	–
324		if (mode == TIMEOUT) {
325		long now = System.nanoTime();
326		nanos -= now - lastTime;
#	Line 286 | Line 331 | public class LinkedTransferQueue<E> exte
331		}
332		}
333		if (spins < 0) {
334	<	QNode h = head.get(); // only spin if at head
334	>	Node<E> h = head.get(); // only spin if at head
335		spins = ((h != null && h.next == s) ?
336	<	(mode == TIMEOUT?
336	>	((mode == TIMEOUT) ?
337		maxTimedSpins : maxUntimedSpins) : 0);
338		}
339		if (spins > 0)
#	Line 296 | Line 341 | public class LinkedTransferQueue<E> exte
341		else if (s.waiter == null)
342		s.waiter = w;
343		else if (mode != TIMEOUT) {
344	<	//                LockSupport.park(this);
300	<	LockSupport.park(); // allows run on java5
344	>	LockSupport.park(this);
345		s.waiter = null;
346		spins = -1;
347		}
348		else if (nanos > spinForTimeoutThreshold) {
349	<	//                LockSupport.parkNanos(this, nanos);
306	<	LockSupport.parkNanos(nanos);
349	>	LockSupport.parkNanos(this, nanos);
350		s.waiter = null;
351		spins = -1;
352		}
#	Line 311 | Line 354 | public class LinkedTransferQueue<E> exte
354		}
355
356		/**
357	+	* Returns validated tail for use in cleaning methods.
358	+	*/
359	+	private Node<E> getValidatedTail() {
360	+	for (;;) {
361	+	Node<E> h = head.get();
362	+	Node<E> first = h.next;
363	+	if (first != null && first.next == first) { // help advance
364	+	advanceHead(h, first);
365	+	continue;
366	+	}
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	+	}
375	+	}
376	+	}
377	+
378	+	/**
379		* Gets rid of cancelled node s with original predecessor pred.
380	<	* @return null (to simplify use by callers)
380	>	*
381	>	* @param pred predecessor of cancelled node
382	>	* @param s the cancelled node
383		*/
384	<	private Object clean(QNode pred, QNode s) {
384	>	private void clean(Node<E> pred, Node<E> s) {
385		Thread w = s.waiter;
386		if (w != null) {             // Wake up thread
387		s.waiter = null;
#	Line 322 | Line 389 | public class LinkedTransferQueue<E> exte
389		LockSupport.unpark(w);
390		}
391
392	<	for (;;) {
393	<	if (pred.next != s) // already cleaned
394	<	return null;
395	<	QNode h = head.get();
396	<	QNode hn = h.next;   // Absorb cancelled first node as head
397	<	if (hn != null && hn.next == hn) {
398	<	advanceHead(h, hn);
399	<	continue;
400	<	}
401	<	QNode t = tail.get();      // Ensure consistent read for tail
402	<	if (t == h)
403	<	return null;
404	<	QNode tn = t.next;
405	<	if (t != tail.get())
406	<	continue;
407	<	if (tn != null) {          // Help advance tail
341	<	tail.compareAndSet(t, tn);
342	<	continue;
343	<	}
344	<	if (s != t) {             // If not tail, try to unsplice
345	<	QNode sn = s.next;
392	>	if (pred == null)
393	>	return;
394	>
395	>	/*
396	>	* 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.
402	>	*/
403	>	while (pred.next == s) {
404	>	Node<E> oldpred = reclean();  // First, help get rid of cleanMe
405	>	Node<E> t = getValidatedTail();
406	>	if (s != t) {               // If not tail, try to unsplice
407	>	Node<E> sn = s.next;      // s.next == s means s already off list
408		if (sn == s || pred.casNext(s, sn))
409	<	return null;
409	>	break;
410		}
411	<	QNode dp = cleanMe.get();
412	<	if (dp != null) {    // Try unlinking previous cancelled node
413	<	QNode d = dp.next;
414	<	QNode dn;
415	<	if (d == null ||               // d is gone or
416	<	d == dp ||                 // d is off list or
417	<	d.get() != d ||            // d not cancelled or
418	<	(d != t &&                 // d not tail and
419	<	(dn = d.next) != null &&  //   has successor
420	<	dn != d &&                //   that is on list
421	<	dp.casNext(d, dn)))       // d unspliced
422	<	cleanMe.compareAndSet(dp, null);
423	<	if (dp == pred)
424	<	return null;      // s is already saved node
411	>	else if (oldpred == pred || // Already saved
412	>	(oldpred == null && cleanMe.compareAndSet(null, pred)))
413	>	break;                  // Postpone cleaning
414	>	}
415	>	}
416	>
417	>	/**
418	>	* Tries to unsplice the cancelled node held in cleanMe that was
419	>	* previously uncleanable because it was at tail.
420	>	*
421	>	* @return current cleanMe node (or null)
422	>	*/
423	>	private Node<E> reclean() {
424	>	/*
425	>	* cleanMe is, or at one time was, predecessor of cancelled
426	>	* node s that was the tail so could not be unspliced.  If s
427	>	* is no longer the tail, try to unsplice if necessary and
428	>	* make cleanMe slot available.  This differs from similar
429	>	* 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.
434	>	*/
435	>	Node<E> pred;
436	>	while ((pred = cleanMe.get()) != null) {
437	>	Node<E> t = getValidatedTail();
438	>	Node<E> s = pred.next;
439	>	if (s != t) {
440	>	Node<E> sn;
441	>	if (s == null || s == pred || s.get() != s ||
442	>	(sn = s.next) == s || pred.casNext(s, sn))
443	>	cleanMe.compareAndSet(pred, null);
444		}
445	<	else if (cleanMe.compareAndSet(null, pred))
446	<	return null;          // Postpone cleaning s
445	>	else // s is still tail; cannot clean
446	>	break;
447		}
448	+	return pred;
449		}
450
451		/**
452	<	* Creates an initially empty <tt>LinkedTransferQueue</tt>.
452	>	* Creates an initially empty {@code LinkedTransferQueue}.
453		*/
454		public LinkedTransferQueue() {
455	<	QNode dummy = new QNode(null, false);
456	<	head = new PaddedAtomicReference<QNode>(dummy);
457	<	tail = new PaddedAtomicReference<QNode>(dummy);
458	<	cleanMe = new PaddedAtomicReference<QNode>(null);
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);
459		}
460
461		/**
462	<	* Creates a <tt>LinkedTransferQueue</tt>
462	>	* Creates a {@code LinkedTransferQueue}
463		* initially containing the elements of the given collection,
464		* added in traversal order of the collection's iterator.
465	+	*
466		* @param c the collection of elements to initially contain
467		* @throws NullPointerException if the specified collection or any
468		*         of its elements are null
#	Line 389 | Line 472 | public class LinkedTransferQueue<E> exte
472		addAll(c);
473		}
474
475	<	public void put(E e) throws InterruptedException {
476	<	if (e == null) throw new NullPointerException();
477	<	if (Thread.interrupted()) throw new InterruptedException();
478	<	xfer(e, NOWAIT, 0);
475	>	/**
476	>	* Inserts the specified element at the tail of this queue.
477	>	* As the queue is unbounded, this method will never block.
478	>	*
479	>	* @throws NullPointerException if the specified element is null
480	>	*/
481	>	public void put(E e) {
482	>	offer(e);
483		}
484
485	<	public boolean offer(E e, long timeout, TimeUnit unit)
486	<	throws InterruptedException {
487	<	if (e == null) throw new NullPointerException();
488	<	if (Thread.interrupted()) throw new InterruptedException();
489	<	xfer(e, NOWAIT, 0);
490	<	return true;
485	>	/**
486	>	* Inserts the specified element at the tail of this queue.
487	>	* As the queue is unbounded, this method will never block or
488	>	* return {@code false}.
489	>	*
490	>	* @return {@code true} (as specified by
491	>	*  {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer})
492	>	* @throws NullPointerException if the specified element is null
493	>	*/
494	>	public boolean offer(E e, long timeout, TimeUnit unit) {
495	>	return offer(e);
496		}
497
498	+	/**
499	+	* Inserts the specified element at the tail of this queue.
500	+	* As the queue is unbounded, this method will never return {@code false}.
501	+	*
502	+	* @return {@code true} (as specified by
503	+	*         {@link BlockingQueue#offer(Object) BlockingQueue.offer})
504	+	* @throws NullPointerException if the specified element is null
505	+	*/
506		public boolean offer(E e) {
507		if (e == null) throw new NullPointerException();
508		xfer(e, NOWAIT, 0);
509		return true;
510		}
511
512	+	/**
513	+	* Inserts the specified element at the tail of this queue.
514	+	* As the queue is unbounded this method will never throw
515	+	* {@link IllegalStateException} or return {@code false}.
516	+	*
517	+	* @return {@code true} (as specified by {@link Collection#add})
518	+	* @throws NullPointerException if the specified element is null
519	+	*/
520	+	public boolean add(E e) {
521	+	return offer(e);
522	+	}
523	+
524	+	/**
525	+	* Transfers the specified element immediately if there exists a
526	+	* consumer already waiting to receive it (in {@link #take} or
527	+	* timed {@link #poll(Object,long,TimeUnit) poll}), otherwise
528	+	* returning {@code false} without enqueuing the element.
529	+	*
530	+	* @throws NullPointerException if the specified element is null
531	+	*/
532	+	public boolean tryTransfer(E e) {
533	+	if (e == null) throw new NullPointerException();
534	+	return fulfill(e) != null;
535	+	}
536	+
537	+	/**
538	+	* Inserts the specified element at the tail of this queue,
539	+	* waiting if necessary for the element to be received by a
540	+	* consumer invoking {@code take} or {@code poll}.
541	+	*
542	+	* @throws InterruptedException {@inheritDoc}
543	+	* @throws NullPointerException if the specified element is null
544	+	*/
545		public void transfer(E e) throws InterruptedException {
546		if (e == null) throw new NullPointerException();
547		if (xfer(e, WAIT, 0) == null) {
#	Line 417 | Line 550 | public class LinkedTransferQueue<E> exte
550		}
551		}
552
553	+	/**
554	+	* Inserts the specified element at the tail of this queue,
555	+	* waiting up to the specified wait time for the element to be
556	+	* received by a consumer invoking {@code take} or {@code poll}.
557	+	*
558	+	* @throws InterruptedException {@inheritDoc}
559	+	* @throws NullPointerException if the specified element is null
560	+	*/
561		public boolean tryTransfer(E e, long timeout, TimeUnit unit)
562		throws InterruptedException {
563		if (e == null) throw new NullPointerException();
#	Line 427 | Line 568 | public class LinkedTransferQueue<E> exte
568		throw new InterruptedException();
569		}
570
430	–	public boolean tryTransfer(E e) {
431	–	if (e == null) throw new NullPointerException();
432	–	return fulfill(e) != null;
433	–	}
434	–
571		public E take() throws InterruptedException {
572	<	Object e = xfer(null, WAIT, 0);
572	>	E e = xfer(null, WAIT, 0);
573		if (e != null)
574	<	return (E)e;
574	>	return e;
575		Thread.interrupted();
576		throw new InterruptedException();
577		}
578
579	+	/**
580	+	* @throws InterruptedException {@inheritDoc}
581	+	*/
582		public E poll(long timeout, TimeUnit unit) throws InterruptedException {
583	<	Object e = xfer(null, TIMEOUT, unit.toNanos(timeout));
583	>	E e = xfer(null, TIMEOUT, unit.toNanos(timeout));
584		if (e != null || !Thread.interrupted())
585	<	return (E)e;
585	>	return e;
586		throw new InterruptedException();
587		}
588
589		public E poll() {
590	<	return (E)fulfill(null);
590	>	return fulfill(null);
591		}
592
593	+	/**
594	+	* @throws NullPointerException     {@inheritDoc}
595	+	* @throws IllegalArgumentException {@inheritDoc}
596	+	*/
597		public int drainTo(Collection<? super E> c) {
598		if (c == null)
599		throw new NullPointerException();
#	Line 465 | Line 608 | public class LinkedTransferQueue<E> exte
608		return n;
609		}
610
611	+	/**
612	+	* @throws NullPointerException     {@inheritDoc}
613	+	* @throws IllegalArgumentException {@inheritDoc}
614	+	*/
615		public int drainTo(Collection<? super E> c, int maxElements) {
616		if (c == null)
617		throw new NullPointerException();
#	Line 482 | Line 629 | public class LinkedTransferQueue<E> exte
629		// Traversal-based methods
630
631		/**
632	<	* Return head after performing any outstanding helping steps
632	>	* Returns head after performing any outstanding helping steps.
633		*/
634	<	private QNode traversalHead() {
634	>	private Node<E> traversalHead() {
635		for (;;) {
636	<	QNode t = tail.get();
637	<	QNode h = head.get();
636	>	Node<E> t = tail.get();
637	>	Node<E> h = head.get();
638		if (h != null && t != null) {
639	<	QNode last = t.next;
640	<	QNode first = h.next;
639	>	Node<E> last = t.next;
640	>	Node<E> first = h.next;
641		if (t == tail.get()) {
642		if (last != null)
643		tail.compareAndSet(t, last);
#	Line 505 | Line 652 | public class LinkedTransferQueue<E> exte
652		return h;
653		}
654		}
655	+	reclean();
656		}
657		}
658
659	<
659	>	/**
660	>	* Returns an iterator over the elements in this queue in proper
661	>	* sequence, from head to tail.
662	>	*
663	>	* <p>The returned iterator is a "weakly consistent" iterator that
664	>	* will never throw
665	>	* {@link ConcurrentModificationException ConcurrentModificationException},
666	>	* and guarantees to traverse elements as they existed upon
667	>	* construction of the iterator, and may (but is not guaranteed
668	>	* to) reflect any modifications subsequent to construction.
669	>	*
670	>	* @return an iterator over the elements in this queue in proper sequence
671	>	*/
672		public Iterator<E> iterator() {
673		return new Itr();
674		}
#	Line 521 | Line 681 | public class LinkedTransferQueue<E> exte
681		* if subsequently removed.
682		*/
683		class Itr implements Iterator<E> {
684	<	QNode nextNode;    // Next node to return next
685	<	QNode currentNode; // last returned node, for remove()
686	<	QNode prevNode;    // predecessor of last returned node
687	<	E nextItem;        // Cache of next item, once commited to in next
684	>	Node<E> next;        // node to return next
685	>	Node<E> pnext;       // predecessor of next
686	>	Node<E> curr;        // last returned node, for remove()
687	>	Node<E> pcurr;       // predecessor of curr, for remove()
688	>	E nextItem;          // Cache of next item, once committed to in next
689
690		Itr() {
530	–	nextNode = traversalHead();
691		advance();
692		}
693
694	<	E advance() {
695	<	prevNode = currentNode;
696	<	currentNode = nextNode;
697	<	E x = nextItem;
694	>	/**
695	>	* Moves to next valid node and returns item to return for
696	>	* next(), or null if no such.
697	>	*/
698	>	private E advance() {
699	>	pcurr = pnext;
700	>	curr = next;
701	>	E item = nextItem;
702
539	–	QNode p = nextNode.next;
703		for (;;) {
704	<	if (p == null || !p.isData) {
705	<	nextNode = null;
706	<	nextItem = null;
707	<	return x;
708	<	}
709	<	Object item = p.get();
710	<	if (item != p && item != null) {
711	<	nextNode = p;
712	<	nextItem = (E)item;
713	<	return x;
704	>	pnext = (next == null) ? traversalHead() : next;
705	>	next = pnext.next;
706	>	if (next == pnext) {
707	>	next = null;
708	>	continue;  // restart
709	>	}
710	>	if (next == null)
711	>	break;
712	>	Object x = next.get();
713	>	if (x != null && x != next) {
714	>	nextItem = (E) x;
715	>	break;
716		}
552	–	prevNode = p;
553	–	p = p.next;
717		}
718	+	return item;
719		}
720
721		public boolean hasNext() {
722	<	return nextNode != null;
722	>	return next != null;
723		}
724
725		public E next() {
726	<	if (nextNode == null) throw new NoSuchElementException();
726	>	if (next == null)
727	>	throw new NoSuchElementException();
728		return advance();
729		}
730
731		public void remove() {
732	<	QNode p = currentNode;
733	<	QNode prev = prevNode;
569	<	if (prev == null || p == null)
732	>	Node<E> p = curr;
733	>	if (p == null)
734		throw new IllegalStateException();
735		Object x = p.get();
736		if (x != null && x != p && p.compareAndSet(x, p))
737	<	clean(prev, p);
737	>	clean(pcurr, p);
738		}
739		}
740
741		public E peek() {
742		for (;;) {
743	<	QNode h = traversalHead();
744	<	QNode p = h.next;
743	>	Node<E> h = traversalHead();
744	>	Node<E> p = h.next;
745		if (p == null)
746		return null;
747		Object x = p.get();
#	Line 585 | Line 749 | public class LinkedTransferQueue<E> exte
749		if (!p.isData)
750		return null;
751		if (x != null)
752	<	return (E)x;
752	>	return (E) x;
753		}
754		}
755		}
756
757		public boolean isEmpty() {
758		for (;;) {
759	<	QNode h = traversalHead();
760	<	QNode p = h.next;
759	>	Node<E> h = traversalHead();
760	>	Node<E> p = h.next;
761		if (p == null)
762		return true;
763		Object x = p.get();
#	Line 608 | Line 772 | public class LinkedTransferQueue<E> exte
772
773		public boolean hasWaitingConsumer() {
774		for (;;) {
775	<	QNode h = traversalHead();
776	<	QNode p = h.next;
775	>	Node<E> h = traversalHead();
776	>	Node<E> p = h.next;
777		if (p == null)
778		return false;
779		Object x = p.get();
#	Line 620 | Line 784 | public class LinkedTransferQueue<E> exte
784
785		/**
786		* Returns the number of elements in this queue.  If this queue
787	<	* contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
788	<	* <tt>Integer.MAX_VALUE</tt>.
787	>	* contains more than {@code Integer.MAX_VALUE} elements, returns
788	>	* {@code Integer.MAX_VALUE}.
789		*
790		* <p>Beware that, unlike in most collections, this method is
791		* <em>NOT</em> a constant-time operation. Because of the
#	Line 631 | Line 795 | public class LinkedTransferQueue<E> exte
795		* @return the number of elements in this queue
796		*/
797		public int size() {
798	<	int count = 0;
799	<	QNode h = traversalHead();
800	<	for (QNode p = h.next; p != null && p.isData; p = p.next) {
801	<	Object x = p.get();
802	<	if (x != null && x != p) {
803	<	if (++count == Integer.MAX_VALUE) // saturated
798	>	for (;;) {
799	>	int count = 0;
800	>	Node<E> pred = traversalHead();
801	>	for (;;) {
802	>	Node<E> q = pred.next;
803	>	if (q == pred) // restart
804		break;
805	+	if (q == null || !q.isData)
806	+	return count;
807	+	Object x = q.get();
808	+	if (x != null && x != q) {
809	+	if (++count == Integer.MAX_VALUE) // saturated
810	+	return count;
811	+	}
812	+	pred = q;
813		}
814		}
643	–	return count;
815		}
816
817		public int getWaitingConsumerCount() {
818	<	int count = 0;
819	<	QNode h = traversalHead();
820	<	for (QNode p = h.next; p != null && !p.isData; p = p.next) {
821	<	if (p.get() == null) {
822	<	if (++count == Integer.MAX_VALUE)
818	>	// converse of size -- count valid non-data nodes
819	>	for (;;) {
820	>	int count = 0;
821	>	Node<E> pred = traversalHead();
822	>	for (;;) {
823	>	Node<E> q = pred.next;
824	>	if (q == pred) // restart
825		break;
826	+	if (q == null || q.isData)
827	+	return count;
828	+	Object x = q.get();
829	+	if (x == null) {
830	+	if (++count == Integer.MAX_VALUE) // saturated
831	+	return count;
832	+	}
833	+	pred = q;
834		}
835		}
655	–	return count;
836		}
837
838	+	public boolean remove(Object o) {
839	+	if (o == null)
840	+	return false;
841	+	for (;;) {
842	+	Node<E> pred = traversalHead();
843	+	for (;;) {
844	+	Node<E> q = pred.next;
845	+	if (q == pred) // restart
846	+	break;
847	+	if (q == null || !q.isData)
848	+	return false;
849	+	Object x = q.get();
850	+	if (x != null && x != q && o.equals(x) &&
851	+	q.compareAndSet(x, q)) {
852	+	clean(pred, q);
853	+	return true;
854	+	}
855	+	pred = q;
856	+	}
857	+	}
858	+	}
859	+
860	+	/**
861	+	* Always returns {@code Integer.MAX_VALUE} because a
862	+	* {@code LinkedTransferQueue} is not capacity constrained.
863	+	*
864	+	* @return {@code Integer.MAX_VALUE} (as specified by
865	+	*         {@link BlockingQueue#remainingCapacity()})
866	+	*/
867		public int remainingCapacity() {
868		return Integer.MAX_VALUE;
869		}
#	Line 662 | Line 871 | public class LinkedTransferQueue<E> exte
871		/**
872		* Save the state to a stream (that is, serialize it).
873		*
874	<	* @serialData All of the elements (each an <tt>E</tt>) in
874	>	* @serialData All of the elements (each an {@code E}) in
875		* the proper order, followed by a null
876		* @param s the stream
877		*/
878		private void writeObject(java.io.ObjectOutputStream s)
879		throws java.io.IOException {
880		s.defaultWriteObject();
881	<	for (Iterator<E> it = iterator(); it.hasNext(); )
882	<	s.writeObject(it.next());
881	>	for (E e : this)
882	>	s.writeObject(e);
883		// Use trailing null as sentinel
884		s.writeObject(null);
885		}
#	Line 678 | Line 887 | public class LinkedTransferQueue<E> exte
887		/**
888		* Reconstitute the Queue instance from a stream (that is,
889		* deserialize it).
890	+	*
891		* @param s the stream
892		*/
893		private void readObject(java.io.ObjectInputStream s)
#	Line 685 | Line 895 | public class LinkedTransferQueue<E> exte
895		s.defaultReadObject();
896		resetHeadAndTail();
897		for (;;) {
898	<	E item = (E)s.readObject();
898	>	@SuppressWarnings("unchecked") E item = (E) s.readObject();
899		if (item == null)
900		break;
901		else
#	Line 693 | Line 903 | public class LinkedTransferQueue<E> exte
903		}
904		}
905
696	–
906		// Support for resetting head/tail while deserializing
907	+	private void resetHeadAndTail() {
908	+	Node<E> dummy = new Node<E>(null, false);
909	+	UNSAFE.putObjectVolatile(this, headOffset,
910	+	new PaddedAtomicReference<Node<E>>(dummy));
911	+	UNSAFE.putObjectVolatile(this, tailOffset,
912	+	new PaddedAtomicReference<Node<E>>(dummy));
913	+	UNSAFE.putObjectVolatile(this, cleanMeOffset,
914	+	new PaddedAtomicReference<Node<E>>(null));
915	+	}
916	+
917	+	// Unsafe mechanics
918	+
919	+	private static final sun.misc.Unsafe UNSAFE = getUnsafe();
920	+	private static final long headOffset =
921	+	objectFieldOffset(UNSAFE, "head", LinkedTransferQueue.class);
922	+	private static final long tailOffset =
923	+	objectFieldOffset(UNSAFE, "tail", LinkedTransferQueue.class);
924	+	private static final long cleanMeOffset =
925	+	objectFieldOffset(UNSAFE, "cleanMe", LinkedTransferQueue.class);
926
927	<	// Temporary Unsafe mechanics for preliminary release
928	<	private static final Unsafe _unsafe;
929	<	private static final long headOffset;
702	<	private static final long tailOffset;
703	<	private static final long cleanMeOffset;
704	<	static {
927	>
928	>	static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
929	>	String field, Class<?> klazz) {
930		try {
931	<	if (LinkedTransferQueue.class.getClassLoader() != null) {
932	<	Field f = Unsafe.class.getDeclaredField("theUnsafe");
933	<	f.setAccessible(true);
934	<	_unsafe = (Unsafe)f.get(null);
935	<	}
936	<	else
712	<	_unsafe = Unsafe.getUnsafe();
713	<	headOffset = _unsafe.objectFieldOffset
714	<	(LinkedTransferQueue.class.getDeclaredField("head"));
715	<	tailOffset = _unsafe.objectFieldOffset
716	<	(LinkedTransferQueue.class.getDeclaredField("tail"));
717	<	cleanMeOffset = _unsafe.objectFieldOffset
718	<	(LinkedTransferQueue.class.getDeclaredField("cleanMe"));
719	<	} catch (Exception e) {
720	<	throw new RuntimeException("Could not initialize intrinsics", e);
931	>	return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
932	>	} catch (NoSuchFieldException e) {
933	>	// Convert Exception to corresponding Error
934	>	NoSuchFieldError error = new NoSuchFieldError(field);
935	>	error.initCause(e);
936	>	throw error;
937		}
938		}
939
940	<	private void resetHeadAndTail() {
941	<	QNode dummy = new QNode(null, false);
942	<	_unsafe.putObjectVolatile(this, headOffset,
943	<	new PaddedAtomicReference<QNode>(dummy));
944	<	_unsafe.putObjectVolatile(this, tailOffset,
945	<	new PaddedAtomicReference<QNode>(dummy));
946	<	_unsafe.putObjectVolatile(this, cleanMeOffset,
947	<	new PaddedAtomicReference<QNode>(null));
948	<
940	>	/**
941	>	* Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
942	>	* Replace with a simple call to Unsafe.getUnsafe when integrating
943	>	* into a jdk.
944	>	*
945	>	* @return a sun.misc.Unsafe
946	>	*/
947	>	private static sun.misc.Unsafe getUnsafe() {
948	>	try {
949	>	return sun.misc.Unsafe.getUnsafe();
950	>	} catch (SecurityException se) {
951	>	try {
952	>	return java.security.AccessController.doPrivileged
953	>	(new java.security
954	>	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
955	>	public sun.misc.Unsafe run() throws Exception {
956	>	java.lang.reflect.Field f = sun.misc
957	>	.Unsafe.class.getDeclaredField("theUnsafe");
958	>	f.setAccessible(true);
959	>	return (sun.misc.Unsafe) f.get(null);
960	>	}});
961	>	} catch (java.security.PrivilegedActionException e) {
962	>	throw new RuntimeException("Could not initialize intrinsics",
963	>	e.getCause());
964	>	}
965	>	}
966		}
734	–
967		}

Diff Legend

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