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