Fix ArrayDeque's bug when expanding capacity.
Also fixes concurrent modification check for the case
when head > tail.
Bug: #9404
Bug-Link: https://github.com/gwtproject/gwt/issues/9404
Change-Id: I9e13b1c80ddad1c69d8863855d2f4f6fb62b1b6f
diff --git a/user/super/com/google/gwt/emul/java/util/ArrayDeque.java b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
index 619b7e8..694593f 100644
--- a/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
+++ b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
@@ -72,7 +72,6 @@
@Override
public void remove() {
checkState(lastIndex >= 0);
- checkConcurrentModification(head <= lastIndex && lastIndex < tail);
if (removeAtIndex(lastIndex) < 0) {
// if left-shifted, undo increment in next()
@@ -107,7 +106,6 @@
@Override
public void remove() {
checkState(lastIndex >= 0);
- checkConcurrentModification(head <= lastIndex && lastIndex < tail);
if (removeAtIndex(lastIndex) > 0) {
// if right-shifted, undo decrement in next()
@@ -382,11 +380,7 @@
if (out.length < size) {
out = ArrayHelper.createFrom(out, size);
}
- Object[] dest = out;
- final int mask = size - 1;
- for (int i = head, dstIdx = 0; dstIdx < size; i = (i + 1) & mask, ++dstIdx) {
- dest[dstIdx] = array[i];
- }
+ copyElements(out, size);
if (out.length > size) {
out[size] = null;
}
@@ -423,6 +417,19 @@
}
/**
+ * Copies {@code count} ArrayDeque's elements to {@code dest} array.
+ * The method is safe to use when ArrayDeque's array has been rolled over,
+ * i.e. {@code head == tail}.
+ * It is assumed that {@code count < size()}.
+ */
+ private void copyElements(Object[] dest, int count) {
+ final int mask = array.length - 1;
+ for (int i = head, dstIdx = 0; dstIdx < count; i = (i + 1) & mask, ++dstIdx) {
+ dest[dstIdx] = array[i];
+ }
+ }
+
+ /**
* Increase the capacity of this deque when full, i.e.,
* when head and tail have wrapped around to become equal.
*/
@@ -435,11 +442,12 @@
int newLength = nextArrayLength(numElements);
if (head != 0) {
E[] newArray = ArrayHelper.createFrom(array, newLength);
- array = toArray(newArray);
+ copyElements(newArray, numElements);
+ array = newArray;
+ head = 0;
} else {
ArrayHelper.setLength(array, newLength);
}
- head = 0;
tail = numElements;
}
@@ -454,6 +462,9 @@
final int mask = array.length - 1;
int headDistance = (i - head) & mask;
int tailDistance = (tail - i) & mask;
+ int size = (tail - head) & mask;
+
+ checkConcurrentModification(headDistance < size);
if (headDistance >= tailDistance) {
shiftLeftAtIndex(i);
return -1;
diff --git a/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
index 9915e2a..13e5a09 100644
--- a/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
@@ -822,6 +822,28 @@
assertFalse(deque.removeLastOccurrence(null));
}
+ public void testRolloverInvariants() {
+ ArrayDeque<Integer> deque = new ArrayDeque<>();
+
+ assertTrue(deque.add(1));
+ assertEquals(1, (int) deque.removeFirst());
+ for (int i = 0; i < 100; i++) {
+ assertTrue(deque.add(i));
+ }
+ assertNotNull(deque.peek());
+ assertFalse(deque.isEmpty());
+
+ Iterator<Integer> it = deque.iterator();
+ for (int i = 0; i < 100; i++) {
+ assertTrue(it.hasNext());
+ assertEquals(i, (int) it.next());
+ it.remove();
+ }
+ assertFalse(it.hasNext());
+ assertNull(deque.peek());
+ assertTrue(deque.isEmpty());
+ }
+
/**
* Null elements are prohibited in ArrayDeque.
*/
