--- jsr166/src/jsr166y/LinkedTransferQueue.java	2009/10/24 14:57:32	1.52
+++ jsr166/src/jsr166y/LinkedTransferQueue.java	2009/11/02 00:28:28	1.61
@@ -373,6 +373,7 @@ public class LinkedTransferQueue<E> exte
         }
 
         final boolean casItem(Object cmp, Object val) {
+            assert cmp == null || cmp.getClass() != Node.class;
             return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
         }
 
@@ -409,7 +410,14 @@ public class LinkedTransferQueue<E> exte
          */
         final boolean isMatched() {
             Object x = item;
-            return x == this || (x != null) != isData;
+            return (x == this) || ((x == null) == isData);
+        }
+
+        /**
+         * Returns true if this is an unmatched request node.
+         */
+        final boolean isUnmatchedRequest() {
+            return !isData && item == null;
         }
 
         /**
@@ -427,6 +435,7 @@ public class LinkedTransferQueue<E> exte
          * Tries to artificially match a data node -- used by remove.
          */
         final boolean tryMatchData() {
+            assert isData;
             Object x = item;
             if (x != null && x != this && casItem(x, null)) {
                 LockSupport.unpark(waiter);
@@ -448,10 +457,10 @@ public class LinkedTransferQueue<E> exte
     }
 
     /** head of the queue; null until first enqueue */
-    private transient volatile Node head;
+    transient volatile Node head;
 
     /** predecessor of dangling unspliceable node */
-    private transient volatile Node cleanMe; // decl here to reduce contention
+    private transient volatile Node cleanMe; // decl here reduces contention
 
     /** tail of the queue; null until first append */
     private transient volatile Node tail;
@@ -478,6 +487,12 @@ public class LinkedTransferQueue<E> exte
     private static final int SYNC    = 2; // for transfer, take
     private static final int TIMEOUT = 3; // for timed poll, tryTransfer
 
+    @SuppressWarnings("unchecked")
+    static <E> E cast(Object item) {
+        assert item == null || item.getClass() != Node.class;
+        return (E) item;
+    }
+
     /**
      * Implements all queuing methods. See above for explanation.
      *
@@ -488,7 +503,7 @@ public class LinkedTransferQueue<E> exte
      * @return an item if matched, else e
      * @throws NullPointerException if haveData mode but e is null
      */
-    private Object xfer(Object e, boolean haveData, int how, long nanos) {
+    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
@@ -515,7 +530,7 @@ public class LinkedTransferQueue<E> exte
                                 break;        // unless slack < 2
                         }
                         LockSupport.unpark(p.waiter);
-                        return item;
+                        return this.<E>cast(item);
                     }
                 }
                 Node n = p.next;
@@ -545,7 +560,7 @@ public class LinkedTransferQueue<E> exte
      * predecessor
      */
     private Node tryAppend(Node s, boolean haveData) {
-        for (Node t = tail, p = t;;) { // move p to last node and append
+        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))
@@ -582,8 +597,7 @@ public class LinkedTransferQueue<E> exte
      * @param nanos timeout value
      * @return matched item, or e if unmatched on interrupt or timeout
      */
-    private Object awaitMatch(Node s, Node pred, Object e,
-                              int how, long nanos) {
+    private E awaitMatch(Node s, Node pred, E e, int how, long nanos) {
         long lastTime = (how == TIMEOUT) ? System.nanoTime() : 0L;
         Thread w = Thread.currentThread();
         int spins = -1; // initialized after first item and cancel checks
@@ -592,11 +606,12 @@ public class LinkedTransferQueue<E> exte
         for (;;) {
             Object item = s.item;
             if (item != e) {                  // matched
+                assert item != s;
                 s.forgetContents();           // avoid garbage
-                return item;
+                return this.<E>cast(item);
             }
             if ((w.isInterrupted() || (how == TIMEOUT && nanos <= 0)) &&
-                     s.casItem(e, s)) {       // cancel
+                    s.casItem(e, s)) {       // cancel
                 unsplice(pred, s);
                 return e;
             }
@@ -683,14 +698,14 @@ public class LinkedTransferQueue<E> exte
 
     /**
      * Returns the item in the first unmatched node with isData; or
-     * null if none. Used by peek.
+     * null if none.  Used by peek.
      */
-    private Object firstDataItem() {
+    private E firstDataItem() {
         for (Node p = head; p != null; ) {
             boolean isData = p.isData;
             Object item = p.item;
             if (item != p && (item != null) == isData)
-                return isData ? item : null;
+                return isData ? this.<E>cast(item) : null;
             Node n = p.next;
             p = (n != p) ? n : head;
         }
@@ -723,13 +738,15 @@ public class LinkedTransferQueue<E> exte
 
     final class Itr implements Iterator<E> {
         private Node nextNode;   // next node to return item for
-        private Object nextItem; // the corresponding item
+        private E nextItem;      // the corresponding item
         private Node lastRet;    // last returned node, to support remove
+        private Node lastPred;   // predecessor to unlink lastRet
 
         /**
          * Moves to next node after prev, or first node if prev null.
          */
         private void advance(Node prev) {
+            lastPred = lastRet;
             lastRet = prev;
             Node p;
             if (prev == null || (p = prev.next) == prev)
@@ -738,7 +755,7 @@ public class LinkedTransferQueue<E> exte
                 Object item = p.item;
                 if (p.isData) {
                     if (item != null && item != p) {
-                        nextItem = item;
+                        nextItem = LinkedTransferQueue.this.<E>cast(item);
                         nextNode = p;
                         return;
                     }
@@ -762,16 +779,15 @@ public class LinkedTransferQueue<E> exte
         public final E next() {
             Node p = nextNode;
             if (p == null) throw new NoSuchElementException();
-            Object e = nextItem;
+            E e = nextItem;
             advance(p);
-            return (E) e;
+            return e;
         }
 
         public final void remove() {
             Node p = lastRet;
             if (p == null) throw new IllegalStateException();
-            lastRet = null;
-            findAndRemoveNode(p);
+            findAndRemoveDataNode(lastPred, p);
         }
     }
 
@@ -805,8 +821,10 @@ public class LinkedTransferQueue<E> exte
                     break;
                 }
                 if (oldpred == pred ||      // Already saved
-                    (oldpred == null && casCleanMe(null, pred)))
-                    break;                  // Postpone cleaning
+                    ((oldpred == null || oldpred.next == s) &&
+                     casCleanMe(oldpred, pred))) {
+                    break;
+                }
             }
         }
     }
@@ -847,23 +865,28 @@ public class LinkedTransferQueue<E> exte
 
     /**
      * Main implementation of Iterator.remove(). Find
-     * and unsplice the given node.
+     * and unsplice the given data node.
+     * @param possiblePred possible predecessor of s
+     * @param s the node to remove
      */
-    final void findAndRemoveNode(Node s) {
+    final void findAndRemoveDataNode(Node possiblePred, Node s) {
+        assert s.isData;
         if (s.tryMatchData()) {
-            Node pred = null;
-            Node p = head;
-            while (p != null) {
-                if (p == s) {
-                    unsplice(pred, p);
-                    break;
-                }
-                if (!p.isData && !p.isMatched())
-                    break;
-                pred = p;
-                if ((p = p.next) == pred) { // stale
-                    pred = null;
-                    p = head;
+            if (possiblePred != null && possiblePred.next == s)
+                unsplice(possiblePred, s); // was actual predecessor
+            else {
+                for (Node pred = null, p = head; p != null; ) {
+                    if (p == s) {
+                        unsplice(pred, p);
+                        break;
+                    }
+                    if (p.isUnmatchedRequest())
+                        break;
+                    pred = p;
+                    if ((p = p.next) == pred) { // stale
+                        pred = null;
+                        p = head;
+                    }
                 }
             }
         }
@@ -874,9 +897,7 @@ public class LinkedTransferQueue<E> exte
      */
     private boolean findAndRemove(Object e) {
         if (e != null) {
-            Node pred = null;
-            Node p = head;
-            while (p != null) {
+            for (Node pred = null, p = head; p != null; ) {
                 Object item = p.item;
                 if (p.isData) {
                     if (item != null && item != p && e.equals(item) &&
@@ -888,7 +909,7 @@ public class LinkedTransferQueue<E> exte
                 else if (item == null)
                     break;
                 pred = p;
-                if ((p = p.next) == pred) {
+                if ((p = p.next) == pred) { // stale
                     pred = null;
                     p = head;
                 }
@@ -1024,22 +1045,22 @@ public class LinkedTransferQueue<E> exte
     }
 
     public E take() throws InterruptedException {
-        Object e = xfer(null, false, SYNC, 0);
+        E e = xfer(null, false, SYNC, 0);
         if (e != null)
-            return (E)e;
+            return e;
         Thread.interrupted();
         throw new InterruptedException();
     }
 
     public E poll(long timeout, TimeUnit unit) throws InterruptedException {
-        Object e = xfer(null, false, TIMEOUT, unit.toNanos(timeout));
+        E e = xfer(null, false, TIMEOUT, unit.toNanos(timeout));
         if (e != null || !Thread.interrupted())
-            return (E)e;
+            return e;
         throw new InterruptedException();
     }
 
     public E poll() {
-        return (E)xfer(null, false, NOW, 0);
+        return xfer(null, false, NOW, 0);
     }
 
     /**
@@ -1096,7 +1117,7 @@ public class LinkedTransferQueue<E> exte
     }
 
     public E peek() {
-        return (E) firstDataItem();
+        return firstDataItem();
     }
 
     /**
@@ -1192,7 +1213,6 @@ public class LinkedTransferQueue<E> exte
         }
     }
 
-
     // Unsafe mechanics
 
     private static final sun.misc.Unsafe UNSAFE = getUnsafe();
@@ -1215,7 +1235,14 @@ public class LinkedTransferQueue<E> exte
         }
     }
 
-    private static sun.misc.Unsafe getUnsafe() {
+    /**
+     * Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
+     * Replace with a simple call to Unsafe.getUnsafe when integrating
+     * into a jdk.
+     *
+     * @return a sun.misc.Unsafe
+     */
+    static sun.misc.Unsafe getUnsafe() {
         try {
             return sun.misc.Unsafe.getUnsafe();
         } catch (SecurityException se) {