hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From cmcc...@apache.org
Subject hadoop git commit: HADOOP-11427. ChunkedArrayList: fix removal via iterator and implement get (cmccabe) (cherry picked from commit 07619aa516deb9094a18e0c64ce66ff9c8b05e92)
Date Thu, 18 Dec 2014 19:05:41 GMT
Repository: hadoop
Updated Branches:
  refs/heads/branch-2 8bffaa46f -> 2743b94c2


HADOOP-11427. ChunkedArrayList: fix removal via iterator and implement get (cmccabe)
(cherry picked from commit 07619aa516deb9094a18e0c64ce66ff9c8b05e92)


Project: http://git-wip-us.apache.org/repos/asf/hadoop/repo
Commit: http://git-wip-us.apache.org/repos/asf/hadoop/commit/2743b94c
Tree: http://git-wip-us.apache.org/repos/asf/hadoop/tree/2743b94c
Diff: http://git-wip-us.apache.org/repos/asf/hadoop/diff/2743b94c

Branch: refs/heads/branch-2
Commit: 2743b94c2759397d5151b36a1c814e3fe650aa66
Parents: 8bffaa4
Author: Colin Patrick Mccabe <cmccabe@cloudera.com>
Authored: Thu Dec 18 11:05:06 2014 -0800
Committer: Colin Patrick Mccabe <cmccabe@cloudera.com>
Committed: Thu Dec 18 11:05:33 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/2743b94c/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 5b980d2..627f9b0 100644
--- a/hadoop-common-project/hadoop-common/CHANGES.txt
+++ b/hadoop-common-project/hadoop-common/CHANGES.txt
@@ -76,6 +76,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/2743b94c/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/2743b94c/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));
+  }
 }


Mime
View raw message