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 17 package android.util; 18 19 import libcore.util.EmptyArray; 20 21 import java.util.Collection; 22 import java.util.ConcurrentModificationException; 23 import java.util.Map; 24 import java.util.Set; 25 26 /** 27 * ArrayMap is a generic key->value mapping data structure that is 28 * designed to be more memory efficient than a traditional {@link java.util.HashMap}. 29 * It keeps its mappings in an array data structure -- an integer array of hash 30 * codes for each item, and an Object array of the key/value pairs. This allows it to 31 * avoid having to create an extra object for every entry put in to the map, and it 32 * also tries to control the growth of the size of these arrays more aggressively 33 * (since growing them only requires copying the entries in the array, not rebuilding 34 * a hash map). 35 * 36 * <p>Note that this implementation is not intended to be appropriate for data structures 37 * that may contain large numbers of items. It is generally slower than a traditional 38 * HashMap, since lookups require a binary search and adds and removes require inserting 39 * and deleting entries in the array. For containers holding up to hundreds of items, 40 * the performance difference is not significant, less than 50%.</p> 41 * 42 * <p>Because this container is intended to better balance memory use, unlike most other 43 * standard Java containers it will shrink its array as items are removed from it. Currently 44 * you have no control over this shrinking -- if you set a capacity and then remove an 45 * item, it may reduce the capacity to better match the current size. In the future an 46 * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 47 */ 48 public final class ArrayMap<K, V> implements Map<K, V> { 49 private static final boolean DEBUG = false; 50 private static final String TAG = "ArrayMap"; 51 52 /** 53 * Attempt to spot concurrent modifications to this data structure. 54 * 55 * It's best-effort, but any time we can throw something more diagnostic than an 56 * ArrayIndexOutOfBoundsException deep in the ArrayMap internals it's going to 57 * save a lot of development time. 58 * 59 * Good times to look for CME include after any allocArrays() call and at the end of 60 * functions that change mSize (put/remove/clear). 61 */ 62 private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true; 63 64 /** 65 * The minimum amount by which the capacity of a ArrayMap will increase. 66 * This is tuned to be relatively space-efficient. 67 */ 68 private static final int BASE_SIZE = 4; 69 70 /** 71 * Maximum number of entries to have in array caches. 72 */ 73 private static final int CACHE_SIZE = 10; 74 75 /** 76 * Special hash array value that indicates the container is immutable. 77 */ 78 static final int[] EMPTY_IMMUTABLE_INTS = new int[0]; 79 80 /** 81 * @hide Special immutable empty ArrayMap. 82 */ 83 public static final ArrayMap EMPTY = new ArrayMap<>(-1); 84 85 /** 86 * Caches of small array objects to avoid spamming garbage. The cache 87 * Object[] variable is a pointer to a linked list of array objects. 88 * The first entry in the array is a pointer to the next array in the 89 * list; the second entry is a pointer to the int[] hash code array for it. 90 */ 91 static Object[] mBaseCache; 92 static int mBaseCacheSize; 93 static Object[] mTwiceBaseCache; 94 static int mTwiceBaseCacheSize; 95 96 final boolean mIdentityHashCode; 97 int[] mHashes; 98 Object[] mArray; 99 int mSize; 100 MapCollections<K, V> mCollections; 101 binarySearchHashes(int[] hashes, int N, int hash)102 private static int binarySearchHashes(int[] hashes, int N, int hash) { 103 try { 104 return ContainerHelpers.binarySearch(hashes, N, hash); 105 } catch (ArrayIndexOutOfBoundsException e) { 106 if (CONCURRENT_MODIFICATION_EXCEPTIONS) { 107 throw new ConcurrentModificationException(); 108 } else { 109 throw e; // the cache is poisoned at this point, there's not much we can do 110 } 111 } 112 } 113 indexOf(Object key, int hash)114 int indexOf(Object key, int hash) { 115 final int N = mSize; 116 117 // Important fast case: if nothing is in here, nothing to look for. 118 if (N == 0) { 119 return ~0; 120 } 121 122 int index = binarySearchHashes(mHashes, N, hash); 123 124 // If the hash code wasn't found, then we have no entry for this key. 125 if (index < 0) { 126 return index; 127 } 128 129 // If the key at the returned index matches, that's what we want. 130 if (key.equals(mArray[index<<1])) { 131 return index; 132 } 133 134 // Search for a matching key after the index. 135 int end; 136 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 137 if (key.equals(mArray[end << 1])) return end; 138 } 139 140 // Search for a matching key before the index. 141 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 142 if (key.equals(mArray[i << 1])) return i; 143 } 144 145 // Key not found -- return negative value indicating where a 146 // new entry for this key should go. We use the end of the 147 // hash chain to reduce the number of array entries that will 148 // need to be copied when inserting. 149 return ~end; 150 } 151 indexOfNull()152 int indexOfNull() { 153 final int N = mSize; 154 155 // Important fast case: if nothing is in here, nothing to look for. 156 if (N == 0) { 157 return ~0; 158 } 159 160 int index = binarySearchHashes(mHashes, N, 0); 161 162 // If the hash code wasn't found, then we have no entry for this key. 163 if (index < 0) { 164 return index; 165 } 166 167 // If the key at the returned index matches, that's what we want. 168 if (null == mArray[index<<1]) { 169 return index; 170 } 171 172 // Search for a matching key after the index. 173 int end; 174 for (end = index + 1; end < N && mHashes[end] == 0; end++) { 175 if (null == mArray[end << 1]) return end; 176 } 177 178 // Search for a matching key before the index. 179 for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 180 if (null == mArray[i << 1]) return i; 181 } 182 183 // Key not found -- return negative value indicating where a 184 // new entry for this key should go. We use the end of the 185 // hash chain to reduce the number of array entries that will 186 // need to be copied when inserting. 187 return ~end; 188 } 189 allocArrays(final int size)190 private void allocArrays(final int size) { 191 if (mHashes == EMPTY_IMMUTABLE_INTS) { 192 throw new UnsupportedOperationException("ArrayMap is immutable"); 193 } 194 if (size == (BASE_SIZE*2)) { 195 synchronized (ArrayMap.class) { 196 if (mTwiceBaseCache != null) { 197 final Object[] array = mTwiceBaseCache; 198 mArray = array; 199 mTwiceBaseCache = (Object[])array[0]; 200 mHashes = (int[])array[1]; 201 array[0] = array[1] = null; 202 mTwiceBaseCacheSize--; 203 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 204 + " now have " + mTwiceBaseCacheSize + " entries"); 205 return; 206 } 207 } 208 } else if (size == BASE_SIZE) { 209 synchronized (ArrayMap.class) { 210 if (mBaseCache != null) { 211 final Object[] array = mBaseCache; 212 mArray = array; 213 mBaseCache = (Object[])array[0]; 214 mHashes = (int[])array[1]; 215 array[0] = array[1] = null; 216 mBaseCacheSize--; 217 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 218 + " now have " + mBaseCacheSize + " entries"); 219 return; 220 } 221 } 222 } 223 224 mHashes = new int[size]; 225 mArray = new Object[size<<1]; 226 } 227 freeArrays(final int[] hashes, final Object[] array, final int size)228 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 229 if (hashes.length == (BASE_SIZE*2)) { 230 synchronized (ArrayMap.class) { 231 if (mTwiceBaseCacheSize < CACHE_SIZE) { 232 array[0] = mTwiceBaseCache; 233 array[1] = hashes; 234 for (int i=(size<<1)-1; i>=2; i--) { 235 array[i] = null; 236 } 237 mTwiceBaseCache = array; 238 mTwiceBaseCacheSize++; 239 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 240 + " now have " + mTwiceBaseCacheSize + " entries"); 241 } 242 } 243 } else if (hashes.length == BASE_SIZE) { 244 synchronized (ArrayMap.class) { 245 if (mBaseCacheSize < CACHE_SIZE) { 246 array[0] = mBaseCache; 247 array[1] = hashes; 248 for (int i=(size<<1)-1; i>=2; i--) { 249 array[i] = null; 250 } 251 mBaseCache = array; 252 mBaseCacheSize++; 253 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 254 + " now have " + mBaseCacheSize + " entries"); 255 } 256 } 257 } 258 } 259 260 /** 261 * Create a new empty ArrayMap. The default capacity of an array map is 0, and 262 * will grow once items are added to it. 263 */ ArrayMap()264 public ArrayMap() { 265 this(0, false); 266 } 267 268 /** 269 * Create a new ArrayMap with a given initial capacity. 270 */ ArrayMap(int capacity)271 public ArrayMap(int capacity) { 272 this(capacity, false); 273 } 274 275 /** {@hide} */ ArrayMap(int capacity, boolean identityHashCode)276 public ArrayMap(int capacity, boolean identityHashCode) { 277 mIdentityHashCode = identityHashCode; 278 279 // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS 280 // instance instead of the usual EmptyArray.INT. The reference 281 // is checked later to see if the array is allowed to grow. 282 if (capacity < 0) { 283 mHashes = EMPTY_IMMUTABLE_INTS; 284 mArray = EmptyArray.OBJECT; 285 } else if (capacity == 0) { 286 mHashes = EmptyArray.INT; 287 mArray = EmptyArray.OBJECT; 288 } else { 289 allocArrays(capacity); 290 } 291 mSize = 0; 292 } 293 294 /** 295 * Create a new ArrayMap with the mappings from the given ArrayMap. 296 */ ArrayMap(ArrayMap<K, V> map)297 public ArrayMap(ArrayMap<K, V> map) { 298 this(); 299 if (map != null) { 300 putAll(map); 301 } 302 } 303 304 /** 305 * Make the array map empty. All storage is released. 306 */ 307 @Override clear()308 public void clear() { 309 if (mSize > 0) { 310 final int[] ohashes = mHashes; 311 final Object[] oarray = mArray; 312 final int osize = mSize; 313 mHashes = EmptyArray.INT; 314 mArray = EmptyArray.OBJECT; 315 mSize = 0; 316 freeArrays(ohashes, oarray, osize); 317 } 318 if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) { 319 throw new ConcurrentModificationException(); 320 } 321 } 322 323 /** 324 * @hide 325 * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 326 */ erase()327 public void erase() { 328 if (mSize > 0) { 329 final int N = mSize<<1; 330 final Object[] array = mArray; 331 for (int i=0; i<N; i++) { 332 array[i] = null; 333 } 334 mSize = 0; 335 } 336 } 337 338 /** 339 * Ensure the array map can hold at least <var>minimumCapacity</var> 340 * items. 341 */ ensureCapacity(int minimumCapacity)342 public void ensureCapacity(int minimumCapacity) { 343 final int osize = mSize; 344 if (mHashes.length < minimumCapacity) { 345 final int[] ohashes = mHashes; 346 final Object[] oarray = mArray; 347 allocArrays(minimumCapacity); 348 if (mSize > 0) { 349 System.arraycopy(ohashes, 0, mHashes, 0, osize); 350 System.arraycopy(oarray, 0, mArray, 0, osize<<1); 351 } 352 freeArrays(ohashes, oarray, osize); 353 } 354 if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) { 355 throw new ConcurrentModificationException(); 356 } 357 } 358 359 /** 360 * Check whether a key exists in the array. 361 * 362 * @param key The key to search for. 363 * @return Returns true if the key exists, else false. 364 */ 365 @Override containsKey(Object key)366 public boolean containsKey(Object key) { 367 return indexOfKey(key) >= 0; 368 } 369 370 /** 371 * Returns the index of a key in the set. 372 * 373 * @param key The key to search for. 374 * @return Returns the index of the key if it exists, else a negative integer. 375 */ indexOfKey(Object key)376 public int indexOfKey(Object key) { 377 return key == null ? indexOfNull() 378 : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()); 379 } 380 indexOfValue(Object value)381 int indexOfValue(Object value) { 382 final int N = mSize*2; 383 final Object[] array = mArray; 384 if (value == null) { 385 for (int i=1; i<N; i+=2) { 386 if (array[i] == null) { 387 return i>>1; 388 } 389 } 390 } else { 391 for (int i=1; i<N; i+=2) { 392 if (value.equals(array[i])) { 393 return i>>1; 394 } 395 } 396 } 397 return -1; 398 } 399 400 /** 401 * Check whether a value exists in the array. This requires a linear search 402 * through the entire array. 403 * 404 * @param value The value to search for. 405 * @return Returns true if the value exists, else false. 406 */ 407 @Override containsValue(Object value)408 public boolean containsValue(Object value) { 409 return indexOfValue(value) >= 0; 410 } 411 412 /** 413 * Retrieve a value from the array. 414 * @param key The key of the value to retrieve. 415 * @return Returns the value associated with the given key, 416 * or null if there is no such key. 417 */ 418 @Override get(Object key)419 public V get(Object key) { 420 final int index = indexOfKey(key); 421 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 422 } 423 424 /** 425 * Return the key at the given index in the array. 426 * @param index The desired index, must be between 0 and {@link #size()}-1. 427 * @return Returns the key stored at the given index. 428 */ keyAt(int index)429 public K keyAt(int index) { 430 return (K)mArray[index << 1]; 431 } 432 433 /** 434 * Return the value at the given index in the array. 435 * @param index The desired index, must be between 0 and {@link #size()}-1. 436 * @return Returns the value stored at the given index. 437 */ valueAt(int index)438 public V valueAt(int index) { 439 return (V)mArray[(index << 1) + 1]; 440 } 441 442 /** 443 * Set the value at a given index in the array. 444 * @param index The desired index, must be between 0 and {@link #size()}-1. 445 * @param value The new value to store at this index. 446 * @return Returns the previous value at the given index. 447 */ setValueAt(int index, V value)448 public V setValueAt(int index, V value) { 449 index = (index << 1) + 1; 450 V old = (V)mArray[index]; 451 mArray[index] = value; 452 return old; 453 } 454 455 /** 456 * Return true if the array map contains no items. 457 */ 458 @Override isEmpty()459 public boolean isEmpty() { 460 return mSize <= 0; 461 } 462 463 /** 464 * Add a new value to the array map. 465 * @param key The key under which to store the value. If 466 * this key already exists in the array, its value will be replaced. 467 * @param value The value to store for the given key. 468 * @return Returns the old value that was stored for the given key, or null if there 469 * was no such key. 470 */ 471 @Override put(K key, V value)472 public V put(K key, V value) { 473 final int osize = mSize; 474 final int hash; 475 int index; 476 if (key == null) { 477 hash = 0; 478 index = indexOfNull(); 479 } else { 480 hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode(); 481 index = indexOf(key, hash); 482 } 483 if (index >= 0) { 484 index = (index<<1) + 1; 485 final V old = (V)mArray[index]; 486 mArray[index] = value; 487 return old; 488 } 489 490 index = ~index; 491 if (osize >= mHashes.length) { 492 final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) 493 : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 494 495 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 496 497 final int[] ohashes = mHashes; 498 final Object[] oarray = mArray; 499 allocArrays(n); 500 501 if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 502 throw new ConcurrentModificationException(); 503 } 504 505 if (mHashes.length > 0) { 506 if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0"); 507 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 508 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 509 } 510 511 freeArrays(ohashes, oarray, osize); 512 } 513 514 if (index < osize) { 515 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index) 516 + " to " + (index+1)); 517 System.arraycopy(mHashes, index, mHashes, index + 1, osize - index); 518 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 519 } 520 521 if (CONCURRENT_MODIFICATION_EXCEPTIONS) { 522 if (osize != mSize || index >= mHashes.length) { 523 throw new ConcurrentModificationException(); 524 } 525 } 526 mHashes[index] = hash; 527 mArray[index<<1] = key; 528 mArray[(index<<1)+1] = value; 529 mSize++; 530 return null; 531 } 532 533 /** 534 * Special fast path for appending items to the end of the array without validation. 535 * The array must already be large enough to contain the item. 536 * @hide 537 */ append(K key, V value)538 public void append(K key, V value) { 539 int index = mSize; 540 final int hash = key == null ? 0 541 : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()); 542 if (index >= mHashes.length) { 543 throw new IllegalStateException("Array is full"); 544 } 545 if (index > 0 && mHashes[index-1] > hash) { 546 RuntimeException e = new RuntimeException("here"); 547 e.fillInStackTrace(); 548 Log.w(TAG, "New hash " + hash 549 + " is before end of array hash " + mHashes[index-1] 550 + " at index " + index + " key " + key, e); 551 put(key, value); 552 return; 553 } 554 mSize = index+1; 555 mHashes[index] = hash; 556 index <<= 1; 557 mArray[index] = key; 558 mArray[index+1] = value; 559 } 560 561 /** 562 * The use of the {@link #append} function can result in invalid array maps, in particular 563 * an array map where the same key appears multiple times. This function verifies that 564 * the array map is valid, throwing IllegalArgumentException if a problem is found. The 565 * main use for this method is validating an array map after unpacking from an IPC, to 566 * protect against malicious callers. 567 * @hide 568 */ validate()569 public void validate() { 570 final int N = mSize; 571 if (N <= 1) { 572 // There can't be dups. 573 return; 574 } 575 int basehash = mHashes[0]; 576 int basei = 0; 577 for (int i=1; i<N; i++) { 578 int hash = mHashes[i]; 579 if (hash != basehash) { 580 basehash = hash; 581 basei = i; 582 continue; 583 } 584 // We are in a run of entries with the same hash code. Go backwards through 585 // the array to see if any keys are the same. 586 final Object cur = mArray[i<<1]; 587 for (int j=i-1; j>=basei; j--) { 588 final Object prev = mArray[j<<1]; 589 if (cur == prev) { 590 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 591 } 592 if (cur != null && prev != null && cur.equals(prev)) { 593 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 594 } 595 } 596 } 597 } 598 599 /** 600 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 601 * @param array The array whose contents are to be retrieved. 602 */ putAll(ArrayMap<? extends K, ? extends V> array)603 public void putAll(ArrayMap<? extends K, ? extends V> array) { 604 final int N = array.mSize; 605 ensureCapacity(mSize + N); 606 if (mSize == 0) { 607 if (N > 0) { 608 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 609 System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 610 mSize = N; 611 } 612 } else { 613 for (int i=0; i<N; i++) { 614 put(array.keyAt(i), array.valueAt(i)); 615 } 616 } 617 } 618 619 /** 620 * Remove an existing key from the array map. 621 * @param key The key of the mapping to remove. 622 * @return Returns the value that was stored under the key, or null if there 623 * was no such key. 624 */ 625 @Override remove(Object key)626 public V remove(Object key) { 627 final int index = indexOfKey(key); 628 if (index >= 0) { 629 return removeAt(index); 630 } 631 632 return null; 633 } 634 635 /** 636 * Remove the key/value mapping at the given index. 637 * @param index The desired index, must be between 0 and {@link #size()}-1. 638 * @return Returns the value that was stored at this index. 639 */ removeAt(int index)640 public V removeAt(int index) { 641 final Object old = mArray[(index << 1) + 1]; 642 final int osize = mSize; 643 final int nsize; 644 if (osize <= 1) { 645 // Now empty. 646 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 647 freeArrays(mHashes, mArray, osize); 648 mHashes = EmptyArray.INT; 649 mArray = EmptyArray.OBJECT; 650 nsize = 0; 651 } else { 652 nsize = osize - 1; 653 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 654 // Shrunk enough to reduce size of arrays. We don't allow it to 655 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 656 // that and BASE_SIZE. 657 final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2); 658 659 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 660 661 final int[] ohashes = mHashes; 662 final Object[] oarray = mArray; 663 allocArrays(n); 664 665 if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 666 throw new ConcurrentModificationException(); 667 } 668 669 if (index > 0) { 670 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 671 System.arraycopy(ohashes, 0, mHashes, 0, index); 672 System.arraycopy(oarray, 0, mArray, 0, index << 1); 673 } 674 if (index < nsize) { 675 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize 676 + " to " + index); 677 System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index); 678 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 679 (nsize - index) << 1); 680 } 681 } else { 682 if (index < nsize) { 683 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize 684 + " to " + index); 685 System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index); 686 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 687 (nsize - index) << 1); 688 } 689 mArray[nsize << 1] = null; 690 mArray[(nsize << 1) + 1] = null; 691 } 692 } 693 if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 694 throw new ConcurrentModificationException(); 695 } 696 mSize = nsize; 697 return (V)old; 698 } 699 700 /** 701 * Return the number of items in this array map. 702 */ 703 @Override size()704 public int size() { 705 return mSize; 706 } 707 708 /** 709 * {@inheritDoc} 710 * 711 * <p>This implementation returns false if the object is not a map, or 712 * if the maps have different sizes. Otherwise, for each key in this map, 713 * values of both maps are compared. If the values for any key are not 714 * equal, the method returns false, otherwise it returns true. 715 */ 716 @Override equals(Object object)717 public boolean equals(Object object) { 718 if (this == object) { 719 return true; 720 } 721 if (object instanceof Map) { 722 Map<?, ?> map = (Map<?, ?>) object; 723 if (size() != map.size()) { 724 return false; 725 } 726 727 try { 728 for (int i=0; i<mSize; i++) { 729 K key = keyAt(i); 730 V mine = valueAt(i); 731 Object theirs = map.get(key); 732 if (mine == null) { 733 if (theirs != null || !map.containsKey(key)) { 734 return false; 735 } 736 } else if (!mine.equals(theirs)) { 737 return false; 738 } 739 } 740 } catch (NullPointerException ignored) { 741 return false; 742 } catch (ClassCastException ignored) { 743 return false; 744 } 745 return true; 746 } 747 return false; 748 } 749 750 /** 751 * {@inheritDoc} 752 */ 753 @Override hashCode()754 public int hashCode() { 755 final int[] hashes = mHashes; 756 final Object[] array = mArray; 757 int result = 0; 758 for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 759 Object value = array[v]; 760 result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 761 } 762 return result; 763 } 764 765 /** 766 * {@inheritDoc} 767 * 768 * <p>This implementation composes a string by iterating over its mappings. If 769 * this map contains itself as a key or a value, the string "(this Map)" 770 * will appear in its place. 771 */ 772 @Override toString()773 public String toString() { 774 if (isEmpty()) { 775 return "{}"; 776 } 777 778 StringBuilder buffer = new StringBuilder(mSize * 28); 779 buffer.append('{'); 780 for (int i=0; i<mSize; i++) { 781 if (i > 0) { 782 buffer.append(", "); 783 } 784 Object key = keyAt(i); 785 if (key != this) { 786 buffer.append(key); 787 } else { 788 buffer.append("(this Map)"); 789 } 790 buffer.append('='); 791 Object value = valueAt(i); 792 if (value != this) { 793 buffer.append(value); 794 } else { 795 buffer.append("(this Map)"); 796 } 797 } 798 buffer.append('}'); 799 return buffer.toString(); 800 } 801 802 // ------------------------------------------------------------------------ 803 // Interop with traditional Java containers. Not as efficient as using 804 // specialized collection APIs. 805 // ------------------------------------------------------------------------ 806 getCollection()807 private MapCollections<K, V> getCollection() { 808 if (mCollections == null) { 809 mCollections = new MapCollections<K, V>() { 810 @Override 811 protected int colGetSize() { 812 return mSize; 813 } 814 815 @Override 816 protected Object colGetEntry(int index, int offset) { 817 return mArray[(index<<1) + offset]; 818 } 819 820 @Override 821 protected int colIndexOfKey(Object key) { 822 return indexOfKey(key); 823 } 824 825 @Override 826 protected int colIndexOfValue(Object value) { 827 return indexOfValue(value); 828 } 829 830 @Override 831 protected Map<K, V> colGetMap() { 832 return ArrayMap.this; 833 } 834 835 @Override 836 protected void colPut(K key, V value) { 837 put(key, value); 838 } 839 840 @Override 841 protected V colSetValue(int index, V value) { 842 return setValueAt(index, value); 843 } 844 845 @Override 846 protected void colRemoveAt(int index) { 847 removeAt(index); 848 } 849 850 @Override 851 protected void colClear() { 852 clear(); 853 } 854 }; 855 } 856 return mCollections; 857 } 858 859 /** 860 * Determine if the array map contains all of the keys in the given collection. 861 * @param collection The collection whose contents are to be checked against. 862 * @return Returns true if this array map contains a key for every entry 863 * in <var>collection</var>, else returns false. 864 */ containsAll(Collection<?> collection)865 public boolean containsAll(Collection<?> collection) { 866 return MapCollections.containsAllHelper(this, collection); 867 } 868 869 /** 870 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 871 * @param map The map whose contents are to be retrieved. 872 */ 873 @Override putAll(Map<? extends K, ? extends V> map)874 public void putAll(Map<? extends K, ? extends V> map) { 875 ensureCapacity(mSize + map.size()); 876 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 877 put(entry.getKey(), entry.getValue()); 878 } 879 } 880 881 /** 882 * Remove all keys in the array map that exist in the given collection. 883 * @param collection The collection whose contents are to be used to remove keys. 884 * @return Returns true if any keys were removed from the array map, else false. 885 */ removeAll(Collection<?> collection)886 public boolean removeAll(Collection<?> collection) { 887 return MapCollections.removeAllHelper(this, collection); 888 } 889 890 /** 891 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 892 * @param collection The collection whose contents are to be used to determine which 893 * keys to keep. 894 * @return Returns true if any keys were removed from the array map, else false. 895 */ retainAll(Collection<?> collection)896 public boolean retainAll(Collection<?> collection) { 897 return MapCollections.retainAllHelper(this, collection); 898 } 899 900 /** 901 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 902 * in the array map. 903 * 904 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 905 * requires generating a number of temporary objects and allocates additional state 906 * information associated with the container that will remain for the life of the container.</p> 907 * 908 * <p><b>Note:</b></p> the semantics of this 909 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 910 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 911 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 912 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 913 */ 914 @Override entrySet()915 public Set<Map.Entry<K, V>> entrySet() { 916 return getCollection().getEntrySet(); 917 } 918 919 /** 920 * Return a {@link java.util.Set} for iterating over and interacting with all keys 921 * in the array map. 922 * 923 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 924 * requires generating a number of temporary objects and allocates additional state 925 * information associated with the container that will remain for the life of the container.</p> 926 */ 927 @Override keySet()928 public Set<K> keySet() { 929 return getCollection().getKeySet(); 930 } 931 932 /** 933 * Return a {@link java.util.Collection} for iterating over and interacting with all values 934 * in the array map. 935 * 936 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 937 * requires generating a number of temporary objects and allocates additional state 938 * information associated with the container that will remain for the life of the container.</p> 939 */ 940 @Override values()941 public Collection<V> values() { 942 return getCollection().getValues(); 943 } 944 } 945