1/* 2 * Copyright (C) 2013 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 android.support.v4.util; 18 19import android.util.Log; 20 21import java.util.Map; 22 23/** 24 * Base implementation of {@link ArrayMap} that doesn't include any standard Java 25 * container API interoperability. These features are generally heavier-weight ways 26 * to interact with the container, so discouraged, but they can be useful to make it 27 * easier to use as a drop-in replacement for HashMap. If you don't need them, this 28 * class can be preferrable since it doesn't bring in any of the implementation of those 29 * APIs, allowing that code to be stripped by ProGuard. 30 */ 31public class SimpleArrayMap<K, V> { 32 private static final boolean DEBUG = false; 33 private static final String TAG = "ArrayMap"; 34 35 /** 36 * The minimum amount by which the capacity of a ArrayMap will increase. 37 * This is tuned to be relatively space-efficient. 38 */ 39 private static final int BASE_SIZE = 4; 40 41 /** 42 * Maximum number of entries to have in array caches. 43 */ 44 private static final int CACHE_SIZE = 10; 45 46 /** 47 * Caches of small array objects to avoid spamming garbage. The cache 48 * Object[] variable is a pointer to a linked list of array objects. 49 * The first entry in the array is a pointer to the next array in the 50 * list; the second entry is a pointer to the int[] hash code array for it. 51 */ 52 static Object[] mBaseCache; 53 static int mBaseCacheSize; 54 static Object[] mTwiceBaseCache; 55 static int mTwiceBaseCacheSize; 56 57 int[] mHashes; 58 Object[] mArray; 59 int mSize; 60 61 int indexOf(Object key, int hash) { 62 final int N = mSize; 63 64 // Important fast case: if nothing is in here, nothing to look for. 65 if (N == 0) { 66 return ~0; 67 } 68 69 int index = ContainerHelpers.binarySearch(mHashes, N, hash); 70 71 // If the hash code wasn't found, then we have no entry for this key. 72 if (index < 0) { 73 return index; 74 } 75 76 // If the key at the returned index matches, that's what we want. 77 if (key.equals(mArray[index<<1])) { 78 return index; 79 } 80 81 // Search for a matching key after the index. 82 int end; 83 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 84 if (key.equals(mArray[end << 1])) return end; 85 } 86 87 // Search for a matching key before the index. 88 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 89 if (key.equals(mArray[i << 1])) return i; 90 } 91 92 // Key not found -- return negative value indicating where a 93 // new entry for this key should go. We use the end of the 94 // hash chain to reduce the number of array entries that will 95 // need to be copied when inserting. 96 return ~end; 97 } 98 99 int indexOfNull() { 100 final int N = mSize; 101 102 // Important fast case: if nothing is in here, nothing to look for. 103 if (N == 0) { 104 return ~0; 105 } 106 107 int index = ContainerHelpers.binarySearch(mHashes, N, 0); 108 109 // If the hash code wasn't found, then we have no entry for this key. 110 if (index < 0) { 111 return index; 112 } 113 114 // If the key at the returned index matches, that's what we want. 115 if (null == mArray[index<<1]) { 116 return index; 117 } 118 119 // Search for a matching key after the index. 120 int end; 121 for (end = index + 1; end < N && mHashes[end] == 0; end++) { 122 if (null == mArray[end << 1]) return end; 123 } 124 125 // Search for a matching key before the index. 126 for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 127 if (null == mArray[i << 1]) return i; 128 } 129 130 // Key not found -- return negative value indicating where a 131 // new entry for this key should go. We use the end of the 132 // hash chain to reduce the number of array entries that will 133 // need to be copied when inserting. 134 return ~end; 135 } 136 137 private void allocArrays(final int size) { 138 if (size == (BASE_SIZE*2)) { 139 synchronized (ArrayMap.class) { 140 if (mTwiceBaseCache != null) { 141 final Object[] array = mTwiceBaseCache; 142 mArray = array; 143 mTwiceBaseCache = (Object[])array[0]; 144 mHashes = (int[])array[1]; 145 array[0] = array[1] = null; 146 mTwiceBaseCacheSize--; 147 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 148 + " now have " + mTwiceBaseCacheSize + " entries"); 149 return; 150 } 151 } 152 } else if (size == BASE_SIZE) { 153 synchronized (ArrayMap.class) { 154 if (mBaseCache != null) { 155 final Object[] array = mBaseCache; 156 mArray = array; 157 mBaseCache = (Object[])array[0]; 158 mHashes = (int[])array[1]; 159 array[0] = array[1] = null; 160 mBaseCacheSize--; 161 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 162 + " now have " + mBaseCacheSize + " entries"); 163 return; 164 } 165 } 166 } 167 168 mHashes = new int[size]; 169 mArray = new Object[size<<1]; 170 } 171 172 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 173 if (hashes.length == (BASE_SIZE*2)) { 174 synchronized (ArrayMap.class) { 175 if (mTwiceBaseCacheSize < CACHE_SIZE) { 176 array[0] = mTwiceBaseCache; 177 array[1] = hashes; 178 for (int i=(size<<1)-1; i>=2; i--) { 179 array[i] = null; 180 } 181 mTwiceBaseCache = array; 182 mTwiceBaseCacheSize++; 183 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 184 + " now have " + mTwiceBaseCacheSize + " entries"); 185 } 186 } 187 } else if (hashes.length == BASE_SIZE) { 188 synchronized (ArrayMap.class) { 189 if (mBaseCacheSize < CACHE_SIZE) { 190 array[0] = mBaseCache; 191 array[1] = hashes; 192 for (int i=(size<<1)-1; i>=2; i--) { 193 array[i] = null; 194 } 195 mBaseCache = array; 196 mBaseCacheSize++; 197 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 198 + " now have " + mBaseCacheSize + " entries"); 199 } 200 } 201 } 202 } 203 204 /** 205 * Create a new empty ArrayMap. The default capacity of an array map is 0, and 206 * will grow once items are added to it. 207 */ 208 public SimpleArrayMap() { 209 mHashes = ContainerHelpers.EMPTY_INTS; 210 mArray = ContainerHelpers.EMPTY_OBJECTS; 211 mSize = 0; 212 } 213 214 /** 215 * Create a new ArrayMap with a given initial capacity. 216 */ 217 public SimpleArrayMap(int capacity) { 218 if (capacity == 0) { 219 mHashes = ContainerHelpers.EMPTY_INTS; 220 mArray = ContainerHelpers.EMPTY_OBJECTS; 221 } else { 222 allocArrays(capacity); 223 } 224 mSize = 0; 225 } 226 227 /** 228 * Create a new ArrayMap with the mappings from the given ArrayMap. 229 */ 230 public SimpleArrayMap(SimpleArrayMap map) { 231 this(); 232 if (map != null) { 233 putAll(map); 234 } 235 } 236 237 /** 238 * Make the array map empty. All storage is released. 239 */ 240 public void clear() { 241 if (mSize != 0) { 242 freeArrays(mHashes, mArray, mSize); 243 mHashes = ContainerHelpers.EMPTY_INTS; 244 mArray = ContainerHelpers.EMPTY_OBJECTS; 245 mSize = 0; 246 } 247 } 248 249 /** 250 * Ensure the array map can hold at least <var>minimumCapacity</var> 251 * items. 252 */ 253 public void ensureCapacity(int minimumCapacity) { 254 if (mHashes.length < minimumCapacity) { 255 final int[] ohashes = mHashes; 256 final Object[] oarray = mArray; 257 allocArrays(minimumCapacity); 258 if (mSize > 0) { 259 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 260 System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 261 } 262 freeArrays(ohashes, oarray, mSize); 263 } 264 } 265 266 /** 267 * Check whether a key exists in the array. 268 * 269 * @param key The key to search for. 270 * @return Returns true if the key exists, else false. 271 */ 272 public boolean containsKey(Object key) { 273 return indexOfKey(key) >= 0; 274 } 275 276 /** 277 * Returns the index of a key in the set. 278 * 279 * @param key The key to search for. 280 * @return Returns the index of the key if it exists, else a negative integer. 281 */ 282 public int indexOfKey(Object key) { 283 return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 284 } 285 286 int indexOfValue(Object value) { 287 final int N = mSize*2; 288 final Object[] array = mArray; 289 if (value == null) { 290 for (int i=1; i<N; i+=2) { 291 if (array[i] == null) { 292 return i>>1; 293 } 294 } 295 } else { 296 for (int i=1; i<N; i+=2) { 297 if (value.equals(array[i])) { 298 return i>>1; 299 } 300 } 301 } 302 return -1; 303 } 304 305 /** 306 * Check whether a value exists in the array. This requires a linear search 307 * through the entire array. 308 * 309 * @param value The value to search for. 310 * @return Returns true if the value exists, else false. 311 */ 312 public boolean containsValue(Object value) { 313 return indexOfValue(value) >= 0; 314 } 315 316 /** 317 * Retrieve a value from the array. 318 * @param key The key of the value to retrieve. 319 * @return Returns the value associated with the given key, 320 * or null if there is no such key. 321 */ 322 public V get(Object key) { 323 final int index = indexOfKey(key); 324 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 325 } 326 327 /** 328 * Return the key at the given index in the array. 329 * @param index The desired index, must be between 0 and {@link #size()}-1. 330 * @return Returns the key stored at the given index. 331 */ 332 public K keyAt(int index) { 333 return (K)mArray[index << 1]; 334 } 335 336 /** 337 * Return the value at the given index in the array. 338 * @param index The desired index, must be between 0 and {@link #size()}-1. 339 * @return Returns the value stored at the given index. 340 */ 341 public V valueAt(int index) { 342 return (V)mArray[(index << 1) + 1]; 343 } 344 345 /** 346 * Set the value at a given index in the array. 347 * @param index The desired index, must be between 0 and {@link #size()}-1. 348 * @param value The new value to store at this index. 349 * @return Returns the previous value at the given index. 350 */ 351 public V setValueAt(int index, V value) { 352 index = (index << 1) + 1; 353 V old = (V)mArray[index]; 354 mArray[index] = value; 355 return old; 356 } 357 358 /** 359 * Return true if the array map contains no items. 360 */ 361 public boolean isEmpty() { 362 return mSize <= 0; 363 } 364 365 /** 366 * Add a new value to the array map. 367 * @param key The key under which to store the value. <b>Must not be null.</b> If 368 * this key already exists in the array, its value will be replaced. 369 * @param value The value to store for the given key. 370 * @return Returns the old value that was stored for the given key, or null if there 371 * was no such key. 372 */ 373 public V put(K key, V value) { 374 final int hash; 375 int index; 376 if (key == null) { 377 hash = 0; 378 index = indexOfNull(); 379 } else { 380 hash = key.hashCode(); 381 index = indexOf(key, hash); 382 } 383 if (index >= 0) { 384 index = (index<<1) + 1; 385 final V old = (V)mArray[index]; 386 mArray[index] = value; 387 return old; 388 } 389 390 index = ~index; 391 if (mSize >= mHashes.length) { 392 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 393 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 394 395 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 396 397 final int[] ohashes = mHashes; 398 final Object[] oarray = mArray; 399 allocArrays(n); 400 401 if (mHashes.length > 0) { 402 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 403 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 404 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 405 } 406 407 freeArrays(ohashes, oarray, mSize); 408 } 409 410 if (index < mSize) { 411 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 412 + " to " + (index+1)); 413 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 414 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 415 } 416 417 mHashes[index] = hash; 418 mArray[index<<1] = key; 419 mArray[(index<<1)+1] = value; 420 mSize++; 421 return null; 422 } 423 424 /** 425 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 426 * @param array The array whose contents are to be retrieved. 427 */ 428 public void putAll(SimpleArrayMap<? extends K, ? extends V> array) { 429 final int N = array.mSize; 430 ensureCapacity(mSize + N); 431 if (mSize == 0) { 432 if (N > 0) { 433 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 434 System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 435 mSize = N; 436 } 437 } else { 438 for (int i=0; i<N; i++) { 439 put(array.keyAt(i), array.valueAt(i)); 440 } 441 } 442 } 443 444 /** 445 * Remove an existing key from the array map. 446 * @param key The key of the mapping to remove. 447 * @return Returns the value that was stored under the key, or null if there 448 * was no such key. 449 */ 450 public V remove(Object key) { 451 final int index = indexOfKey(key); 452 if (index >= 0) { 453 return removeAt(index); 454 } 455 456 return null; 457 } 458 459 /** 460 * Remove the key/value mapping at the given index. 461 * @param index The desired index, must be between 0 and {@link #size()}-1. 462 * @return Returns the value that was stored at this index. 463 */ 464 public V removeAt(int index) { 465 final Object old = mArray[(index << 1) + 1]; 466 if (mSize <= 1) { 467 // Now empty. 468 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 469 freeArrays(mHashes, mArray, mSize); 470 mHashes = ContainerHelpers.EMPTY_INTS; 471 mArray = ContainerHelpers.EMPTY_OBJECTS; 472 mSize = 0; 473 } else { 474 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 475 // Shrunk enough to reduce size of arrays. We don't allow it to 476 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 477 // that and BASE_SIZE. 478 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 479 480 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 481 482 final int[] ohashes = mHashes; 483 final Object[] oarray = mArray; 484 allocArrays(n); 485 486 mSize--; 487 if (index > 0) { 488 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 489 System.arraycopy(ohashes, 0, mHashes, 0, index); 490 System.arraycopy(oarray, 0, mArray, 0, index << 1); 491 } 492 if (index < mSize) { 493 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 494 + " to " + index); 495 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 496 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 497 (mSize - index) << 1); 498 } 499 } else { 500 mSize--; 501 if (index < mSize) { 502 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 503 + " to " + index); 504 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 505 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 506 (mSize - index) << 1); 507 } 508 mArray[mSize << 1] = null; 509 mArray[(mSize << 1) + 1] = null; 510 } 511 } 512 return (V)old; 513 } 514 515 /** 516 * Return the number of items in this array map. 517 */ 518 public int size() { 519 return mSize; 520 } 521 522 /** 523 * {@inheritDoc} 524 * 525 * <p>This implementation returns false if the object is not a Map or 526 * SimpleArrayMap, or if the maps have different sizes. Otherwise, for each 527 * key in this map, values of both maps are compared. If the values for any 528 * key are not equal, the method returns false, otherwise it returns true. 529 */ 530 @Override 531 public boolean equals(Object object) { 532 if (this == object) { 533 return true; 534 } 535 if (object instanceof SimpleArrayMap) { 536 SimpleArrayMap<?, ?> map = (SimpleArrayMap<?, ?>) object; 537 if (size() != map.size()) { 538 return false; 539 } 540 541 try { 542 for (int i=0; i<mSize; i++) { 543 K key = keyAt(i); 544 V mine = valueAt(i); 545 Object theirs = map.get(key); 546 if (mine == null) { 547 if (theirs != null || !map.containsKey(key)) { 548 return false; 549 } 550 } else if (!mine.equals(theirs)) { 551 return false; 552 } 553 } 554 } catch (NullPointerException ignored) { 555 return false; 556 } catch (ClassCastException ignored) { 557 return false; 558 } 559 return true; 560 } else if (object instanceof Map) { 561 Map<?, ?> map = (Map<?, ?>) object; 562 if (size() != map.size()) { 563 return false; 564 } 565 566 try { 567 for (int i=0; i<mSize; i++) { 568 K key = keyAt(i); 569 V mine = valueAt(i); 570 Object theirs = map.get(key); 571 if (mine == null) { 572 if (theirs != null || !map.containsKey(key)) { 573 return false; 574 } 575 } else if (!mine.equals(theirs)) { 576 return false; 577 } 578 } 579 } catch (NullPointerException ignored) { 580 return false; 581 } catch (ClassCastException ignored) { 582 return false; 583 } 584 return true; 585 } 586 return false; 587 } 588 589 /** 590 * {@inheritDoc} 591 */ 592 @Override 593 public int hashCode() { 594 final int[] hashes = mHashes; 595 final Object[] array = mArray; 596 int result = 0; 597 for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 598 Object value = array[v]; 599 result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 600 } 601 return result; 602 } 603 604 /** 605 * {@inheritDoc} 606 * 607 * <p>This implementation composes a string by iterating over its mappings. If 608 * this map contains itself as a key or a value, the string "(this Map)" 609 * will appear in its place. 610 */ 611 @Override 612 public String toString() { 613 if (isEmpty()) { 614 return "{}"; 615 } 616 617 StringBuilder buffer = new StringBuilder(mSize * 28); 618 buffer.append('{'); 619 for (int i=0; i<mSize; i++) { 620 if (i > 0) { 621 buffer.append(", "); 622 } 623 Object key = keyAt(i); 624 if (key != this) { 625 buffer.append(key); 626 } else { 627 buffer.append("(this Map)"); 628 } 629 buffer.append('='); 630 Object value = valueAt(i); 631 if (value != this) { 632 buffer.append(value); 633 } else { 634 buffer.append("(this Map)"); 635 } 636 } 637 buffer.append('}'); 638 return buffer.toString(); 639 } 640} 641