Merge "Slight improvements to ArraySet."

3 files changed, 319 insertions, 10 deletions

diff --git a/apct-tests/perftests/core/src/android/util/ArraySetPerfTest.java b/apct-tests/perftests/core/src/android/util/ArraySetPerfTest.java
new file mode 100644
index 000000000000..0c1f2899690d
--- /dev/null
+++ b/apct-tests/perftests/core/src/android/util/ArraySetPerfTest.java
@@ -0,0 +1,212 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.util;
+
+import android.perftests.utils.BenchmarkState;
+import android.perftests.utils.PerfStatusReporter;
+import android.support.test.filters.LargeTest;
+import android.support.test.runner.AndroidJUnit4;
+
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.util.function.Predicate;
+
+@RunWith(AndroidJUnit4.class)
+@LargeTest
+public class ArraySetPerfTest {
+    private static final int NUM_ITERATIONS = 100;
+    private static final int SET_SIZE_SMALL = 10;
+    private static final int SET_SIZE_LARGE = 50;
+
+    @Rule
+    public PerfStatusReporter mPerfStatusReporter = new PerfStatusReporter();
+
+    @Test
+    public void testValueAt_InBounds() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        ArraySet<Integer> set = new ArraySet<>();
+        set.add(0);
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                set.valueAt(0);
+            }
+        }
+    }
+
+    @Test
+    public void testValueAt_OutOfBounds_Negative() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        ArraySet<Integer> set = new ArraySet<>();
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                try {
+                    set.valueAt(-1);
+                } catch (ArrayIndexOutOfBoundsException expected) {
+                    // expected
+                }
+            }
+        }
+    }
+
+    /**
+     * Tests the case where ArraySet could index into its array even though the index is out of
+     * bounds.
+     */
+    @Test
+    public void testValueAt_OutOfBounds_EdgeCase() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        ArraySet<Integer> set = new ArraySet<>();
+        set.add(0);
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                try {
+                    set.valueAt(1);
+                } catch (ArrayIndexOutOfBoundsException expected) {
+                    // expected
+                }
+            }
+        }
+    }
+
+    /**
+     * This is the same code as testRemoveIf_Small_* without the removeIf in order to measure
+     * the performance of the rest of the code in the loop.
+     */
+    @Test
+    public void testRemoveIf_Small_Base() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> i % 2 == 0;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_SMALL; ++j) {
+                    set.add(j);
+                }
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf_Small_RemoveNothing() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> false;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_SMALL; ++j) {
+                    set.add(j);
+                }
+                set.removeIf(predicate);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf_Small_RemoveAll() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> true;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_SMALL; j++) {
+                    set.add(j);
+                }
+                set.removeIf(predicate);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf_Small_RemoveHalf() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> i % 2 == 0;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_SMALL; ++j) {
+                    set.add(j);
+                }
+                set.removeIf(predicate);
+            }
+        }
+    }
+
+    /**
+     * This is the same code as testRemoveIf_Large_* without the removeIf in order to measure
+     * the performance of the rest of the code in the loop.
+     */
+    @Test
+    public void testRemoveIf_Large_Base() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> i % 2 == 0;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+                    set.add(j);
+                }
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf_Large_RemoveNothing() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> false;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+                    set.add(j);
+                }
+                set.removeIf(predicate);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf_Large_RemoveAll() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> true;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+                    set.add(j);
+                }
+                set.removeIf(predicate);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveIf_Large_RemoveHalf() {
+        BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+        Predicate<Integer> predicate = (i) -> i % 2 == 0;
+        while (state.keepRunning()) {
+            for (int i = 0; i < NUM_ITERATIONS; ++i) {
+                ArraySet<Integer> set = new ArraySet<>();
+                for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+                    set.add(j);
+                }
+                set.removeIf(predicate);
+            }
+        }
+    }
+}
diff --git a/api/test-current.txt b/api/test-current.txt
index b59eaccf7823..b393d205679f 100644
--- a/api/test-current.txt
+++ b/api/test-current.txt
@@ -1323,6 +1323,14 @@ package android.transition {
 
 }
 
+package android.util {
+
+  public final class ArraySet<E> implements java.util.Collection java.util.Set {
+    method public E valueAtUnchecked(int);
+  }
+
+}
+
 package android.util.proto {
 
   public final class EncodedBuffer {
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index d74a0fe8d2c1..4bd43d05ae61 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -16,14 +16,17 @@
 
 package android.util;
 
+import android.annotation.TestApi;
+import android.annotation.UnsupportedAppUsage;
+
 import libcore.util.EmptyArray;
 
-import android.annotation.UnsupportedAppUsage;
 import java.lang.reflect.Array;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.function.Predicate;
 
 /**
  * ArraySet is a generic set data structure that is designed to be more memory efficient than a
@@ -357,6 +360,22 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
      * @return Returns the value stored at the given index.
      */
     public E valueAt(int index) {
+        if (index >= mSize) {
+            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
+            throw new ArrayIndexOutOfBoundsException(index);
+        }
+        return valueAtUnchecked(index);
+    }
+
+    /**
+     * Returns the value at the given index in the array without checking that the index is within
+     * bounds. This allows testing values at the end of the internal array, outside of the
+     * [0, mSize) bounds.
+     *
+     * @hide
+     */
+    @TestApi
+    public E valueAtUnchecked(int index) {
         return (E) mArray[index];
     }
 
@@ -491,26 +510,40 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
         return false;
     }
 
+    /** Returns true if the array size should be decreased. */
+    private boolean shouldShrink() {
+        return mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3;
+    }
+
+    /**
+     * Returns the new size the array should have. Is only valid if {@link #shouldShrink} returns
+     * true.
+     */
+    private int getNewShrunkenSize() {
+        // We don't allow it to shrink smaller than (BASE_SIZE*2) to avoid flapping between that
+        // and BASE_SIZE.
+        return mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);
+    }
+
     /**
      * Remove the key/value mapping at the given index.
      * @param index The desired index, must be between 0 and {@link #size()}-1.
      * @return Returns the value that was stored at this index.
      */
     public E removeAt(int index) {
+        if (index >= mSize) {
+            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
+            throw new ArrayIndexOutOfBoundsException(index);
+        }
         final Object old = mArray[index];
         if (mSize <= 1) {
             // Now empty.
             if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
-            freeArrays(mHashes, mArray, mSize);
-            mHashes = EmptyArray.INT;
-            mArray = EmptyArray.OBJECT;
-            mSize = 0;
+            clear();
         } else {
-            if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3) {
-                // Shrunk enough to reduce size of arrays.  We don't allow it to
-                // shrink smaller than (BASE_SIZE*2) to avoid flapping between
-                // that and BASE_SIZE.
-                final int n = mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);
+            if (shouldShrink()) {
+                // Shrunk enough to reduce size of arrays.
+                final int n = getNewShrunkenSize();
 
                 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
 
@@ -568,6 +601,62 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
     }
 
     /**
+     * Removes all values that satisfy the predicate. This implementation avoids using the
+     * {@link #iterator()}.
+     *
+     * @param filter A predicate which returns true for elements to be removed
+     */
+    @Override
+    public boolean removeIf(Predicate<? super E> filter) {
+        if (mSize == 0) {
+            return false;
+        }
+
+        // Intentionally not using removeAt() to avoid unnecessary intermediate resizing.
+
+        int replaceIndex = 0;
+        int numRemoved = 0;
+        for (int i = 0; i < mSize; ++i) {
+            if (filter.test((E) mArray[i])) {
+                numRemoved++;
+            } else {
+                if (replaceIndex != i) {
+                    mArray[replaceIndex] = mArray[i];
+                    mHashes[replaceIndex] = mHashes[i];
+                }
+                replaceIndex++;
+            }
+        }
+
+        if (numRemoved == 0) {
+            return false;
+        } else if (numRemoved == mSize) {
+            clear();
+            return true;
+        }
+
+        mSize -= numRemoved;
+        if (shouldShrink()) {
+            // Shrunk enough to reduce size of arrays.
+            final int n = getNewShrunkenSize();
+            final int[] ohashes = mHashes;
+            final Object[] oarray = mArray;
+            allocArrays(n);
+
+            System.arraycopy(ohashes, 0, mHashes, 0, mSize);
+            System.arraycopy(oarray, 0, mArray, 0, mSize);
+        } else {
+            // Null out values at the end of the array. Not doing it in the loop above to avoid
+            // writing twice to the same index or writing unnecessarily if the array would have been
+            // discarded anyway.
+            for (int i = mSize; i < mArray.length; ++i) {
+                mArray[i] = null;
+            }
+        }
+        return true;
+    }
+
+    /**
      * Return the number of items in this array map.
      */
     @Override