You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-commits@hadoop.apache.org by cm...@apache.org on 2014/12/18 20:05:23 UTC
hadoop git commit: HADOOP-11427. ChunkedArrayList: fix removal via
iterator and implement get (cmccabe)
Repository: hadoop
Updated Branches:
refs/heads/trunk abb2ebbc3 -> 07619aa51
HADOOP-11427. ChunkedArrayList: fix removal via iterator and implement get (cmccabe)
Project: http://git-wip-us.apache.org/repos/asf/hadoop/repo
Commit: http://git-wip-us.apache.org/repos/asf/hadoop/commit/07619aa5
Tree: http://git-wip-us.apache.org/repos/asf/hadoop/tree/07619aa5
Diff: http://git-wip-us.apache.org/repos/asf/hadoop/diff/07619aa5
Branch: refs/heads/trunk
Commit: 07619aa516deb9094a18e0c64ce66ff9c8b05e92
Parents: abb2ebb
Author: Colin Patrick Mccabe <cm...@cloudera.com>
Authored: Thu Dec 18 11:05:06 2014 -0800
Committer: Colin Patrick Mccabe <cm...@cloudera.com>
Committed: Thu Dec 18 11:05:06 2014 -0800
----------------------------------------------------------------------
hadoop-common-project/hadoop-common/CHANGES.txt | 3 +
.../apache/hadoop/util/ChunkedArrayList.java | 42 ++++++++++-
.../hadoop/util/TestChunkedArrayList.java | 78 ++++++++++++++++++++
3 files changed, 119 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hadoop/blob/07619aa5/hadoop-common-project/hadoop-common/CHANGES.txt
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/CHANGES.txt b/hadoop-common-project/hadoop-common/CHANGES.txt
index 2378b5b..167bf38 100644
--- a/hadoop-common-project/hadoop-common/CHANGES.txt
+++ b/hadoop-common-project/hadoop-common/CHANGES.txt
@@ -429,6 +429,9 @@ Release 2.7.0 - UNRELEASED
HADOOP-11421. Add IOUtils#listDirectory (cmccabe)
+ HADOOP-11427. ChunkedArrayList: fix removal via iterator and implement get
+ (cmccabe)
+
OPTIMIZATIONS
HADOOP-11323. WritableComparator#compare keeps reference to byte array.
http://git-wip-us.apache.org/repos/asf/hadoop/blob/07619aa5/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/ChunkedArrayList.java
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/ChunkedArrayList.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/ChunkedArrayList.java
index 42cd324..84ddc32 100644
--- a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/ChunkedArrayList.java
+++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/ChunkedArrayList.java
@@ -110,11 +110,33 @@ public class ChunkedArrayList<T> extends AbstractList<T> {
@Override
public Iterator<T> iterator() {
- return Iterables.concat(chunks).iterator();
+ final Iterator<T> it = Iterables.concat(chunks).iterator();
+
+ return new Iterator<T>() {
+ @Override
+ public boolean hasNext() {
+ return it.hasNext();
+ }
+
+ @Override
+ public T next() {
+ return it.next();
+ }
+
+ @Override
+ public void remove() {
+ it.remove();
+ size--;
+ }
+ };
}
@Override
public boolean add(T e) {
+ if (size == Integer.MAX_VALUE) {
+ throw new RuntimeException("Can't add an additional element to the " +
+ "list; list already has INT_MAX elements.");
+ }
if (lastChunk == null) {
addChunk(initialChunkCapacity);
} else if (lastChunk.size() >= lastChunkCapacity) {
@@ -164,8 +186,20 @@ public class ChunkedArrayList<T> extends AbstractList<T> {
}
@Override
- public T get(int arg0) {
- throw new UnsupportedOperationException(
- this.getClass().getName() + " does not support random access");
+ public T get(int idx) {
+ if (idx < 0) {
+ throw new IndexOutOfBoundsException();
+ }
+ int base = 0;
+ Iterator<List<T>> it = chunks.iterator();
+ while (it.hasNext()) {
+ List<T> list = it.next();
+ int size = list.size();
+ if (idx < base + size) {
+ return list.get(idx - base);
+ }
+ base += size;
+ }
+ throw new IndexOutOfBoundsException();
}
}
http://git-wip-us.apache.org/repos/asf/hadoop/blob/07619aa5/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/TestChunkedArrayList.java
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/TestChunkedArrayList.java b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/TestChunkedArrayList.java
index ad17094..f8a2d49 100644
--- a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/TestChunkedArrayList.java
+++ b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/util/TestChunkedArrayList.java
@@ -20,7 +20,9 @@ package org.apache.hadoop.util;
import static org.junit.Assert.*;
import java.util.ArrayList;
+import java.util.Iterator;
+import org.junit.Assert;
import org.junit.Test;
import com.google.common.base.Stopwatch;
@@ -90,4 +92,80 @@ public class TestChunkedArrayList {
}
}
}
+
+ @Test
+ public void testRemovals() throws Exception {
+ final int NUM_ELEMS = 100000;
+ ChunkedArrayList<Integer> list = new ChunkedArrayList<Integer>();
+ for (int i = 0; i < NUM_ELEMS; i++) {
+ list.add(i);
+ }
+
+ // Iterate through all list elements.
+ Iterator<Integer> iter = list.iterator();
+ for (int i = 0; i < NUM_ELEMS; i++) {
+ Assert.assertTrue(iter.hasNext());
+ Integer val = iter.next();
+ Assert.assertEquals(Integer.valueOf(i), val);
+ }
+ Assert.assertFalse(iter.hasNext());
+ Assert.assertEquals(NUM_ELEMS, list.size());
+
+ // Remove even elements.
+ iter = list.iterator();
+ for (int i = 0; i < NUM_ELEMS; i++) {
+ Assert.assertTrue(iter.hasNext());
+ Integer val = iter.next();
+ Assert.assertEquals(Integer.valueOf(i), val);
+ if (i % 2 == 0) {
+ iter.remove();
+ }
+ }
+ Assert.assertFalse(iter.hasNext());
+ Assert.assertEquals(NUM_ELEMS / 2, list.size());
+
+ // Iterate through all odd list elements.
+ iter = list.iterator();
+ for (int i = 0; i < NUM_ELEMS / 2; i++) {
+ Assert.assertTrue(iter.hasNext());
+ Integer val = iter.next();
+ Assert.assertEquals(Integer.valueOf(1 + (2 * i)), val);
+ iter.remove();
+ }
+ Assert.assertFalse(iter.hasNext());
+
+ // Check that list is now empty.
+ Assert.assertEquals(0, list.size());
+ Assert.assertTrue(list.isEmpty());
+ iter = list.iterator();
+ Assert.assertFalse(iter.hasNext());
+ }
+
+ @Test
+ public void testGet() throws Exception {
+ final int NUM_ELEMS = 100001;
+ ChunkedArrayList<Integer> list = new ChunkedArrayList<Integer>();
+ for (int i = 0; i < NUM_ELEMS; i++) {
+ list.add(i);
+ }
+
+ Assert.assertEquals(Integer.valueOf(100), list.get(100));
+ Assert.assertEquals(Integer.valueOf(1000), list.get(1000));
+ Assert.assertEquals(Integer.valueOf(10000), list.get(10000));
+ Assert.assertEquals(Integer.valueOf(100000), list.get(100000));
+
+ Iterator<Integer> iter = list.iterator();
+ iter.next();
+ iter.remove();
+ Assert.assertEquals(Integer.valueOf(1), list.get(0));
+
+ iter = list.iterator();
+ for (int i = 0; i < 500; i++) {
+ iter.next();
+ }
+ iter.remove();
+
+ Assert.assertEquals(Integer.valueOf(502), list.get(500));
+ Assert.assertEquals(Integer.valueOf(602), list.get(600));
+ }
}