FileDocCategorySizeDatePackage
SimpleArrayMap.javaAPI DocAndroid 5.1 API20594Thu Mar 12 22:22:56 GMT 2015android.support.v4.util

SimpleArrayMap

public class SimpleArrayMap extends Object
Base implementation of {@link ArrayMap} that doesn't include any standard Java container API interoperability. These features are generally heavier-weight ways to interact with the container, so discouraged, but they can be useful to make it easier to use as a drop-in replacement for HashMap. If you don't need them, this class can be preferrable since it doesn't bring in any of the implementation of those APIs, allowing that code to be stripped by ProGuard.

Fields Summary
private static final boolean
DEBUG
private static final String
TAG
private static final int
BASE_SIZE
The minimum amount by which the capacity of a ArrayMap will increase. This is tuned to be relatively space-efficient.
private static final int
CACHE_SIZE
Maximum number of entries to have in array caches.
static Object[]
mBaseCache
Caches of small array objects to avoid spamming garbage. The cache Object[] variable is a pointer to a linked list of array objects. The first entry in the array is a pointer to the next array in the list; the second entry is a pointer to the int[] hash code array for it.
static int
mBaseCacheSize
static Object[]
mTwiceBaseCache
static int
mTwiceBaseCacheSize
int[]
mHashes
Object[]
mArray
int
mSize
Constructors Summary
public SimpleArrayMap()
Create a new empty ArrayMap. The default capacity of an array map is 0, and will grow once items are added to it.

        mHashes = ContainerHelpers.EMPTY_INTS;
        mArray = ContainerHelpers.EMPTY_OBJECTS;
        mSize = 0;
public SimpleArrayMap(int capacity)
Create a new ArrayMap with a given initial capacity.

        if (capacity == 0) {
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
public SimpleArrayMap(SimpleArrayMap map)
Create a new ArrayMap with the mappings from the given ArrayMap.

        this();
        if (map != null) {
            putAll(map);
        }
Methods Summary
private voidallocArrays(int size)

        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCache != null) {
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
                            + " now have " + mTwiceBaseCacheSize + " entries");
                    return;
                }
            }
        } else if (size == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCache != null) {
                    final Object[] array = mBaseCache;
                    mArray = array;
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                    return;
                }
            }
        }

        mHashes = new int[size];
        mArray = new Object[size<<1];
public voidclear()
Make the array map empty. All storage is released.

        if (mSize != 0) {
            freeArrays(mHashes, mArray, mSize);
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
            mSize = 0;
        }
public booleancontainsKey(java.lang.Object key)
Check whether a key exists in the array.

param
key The key to search for.
return
Returns true if the key exists, else false.

        return indexOfKey(key) >= 0;
public booleancontainsValue(java.lang.Object value)
Check whether a value exists in the array. This requires a linear search through the entire array.

param
value The value to search for.
return
Returns true if the value exists, else false.

        return indexOfValue(value) >= 0;
public voidensureCapacity(int minimumCapacity)
Ensure the array map can hold at least minimumCapacity items.

        if (mHashes.length < minimumCapacity) {
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(minimumCapacity);
            if (mSize > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, mSize);
                System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
            }
            freeArrays(ohashes, oarray, mSize);
        }
public booleanequals(java.lang.Object object)
{@inheritDoc}

This implementation returns false if the object is not a map, or if the maps have different sizes. Otherwise, for each key in this map, values of both maps are compared. If the values for any key are not equal, the method returns false, otherwise it returns true.

        if (this == object) {
            return true;
        }
        if (object instanceof Map) {
            Map<?, ?> map = (Map<?, ?>) object;
            if (size() != map.size()) {
                return false;
            }

            try {
                for (int i=0; i<mSize; i++) {
                    K key = keyAt(i);
                    V mine = valueAt(i);
                    Object theirs = map.get(key);
                    if (mine == null) {
                        if (theirs != null || !map.containsKey(key)) {
                            return false;
                        }
                    } else if (!mine.equals(theirs)) {
                        return false;
                    }
                }
            } catch (NullPointerException ignored) {
                return false;
            } catch (ClassCastException ignored) {
                return false;
            }
            return true;
        }
        return false;
private static voidfreeArrays(int[] hashes, java.lang.Object[] array, int size)

        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                    if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
                            + " now have " + mTwiceBaseCacheSize + " entries");
                }
            }
        } else if (hashes.length == BASE_SIZE) {
            synchronized (ArrayMap.class) {
                if (mBaseCacheSize < CACHE_SIZE) {
                    array[0] = mBaseCache;
                    array[1] = hashes;
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    mBaseCache = array;
                    mBaseCacheSize++;
                    if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
                            + " now have " + mBaseCacheSize + " entries");
                }
            }
        }
public Vget(java.lang.Object key)
Retrieve a value from the array.

param
key The key of the value to retrieve.
return
Returns the value associated with the given key, or null if there is no such key.

        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
public inthashCode()
{@inheritDoc}

        final int[] hashes = mHashes;
        final Object[] array = mArray;
        int result = 0;
        for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) {
            Object value = array[v];
            result += hashes[i] ^ (value == null ? 0 : value.hashCode());
        }
        return result;
intindexOf(java.lang.Object key, int hash)


         
        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }

        int index = ContainerHelpers.binarySearch(mHashes, N, hash);

        // If the hash code wasn't found, then we have no entry for this key.
        if (index < 0) {
            return index;
        }

        // If the key at the returned index matches, that's what we want.
        if (key.equals(mArray[index<<1])) {
            return index;
        }

        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            if (key.equals(mArray[end << 1])) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            if (key.equals(mArray[i << 1])) return i;
        }

        // Key not found -- return negative value indicating where a
        // new entry for this key should go.  We use the end of the
        // hash chain to reduce the number of array entries that will
        // need to be copied when inserting.
        return ~end;
public intindexOfKey(java.lang.Object key)
Returns the index of a key in the set.

param
key The key to search for.
return
Returns the index of the key if it exists, else a negative integer.

        return key == null ? indexOfNull() : indexOf(key, key.hashCode());
intindexOfNull()

        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }

        int index = ContainerHelpers.binarySearch(mHashes, N, 0);

        // If the hash code wasn't found, then we have no entry for this key.
        if (index < 0) {
            return index;
        }

        // If the key at the returned index matches, that's what we want.
        if (null == mArray[index<<1]) {
            return index;
        }

        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == 0; end++) {
            if (null == mArray[end << 1]) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
            if (null == mArray[i << 1]) return i;
        }

        // Key not found -- return negative value indicating where a
        // new entry for this key should go.  We use the end of the
        // hash chain to reduce the number of array entries that will
        // need to be copied when inserting.
        return ~end;
intindexOfValue(java.lang.Object value)

        final int N = mSize*2;
        final Object[] array = mArray;
        if (value == null) {
            for (int i=1; i<N; i+=2) {
                if (array[i] == null) {
                    return i>>1;
                }
            }
        } else {
            for (int i=1; i<N; i+=2) {
                if (value.equals(array[i])) {
                    return i>>1;
                }
            }
        }
        return -1;
public booleanisEmpty()
Return true if the array map contains no items.

        return mSize <= 0;
public KkeyAt(int index)
Return the key at the given index in the array.

param
index The desired index, must be between 0 and {@link #size()}-1.
return
Returns the key stored at the given index.

        return (K)mArray[index << 1];
public Vput(K key, V value)
Add a new value to the array map.

param
key The key under which to store the value. Must not be null. If this key already exists in the array, its value will be replaced.
param
value The value to store for the given key.
return
Returns the old value that was stored for the given key, or null if there was no such key.

        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            hash = key.hashCode();
            index = indexOf(key, hash);
        }
        if (index >= 0) {
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }

        index = ~index;
        if (mSize >= mHashes.length) {
            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n);

            if (mHashes.length > 0) {
                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }

            freeArrays(ohashes, oarray, mSize);
        }

        if (index < mSize) {
            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }

        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
public voidputAll(android.support.v4.util.SimpleArrayMap array)
Perform a {@link #put(Object, Object)} of all key/value pairs in array

param
array The array whose contents are to be retrieved.

        final int N = array.mSize;
        ensureCapacity(mSize + N);
        if (mSize == 0) {
            if (N > 0) {
                System.arraycopy(array.mHashes, 0, mHashes, 0, N);
                System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
                mSize = N;
            }
        } else {
            for (int i=0; i<N; i++) {
                put(array.keyAt(i), array.valueAt(i));
            }
        }
public Vremove(java.lang.Object key)
Remove an existing key from the array map.

param
key The key of the mapping to remove.
return
Returns the value that was stored under the key, or null if there was no such key.

        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }

        return null;
public VremoveAt(int index)
Remove the key/value mapping at the given index.

param
index The desired index, must be between 0 and {@link #size()}-1.
return
Returns the value that was stored at this index.

        final Object old = mArray[(index << 1) + 1];
        if (mSize <= 1) {
            // Now empty.
            if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
            freeArrays(mHashes, mArray, mSize);
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
            mSize = 0;
        } else {
            if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
                // Shrunk enough to reduce size of arrays.  We don't allow it to
                // shrink smaller than (BASE_SIZE*2) to avoid flapping between
                // that and BASE_SIZE.
                final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);

                if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);

                final int[] ohashes = mHashes;
                final Object[] oarray = mArray;
                allocArrays(n);

                mSize--;
                if (index > 0) {
                    if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
                    System.arraycopy(ohashes, 0, mHashes, 0, index);
                    System.arraycopy(oarray, 0, mArray, 0, index << 1);
                }
                if (index < mSize) {
                    if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
                            + " to " + index);
                    System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
            } else {
                mSize--;
                if (index < mSize) {
                    if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
                            + " to " + index);
                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
                mArray[mSize << 1] = null;
                mArray[(mSize << 1) + 1] = null;
            }
        }
        return (V)old;
public VsetValueAt(int index, V value)
Set the value at a given index in the array.

param
index The desired index, must be between 0 and {@link #size()}-1.
param
value The new value to store at this index.
return
Returns the previous value at the given index.

        index = (index << 1) + 1;
        V old = (V)mArray[index];
        mArray[index] = value;
        return old;
public intsize()
Return the number of items in this array map.

        return mSize;
public java.lang.StringtoString()
{@inheritDoc}

This implementation composes a string by iterating over its mappings. If this map contains itself as a key or a value, the string "(this Map)" will appear in its place.

        if (isEmpty()) {
            return "{}";
        }

        StringBuilder buffer = new StringBuilder(mSize * 28);
        buffer.append('{");
        for (int i=0; i<mSize; i++) {
            if (i > 0) {
                buffer.append(", ");
            }
            Object key = keyAt(i);
            if (key != this) {
                buffer.append(key);
            } else {
                buffer.append("(this Map)");
            }
            buffer.append('=");
            Object value = valueAt(i);
            if (value != this) {
                buffer.append(value);
            } else {
                buffer.append("(this Map)");
            }
        }
        buffer.append('}");
        return buffer.toString();
public VvalueAt(int index)
Return the value at the given index in the array.

param
index The desired index, must be between 0 and {@link #size()}-1.
return
Returns the value stored at the given index.

        return (V)mArray[(index << 1) + 1];