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
diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java
index 7e8fee5..001fc5b 100644
--- a/core/java/android/util/SparseArray.java
+++ b/core/java/android/util/SparseArray.java
@@ -25,6 +25,8 @@
*/
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 @@
/**
* 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 @@
*/
@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 @@
* 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 @@
* 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 @@
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 @@
gc();
}
- return binarySearch(mKeys, 0, mSize, key);
+ return binarySearch(mKeys, mSize, key);
}
/**
@@ -335,23 +343,23 @@
mSize = pos + 1;
}
- private static int binarySearch(int[] a, int start, int len, int key) {
- int high = start + len, low = start - 1, 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 (high - low > 1) {
- guess = (high + low) / 2;
+ while (lo <= hi) {
+ int mid = (lo + hi) >>> 1;
+ int midVal = array[mid];
- if (a[guess] < key)
- low = guess;
- else
- high = guess;
+ 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
}
}