src/share/classes/java/util/concurrent/LinkedTransferQueue.java
Print this page
*** 35,48 ****
package java.util.concurrent;
import java.util.AbstractQueue;
import java.util.Collection;
- import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.concurrent.locks.LockSupport;
/**
* An unbounded {@link TransferQueue} based on linked nodes.
* This queue orders elements FIFO (first-in-first-out) with respect
--- 35,48 ----
package java.util.concurrent;
import java.util.AbstractQueue;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
+ import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.LockSupport;
/**
* An unbounded {@link TransferQueue} based on linked nodes.
* This queue orders elements FIFO (first-in-first-out) with respect
*** 586,596 ****
private E xfer(E e, boolean haveData, int how, long nanos) {
if (haveData && (e == null))
throw new NullPointerException();
Node s = null; // the node to append, if needed
! retry: for (;;) { // restart on append race
for (Node h = head, p = h; p != null;) { // find & match first node
boolean isData = p.isData;
Object item = p.item;
if (item != p && (item != null) == isData) { // unmatched
--- 586,597 ----
private E xfer(E e, boolean haveData, int how, long nanos) {
if (haveData && (e == null))
throw new NullPointerException();
Node s = null; // the node to append, if needed
! retry:
! for (;;) { // restart on append race
for (Node h = head, p = h; p != null;) { // find & match first node
boolean isData = p.isData;
Object item = p.item;
if (item != p && (item != null) == isData) { // unmatched
*** 597,607 ****
if (isData == haveData) // can't match
break;
if (p.casItem(item, e)) { // match
for (Node q = p; q != h;) {
Node n = q.next; // update by 2 unless singleton
! if (head == h && casHead(h, n == null? q : n)) {
h.forgetNext();
break;
} // advance and retry
if ((h = head) == null ||
(q = h.next) == null || !q.isMatched())
--- 598,608 ----
if (isData == haveData) // can't match
break;
if (p.casItem(item, e)) { // match
for (Node q = p; q != h;) {
Node n = q.next; // update by 2 unless singleton
! if (head == h && casHead(h, n == null ? q : n)) {
h.forgetNext();
break;
} // advance and retry
if ((h = head) == null ||
(q = h.next) == null || !q.isMatched())
*** 807,832 ****
/**
* Moves to next node after prev, or first node if prev null.
*/
private void advance(Node prev) {
! lastPred = lastRet;
! lastRet = prev;
! for (Node p = (prev == null) ? head : succ(prev);
! p != null; p = succ(p)) {
! Object item = p.item;
! if (p.isData) {
! if (item != null && item != p) {
! nextItem = LinkedTransferQueue.this.<E>cast(item);
! nextNode = p;
return;
}
}
else if (item == null)
break;
}
nextNode = null;
}
Itr() {
advance(null);
}
--- 808,872 ----
/**
* Moves to next node after prev, or first node if prev null.
*/
private void advance(Node prev) {
! /*
! * To track and avoid buildup of deleted nodes in the face
! * of calls to both Queue.remove and Itr.remove, we must
! * include variants of unsplice and sweep upon each
! * advance: Upon Itr.remove, we may need to catch up links
! * from lastPred, and upon other removes, we might need to
! * skip ahead from stale nodes and unsplice deleted ones
! * found while advancing.
! */
!
! Node r, b; // reset lastPred upon possible deletion of lastRet
! if ((r = lastRet) != null && !r.isMatched())
! lastPred = r; // next lastPred is old lastRet
! else if ((b = lastPred) == null || b.isMatched())
! lastPred = null; // at start of list
! else {
! Node s, n; // help with removal of lastPred.next
! while ((s = b.next) != null &&
! s != b && s.isMatched() &&
! (n = s.next) != null && n != s)
! b.casNext(s, n);
! }
!
! this.lastRet = prev;
!
! for (Node p = prev, s, n;;) {
! s = (p == null) ? head : p.next;
! if (s == null)
! break;
! else if (s == p) {
! p = null;
! continue;
! }
! Object item = s.item;
! if (s.isData) {
! if (item != null && item != s) {
! nextItem = LinkedTransferQueue.<E>cast(item);
! nextNode = s;
return;
}
}
else if (item == null)
break;
+ // assert s.isMatched();
+ if (p == null)
+ p = s;
+ else if ((n = s.next) == null)
+ break;
+ else if (s == n)
+ p = null;
+ else
+ p.casNext(s, n);
}
nextNode = null;
+ nextItem = null;
}
Itr() {
advance(null);
}
*** 842,855 ****
advance(p);
return e;
}
public final void remove() {
! Node p = lastRet;
! if (p == null) throw new IllegalStateException();
! if (p.tryMatchData())
! unsplice(lastPred, p);
}
}
/* -------------- Removal methods -------------- */
--- 882,897 ----
advance(p);
return e;
}
public final void remove() {
! final Node lastRet = this.lastRet;
! if (lastRet == null)
! throw new IllegalStateException();
! this.lastRet = null;
! if (lastRet.tryMatchData())
! unsplice(lastPred, lastRet);
}
}
/* -------------- Removal methods -------------- */
*** 995,1006 ****
/**
* Inserts the specified element at the tail of this queue.
* As the queue is unbounded, this method will never return {@code false}.
*
! * @return {@code true} (as specified by
! * {@link BlockingQueue#offer(Object) BlockingQueue.offer})
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
xfer(e, true, ASYNC, 0);
return true;
--- 1037,1047 ----
/**
* Inserts the specified element at the tail of this queue.
* As the queue is unbounded, this method will never return {@code false}.
*
! * @return {@code true} (as specified by {@link Queue#offer})
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
xfer(e, true, ASYNC, 0);
return true;
*** 1128,1146 ****
}
return n;
}
/**
! * Returns an iterator over the elements in this queue in proper
! * sequence, from head to tail.
*
* <p>The returned iterator is a "weakly consistent" iterator that
! * will never throw
! * {@link ConcurrentModificationException ConcurrentModificationException},
! * and guarantees to traverse elements as they existed upon
! * construction of the iterator, and may (but is not guaranteed
! * to) reflect any modifications subsequent to construction.
*
* @return an iterator over the elements in this queue in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
--- 1169,1187 ----
}
return n;
}
/**
! * Returns an iterator over the elements in this queue in proper sequence.
! * The elements will be returned in order from first (head) to last (tail).
*
* <p>The returned iterator is a "weakly consistent" iterator that
! * will never throw {@link java.util.ConcurrentModificationException
! * ConcurrentModificationException}, and guarantees to traverse
! * elements as they existed upon construction of the iterator, and
! * may (but is not guaranteed to) reflect any modifications
! * subsequent to construction.
*
* @return an iterator over the elements in this queue in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
*** 1200,1209 ****
--- 1241,1272 ----
*/
public boolean remove(Object o) {
return findAndRemove(o);
}
+ /**
+ * Returns {@code true} if this queue contains the specified element.
+ * More formally, returns {@code true} if and only if this queue contains
+ * at least one element {@code e} such that {@code o.equals(e)}.
+ *
+ * @param o object to be checked for containment in this queue
+ * @return {@code true} if this queue contains the specified element
+ */
+ public boolean contains(Object o) {
+ if (o == null) return false;
+ for (Node p = head; p != null; p = succ(p)) {
+ Object item = p.item;
+ if (p.isData) {
+ if (item != null && item != p && o.equals(item))
+ return true;
+ }
+ else if (item == null)
+ break;
+ }
+ return false;
+ }
+
/**
* Always returns {@code Integer.MAX_VALUE} because a
* {@code LinkedTransferQueue} is not capacity constrained.
*
* @return {@code Integer.MAX_VALUE} (as specified by