1282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/* 2282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Copyright (C) 2011 The Android Open Source Project 3282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 4282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 5282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * you may not use this file except in compliance with the License. 6282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * You may obtain a copy of the License at 7282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 8282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 9282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 10282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Unless required by applicable law or agreed to in writing, software 11282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 12282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * See the License for the specific language governing permissions and 14282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * limitations under the License. 15282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 16282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 17282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskipackage com.android.layoutlib.bridge.util; 18282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 19282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 20282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiimport com.android.internal.util.ArrayUtils; 21776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport com.android.internal.util.GrowingArrayUtils; 22282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 23282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiimport android.util.SparseArray; 24282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 25282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiimport java.lang.ref.WeakReference; 26282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 27282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski/** 28282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * This is a custom {@link SparseArray} that uses {@link WeakReference} around the objects added 29282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * to it. When the array is compacted, not only deleted indices but also empty references 30282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * are removed, making the array efficient at removing references that were reclaimed. 31282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 32282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * The code is taken from {@link SparseArray} directly and adapted to use weak references. 33282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 3488a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * Because our usage means that we never actually call {@link #remove(long)} or 3588a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * {@link #delete(long)}, we must manually check if there are reclaimed references to 3688a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * trigger an internal compact step (which is normally only triggered when an item is manually 3788a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * removed). 38282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * 3988a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * SparseArrays map integral values to Objects. Unlike a normal array of Objects, 40282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * there can be gaps in the indices. It is intended to be more efficient 4188a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * than using a HashMap to map Integers (or Longs) to Objects. 42282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 43282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski@SuppressWarnings("unchecked") 44282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskipublic class SparseWeakArray<E> { 45282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 46282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private static final Object DELETED_REF = new Object(); 47282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private static final WeakReference<?> DELETED = new WeakReference(DELETED_REF); 48282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private boolean mGarbage = false; 49282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 50282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 51282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Creates a new SparseArray containing no mappings. 52282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 53282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public SparseWeakArray() { 54282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski this(10); 55282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 56282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 57282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 58282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Creates a new SparseArray containing no mappings that will not 59282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * require any additional memory allocation to store the specified 60282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * number of mappings. 61282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 62282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public SparseWeakArray(int initialCapacity) { 63776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity); 64776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = new WeakReference[mKeys.length]; 65282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mSize = 0; 66282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 67282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 68282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 69282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Gets the Object mapped from the specified key, or <code>null</code> 70282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * if no such mapping has been made. 71282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 7288a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public E get(long key) { 73282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return get(key, null); 74282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 75282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 76282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 77282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Gets the Object mapped from the specified key, or the specified Object 78282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * if no such mapping has been made. 79282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 8088a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public E get(long key, E valueIfKeyNotFound) { 81282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int i = binarySearch(mKeys, 0, mSize, key); 82282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 83282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (i < 0 || mValues[i] == DELETED || mValues[i].get() == null) { 84282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return valueIfKeyNotFound; 85282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 86282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return (E) mValues[i].get(); 87282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 88282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 89282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 90282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 91282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Removes the mapping from the specified key, if there was any. 92282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 9388a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public void delete(long key) { 94282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int i = binarySearch(mKeys, 0, mSize, key); 95282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 96282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (i >= 0) { 97282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mValues[i] != DELETED) { 98282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mValues[i] = DELETED; 99282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mGarbage = true; 100282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 101282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 102282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 103282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 104282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 10588a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath * Alias for {@link #delete(long)}. 106282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 10788a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public void remove(long key) { 108282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski delete(key); 109282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 110282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 111282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 112282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Removes the mapping at the specified index. 113282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 114282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public void removeAt(int index) { 115282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mValues[index] != DELETED) { 116282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mValues[index] = DELETED; 117282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mGarbage = true; 118282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 119282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 120282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 121282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private void gc() { 122282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int n = mSize; 123282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int o = 0; 12488a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath long[] keys = mKeys; 125282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski WeakReference<?>[] values = mValues; 126282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 127282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (int i = 0; i < n; i++) { 128282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski WeakReference<?> val = values[i]; 129282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 130282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Don't keep any non DELETED values, but only the one that still have a valid 131282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // reference. 132282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (val != DELETED && val.get() != null) { 133282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (i != o) { 134282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski keys[o] = keys[i]; 135282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski values[o] = val; 136282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 137282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 138282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski o++; 139282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 140282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 141282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 142282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mGarbage = false; 143282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mSize = o; 144282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 145282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 146282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 147282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Adds a mapping from the specified key to the specified value, 148282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * replacing the previous mapping from the specified key if there 149282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * was one. 150282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 15188a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public void put(long key, E value) { 152282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int i = binarySearch(mKeys, 0, mSize, key); 153282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 154282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (i >= 0) { 155282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mValues[i] = new WeakReference(value); 156282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } else { 157282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski i = ~i; 158282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 159282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (i < mSize && (mValues[i] == DELETED || mValues[i].get() == null)) { 160282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mKeys[i] = key; 161282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mValues[i] = new WeakReference(value); 162282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return; 163282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 164282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 165282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) { 166282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 167282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 168282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Search again because indices may have changed. 169282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski i = ~binarySearch(mKeys, 0, mSize, key); 170282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 171282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 172776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); 173776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = GrowingArrayUtils.insert(mValues, mSize, i, new WeakReference(value)); 174282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mSize++; 175282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 176282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 177282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 178282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 179282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the number of key-value mappings that this SparseArray 180282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * currently stores. 181282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 182282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public int size() { 183282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mGarbage) { 184282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 185282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 186282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 187282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return mSize; 188282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 189282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 190282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 191282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Given an index in the range <code>0...size()-1</code>, returns 192282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the key from the <code>index</code>th key-value mapping that this 193282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * SparseArray stores. 194282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 19588a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public long keyAt(int index) { 196282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mGarbage) { 197282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 198282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 199282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 200282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return mKeys[index]; 201282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 202282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 203282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 204282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Given an index in the range <code>0...size()-1</code>, returns 205282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the value from the <code>index</code>th key-value mapping that this 206282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * SparseArray stores. 207282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 208282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public E valueAt(int index) { 209282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mGarbage) { 210282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 211282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 212282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 213282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return (E) mValues[index].get(); 214282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 215282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 216282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 217282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Given an index in the range <code>0...size()-1</code>, sets a new 218282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * value for the <code>index</code>th key-value mapping that this 219282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * SparseArray stores. 220282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 221282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public void setValueAt(int index, E value) { 222282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mGarbage) { 223282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 224282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 225282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 226282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mValues[index] = new WeakReference(value); 227282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 228282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 229282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 230282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns the index for which {@link #keyAt} would return the 231282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * specified key, or a negative number if the specified 232282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * key is not mapped. 233282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 23488a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public int indexOfKey(long key) { 235282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mGarbage) { 236282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 237282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 238282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 239282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return binarySearch(mKeys, 0, mSize, key); 240282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 241282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 242282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 243282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Returns an index for which {@link #valueAt} would return the 244282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * specified key, or a negative number if no keys map to the 245282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * specified value. 246282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Beware that this is a linear search, unlike lookups by key, 247282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * and that multiple keys can map to the same value and this will 248282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * find only one of them. 249282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 250282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public int indexOfValue(E value) { 251282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mGarbage) { 252282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 253282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 254282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 255282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (int i = 0; i < mSize; i++) 256282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mValues[i].get() == value) 257282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return i; 258282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 259282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return -1; 260282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 261282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 262282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 263282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Removes all key-value mappings from this SparseArray. 264282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 265282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public void clear() { 266282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int n = mSize; 267282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski WeakReference<?>[] values = mValues; 268282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 269282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (int i = 0; i < n; i++) { 270282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski values[i] = null; 271282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 272282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 273282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mSize = 0; 274282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mGarbage = false; 275282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 276282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 277282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /** 278282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * Puts a key/value pair into the array, optimizing for the case where 279282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski * the key is greater than all existing keys in the array. 280282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski */ 28188a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath public void append(long key, E value) { 282282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mSize != 0 && key <= mKeys[mSize - 1]) { 283282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski put(key, value); 284282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return; 285282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 286282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 287282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) { 288282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski gc(); 289282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 290282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 291776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = GrowingArrayUtils.append(mKeys, mSize, key); 292776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = GrowingArrayUtils.append(mValues, mSize, new WeakReference(value)); 293776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mSize++; 294282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 295282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 296282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private boolean hasReclaimedRefs() { 297282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski for (int i = 0 ; i < mSize ; i++) { 298282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mValues[i].get() == null) { // DELETED.get() never returns null. 299282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return true; 300282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 301282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 302282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 303282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return false; 304282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 305282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 30688a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath private static int binarySearch(long[] a, int start, int len, long key) { 307282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int high = start + len, low = start - 1, guess; 308282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 309282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (high - low > 1) { 310282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski guess = (high + low) / 2; 311282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 312282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (a[guess] < key) 313282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski low = guess; 314282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski else 315282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski high = guess; 316282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 317282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 318282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (high == start + len) 319282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return ~(start + len); 320282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski else if (a[high] == key) 321282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return high; 322282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski else 323282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return ~high; 324282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 325282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 32688a8364c386c694f7ad56662ef89713dbf7c9d63Narayan Kamath private long[] mKeys; 327282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private WeakReference<?>[] mValues; 328282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski private int mSize; 329282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 330