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.lang.reflect.Array; 22 import java.util.Collection; 23 import java.util.Iterator; 24 import java.util.Map; 25 import java.util.Set; 26 27 /** 28 * ArraySet is a generic set data structure that is designed to be more memory efficient than a 29 * traditional {@link java.util.HashSet}. The design is very similar to 30 * {@link ArrayMap}, with all of the caveats described there. This implementation is 31 * separate from ArrayMap, however, so the Object array contains only one item for each 32 * entry in the set (instead of a pair for a mapping). 33 * 34 * <p>Note that this implementation is not intended to be appropriate for data structures 35 * that may contain large numbers of items. It is generally slower than a traditional 36 * HashSet, since lookups require a binary search and adds and removes require inserting 37 * and deleting entries in the array. For containers holding up to hundreds of items, 38 * the performance difference is not significant, less than 50%.</p> 39 * 40 * <p>Because this container is intended to better balance memory use, unlike most other 41 * standard Java containers it will shrink its array as items are removed from it. Currently 42 * you have no control over this shrinking -- if you set a capacity and then remove an 43 * item, it may reduce the capacity to better match the current size. In the future an 44 * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 45 * 46 * @hide 47 */ 48 public final class ArraySet<E> implements Collection<E>, Set<E> { 49 private static final boolean DEBUG = false; 50 private static final String TAG = "ArraySet"; 51 52 /** 53 * The minimum amount by which the capacity of a ArraySet will increase. 54 * This is tuned to be relatively space-efficient. 55 */ 56 private static final int BASE_SIZE = 4; 57 58 /** 59 * Maximum number of entries to have in array caches. 60 */ 61 private static final int CACHE_SIZE = 10; 62 63 /** 64 * Caches of small array objects to avoid spamming garbage. The cache 65 * Object[] variable is a pointer to a linked list of array objects. 66 * The first entry in the array is a pointer to the next array in the 67 * list; the second entry is a pointer to the int[] hash code array for it. 68 */ 69 static Object[] mBaseCache; 70 static int mBaseCacheSize; 71 static Object[] mTwiceBaseCache; 72 static int mTwiceBaseCacheSize; 73 74 int[] mHashes; 75 Object[] mArray; 76 int mSize; 77 MapCollections<E, E> mCollections; 78 79 private int indexOf(Object key, int hash) { 80 final int N = mSize; 81 82 // Important fast case: if nothing is in here, nothing to look for. 83 if (N == 0) { 84 return ~0; 85 } 86 87 int index = ContainerHelpers.binarySearch(mHashes, N, hash); 88 89 // If the hash code wasn't found, then we have no entry for this key. 90 if (index < 0) { 91 return index; 92 } 93 94 // If the key at the returned index matches, that's what we want. 95 if (key.equals(mArray[index])) { 96 return index; 97 } 98 99 // Search for a matching key after the index. 100 int end; 101 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 102 if (key.equals(mArray[end])) return end; 103 } 104 105 // Search for a matching key before the index. 106 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 107 if (key.equals(mArray[i])) return i; 108 } 109 110 // Key not found -- return negative value indicating where a 111 // new entry for this key should go. We use the end of the 112 // hash chain to reduce the number of array entries that will 113 // need to be copied when inserting. 114 return ~end; 115 } 116 117 private int indexOfNull() { 118 final int N = mSize; 119 120 // Important fast case: if nothing is in here, nothing to look for. 121 if (N == 0) { 122 return ~0; 123 } 124 125 int index = ContainerHelpers.binarySearch(mHashes, N, 0); 126 127 // If the hash code wasn't found, then we have no entry for this key. 128 if (index < 0) { 129 return index; 130 } 131 132 // If the key at the returned index matches, that's what we want. 133 if (null == mArray[index]) { 134 return index; 135 } 136 137 // Search for a matching key after the index. 138 int end; 139 for (end = index + 1; end < N && mHashes[end] == 0; end++) { 140 if (null == mArray[end]) return end; 141 } 142 143 // Search for a matching key before the index. 144 for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 145 if (null == mArray[i]) return i; 146 } 147 148 // Key not found -- return negative value indicating where a 149 // new entry for this key should go. We use the end of the 150 // hash chain to reduce the number of array entries that will 151 // need to be copied when inserting. 152 return ~end; 153 } 154 155 private void allocArrays(final int size) { 156 if (size == (BASE_SIZE*2)) { 157 synchronized (ArraySet.class) { 158 if (mTwiceBaseCache != null) { 159 final Object[] array = mTwiceBaseCache; 160 mArray = array; 161 mTwiceBaseCache = (Object[])array[0]; 162 mHashes = (int[])array[1]; 163 array[0] = array[1] = null; 164 mTwiceBaseCacheSize--; 165 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 166 + " now have " + mTwiceBaseCacheSize + " entries"); 167 return; 168 } 169 } 170 } else if (size == BASE_SIZE) { 171 synchronized (ArraySet.class) { 172 if (mBaseCache != null) { 173 final Object[] array = mBaseCache; 174 mArray = array; 175 mBaseCache = (Object[])array[0]; 176 mHashes = (int[])array[1]; 177 array[0] = array[1] = null; 178 mBaseCacheSize--; 179 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 180 + " now have " + mBaseCacheSize + " entries"); 181 return; 182 } 183 } 184 } 185 186 mHashes = new int[size]; 187 mArray = new Object[size]; 188 } 189 190 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 191 if (hashes.length == (BASE_SIZE*2)) { 192 synchronized (ArraySet.class) { 193 if (mTwiceBaseCacheSize < CACHE_SIZE) { 194 array[0] = mTwiceBaseCache; 195 array[1] = hashes; 196 for (int i=size-1; i>=2; i--) { 197 array[i] = null; 198 } 199 mTwiceBaseCache = array; 200 mTwiceBaseCacheSize++; 201 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 202 + " now have " + mTwiceBaseCacheSize + " entries"); 203 } 204 } 205 } else if (hashes.length == BASE_SIZE) { 206 synchronized (ArraySet.class) { 207 if (mBaseCacheSize < CACHE_SIZE) { 208 array[0] = mBaseCache; 209 array[1] = hashes; 210 for (int i=size-1; i>=2; i--) { 211 array[i] = null; 212 } 213 mBaseCache = array; 214 mBaseCacheSize++; 215 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 216 + " now have " + mBaseCacheSize + " entries"); 217 } 218 } 219 } 220 } 221 222 /** 223 * Create a new empty ArraySet. The default capacity of an array map is 0, and 224 * will grow once items are added to it. 225 */ 226 public ArraySet() { 227 mHashes = EmptyArray.INT; 228 mArray = EmptyArray.OBJECT; 229 mSize = 0; 230 } 231 232 /** 233 * Create a new ArraySet with a given initial capacity. 234 */ 235 public ArraySet(int capacity) { 236 if (capacity == 0) { 237 mHashes = EmptyArray.INT; 238 mArray = EmptyArray.OBJECT; 239 } else { 240 allocArrays(capacity); 241 } 242 mSize = 0; 243 } 244 245 /** 246 * Create a new ArraySet with the mappings from the given ArraySet. 247 */ 248 public ArraySet(ArraySet set) { 249 this(); 250 if (set != null) { 251 addAll(set); 252 } 253 } 254 255 256 /** 257 * Make the array map empty. All storage is released. 258 */ 259 @Override 260 public void clear() { 261 if (mSize != 0) { 262 freeArrays(mHashes, mArray, mSize); 263 mHashes = EmptyArray.INT; 264 mArray = EmptyArray.OBJECT; 265 mSize = 0; 266 } 267 } 268 269 /** 270 * Ensure the array map can hold at least <var>minimumCapacity</var> 271 * items. 272 */ 273 public void ensureCapacity(int minimumCapacity) { 274 if (mHashes.length < minimumCapacity) { 275 final int[] ohashes = mHashes; 276 final Object[] oarray = mArray; 277 allocArrays(minimumCapacity); 278 if (mSize > 0) { 279 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 280 System.arraycopy(oarray, 0, mArray, 0, mSize); 281 } 282 freeArrays(ohashes, oarray, mSize); 283 } 284 } 285 286 /** 287 * Check whether a value exists in the set. 288 * 289 * @param key The value to search for. 290 * @return Returns true if the value exists, else false. 291 */ 292 @Override 293 public boolean contains(Object key) { 294 return indexOf(key) >= 0; 295 } 296 297 /** 298 * Returns the index of a value in the set. 299 * 300 * @param key The value to search for. 301 * @return Returns the index of the value if it exists, else a negative integer. 302 */ 303 public int indexOf(Object key) { 304 return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 305 } 306 307 /** 308 * Return the value at the given index in the array. 309 * @param index The desired index, must be between 0 and {@link #size()}-1. 310 * @return Returns the value stored at the given index. 311 */ 312 public E valueAt(int index) { 313 return (E)mArray[index]; 314 } 315 316 /** 317 * Return true if the array map contains no items. 318 */ 319 @Override 320 public boolean isEmpty() { 321 return mSize <= 0; 322 } 323 324 /** 325 * Adds the specified object to this set. The set is not modified if it 326 * already contains the object. 327 * 328 * @param value the object to add. 329 * @return {@code true} if this set is modified, {@code false} otherwise. 330 * @throws ClassCastException 331 * when the class of the object is inappropriate for this set. 332 */ 333 @Override 334 public boolean add(E value) { 335 final int hash; 336 int index; 337 if (value == null) { 338 hash = 0; 339 index = indexOfNull(); 340 } else { 341 hash = value.hashCode(); 342 index = indexOf(value, hash); 343 } 344 if (index >= 0) { 345 return false; 346 } 347 348 index = ~index; 349 if (mSize >= mHashes.length) { 350 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 351 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 352 353 if (DEBUG) Log.d(TAG, "add: grow from " + mHashes.length + " to " + n); 354 355 final int[] ohashes = mHashes; 356 final Object[] oarray = mArray; 357 allocArrays(n); 358 359 if (mHashes.length > 0) { 360 if (DEBUG) Log.d(TAG, "add: copy 0-" + mSize + " to 0"); 361 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 362 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 363 } 364 365 freeArrays(ohashes, oarray, mSize); 366 } 367 368 if (index < mSize) { 369 if (DEBUG) Log.d(TAG, "add: move " + index + "-" + (mSize-index) 370 + " to " + (index+1)); 371 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 372 System.arraycopy(mArray, index, mArray, index + 1, mSize - index); 373 } 374 375 mHashes[index] = hash; 376 mArray[index] = value; 377 mSize++; 378 return true; 379 } 380 381 /** 382 * Perform a {@link #add(Object)} of all values in <var>array</var> 383 * @param array The array whose contents are to be retrieved. 384 */ 385 public void addAll(ArraySet<? extends E> array) { 386 final int N = array.mSize; 387 ensureCapacity(mSize + N); 388 if (mSize == 0) { 389 if (N > 0) { 390 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 391 System.arraycopy(array.mArray, 0, mArray, 0, N); 392 mSize = N; 393 } 394 } else { 395 for (int i=0; i<N; i++) { 396 add(array.valueAt(i)); 397 } 398 } 399 } 400 401 /** 402 * Removes the specified object from this set. 403 * 404 * @param object the object to remove. 405 * @return {@code true} if this set was modified, {@code false} otherwise. 406 */ 407 @Override 408 public boolean remove(Object object) { 409 final int index = indexOf(object); 410 if (index >= 0) { 411 removeAt(index); 412 return true; 413 } 414 return false; 415 } 416 417 /** 418 * Remove the key/value mapping at the given index. 419 * @param index The desired index, must be between 0 and {@link #size()}-1. 420 * @return Returns the value that was stored at this index. 421 */ 422 public E removeAt(int index) { 423 final Object old = mArray[index]; 424 if (mSize <= 1) { 425 // Now empty. 426 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 427 freeArrays(mHashes, mArray, mSize); 428 mHashes = EmptyArray.INT; 429 mArray = EmptyArray.OBJECT; 430 mSize = 0; 431 } else { 432 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 433 // Shrunk enough to reduce size of arrays. We don't allow it to 434 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 435 // that and BASE_SIZE. 436 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 437 438 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 439 440 final int[] ohashes = mHashes; 441 final Object[] oarray = mArray; 442 allocArrays(n); 443 444 mSize--; 445 if (index > 0) { 446 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 447 System.arraycopy(ohashes, 0, mHashes, 0, index); 448 System.arraycopy(oarray, 0, mArray, 0, index); 449 } 450 if (index < mSize) { 451 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 452 + " to " + index); 453 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 454 System.arraycopy(oarray, index + 1, mArray, index, mSize - index); 455 } 456 } else { 457 mSize--; 458 if (index < mSize) { 459 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 460 + " to " + index); 461 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 462 System.arraycopy(mArray, index + 1, mArray, index, mSize - index); 463 } 464 mArray[mSize] = null; 465 } 466 } 467 return (E)old; 468 } 469 470 /** 471 * Return the number of items in this array map. 472 */ 473 @Override 474 public int size() { 475 return mSize; 476 } 477 478 @Override 479 public Object[] toArray() { 480 Object[] result = new Object[mSize]; 481 System.arraycopy(mArray, 0, result, 0, mSize); 482 return result; 483 } 484 485 @Override 486 public <T> T[] toArray(T[] array) { 487 if (array.length < mSize) { 488 @SuppressWarnings("unchecked") T[] newArray 489 = (T[]) Array.newInstance(array.getClass().getComponentType(), mSize); 490 array = newArray; 491 } 492 System.arraycopy(mArray, 0, array, 0, mSize); 493 if (array.length > mSize) { 494 array[mSize] = null; 495 } 496 return array; 497 } 498 499 /** 500 * {@inheritDoc} 501 * 502 * <p>This implementation returns false if the object is not a set, or 503 * if the sets have different sizes. Otherwise, for each value in this 504 * set, it checks to make sure the value also exists in the other set. 505 * If any value doesn't exist, the method returns false; otherwise, it 506 * returns true. 507 */ 508 @Override 509 public boolean equals(Object object) { 510 if (this == object) { 511 return true; 512 } 513 if (object instanceof Set) { 514 Set<?> set = (Set<?>) object; 515 if (size() != set.size()) { 516 return false; 517 } 518 519 try { 520 for (int i=0; i<mSize; i++) { 521 E mine = valueAt(i); 522 if (!set.contains(mine)) { 523 return false; 524 } 525 } 526 } catch (NullPointerException ignored) { 527 return false; 528 } catch (ClassCastException ignored) { 529 return false; 530 } 531 return true; 532 } 533 return false; 534 } 535 536 /** 537 * {@inheritDoc} 538 */ 539 @Override 540 public int hashCode() { 541 final int[] hashes = mHashes; 542 int result = 0; 543 for (int i = 0, s = mSize; i < s; i++) { 544 result += hashes[i]; 545 } 546 return result; 547 } 548 549 /** 550 * {@inheritDoc} 551 * 552 * <p>This implementation composes a string by iterating over its values. If 553 * this set contains itself as a value, the string "(this Set)" 554 * will appear in its place. 555 */ 556 @Override 557 public String toString() { 558 if (isEmpty()) { 559 return "{}"; 560 } 561 562 StringBuilder buffer = new StringBuilder(mSize * 14); 563 buffer.append('{'); 564 for (int i=0; i<mSize; i++) { 565 if (i > 0) { 566 buffer.append(", "); 567 } 568 Object value = valueAt(i); 569 if (value != this) { 570 buffer.append(value); 571 } else { 572 buffer.append("(this Set)"); 573 } 574 } 575 buffer.append('}'); 576 return buffer.toString(); 577 } 578 579 // ------------------------------------------------------------------------ 580 // Interop with traditional Java containers. Not as efficient as using 581 // specialized collection APIs. 582 // ------------------------------------------------------------------------ 583 584 private MapCollections<E, E> getCollection() { 585 if (mCollections == null) { 586 mCollections = new MapCollections<E, E>() { 587 @Override 588 protected int colGetSize() { 589 return mSize; 590 } 591 592 @Override 593 protected Object colGetEntry(int index, int offset) { 594 return mArray[index]; 595 } 596 597 @Override 598 protected int colIndexOfKey(Object key) { 599 return indexOf(key); 600 } 601 602 @Override 603 protected int colIndexOfValue(Object value) { 604 return indexOf(value); 605 } 606 607 @Override 608 protected Map<E, E> colGetMap() { 609 throw new UnsupportedOperationException("not a map"); 610 } 611 612 @Override 613 protected void colPut(E key, E value) { 614 add(key); 615 } 616 617 @Override 618 protected E colSetValue(int index, E value) { 619 throw new UnsupportedOperationException("not a map"); 620 } 621 622 @Override 623 protected void colRemoveAt(int index) { 624 removeAt(index); 625 } 626 627 @Override 628 protected void colClear() { 629 clear(); 630 } 631 }; 632 } 633 return mCollections; 634 } 635 636 @Override 637 public Iterator<E> iterator() { 638 return getCollection().getKeySet().iterator(); 639 } 640 641 @Override 642 public boolean containsAll(Collection<?> collection) { 643 Iterator<?> it = collection.iterator(); 644 while (it.hasNext()) { 645 if (!contains(it.next())) { 646 return false; 647 } 648 } 649 return true; 650 } 651 652 @Override 653 public boolean addAll(Collection<? extends E> collection) { 654 ensureCapacity(mSize + collection.size()); 655 boolean added = false; 656 for (E value : collection) { 657 added |= add(value); 658 } 659 return added; 660 } 661 662 @Override 663 public boolean removeAll(Collection<?> collection) { 664 boolean removed = false; 665 for (Object value : collection) { 666 removed |= remove(value); 667 } 668 return removed; 669 } 670 671 @Override 672 public boolean retainAll(Collection<?> collection) { 673 boolean removed = false; 674 for (int i=mSize-1; i>=0; i--) { 675 if (!collection.contains(mArray[i])) { 676 removeAt(i); 677 removed = true; 678 } 679 } 680 return removed; 681 } 682 } 683