summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/java/android/util/ArrayMap.java114
-rw-r--r--core/tests/coretests/src/android/util/ArrayMapTest.java108
2 files changed, 192 insertions, 30 deletions
diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
index 92a5803b5ddb..d51a13f3d119 100644
--- a/core/java/android/util/ArrayMap.java
+++ b/core/java/android/util/ArrayMap.java
@@ -19,6 +19,7 @@ package android.util;
import libcore.util.EmptyArray;
import java.util.Collection;
+import java.util.ConcurrentModificationException;
import java.util.Map;
import java.util.Set;
@@ -49,6 +50,18 @@ public final class ArrayMap<K, V> implements Map<K, V> {
private static final String TAG = "ArrayMap";
/**
+ * Attempt to spot concurrent modifications to this data structure.
+ *
+ * It's best-effort, but any time we can throw something more diagnostic than an
+ * ArrayIndexOutOfBoundsException deep in the ArrayMap internals it's going to
+ * save a lot of development time.
+ *
+ * Good times to look for CME include after any allocArrays() call and at the end of
+ * functions that change mSize (put/remove/clear).
+ */
+ private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
+
+ /**
* The minimum amount by which the capacity of a ArrayMap will increase.
* This is tuned to be relatively space-efficient.
*/
@@ -86,6 +99,18 @@ public final class ArrayMap<K, V> implements Map<K, V> {
int mSize;
MapCollections<K, V> mCollections;
+ private static int binarySearchHashes(int[] hashes, int N, int hash) {
+ try {
+ return ContainerHelpers.binarySearch(hashes, N, hash);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
+ throw new ConcurrentModificationException();
+ } else {
+ throw e; // the cache is poisoned at this point, there's not much we can do
+ }
+ }
+ }
+
int indexOf(Object key, int hash) {
final int N = mSize;
@@ -94,7 +119,7 @@ public final class ArrayMap<K, V> implements Map<K, V> {
return ~0;
}
- int index = ContainerHelpers.binarySearch(mHashes, N, hash);
+ int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
@@ -132,7 +157,7 @@ public final class ArrayMap<K, V> implements Map<K, V> {
return ~0;
}
- int index = ContainerHelpers.binarySearch(mHashes, N, 0);
+ int index = binarySearchHashes(mHashes, N, 0);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
@@ -282,10 +307,16 @@ public final class ArrayMap<K, V> implements Map<K, V> {
@Override
public void clear() {
if (mSize > 0) {
- freeArrays(mHashes, mArray, mSize);
+ final int[] ohashes = mHashes;
+ final Object[] oarray = mArray;
+ final int osize = mSize;
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
mSize = 0;
+ freeArrays(ohashes, oarray, osize);
+ }
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
+ throw new ConcurrentModificationException();
}
}
@@ -309,15 +340,19 @@ public final class ArrayMap<K, V> implements Map<K, V> {
* items.
*/
public void ensureCapacity(int minimumCapacity) {
+ final int osize = mSize;
if (mHashes.length < minimumCapacity) {
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(minimumCapacity);
if (mSize > 0) {
- System.arraycopy(ohashes, 0, mHashes, 0, mSize);
- System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
+ System.arraycopy(ohashes, 0, mHashes, 0, osize);
+ System.arraycopy(oarray, 0, mArray, 0, osize<<1);
}
- freeArrays(ohashes, oarray, mSize);
+ freeArrays(ohashes, oarray, osize);
+ }
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) {
+ throw new ConcurrentModificationException();
}
}
@@ -435,6 +470,7 @@ public final class ArrayMap<K, V> implements Map<K, V> {
*/
@Override
public V put(K key, V value) {
+ final int osize = mSize;
final int hash;
int index;
if (key == null) {
@@ -452,9 +488,9 @@ public final class ArrayMap<K, V> implements Map<K, V> {
}
index = ~index;
- if (mSize >= mHashes.length) {
- final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
- : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
+ if (osize >= mHashes.length) {
+ final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
+ : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
@@ -462,22 +498,31 @@ public final class ArrayMap<K, V> implements Map<K, V> {
final Object[] oarray = mArray;
allocArrays(n);
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
+ throw new ConcurrentModificationException();
+ }
+
if (mHashes.length > 0) {
- if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
+ if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
- freeArrays(ohashes, oarray, mSize);
+ freeArrays(ohashes, oarray, osize);
}
- if (index < mSize) {
- if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
+ if (index < osize) {
+ if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
+ " to " + (index+1));
- System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
+ System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
+ if (osize != mSize || index >= mHashes.length) {
+ throw new ConcurrentModificationException();
+ }
+ }
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
@@ -594,19 +639,22 @@ public final class ArrayMap<K, V> implements Map<K, V> {
*/
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
- if (mSize <= 1) {
+ final int osize = mSize;
+ final int nsize;
+ if (osize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
- freeArrays(mHashes, mArray, mSize);
+ freeArrays(mHashes, mArray, osize);
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
- mSize = 0;
+ nsize = 0;
} else {
+ nsize = osize - 1;
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);
+ final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
@@ -614,32 +662,38 @@ public final class ArrayMap<K, V> implements Map<K, V> {
final Object[] oarray = mArray;
allocArrays(n);
- mSize--;
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
+ throw new ConcurrentModificationException();
+ }
+
if (index > 0) {
if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
- if (index < mSize) {
- if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
+ if (index < nsize) {
+ if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize
+ " to " + index);
- System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
+ System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
- (mSize - index) << 1);
+ (nsize - index) << 1);
}
} else {
- mSize--;
- if (index < mSize) {
- if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
+ if (index < nsize) {
+ if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize
+ " to " + index);
- System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
+ System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
- (mSize - index) << 1);
+ (nsize - index) << 1);
}
- mArray[mSize << 1] = null;
- mArray[(mSize << 1) + 1] = null;
+ mArray[nsize << 1] = null;
+ mArray[(nsize << 1) + 1] = null;
}
}
+ if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
+ throw new ConcurrentModificationException();
+ }
+ mSize = nsize;
return (V)old;
}
diff --git a/core/tests/coretests/src/android/util/ArrayMapTest.java b/core/tests/coretests/src/android/util/ArrayMapTest.java
new file mode 100644
index 000000000000..32aa29fa3339
--- /dev/null
+++ b/core/tests/coretests/src/android/util/ArrayMapTest.java
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2017 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.util.ArrayMap;
+
+import junit.framework.TestCase;
+import org.junit.Test;
+
+import java.util.ConcurrentModificationException;
+
+/**
+ * Unit tests for ArrayMap that don't belong in CTS.
+ */
+public class ArrayMapTest extends TestCase {
+ private static final String TAG = "ArrayMapTest";
+ ArrayMap<String, String> map = new ArrayMap<>();
+
+ /**
+ * Attempt to generate a ConcurrentModificationException in ArrayMap.
+ * <p>
+ * ArrayMap is explicitly documented to be non-thread-safe, yet it's easy to accidentally screw
+ * this up; ArrayMap should (in the spirit of the core Java collection types) make an effort to
+ * catch this and throw ConcurrentModificationException instead of crashing somewhere in its
+ * internals.
+ *
+ * @throws Exception
+ */
+ @Test
+ public void testConcurrentModificationException() throws Exception {
+ final int TEST_LEN_MS = 5000;
+ System.out.println("Starting ArrayMap concurrency test");
+ new Thread(() -> {
+ int i = 0;
+ while (map != null) {
+ try {
+ map.put(String.format("key %d", i++), "B_DONT_DO_THAT");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ Log.e(TAG, "concurrent modification uncaught, causing indexing failure", e);
+ fail();
+ } catch (ClassCastException e) {
+ Log.e(TAG, "concurrent modification uncaught, causing cache corruption", e);
+ fail();
+ } catch (ConcurrentModificationException e) {
+ System.out.println("[successfully caught CME at put #" + i
+ + " size=" + (map == null ? "??" : String.valueOf(map.size())) + "]");
+ }
+ if (i % 200 == 0) {
+ System.out.print(".");
+ }
+ }
+ }).start();
+ for (int i = 0; i < (TEST_LEN_MS / 100); i++) {
+ try {
+ Thread.sleep(100);
+ map.clear();
+ System.out.print("X");
+ } catch (InterruptedException e) {
+ } catch (ArrayIndexOutOfBoundsException e) {
+ Log.e(TAG, "concurrent modification uncaught, causing indexing failure");
+ fail();
+ } catch (ClassCastException e) {
+ Log.e(TAG, "concurrent modification uncaught, causing cache corruption");
+ fail();
+ } catch (ConcurrentModificationException e) {
+ System.out.println(
+ "[successfully caught CME at clear #"
+ + i + " size=" + map.size() + "]");
+ }
+ }
+ map = null; // will stop other thread
+ System.out.println();
+ }
+
+ /**
+ * Check to make sure the same operations behave as expected in a single thread.
+ */
+ @Test
+ public void testNonConcurrentAccesses() throws Exception {
+ for (int i = 0; i < 100000; i++) {
+ try {
+ map.put(String.format("key %d", i++), "B_DONT_DO_THAT");
+ if (i % 200 == 0) {
+ System.out.print(".");
+ }
+ if (i % 500 == 0) {
+ map.clear();
+ System.out.print("X");
+ }
+ } catch (ConcurrentModificationException e) {
+ Log.e(TAG, "concurrent modification caught on single thread", e);
+ fail();
+ }
+ }
+ }
+}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-16 02:11:47 +0000