Repository: calcite Updated Branches: refs/heads/master 2712d7daf -> 3cba70550
[CALCITE-1047] ChunkList.clear throws AssertionError Re-work ChunkList with a more robust implementation of ListIterator and more thorough tests. Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/3cba7055 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/3cba7055 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/3cba7055 Branch: refs/heads/master Commit: 3cba7055061108ce0e079d8756bcfb020b8628c3 Parents: 2712d7d Author: Julian Hyde <[email protected]> Authored: Tue Jan 12 20:14:51 2016 -0800 Committer: Julian Hyde <[email protected]> Committed: Wed Jan 13 08:43:29 2016 -0800 ---------------------------------------------------------------------- .../java/org/apache/calcite/util/ChunkList.java | 243 ++++++++++++------- .../org/apache/calcite/util/ChunkListTest.java | 217 ++++++++++++++--- 2 files changed, 340 insertions(+), 120 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/3cba7055/core/src/main/java/org/apache/calcite/util/ChunkList.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/ChunkList.java b/core/src/main/java/org/apache/calcite/util/ChunkList.java index 66644e9..8d7c9bf 100644 --- a/core/src/main/java/org/apache/calcite/util/ChunkList.java +++ b/core/src/main/java/org/apache/calcite/util/ChunkList.java @@ -17,6 +17,7 @@ package org.apache.calcite.util; import java.util.AbstractSequentialList; +import java.util.Arrays; import java.util.Collection; import java.util.LinkedList; import java.util.ListIterator; @@ -33,10 +34,6 @@ import java.util.NoSuchElementException; */ public class ChunkList<E> extends AbstractSequentialList<E> { private static final int HEADER_SIZE = 3; - private int size; - private Object[] first; - private Object[] last; - private static final int CHUNK_SIZE = 64; private static final Integer[] INTEGERS = new Integer[CHUNK_SIZE + 3]; @@ -46,6 +43,10 @@ public class ChunkList<E> extends AbstractSequentialList<E> { } } + private int size; + private Object[] first; + private Object[] last; + /** * Creates an empty ChunkList. */ @@ -105,6 +106,12 @@ public class ChunkList<E> extends AbstractSequentialList<E> { return size; } + @Override public void clear() { + // base class method works, but let's optimize + size = 0; + first = last = null; + } + @Override public boolean add(E element) { Object[] chunk = last; int occupied; @@ -169,18 +176,20 @@ public class ChunkList<E> extends AbstractSequentialList<E> { } private ChunkListIterator locate(int index) { - if (index == 0) { - return new ChunkListIterator(); + if (index < 0 || index > size) { + throw new IndexOutOfBoundsException(); + } + if (first == null) { + // Create an iterator positioned before the first element. + return new ChunkListIterator(null, 0, 0, -1, 0); } int n = 0; for (Object[] chunk = first;;) { final int occupied = occupied(chunk); final int nextN = n + occupied; final Object[] next = next(chunk); - if (nextN > index || next == null) { - return new ChunkListIterator( - chunk, n, index - n - 1 + HEADER_SIZE, - occupied + HEADER_SIZE); + if (nextN >= index || next == null) { + return new ChunkListIterator(chunk, n, index, -1, n + occupied); } n = nextN; chunk = next; @@ -190,76 +199,87 @@ public class ChunkList<E> extends AbstractSequentialList<E> { /** Iterator over a {@link ChunkList}. */ private class ChunkListIterator implements ListIterator<E> { private Object[] chunk; - private int startIndex; - private int offset; + /** Offset in the list of the first element of this chunk. */ + private int start; + /** Offset within current chunk of the next element to return. */ + private int cursor; + /** Offset within the current chunk of the last element returned. -1 if + * {@link #next} or {@link #previous()} has not been called. */ + private int lastRet; + /** Offset of the first unoccupied location in the current chunk. */ private int end; - ChunkListIterator() { - this(null, 0, -1, 0); - } - - ChunkListIterator(Object[] chunk, int startIndex, int offset, int end) { + ChunkListIterator(Object[] chunk, int start, int cursor, int lastRet, + int end) { this.chunk = chunk; - this.startIndex = startIndex; - this.offset = offset; + this.start = start; + this.cursor = cursor; + this.lastRet = lastRet; this.end = end; } public boolean hasNext() { - return offset + 1 < end - || (chunk == null - ? first != null - : ChunkList.next(chunk) != null); + return cursor < size; } public E next() { - ++offset; - assert offset <= end; - if (offset == end) { + if (cursor >= size) { + throw new NoSuchElementException(); + } + if (cursor == end) { if (chunk == null) { chunk = first; } else { chunk = ChunkList.next(chunk); - startIndex += end - HEADER_SIZE; } + start = end; if (chunk == null) { - throw new NoSuchElementException(); + end = start; + } else { + end = start + occupied(chunk); } - offset = HEADER_SIZE; - end = occupied(chunk) + HEADER_SIZE; } - return (E) element(chunk, offset); + @SuppressWarnings("unchecked") + final E element = (E) element(chunk, + HEADER_SIZE + (lastRet = cursor++) - start); + return element; } public boolean hasPrevious() { - return offset >= HEADER_SIZE || ChunkList.prev(chunk) != null; + return cursor > 0; } public E previous() { - --offset; - if (offset == HEADER_SIZE - 1) { + lastRet = cursor--; + if (cursor < start) { chunk = chunk == null ? last : ChunkList.prev(chunk); if (chunk == null) { throw new NoSuchElementException(); } - end = occupied(chunk); - startIndex -= end; - offset = end - 1; + final int o = occupied(chunk); + end = start; + start -= o; + assert cursor == end - 1; } - return (E) element(chunk, offset); + //noinspection unchecked + return (E) element(chunk, cursor - start); } public int nextIndex() { - return startIndex + (offset - HEADER_SIZE) + 1; + return cursor; } public int previousIndex() { - return startIndex + (offset - HEADER_SIZE); + return cursor - 1; } public void remove() { + if (lastRet < 0) { + throw new IllegalStateException(); + } --size; - if (end == HEADER_SIZE + 1) { + --cursor; + if (end == start + 1) { // Chunk is now empty. final Object[] prev = prev(chunk); final Object[] next = ChunkList.next(chunk); @@ -272,80 +292,125 @@ public class ChunkList<E> extends AbstractSequentialList<E> { } chunk = null; end = HEADER_SIZE; - offset = end - 1; } else { if (prev == null) { - first = next; + chunk = first = next; setPrev(next, null); + end = occupied(chunk); } else { setNext(prev, next); setPrev(next, prev); + chunk = prev; + end = start; + start -= occupied(chunk); } - chunk = next; - offset = HEADER_SIZE; - end = HEADER_SIZE + occupied(next); } + lastRet = -1; return; } - // Move existing contents down one. - System.arraycopy( - chunk, offset + 1, chunk, offset, end - offset - 1); - --end; - setElement(chunk, end, null); // allow gc - setOccupied(chunk, end - HEADER_SIZE); - if (offset == end) { - final Object[] next = ChunkList.next(chunk); - if (next != null) { - startIndex += end - HEADER_SIZE; - chunk = next; - offset = HEADER_SIZE - 1; - end = HEADER_SIZE + occupied(next); + final int r = lastRet; + lastRet = -1; + if (r < start) { + // Element we wish to eliminate is the last element in the previous + // block. + Object[] c = chunk; + if (c == null) { + c = last; } + int o = occupied(c); + if (o == 1) { + // Block is now empty; remove it + final Object[] prev = prev(c); + if (prev == null) { + if (chunk == null) { + first = last = null; + } else { + first = chunk; + setPrev(chunk, null); + } + } else { + setNext(prev, chunk); + setPrev(chunk, prev); + } + } else { + --o; + setElement(c, HEADER_SIZE + o, null); // allow gc + setOccupied(c, o); + } + } else { + // Move existing contents down one. + System.arraycopy(chunk, HEADER_SIZE + r - start + 1, + chunk, HEADER_SIZE + r - start, end - r - 1); + --end; + final int o = end - start; + setElement(chunk, HEADER_SIZE + o, null); // allow gc + setOccupied(chunk, o); } } public void set(E e) { - setElement(chunk, offset, e); + if (lastRet < 0) { + throw new IllegalStateException(); + } + Object[] c = chunk; + int p = lastRet; + int s = start; + if (p < start) { + // The element is at the end of the previous chunk + c = prev(c); + s -= occupied(c); + } + setElement(c, HEADER_SIZE + p - s, e); } public void add(E e) { - if (chunk == null || end == CHUNK_SIZE + HEADER_SIZE) { + if (chunk == null) { + Object[] newChunk = new Object[CHUNK_SIZE + HEADER_SIZE]; + if (first != null) { + setNext(newChunk, first); + setPrev(first, newChunk); + } + first = newChunk; + if (last == null) { + last = newChunk; + } + chunk = newChunk; + end = start; + } else if (end == start + CHUNK_SIZE) { // FIXME We create a new chunk, but the next chunk might be // less than half full. We should consider using it. Object[] newChunk = new Object[CHUNK_SIZE + HEADER_SIZE]; - if (chunk == null) { - if (first != null) { - setNext(newChunk, first); - setPrev(first, newChunk); - } - first = newChunk; - if (last == null) { - last = newChunk; - } + final Object[] next = ChunkList.next(chunk); + setPrev(newChunk, chunk); + setNext(chunk, newChunk); + + if (next == null) { + last = newChunk; } else { - final Object[] next = ChunkList.next(chunk); - setPrev(newChunk, chunk); - setNext(chunk, newChunk); + setPrev(next, newChunk); + setNext(newChunk, next); + } - if (next == null) { - last = newChunk; - } else { - setPrev(next, newChunk); - setNext(newChunk, next); - } - startIndex += CHUNK_SIZE; + setOccupied(chunk, CHUNK_SIZE / 2); + setOccupied(newChunk, CHUNK_SIZE / 2); + System.arraycopy(chunk, HEADER_SIZE + CHUNK_SIZE / 2, + newChunk, HEADER_SIZE, CHUNK_SIZE / 2); + Arrays.fill(chunk, HEADER_SIZE + CHUNK_SIZE / 2, + HEADER_SIZE + CHUNK_SIZE, null); + + if (cursor - start < CHUNK_SIZE / 2) { + end -= CHUNK_SIZE / 2; + } else { + start += CHUNK_SIZE / 2; + chunk = newChunk; } - chunk = newChunk; - end = offset = HEADER_SIZE; - } else { - // Move existing contents up one. - System.arraycopy( - chunk, offset, chunk, offset + 1, end - offset); } - setElement(chunk, offset, e); -// ++offset; + // Move existing contents up one. + System.arraycopy(chunk, HEADER_SIZE + cursor - start, + chunk, HEADER_SIZE + cursor - start + 1, end - cursor); ++end; - setOccupied(chunk, end - HEADER_SIZE); + setElement(chunk, HEADER_SIZE + cursor - start, e); + setOccupied(chunk, end - start); ++size; } } http://git-wip-us.apache.org/repos/asf/calcite/blob/3cba7055/core/src/test/java/org/apache/calcite/util/ChunkListTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/util/ChunkListTest.java b/core/src/test/java/org/apache/calcite/util/ChunkListTest.java index 0e2bb2d..efb1b09 100644 --- a/core/src/test/java/org/apache/calcite/util/ChunkListTest.java +++ b/core/src/test/java/org/apache/calcite/util/ChunkListTest.java @@ -19,6 +19,8 @@ package org.apache.calcite.util; import org.apache.calcite.linq4j.function.Function0; import org.apache.calcite.linq4j.function.Function1; +import com.google.common.collect.ImmutableList; + import org.junit.Test; import java.util.ArrayList; @@ -30,9 +32,11 @@ import java.util.List; import java.util.ListIterator; import java.util.Random; +import static org.hamcrest.CoreMatchers.is; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertThat; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; @@ -44,8 +48,13 @@ public class ChunkListTest { * Unit test for {@link ChunkList}. */ @Test public void testChunkList() { - final ChunkList<Integer> list = new ChunkList<Integer>(); + final ChunkList<Integer> list = new ChunkList<>(); + final ChunkList<Integer> list0 = new ChunkList<>(list); + final ChunkList<Integer> list1 = new ChunkList<>(list); + list1.add(123); assertEquals(0, list.size()); + assertEquals(0, list0.size()); + assertEquals(1, list1.size()); assertTrue(list.isEmpty()); assertEquals("[]", list.toString()); @@ -56,6 +65,20 @@ public class ChunkListTest { // ok } + try { + list.get(-1); + fail("expected exception"); + } catch (IndexOutOfBoundsException e) { + // ok + } + + try { + list.get(0); + fail("expected exception"); + } catch (IndexOutOfBoundsException e) { + // ok + } + list.add(7); assertEquals(1, list.size()); assertEquals(7, (int) list.get(0)); @@ -76,9 +99,10 @@ public class ChunkListTest { assertTrue(list.contains(9)); assertFalse(list.contains(8)); - list.addAll(Collections.nCopies(40, 1)); - assertEquals(44, list.size()); + list.addAll(Collections.nCopies(70, 1)); + assertEquals(74, list.size()); assertEquals(1, (int) list.get(40)); + assertEquals(1, (int) list.get(70)); int n = 0; for (Integer integer : list) { @@ -96,44 +120,142 @@ public class ChunkListTest { i = list.indexOf(null); assertEquals(-1, i); + // sort an empty list + Collections.sort(list0); + assertThat(list0.isEmpty(), is(true)); + + // sort a list with 1 element + Collections.sort(list1); + assertThat(list1.size(), is(1)); + Collections.sort(list); + assertEquals(74, list.size()); list.remove((Integer) 7); Collections.sort(list); assertEquals(1, (int) list.get(3)); // remove all instances of a value that exists - boolean b = list.removeAll(Arrays.asList(9)); + boolean b = list.removeAll(Collections.singletonList(9)); assertTrue(b); // remove all instances of a non-existent value - b = list.removeAll(Arrays.asList(99)); + b = list.removeAll(Collections.singletonList(99)); assertFalse(b); // remove all instances of a value that occurs in the last chunk list.add(12345); - b = list.removeAll(Arrays.asList(12345)); + b = list.removeAll(Collections.singletonList(12345)); assertTrue(b); // remove all instances of a value that occurs in the last chunk but // not as the last value list.add(12345); list.add(123); - b = list.removeAll(Arrays.asList(12345)); + b = list.removeAll(Collections.singletonList(12345)); assertTrue(b); - assertEquals( - 1000, new ChunkList<Integer>(Collections.nCopies(1000, 77)).size()); + assertThat(new ChunkList<>(Collections.nCopies(1000, 77)).size(), + is(1000)); // add to an empty list via iterator //noinspection MismatchedQueryAndUpdateOfCollection - final ChunkList<String> list2 = new ChunkList<String>(); + final ChunkList<String> list2 = new ChunkList<>(); list2.listIterator(0).add("x"); assertEquals("[x]", list2.toString()); // add at start list2.add(0, "y"); assertEquals("[y, x]", list2.toString()); + + list2.remove(0); + assertEquals("[x]", list2.toString()); + + // clear a list of length 5, one element at a time, using an iterator + list2.clear(); + list2.addAll(ImmutableList.of("a", "b", "c", "d", "e")); + assertThat(list2.size(), is(5)); + final ListIterator<String> listIterator = list2.listIterator(0); + assertThat(listIterator.next(), is("a")); + listIterator.remove(); + assertThat(listIterator.next(), is("b")); + listIterator.remove(); + assertThat(listIterator.next(), is("c")); + listIterator.remove(); + assertThat(listIterator.next(), is("d")); + listIterator.remove(); + assertThat(list2.size(), is(1)); + assertThat(listIterator.next(), is("e")); + listIterator.remove(); + assertThat(list2.size(), is(0)); + } + + /** Clears lists of various sizes. */ + @Test public void testClear() { + checkListClear(0); + checkListClear(1); + checkListClear(2); + checkListClear(32); + checkListClear(64); + checkListClear(65); + checkListClear(66); + checkListClear(100); + checkListClear(127); + checkListClear(128); + checkListClear(129); + } + + private void checkListClear(int n) { + for (int i = 0; i < 4; i++) { + ChunkList<String> list = new ChunkList<>(Collections.nCopies(n, "z")); + assertThat(list.size(), is(n)); + switch (i) { + case 0: + list.clear(); + break; + case 1: + for (int j = 0; j < n; j++) { + list.remove(0); + } + break; + case 2: + for (int j = 0; j < n; j++) { + list.remove(list.size() - 1); + } + break; + case 3: + Random random = new Random(); + for (int j = 0; j < n; j++) { + list.remove(random.nextInt(list.size())); + } + break; + } + assertThat(list.isEmpty(), is(true)); + } + } + + /** + * Removing via an iterator. + */ + @Test public void testIterator() { + final ChunkList<String> list = new ChunkList<>(); + list.add("a"); + list.add("b"); + final ListIterator<String> listIterator = list.listIterator(0); + try { + listIterator.remove(); + fail("excepted exception"); + } catch (IllegalStateException e) { + // ok + } + listIterator.next(); + listIterator.remove(); + assertThat(list.size(), is(1)); + assertThat(listIterator.hasNext(), is(true)); + listIterator.next(); + listIterator.remove(); + assertThat(list.size(), is(0)); + assertThat(listIterator.hasNext(), is(false)); } /** @@ -142,41 +264,52 @@ public class ChunkListTest { */ @Test public void testRandom() { final int iterationCount = 10000; - checkRandom(new Random(1), new ChunkList<Integer>(), iterationCount); + checkRandom(new Random(1), new ChunkList<Integer>(), + new ArrayList<Integer>(), iterationCount); final Random random = new Random(2); for (int j = 0; j < 10; j++) { - checkRandom(random, new ChunkList<Integer>(), iterationCount); + checkRandom(random, new ChunkList<Integer>(), new ArrayList<Integer>(), + iterationCount); } - checkRandom( - new Random(3), new ChunkList<Integer>(Collections.nCopies(1000, 5)), - iterationCount); + final ChunkList<Integer> chunkList = + new ChunkList<>(Collections.nCopies(1000, 5)); + final List<Integer> referenceList = new ArrayList<>(chunkList); + checkRandom(new Random(3), chunkList, referenceList, iterationCount); } void checkRandom( Random random, ChunkList<Integer> list, + List<Integer> list2, int iterationCount) { int removeCount = 0; int addCount = 0; + int size; + int e; final int initialCount = list.size(); for (int i = 0; i < iterationCount; i++) { assert list.isValid(true); - switch (random.nextInt(8)) { + switch (random.nextInt(10)) { case 0: // remove last if (!list.isEmpty()) { + assertThat(list2.isEmpty(), is(false)); list.remove(list.size() - 1); + list2.remove(list2.size() - 1); ++removeCount; } break; case 1: // add to end - list.add(random.nextInt(1000)); + e = random.nextInt(1000); + list.add(e); + list2.add(e); ++addCount; break; case 2: int n = 0; - final int size = list.size(); + size = list.size(); + assertThat(list.size(), is(list2.size())); for (Integer integer : list) { Util.discard(integer); assertTrue(n++ < size); @@ -184,20 +317,26 @@ public class ChunkListTest { break; case 3: // remove all instances of a particular value - int sizeBefore = list.size(); - boolean b = list.removeAll( - Collections.singletonList(random.nextInt(500))); + size = list.size(); + final List<Integer> zz = Collections.singletonList(random.nextInt(500)); + boolean b = list.removeAll(zz); + boolean b2 = list2.removeAll(zz); + assertThat(b, is(b2)); if (b) { - assertTrue(list.size() < sizeBefore); + assertTrue(list.size() < size); + assertTrue(list2.size() < size); } else { - assertTrue(list.size() == sizeBefore); + assertTrue(list.size() == size); + assertTrue(list2.size() == size); } - removeCount += sizeBefore - list.size(); + removeCount += size - list.size(); break; case 4: // remove at random position if (!list.isEmpty()) { - list.remove(random.nextInt(list.size())); + e = random.nextInt(list.size()); + list.remove(e); + list2.remove(e); ++removeCount; } break; @@ -205,19 +344,35 @@ public class ChunkListTest { // add at random position int count = random.nextInt(list.size() + 1); ListIterator<Integer> it = list.listIterator(); + ListIterator<Integer> it2 = list2.listIterator(); for (int j = 0; j < count; j++) { it.next(); + it2.next(); } - it.add(list.size()); + size = list.size(); + it.add(size); + it2.add(size); ++addCount; break; + case 6: + // clear + if (random.nextInt(200) == 0) { + removeCount += list.size(); + list.clear(); + list2.clear(); + } + break; default: // add at random position - list.add(random.nextInt(list.size() + 1), list.size()); + int pos = random.nextInt(list.size() + 1); + e = list.size(); + list.add(pos, e); + list2.add(pos, e); ++addCount; break; } assertEquals(list.size(), initialCount + addCount - removeCount); + assertEquals(list, list2); } } @@ -231,22 +386,22 @@ public class ChunkListTest { Arrays.asList( new Function0<List<Integer>>() { public List<Integer> apply() { - return new ArrayList<Integer>(); + return new ArrayList<>(); } }, new Function0<List<Integer>>() { public List<Integer> apply() { - return new LinkedList<Integer>(); + return new LinkedList<>(); } }, new Function0<List<Integer>>() { public List<Integer> apply() { - return new ChunkList<Integer>(); + return new ChunkList<>(); } }), Arrays.asList("ArrayList", "LinkedList", "ChunkList-64")); final List<Pair<Function0<List<Integer>>, String>> factories1 = - new ArrayList<Pair<Function0<List<Integer>>, String>>(); + new ArrayList<>(); for (Pair<Function0<List<Integer>>, String> pair : factories0) { factories1.add(pair); }
