src/share/classes/java/util/concurrent/LinkedBlockingDeque.java

@@ -124,14 +124,12 @@
          * - this Node, meaning the successor is head
          * - null, meaning there is no successor
          */
         Node<E> next;
 
-        Node(E x, Node<E> p, Node<E> n) {
+        Node(E x) {
             item = x;
-            prev = p;
-            next = n;
         }
     }
 
     /**
      * Pointer to first node.

@@ -197,11 +195,11 @@
         lock.lock(); // Never contended, but necessary for visibility
         try {
             for (E e : c) {
                 if (e == null)
                     throw new NullPointerException();
-                if (!linkLast(e))
+                if (!linkLast(new Node<E>(e)))
                     throw new IllegalStateException("Deque full");
             }
         } finally {
             lock.unlock();
         }

@@ -209,42 +207,42 @@
 
 
     // Basic linking and unlinking operations, called only while holding lock
 
     /**
-     * Links e as first element, or returns false if full.
+     * Links node as first element, or returns false if full.
      */
-    private boolean linkFirst(E e) {
+    private boolean linkFirst(Node<E> node) {
         // assert lock.isHeldByCurrentThread();
         if (count >= capacity)
             return false;
         Node<E> f = first;
-        Node<E> x = new Node<E>(e, null, f);
-        first = x;
+        node.next = f;
+        first = node;
         if (last == null)
-            last = x;
+            last = node;
         else
-            f.prev = x;
+            f.prev = node;
         ++count;
         notEmpty.signal();
         return true;
     }
 
     /**
-     * Links e as last element, or returns false if full.
+     * Links node as last element, or returns false if full.
      */
-    private boolean linkLast(E e) {
+    private boolean linkLast(Node<E> node) {
         // assert lock.isHeldByCurrentThread();
         if (count >= capacity)
             return false;
         Node<E> l = last;
-        Node<E> x = new Node<E>(e, l, null);
-        last = x;
+        node.prev = l;
+        last = node;
         if (first == null)
-            first = x;
+            first = node;
         else
-            l.next = x;
+            l.next = node;
         ++count;
         notEmpty.signal();
         return true;
     }
 

@@ -337,14 +335,15 @@
     /**
      * @throws NullPointerException {@inheritDoc}
      */
     public boolean offerFirst(E e) {
         if (e == null) throw new NullPointerException();
+        Node<E> node = new Node<E>(e);
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return linkFirst(e);
+            return linkFirst(node);
         } finally {
             lock.unlock();
         }
     }
 

@@ -351,14 +350,15 @@
     /**
      * @throws NullPointerException {@inheritDoc}
      */
     public boolean offerLast(E e) {
         if (e == null) throw new NullPointerException();
+        Node<E> node = new Node<E>(e);
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return linkLast(e);
+            return linkLast(node);
         } finally {
             lock.unlock();
         }
     }
 

@@ -366,14 +366,15 @@
      * @throws NullPointerException {@inheritDoc}
      * @throws InterruptedException {@inheritDoc}
      */
     public void putFirst(E e) throws InterruptedException {
         if (e == null) throw new NullPointerException();
+        Node<E> node = new Node<E>(e);
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            while (!linkFirst(e))
+            while (!linkFirst(node))
                 notFull.await();
         } finally {
             lock.unlock();
         }
     }

@@ -382,14 +383,15 @@
      * @throws NullPointerException {@inheritDoc}
      * @throws InterruptedException {@inheritDoc}
      */
     public void putLast(E e) throws InterruptedException {
         if (e == null) throw new NullPointerException();
+        Node<E> node = new Node<E>(e);
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            while (!linkLast(e))
+            while (!linkLast(node))
                 notFull.await();
         } finally {
             lock.unlock();
         }
     }

@@ -399,15 +401,16 @@
      * @throws InterruptedException {@inheritDoc}
      */
     public boolean offerFirst(E e, long timeout, TimeUnit unit)
         throws InterruptedException {
         if (e == null) throw new NullPointerException();
+        Node<E> node = new Node<E>(e);
         long nanos = unit.toNanos(timeout);
         final ReentrantLock lock = this.lock;
         lock.lockInterruptibly();
         try {
-            while (!linkFirst(e)) {
+            while (!linkFirst(node)) {
                 if (nanos <= 0)
                     return false;
                 nanos = notFull.awaitNanos(nanos);
             }
             return true;

@@ -421,15 +424,16 @@
      * @throws InterruptedException {@inheritDoc}
      */
     public boolean offerLast(E e, long timeout, TimeUnit unit)
         throws InterruptedException {
         if (e == null) throw new NullPointerException();
+        Node<E> node = new Node<E>(e);
         long nanos = unit.toNanos(timeout);
         final ReentrantLock lock = this.lock;
         lock.lockInterruptibly();
         try {
-            while (!linkLast(e)) {
+            while (!linkLast(node)) {
                 if (nanos <= 0)
                     return false;
                 nanos = notFull.awaitNanos(nanos);
             }
             return true;

@@ -953,11 +957,24 @@
 
     public String toString() {
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return super.toString();
+            Node<E> p = first;
+            if (p == null)
+                return "[]";
+
+            StringBuilder sb = new StringBuilder();
+            sb.append('[');
+            for (;;) {
+                E e = p.item;
+                sb.append(e == this ? "(this Collection)" : e);
+                p = p.next;
+                if (p == null)
+                    return sb.append(']').toString();
+                sb.append(',').append(' ');
+            }
         } finally {
             lock.unlock();
         }
     }
 

@@ -1052,27 +1069,38 @@
                 lock.unlock();
             }
         }
 
         /**
+         * Returns the successor node of the given non-null, but
+         * possibly previously deleted, node.
+         */
+        private Node<E> succ(Node<E> n) {
+            // Chains of deleted nodes ending in null or self-links
+            // are possible if multiple interior nodes are removed.
+            for (;;) {
+                Node<E> s = nextNode(n);
+                if (s == null)
+                    return null;
+                else if (s.item != null)
+                    return s;
+                else if (s == n)
+                    return firstNode();
+                else
+                    n = s;
+            }
+        }
+
+        /**
          * Advances next.
          */
         void advance() {
             final ReentrantLock lock = LinkedBlockingDeque.this.lock;
             lock.lock();
             try {
                 // assert next != null;
-                Node<E> s = nextNode(next);
-                if (s == next) {
-                    next = firstNode();
-                } else {
-                    // Skip over removed nodes.
-                    // May be necessary if multiple interior Nodes are removed.
-                    while (s != null && s.item == null)
-                        s = nextNode(s);
-                    next = s;
-                }
+                next = succ(next);
                 nextItem = (next == null) ? null : next.item;
             } finally {
                 lock.unlock();
             }
         }