diff options
21 files changed, 1758 insertions, 924 deletions
diff --git a/core/java/android/app/LoaderManager.java b/core/java/android/app/LoaderManager.java index 267555a70921..b13b24a1ca0c 100644 --- a/core/java/android/app/LoaderManager.java +++ b/core/java/android/app/LoaderManager.java @@ -204,13 +204,13 @@ class LoaderManagerImpl extends LoaderManager { // These are the currently active loaders. A loader is here // from the time its load is started until it has been explicitly // stopped or restarted by the application. - final SparseArray<LoaderInfo> mLoaders = new SparseArray<LoaderInfo>(); + final SparseArray<LoaderInfo> mLoaders = new SparseArray<LoaderInfo>(0); // These are previously run loaders. This list is maintained internally // to avoid destroying a loader while an application is still using it. // It allows an application to restart a loader, but continue using its // previously run loader until the new loader's data is available. - final SparseArray<LoaderInfo> mInactiveLoaders = new SparseArray<LoaderInfo>(); + final SparseArray<LoaderInfo> mInactiveLoaders = new SparseArray<LoaderInfo>(0); final String mWho; diff --git a/core/java/android/content/pm/RegisteredServicesCache.java b/core/java/android/content/pm/RegisteredServicesCache.java index 288d55f577f6..875e8de2daed 100644 --- a/core/java/android/content/pm/RegisteredServicesCache.java +++ b/core/java/android/content/pm/RegisteredServicesCache.java @@ -82,7 +82,7 @@ public abstract class RegisteredServicesCache<V> { @GuardedBy("mServicesLock") private boolean mPersistentServicesFileDidNotExist; @GuardedBy("mServicesLock") - private final SparseArray<UserServices<V>> mUserServices = new SparseArray<UserServices<V>>(); + private final SparseArray<UserServices<V>> mUserServices = new SparseArray<UserServices<V>>(2); private static class UserServices<V> { @GuardedBy("mServicesLock") diff --git a/core/java/android/content/res/Resources.java b/core/java/android/content/res/Resources.java index c7976c3c6723..cff974d01792 100644 --- a/core/java/android/content/res/Resources.java +++ b/core/java/android/content/res/Resources.java @@ -99,11 +99,11 @@ public class Resources { /*package*/ final Configuration mTmpConfig = new Configuration(); /*package*/ TypedValue mTmpValue = new TypedValue(); /*package*/ final LongSparseArray<WeakReference<Drawable.ConstantState> > mDrawableCache - = new LongSparseArray<WeakReference<Drawable.ConstantState> >(); + = new LongSparseArray<WeakReference<Drawable.ConstantState> >(0); /*package*/ final LongSparseArray<WeakReference<ColorStateList> > mColorStateListCache - = new LongSparseArray<WeakReference<ColorStateList> >(); + = new LongSparseArray<WeakReference<ColorStateList> >(0); /*package*/ final LongSparseArray<WeakReference<Drawable.ConstantState> > mColorDrawableCache - = new LongSparseArray<WeakReference<Drawable.ConstantState> >(); + = new LongSparseArray<WeakReference<Drawable.ConstantState> >(0); /*package*/ boolean mPreloading; /*package*/ TypedArray mCachedStyledAttributes = null; diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java new file mode 100644 index 000000000000..70f7d2edecc9 --- /dev/null +++ b/core/java/android/util/ArrayMap.java @@ -0,0 +1,615 @@ +/* + * Copyright (C) 2013 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 java.util.Collection; +import java.util.Map; +import java.util.Set; + +/** + * ArrayMap is a generic key->value mapping data structure that is + * designed to be more memory efficient than a traditional {@link java.util.HashMap}. + * It keeps its mappings in an array data structure -- an integer array of hash + * codes for each item, and an Object array of the key/value pairs. This allows it to + * avoid having to create an extra object for every entry put in to the map, and it + * also tries to control the growth of the size of these arrays more aggressively + * (since growing them only requires copying the entries in the array, not rebuilding + * a hash map). + * + * <p>Note that this implementation is not intended to be appropriate for data structures + * that may contain large numbers of items. It is generally slower than a traditional + * HashMap, since lookups require a binary search and adds and removes require inserting + * and deleting entries in the array. For containers holding up to hundreds of items, + * the performance difference is not significant, less than 50%. For larger numbers of items + * this data structure should be avoided.</p> + * + * <p><b>Note:</b> unlike {@link java.util.HashMap}, this container does not support + * null keys.</p> + * + * <p>Because this container is intended to better balance memory use, unlike most other + * standard Java containers it will shrink its array as items are removed from it. Currently + * you have no control over this shrinking -- if you set a capacity and then remove an + * item, it may reduce the capacity to better match the current size. In the future an + * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p> + * + * @hide + */ +public final class ArrayMap<K, V> implements Map<K, V> { + private static final boolean DEBUG = false; + private static final String TAG = "ArrayMap"; + + /** + * The minimum amount by which the capacity of a ArrayMap will increase. + * This is tuned to be relatively space-efficient. + */ + private static final int BASE_SIZE = 4; + + /** + * Maximum number of entries to have in array caches. + */ + private static final int CACHE_SIZE = 10; + + /** + * Caches of small array objects to avoid spamming garbage. The cache + * Object[] variable is a pointer to a linked list of array objects. + * The first entry in the array is a pointer to the next array in the + * list; the second entry is a pointer to the int[] hash code array for it. + */ + static Object[] mBaseCache; + static int mBaseCacheSize; + static Object[] mTwiceBaseCache; + static int mTwiceBaseCacheSize; + + int[] mHashes; + Object[] mArray; + int mSize; + MapCollections<K, V> mCollections; + + private int indexOf(Object key, int hash) { + final int N = mSize; + + // Important fast case: if nothing is in here, nothing to look for. + if (N == 0) { + return ~0; + } + + int index = SparseArray.binarySearch(mHashes, N, hash); + + // If the hash code wasn't found, then we have no entry for this key. + if (index < 0) { + return index; + } + + // If the key at the returned index matches, that's what we want. + if (mArray[index<<1].equals(key)) { + return index; + } + + // Search for a matching key after the index. + int end; + for (end = index + 1; end < N && mHashes[end] == hash; end++) { + if (mArray[end << 1].equals(key)) return end; + } + + // Search for a matching key before the index. + for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { + if (mArray[i << 1].equals(key)) return i; + } + + // Key not found -- return negative value indicating where a + // new entry for this key should go. We use the end of the + // hash chain to reduce the number of array entries that will + // need to be copied when inserting. + return ~end; + } + + private void allocArrays(final int size) { + if (size == (BASE_SIZE*2)) { + synchronized (ArrayMap.class) { + if (mTwiceBaseCache != null) { + final Object[] array = mTwiceBaseCache; + mArray = array; + mTwiceBaseCache = (Object[])array[0]; + mHashes = (int[])array[1]; + array[0] = array[1] = null; + mTwiceBaseCacheSize--; + if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes + + " now have " + mTwiceBaseCacheSize + " entries"); + return; + } + } + } else if (size == BASE_SIZE) { + synchronized (ArrayMap.class) { + if (mBaseCache != null) { + final Object[] array = mBaseCache; + mArray = array; + mBaseCache = (Object[])array[0]; + mHashes = (int[])array[1]; + array[0] = array[1] = null; + mBaseCacheSize--; + if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes + + " now have " + mBaseCacheSize + " entries"); + return; + } + } + } + + mHashes = new int[size]; + mArray = new Object[size<<1]; + } + + private static void freeArrays(final int[] hashes, final Object[] array, final int size) { + if (hashes.length == (BASE_SIZE*2)) { + synchronized (ArrayMap.class) { + if (mTwiceBaseCacheSize < CACHE_SIZE) { + array[0] = mTwiceBaseCache; + array[1] = hashes; + for (int i=(size<<1)-1; i>=2; i--) { + array[i] = null; + } + mTwiceBaseCache = array; + mTwiceBaseCacheSize++; + if (DEBUG) Log.d(TAG, "Storing 2x cache " + array + + " now have " + mTwiceBaseCacheSize + " entries"); + } + } + } else if (hashes.length == BASE_SIZE) { + synchronized (ArrayMap.class) { + if (mBaseCacheSize < CACHE_SIZE) { + array[0] = mBaseCache; + array[1] = hashes; + for (int i=(size<<1)-1; i>=2; i--) { + array[i] = null; + } + mBaseCache = array; + mBaseCacheSize++; + if (DEBUG) Log.d(TAG, "Storing 1x cache " + array + + " now have " + mBaseCacheSize + " entries"); + } + } + } + } + + /** + * Create a new empty ArrayMap. The default capacity of an array map is 0, and + * will grow once items are added to it. + */ + public ArrayMap() { + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + mSize = 0; + } + + /** + * Create a new ArrayMap with a given initial capacity. + */ + public ArrayMap(int capacity) { + if (capacity == 0) { + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + } else { + allocArrays(capacity); + } + mSize = 0; + } + + /** + * Make the array map empty. All storage is released. + */ + @Override + public void clear() { + freeArrays(mHashes, mArray, mSize); + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + mSize = 0; + } + + /** + * Ensure the array map can hold at least <var>minimumCapacity</var> + * items. + */ + public void ensureCapacity(int minimumCapacity) { + if (mHashes.length < minimumCapacity) { + int[] ohashes = mHashes; + Object[] oarray = mArray; + allocArrays(minimumCapacity); + if (mHashes.length > 0) { + System.arraycopy(ohashes, 0, mHashes, 0, mHashes.length); + System.arraycopy(oarray, 0, mArray, 0, mArray.length); + } + freeArrays(ohashes, oarray, mSize); + } + } + + /** + * Check whether a key exists in the array. + * + * @param key The key to search for. + * @return Returns true if the key exists, else false. + */ + @Override + public boolean containsKey(Object key) { + return indexOf(key, key.hashCode()) >= 0; + } + + private int indexOfValue(Object value) { + final int N = mSize*2; + final Object[] array = mArray; + if (value == null) { + for (int i=1; i<N; i+=2) { + if (array[i] == null) { + return i>>1; + } + } + } else { + for (int i=1; i<N; i+=2) { + if (value.equals(array[i])) { + return i>>1; + } + } + } + return -1; + } + + /** + * Check whether a value exists in the array. This requires a linear search + * through the entire array. + * + * @param value The value to search for. + * @return Returns true if the value exists, else false. + */ + @Override + public boolean containsValue(Object value) { + return indexOfValue(value) >= 0; + } + + /** + * Retrieve a value from the array. + * @param key The key of the value to retrieve. + * @return Returns the value associated with the given key, + * or null if there is no such key. + */ + @Override + public V get(Object key) { + final int index = indexOf(key, key.hashCode()); + return index >= 0 ? (V)mArray[(index<<1)+1] : null; + } + + /** + * Return the key at the given index in the array. + * @param index The desired index, must be between 0 and {@link #size()}-1. + * @return Returns the key stored at the given index. + */ + public K keyAt(int index) { + return (K)mArray[index << 1]; + } + + /** + * Return the value at the given index in the array. + * @param index The desired index, must be between 0 and {@link #size()}-1. + * @return Returns the value stored at the given index. + */ + public V valueAt(int index) { + return (V)mArray[(index << 1) + 1]; + } + + /** + * Set the value at a given index in the array. + * @param index The desired index, must be between 0 and {@link #size()}-1. + * @param value The new value to store at this index. + * @return Returns the previous value at the given index. + */ + public V setValueAt(int index, V value) { + index = (index << 1) + 1; + V old = (V)mArray[index]; + mArray[index] = value; + return old; + } + + /** + * Return true if the array map contains no items. + */ + @Override + public boolean isEmpty() { + return mSize <= 0; + } + + /** + * Add a new value to the array map. + * @param key The key under which to store the value. <b>Must not be null.</b> If + * this key already exists in the array, its value will be replaced. + * @param value The value to store for the given key. + * @return Returns the old value that was stored for the given key, or null if there + * was no such key. + */ + @Override + public V put(K key, V value) { + final int hash = key.hashCode(); + int index = indexOf(key, hash); + if (index >= 0) { + index = (index<<1) + 1; + final V old = (V)mArray[index]; + mArray[index] = value; + return old; + } + + 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 (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); + + final int[] ohashes = mHashes; + final Object[] oarray = mArray; + allocArrays(n); + + if (mHashes.length > 0) { + if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); + System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); + System.arraycopy(oarray, 0, mArray, 0, oarray.length); + } + + freeArrays(ohashes, oarray, mSize); + } + + if (index < mSize) { + if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) + + " to " + (index+1)); + System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); + System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); + } + + mHashes[index] = hash; + mArray[index<<1] = key; + mArray[(index<<1)+1] = value; + mSize++; + return null; + } + + /** + * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> + * @param array The array whose contents are to be retrieved. + */ + public void putAll(ArrayMap<? extends K, ? extends V> array) { + final int N = array.mSize; + ensureCapacity(mSize + N); + for (int i=0; i<N; i++) { + put(array.keyAt(i), array.valueAt(i)); + } + } + + /** + * Remove an existing key from the array map. + * @param key The key of the mapping to remove. + * @return Returns the value that was stored under the key, or null if there + * was no such key. + */ + @Override + public V remove(Object key) { + int index = indexOf(key, key.hashCode()); + if (index >= 0) { + return removeAt(index); + } + + return null; + } + + /** + * 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 V removeAt(int index) { + final V old = (V)mArray[(index << 1) + 1]; + if (mSize <= 1) { + // Now empty. + if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); + freeArrays(mHashes, mArray, mSize); + mHashes = SparseArray.EMPTY_INTS; + mArray = SparseArray.EMPTY_OBJECTS; + mSize = 0; + } 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 (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); + + final int[] ohashes = mHashes; + final Object[] oarray = mArray; + allocArrays(n); + + mSize--; + 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 + + " to " + index); + System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); + System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, + (mSize - index) << 1); + } + } else { + mSize--; + if (index < mSize) { + if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize + + " to " + index); + System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); + System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, + (mSize - index) << 1); + } + mArray[mSize << 1] = null; + mArray[(mSize << 1) + 1] = null; + } + } + return old; + } + + /** + * Return the number of items in this array map. + */ + @Override + public int size() { + return mSize; + } + + // ------------------------------------------------------------------------ + // Interop with traditional Java containers. Not as efficient as using + // specialized collection APIs. + // ------------------------------------------------------------------------ + + private MapCollections<K, V> getCollection() { + if (mCollections == null) { + mCollections = new MapCollections<K, V>() { + @Override + protected int colGetSize() { + return mSize; + } + + @Override + protected Object colGetEntry(int index, int offset) { + return mArray[(index<<1) + offset]; + } + + @Override + protected int colIndexOfKey(Object key) { + return indexOf(key, key.hashCode()); + } + + @Override + protected int colIndexOfValue(Object value) { + return indexOfValue(value); + } + + @Override + protected Map<K, V> colGetMap() { + return ArrayMap.this; + } + + @Override + protected void colPut(K key, V value) { + put(key, value); + } + + @Override + protected V colSetValue(int index, V value) { + return setValueAt(index, value); + } + + @Override + protected void colRemoveAt(int index) { + removeAt(index); + } + + @Override + protected void colClear() { + clear(); + } + }; + } + return mCollections; + } + + /** + * Determine if the array map contains all of the keys in the given collection. + * @param collection The collection whose contents are to be checked against. + * @return Returns true if this array map contains a key for every entry + * in <var>collection</var>, else returns false. + */ + public boolean containsAll(Collection<?> collection) { + return MapCollections.containsAllHelper(this, collection); + } + + /** + * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> + * @param map The map whose contents are to be retrieved. + */ + @Override + public void putAll(Map<? extends K, ? extends V> map) { + ensureCapacity(mSize + map.size()); + for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { + put(entry.getKey(), entry.getValue()); + } + } + + /** + * Remove all keys in the array map that exist in the given collection. + * @param collection The collection whose contents are to be used to remove keys. + * @return Returns true if any keys were removed from the array map, else false. + */ + public boolean removeAll(Collection<?> collection) { + return MapCollections.removeAllHelper(this, collection); + } + + /** + * Remove all keys in the array map that do <b>not</b> exist in the given collection. + * @param collection The collection whose contents are to be used to determine which + * keys to keep. + * @return Returns true if any keys were removed from the array map, else false. + */ + public boolean retainAll(Collection<?> collection) { + return MapCollections.retainAllHelper(this, collection); + } + + /** + * Return a {@link java.util.Set} for iterating over and interacting with all mappings + * in the array map. + * + * <p><b>Note:</b> this is a very inefficient way to access the array contents, it + * requires generating a number of temporary objects.</p> + * + * <p><b>Note:</b></p> the semantics of this + * Set are subtly different than that of a {@link java.util.HashMap}: most important, + * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single + * object that exists for the entire iterator, so you can <b>not</b> hold on to it + * after calling {@link java.util.Iterator#next() Iterator.next}.</p> + */ + @Override + public Set<Map.Entry<K, V>> entrySet() { + return getCollection().getEntrySet(); + } + + /** + * Return a {@link java.util.Set} for iterating over and interacting with all keys + * in the array map. + * + * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it + * requires generating a number of temporary objects.</p> + */ + @Override + public Set<K> keySet() { + return getCollection().getKeySet(); + } + + /** + * Return a {@link java.util.Collection} for iterating over and interacting with all values + * in the array map. + * + * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it + * requires generating a number of temporary objects.</p> + */ + @Override + public Collection<V> values() { + return getCollection().getValues(); + } +} diff --git a/core/java/android/util/LongSparseArray.java b/core/java/android/util/LongSparseArray.java index 630e5f37d8a0..660b743a14e6 100644 --- a/core/java/android/util/LongSparseArray.java +++ b/core/java/android/util/LongSparseArray.java @@ -41,13 +41,19 @@ public class LongSparseArray<E> implements Cloneable { /** * Creates a new LongSparseArray containing no mappings that will not * require any additional memory allocation to store the specified - * number of mappings. + * number of mappings. If you supply an initial capacity of 0, the + * sparse array will be initialized with a light-weight representation + * not requiring any additional array allocations. */ public LongSparseArray(int initialCapacity) { - initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); - - mKeys = new long[initialCapacity]; - mValues = new Object[initialCapacity]; + if (initialCapacity == 0) { + mKeys = SparseLongArray.EMPTY_LONGS; + mValues = SparseArray.EMPTY_OBJECTS; + } else { + initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); + mKeys = new long[initialCapacity]; + mValues = new Object[initialCapacity]; + } mSize = 0; } diff --git a/core/java/android/util/LongSparseLongArray.java b/core/java/android/util/LongSparseLongArray.java index 34b61264d653..503295c52bea 100644 --- a/core/java/android/util/LongSparseLongArray.java +++ b/core/java/android/util/LongSparseLongArray.java @@ -42,13 +42,19 @@ public class LongSparseLongArray implements Cloneable { /** * Creates a new SparseLongArray containing no mappings that will not * require any additional memory allocation to store the specified - * number of mappings. + * number of mappings. If you supply an initial capacity of 0, the + * sparse array will be initialized with a light-weight representation + * not requiring any additional array allocations. */ public LongSparseLongArray(int initialCapacity) { - initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); - - mKeys = new long[initialCapacity]; - mValues = new long[initialCapacity]; + if (initialCapacity == 0) { + mKeys = SparseLongArray.EMPTY_LONGS; + mValues = SparseLongArray.EMPTY_LONGS; + } else { + initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); + mKeys = new long[initialCapacity]; + mValues = new long[initialCapacity]; + } mSize = 0; } diff --git a/core/java/android/util/MapCollections.java b/core/java/android/util/MapCollections.java new file mode 100644 index 000000000000..f29fb65c6ce4 --- /dev/null +++ b/core/java/android/util/MapCollections.java @@ -0,0 +1,496 @@ +/* + * Copyright (C) 2013 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 libcore.util.Objects; + +import java.lang.reflect.Array; +import java.util.Collection; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; + +/** + * Helper for writing standard Java collection interfaces to a data + * structure like {@link ArrayMap}. + * @hide + */ +abstract class MapCollections<K, V> { + EntrySet mEntrySet; + KeySet mKeySet; + ValuesCollection mValues; + + final class ArrayIterator<T> implements Iterator<T> { + final int mOffset; + int mSize; + int mIndex; + boolean mCanRemove = false; + + ArrayIterator(int offset) { + mOffset = offset; + mSize = colGetSize(); + } + + @Override + public boolean hasNext() { + return mIndex < mSize; + } + + @Override + public T next() { + Object res = colGetEntry(mIndex, mOffset); + mIndex++; + mCanRemove = true; + return (T)res; + } + + @Override + public void remove() { + if (!mCanRemove) { + throw new IllegalStateException(); + } + mIndex--; + mSize--; + mCanRemove = false; + colRemoveAt(mIndex); + } + } + + final class MapIterator implements Iterator<Map.Entry<K, V>>, Map.Entry<K, V> { + int mEnd; + int mIndex; + boolean mEntryValid = false; + + MapIterator() { + mEnd = colGetSize() - 1; + mIndex = -1; + } + + @Override + public boolean hasNext() { + return mIndex < mEnd; + } + + @Override + public Map.Entry<K, V> next() { + mIndex++; + mEntryValid = true; + return this; + } + + @Override + public void remove() { + if (!mEntryValid) { + throw new IllegalStateException(); + } + mIndex--; + mEnd--; + mEntryValid = false; + colRemoveAt(mIndex); + } + + @Override + public K getKey() { + if (!mEntryValid) { + throw new IllegalStateException( + "This container does not support retaining Map.Entry objects"); + } + return (K)colGetEntry(mIndex, 0); + } + + @Override + public V getValue() { + if (!mEntryValid) { + throw new IllegalStateException( + "This container does not support retaining Map.Entry objects"); + } + return (V)colGetEntry(mIndex, 1); + } + + @Override + public V setValue(V object) { + if (!mEntryValid) { + throw new IllegalStateException( + "This container does not support retaining Map.Entry objects"); + } + return colSetValue(mIndex, object); + } + + @Override + public final boolean equals(Object o) { + if (!mEntryValid) { + throw new IllegalStateException( + "This container does not support retaining Map.Entry objects"); + } + if (!(o instanceof Map.Entry)) { + return false; + } + Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; + return Objects.equal(e.getKey(), colGetEntry(mIndex, 0)) + && Objects.equal(e.getValue(), colGetEntry(mIndex, 1)); + } + + @Override + public final int hashCode() { + if (!mEntryValid) { + throw new IllegalStateException( + "This container does not support retaining Map.Entry objects"); + } + final Object key = colGetEntry(mIndex, 0); + final Object value = colGetEntry(mIndex, 1); + return (key == null ? 0 : key.hashCode()) ^ + (value == null ? 0 : value.hashCode()); + } + + @Override + public final String toString() { + return getKey() + "=" + getValue(); + } + } + + final class EntrySet implements Set<Map.Entry<K, V>> { + @Override + public boolean add(Map.Entry<K, V> object) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends Map.Entry<K, V>> collection) { + int oldSize = colGetSize(); + for (Map.Entry<K, V> entry : collection) { + colPut(entry.getKey(), entry.getValue()); + } + return oldSize != colGetSize(); + } + + @Override + public void clear() { + colClear(); + } + + @Override + public boolean contains(Object object) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean containsAll(Collection<?> collection) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean isEmpty() { + return colGetSize() == 0; + } + + @Override + public Iterator<Map.Entry<K, V>> iterator() { + return new MapIterator(); + } + + @Override + public boolean remove(Object object) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean removeAll(Collection<?> collection) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean retainAll(Collection<?> collection) { + throw new UnsupportedOperationException(); + } + + @Override + public int size() { + return colGetSize(); + } + + @Override + public Object[] toArray() { + throw new UnsupportedOperationException(); + } + + @Override + public <T> T[] toArray(T[] array) { + throw new UnsupportedOperationException(); + } + }; + + final class KeySet implements Set<K> { + + @Override + public boolean add(K object) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends K> collection) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + colClear(); + } + + @Override + public boolean contains(Object object) { + return colIndexOfKey(object) >= 0; + } + + @Override + public boolean containsAll(Collection<?> collection) { + return removeAllHelper(colGetMap(), collection); + } + + @Override + public boolean isEmpty() { + return colGetSize() == 0; + } + + @Override + public Iterator<K> iterator() { + return new ArrayIterator<K>(0); + } + + @Override + public boolean remove(Object object) { + int index = colIndexOfKey(object); + if (index >= 0) { + colRemoveAt(index); + return true; + } + return false; + } + + @Override + public boolean removeAll(Collection<?> collection) { + return removeAllHelper(colGetMap(), collection); + } + + @Override + public boolean retainAll(Collection<?> collection) { + return retainAllHelper(colGetMap(), collection); + } + + @Override + public int size() { + return colGetSize(); + } + + @Override + public Object[] toArray() { + return toArrayHelper(1); + } + + @Override + public <T> T[] toArray(T[] array) { + return toArrayHelper(array, 1); + } + }; + + final class ValuesCollection implements Collection<V> { + + @Override + public boolean add(V object) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends V> collection) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + colClear(); + } + + @Override + public boolean contains(Object object) { + return colIndexOfValue(object) >= 0; + } + + @Override + public boolean containsAll(Collection<?> collection) { + Iterator<?> it = collection.iterator(); + while (it.hasNext()) { + if (!contains(it.next())) { + return false; + } + } + return true; + } + + @Override + public boolean isEmpty() { + return colGetSize() == 0; + } + + @Override + public Iterator<V> iterator() { + return new ArrayIterator<V>(1); + } + + @Override + public boolean remove(Object object) { + int index = colIndexOfValue(object); + if (index >= 0) { + colRemoveAt(index); + return true; + } + return false; + } + + @Override + public boolean removeAll(Collection<?> collection) { + int N = colGetSize(); + boolean changed = false; + for (int i=0; i<N; i++) { + Object cur = colGetEntry(i, 1); + if (collection.contains(cur)) { + colRemoveAt(i); + i--; + N--; + changed = true; + } + } + return changed; + } + + @Override + public boolean retainAll(Collection<?> collection) { + int N = colGetSize(); + boolean changed = false; + for (int i=0; i<N; i++) { + Object cur = colGetEntry(i, 1); + if (!collection.contains(cur)) { + colRemoveAt(i); + i--; + N--; + changed = true; + } + } + return changed; + } + + @Override + public int size() { + return colGetSize(); + } + + @Override + public Object[] toArray() { + return toArrayHelper(1); + } + + @Override + public <T> T[] toArray(T[] array) { + return toArrayHelper(array, 1); + } + }; + + public static <K, V> boolean containsAllHelper(Map<K, V> map, Collection<?> collection) { + Iterator<?> it = collection.iterator(); + while (it.hasNext()) { + if (!map.containsKey(it.next())) { + return false; + } + } + return true; + } + + public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) { + int oldSize = map.size(); + Iterator<?> it = collection.iterator(); + while (it.hasNext()) { + map.remove(it.next()); + } + return oldSize != map.size(); + } + + public static <K, V> boolean retainAllHelper(Map<K, V> map, Collection<?> collection) { + int oldSize = map.size(); + Iterator<K> it = map.keySet().iterator(); + while (it.hasNext()) { + if (!collection.contains(it.next())) { + it.remove(); + } + } + return oldSize != map.size(); + } + + + public Object[] toArrayHelper(int offset) { + final int N = colGetSize(); + Object[] result = new Object[N]; + for (int i=0; i<N; i++) { + result[i] = colGetEntry(i, offset); + } + return result; + } + + public <T> T[] toArrayHelper(T[] array, int offset) { + final int N = colGetSize(); + if (array.length < N) { + @SuppressWarnings("unchecked") T[] newArray + = (T[]) Array.newInstance(array.getClass().getComponentType(), N); + array = newArray; + } + for (int i=0; i<N; i++) { + array[i] = (T)colGetEntry(i, offset); + } + if (array.length > N) { + array[N] = null; + } + return array; + } + + public Set<Map.Entry<K, V>> getEntrySet() { + if (mEntrySet == null) { + mEntrySet = new EntrySet(); + } + return mEntrySet; + } + + public Set<K> getKeySet() { + if (mKeySet == null) { + mKeySet = new KeySet(); + } + return mKeySet; + } + + public Collection<V> getValues() { + if (mValues == null) { + mValues = new ValuesCollection(); + } + return mValues; + } + + protected abstract int colGetSize(); + protected abstract Object colGetEntry(int index, int offset); + protected abstract int colIndexOfKey(Object key); + protected abstract int colIndexOfValue(Object key); + protected abstract Map<K, V> colGetMap(); + protected abstract void colPut(K key, V value); + protected abstract V colSetValue(int index, V value); + protected abstract void colRemoveAt(int index); + protected abstract void colClear(); +} diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java index 7e8fee56ea95..001fc5bcbbb6 100644 --- a/core/java/android/util/SparseArray.java +++ b/core/java/android/util/SparseArray.java @@ -25,6 +25,8 @@ import com.android.internal.util.ArrayUtils; */ public class SparseArray<E> implements Cloneable { private static final Object DELETED = new Object(); + static final int[] EMPTY_INTS = new int[0]; + static final Object[] EMPTY_OBJECTS = new Object[0]; private boolean mGarbage = false; private int[] mKeys; @@ -41,13 +43,19 @@ public class SparseArray<E> implements Cloneable { /** * Creates a new SparseArray containing no mappings that will not * require any additional memory allocation to store the specified - * number of mappings. + * number of mappings. If you supply an initial capacity of 0, the + * sparse array will be initialized with a light-weight representation + * not requiring any additional array allocations. */ public SparseArray(int initialCapacity) { - initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); - - mKeys = new int[initialCapacity]; - mValues = new Object[initialCapacity]; + if (initialCapacity == 0) { + mKeys = EMPTY_INTS; + mValues = EMPTY_OBJECTS; + } else { + initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); + mKeys = new int[initialCapacity]; + mValues = new Object[initialCapacity]; + } mSize = 0; } @@ -79,7 +87,7 @@ public class SparseArray<E> implements Cloneable { */ @SuppressWarnings("unchecked") public E get(int key, E valueIfKeyNotFound) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; @@ -92,7 +100,7 @@ public class SparseArray<E> implements Cloneable { * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { @@ -153,7 +161,7 @@ public class SparseArray<E> implements Cloneable { * was one. */ public void put(int key, E value) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; @@ -170,7 +178,7 @@ public class SparseArray<E> implements Cloneable { gc(); // Search again because indices may have changed. - i = ~binarySearch(mKeys, 0, mSize, key); + i = ~binarySearch(mKeys, mSize, key); } if (mSize >= mKeys.length) { @@ -261,7 +269,7 @@ public class SparseArray<E> implements Cloneable { gc(); } - return binarySearch(mKeys, 0, mSize, key); + return binarySearch(mKeys, mSize, key); } /** @@ -335,23 +343,23 @@ public class SparseArray<E> implements Cloneable { mSize = pos + 1; } - private static int binarySearch(int[] a, int start, int len, int key) { - int high = start + len, low = start - 1, guess; - - while (high - low > 1) { - guess = (high + low) / 2; - - if (a[guess] < key) - low = guess; - else - high = guess; + // This is Arrays.binarySearch(), but doesn't do any argument validation. + static int binarySearch(int[] array, int size, int value) { + int lo = 0; + int hi = size - 1; + + while (lo <= hi) { + int mid = (lo + hi) >>> 1; + int midVal = array[mid]; + + if (midVal < value) { + lo = mid + 1; + } else if (midVal > value) { + hi = mid - 1; + } else { + return mid; // value found + } } - - if (high == start + len) - return ~(start + len); - else if (a[high] == key) - return high; - else - return ~high; + return ~lo; // value not present } } diff --git a/core/java/android/util/SparseBooleanArray.java b/core/java/android/util/SparseBooleanArray.java index 76c47c6aabad..73e3629d467d 100644 --- a/core/java/android/util/SparseBooleanArray.java +++ b/core/java/android/util/SparseBooleanArray.java @@ -25,6 +25,8 @@ import com.android.internal.util.ArrayUtils; * than using a HashMap to map Integers to Booleans. */ public class SparseBooleanArray implements Cloneable { + static final boolean[] EMPTY_BOOLEANS = new boolean[0]; + /** * Creates a new SparseBooleanArray containing no mappings. */ @@ -35,13 +37,19 @@ public class SparseBooleanArray implements Cloneable { /** * Creates a new SparseBooleanArray containing no mappings that will not * require any additional memory allocation to store the specified - * number of mappings. + * number of mappings. If you supply an initial capacity of 0, the + * sparse array will be initialized with a light-weight representation + * not requiring any additional array allocations. */ public SparseBooleanArray(int initialCapacity) { - initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); - - mKeys = new int[initialCapacity]; - mValues = new boolean[initialCapacity]; + if (initialCapacity == 0) { + mKeys = SparseArray.EMPTY_INTS; + mValues = EMPTY_BOOLEANS; + } else { + initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); + mKeys = new int[initialCapacity]; + mValues = new boolean[initialCapacity]; + } mSize = 0; } @@ -71,7 +79,7 @@ public class SparseBooleanArray implements Cloneable { * if no such mapping has been made. */ public boolean get(int key, boolean valueIfKeyNotFound) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i < 0) { return valueIfKeyNotFound; @@ -84,7 +92,7 @@ public class SparseBooleanArray implements Cloneable { * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i >= 0) { System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1)); @@ -99,7 +107,7 @@ public class SparseBooleanArray implements Cloneable { * was one. */ public void put(int key, boolean value) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; @@ -164,7 +172,7 @@ public class SparseBooleanArray implements Cloneable { * key is not mapped. */ public int indexOfKey(int key) { - return binarySearch(mKeys, 0, mSize, key); + return SparseArray.binarySearch(mKeys, mSize, key); } /** @@ -220,26 +228,6 @@ public class SparseBooleanArray implements Cloneable { mSize = pos + 1; } - private static int binarySearch(int[] a, int start, int len, int key) { - int high = start + len, low = start - 1, guess; - - while (high - low > 1) { - guess = (high + low) / 2; - - if (a[guess] < key) - low = guess; - else - high = guess; - } - - if (high == start + len) - return ~(start + len); - else if (a[high] == key) - return high; - else - return ~high; - } - private int[] mKeys; private boolean[] mValues; private int mSize; diff --git a/core/java/android/util/SparseIntArray.java b/core/java/android/util/SparseIntArray.java index 8d111770e8dd..122f7f58e0e5 100644 --- a/core/java/android/util/SparseIntArray.java +++ b/core/java/android/util/SparseIntArray.java @@ -24,7 +24,6 @@ import com.android.internal.util.ArrayUtils; * than using a HashMap to map Integers to Integers. */ public class SparseIntArray implements Cloneable { - private int[] mKeys; private int[] mValues; private int mSize; @@ -39,13 +38,19 @@ public class SparseIntArray implements Cloneable { /** * Creates a new SparseIntArray containing no mappings that will not * require any additional memory allocation to store the specified - * number of mappings. + * number of mappings. If you supply an initial capacity of 0, the + * sparse array will be initialized with a light-weight representation + * not requiring any additional array allocations. */ public SparseIntArray(int initialCapacity) { - initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); - - mKeys = new int[initialCapacity]; - mValues = new int[initialCapacity]; + if (initialCapacity == 0) { + mKeys = SparseArray.EMPTY_INTS; + mValues = SparseArray.EMPTY_INTS; + } else { + initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); + mKeys = new int[initialCapacity]; + mValues = new int[initialCapacity]; + } mSize = 0; } @@ -75,7 +80,7 @@ public class SparseIntArray implements Cloneable { * if no such mapping has been made. */ public int get(int key, int valueIfKeyNotFound) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i < 0) { return valueIfKeyNotFound; @@ -88,7 +93,7 @@ public class SparseIntArray implements Cloneable { * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i >= 0) { removeAt(i); @@ -110,7 +115,7 @@ public class SparseIntArray implements Cloneable { * was one. */ public void put(int key, int value) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; @@ -175,7 +180,7 @@ public class SparseIntArray implements Cloneable { * key is not mapped. */ public int indexOfKey(int key) { - return binarySearch(mKeys, 0, mSize, key); + return SparseArray.binarySearch(mKeys, mSize, key); } /** @@ -230,24 +235,4 @@ public class SparseIntArray implements Cloneable { mValues[pos] = value; mSize = pos + 1; } - - private static int binarySearch(int[] a, int start, int len, int key) { - int high = start + len, low = start - 1, guess; - - while (high - low > 1) { - guess = (high + low) / 2; - - if (a[guess] < key) - low = guess; - else - high = guess; - } - - if (high == start + len) - return ~(start + len); - else if (a[high] == key) - return high; - else - return ~high; - } } diff --git a/core/java/android/util/SparseLongArray.java b/core/java/android/util/SparseLongArray.java index 2f7a6fe63bb5..c608996c99bf 100644 --- a/core/java/android/util/SparseLongArray.java +++ b/core/java/android/util/SparseLongArray.java @@ -24,6 +24,7 @@ import com.android.internal.util.ArrayUtils; * than using a HashMap to map Integers to Longs. */ public class SparseLongArray implements Cloneable { + static final long[] EMPTY_LONGS = new long[0]; private int[] mKeys; private long[] mValues; @@ -39,13 +40,19 @@ public class SparseLongArray implements Cloneable { /** * Creates a new SparseLongArray containing no mappings that will not * require any additional memory allocation to store the specified - * number of mappings. + * number of mappings. If you supply an initial capacity of 0, the + * sparse array will be initialized with a light-weight representation + * not requiring any additional array allocations. */ public SparseLongArray(int initialCapacity) { - initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); - - mKeys = new int[initialCapacity]; - mValues = new long[initialCapacity]; + if (initialCapacity == 0) { + mKeys = SparseArray.EMPTY_INTS; + mValues = EMPTY_LONGS; + } else { + initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); + mKeys = new int[initialCapacity]; + mValues = new long[initialCapacity]; + } mSize = 0; } @@ -75,7 +82,7 @@ public class SparseLongArray implements Cloneable { * if no such mapping has been made. */ public long get(int key, long valueIfKeyNotFound) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i < 0) { return valueIfKeyNotFound; @@ -88,7 +95,7 @@ public class SparseLongArray implements Cloneable { * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i >= 0) { removeAt(i); @@ -110,7 +117,7 @@ public class SparseLongArray implements Cloneable { * was one. */ public void put(int key, long value) { - int i = binarySearch(mKeys, 0, mSize, key); + int i = SparseArray.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; @@ -164,7 +171,7 @@ public class SparseLongArray implements Cloneable { * key is not mapped. */ public int indexOfKey(int key) { - return binarySearch(mKeys, 0, mSize, key); + return SparseArray.binarySearch(mKeys, mSize, key); } /** @@ -222,24 +229,4 @@ public class SparseLongArray implements Cloneable { mKeys = nkeys; mValues = nvalues; } - - private static int binarySearch(int[] a, int start, int len, long key) { - int high = start + len, low = start - 1, guess; - - while (high - low > 1) { - guess = (high + low) / 2; - - if (a[guess] < key) - low = guess; - else - high = guess; - } - - if (high == start + len) - return ~(start + len); - else if (a[high] == key) - return high; - else - return ~high; - } } diff --git a/core/java/android/view/View.java b/core/java/android/view/View.java index babccf6f1c65..667505a573b1 100644 --- a/core/java/android/view/View.java +++ b/core/java/android/view/View.java @@ -15688,7 +15688,7 @@ public class View implements Drawable.Callback, KeyEvent.Callback, private void setKeyedTag(int key, Object tag) { if (mKeyedTags == null) { - mKeyedTags = new SparseArray<Object>(); + mKeyedTags = new SparseArray<Object>(2); } mKeyedTags.put(key, tag); diff --git a/core/java/android/widget/AbsListView.java b/core/java/android/widget/AbsListView.java index 5de739945494..4c0ccca0a784 100644 --- a/core/java/android/widget/AbsListView.java +++ b/core/java/android/widget/AbsListView.java @@ -1151,10 +1151,10 @@ public abstract class AbsListView extends AdapterView<ListAdapter> implements Te } if (mChoiceMode != CHOICE_MODE_NONE) { if (mCheckStates == null) { - mCheckStates = new SparseBooleanArray(); + mCheckStates = new SparseBooleanArray(0); } if (mCheckedIdStates == null && mAdapter != null && mAdapter.hasStableIds()) { - mCheckedIdStates = new LongSparseArray<Integer>(); + mCheckedIdStates = new LongSparseArray<Integer>(0); } // Modal multi-choice mode only has choices when the mode is active. Clear them. if (mChoiceMode == CHOICE_MODE_MULTIPLE_MODAL) { diff --git a/services/java/com/android/server/IntentResolver.java b/services/java/com/android/server/IntentResolver.java index 35345f5762ee..3a35f3f857dd 100644 --- a/services/java/com/android/server/IntentResolver.java +++ b/services/java/com/android/server/IntentResolver.java @@ -20,7 +20,6 @@ import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; -import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; @@ -29,12 +28,12 @@ import java.util.Set; import android.net.Uri; import android.util.FastImmutableArraySet; +import android.util.ArrayMap; import android.util.Log; import android.util.PrintWriterPrinter; import android.util.Slog; import android.util.LogPrinter; import android.util.Printer; -import android.util.StringBuilderPrinter; import android.content.Intent; import android.content.IntentFilter; @@ -46,7 +45,6 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { final private static String TAG = "IntentResolver"; final private static boolean DEBUG = false; final private static boolean localLOGV = DEBUG || false; - final private static boolean VALIDATE = false; public void addFilter(F f) { if (localLOGV) { @@ -67,21 +65,11 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { register_intent_filter(f, f.actionsIterator(), mTypedActionToFilter, " TypedAction: "); } - - if (VALIDATE) { - mOldResolver.addFilter(f); - verifyDataStructures(f); - } } public void removeFilter(F f) { removeFilterInternal(f); mFilters.remove(f); - - if (VALIDATE) { - mOldResolver.removeFilter(f); - verifyDataStructures(f); - } } void removeFilterInternal(F f) { @@ -319,16 +307,6 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { } sortResults(finalList); - if (VALIDATE) { - List<R> oldList = mOldResolver.queryIntent(intent, resolvedType, defaultOnly, userId); - if (oldList.size() != finalList.size()) { - ValidationFailure here = new ValidationFailure(); - here.fillInStackTrace(); - Log.wtf(TAG, "Query result " + intent + " size is " + finalList.size() - + "; old implementation is " + oldList.size(), here); - } - } - if (debug) { Slog.v(TAG, "Final result list:"); for (R r : finalList) { @@ -379,7 +357,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { out.print(prefix); out.println(filter); } - private final void addFilter(HashMap<String, F[]> map, String name, F filter) { + private final void addFilter(ArrayMap<String, F[]> map, String name, F filter) { F[] array = map.get(name); if (array == null) { array = newArray(2); @@ -464,7 +442,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { } private final int register_intent_filter(F filter, Iterator<String> i, - HashMap<String, F[]> dest, String prefix) { + ArrayMap<String, F[]> dest, String prefix) { if (i == null) { return 0; } @@ -480,7 +458,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { } private final int unregister_intent_filter(F filter, Iterator<String> i, - HashMap<String, F[]> dest, String prefix) { + ArrayMap<String, F[]> dest, String prefix) { if (i == null) { return 0; } @@ -495,7 +473,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { return num; } - private final void remove_all_objects(HashMap<String, F[]> map, String name, + private final void remove_all_objects(ArrayMap<String, F[]> map, String name, Object object) { F[] array = map.get(name); if (array != null) { @@ -613,120 +591,6 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { } }; - static class ValidationFailure extends RuntimeException { - } - - private void verifyDataStructures(IntentFilter src) { - compareMaps(src, "mTypeToFilter", mTypeToFilter, mOldResolver.mTypeToFilter); - compareMaps(src, "mBaseTypeToFilter", mBaseTypeToFilter, mOldResolver.mBaseTypeToFilter); - compareMaps(src, "mWildTypeToFilter", mWildTypeToFilter, mOldResolver.mWildTypeToFilter); - compareMaps(src, "mSchemeToFilter", mSchemeToFilter, mOldResolver.mSchemeToFilter); - compareMaps(src, "mActionToFilter", mActionToFilter, mOldResolver.mActionToFilter); - compareMaps(src, "mTypedActionToFilter", mTypedActionToFilter, mOldResolver.mTypedActionToFilter); - } - - private void compareMaps(IntentFilter src, String name, HashMap<String, F[]> cur, - HashMap<String, ArrayList<F>> old) { - if (cur.size() != old.size()) { - StringBuilder missing = new StringBuilder(128); - for (Map.Entry<String, ArrayList<F>> e : old.entrySet()) { - final F[] curArray = cur.get(e.getKey()); - if (curArray == null) { - if (missing.length() > 0) { - missing.append(' '); - } - missing.append(e.getKey()); - } - } - StringBuilder extra = new StringBuilder(128); - for (Map.Entry<String, F[]> e : cur.entrySet()) { - if (old.get(e.getKey()) == null) { - if (extra.length() > 0) { - extra.append(' '); - } - extra.append(e.getKey()); - } - } - StringBuilder srcStr = new StringBuilder(1024); - StringBuilderPrinter printer = new StringBuilderPrinter(srcStr); - src.dump(printer, ""); - ValidationFailure here = new ValidationFailure(); - here.fillInStackTrace(); - Log.wtf(TAG, "New map " + name + " size is " + cur.size() - + "; old implementation is " + old.size() - + "; missing: " + missing.toString() - + "; extra: " + extra.toString() - + "; src: " + srcStr.toString(), here); - return; - } - for (Map.Entry<String, ArrayList<F>> e : old.entrySet()) { - final F[] curArray = cur.get(e.getKey()); - int curLen = curArray != null ? curArray.length : 0; - if (curLen == 0) { - ValidationFailure here = new ValidationFailure(); - here.fillInStackTrace(); - Log.wtf(TAG, "New map " + name + " doesn't contain expected key " - + e.getKey() + " (array=" + curArray + ")"); - return; - } - while (curLen > 0 && curArray[curLen-1] == null) { - curLen--; - } - final ArrayList<F> oldArray = e.getValue(); - final int oldLen = oldArray.size(); - if (curLen != oldLen) { - ValidationFailure here = new ValidationFailure(); - here.fillInStackTrace(); - Log.wtf(TAG, "New map " + name + " entry " + e.getKey() + " size is " - + curLen + "; old implementation is " + oldLen, here); - return; - } - for (int i=0; i<oldLen; i++) { - F f = oldArray.get(i); - boolean found = false; - for (int j=0; j<curLen; j++) { - if (curArray[j] == f) { - found = true; - break; - } - } - if (!found) { - ValidationFailure here = new ValidationFailure(); - here.fillInStackTrace(); - Log.wtf(TAG, "New map " + name + " entry + " + e.getKey() - + " doesn't contain expected filter " + f, here); - } - } - for (int i=0; i<curLen; i++) { - if (curArray[i] == null) { - ValidationFailure here = new ValidationFailure(); - here.fillInStackTrace(); - Log.wtf(TAG, "New map " + name + " entry + " + e.getKey() - + " has unexpected null at " + i + "; array: " + curArray, here); - break; - } - } - } - } - - private final IntentResolverOld<F, R> mOldResolver = new IntentResolverOld<F, R>() { - @Override protected boolean isPackageForFilter(String packageName, F filter) { - return IntentResolver.this.isPackageForFilter(packageName, filter); - } - @Override protected boolean allowFilterResult(F filter, List<R> dest) { - return IntentResolver.this.allowFilterResult(filter, dest); - } - @Override protected boolean isFilterStopped(F filter, int userId) { - return IntentResolver.this.isFilterStopped(filter, userId); - } - @Override protected R newResult(F filter, int match, int userId) { - return IntentResolver.this.newResult(filter, match, userId); - } - @Override protected void sortResults(List<R> results) { - IntentResolver.this.sortResults(results); - } - }; - /** * All filters that have been registered. */ @@ -736,14 +600,14 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { * All of the MIME types that have been registered, such as "image/jpeg", * "image/*", or "{@literal *}/*". */ - private final HashMap<String, F[]> mTypeToFilter = new HashMap<String, F[]>(); + private final ArrayMap<String, F[]> mTypeToFilter = new ArrayMap<String, F[]>(); /** * The base names of all of all fully qualified MIME types that have been * registered, such as "image" or "*". Wild card MIME types such as * "image/*" will not be here. */ - private final HashMap<String, F[]> mBaseTypeToFilter = new HashMap<String, F[]>(); + private final ArrayMap<String, F[]> mBaseTypeToFilter = new ArrayMap<String, F[]>(); /** * The base names of all of the MIME types with a sub-type wildcard that @@ -752,21 +616,21 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> { * included here. This also includes the "*" for the "{@literal *}/*" * MIME type. */ - private final HashMap<String, F[]> mWildTypeToFilter = new HashMap<String, F[]>(); + private final ArrayMap<String, F[]> mWildTypeToFilter = new ArrayMap<String, F[]>(); /** * All of the URI schemes (such as http) that have been registered. */ - private final HashMap<String, F[]> mSchemeToFilter = new HashMap<String, F[]>(); + private final ArrayMap<String, F[]> mSchemeToFilter = new ArrayMap<String, F[]>(); /** * All of the actions that have been registered, but only those that did * not specify data. */ - private final HashMap<String, F[]> mActionToFilter = new HashMap<String, F[]>(); + private final ArrayMap<String, F[]> mActionToFilter = new ArrayMap<String, F[]>(); /** * All of the actions that have been registered and specified a MIME type. */ - private final HashMap<String, F[]> mTypedActionToFilter = new HashMap<String, F[]>(); + private final ArrayMap<String, F[]> mTypedActionToFilter = new ArrayMap<String, F[]>(); } diff --git a/services/java/com/android/server/IntentResolverOld.java b/services/java/com/android/server/IntentResolverOld.java deleted file mode 100644 index 94a23796cbb0..000000000000 --- a/services/java/com/android/server/IntentResolverOld.java +++ /dev/null @@ -1,638 +0,0 @@ -/* - * Copyright (C) 2006 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 com.android.server; - -import java.io.PrintWriter; -import java.util.ArrayList; -import java.util.Collections; -import java.util.Comparator; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.Set; - -import android.net.Uri; -import android.util.FastImmutableArraySet; -import android.util.Log; -import android.util.PrintWriterPrinter; -import android.util.Slog; -import android.util.LogPrinter; -import android.util.Printer; - -import android.content.Intent; -import android.content.IntentFilter; - -/** - * Temporary for verification of new implementation. - * {@hide} - */ -public abstract class IntentResolverOld<F extends IntentFilter, R extends Object> { - final private static String TAG = "IntentResolver"; - final private static boolean DEBUG = false; - final private static boolean localLOGV = DEBUG || false; - - public void addFilter(F f) { - if (localLOGV) { - Slog.v(TAG, "Adding filter: " + f); - f.dump(new LogPrinter(Log.VERBOSE, TAG, Log.LOG_ID_SYSTEM), " "); - Slog.v(TAG, " Building Lookup Maps:"); - } - - mFilters.add(f); - int numS = register_intent_filter(f, f.schemesIterator(), - mSchemeToFilter, " Scheme: "); - int numT = register_mime_types(f, " Type: "); - if (numS == 0 && numT == 0) { - register_intent_filter(f, f.actionsIterator(), - mActionToFilter, " Action: "); - } - if (numT != 0) { - register_intent_filter(f, f.actionsIterator(), - mTypedActionToFilter, " TypedAction: "); - } - } - - public void removeFilter(F f) { - removeFilterInternal(f); - mFilters.remove(f); - } - - void removeFilterInternal(F f) { - if (localLOGV) { - Slog.v(TAG, "Removing filter: " + f); - f.dump(new LogPrinter(Log.VERBOSE, TAG, Log.LOG_ID_SYSTEM), " "); - Slog.v(TAG, " Cleaning Lookup Maps:"); - } - - int numS = unregister_intent_filter(f, f.schemesIterator(), - mSchemeToFilter, " Scheme: "); - int numT = unregister_mime_types(f, " Type: "); - if (numS == 0 && numT == 0) { - unregister_intent_filter(f, f.actionsIterator(), - mActionToFilter, " Action: "); - } - if (numT != 0) { - unregister_intent_filter(f, f.actionsIterator(), - mTypedActionToFilter, " TypedAction: "); - } - } - - boolean dumpMap(PrintWriter out, String titlePrefix, String title, - String prefix, Map<String, ArrayList<F>> map, String packageName, - boolean printFilter) { - String eprefix = prefix + " "; - String fprefix = prefix + " "; - boolean printedSomething = false; - Printer printer = null; - for (Map.Entry<String, ArrayList<F>> e : map.entrySet()) { - ArrayList<F> a = e.getValue(); - final int N = a.size(); - boolean printedHeader = false; - for (int i=0; i<N; i++) { - F filter = a.get(i); - if (packageName != null && !isPackageForFilter(packageName, filter)) { - continue; - } - if (title != null) { - out.print(titlePrefix); out.println(title); - title = null; - } - if (!printedHeader) { - out.print(eprefix); out.print(e.getKey()); out.println(":"); - printedHeader = true; - } - printedSomething = true; - dumpFilter(out, fprefix, filter); - if (printFilter) { - if (printer == null) { - printer = new PrintWriterPrinter(out); - } - filter.dump(printer, fprefix + " "); - } - } - } - return printedSomething; - } - - public boolean dump(PrintWriter out, String title, String prefix, String packageName, - boolean printFilter) { - String innerPrefix = prefix + " "; - String sepPrefix = "\n" + prefix; - String curPrefix = title + "\n" + prefix; - if (dumpMap(out, curPrefix, "Full MIME Types:", innerPrefix, - mTypeToFilter, packageName, printFilter)) { - curPrefix = sepPrefix; - } - if (dumpMap(out, curPrefix, "Base MIME Types:", innerPrefix, - mBaseTypeToFilter, packageName, printFilter)) { - curPrefix = sepPrefix; - } - if (dumpMap(out, curPrefix, "Wild MIME Types:", innerPrefix, - mWildTypeToFilter, packageName, printFilter)) { - curPrefix = sepPrefix; - } - if (dumpMap(out, curPrefix, "Schemes:", innerPrefix, - mSchemeToFilter, packageName, printFilter)) { - curPrefix = sepPrefix; - } - if (dumpMap(out, curPrefix, "Non-Data Actions:", innerPrefix, - mActionToFilter, packageName, printFilter)) { - curPrefix = sepPrefix; - } - if (dumpMap(out, curPrefix, "MIME Typed Actions:", innerPrefix, - mTypedActionToFilter, packageName, printFilter)) { - curPrefix = sepPrefix; - } - return curPrefix == sepPrefix; - } - - private class IteratorWrapper implements Iterator<F> { - private final Iterator<F> mI; - private F mCur; - - IteratorWrapper(Iterator<F> it) { - mI = it; - } - - public boolean hasNext() { - return mI.hasNext(); - } - - public F next() { - return (mCur = mI.next()); - } - - public void remove() { - if (mCur != null) { - removeFilterInternal(mCur); - } - mI.remove(); - } - - } - - /** - * Returns an iterator allowing filters to be removed. - */ - public Iterator<F> filterIterator() { - return new IteratorWrapper(mFilters.iterator()); - } - - /** - * Returns a read-only set of the filters. - */ - public Set<F> filterSet() { - return Collections.unmodifiableSet(mFilters); - } - - public List<R> queryIntentFromList(Intent intent, String resolvedType, - boolean defaultOnly, ArrayList<ArrayList<F>> listCut, int userId) { - ArrayList<R> resultList = new ArrayList<R>(); - - final boolean debug = localLOGV || - ((intent.getFlags() & Intent.FLAG_DEBUG_LOG_RESOLUTION) != 0); - - FastImmutableArraySet<String> categories = getFastIntentCategories(intent); - final String scheme = intent.getScheme(); - int N = listCut.size(); - for (int i = 0; i < N; ++i) { - buildResolveList(intent, categories, debug, defaultOnly, - resolvedType, scheme, listCut.get(i), resultList, userId); - } - sortResults(resultList); - return resultList; - } - - public List<R> queryIntent(Intent intent, String resolvedType, boolean defaultOnly, - int userId) { - String scheme = intent.getScheme(); - - ArrayList<R> finalList = new ArrayList<R>(); - - final boolean debug = localLOGV || - ((intent.getFlags() & Intent.FLAG_DEBUG_LOG_RESOLUTION) != 0); - - if (debug) Slog.v( - TAG, "Resolving type " + resolvedType + " scheme " + scheme - + " of intent " + intent); - - ArrayList<F> firstTypeCut = null; - ArrayList<F> secondTypeCut = null; - ArrayList<F> thirdTypeCut = null; - ArrayList<F> schemeCut = null; - - // If the intent includes a MIME type, then we want to collect all of - // the filters that match that MIME type. - if (resolvedType != null) { - int slashpos = resolvedType.indexOf('/'); - if (slashpos > 0) { - final String baseType = resolvedType.substring(0, slashpos); - if (!baseType.equals("*")) { - if (resolvedType.length() != slashpos+2 - || resolvedType.charAt(slashpos+1) != '*') { - // Not a wild card, so we can just look for all filters that - // completely match or wildcards whose base type matches. - firstTypeCut = mTypeToFilter.get(resolvedType); - if (debug) Slog.v(TAG, "First type cut: " + firstTypeCut); - secondTypeCut = mWildTypeToFilter.get(baseType); - if (debug) Slog.v(TAG, "Second type cut: " + secondTypeCut); - } else { - // We can match anything with our base type. - firstTypeCut = mBaseTypeToFilter.get(baseType); - if (debug) Slog.v(TAG, "First type cut: " + firstTypeCut); - secondTypeCut = mWildTypeToFilter.get(baseType); - if (debug) Slog.v(TAG, "Second type cut: " + secondTypeCut); - } - // Any */* types always apply, but we only need to do this - // if the intent type was not already */*. - thirdTypeCut = mWildTypeToFilter.get("*"); - if (debug) Slog.v(TAG, "Third type cut: " + thirdTypeCut); - } else if (intent.getAction() != null) { - // The intent specified any type ({@literal *}/*). This - // can be a whole heck of a lot of things, so as a first - // cut let's use the action instead. - firstTypeCut = mTypedActionToFilter.get(intent.getAction()); - if (debug) Slog.v(TAG, "Typed Action list: " + firstTypeCut); - } - } - } - - // If the intent includes a data URI, then we want to collect all of - // the filters that match its scheme (we will further refine matches - // on the authority and path by directly matching each resulting filter). - if (scheme != null) { - schemeCut = mSchemeToFilter.get(scheme); - if (debug) Slog.v(TAG, "Scheme list: " + schemeCut); - } - - // If the intent does not specify any data -- either a MIME type or - // a URI -- then we will only be looking for matches against empty - // data. - if (resolvedType == null && scheme == null && intent.getAction() != null) { - firstTypeCut = mActionToFilter.get(intent.getAction()); - if (debug) Slog.v(TAG, "Action list: " + firstTypeCut); - } - - FastImmutableArraySet<String> categories = getFastIntentCategories(intent); - if (firstTypeCut != null) { - buildResolveList(intent, categories, debug, defaultOnly, - resolvedType, scheme, firstTypeCut, finalList, userId); - } - if (secondTypeCut != null) { - buildResolveList(intent, categories, debug, defaultOnly, - resolvedType, scheme, secondTypeCut, finalList, userId); - } - if (thirdTypeCut != null) { - buildResolveList(intent, categories, debug, defaultOnly, - resolvedType, scheme, thirdTypeCut, finalList, userId); - } - if (schemeCut != null) { - buildResolveList(intent, categories, debug, defaultOnly, - resolvedType, scheme, schemeCut, finalList, userId); - } - sortResults(finalList); - - if (debug) { - Slog.v(TAG, "Final result list:"); - for (R r : finalList) { - Slog.v(TAG, " " + r); - } - } - return finalList; - } - - /** - * Control whether the given filter is allowed to go into the result - * list. Mainly intended to prevent adding multiple filters for the - * same target object. - */ - protected boolean allowFilterResult(F filter, List<R> dest) { - return true; - } - - /** - * Returns whether the object associated with the given filter is - * "stopped," that is whether it should not be included in the result - * if the intent requests to excluded stopped objects. - */ - protected boolean isFilterStopped(F filter, int userId) { - return false; - } - - /** - * Returns whether this filter is owned by this package. This must be - * implemented to provide correct filtering of Intents that have - * specified a package name they are to be delivered to. - */ - protected abstract boolean isPackageForFilter(String packageName, F filter); - - @SuppressWarnings("unchecked") - protected R newResult(F filter, int match, int userId) { - return (R)filter; - } - - @SuppressWarnings("unchecked") - protected void sortResults(List<R> results) { - Collections.sort(results, mResolvePrioritySorter); - } - - protected void dumpFilter(PrintWriter out, String prefix, F filter) { - out.print(prefix); out.println(filter); - } - - private final int register_mime_types(F filter, String prefix) { - final Iterator<String> i = filter.typesIterator(); - if (i == null) { - return 0; - } - - int num = 0; - while (i.hasNext()) { - String name = i.next(); - num++; - if (localLOGV) Slog.v(TAG, prefix + name); - String baseName = name; - final int slashpos = name.indexOf('/'); - if (slashpos > 0) { - baseName = name.substring(0, slashpos).intern(); - } else { - name = name + "/*"; - } - - ArrayList<F> array = mTypeToFilter.get(name); - if (array == null) { - //Slog.v(TAG, "Creating new array for " + name); - array = new ArrayList<F>(); - mTypeToFilter.put(name, array); - } - array.add(filter); - - if (slashpos > 0) { - array = mBaseTypeToFilter.get(baseName); - if (array == null) { - //Slog.v(TAG, "Creating new array for " + name); - array = new ArrayList<F>(); - mBaseTypeToFilter.put(baseName, array); - } - array.add(filter); - } else { - array = mWildTypeToFilter.get(baseName); - if (array == null) { - //Slog.v(TAG, "Creating new array for " + name); - array = new ArrayList<F>(); - mWildTypeToFilter.put(baseName, array); - } - array.add(filter); - } - } - - return num; - } - - private final int unregister_mime_types(F filter, String prefix) { - final Iterator<String> i = filter.typesIterator(); - if (i == null) { - return 0; - } - - int num = 0; - while (i.hasNext()) { - String name = i.next(); - num++; - if (localLOGV) Slog.v(TAG, prefix + name); - String baseName = name; - final int slashpos = name.indexOf('/'); - if (slashpos > 0) { - baseName = name.substring(0, slashpos).intern(); - } else { - name = name + "/*"; - } - - if (!remove_all_objects(mTypeToFilter.get(name), filter)) { - mTypeToFilter.remove(name); - } - - if (slashpos > 0) { - if (!remove_all_objects(mBaseTypeToFilter.get(baseName), filter)) { - mBaseTypeToFilter.remove(baseName); - } - } else { - if (!remove_all_objects(mWildTypeToFilter.get(baseName), filter)) { - mWildTypeToFilter.remove(baseName); - } - } - } - return num; - } - - private final int register_intent_filter(F filter, Iterator<String> i, - HashMap<String, ArrayList<F>> dest, String prefix) { - if (i == null) { - return 0; - } - - int num = 0; - while (i.hasNext()) { - String name = i.next(); - num++; - if (localLOGV) Slog.v(TAG, prefix + name); - ArrayList<F> array = dest.get(name); - if (array == null) { - //Slog.v(TAG, "Creating new array for " + name); - array = new ArrayList<F>(); - dest.put(name, array); - } - array.add(filter); - } - return num; - } - - private final int unregister_intent_filter(F filter, Iterator<String> i, - HashMap<String, ArrayList<F>> dest, String prefix) { - if (i == null) { - return 0; - } - - int num = 0; - while (i.hasNext()) { - String name = i.next(); - num++; - if (localLOGV) Slog.v(TAG, prefix + name); - if (!remove_all_objects(dest.get(name), filter)) { - dest.remove(name); - } - } - return num; - } - - private final boolean remove_all_objects(List<F> list, Object object) { - if (list != null) { - int N = list.size(); - for (int idx=0; idx<N; idx++) { - if (list.get(idx) == object) { - list.remove(idx); - idx--; - N--; - } - } - return N > 0; - } - return false; - } - - private static FastImmutableArraySet<String> getFastIntentCategories(Intent intent) { - final Set<String> categories = intent.getCategories(); - if (categories == null) { - return null; - } - return new FastImmutableArraySet<String>(categories.toArray(new String[categories.size()])); - } - - private void buildResolveList(Intent intent, FastImmutableArraySet<String> categories, - boolean debug, boolean defaultOnly, - String resolvedType, String scheme, List<F> src, List<R> dest, int userId) { - final String action = intent.getAction(); - final Uri data = intent.getData(); - final String packageName = intent.getPackage(); - - final boolean excludingStopped = intent.isExcludingStopped(); - - final int N = src != null ? src.size() : 0; - boolean hasNonDefaults = false; - int i; - for (i=0; i<N; i++) { - F filter = src.get(i); - int match; - if (debug) Slog.v(TAG, "Matching against filter " + filter); - - if (excludingStopped && isFilterStopped(filter, userId)) { - if (debug) { - Slog.v(TAG, " Filter's target is stopped; skipping"); - } - continue; - } - - // Is delivery being limited to filters owned by a particular package? - if (packageName != null && !isPackageForFilter(packageName, filter)) { - if (debug) { - Slog.v(TAG, " Filter is not from package " + packageName + "; skipping"); - } - continue; - } - - // Do we already have this one? - if (!allowFilterResult(filter, dest)) { - if (debug) { - Slog.v(TAG, " Filter's target already added"); - } - continue; - } - - match = filter.match(action, resolvedType, scheme, data, categories, TAG); - if (match >= 0) { - if (debug) Slog.v(TAG, " Filter matched! match=0x" + - Integer.toHexString(match)); - if (!defaultOnly || filter.hasCategory(Intent.CATEGORY_DEFAULT)) { - final R oneResult = newResult(filter, match, userId); - if (oneResult != null) { - dest.add(oneResult); - } - } else { - hasNonDefaults = true; - } - } else { - if (debug) { - String reason; - switch (match) { - case IntentFilter.NO_MATCH_ACTION: reason = "action"; break; - case IntentFilter.NO_MATCH_CATEGORY: reason = "category"; break; - case IntentFilter.NO_MATCH_DATA: reason = "data"; break; - case IntentFilter.NO_MATCH_TYPE: reason = "type"; break; - default: reason = "unknown reason"; break; - } - Slog.v(TAG, " Filter did not match: " + reason); - } - } - } - - if (dest.size() == 0 && hasNonDefaults) { - Slog.w(TAG, "resolveIntent failed: found match, but none with Intent.CATEGORY_DEFAULT"); - } - } - - // Sorts a List of IntentFilter objects into descending priority order. - @SuppressWarnings("rawtypes") - private static final Comparator mResolvePrioritySorter = new Comparator() { - public int compare(Object o1, Object o2) { - final int q1 = ((IntentFilter) o1).getPriority(); - final int q2 = ((IntentFilter) o2).getPriority(); - return (q1 > q2) ? -1 : ((q1 < q2) ? 1 : 0); - } - }; - - /** - * All filters that have been registered. - */ - final HashSet<F> mFilters = new HashSet<F>(); - - /** - * All of the MIME types that have been registered, such as "image/jpeg", - * "image/*", or "{@literal *}/*". - */ - final HashMap<String, ArrayList<F>> mTypeToFilter - = new HashMap<String, ArrayList<F>>(); - - /** - * The base names of all of all fully qualified MIME types that have been - * registered, such as "image" or "*". Wild card MIME types such as - * "image/*" will not be here. - */ - final HashMap<String, ArrayList<F>> mBaseTypeToFilter - = new HashMap<String, ArrayList<F>>(); - - /** - * The base names of all of the MIME types with a sub-type wildcard that - * have been registered. For example, a filter with "image/*" will be - * included here as "image" but one with "image/jpeg" will not be - * included here. This also includes the "*" for the "{@literal *}/*" - * MIME type. - */ - final HashMap<String, ArrayList<F>> mWildTypeToFilter - = new HashMap<String, ArrayList<F>>(); - - /** - * All of the URI schemes (such as http) that have been registered. - */ - final HashMap<String, ArrayList<F>> mSchemeToFilter - = new HashMap<String, ArrayList<F>>(); - - /** - * All of the actions that have been registered, but only those that did - * not specify data. - */ - final HashMap<String, ArrayList<F>> mActionToFilter - = new HashMap<String, ArrayList<F>>(); - - /** - * All of the actions that have been registered and specified a MIME type. - */ - final HashMap<String, ArrayList<F>> mTypedActionToFilter - = new HashMap<String, ArrayList<F>>(); -} - diff --git a/services/java/com/android/server/pm/PackageManagerService.java b/services/java/com/android/server/pm/PackageManagerService.java index f8531fad258b..9d195df19d34 100644 --- a/services/java/com/android/server/pm/PackageManagerService.java +++ b/services/java/com/android/server/pm/PackageManagerService.java @@ -431,7 +431,7 @@ public class PackageManagerService extends IPackageManager.Stub { final SparseArray<HashMap<String, ArrayList<String>>> mUidMap; public PendingPackageBroadcasts() { - mUidMap = new SparseArray<HashMap<String, ArrayList<String>>>(); + mUidMap = new SparseArray<HashMap<String, ArrayList<String>>>(2); } public ArrayList<String> get(int userId, String packageName) { diff --git a/services/java/com/android/server/wm/WindowAnimator.java b/services/java/com/android/server/wm/WindowAnimator.java index dbc991583033..3fc3ac6f6986 100644 --- a/services/java/com/android/server/wm/WindowAnimator.java +++ b/services/java/com/android/server/wm/WindowAnimator.java @@ -65,7 +65,7 @@ public class WindowAnimator { Object mLastWindowFreezeSource; SparseArray<DisplayContentsAnimator> mDisplayContentsAnimators = - new SparseArray<WindowAnimator.DisplayContentsAnimator>(); + new SparseArray<WindowAnimator.DisplayContentsAnimator>(2); boolean mInitialized = false; @@ -654,7 +654,7 @@ public class WindowAnimator { void setAppLayoutChanges(final AppWindowAnimator appAnimator, final int changes, String s) { // Used to track which displays layout changes have been done. - SparseIntArray displays = new SparseIntArray(); + SparseIntArray displays = new SparseIntArray(2); WindowList windows = appAnimator.mAppToken.allAppWindows; for (int i = windows.size() - 1; i >= 0; i--) { final int displayId = windows.get(i).getDisplayId(); diff --git a/services/java/com/android/server/wm/WindowManagerService.java b/services/java/com/android/server/wm/WindowManagerService.java index 3ebe083fb017..62141fd66eb8 100644 --- a/services/java/com/android/server/wm/WindowManagerService.java +++ b/services/java/com/android/server/wm/WindowManagerService.java @@ -424,7 +424,7 @@ public class WindowManagerService extends IWindowManager.Stub String mLastANRState; /** All DisplayContents in the world, kept here */ - private SparseArray<DisplayContent> mDisplayContents = new SparseArray<DisplayContent>(); + private SparseArray<DisplayContent> mDisplayContents = new SparseArray<DisplayContent>(2); private final AllWindowsIterator mTmpWindowsIterator = new AllWindowsIterator(); diff --git a/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java b/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java index c7cd975c8d1c..d7a6c1d56fa8 100644 --- a/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java +++ b/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java @@ -182,7 +182,7 @@ public class ActivityTestMain extends Activity { menu.add("Send!").setOnMenuItemClickListener(new MenuItem.OnMenuItemClickListener() { @Override public boolean onMenuItemClick(MenuItem item) { Intent intent = new Intent(ActivityTestMain.this, SingleUserReceiver.class); - sendOrderedBroadcast(intent, null, new BroadcastResultReceiver(), + sendOrderedBroadcast(intent, null, new BroadcastResultReceiver(), null, Activity.RESULT_OK, null, null); return true; } @@ -285,6 +285,12 @@ public class ActivityTestMain extends Activity { return true; } }); + menu.add("HashArray").setOnMenuItemClickListener(new MenuItem.OnMenuItemClickListener() { + @Override public boolean onMenuItemClick(MenuItem item) { + ArrayMapTests.run(); + return true; + } + }); return true; } diff --git a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java new file mode 100644 index 000000000000..d9e1a83b0bde --- /dev/null +++ b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java @@ -0,0 +1,303 @@ +/* + * Copyright (C) 2013 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 com.google.android.test.activity; + +import android.util.ArrayMap; +import android.util.Log; + +import java.util.Collection; +import java.util.HashMap; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; + +public class ArrayMapTests { + static final int OP_ADD = 1; + static final int OP_REM = 2; + + static int[] OPS = new int[] { + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, + }; + + static int[] KEYS = new int[] { + // General adding and removing. + 100, 1900, 600, 200, 1200, 1500, 1800, 100, 1900, + 2100, 300, 800, 600, 1100, 1300, 2000, 1000, 1400, + 600, 100, 1900, 600, 300, 2100, 200, 800, 800, + 1800, 1500, 1300, 1100, 2000, 1400, 1000, 1200, 1900, + + // Shrink when removing item from end. + 100, 200, 300, 400, 500, 600, 700, 800, 900, + 900, 800, 700, 600, 500, 400, 300, 200, 100, + + // Shrink when removing item from middle. + 100, 200, 300, 400, 500, 600, 700, 800, 900, + 900, 800, 700, 600, 500, 400, 200, 300, 100, + + // Shrink when removing item from front. + 100, 200, 300, 400, 500, 600, 700, 800, 900, + 900, 800, 700, 600, 500, 400, 100, 200, 300, + + // Test hash collisions. + 105, 106, 108, 104, 102, 102, 107, 5, 205, + 4, 202, 203, 3, 5, 101, 109, 200, 201, + 106, 108, 104, 102, 103, 105, 107, 101, 109, + 4, 5, 3, 5, 200, 203, 202, 201, 205, + }; + + static class ControlledHash { + final int mValue; + + ControlledHash(int value) { + mValue = value; + } + + @Override + public final boolean equals(Object o) { + return mValue == ((ControlledHash)o).mValue; + } + + @Override + public final int hashCode() { + return mValue/100; + } + + @Override + public final String toString() { + return Integer.toString(mValue); + } + } + + private static boolean compare(Object v1, Object v2) { + if (v1 == null) { + return v2 == null; + } + if (v2 == null) { + return false; + } + return v1.equals(v2); + } + + private static boolean compareMaps(HashMap map, ArrayMap array) { + if (map.size() != array.size()) { + Log.e("test", "Bad size: expected " + map.size() + ", got " + array.size()); + return false; + } + + Set<Map.Entry> mapSet = map.entrySet(); + for (Map.Entry entry : mapSet) { + Object expValue = entry.getValue(); + Object gotValue = array.get(entry.getKey()); + if (!compare(expValue, gotValue)) { + Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue + + " at key " + entry.getKey()); + return false; + } + } + + for (int i=0; i<array.size(); i++) { + Object gotValue = array.valueAt(i); + Object key = array.keyAt(i); + Object expValue = map.get(key); + if (!compare(expValue, gotValue)) { + Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue + + " at key " + key); + return false; + } + } + + int index = 0; + for (Object entry : array.entrySet()) { + Object key = ((Map.Entry)entry).getKey(); + Object value = ((Map.Entry)entry).getValue(); + Object realKey = array.keyAt(index); + Object realValue = array.valueAt(index); + if (!compare(key, realKey)) { + Log.e("test", "Bad entry iterator: expected key " + realKey + ", got " + key + + " at index " + index); + return false; + } + if (!compare(value, realValue)) { + Log.e("test", "Bad entry iterator: expected value " + realValue + ", got " + value + + " at index " + index); + return false; + } + index++; + } + + index = 0; + for (Object key : array.keySet()) { + Object realKey = array.keyAt(index); + if (!compare(key, realKey)) { + Log.e("test", "Bad key iterator: expected key " + realKey + ", got " + key + + " at index " + index); + return false; + } + index++; + } + + index = 0; + for (Object value : array.values()) { + Object realValue = array.valueAt(index); + if (!compare(value, realValue)) { + Log.e("test", "Bad value iterator: expected value " + realValue + ", got " + value + + " at index " + index); + return false; + } + index++; + } + + return true; + } + + private static boolean validateArrayMap(ArrayMap array) { + Set<Map.Entry> entrySet = array.entrySet(); + int index=0; + Iterator<Map.Entry> entryIt = entrySet.iterator(); + while (entryIt.hasNext()) { + Map.Entry entry = entryIt.next(); + Object value = entry.getKey(); + Object realValue = array.keyAt(index); + if (!compare(realValue, value)) { + Log.e("test", "Bad hash array entry set: expected key " + realValue + + ", got " + value + " at index " + index); + return false; + } + value = entry.getValue(); + realValue = array.valueAt(index); + if (!compare(realValue, value)) { + Log.e("test", "Bad hash array entry set: expected value " + realValue + + ", got " + value + " at index " + index); + return false; + } + index++; + } + + index = 0; + Set keySet = array.keySet(); + Iterator keyIt = keySet.iterator(); + while (keyIt.hasNext()) { + Object value = keyIt.next(); + Object realValue = array.keyAt(index); + if (!compare(realValue, value)) { + Log.e("test", "Bad hash array key set: expected key " + realValue + + ", got " + value + " at index " + index); + return false; + } + index++; + } + + index = 0; + Collection valueCol = array.values(); + Iterator valueIt = valueCol.iterator(); + while (valueIt.hasNext()) { + Object value = valueIt.next(); + Object realValue = array.valueAt(index); + if (!compare(realValue, value)) { + Log.e("test", "Bad hash array value col: expected value " + realValue + + ", got " + value + " at index " + index); + return false; + } + index++; + } + + return true; + } + + private static void dump(HashMap map, ArrayMap array) { + Log.e("test", "HashMap of " + map.size() + " entries:"); + Set<Map.Entry> mapSet = map.entrySet(); + for (Map.Entry entry : mapSet) { + Log.e("test", " " + entry.getKey() + " -> " + entry.getValue()); + } + Log.e("test", "ArrayMap of " + array.size() + " entries:"); + for (int i=0; i<array.size(); i++) { + Log.e("test", " " + array.keyAt(i) + " -> " + array.valueAt(i)); + } + } + + public static void run() { + HashMap<ControlledHash, Integer> mHashMap = new HashMap<ControlledHash, Integer>(); + ArrayMap<ControlledHash, Integer> mArrayMap = new ArrayMap<ControlledHash, Integer>(); + + for (int i=0; i<OPS.length; i++) { + Integer oldMap; + Integer oldArray; + switch (OPS[i]) { + case OP_ADD: + Log.i("test", "Adding key: " + KEYS[i]); + oldMap = mHashMap.put(new ControlledHash(KEYS[i]), i); + oldArray = mArrayMap.put(new ControlledHash(KEYS[i]), i); + break; + case OP_REM: + Log.i("test", "Removing key: " + KEYS[i]); + oldMap = mHashMap.remove(new ControlledHash(KEYS[i])); + oldArray = mArrayMap.remove(new ControlledHash(KEYS[i])); + break; + default: + Log.e("test", "Bad operation " + OPS[i] + " @ " + i); + return; + } + if (!compare(oldMap, oldArray)) { + Log.e("test", "Bad result: expected " + oldMap + ", got " + oldArray); + dump(mHashMap, mArrayMap); + return; + } + if (!validateArrayMap(mArrayMap)) { + dump(mHashMap, mArrayMap); + return; + } + if (!compareMaps(mHashMap, mArrayMap)) { + dump(mHashMap, mArrayMap); + return; + } + } + + mArrayMap.put(new ControlledHash(50000), 100); + ControlledHash lookup = new ControlledHash(50000); + Iterator<ControlledHash> it = mArrayMap.keySet().iterator(); + while (it.hasNext()) { + if (it.next().equals(lookup)) { + it.remove(); + } + } + if (mArrayMap.containsKey(lookup)) { + Log.e("test", "Bad iterator: didn't remove test key"); + dump(mHashMap, mArrayMap); + } + + Log.e("test", "Test successful; printing final map."); + dump(mHashMap, mArrayMap); + } +} diff --git a/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java b/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java index 5f4f00626059..309ce34dc87a 100644 --- a/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java +++ b/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java @@ -21,7 +21,11 @@ import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.RandomAccessFile; +import java.lang.String; +import java.util.HashMap; +import java.util.Random; +import android.util.ArrayMap; import org.xmlpull.v1.XmlPullParser; import org.xmlpull.v1.XmlPullParserException; @@ -142,6 +146,18 @@ public class TestService extends Service { new LoadRecycleLargeBitmapOp(), new LoadSmallScaledBitmapOp(), new LoadLargeScaledBitmapOp(), + new GrowTinyHashMapOp(), + new GrowTinyArrayMapOp(), + new GrowSmallHashMapOp(), + new GrowSmallArrayMapOp(), + new GrowLargeHashMapOp(), + new GrowLargeArrayMapOp(), + new LookupTinyHashMapOp(), + new LookupTinyArrayMapOp(), + new LookupSmallHashMapOp(), + new LookupSmallArrayMapOp(), + new LookupLargeHashMapOp(), + new LookupLargeArrayMapOp(), }; static final int CMD_START_TEST = 1; @@ -1111,4 +1127,196 @@ public class TestService extends Service { mFile.delete(); } } + + static abstract class GenericMapOp extends Op { + final int mSize; + String[] mKeys; + String[] mValues; + + GenericMapOp(String name, String longName, int size) { + super(name, longName); + mSize = size; + } + + void onInit(Context context, boolean foreground) { + mKeys = new String[mSize]; + mValues = new String[mSize]; + Random random = new Random(0); + for (int i=0; i<mSize; i++) { + int chars = random.nextInt(10); + StringBuilder builder = new StringBuilder(chars); + for (int j=0; j<chars; j++) { + builder.append('a' + random.nextInt(100)); + } + mKeys[i] = builder.toString(); + mValues[i] = Integer.toString(i); + } + } + + int getOpsPerRun() { + return mSize; + } + } + + static class GrowTinyHashMapOp extends GenericMapOp { + GrowTinyHashMapOp() { + super("GrowTinyHashMap", "Add 5 items to a HashMap", 5); + } + + boolean onRun() { + HashMap<String, String> map = new HashMap<String, String>(); + for (int i=0; i<mSize; i++) { + map.put(mKeys[i], mValues[i]); + } + return true; + } + } + + static class GrowTinyArrayMapOp extends GenericMapOp { + GrowTinyArrayMapOp() { + super("GrowTinyArrayMap", "Add 5 items to a ArrayMap", 5); + } + + boolean onRun() { + ArrayMap<String, String> map = new ArrayMap<String, String>(); + for (int i=0; i<mSize; i++) { + map.put(mKeys[i], mValues[i]); + } + return true; + } + } + + static class GrowSmallHashMapOp extends GenericMapOp { + GrowSmallHashMapOp() { + super("GrowSmallHashMap", "Add 100 items to a HashMap", 100); + } + + boolean onRun() { + HashMap<String, String> map = new HashMap<String, String>(); + for (int i=0; i<mSize; i++) { + map.put(mKeys[i], mValues[i]); + } + return true; + } + } + + static class GrowSmallArrayMapOp extends GenericMapOp { + GrowSmallArrayMapOp() { + super("GrowSmallArrayMap", "Add 100 items to a ArrayMap", 100); + } + + boolean onRun() { + ArrayMap<String, String> map = new ArrayMap<String, String>(); + for (int i=0; i<mSize; i++) { + map.put(mKeys[i], mValues[i]); + } + return true; + } + } + + static class GrowLargeHashMapOp extends GenericMapOp { + GrowLargeHashMapOp() { + super("GrowLargeHashMap", "Add 10000 items to a HashMap", 10000); + } + + boolean onRun() { + HashMap<String, String> map = new HashMap<String, String>(); + for (int i=0; i<mSize; i++) { + map.put(mKeys[i], mValues[i]); + } + return true; + } + } + + static class GrowLargeArrayMapOp extends GenericMapOp { + GrowLargeArrayMapOp() { + super("GrowLargeArrayMap", "Add 10000 items to a ArrayMap", 10000); + } + + boolean onRun() { + ArrayMap<String, String> map = new ArrayMap<String, String>(); + for (int i=0; i<mSize; i++) { + map.put(mKeys[i], mValues[i]); + } + return true; + } + } + + static class LookupTinyHashMapOp extends LookupSmallHashMapOp { + LookupTinyHashMapOp() { + super("LookupTinyHashMap", "Lookup items in 5 entry HashMap", 5); + } + } + + static class LookupTinyArrayMapOp extends LookupSmallArrayMapOp { + LookupTinyArrayMapOp() { + super("LookupTinyArrayMap", "Lookup items in 5 entry ArrayMap", 5); + } + } + + static class LookupSmallHashMapOp extends GenericMapOp { + HashMap<String, String> mHashMap; + + LookupSmallHashMapOp() { + super("LookupSmallHashMap", "Lookup items in 100 entry HashMap", 100); + } + + LookupSmallHashMapOp(String name, String longname, int size) { + super(name, longname, size); + } + + void onInit(Context context, boolean foreground) { + super.onInit(context, foreground); + mHashMap = new HashMap<String, String>(); + for (int i=0; i<mSize; i++) { + mHashMap.put(mKeys[i], mValues[i]); + } + } + + boolean onRun() { + for (int i=0; i<mSize; i++) { + mHashMap.get(mKeys[i]); + } + return true; + } + } + + static class LookupSmallArrayMapOp extends GenericMapOp { + ArrayMap<String, String> mArrayMap; + + LookupSmallArrayMapOp() { + super("LookupSmallArrayMap", "Lookup items in 100 entry ArrayMap", 100); + } + + LookupSmallArrayMapOp(String name, String longname, int size) { + super(name, longname, size); + } + + void onInit(Context context, boolean foreground) { + super.onInit(context, foreground); + mArrayMap = new ArrayMap<String, String>(); + for (int i=0; i<mSize; i++) { + mArrayMap.put(mKeys[i], mValues[i]); + } + } + + boolean onRun() { + for (int i=0; i<mSize; i++) { + mArrayMap.get(mKeys[i]); + } + return true; + } + } + + static class LookupLargeHashMapOp extends LookupSmallHashMapOp { + LookupLargeHashMapOp() { + super("LookupLargeHashMap", "Lookup items in 10000 entry HashMap", 10000); + } + } + + static class LookupLargeArrayMapOp extends LookupSmallArrayMapOp { + LookupLargeArrayMapOp() { + super("LookupLargeArrayMap", "Lookup items in 10000 entry ArrayMap", 10000); + } + } } |