From f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccda Mon Sep 17 00:00:00 2001 From: Dianne Hackborn Date: Mon, 20 May 2013 18:42:16 -0700 Subject: New ArrayMap class. This is a new kind of key/value mapping that stores its data as an array, so it doesn't need to create an extra Entry object for every mapping placed in to it. It is also optimized to reduce memory overhead in other ways, by keeping the base object small, being fairly aggressive about keeping the array data structures small, etc. There are some unit and performance tests dropped in to some random places; they will need to be put somewhere else once I decided what we are going to do with this for the next release (for example if we make it public the unit tests should go in to CTS). Switch IntentResolver to using ArrayMap instead of HashMap. Also get rid of a bunch of duplicate implementations of binarySearch, and add an optimization to the various sparse arrays where you can supply an explicit 0 capacity to prevent it from doing an initial array allocation; use this new optimization in a few places where it makes sense. Change-Id: I01ef2764680f8ae49938e2a2ed40dc01606a056b --- core/java/android/util/SparseArray.java | 62 +++++++++++++++++++-------------- 1 file changed, 35 insertions(+), 27 deletions(-) (limited to 'core/java/android/util/SparseArray.java') 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 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 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 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 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 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 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 implements Cloneable { gc(); } - return binarySearch(mKeys, 0, mSize, key); + return binarySearch(mKeys, mSize, key); } /** @@ -335,23 +343,23 @@ public class SparseArray 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 } } -- cgit v1.2.3 From b993f41eb2f165425dfdf0f93ea0b1e354eca837 Mon Sep 17 00:00:00 2001 From: Dianne Hackborn Date: Fri, 12 Jul 2013 17:46:45 -0700 Subject: Update SparseArray docs to be more informative. Change-Id: I5d8d17d46a69ccdcf6b29f93be3d44addd80ab61 --- core/java/android/util/SparseArray.java | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-) (limited to 'core/java/android/util/SparseArray.java') diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java index 001fc5bcbbb6..0e013c376303 100644 --- a/core/java/android/util/SparseArray.java +++ b/core/java/android/util/SparseArray.java @@ -20,8 +20,25 @@ import com.android.internal.util.ArrayUtils; /** * SparseArrays map integers to Objects. Unlike a normal array of Objects, - * there can be gaps in the indices. It is intended to be more efficient - * than using a HashMap to map Integers to Objects. + * there can be gaps in the indices. It is intended to be more memory efficient + * than using a HashMap to map Integers to Objects, both because it avoids + * auto-boxing keys and its data structure doesn't rely on an extra entry object + * for each mapping. + * + *

Note that this container keeps its mappings in an array data structure, + * using a binary search to find keys. The 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%.

+ * + *

To help with performance, the container includes an optimization when removing + * keys: instead of compacting its array immediately, it leaves the removed entry marked + * as deleted. The entry can then be re-used for the same key, or compacted later in + * a single garbage collection step of all removed entries. This garbage collection will + * need to be performed at any time the array needs to be grown or the the map size or + * entry values are retrieved.

*/ public class SparseArray implements Cloneable { private static final Object DELETED = new Object(); -- cgit v1.2.3 From 3e82ba1a67b0c756ab6a289985f4cfc53725b311 Mon Sep 17 00:00:00 2001 From: Dianne Hackborn Date: Tue, 16 Jul 2013 13:23:55 -0700 Subject: Make ArrayMap public! :) Also do some tweaking of the various container classes to synchronize them with the support lib and make it easier to copy code between the two. And update activity/fragment to use ArrayMap. Change-Id: I3cfe82392a17119dfc72c3d9961f64e1914f42be --- core/java/android/util/SparseArray.java | 70 ++++++++++++++++++++++----------- 1 file changed, 47 insertions(+), 23 deletions(-) (limited to 'core/java/android/util/SparseArray.java') diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java index 0e013c376303..6e6609051aae 100644 --- a/core/java/android/util/SparseArray.java +++ b/core/java/android/util/SparseArray.java @@ -42,8 +42,6 @@ import com.android.internal.util.ArrayUtils; */ public class SparseArray 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; @@ -66,8 +64,8 @@ public class SparseArray implements Cloneable { */ public SparseArray(int initialCapacity) { if (initialCapacity == 0) { - mKeys = EMPTY_INTS; - mValues = EMPTY_OBJECTS; + mKeys = ContainerHelpers.EMPTY_INTS; + mValues = ContainerHelpers.EMPTY_OBJECTS; } else { initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); mKeys = new int[initialCapacity]; @@ -104,7 +102,7 @@ public class SparseArray implements Cloneable { */ @SuppressWarnings("unchecked") public E get(int key, E valueIfKeyNotFound) { - int i = binarySearch(mKeys, mSize, key); + int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; @@ -117,7 +115,7 @@ public class SparseArray implements Cloneable { * Removes the mapping from the specified key, if there was any. */ public void delete(int key) { - int i = binarySearch(mKeys, mSize, key); + int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { @@ -144,6 +142,19 @@ public class SparseArray implements Cloneable { } } + /** + * Remove a range of mappings as a batch. + * + * @param index Index to begin at + * @param size Number of mappings to remove + */ + public void removeAtRange(int index, int size) { + final int end = Math.min(mSize, index + size); + for (int i = index; i < end; i++) { + removeAt(i); + } + } + private void gc() { // Log.e("SparseArray", "gc start with " + mSize); @@ -178,7 +189,7 @@ public class SparseArray implements Cloneable { * was one. */ public void put(int key, E value) { - int i = binarySearch(mKeys, mSize, key); + int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { mValues[i] = value; @@ -195,7 +206,7 @@ public class SparseArray implements Cloneable { gc(); // Search again because indices may have changed. - i = ~binarySearch(mKeys, mSize, key); + i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } if (mSize >= mKeys.length) { @@ -286,7 +297,7 @@ public class SparseArray implements Cloneable { gc(); } - return binarySearch(mKeys, mSize, key); + return ContainerHelpers.binarySearch(mKeys, mSize, key); } /** @@ -360,23 +371,36 @@ public class SparseArray implements Cloneable { mSize = pos + 1; } - // 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]; + /** + * {@inheritDoc} + * + *

This implementation composes a string by iterating over its mappings. If + * this map contains itself as a value, the string "(this Map)" + * will appear in its place. + */ + @Override + public String toString() { + if (size() <= 0) { + return "{}"; + } - if (midVal < value) { - lo = mid + 1; - } else if (midVal > value) { - hi = mid - 1; + StringBuilder buffer = new StringBuilder(mSize * 28); + buffer.append('{'); + for (int i=0; i 0) { + buffer.append(", "); + } + int key = keyAt(i); + buffer.append(key); + buffer.append('='); + Object value = valueAt(i); + if (value != this) { + buffer.append(value); } else { - return mid; // value found + buffer.append("(this Map)"); } } - return ~lo; // value not present + buffer.append('}'); + return buffer.toString(); } } -- cgit v1.2.3 From 5771302ca13c31cb85f17bc58da8f6f8227c9b85 Mon Sep 17 00:00:00 2001 From: Flavio Lerda Date: Sun, 8 Sep 2013 18:04:58 +0100 Subject: Document the order of values returned by keyAt(). The values returned by keyAt() are currently guaranteed to be in ascending order. This is helpful to users of the API to be able to make assumptions about the keys and values when iterating over one of the sparse array implementations. This commit adds documentation about this. Change-Id: I3d7eb78e115ce174f1167b83904b44bf5120b223 --- core/java/android/util/SparseArray.java | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'core/java/android/util/SparseArray.java') diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java index 6e6609051aae..6e168a8b4ccd 100644 --- a/core/java/android/util/SparseArray.java +++ b/core/java/android/util/SparseArray.java @@ -39,6 +39,12 @@ import com.android.internal.util.ArrayUtils; * a single garbage collection step of all removed entries. This garbage collection will * need to be performed at any time the array needs to be grown or the the map size or * entry values are retrieved.

+ * + *

It is possible to iterate over the items in this container using + * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using + * keyAt(int) with ascending values of the index will return the + * keys in ascending order, or the values corresponding to the keys in ascending + * order in the case of valueAt(int).

*/ public class SparseArray implements Cloneable { private static final Object DELETED = new Object(); @@ -251,6 +257,11 @@ public class SparseArray implements Cloneable { * Given an index in the range 0...size()-1, returns * the key from the indexth key-value mapping that this * SparseArray stores. + * + *

The keys corresponding to indices in ascending order are guaranteed to + * be in ascending order, e.g., keyAt(0) will return the + * smallest key and keyAt(size()-1) will return the largest + * key.

*/ public int keyAt(int index) { if (mGarbage) { @@ -264,6 +275,12 @@ public class SparseArray implements Cloneable { * Given an index in the range 0...size()-1, returns * the value from the indexth key-value mapping that this * SparseArray stores. + * + *

The values corresponding to indices in ascending order are guaranteed + * to be associated with keys in ascending order, e.g., + * valueAt(0) will return the value associated with the + * smallest key and valueAt(size()-1) will return the value + * associated with the largest key.

*/ @SuppressWarnings("unchecked") public E valueAt(int index) { -- cgit v1.2.3