implements TransferQueue<E>, java.io.Serializable {

private static final long serialVersionUID = -3223113410248163686L;

/*

/** True if on multiprocessor */

private static final boolean MP =

Runtime.getRuntime().availableProcessors() > 1;

/**

private static final int FRONT_SPINS = 1 << 7;

/**

private static final int CHAINED_SPINS = FRONT_SPINS >>> 1;

/**

static final int SWEEP_THRESHOLD = 32;

/**

static final class Node {

final boolean isData; // false if this is a request node

volatile Object item; // initially non-null if isData; CASed to match

volatile Node next;

volatile Thread waiter; // null until waiting

// CAS methods for fields

final boolean casNext(Node cmp, Node val) {

return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);

}

final boolean casItem(Object cmp, Object val) {

// assert cmp == null || cmp.getClass() != Node.class;

return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);

}

/**

Node(Object item, boolean isData) {

UNSAFE.putObject(this, itemOffset, item); // relaxed write

this.isData = isData;

}

/**

final void forgetNext() {

UNSAFE.putObject(this, nextOffset, this);

}

/**

final void forgetContents() {

UNSAFE.putObject(this, itemOffset, this);

UNSAFE.putObject(this, waiterOffset, null);

}

/**

final boolean isMatched() {

Object x = item;

return (x == this) || ((x == null) == isData);

}

/**

final boolean isUnmatchedRequest() {

return !isData && item == null;

}

/**

final boolean cannotPrecede(boolean haveData) {

boolean d = isData;

Object x;

return d != haveData && (x = item) != this && (x != null) == d;

}

/**

final boolean tryMatchData() {

// assert isData;

Object x = item;

if (x != null && x != this && casItem(x, null)) {

LockSupport.unpark(waiter);

return true;

}

return false;

}

private static final long serialVersionUID = -3375979862319811754L;

// Unsafe mechanics

private static final sun.misc.Unsafe UNSAFE;

private static final long itemOffset;

private static final long nextOffset;

private static final long waiterOffset;

static {

try {

UNSAFE = sun.misc.Unsafe.getUnsafe();

Class<?> k = Node.class;

itemOffset = UNSAFE.objectFieldOffset

(k.getDeclaredField("item"));

nextOffset = UNSAFE.objectFieldOffset

(k.getDeclaredField("next"));

waiterOffset = UNSAFE.objectFieldOffset

(k.getDeclaredField("waiter"));

} catch (Exception e) {

throw new Error(e);

}

}

}

/** head of the queue; null until first enqueue */

transient volatile Node head;

/** tail of the queue; null until first append */

private transient volatile Node tail;

/** The number of apparent failures to unsplice removed nodes */

private transient volatile int sweepVotes;

// CAS methods for fields

private boolean casTail(Node cmp, Node val) {

return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);

}

private boolean casHead(Node cmp, Node val) {

return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);

}

private boolean casSweepVotes(int cmp, int val) {

return UNSAFE.compareAndSwapInt(this, sweepVotesOffset, cmp, val);

}

/*

private static final int NOW = 0; // for untimed poll, tryTransfer

private static final int ASYNC = 1; // for offer, put, add

private static final int SYNC = 2; // for transfer, take

private static final int TIMED = 3; // for timed poll, tryTransfer

@SuppressWarnings("unchecked")

static <E> E cast(Object item) {

// assert item == null || item.getClass() != Node.class;

return (E) item;

}

/**

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

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())

break; // unless slack < 2

}

LockSupport.unpark(p.waiter);

return LinkedTransferQueue.<E>cast(item);

}

}

Node n = p.next;

p = (p != n) ? n : (h = head); // Use head if p offlist

}

if (how != NOW) { // No matches available

if (s == null)

s = new Node(e, haveData);

Node pred = tryAppend(s, haveData);

if (pred == null)

continue retry; // lost race vs opposite mode

if (how != ASYNC)

return awaitMatch(s, pred, e, (how == TIMED), nanos);

}

return e; // not waiting

}

}

/**

private Node tryAppend(Node s, boolean haveData) {

for (Node t = tail, p = t;;) { // move p to last node and append

Node n, u; // temps for reads of next & tail

if (p == null && (p = head) == null) {

if (casHead(null, s))

return s; // initialize

}

else if (p.cannotPrecede(haveData))

return null; // lost race vs opposite mode

else if ((n = p.next) != null) // not last; keep traversing

p = p != t && t != (u = tail) ? (t = u) : // stale tail

(p != n) ? n : null; // restart if off list

else if (!p.casNext(null, s))

p = p.next; // re-read on CAS failure

else {

if (p != t) { // update if slack now >= 2

while ((tail != t || !casTail(t, s)) &&

(t = tail) != null &&

(s = t.next) != null && // advance and retry

(s = s.next) != null && s != t);

}

return p;

}

}

}

/**

private E awaitMatch(Node s, Node pred, E e, boolean timed, long nanos) {

final long deadline = timed ? System.nanoTime() + nanos : 0L;

Thread w = Thread.currentThread();

int spins = -1; // initialized after first item and cancel checks

ThreadLocalRandom randomYields = null; // bound if needed

for (;;) {

Object item = s.item;

if (item != e) { // matched

// assert item != s;

s.forgetContents(); // avoid garbage

return LinkedTransferQueue.<E>cast(item);

}

if ((w.isInterrupted() || (timed && nanos <= 0)) &&

s.casItem(e, s)) { // cancel

unsplice(pred, s);

return e;

}

if (spins < 0) { // establish spins at/near front

if ((spins = spinsFor(pred, s.isData)) > 0)

randomYields = ThreadLocalRandom.current();

}

else if (spins > 0) { // spin

--spins;

if (randomYields.nextInt(CHAINED_SPINS) == 0)

Thread.yield(); // occasionally yield

}

else if (s.waiter == null) {

s.waiter = w; // request unpark then recheck

}

else if (timed) {

nanos = deadline - System.nanoTime();

if (nanos > 0L)

LockSupport.parkNanos(this, nanos);

}

else {

LockSupport.park(this);

}

}

}

/**

private static int spinsFor(Node pred, boolean haveData) {

if (MP && pred != null) {

if (pred.isData != haveData) // phase change

return FRONT_SPINS + CHAINED_SPINS;

if (pred.isMatched()) // probably at front

return FRONT_SPINS;

if (pred.waiter == null) // pred apparently spinning

return CHAINED_SPINS;

}

return 0;

}

/* -------------- Traversal methods -------------- */

/**

final Node succ(Node p) {

Node next = p.next;

return (p == next) ? head : next;

}

/**

private Node firstOfMode(boolean isData) {

for (Node p = head; p != null; p = succ(p)) {

if (!p.isMatched())

return (p.isData == isData) ? p : null;

}

return null;

}

/**

final Node firstDataNode() {

for (Node p = head; p != null;) {

Object item = p.item;

if (p.isData) {

if (item != null && item != p)

return p;

}

else if (item == null)

break;

if (p == (p = p.next))

p = head;

}

return null;

}

/**

private E firstDataItem() {

for (Node p = head; p != null; p = succ(p)) {

Object item = p.item;

if (p.isData) {

if (item != null && item != p)

return LinkedTransferQueue.<E>cast(item);

}

else if (item == null)

return null;

}

return null;

}

/**

private int countOfMode(boolean data) {

int count = 0;

for (Node p = head; p != null; ) {

if (!p.isMatched()) {

if (p.isData != data)

return 0;

if (++count == Integer.MAX_VALUE) // saturated

break;

}

Node n = p.next;

if (n != p)

p = n;

else {

count = 0;

p = head;

}

}

return count;

}

final class Itr implements Iterator<E> {

private Node nextNode; // next node to return item for

private E nextItem; // the corresponding item

private Node lastRet; // last returned node, to support remove

private Node lastPred; // predecessor to unlink lastRet

/**

private void advance(Node prev) {

/*

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);

}

public final boolean hasNext() {

return nextNode != null;

}

public final E next() {

Node p = nextNode;

if (p == null) throw new NoSuchElementException();

E e = nextItem;

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);

}

}

/** A customized variant of Spliterators.IteratorSpliterator */

static final class LTQSpliterator<E> implements Spliterator<E> {

static final int MAX_BATCH = 1 << 25; // max batch array size;

final LinkedTransferQueue<E> queue;

Node current; // current node; null until initialized

int batch; // batch size for splits

boolean exhausted; // true when no more nodes

LTQSpliterator(LinkedTransferQueue<E> queue) {

this.queue = queue;

}

public Spliterator<E> trySplit() {

Node p;

final LinkedTransferQueue<E> q = this.queue;

int b = batch;

int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;

if (!exhausted &&

((p = current) != null || (p = q.firstDataNode()) != null) &&

p.next != null) {

Object[] a = new Object[n];

int i = 0;

do {

Object e = p.item;

if (e != p && (a[i] = e) != null)

++i;

if (p == (p = p.next))

p = q.firstDataNode();

} while (p != null && i < n && p.isData);

if ((current = p) == null)

exhausted = true;

if (i > 0) {

batch = i;

return Spliterators.spliterator

(a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |

Spliterator.CONCURRENT);

}

}

return null;

}

@SuppressWarnings("unchecked")

public void forEachRemaining(Consumer<? super E> action) {

Node p;

if (action == null) throw new NullPointerException();

final LinkedTransferQueue<E> q = this.queue;

if (!exhausted &&

((p = current) != null || (p = q.firstDataNode()) != null)) {

exhausted = true;

do {

Object e = p.item;

if (e != null && e != p)

action.accept((E)e);

if (p == (p = p.next))

p = q.firstDataNode();

} while (p != null && p.isData);

}

}

@SuppressWarnings("unchecked")

public boolean tryAdvance(Consumer<? super E> action) {

Node p;

if (action == null) throw new NullPointerException();

final LinkedTransferQueue<E> q = this.queue;

if (!exhausted &&

((p = current) != null || (p = q.firstDataNode()) != null)) {