SparseWeakArray.java revision cc4977d0fdaf657907912fd6cc2f9426dc8d2e36
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.android.layoutlib.bridge.util; 18 19 20import com.android.internal.util.ArrayUtils; 21 22import android.util.SparseArray; 23 24import java.lang.ref.WeakReference; 25 26/** 27 * This is a custom {@link SparseArray} that uses {@link WeakReference} around the objects added 28 * to it. When the array is compacted, not only deleted indices but also empty references 29 * are removed, making the array efficient at removing references that were reclaimed. 30 * 31 * The code is taken from {@link SparseArray} directly and adapted to use weak references. 32 * 33 * Because our usage means that we never actually call {@link #remove(int)} or {@link #delete(int)}, 34 * we must manually check if there are reclaimed references to trigger an internal compact step 35 * (which is normally only triggered when an item is manually removed). 36 * 37 * SparseArrays map integers to Objects. Unlike a normal array of Objects, 38 * there can be gaps in the indices. It is intended to be more efficient 39 * than using a HashMap to map Integers to Objects. 40 */ 41@SuppressWarnings("unchecked") 42public class SparseWeakArray<E> { 43 44 private static final Object DELETED_REF = new Object(); 45 private static final WeakReference<?> DELETED = new WeakReference(DELETED_REF); 46 private boolean mGarbage = false; 47 48 /** 49 * Creates a new SparseArray containing no mappings. 50 */ 51 public SparseWeakArray() { 52 this(10); 53 } 54 55 /** 56 * Creates a new SparseArray containing no mappings that will not 57 * require any additional memory allocation to store the specified 58 * number of mappings. 59 */ 60 public SparseWeakArray(int initialCapacity) { 61 initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); 62 63 mKeys = new int[initialCapacity]; 64 mValues = new WeakReference[initialCapacity]; 65 mSize = 0; 66 } 67 68 /** 69 * Gets the Object mapped from the specified key, or <code>null</code> 70 * if no such mapping has been made. 71 */ 72 public E get(int key) { 73 return get(key, null); 74 } 75 76 /** 77 * Gets the Object mapped from the specified key, or the specified Object 78 * if no such mapping has been made. 79 */ 80 public E get(int key, E valueIfKeyNotFound) { 81 int i = binarySearch(mKeys, 0, mSize, key); 82 83 if (i < 0 || mValues[i] == DELETED || mValues[i].get() == null) { 84 return valueIfKeyNotFound; 85 } else { 86 return (E) mValues[i].get(); 87 } 88 } 89 90 /** 91 * Removes the mapping from the specified key, if there was any. 92 */ 93 public void delete(int key) { 94 int i = binarySearch(mKeys, 0, mSize, key); 95 96 if (i >= 0) { 97 if (mValues[i] != DELETED) { 98 mValues[i] = DELETED; 99 mGarbage = true; 100 } 101 } 102 } 103 104 /** 105 * Alias for {@link #delete(int)}. 106 */ 107 public void remove(int key) { 108 delete(key); 109 } 110 111 /** 112 * Removes the mapping at the specified index. 113 */ 114 public void removeAt(int index) { 115 if (mValues[index] != DELETED) { 116 mValues[index] = DELETED; 117 mGarbage = true; 118 } 119 } 120 121 private void gc() { 122 // Log.e("SparseArray", "gc start with " + mSize); 123 124 int n = mSize; 125 int o = 0; 126 int[] keys = mKeys; 127 WeakReference<?>[] values = mValues; 128 129 for (int i = 0; i < n; i++) { 130 WeakReference<?> val = values[i]; 131 132 // Don't keep any non DELETED values, but only the one that still have a valid 133 // reference. 134 if (val != DELETED && val.get() != null) { 135 if (i != o) { 136 keys[o] = keys[i]; 137 values[o] = val; 138 } 139 140 o++; 141 } 142 } 143 144 mGarbage = false; 145 mSize = o; 146 147 // Log.e("SparseArray", "gc end with " + mSize); 148 } 149 150 /** 151 * Adds a mapping from the specified key to the specified value, 152 * replacing the previous mapping from the specified key if there 153 * was one. 154 */ 155 public void put(int key, E value) { 156 int i = binarySearch(mKeys, 0, mSize, key); 157 158 if (i >= 0) { 159 mValues[i] = new WeakReference(value); 160 } else { 161 i = ~i; 162 163 if (i < mSize && (mValues[i] == DELETED || mValues[i].get() == null)) { 164 mKeys[i] = key; 165 mValues[i] = new WeakReference(value); 166 return; 167 } 168 169 if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) { 170 gc(); 171 172 // Search again because indices may have changed. 173 i = ~binarySearch(mKeys, 0, mSize, key); 174 } 175 176 if (mSize >= mKeys.length) { 177 int n = ArrayUtils.idealIntArraySize(mSize + 1); 178 179 int[] nkeys = new int[n]; 180 WeakReference<?>[] nvalues = new WeakReference[n]; 181 182 // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 183 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 184 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 185 186 mKeys = nkeys; 187 mValues = nvalues; 188 } 189 190 if (mSize - i != 0) { 191 // Log.e("SparseArray", "move " + (mSize - i)); 192 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 193 System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 194 } 195 196 mKeys[i] = key; 197 mValues[i] = new WeakReference(value); 198 mSize++; 199 } 200 } 201 202 /** 203 * Returns the number of key-value mappings that this SparseArray 204 * currently stores. 205 */ 206 public int size() { 207 if (mGarbage) { 208 gc(); 209 } 210 211 return mSize; 212 } 213 214 /** 215 * Given an index in the range <code>0...size()-1</code>, returns 216 * the key from the <code>index</code>th key-value mapping that this 217 * SparseArray stores. 218 */ 219 public int keyAt(int index) { 220 if (mGarbage) { 221 gc(); 222 } 223 224 return mKeys[index]; 225 } 226 227 /** 228 * Given an index in the range <code>0...size()-1</code>, returns 229 * the value from the <code>index</code>th key-value mapping that this 230 * SparseArray stores. 231 */ 232 public E valueAt(int index) { 233 if (mGarbage) { 234 gc(); 235 } 236 237 return (E) mValues[index].get(); 238 } 239 240 /** 241 * Given an index in the range <code>0...size()-1</code>, sets a new 242 * value for the <code>index</code>th key-value mapping that this 243 * SparseArray stores. 244 */ 245 public void setValueAt(int index, E value) { 246 if (mGarbage) { 247 gc(); 248 } 249 250 mValues[index] = new WeakReference(value); 251 } 252 253 /** 254 * Returns the index for which {@link #keyAt} would return the 255 * specified key, or a negative number if the specified 256 * key is not mapped. 257 */ 258 public int indexOfKey(int key) { 259 if (mGarbage) { 260 gc(); 261 } 262 263 return binarySearch(mKeys, 0, mSize, key); 264 } 265 266 /** 267 * Returns an index for which {@link #valueAt} would return the 268 * specified key, or a negative number if no keys map to the 269 * specified value. 270 * Beware that this is a linear search, unlike lookups by key, 271 * and that multiple keys can map to the same value and this will 272 * find only one of them. 273 */ 274 public int indexOfValue(E value) { 275 if (mGarbage) { 276 gc(); 277 } 278 279 for (int i = 0; i < mSize; i++) 280 if (mValues[i].get() == value) 281 return i; 282 283 return -1; 284 } 285 286 /** 287 * Removes all key-value mappings from this SparseArray. 288 */ 289 public void clear() { 290 int n = mSize; 291 WeakReference<?>[] values = mValues; 292 293 for (int i = 0; i < n; i++) { 294 values[i] = null; 295 } 296 297 mSize = 0; 298 mGarbage = false; 299 } 300 301 /** 302 * Puts a key/value pair into the array, optimizing for the case where 303 * the key is greater than all existing keys in the array. 304 */ 305 public void append(int key, E value) { 306 if (mSize != 0 && key <= mKeys[mSize - 1]) { 307 put(key, value); 308 return; 309 } 310 311 if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) { 312 gc(); 313 } 314 315 int pos = mSize; 316 if (pos >= mKeys.length) { 317 int n = ArrayUtils.idealIntArraySize(pos + 1); 318 319 int[] nkeys = new int[n]; 320 WeakReference<?>[] nvalues = new WeakReference[n]; 321 322 // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 323 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 324 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 325 326 mKeys = nkeys; 327 mValues = nvalues; 328 } 329 330 mKeys[pos] = key; 331 mValues[pos] = new WeakReference(value); 332 mSize = pos + 1; 333 } 334 335 private boolean hasReclaimedRefs() { 336 for (int i = 0 ; i < mSize ; i++) { 337 if (mValues[i].get() == null) { // DELETED.get() never returns null. 338 return true; 339 } 340 } 341 342 return false; 343 } 344 345 private static int binarySearch(int[] a, int start, int len, int key) { 346 int high = start + len, low = start - 1, guess; 347 348 while (high - low > 1) { 349 guess = (high + low) / 2; 350 351 if (a[guess] < key) 352 low = guess; 353 else 354 high = guess; 355 } 356 357 if (high == start + len) 358 return ~(start + len); 359 else if (a[high] == key) 360 return high; 361 else 362 return ~high; 363 } 364 365 private int[] mKeys; 366 private WeakReference<?>[] mValues; 367 private int mSize; 368} 369