jdk-sandbox: comparison src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java

equal deleted inserted replaced

-:186868cadb5d
+:83f933b97787
 * to check whether we have reached a TERMINATOR node; if so,
 * restart traversal from tail.
 *
 * The implementation is completely directionally symmetrical,
 * except that most public methods that iterate through the list
-* follow next pointers ("forward" direction).
+* follow next pointers, in the "forward" direction.
 *
-* We believe (without full proof) that all single-element deque
+* We believe (without full proof) that all single-element Deque
-* operations (e.g., addFirst, peekLast, pollLast) are linearizable
+* operations that operate directly at the two ends of the Deque
-* (see Herlihy and Shavit's book).  However, some combinations of
+* (e.g., addFirst, peekLast, pollLast) are linearizable (see
+* Herlihy and Shavit's book).  However, some combinations of
 * operations are known not to be linearizable.  In particular,
-* when an addFirst(A) is racing with pollFirst() removing B, it is
+* when an addFirst(A) is racing with pollFirst() removing B, it
-* possible for an observer iterating over the elements to observe
+* is possible for an observer iterating over the elements to
-* A B C and subsequently observe A C, even though no interior
+* observe first [A B C] and then [A C], even though no interior
 * removes are ever performed.  Nevertheless, iterators behave
 * reasonably, providing the "weakly consistent" guarantees.
 *
 * Empirically, microbenchmarks suggest that this class adds about
 * 40% overhead relative to ConcurrentLinkedQueue, which feels as
 linkLast(e);
 return true;
 }
 public E peekFirst() {
-for (Node<E> p = first(); p != null; p = succ(p)) {
+restart: for (;;) {
-final E item;
+for (Node<E> first = first(), p = first;;) {
-if ((item = p.item) != null)
+final E item;
-return item;
+if ((item = p.item) != null) {
-}
+// recheck for linearizability
-return null;
+if (first.prev != null) continue restart;
+return item;
+}
+if ((p = succ(p)) == null)
+return null;
+}
+}
 }
 public E peekLast() {
-for (Node<E> p = last(); p != null; p = pred(p)) {
+restart: for (;;) {
-final E item;
+for (Node<E> last = last(), p = last;;) {
-if ((item = p.item) != null)
+final E item;
-return item;
+if ((item = p.item) != null) {
-}
+// recheck for linearizability
-return null;
+if (last.next != null) continue restart;
+return item;
+}
+if ((p = pred(p)) == null)
+return null;
+}
+}
 }
 /**
 * @throws NoSuchElementException {@inheritDoc}
 */
 public E getLast() {
 return screenNullResult(peekLast());
 }
 public E pollFirst() {
-for (Node<E> p = first(); p != null; p = succ(p)) {
+restart: for (;;) {
-final E item;
+for (Node<E> first = first(), p = first;;) {
-if ((item = p.item) != null
+final E item;
-&& ITEM.compareAndSet(p, item, null)) {
+if ((item = p.item) != null) {
-unlink(p);
+// recheck for linearizability
-return item;
+if (first.prev != null) continue restart;
-}
+if (ITEM.compareAndSet(p, item, null)) {
-}
+unlink(p);
-return null;
+return item;
+}
+}
+if ((p = succ(p)) == null)
+return null;
+}
+}
 }
 public E pollLast() {
-for (Node<E> p = last(); p != null; p = pred(p)) {
+restart: for (;;) {
-final E item;
+for (Node<E> last = last(), p = last;;) {
-if ((item = p.item) != null
+final E item;
-&& ITEM.compareAndSet(p, item, null)) {
+if ((item = p.item) != null) {
-unlink(p);
+// recheck for linearizability
-return item;
+if (last.next != null) continue restart;
-}
+if (ITEM.compareAndSet(p, item, null)) {
-}
+unlink(p);
-return null;
+return item;
+}
+}
+if ((p = pred(p)) == null)
+return null;
+}
+}
 }
 /**
 * @throws NoSuchElementException {@inheritDoc}
 */
 * useful in concurrent applications.
 *
 * @return the number of elements in this deque
 */
 public int size() {
-restartFromHead: for (;;) {
+restart: for (;;) {
 int count = 0;
 for (Node<E> p = first(); p != null;) {
 if (p.item != null)
 if (++count == Integer.MAX_VALUE)
 break;  // @see Collection.size()
 if (p == (p = p.next))
-continue restartFromHead;
+continue restart;
 }
 return count;
 }
 }
 ;
 }
 public String toString() {
 String[] a = null;
-restartFromHead: for (;;) {
+restart: for (;;) {
 int charLength = 0;
 int size = 0;
 for (Node<E> p = first(); p != null;) {
 final E item;
 if ((item = p.item) != null) {
 String s = item.toString();
 a[size++] = s;
 charLength += s.length();
 }
 if (p == (p = p.next))
-continue restartFromHead;
+continue restart;
 }
 if (size == 0)
 return "[]";
 }
 }
 private Object[] toArrayInternal(Object[] a) {
 Object[] x = a;
-restartFromHead: for (;;) {
+restart: for (;;) {
 int size = 0;
 for (Node<E> p = first(); p != null;) {
 final E item;
 if ((item = p.item) != null) {
 if (x == null)
 else if (size == x.length)
 x = Arrays.copyOf(x, 2 * (size + 4));
 x[size++] = item;
 }
 if (p == (p = p.next))
-continue restartFromHead;
+continue restart;
 }
 if (x == null)
 return new Object[0];
 else if (a != null && size <= a.length) {
 if (a != x)

changeset 47340	83f933b97787
parent 47216	71c04702a3d5
child 47729	1563167c9520