--- jsr166/src/jsr166y/LinkedTransferQueue.java	2009/01/05 03:43:07	1.10
+++ jsr166/src/jsr166y/LinkedTransferQueue.java	2009/07/21 18:11:44	1.20
@@ -21,7 +21,7 @@ import java.lang.reflect.*;
  * 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.
@@ -116,9 +116,14 @@ public class LinkedTransferQueue<E> exte
             nextUpdater = AtomicReferenceFieldUpdater.newUpdater
             (QNode.class, QNode.class, "next");
 
-        boolean casNext(QNode cmp, QNode val) {
+        final boolean casNext(QNode cmp, QNode val) {
             return nextUpdater.compareAndSet(this, cmp, val);
         }
+
+        final void clearNext() {
+            nextUpdater.lazySet(this, this);
+        }
+
     }
 
     /**
@@ -151,7 +156,7 @@ public class LinkedTransferQueue<E> exte
      */
     private boolean advanceHead(QNode h, QNode nh) {
         if (h == head.get() && head.compareAndSet(h, nh)) {
-            h.next = h; // forget old next
+            h.clearNext(); // forget old next
             return true;
         }
         return false;
@@ -161,6 +166,7 @@ public class LinkedTransferQueue<E> exte
      * Puts or takes an item. Used for most queue operations (except
      * 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
@@ -207,7 +213,7 @@ 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) {
         boolean isData = (e != null);
@@ -267,7 +273,7 @@ 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
+                if (x == s) {             // was cancelled
                     clean(pred, s);
                     return null;
                 }
@@ -298,14 +304,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;
             }
@@ -313,7 +317,7 @@ public class LinkedTransferQueue<E> exte
     }
 
     /**
-     * Returns validated tail for use in cleaning methods
+     * Returns validated tail for use in cleaning methods.
      */
     private QNode getValidatedTail() {
         for (;;) {
@@ -336,6 +340,7 @@ public class LinkedTransferQueue<E> exte
 
     /**
      * Gets rid of cancelled node s with original predecessor pred.
+     *
      * @param pred predecessor of cancelled node
      * @param s the cancelled node
      */
@@ -346,6 +351,10 @@ public class LinkedTransferQueue<E> exte
             if (w != Thread.currentThread())
                 LockSupport.unpark(w);
         }
+
+        if (pred == null)
+            return;
+
         /*
          * At any given time, exactly one node on list cannot be
          * deleted -- the last inserted node. To accommodate this, if
@@ -371,6 +380,7 @@ public class LinkedTransferQueue<E> exte
     /**
      * 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 QNode reclean() {
@@ -402,7 +412,7 @@ public class LinkedTransferQueue<E> exte
     }
 
     /**
-     * Creates an initially empty <tt>LinkedTransferQueue</tt>.
+     * Creates an initially empty {@code LinkedTransferQueue}.
      */
     public LinkedTransferQueue() {
         QNode dummy = new QNode(null, false);
@@ -412,9 +422,10 @@ public class LinkedTransferQueue<E> exte
     }
 
     /**
-     * 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
@@ -444,6 +455,12 @@ 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) {
@@ -517,7 +534,7 @@ 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() {
         for (;;) {
@@ -540,6 +557,7 @@ public class LinkedTransferQueue<E> exte
                         return h;
                 }
             }
+            reclean();
         }
     }
 
@@ -556,56 +574,68 @@ 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
+        QNode next;        // node to return next
+        QNode pnext;       // predecessor of next
+        QNode snext;       // successor of next
+        QNode curr;        // last returned node, for remove()
+        QNode 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;
+                QNode pred = pnext;
+                QNode q = next;
+                if (pred == null || pred == q) {
+                    pred = traversalHead();
+                    q = pred.next;
+                }
+                if (q == null || !q.isData) {
+                    next = null;
+                    return;
+                }
+                Object x = q.get();
+                QNode s = q.next;
+                if (x != null && q != x && q != s) {
+                    nextItem = (E)x;
+                    snext = s;
+                    pnext = pred;
+                    next = q;
+                    return;
                 }
-                prevNode = p;
-                p = p.next;
+                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)
+            QNode 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);
         }
     }
 
@@ -655,8 +685,8 @@ public class LinkedTransferQueue<E> exte
 
     /**
      * 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
@@ -694,18 +724,40 @@ public class LinkedTransferQueue<E> exte
         return Integer.MAX_VALUE;
     }
 
+    public boolean remove(Object o) {
+        if (o == null)
+            return false;
+        for (;;) {
+            QNode pred = traversalHead();
+            for (;;) {
+                QNode 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);
     }
@@ -713,6 +765,7 @@ 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)
@@ -730,41 +783,59 @@ public class LinkedTransferQueue<E> exte
 
 
     // Support for resetting head/tail while deserializing
+    private void resetHeadAndTail() {
+        QNode dummy = new QNode(null, false);
+        UNSAFE.putObjectVolatile(this, headOffset,
+                                  new PaddedAtomicReference<QNode>(dummy));
+        UNSAFE.putObjectVolatile(this, tailOffset,
+                                  new PaddedAtomicReference<QNode>(dummy));
+        UNSAFE.putObjectVolatile(this, cleanMeOffset,
+                                  new PaddedAtomicReference<QNode>(null));
+    }
 
     // Temporary Unsafe mechanics for preliminary release
-    private static final Unsafe _unsafe;
+    private static Unsafe getUnsafe() throws Throwable {
+        try {
+            return Unsafe.getUnsafe();
+        } catch (SecurityException se) {
+            try {
+                return java.security.AccessController.doPrivileged
+                    (new java.security.PrivilegedExceptionAction<Unsafe>() {
+                        public Unsafe run() throws Exception {
+                            return getUnsafePrivileged();
+                        }});
+            } catch (java.security.PrivilegedActionException e) {
+                throw e.getCause();
+            }
+        }
+    }
+
+    private static Unsafe getUnsafePrivileged()
+            throws NoSuchFieldException, IllegalAccessException {
+        Field f = Unsafe.class.getDeclaredField("theUnsafe");
+        f.setAccessible(true);
+        return (Unsafe) f.get(null);
+    }
+
+    private static long fieldOffset(String fieldName)
+            throws NoSuchFieldException {
+        return UNSAFE.objectFieldOffset
+            (LinkedTransferQueue.class.getDeclaredField(fieldName));
+    }
+
+    private static final Unsafe UNSAFE;
     private static final long headOffset;
     private static final long tailOffset;
     private static final long cleanMeOffset;
     static {
         try {
-            if (LinkedTransferQueue.class.getClassLoader() != null) {
-                Field f = Unsafe.class.getDeclaredField("theUnsafe");
-                f.setAccessible(true);
-                _unsafe = (Unsafe)f.get(null);
-            }
-            else
-                _unsafe = Unsafe.getUnsafe();
-            headOffset = _unsafe.objectFieldOffset
-                (LinkedTransferQueue.class.getDeclaredField("head"));
-            tailOffset = _unsafe.objectFieldOffset
-                (LinkedTransferQueue.class.getDeclaredField("tail"));
-            cleanMeOffset = _unsafe.objectFieldOffset
-                (LinkedTransferQueue.class.getDeclaredField("cleanMe"));
-        } catch (Exception e) {
+            UNSAFE = getUnsafe();
+            headOffset = fieldOffset("head");
+            tailOffset = fieldOffset("tail");
+            cleanMeOffset = fieldOffset("cleanMe");
+        } catch (Throwable e) {
             throw new RuntimeException("Could not initialize intrinsics", e);
         }
     }
 
-    private void resetHeadAndTail() {
-        QNode dummy = new QNode(null, false);
-        _unsafe.putObjectVolatile(this, headOffset,
-                                  new PaddedAtomicReference<QNode>(dummy));
-        _unsafe.putObjectVolatile(this, tailOffset,
-                                  new PaddedAtomicReference<QNode>(dummy));
-        _unsafe.putObjectVolatile(this, cleanMeOffset,
-                                  new PaddedAtomicReference<QNode>(null));
-
-    }
-
 }