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; |
11 |
|
import java.util.ConcurrentModificationException; |
12 |
|
import java.util.Iterator; |
13 |
|
import java.util.NoSuchElementException; |
14 |
|
import java.util.Queue; |
15 |
+ |
import java.util.concurrent.TimeUnit; |
16 |
|
import java.util.concurrent.locks.LockSupport; |
17 |
|
|
18 |
|
/** |
422 |
|
} |
423 |
|
|
424 |
|
final boolean casItem(Object cmp, Object val) { |
425 |
< |
// assert cmp == null || cmp.getClass() != Node.class; |
425 |
> |
// assert cmp == null || cmp.getClass() != Node.class; |
426 |
|
return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); |
427 |
|
} |
428 |
|
|
488 |
|
* Tries to artificially match a data node -- used by remove. |
489 |
|
*/ |
490 |
|
final boolean tryMatchData() { |
491 |
< |
// assert isData; |
491 |
> |
// assert isData; |
492 |
|
Object x = item; |
493 |
|
if (x != null && x != this && casItem(x, null)) { |
494 |
|
LockSupport.unpark(waiter); |
541 |
|
|
542 |
|
@SuppressWarnings("unchecked") |
543 |
|
static <E> E cast(Object item) { |
544 |
< |
// assert item == null || item.getClass() != Node.class; |
544 |
> |
// assert item == null || item.getClass() != Node.class; |
545 |
|
return (E) item; |
546 |
|
} |
547 |
|
|
560 |
|
throw new NullPointerException(); |
561 |
|
Node s = null; // the node to append, if needed |
562 |
|
|
563 |
< |
retry: for (;;) { // restart on append race |
563 |
> |
retry: |
564 |
> |
for (;;) { // restart on append race |
565 |
|
|
566 |
|
for (Node h = head, p = h; p != null;) { // find & match first node |
567 |
|
boolean isData = p.isData; |
572 |
|
if (p.casItem(item, e)) { // match |
573 |
|
for (Node q = p; q != h;) { |
574 |
|
Node n = q.next; // update by 2 unless singleton |
575 |
< |
if (head == h && casHead(h, n == null? q : n)) { |
575 |
> |
if (head == h && casHead(h, n == null ? q : n)) { |
576 |
|
h.forgetNext(); |
577 |
|
break; |
578 |
|
} // advance and retry |
657 |
|
for (;;) { |
658 |
|
Object item = s.item; |
659 |
|
if (item != e) { // matched |
660 |
< |
// assert item != s; |
660 |
> |
// assert item != s; |
661 |
|
s.forgetContents(); // avoid garbage |
662 |
|
return this.<E>cast(item); |
663 |
|
} |
782 |
|
* Moves to next node after prev, or first node if prev null. |
783 |
|
*/ |
784 |
|
private void advance(Node prev) { |
785 |
< |
lastPred = lastRet; |
786 |
< |
lastRet = prev; |
787 |
< |
for (Node p = (prev == null) ? head : succ(prev); |
788 |
< |
p != null; p = succ(p)) { |
789 |
< |
Object item = p.item; |
790 |
< |
if (p.isData) { |
791 |
< |
if (item != null && item != p) { |
792 |
< |
nextItem = LinkedTransferQueue.this.<E>cast(item); |
793 |
< |
nextNode = p; |
785 |
> |
/* |
786 |
> |
* To track and avoid buildup of deleted nodes in the face |
787 |
> |
* of calls to both Queue.remove and Itr.remove, we must |
788 |
> |
* include variants of unsplice and sweep upon each |
789 |
> |
* advance: Upon Itr.remove, we may need to catch up links |
790 |
> |
* from lastPred, and upon other removes, we might need to |
791 |
> |
* skip ahead from stale nodes and unsplice deleted ones |
792 |
> |
* found while advancing. |
793 |
> |
*/ |
794 |
> |
|
795 |
> |
Node r, b; // reset lastPred upon possible deletion of lastRet |
796 |
> |
if ((r = lastRet) != null && !r.isMatched()) |
797 |
> |
lastPred = r; // next lastPred is old lastRet |
798 |
> |
else if ((b = lastPred) == null || b.isMatched()) |
799 |
> |
lastPred = null; // at start of list |
800 |
> |
else { |
801 |
> |
Node s, n; // help with removal of lastPred.next |
802 |
> |
while ((s = b.next) != null && |
803 |
> |
s != b && s.isMatched() && |
804 |
> |
(n = s.next) != null && n != s) |
805 |
> |
b.casNext(s, n); |
806 |
> |
} |
807 |
> |
|
808 |
> |
this.lastRet = prev; |
809 |
> |
for (Node p = prev, s, n;;) { |
810 |
> |
s = (p == null) ? head : p.next; |
811 |
> |
if (s == null) |
812 |
> |
break; |
813 |
> |
else if (s == p) { |
814 |
> |
p = null; |
815 |
> |
continue; |
816 |
> |
} |
817 |
> |
Object item = s.item; |
818 |
> |
if (s.isData) { |
819 |
> |
if (item != null && item != s) { |
820 |
> |
nextItem = LinkedTransferQueue.<E>cast(item); |
821 |
> |
nextNode = s; |
822 |
|
return; |
823 |
|
} |
824 |
|
} |
825 |
|
else if (item == null) |
826 |
|
break; |
827 |
+ |
// assert s.isMatched(); |
828 |
+ |
if (p == null) |
829 |
+ |
p = s; |
830 |
+ |
else if ((n = s.next) == null) |
831 |
+ |
break; |
832 |
+ |
else if (s == n) |
833 |
+ |
p = null; |
834 |
+ |
else |
835 |
+ |
p.casNext(s, n); |
836 |
|
} |
837 |
|
nextNode = null; |
838 |
+ |
nextItem = null; |
839 |
|
} |
840 |
|
|
841 |
|
Itr() { |
855 |
|
} |
856 |
|
|
857 |
|
public final void remove() { |
858 |
< |
Node p = lastRet; |
859 |
< |
if (p == null) throw new IllegalStateException(); |
860 |
< |
if (p.tryMatchData()) |
861 |
< |
unsplice(lastPred, p); |
858 |
> |
final Node lastRet = this.lastRet; |
859 |
> |
if (lastRet == null) |
860 |
> |
throw new IllegalStateException(); |
861 |
> |
this.lastRet = null; |
862 |
> |
if (lastRet.tryMatchData()) |
863 |
> |
unsplice(lastPred, lastRet); |
864 |
|
} |
865 |
|
} |
866 |
|
|
1010 |
|
* Inserts the specified element at the tail of this queue. |
1011 |
|
* As the queue is unbounded, this method will never return {@code false}. |
1012 |
|
* |
1013 |
< |
* @return {@code true} (as specified by |
974 |
< |
* {@link BlockingQueue#offer(Object) BlockingQueue.offer}) |
1013 |
> |
* @return {@code true} (as specified by {@link Queue#offer}) |
1014 |
|
* @throws NullPointerException if the specified element is null |
1015 |
|
*/ |
1016 |
|
public boolean offer(E e) { |
1215 |
|
} |
1216 |
|
|
1217 |
|
/** |
1218 |
+ |
* Returns {@code true} if this queue contains the specified element. |
1219 |
+ |
* More formally, returns {@code true} if and only if this queue contains |
1220 |
+ |
* at least one element {@code e} such that {@code o.equals(e)}. |
1221 |
+ |
* |
1222 |
+ |
* @param o object to be checked for containment in this queue |
1223 |
+ |
* @return {@code true} if this queue contains the specified element |
1224 |
+ |
*/ |
1225 |
+ |
public boolean contains(Object o) { |
1226 |
+ |
if (o == null) return false; |
1227 |
+ |
for (Node p = head; p != null; p = succ(p)) { |
1228 |
+ |
Object item = p.item; |
1229 |
+ |
if (p.isData) { |
1230 |
+ |
if (item != null && item != p && o.equals(item)) |
1231 |
+ |
return true; |
1232 |
+ |
} |
1233 |
+ |
else if (item == null) |
1234 |
+ |
break; |
1235 |
+ |
} |
1236 |
+ |
return false; |
1237 |
+ |
} |
1238 |
+ |
|
1239 |
+ |
/** |
1240 |
|
* Always returns {@code Integer.MAX_VALUE} because a |
1241 |
|
* {@code LinkedTransferQueue} is not capacity constrained. |
1242 |
|
* |