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