Fixes #1922373. Resolves a case of keys collision in Resources' cache.

The Resources class keeps a cache of known resources. The keys used by the
cache are stored as int primitives. For any given drawable resource, a key
is built thusly:

TypeValue.assetCookie << 24 | TypedValue.data

In the case of a plain color drawable, assetCookie always equals -1, that
is 0xFF once right-shifted and the data contains the color value. Which
means the key for the following two colors is the same:

0xFF000000
0x00000000

Because of the int storage and the use of the (constant in this case)
asset cookie, the alpha channel of a color is ignored. That means that
if you first load an opaque black color (0xFF000000), subsequent loads
of a totally transparent black color (0x00000000) will give you an
opaque black color.

A workaround is to use a transparent color that is not black,
0x00000001 for instance. Note that this issue would arise with any color
and any opacity level.

The solution to fix this issue is simply to change the cache to use
longs instead of ints to represent the keys. A key thus becomes:

TypedValue.assetCookie << 32 | TypedValue.data

This allows us correct storage of all colors at the cost of a few bytes.
The tradeoff is that we can keep caching ColorDrawable, which is
definitely worth it.

1 files changed, 342 insertions, 0 deletions

diff --git a/core/java/android/util/LongSparseArray.java b/core/java/android/util/LongSparseArray.java
new file mode 100644
index 0000000..d90045f
--- /dev/null
+++ b/core/java/android/util/LongSparseArray.java
@@ -0,0 +1,342 @@
+/*
+ * Copyright (C) 2009 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 com.android.internal.util.ArrayUtils;
+
+/**
+ * SparseArrays map longs 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 Longs to Objects.
+ *
+ * @hide
+ */
+public class LongSparseArray<E> {
+    private static final Object DELETED = new Object();
+    private boolean mGarbage = false;
+
+    /**
+     * Creates a new SparseArray containing no mappings.
+     */
+    public LongSparseArray() {
+        this(10);
+    }
+
+    /**
+     * Creates a new SparseArray containing no mappings that will not
+     * require any additional memory allocation to store the specified
+     * number of mappings.
+     */
+    public LongSparseArray(int initialCapacity) {
+        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
+
+        mKeys = new long[initialCapacity];
+        mValues = new Object[initialCapacity];
+        mSize = 0;
+    }
+
+    /**
+     * Gets the Object mapped from the specified key, or <code>null</code>
+     * if no such mapping has been made.
+     */
+    public E get(long key) {
+        return get(key, null);
+    }
+
+    /**
+     * Gets the Object mapped from the specified key, or the specified Object
+     * if no such mapping has been made.
+     */
+    public E get(long key, E valueIfKeyNotFound) {
+        int i = binarySearch(mKeys, 0, mSize, key);
+
+        if (i < 0 || mValues[i] == DELETED) {
+            return valueIfKeyNotFound;
+        } else {
+            return (E) mValues[i];
+        }
+    }
+
+    /**
+     * Removes the mapping from the specified key, if there was any.
+     */
+    public void delete(long key) {
+        int i = binarySearch(mKeys, 0, mSize, key);
+
+        if (i >= 0) {
+            if (mValues[i] != DELETED) {
+                mValues[i] = DELETED;
+                mGarbage = true;
+            }
+        }
+    }
+
+    /**
+     * Alias for {@link #delete(long)}.
+     */
+    public void remove(long key) {
+        delete(key);
+    }
+
+    private void gc() {
+        // Log.e("SparseArray", "gc start with " + mSize);
+
+        int n = mSize;
+        int o = 0;
+        long[] keys = mKeys;
+        Object[] values = mValues;
+
+        for (int i = 0; i < n; i++) {
+            Object val = values[i];
+
+            if (val != DELETED) {
+                if (i != o) {
+                    keys[o] = keys[i];
+                    values[o] = val;
+                }
+
+                o++;
+            }
+        }
+
+        mGarbage = false;
+        mSize = o;
+
+        // Log.e("SparseArray", "gc end with " + mSize);
+    }
+
+    /**
+     * Adds a mapping from the specified key to the specified value,
+     * replacing the previous mapping from the specified key if there
+     * was one.
+     */
+    public void put(long key, E value) {
+        int i = binarySearch(mKeys, 0, mSize, key);
+
+        if (i >= 0) {
+            mValues[i] = value;
+        } else {
+            i = ~i;
+
+            if (i < mSize && mValues[i] == DELETED) {
+                mKeys[i] = key;
+                mValues[i] = value;
+                return;
+            }
+
+            if (mGarbage && mSize >= mKeys.length) {
+                gc();
+
+                // Search again because indices may have changed.
+                i = ~binarySearch(mKeys, 0, mSize, key);
+            }
+
+            if (mSize >= mKeys.length) {
+                int n = ArrayUtils.idealIntArraySize(mSize + 1);
+
+                long[] nkeys = new long[n];
+                Object[] nvalues = new Object[n];
+
+                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
+                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
+                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
+
+                mKeys = nkeys;
+                mValues = nvalues;
+            }
+
+            if (mSize - i != 0) {
+                // Log.e("SparseArray", "move " + (mSize - i));
+                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
+                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
+            }
+
+            mKeys[i] = key;
+            mValues[i] = value;
+            mSize++;
+        }
+    }
+
+    /**
+     * Returns the number of key-value mappings that this SparseArray
+     * currently stores.
+     */
+    public int size() {
+        if (mGarbage) {
+            gc();
+        }
+
+        return mSize;
+    }
+
+    /**
+     * Given an index in the range <code>0...size()-1</code>, returns
+     * the key from the <code>index</code>th key-value mapping that this
+     * SparseArray stores.
+     */
+    public long keyAt(int index) {
+        if (mGarbage) {
+            gc();
+        }
+
+        return mKeys[index];
+    }
+
+    /**
+     * Given an index in the range <code>0...size()-1</code>, returns
+     * the value from the <code>index</code>th key-value mapping that this
+     * SparseArray stores.
+     */
+    public E valueAt(int index) {
+        if (mGarbage) {
+            gc();
+        }
+
+        return (E) mValues[index];
+    }
+
+    /**
+     * Given an index in the range <code>0...size()-1</code>, sets a new
+     * value for the <code>index</code>th key-value mapping that this
+     * SparseArray stores.
+     */
+    public void setValueAt(int index, E value) {
+        if (mGarbage) {
+            gc();
+        }
+
+        mValues[index] = value;
+    }
+
+    /**
+     * Returns the index for which {@link #keyAt} would return the
+     * specified key, or a negative number if the specified
+     * key is not mapped.
+     */
+    public int indexOfKey(long key) {
+        if (mGarbage) {
+            gc();
+        }
+
+        return binarySearch(mKeys, 0, mSize, key);
+    }
+
+    /**
+     * Returns an index for which {@link #valueAt} would return the
+     * specified key, or a negative number if no keys map to the
+     * specified value.
+     * Beware that this is a linear search, unlike lookups by key,
+     * and that multiple keys can map to the same value and this will
+     * find only one of them.
+     */
+    public int indexOfValue(E value) {
+        if (mGarbage) {
+            gc();
+        }
+
+        for (int i = 0; i < mSize; i++)
+            if (mValues[i] == value)
+                return i;
+
+        return -1;
+    }
+
+    /**
+     * Removes all key-value mappings from this SparseArray.
+     */
+    public void clear() {
+        int n = mSize;
+        Object[] values = mValues;
+
+        for (int i = 0; i < n; i++) {
+            values[i] = null;
+        }
+
+        mSize = 0;
+        mGarbage = false;
+    }
+
+    /**
+     * Puts a key/value pair into the array, optimizing for the case where
+     * the key is greater than all existing keys in the array.
+     */
+    public void append(long key, E value) {
+        if (mSize != 0 && key <= mKeys[mSize - 1]) {
+            put(key, value);
+            return;
+        }
+
+        if (mGarbage && mSize >= mKeys.length) {
+            gc();
+        }
+
+        int pos = mSize;
+        if (pos >= mKeys.length) {
+            int n = ArrayUtils.idealIntArraySize(pos + 1);
+
+            long[] nkeys = new long[n];
+            Object[] nvalues = new Object[n];
+
+            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
+            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
+            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
+
+            mKeys = nkeys;
+            mValues = nvalues;
+        }
+
+        mKeys[pos] = key;
+        mValues[pos] = value;
+        mSize = pos + 1;
+    }
+
+    private static int binarySearch(long[] 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;
+    }
+
+    private void checkIntegrity() {
+        for (int i = 1; i < mSize; i++) {
+            if (mKeys[i] <= mKeys[i - 1]) {
+                for (int j = 0; j < mSize; j++) {
+                    Log.e("FAIL", j + ": " + mKeys[j] + " -> " + mValues[j]);
+                }
+
+                throw new RuntimeException();
+            }
+        }
+    }
+
+    private long[] mKeys;
+    private Object[] mValues;
+    private int mSize;
+}
\ No newline at end of file