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

3 files changed, 518 insertions, 1 deletions

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);
+        }
+    }
 }