Refactors LinkedList to not use circular list.
The new implementation is using double pivot instead of
single.
This is to make LinkedList safer when preconditions are
not enabled and iterator is not used properly.
For example, with a circular list, if you keep calling
next/remove you might never hit an NPE because it will
eventually come back to beginning and start iterating
again.
This might be a little bit on the paranoid side but given
the new implementation is no more complex, it is a good
trade-off.
Change-Id: I4915d5c7b3a6a0e48b96c14be4ce0d64bf3b0de2
Review-Link: https://gwt-review.googlesource.com/#/c/9363/
diff --git a/user/super/com/google/gwt/emul/java/util/LinkedList.java b/user/super/com/google/gwt/emul/java/util/LinkedList.java
index ae82156..a276656 100644
--- a/user/super/com/google/gwt/emul/java/util/LinkedList.java
+++ b/user/super/com/google/gwt/emul/java/util/LinkedList.java
@@ -15,8 +15,9 @@
*/
package java.util;
-import static com.google.gwt.core.shared.impl.GwtPreconditions.checkCriticalElement;
+import static com.google.gwt.core.shared.impl.GwtPreconditions.checkElement;
import static com.google.gwt.core.shared.impl.GwtPreconditions.checkPositionIndex;
+import static com.google.gwt.core.shared.impl.GwtPreconditions.checkState;
import java.io.Serializable;
@@ -30,13 +31,13 @@
public class LinkedList<E> extends AbstractSequentialList<E> implements
Cloneable, List<E>, Deque<E>, Serializable {
/*
- * This implementation uses a doubly-linked circular list with a header node.
+ * This implementation uses a doubly-linked list with a header/tail node.
*
* TODO(jat): add more efficient subList implementation.
*/
private final class DescendingIteratorImpl implements Iterator<E> {
- private final ListIterator<E> itr = new ListIteratorImpl(size, header);
+ private final ListIterator<E> itr = new ListIteratorImpl(size, tail);
@Override
public boolean hasNext() {
@@ -84,70 +85,73 @@
currentIndex = index;
}
+ @Override
public void add(E o) {
- addBefore(o, currentNode);
+ addNode(o, currentNode.prev, currentNode);
++currentIndex;
lastNode = null;
}
+ @Override
public boolean hasNext() {
- return currentNode != header;
+ return currentNode != tail;
}
+ @Override
public boolean hasPrevious() {
return currentNode.prev != header;
}
+ @Override
public E next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
+ checkElement(hasNext());
+
lastNode = currentNode;
currentNode = currentNode.next;
++currentIndex;
return lastNode.value;
}
+ @Override
public int nextIndex() {
return currentIndex;
}
+ @Override
public E previous() {
- if (!hasPrevious()) {
- throw new NoSuchElementException();
- }
+ checkElement(hasPrevious());
+
lastNode = currentNode = currentNode.prev;
--currentIndex;
return lastNode.value;
}
+ @Override
public int previousIndex() {
return currentIndex - 1;
}
+ @Override
public void remove() {
- verifyCurrentElement();
+ checkState(lastNode != null);
+
+ Node<E> nextNode = lastNode.next;
+ removeNode(lastNode);
if (currentNode == lastNode) {
// We just did a previous().
- currentNode = lastNode.next;
+ currentNode = nextNode;
} else {
// We just did a next().
--currentIndex;
}
- lastNode.remove();
lastNode = null;
- --size;
}
+ @Override
public void set(E o) {
- verifyCurrentElement();
- lastNode.value = o;
- }
+ checkState(lastNode != null);
- protected void verifyCurrentElement() {
- if (lastNode == null) {
- throw new IllegalStateException();
- }
+ lastNode.value = o;
}
}
@@ -160,38 +164,6 @@
public Node<E> next;
public Node<E> prev;
public E value;
-
- public Node() {
- next = prev = this;
- }
-
- public Node(E value) {
- this.value = value;
- }
-
- /**
- * Construct a node containing a value and add it before the specified node.
- *
- * @param value
- * @param nextNode
- */
- public Node(E value, Node<E> nextNode) {
- this(value);
- this.next = nextNode;
- this.prev = nextNode.prev;
- nextNode.prev.next = this;
- nextNode.prev = this;
- }
-
- /**
- * Remove this node from any list it is in, leaving it with circular
- * references to itself.
- */
- public void remove() {
- this.next.prev = this.prev;
- this.prev.next = this.next;
- this.next = this.prev = this;
- }
}
/**
@@ -202,11 +174,14 @@
private E exposeElement;
/**
- * Header node - header.next is the first element of the list, and header.prev
- * is the last element of the list. If the list is empty, the header node will
- * point to itself.
+ * Header node - header.next is the first element of the list.
*/
- private Node<E> header;
+ private final Node<E> header = new Node<E>();
+
+ /**
+ * Tail node - tail.prev is the last element of the list.
+ */
+ private final Node<E> tail = new Node<E>();
/**
* Number of nodes currently present in the list.
@@ -214,11 +189,11 @@
private int size;
public LinkedList() {
- clear();
+ reset();
}
public LinkedList(Collection<? extends E> c) {
- this();
+ reset();
addAll(c);
}
@@ -228,19 +203,25 @@
return true;
}
+ @Override
public void addFirst(E o) {
- new Node<E>(o, header.next);
- ++size;
+ addNode(o, header, header.next);
}
+ @Override
public void addLast(E o) {
- new Node<E>(o, header);
- ++size;
+ addNode(o, tail.prev, tail);
}
@Override
public void clear() {
- header = new Node<E>();
+ reset();
+ }
+
+ private void reset() {
+ header.next = tail;
+ tail.prev = header;
+ header.prev = tail.next = null;
size = 0;
}
@@ -253,20 +234,23 @@
return new DescendingIteratorImpl();
}
+ @Override
public E element() {
return getFirst();
}
+ @Override
public E getFirst() {
- checkCriticalElement(size != 0);
+ checkElement(size != 0);
return header.next.value;
}
+ @Override
public E getLast() {
- checkCriticalElement(size != 0);
+ checkElement(size != 0);
- return header.prev.value;
+ return tail.prev.value;
}
@Override
@@ -276,7 +260,7 @@
Node<E> node;
// start from the nearest end of the list
if (index >= size >> 1) {
- node = header;
+ node = tail;
for (int i = size; i > index; --i) {
node = node.prev;
}
@@ -290,6 +274,7 @@
return new ListIteratorImpl(index, node);
}
+ @Override
public boolean offer(E o) {
return offerLast(o);
}
@@ -306,48 +291,34 @@
return true;
}
+ @Override
public E peek() {
return peekFirst();
}
@Override
public E peekFirst() {
- if (size == 0) {
- return null;
- } else {
- return getFirst();
- }
+ return size == 0 ? null : getFirst();
}
@Override
public E peekLast() {
- if (size == 0) {
- return null;
- } else {
- return getLast();
- }
+ return size == 0 ? null : getLast();
}
+ @Override
public E poll() {
return pollFirst();
}
@Override
public E pollFirst() {
- if (size == 0) {
- return null;
- } else {
- return removeFirst();
- }
+ return size == 0 ? null : removeFirst();
}
@Override
public E pollLast() {
- if (size == 0) {
- return null;
- } else {
- return removeLast();
- }
+ return size == 0 ? null : removeLast();
}
@Override
@@ -360,13 +331,16 @@
addFirst(e);
}
+ @Override
public E remove() {
return removeFirst();
}
+ @Override
public E removeFirst() {
- Node<E> node = removeNode(header.next);
- return node.value;
+ checkElement(size != 0);
+
+ return removeNode(header.next);
}
@Override
@@ -374,14 +348,16 @@
return remove(o);
}
+ @Override
public E removeLast() {
- Node<E> node = removeNode(header.prev);
- return node.value;
+ checkElement(size != 0);
+
+ return removeNode(tail.prev);
}
@Override
public boolean removeLastOccurrence(Object o) {
- for (Node<E> e = header.prev; e != header; e = e.prev) {
+ for (Node<E> e = tail.prev; e != header; e = e.prev) {
if (Objects.equals(e.value, o)) {
removeNode(e);
return true;
@@ -395,16 +371,22 @@
return size;
}
- private void addBefore(E o, Node<E> target) {
- new Node<E>(o, target);
+ private void addNode(E o, Node<E> prev, Node<E> next) {
+ Node<E> node = new Node<E>();
+ node.value = o;
+ node.prev = prev;
+ node.next = next;
+ next.prev = prev.next = node;
++size;
}
- private Node<E> removeNode(Node<E> node) {
- checkCriticalElement(size != 0);
-
+ private E removeNode(Node<E> node) {
+ E oldValue = node.value;
+ node.next.prev = node.prev;
+ node.prev.next = node.next;
+ node.next = node.prev = null;
+ node.value = null;
--size;
- node.remove();
- return node;
+ return oldValue;
}
}
