SparseWeakArray.java revision 88a8364c386c694f7ad56662ef89713dbf7c9d63
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(long)} or 34 * {@link #delete(long)}, we must manually check if there are reclaimed references to 35 * trigger an internal compact step (which is normally only triggered when an item is manually 36 * removed). 37 * 38 * SparseArrays map integral values to Objects. Unlike a normal array of Objects, 39 * there can be gaps in the indices. It is intended to be more efficient 40 * than using a HashMap to map Integers (or Longs) to Objects. 41 */ 42@SuppressWarnings("unchecked") 43public class SparseWeakArray<E> { 44 45 private static final Object DELETED_REF = new Object(); 46 private static final WeakReference<?> DELETED = new WeakReference(DELETED_REF); 47 private boolean mGarbage = false; 48 49 /** 50 * Creates a new SparseArray containing no mappings. 51 */ 52 public SparseWeakArray() { 53 this(10); 54 } 55 56 /** 57 * Creates a new SparseArray containing no mappings that will not 58 * require any additional memory allocation to store the specified 59 * number of mappings. 60 */ 61 public SparseWeakArray(int initialCapacity) { 62 initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); 63 64 mKeys = new long[initialCapacity]; 65 mValues = new WeakReference[initialCapacity]; 66 mSize = 0; 67 } 68 69 /** 70 * Gets the Object mapped from the specified key, or <code>null</code> 71 * if no such mapping has been made. 72 */ 73 public E get(long key) { 74 return get(key, null); 75 } 76 77 /** 78 * Gets the Object mapped from the specified key, or the specified Object 79 * if no such mapping has been made. 80 */ 81 public E get(long key, E valueIfKeyNotFound) { 82 int i = binarySearch(mKeys, 0, mSize, key); 83 84 if (i < 0 || mValues[i] == DELETED || mValues[i].get() == null) { 85 return valueIfKeyNotFound; 86 } else { 87 return (E) mValues[i].get(); 88 } 89 } 90 91 /** 92 * Removes the mapping from the specified key, if there was any. 93 */ 94 public void delete(long key) { 95 int i = binarySearch(mKeys, 0, mSize, key); 96 97 if (i >= 0) { 98 if (mValues[i] != DELETED) { 99 mValues[i] = DELETED; 100 mGarbage = true; 101 } 102 } 103 } 104 105 /** 106 * Alias for {@link #delete(long)}. 107 */ 108 public void remove(long key) { 109 delete(key); 110 } 111 112 /** 113 * Removes the mapping at the specified index. 114 */ 115 public void removeAt(int index) { 116 if (mValues[index] != DELETED) { 117 mValues[index] = DELETED; 118 mGarbage = true; 119 } 120 } 121 122 private void gc() { 123 int n = mSize; 124 int o = 0; 125 long[] keys = mKeys; 126 WeakReference<?>[] values = mValues; 127 128 for (int i = 0; i < n; i++) { 129 WeakReference<?> val = values[i]; 130 131 // Don't keep any non DELETED values, but only the one that still have a valid 132 // reference. 133 if (val != DELETED && val.get() != null) { 134 if (i != o) { 135 keys[o] = keys[i]; 136 values[o] = val; 137 } 138 139 o++; 140 } 141 } 142 143 mGarbage = false; 144 mSize = o; 145 146 int newSize = ArrayUtils.idealLongArraySize(mSize); 147 if (newSize < mKeys.length) { 148 long[] nkeys = new long[newSize]; 149 WeakReference<?>[] nvalues = new WeakReference[newSize]; 150 151 System.arraycopy(mKeys, 0, nkeys, 0, newSize); 152 System.arraycopy(mValues, 0, nvalues, 0, newSize); 153 154 mKeys = nkeys; 155 mValues = nvalues; 156 } 157 } 158 159 /** 160 * Adds a mapping from the specified key to the specified value, 161 * replacing the previous mapping from the specified key if there 162 * was one. 163 */ 164 public void put(long key, E value) { 165 int i = binarySearch(mKeys, 0, mSize, key); 166 167 if (i >= 0) { 168 mValues[i] = new WeakReference(value); 169 } else { 170 i = ~i; 171 172 if (i < mSize && (mValues[i] == DELETED || mValues[i].get() == null)) { 173 mKeys[i] = key; 174 mValues[i] = new WeakReference(value); 175 return; 176 } 177 178 if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) { 179 gc(); 180 181 // Search again because indices may have changed. 182 i = ~binarySearch(mKeys, 0, mSize, key); 183 } 184 185 if (mSize >= mKeys.length) { 186 int n = ArrayUtils.idealLongArraySize(mSize + 1); 187 188 long[] nkeys = new long[n]; 189 WeakReference<?>[] nvalues = new WeakReference[n]; 190 191 // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 192 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 193 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 194 195 mKeys = nkeys; 196 mValues = nvalues; 197 } 198 199 if (mSize - i != 0) { 200 // Log.e("SparseArray", "move " + (mSize - i)); 201 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 202 System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 203 } 204 205 mKeys[i] = key; 206 mValues[i] = new WeakReference(value); 207 mSize++; 208 } 209 } 210 211 /** 212 * Returns the number of key-value mappings that this SparseArray 213 * currently stores. 214 */ 215 public int size() { 216 if (mGarbage) { 217 gc(); 218 } 219 220 return mSize; 221 } 222 223 /** 224 * Given an index in the range <code>0...size()-1</code>, returns 225 * the key from the <code>index</code>th key-value mapping that this 226 * SparseArray stores. 227 */ 228 public long keyAt(int index) { 229 if (mGarbage) { 230 gc(); 231 } 232 233 return mKeys[index]; 234 } 235 236 /** 237 * Given an index in the range <code>0...size()-1</code>, returns 238 * the value from the <code>index</code>th key-value mapping that this 239 * SparseArray stores. 240 */ 241 public E valueAt(int index) { 242 if (mGarbage) { 243 gc(); 244 } 245 246 return (E) mValues[index].get(); 247 } 248 249 /** 250 * Given an index in the range <code>0...size()-1</code>, sets a new 251 * value for the <code>index</code>th key-value mapping that this 252 * SparseArray stores. 253 */ 254 public void setValueAt(int index, E value) { 255 if (mGarbage) { 256 gc(); 257 } 258 259 mValues[index] = new WeakReference(value); 260 } 261 262 /** 263 * Returns the index for which {@link #keyAt} would return the 264 * specified key, or a negative number if the specified 265 * key is not mapped. 266 */ 267 public int indexOfKey(long key) { 268 if (mGarbage) { 269 gc(); 270 } 271 272 return binarySearch(mKeys, 0, mSize, key); 273 } 274 275 /** 276 * Returns an index for which {@link #valueAt} would return the 277 * specified key, or a negative number if no keys map to the 278 * specified value. 279 * Beware that this is a linear search, unlike lookups by key, 280 * and that multiple keys can map to the same value and this will 281 * find only one of them. 282 */ 283 public int indexOfValue(E value) { 284 if (mGarbage) { 285 gc(); 286 } 287 288 for (int i = 0; i < mSize; i++) 289 if (mValues[i].get() == value) 290 return i; 291 292 return -1; 293 } 294 295 /** 296 * Removes all key-value mappings from this SparseArray. 297 */ 298 public void clear() { 299 int n = mSize; 300 WeakReference<?>[] values = mValues; 301 302 for (int i = 0; i < n; i++) { 303 values[i] = null; 304 } 305 306 mSize = 0; 307 mGarbage = false; 308 } 309 310 /** 311 * Puts a key/value pair into the array, optimizing for the case where 312 * the key is greater than all existing keys in the array. 313 */ 314 public void append(long key, E value) { 315 if (mSize != 0 && key <= mKeys[mSize - 1]) { 316 put(key, value); 317 return; 318 } 319 320 if (mSize >= mKeys.length && (mGarbage || hasReclaimedRefs())) { 321 gc(); 322 } 323 324 int pos = mSize; 325 if (pos >= mKeys.length) { 326 int n = ArrayUtils.idealLongArraySize(pos + 1); 327 328 long[] nkeys = new long[n]; 329 WeakReference<?>[] nvalues = new WeakReference[n]; 330 331 // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 332 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 333 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 334 335 mKeys = nkeys; 336 mValues = nvalues; 337 } 338 339 mKeys[pos] = key; 340 mValues[pos] = new WeakReference(value); 341 mSize = pos + 1; 342 } 343 344 private boolean hasReclaimedRefs() { 345 for (int i = 0 ; i < mSize ; i++) { 346 if (mValues[i].get() == null) { // DELETED.get() never returns null. 347 return true; 348 } 349 } 350 351 return false; 352 } 353 354 private static int binarySearch(long[] a, int start, int len, long key) { 355 int high = start + len, low = start - 1, guess; 356 357 while (high - low > 1) { 358 guess = (high + low) / 2; 359 360 if (a[guess] < key) 361 low = guess; 362 else 363 high = guess; 364 } 365 366 if (high == start + len) 367 return ~(start + len); 368 else if (a[high] == key) 369 return high; 370 else 371 return ~high; 372 } 373 374 private long[] mKeys; 375 private WeakReference<?>[] mValues; 376 private int mSize; 377} 378