FileDocCategorySizeDatePackage
SparseWeakArray.javaAPI DocAndroid 5.1 API9230Thu Mar 12 22:22:44 GMT 2015com.android.layoutlib.bridge.util

SparseWeakArray

public class SparseWeakArray extends Object
This is a custom {@link SparseArray} that uses {@link WeakReference} around the objects added to it. When the array is compacted, not only deleted indices but also empty references are removed, making the array efficient at removing references that were reclaimed. The code is taken from {@link SparseArray} directly and adapted to use weak references. Because our usage means that we never actually call {@link #remove(long)} or {@link #delete(long)}, we must manually check if there are reclaimed references to trigger an internal compact step (which is normally only triggered when an item is manually removed). SparseArrays map integral values 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 (or Longs) to Objects.

Fields Summary
private static final Object
DELETED_REF
private static final WeakReference
DELETED
private boolean
mGarbage
private long[]
mKeys
private WeakReference[]
mValues
private int
mSize
Constructors Summary
public SparseWeakArray()
Creates a new SparseArray containing no mappings.


                
      
        this(10);
public SparseWeakArray(int initialCapacity)
Creates a new SparseArray containing no mappings that will not require any additional memory allocation to store the specified number of mappings.

        mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity);
        mValues = new WeakReference[mKeys.length];
        mSize = 0;
Methods Summary
public voidappend(long key, E value)
Puts a key/value pair into the array, optimizing for the case where the key is greater than all existing keys in the array.

        if (mSize != 0 && key <= mKeys[mSize - 1]) {
            put(key, value);
            return;
        }

        if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) {
            gc();
        }

        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
        mValues = GrowingArrayUtils.append(mValues, mSize, new WeakReference(value));
        mSize++;
private static intbinarySearch(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;
public voidclear()
Removes all key-value mappings from this SparseArray.

        int n = mSize;
        WeakReference<?>[] values = mValues;

        for (int i = 0; i < n; i++) {
            values[i] = null;
        }

        mSize = 0;
        mGarbage = false;
public voiddelete(long key)
Removes the mapping from the specified key, if there was any.

        int i = binarySearch(mKeys, 0, mSize, key);

        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
private voidgc()

        int n = mSize;
        int o = 0;
        long[] keys = mKeys;
        WeakReference<?>[] values = mValues;

        for (int i = 0; i < n; i++) {
            WeakReference<?> val = values[i];

            // Don't keep any non DELETED values, but only the one that still have a valid
            // reference.
            if (val != DELETED && val.get() != null) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;
public Eget(long key)
Gets the Object mapped from the specified key, or null if no such mapping has been made.

        return get(key, null);
public Eget(long key, E valueIfKeyNotFound)
Gets the Object mapped from the specified key, or the specified Object if no such mapping has been made.

        int i = binarySearch(mKeys, 0, mSize, key);

        if (i < 0 || mValues[i] == DELETED || mValues[i].get() == null) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i].get();
        }
private booleanhasReclaimedRefs()

        for (int i = 0 ; i < mSize ; i++) {
            if (mValues[i].get() == null) { // DELETED.get() never returns null.
                return true;
            }
        }

        return false;
public intindexOfKey(long key)
Returns the index for which {@link #keyAt} would return the specified key, or a negative number if the specified key is not mapped.

        if (mGarbage) {
            gc();
        }

        return binarySearch(mKeys, 0, mSize, key);
public intindexOfValue(E value)
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.

        if (mGarbage) {
            gc();
        }

        for (int i = 0; i < mSize; i++)
            if (mValues[i].get() == value)
                return i;

        return -1;
public longkeyAt(int index)
Given an index in the range 0...size()-1, returns the key from the indexth key-value mapping that this SparseArray stores.

        if (mGarbage) {
            gc();
        }

        return mKeys[index];
public voidput(long key, E value)
Adds a mapping from the specified key to the specified value, replacing the previous mapping from the specified key if there was one.

        int i = binarySearch(mKeys, 0, mSize, key);

        if (i >= 0) {
            mValues[i] = new WeakReference(value);
        } else {
            i = ~i;

            if (i < mSize && (mValues[i] == DELETED || mValues[i].get() == null)) {
                mKeys[i] = key;
                mValues[i] = new WeakReference(value);
                return;
            }

            if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) {
                gc();

                // Search again because indices may have changed.
                i = ~binarySearch(mKeys, 0, mSize, key);
            }

            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, new WeakReference(value));
            mSize++;
        }
public voidremove(long key)
Alias for {@link #delete(long)}.

        delete(key);
public voidremoveAt(int index)
Removes the mapping at the specified index.

        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
public voidsetValueAt(int index, E value)
Given an index in the range 0...size()-1, sets a new value for the indexth key-value mapping that this SparseArray stores.

        if (mGarbage) {
            gc();
        }

        mValues[index] = new WeakReference(value);
public intsize()
Returns the number of key-value mappings that this SparseArray currently stores.

        if (mGarbage) {
            gc();
        }

        return mSize;
public EvalueAt(int index)
Given an index in the range 0...size()-1, returns the value from the indexth key-value mapping that this SparseArray stores.

        if (mGarbage) {
            gc();
        }

        return (E) mValues[index].get();