--- jsr166/src/jsr166y/LinkedTransferQueue.java	2008/07/25 18:10:41	1.4
+++ jsr166/src/jsr166y/LinkedTransferQueue.java	2009/07/26 05:55:34	1.27
@@ -5,11 +5,16 @@
  */
 
 package jsr166y;
+
 import java.util.concurrent.*;
-import java.util.concurrent.locks.*;
-import java.util.concurrent.atomic.*;
-import java.util.*;
-import java.io.*;
+
+import java.util.AbstractQueue;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.locks.LockSupport;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
 
 /**
  * An unbounded {@linkplain TransferQueue} based on linked nodes.
@@ -19,7 +24,7 @@ import java.io.*;
  * producer.  The <em>tail</em> of the queue is that element that has
  * been on the queue the shortest time for some producer.
  *
- * <p>Beware that, unlike in most collections, the <tt>size</tt>
+ * <p>Beware that, unlike in most collections, the {@code size}
  * method is <em>NOT</em> a constant-time operation. Because of the
  * asynchronous nature of these queues, determining the current number
  * of elements requires a traversal of the elements.
@@ -42,26 +47,25 @@ import java.io.*;
  * @since 1.7
  * @author Doug Lea
  * @param <E> the type of elements held in this collection
- *
  */
 public class LinkedTransferQueue<E> extends AbstractQueue<E>
     implements TransferQueue<E>, java.io.Serializable {
     private static final long serialVersionUID = -3223113410248163686L;
 
     /*
-     * This is still a work in progress...
-     *
      * This class extends the approach used in FIFO-mode
      * SynchronousQueues. See the internal documentation, as well as
      * the PPoPP 2006 paper "Scalable Synchronous Queues" by Scherer,
      * Lea & Scott
      * (http://www.cs.rice.edu/~wns1/papers/2006-PPoPP-SQ.pdf)
      *
-     * The main extension is to provide different Wait modes
-     * for the main "xfer" method that puts or takes items.
-     * These don't impact the basic dual-queue logic, but instead
-     * control whether or how threads block upon insertion
-     * of request or data nodes into the dual queue.
+     * The main extension is to provide different Wait modes for the
+     * main "xfer" method that puts or takes items.  These don't
+     * impact the basic dual-queue logic, but instead control whether
+     * or how threads block upon insertion of request or data nodes
+     * into the dual queue. It also uses slightly different
+     * conventions for tracking whether nodes are off-list or
+     * cancelled.
      */
 
     // Wait modes for xfer method
@@ -79,7 +83,7 @@ public class LinkedTransferQueue<E> exte
      * seems not to vary with number of CPUs (beyond 2) so is just
      * a constant.
      */
-    static final int maxTimedSpins = (NCPUS < 2)? 0 : 32; 
+    static final int maxTimedSpins = (NCPUS < 2) ? 0 : 32;
 
     /**
      * The number of times to spin before blocking in untimed waits.
@@ -94,29 +98,37 @@ public class LinkedTransferQueue<E> exte
      */
     static final long spinForTimeoutThreshold = 1000L;
 
-    /** 
-     * Node class for LinkedTransferQueue. Opportunistically subclasses from
-     * AtomicReference to represent item. Uses Object, not E, to allow
-     * setting item to "this" after use, to avoid garbage
-     * retention. Similarly, setting the next field to this is used as
-     * sentinel that node is off list.
+    /**
+     * Node class for LinkedTransferQueue. Opportunistically
+     * subclasses from AtomicReference to represent item. Uses Object,
+     * not E, to allow setting item to "this" after use, to avoid
+     * garbage retention. Similarly, setting the next field to this is
+     * used as sentinel that node is off list.
      */
-    static final class QNode extends AtomicReference<Object> {
-        volatile QNode next;
+    static final class Node<E> extends AtomicReference<Object> {
+        volatile Node<E> next;
         volatile Thread waiter;       // to control park/unpark
         final boolean isData;
-        QNode(Object item, boolean isData) {
+
+        Node(E item, boolean isData) {
             super(item);
             this.isData = isData;
         }
 
-        static final AtomicReferenceFieldUpdater<QNode, QNode>
+        @SuppressWarnings("rawtypes")
+        static final AtomicReferenceFieldUpdater<Node, Node>
             nextUpdater = AtomicReferenceFieldUpdater.newUpdater
-            (QNode.class, QNode.class, "next");
+            (Node.class, Node.class, "next");
 
-        boolean casNext(QNode cmp, QNode val) {
+        final boolean casNext(Node<E> cmp, Node<E> val) {
             return nextUpdater.compareAndSet(this, cmp, val);
         }
+
+        final void clearNext() {
+            nextUpdater.lazySet(this, this);
+        }
+
+        private static final long serialVersionUID = -3375979862319811754L;
     }
 
     /**
@@ -128,57 +140,59 @@ public class LinkedTransferQueue<E> exte
         // enough padding for 64bytes with 4byte refs
         Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
         PaddedAtomicReference(T r) { super(r); }
+        private static final long serialVersionUID = 8170090609809740854L;
     }
 
 
-    private final QNode dummy = new QNode(null, false);
-    private final PaddedAtomicReference<QNode> head = 
-        new PaddedAtomicReference<QNode>(dummy);
-    private final PaddedAtomicReference<QNode> tail = 
-        new PaddedAtomicReference<QNode>(dummy);
+    /** head of the queue */
+    private transient final PaddedAtomicReference<Node<E>> head;
+
+    /** tail of the queue */
+    private transient final PaddedAtomicReference<Node<E>> tail;
 
     /**
      * Reference to a cancelled node that might not yet have been
      * unlinked from queue because it was the last inserted node
      * when it cancelled.
      */
-    private final PaddedAtomicReference<QNode> cleanMe =
-        new PaddedAtomicReference<QNode>(null);
+    private transient final PaddedAtomicReference<Node<E>> cleanMe;
 
     /**
      * Tries to cas nh as new head; if successful, unlink
      * old head's next node to avoid garbage retention.
      */
-    private boolean advanceHead(QNode h, QNode nh) {
+    private boolean advanceHead(Node<E> h, Node<E> nh) {
         if (h == head.get() && head.compareAndSet(h, nh)) {
-            h.next = h; // forget old next
+            h.clearNext(); // forget old next
             return true;
         }
         return false;
     }
-    
+
     /**
      * Puts or takes an item. Used for most queue operations (except
-     * poll() and tryTransfer())
+     * poll() and tryTransfer()). See the similar code in
+     * SynchronousQueue for detailed explanation.
+     *
      * @param e the item or if null, signifies that this is a take
      * @param mode the wait mode: NOWAIT, TIMEOUT, WAIT
      * @param nanos timeout in nanosecs, used only if mode is TIMEOUT
      * @return an item, or null on failure
      */
-    private Object xfer(Object e, int mode, long nanos) {
+    private E xfer(E e, int mode, long nanos) {
         boolean isData = (e != null);
-        QNode s = null;
-        final PaddedAtomicReference<QNode> head = this.head;
-        final PaddedAtomicReference<QNode> tail = this.tail;
+        Node<E> s = null;
+        final PaddedAtomicReference<Node<E>> head = this.head;
+        final PaddedAtomicReference<Node<E>> tail = this.tail;
 
         for (;;) {
-            QNode t = tail.get();
-            QNode h = head.get();
+            Node<E> t = tail.get();
+            Node<E> h = head.get();
 
             if (t != null && (t == h || t.isData == isData)) {
                 if (s == null)
-                    s = new QNode(e, isData);
-                QNode last = t.next;
+                    s = new Node<E>(e, isData);
+                Node<E> last = t.next;
                 if (last != null) {
                     if (t == tail.get())
                         tail.compareAndSet(t, last);
@@ -188,15 +202,15 @@ public class LinkedTransferQueue<E> exte
                     return awaitFulfill(t, s, e, mode, nanos);
                 }
             }
-            
+
             else if (h != null) {
-                QNode first = h.next;
-                if (t == tail.get() && first != null && 
+                Node<E> first = h.next;
+                if (t == tail.get() && first != null &&
                     advanceHead(h, first)) {
                     Object x = first.get();
                     if (x != first && first.compareAndSet(x, e)) {
                         LockSupport.unpark(first.waiter);
-                        return isData? e : x;
+                        return isData ? e : (E) x;
                     }
                 }
             }
@@ -206,19 +220,19 @@ public class LinkedTransferQueue<E> exte
 
     /**
      * Version of xfer for poll() and tryTransfer, which
-     * simplifies control paths both here and in xfer
+     * simplifies control paths both here and in xfer.
      */
-    private Object fulfill(Object e) {
+    private E fulfill(E e) {
         boolean isData = (e != null);
-        final PaddedAtomicReference<QNode> head = this.head;
-        final PaddedAtomicReference<QNode> tail = this.tail;
+        final PaddedAtomicReference<Node<E>> head = this.head;
+        final PaddedAtomicReference<Node<E>> tail = this.tail;
 
         for (;;) {
-            QNode t = tail.get();
-            QNode h = head.get();
+            Node<E> t = tail.get();
+            Node<E> h = head.get();
 
             if (t != null && (t == h || t.isData == isData)) {
-                QNode last = t.next;
+                Node<E> last = t.next;
                 if (t == tail.get()) {
                     if (last != null)
                         tail.compareAndSet(t, last);
@@ -227,14 +241,14 @@ public class LinkedTransferQueue<E> exte
                 }
             }
             else if (h != null) {
-                QNode first = h.next;
-                if (t == tail.get() && 
+                Node<E> first = h.next;
+                if (t == tail.get() &&
                     first != null &&
                     advanceHead(h, first)) {
                     Object x = first.get();
                     if (x != first && first.compareAndSet(x, e)) {
                         LockSupport.unpark(first.waiter);
-                        return isData? e : x;
+                        return isData ? e : (E) x;
                     }
                 }
             }
@@ -252,12 +266,12 @@ public class LinkedTransferQueue<E> exte
      * @param nanos timeout value
      * @return matched item, or s if cancelled
      */
-    private Object awaitFulfill(QNode pred, QNode s, Object e, 
-                                int mode, long nanos) {
+    private E awaitFulfill(Node<E> pred, Node<E> s, E e,
+                           int mode, long nanos) {
         if (mode == NOWAIT)
             return null;
 
-        long lastTime = (mode == TIMEOUT)? System.nanoTime() : 0;
+        long lastTime = (mode == TIMEOUT) ? System.nanoTime() : 0;
         Thread w = Thread.currentThread();
         int spins = -1; // set to desired spin count below
         for (;;) {
@@ -266,16 +280,17 @@ public class LinkedTransferQueue<E> exte
             Object x = s.get();
             if (x != e) {                 // Node was matched or cancelled
                 advanceHead(pred, s);     // unlink if head
-                if (x == s)               // was cancelled
-                    return clean(pred, s);
-                else if (x != null) {     
+                if (x == s) {             // was cancelled
+                    clean(pred, s);
+                    return null;
+                }
+                else if (x != null) {
                     s.set(s);             // avoid garbage retention
-                    return x;
+                    return (E) x;
                 }
                 else
                     return e;
             }
-
             if (mode == TIMEOUT) {
                 long now = System.nanoTime();
                 nanos -= now - lastTime;
@@ -286,9 +301,9 @@ public class LinkedTransferQueue<E> exte
                 }
             }
             if (spins < 0) {
-                QNode h = head.get(); // only spin if at head
+                Node<E> h = head.get(); // only spin if at head
                 spins = ((h != null && h.next == s) ?
-                         (mode == TIMEOUT? 
+                         ((mode == TIMEOUT) ?
                           maxTimedSpins : maxUntimedSpins) : 0);
             }
             if (spins > 0)
@@ -296,14 +311,12 @@ public class LinkedTransferQueue<E> exte
             else if (s.waiter == null)
                 s.waiter = w;
             else if (mode != TIMEOUT) {
-                //                LockSupport.park(this);
-                LockSupport.park(); // allows run on java5
+                LockSupport.park(this);
                 s.waiter = null;
                 spins = -1;
             }
             else if (nanos > spinForTimeoutThreshold) {
-                //                LockSupport.parkNanos(this, nanos);
-                LockSupport.parkNanos(nanos);
+                LockSupport.parkNanos(this, nanos);
                 s.waiter = null;
                 spins = -1;
             }
@@ -311,76 +324,121 @@ public class LinkedTransferQueue<E> exte
     }
 
     /**
+     * Returns validated tail for use in cleaning methods.
+     */
+    private Node<E> getValidatedTail() {
+        for (;;) {
+            Node<E> h = head.get();
+            Node<E> first = h.next;
+            if (first != null && first.next == first) { // help advance
+                advanceHead(h, first);
+                continue;
+            }
+            Node<E> t = tail.get();
+            Node<E> last = t.next;
+            if (t == tail.get()) {
+                if (last != null)
+                    tail.compareAndSet(t, last); // help advance
+                else
+                    return t;
+            }
+        }
+    }
+
+    /**
      * Gets rid of cancelled node s with original predecessor pred.
-     * @return null (to simplify use by callers)
+     *
+     * @param pred predecessor of cancelled node
+     * @param s the cancelled node
      */
-    private Object clean(QNode pred, QNode s) {
+    private void clean(Node<E> pred, Node<E> s) {
         Thread w = s.waiter;
         if (w != null) {             // Wake up thread
             s.waiter = null;
             if (w != Thread.currentThread())
                 LockSupport.unpark(w);
         }
-        
-        for (;;) {
-            if (pred.next != s) // already cleaned
-                return null; 
-            QNode h = head.get();
-            QNode hn = h.next;   // Absorb cancelled first node as head
-            if (hn != null && hn.next == hn) {
-                advanceHead(h, hn);
-                continue;
-            }
-            QNode t = tail.get();      // Ensure consistent read for tail
-            if (t == h)
-                return null;
-            QNode tn = t.next;
-            if (t != tail.get())
-                continue;
-            if (tn != null) {          // Help advance tail
-                tail.compareAndSet(t, tn);
-                continue;
-            }
-            if (s != t) {             // If not tail, try to unsplice
-                QNode sn = s.next;
+
+        if (pred == null)
+            return;
+
+        /*
+         * At any given time, exactly one node on list cannot be
+         * deleted -- the last inserted node. To accommodate this, if
+         * we cannot delete s, we save its predecessor as "cleanMe",
+         * processing the previously saved version first. At least one
+         * of node s or the node previously saved can always be
+         * processed, so this always terminates.
+         */
+        while (pred.next == s) {
+            Node<E> oldpred = reclean();  // First, help get rid of cleanMe
+            Node<E> t = getValidatedTail();
+            if (s != t) {               // If not tail, try to unsplice
+                Node<E> sn = s.next;      // s.next == s means s already off list
                 if (sn == s || pred.casNext(s, sn))
-                    return null;
+                    break;
+            }
+            else if (oldpred == pred || // Already saved
+                     (oldpred == null && cleanMe.compareAndSet(null, pred)))
+                break;                  // Postpone cleaning
+        }
+    }
+
+    /**
+     * Tries to unsplice the cancelled node held in cleanMe that was
+     * previously uncleanable because it was at tail.
+     *
+     * @return current cleanMe node (or null)
+     */
+    private Node<E> reclean() {
+        /*
+         * cleanMe is, or at one time was, predecessor of cancelled
+         * node s that was the tail so could not be unspliced.  If s
+         * is no longer the tail, try to unsplice if necessary and
+         * make cleanMe slot available.  This differs from similar
+         * code in clean() because we must check that pred still
+         * points to a cancelled node that must be unspliced -- if
+         * not, we can (must) clear cleanMe without unsplicing.
+         * This can loop only due to contention on casNext or
+         * clearing cleanMe.
+         */
+        Node<E> pred;
+        while ((pred = cleanMe.get()) != null) {
+            Node<E> t = getValidatedTail();
+            Node<E> s = pred.next;
+            if (s != t) {
+                Node<E> sn;
+                if (s == null || s == pred || s.get() != s ||
+                    (sn = s.next) == s || pred.casNext(s, sn))
+                    cleanMe.compareAndSet(pred, null);
             }
-            QNode dp = cleanMe.get();
-            if (dp != null) {    // Try unlinking previous cancelled node
-                QNode d = dp.next;
-                QNode dn;
-                if (d == null ||               // d is gone or
-                    d == dp ||                 // d is off list or
-                    d.get() != d ||            // d not cancelled or
-                    (d != t &&                 // d not tail and
-                     (dn = d.next) != null &&  //   has successor
-                     dn != d &&                //   that is on list
-                     dp.casNext(d, dn)))       // d unspliced
-                    cleanMe.compareAndSet(dp, null);
-                if (dp == pred)
-                    return null;      // s is already saved node
-            } 
-            else if (cleanMe.compareAndSet(null, pred))
-                return null;          // Postpone cleaning s
+            else // s is still tail; cannot clean
+                break;
         }
+        return pred;
     }
-    
+
     /**
-     * Creates an initially empty <tt>LinkedTransferQueue</tt>.
+     * Creates an initially empty {@code LinkedTransferQueue}.
      */
     public LinkedTransferQueue() {
+        Node<E> dummy = new Node<E>(null, false);
+        head = new PaddedAtomicReference<Node<E>>(dummy);
+        tail = new PaddedAtomicReference<Node<E>>(dummy);
+        cleanMe = new PaddedAtomicReference<Node<E>>(null);
     }
 
     /**
-     * Creates a <tt>LinkedTransferQueue</tt>
+     * Creates a {@code LinkedTransferQueue}
      * initially containing the elements of the given collection,
      * added in traversal order of the collection's iterator.
+     *
      * @param c the collection of elements to initially contain
      * @throws NullPointerException if the specified collection or any
      *         of its elements are null
      */
     public LinkedTransferQueue(Collection<? extends E> c) {
+        this();
         addAll(c);
     }
 
@@ -390,7 +448,7 @@ public class LinkedTransferQueue<E> exte
         xfer(e, NOWAIT, 0);
     }
 
-    public boolean offer(E e, long timeout, TimeUnit unit)  
+    public boolean offer(E e, long timeout, TimeUnit unit)
         throws InterruptedException {
         if (e == null) throw new NullPointerException();
         if (Thread.interrupted()) throw new InterruptedException();
@@ -404,12 +462,18 @@ public class LinkedTransferQueue<E> exte
         return true;
     }
 
+    public boolean add(E e) {
+        if (e == null) throw new NullPointerException();
+        xfer(e, NOWAIT, 0);
+        return true;
+    }
+
     public void transfer(E e) throws InterruptedException {
         if (e == null) throw new NullPointerException();
         if (xfer(e, WAIT, 0) == null) {
-	    Thread.interrupted();
+            Thread.interrupted();
             throw new InterruptedException();
-	}
+        }
     }
 
     public boolean tryTransfer(E e, long timeout, TimeUnit unit)
@@ -430,20 +494,20 @@ public class LinkedTransferQueue<E> exte
     public E take() throws InterruptedException {
         Object e = xfer(null, WAIT, 0);
         if (e != null)
-            return (E)e;
-	Thread.interrupted();
+            return (E) e;
+        Thread.interrupted();
         throw new InterruptedException();
     }
 
     public E poll(long timeout, TimeUnit unit) throws InterruptedException {
         Object e = xfer(null, TIMEOUT, unit.toNanos(timeout));
         if (e != null || !Thread.interrupted())
-            return (E)e;
+            return (E) e;
         throw new InterruptedException();
     }
 
     public E poll() {
-        return (E)fulfill(null);
+        return fulfill(null);
     }
 
     public int drainTo(Collection<? super E> c) {
@@ -477,22 +541,22 @@ public class LinkedTransferQueue<E> exte
     // Traversal-based methods
 
     /**
-     * Return head after performing any outstanding helping steps
+     * Returns head after performing any outstanding helping steps.
      */
-    private QNode traversalHead() {
+    private Node<E> traversalHead() {
         for (;;) {
-            QNode t = tail.get();
-            QNode h = head.get();
+            Node<E> t = tail.get();
+            Node<E> h = head.get();
             if (h != null && t != null) {
-                QNode last = t.next;
-                QNode first = h.next;
+                Node<E> last = t.next;
+                Node<E> first = h.next;
                 if (t == tail.get()) {
-                    if (last != null) 
+                    if (last != null)
                         tail.compareAndSet(t, last);
                     else if (first != null) {
                         Object x = first.get();
-                        if (x == first) 
-                            advanceHead(h, first);     
+                        if (x == first)
+                            advanceHead(h, first);
                         else
                             return h;
                     }
@@ -500,6 +564,7 @@ public class LinkedTransferQueue<E> exte
                         return h;
                 }
             }
+            reclean();
         }
     }
 
@@ -516,63 +581,75 @@ public class LinkedTransferQueue<E> exte
      * if subsequently removed.
      */
     class Itr implements Iterator<E> {
-        QNode nextNode;    // Next node to return next
-        QNode currentNode; // last returned node, for remove()
-        QNode prevNode;    // predecessor of last returned node
-        E nextItem;        // Cache of next item, once commited to in next
-        
+        Node<E> next;        // node to return next
+        Node<E> pnext;       // predecessor of next
+        Node<E> snext;       // successor of next
+        Node<E> curr;        // last returned node, for remove()
+        Node<E> pcurr;       // predecessor of curr, for remove()
+        E nextItem;        // Cache of next item, once committed to in next
+
         Itr() {
-            nextNode = traversalHead();
-            advance();
+            findNext();
         }
-        
-        E advance() {
-            prevNode = currentNode;
-            currentNode = nextNode;
-            E x = nextItem;
-            
-            QNode p = nextNode.next;
+
+        /**
+         * Ensures next points to next valid node, or null if none.
+         */
+        void findNext() {
             for (;;) {
-                if (p == null || !p.isData) {
-                    nextNode = null;
-                    nextItem = null;
-                    return x;
-                }
-                Object item = p.get();
-                if (item != p && item != null) {
-                    nextNode = p;
-                    nextItem = (E)item;
-                    return x;
-                } 
-                prevNode = p;
-                p = p.next;
+                Node<E> pred = pnext;
+                Node<E> q = next;
+                if (pred == null || pred == q) {
+                    pred = traversalHead();
+                    q = pred.next;
+                }
+                if (q == null || !q.isData) {
+                    next = null;
+                    return;
+                }
+                Object x = q.get();
+                Node<E> s = q.next;
+                if (x != null && q != x && q != s) {
+                    nextItem = (E) x;
+                    snext = s;
+                    pnext = pred;
+                    next = q;
+                    return;
+                }
+                pnext = q;
+                next = s;
             }
         }
-        
+
         public boolean hasNext() {
-            return nextNode != null;
+            return next != null;
         }
-        
+
         public E next() {
-            if (nextNode == null) throw new NoSuchElementException();
-            return advance();
+            if (next == null) throw new NoSuchElementException();
+            pcurr = pnext;
+            curr = next;
+            pnext = next;
+            next = snext;
+            E x = nextItem;
+            findNext();
+            return x;
         }
-        
+
         public void remove() {
-            QNode p = currentNode;
-            QNode prev = prevNode;
-            if (prev == null || p == null) 
+            Node<E> p = curr;
+            if (p == null)
                 throw new IllegalStateException();
             Object x = p.get();
             if (x != null && x != p && p.compareAndSet(x, p))
-                clean(prev, p);
+                clean(pcurr, p);
         }
     }
 
     public E peek() {
         for (;;) {
-            QNode h = traversalHead();
-            QNode p = h.next;
+            Node<E> h = traversalHead();
+            Node<E> p = h.next;
             if (p == null)
                 return null;
             Object x = p.get();
@@ -580,15 +657,15 @@ public class LinkedTransferQueue<E> exte
                 if (!p.isData)
                     return null;
                 if (x != null)
-                    return (E)x;
+                    return (E) x;
             }
         }
     }
 
     public boolean isEmpty() {
         for (;;) {
-            QNode h = traversalHead();
-            QNode p = h.next;
+            Node<E> h = traversalHead();
+            Node<E> p = h.next;
             if (p == null)
                 return true;
             Object x = p.get();
@@ -603,20 +680,20 @@ public class LinkedTransferQueue<E> exte
 
     public boolean hasWaitingConsumer() {
         for (;;) {
-            QNode h = traversalHead();
-            QNode p = h.next;
+            Node<E> h = traversalHead();
+            Node<E> p = h.next;
             if (p == null)
                 return false;
             Object x = p.get();
-            if (p != x) 
+            if (p != x)
                 return !p.isData;
         }
     }
-    
+
     /**
      * Returns the number of elements in this queue.  If this queue
-     * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
-     * <tt>Integer.MAX_VALUE</tt>.
+     * contains more than {@code Integer.MAX_VALUE} elements, returns
+     * {@code Integer.MAX_VALUE}.
      *
      * <p>Beware that, unlike in most collections, this method is
      * <em>NOT</em> a constant-time operation. Because of the
@@ -627,10 +704,10 @@ public class LinkedTransferQueue<E> exte
      */
     public int size() {
         int count = 0;
-        QNode h = traversalHead();
-        for (QNode p = h.next; p != null && p.isData; p = p.next) {
+        Node<E> h = traversalHead();
+        for (Node<E> p = h.next; p != null && p.isData; p = p.next) {
             Object x = p.get();
-            if (x != null && x != p) { 
+            if (x != null && x != p) {
                 if (++count == Integer.MAX_VALUE) // saturated
                     break;
             }
@@ -640,8 +717,8 @@ public class LinkedTransferQueue<E> exte
 
     public int getWaitingConsumerCount() {
         int count = 0;
-        QNode h = traversalHead();
-        for (QNode p = h.next; p != null && !p.isData; p = p.next) {
+        Node<E> h = traversalHead();
+        for (Node<E> p = h.next; p != null && !p.isData; p = p.next) {
             if (p.get() == null) {
                 if (++count == Integer.MAX_VALUE)
                     break;
@@ -654,18 +731,40 @@ public class LinkedTransferQueue<E> exte
         return Integer.MAX_VALUE;
     }
 
+    public boolean remove(Object o) {
+        if (o == null)
+            return false;
+        for (;;) {
+            Node<E> pred = traversalHead();
+            for (;;) {
+                Node<E> q = pred.next;
+                if (q == null || !q.isData)
+                    return false;
+                if (q == pred) // restart
+                    break;
+                Object x = q.get();
+                if (x != null && x != q && o.equals(x) &&
+                    q.compareAndSet(x, q)) {
+                    clean(pred, q);
+                    return true;
+                }
+                pred = q;
+            }
+        }
+    }
+
     /**
      * Save the state to a stream (that is, serialize it).
      *
-     * @serialData All of the elements (each an <tt>E</tt>) in
+     * @serialData All of the elements (each an {@code E}) in
      * the proper order, followed by a null
      * @param s the stream
      */
     private void writeObject(java.io.ObjectOutputStream s)
         throws java.io.IOException {
         s.defaultWriteObject();
-        for (Iterator<E> it = iterator(); it.hasNext(); )
-            s.writeObject(it.next());
+        for (E e : this)
+            s.writeObject(e);
         // Use trailing null as sentinel
         s.writeObject(null);
     }
@@ -673,17 +772,76 @@ public class LinkedTransferQueue<E> exte
     /**
      * Reconstitute the Queue instance from a stream (that is,
      * deserialize it).
+     *
      * @param s the stream
      */
     private void readObject(java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
         s.defaultReadObject();
+        resetHeadAndTail();
         for (;;) {
-            E item = (E)s.readObject();
+            @SuppressWarnings("unchecked") E item = (E) s.readObject();
             if (item == null)
                 break;
             else
                 offer(item);
         }
     }
+
+    // Support for resetting head/tail while deserializing
+    private void resetHeadAndTail() {
+        Node<E> dummy = new Node<E>(null, false);
+        UNSAFE.putObjectVolatile(this, headOffset,
+                                 new PaddedAtomicReference<Node<E>>(dummy));
+        UNSAFE.putObjectVolatile(this, tailOffset,
+                                 new PaddedAtomicReference<Node<E>>(dummy));
+        UNSAFE.putObjectVolatile(this, cleanMeOffset,
+                                 new PaddedAtomicReference<Node<E>>(null));
+    }
+
+    // Unsafe mechanics for jsr166y 3rd party package.
+    private static sun.misc.Unsafe getUnsafe() {
+        try {
+            return sun.misc.Unsafe.getUnsafe();
+        } catch (SecurityException se) {
+            try {
+                return java.security.AccessController.doPrivileged
+                    (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
+                        public sun.misc.Unsafe run() throws Exception {
+                            return getUnsafeByReflection();
+                        }});
+            } catch (java.security.PrivilegedActionException e) {
+                throw new RuntimeException("Could not initialize intrinsics",
+                                           e.getCause());
+            }
+        }
+    }
+
+    private static sun.misc.Unsafe getUnsafeByReflection()
+            throws NoSuchFieldException, IllegalAccessException {
+        java.lang.reflect.Field f =
+            sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
+        f.setAccessible(true);
+        return (sun.misc.Unsafe) f.get(null);
+    }
+
+    private static long fieldOffset(String fieldName, Class<?> klazz) {
+        try {
+            return UNSAFE.objectFieldOffset(klazz.getDeclaredField(fieldName));
+        } catch (NoSuchFieldException e) {
+            // Convert Exception to Error
+            NoSuchFieldError error = new NoSuchFieldError(fieldName);
+            error.initCause(e);
+            throw error;
+        }
+    }
+
+    private static final sun.misc.Unsafe UNSAFE = getUnsafe();
+    private static final long headOffset =
+        fieldOffset("head", LinkedTransferQueue.class);
+    private static final long tailOffset =
+        fieldOffset("tail", LinkedTransferQueue.class);
+    private static final long cleanMeOffset =
+        fieldOffset("cleanMe", LinkedTransferQueue.class);
+
 }