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 java.lang.reflect.Array; 20import java.util.Collection; 21import java.util.Iterator; 22import java.util.Map; 23import java.util.Set; 24 25/** 26 * ArraySet is a generic set data structure that is designed to be more memory efficient than a 27 * traditional {@link java.util.HashSet}. The design is very similar to 28 * {@link ArrayMap}, with all of the caveats described there. This implementation is 29 * separate from ArrayMap, however, so the Object array contains only one item for each 30 * entry in the set (instead of a pair for a mapping). 31 * 32 * <p>Note that this implementation is not intended to be appropriate for data structures 33 * that may contain large numbers of items. It is generally slower than a traditional 34 * HashSet, since lookups require a binary search and adds and removes require inserting 35 * and deleting entries in the array. For containers holding up to hundreds of items, 36 * the performance difference is not significant, less than 50%.</p> 37 * 38 * <p>Because this container is intended to better balance memory use, unlike most other 39 * standard Java containers it will shrink its array as items are removed from it. Currently 40 * you have no control over this shrinking -- if you set a capacity and then remove an 41 * item, it may reduce the capacity to better match the current size. In the future an 42 * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 43 * 44 * @hide 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 = ContainerHelpers.EMPTY_INTS; 226 mArray = ContainerHelpers.EMPTY_OBJECTS; 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 = ContainerHelpers.EMPTY_INTS; 236 mArray = ContainerHelpers.EMPTY_OBJECTS; 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 set) { 247 this(); 248 if (set != null) { 249 addAll(set); 250 } 251 } 252 253 254 /** 255 * Make the array map empty. All storage is released. 256 */ 257 @Override 258 public void clear() { 259 if (mSize != 0) { 260 freeArrays(mHashes, mArray, mSize); 261 mHashes = ContainerHelpers.EMPTY_INTS; 262 mArray = ContainerHelpers.EMPTY_OBJECTS; 263 mSize = 0; 264 } 265 } 266 267 /** 268 * Ensure the array map can hold at least <var>minimumCapacity</var> 269 * items. 270 */ 271 public void ensureCapacity(int minimumCapacity) { 272 if (mHashes.length < minimumCapacity) { 273 final int[] ohashes = mHashes; 274 final Object[] oarray = mArray; 275 allocArrays(minimumCapacity); 276 if (mSize > 0) { 277 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 278 System.arraycopy(oarray, 0, mArray, 0, mSize); 279 } 280 freeArrays(ohashes, oarray, mSize); 281 } 282 } 283 284 /** 285 * Check whether a value exists in the set. 286 * 287 * @param key The value to search for. 288 * @return Returns true if the value exists, else false. 289 */ 290 @Override 291 public boolean contains(Object key) { 292 return key == null ? (indexOfNull() >= 0) : (indexOf(key, key.hashCode()) >= 0); 293 } 294 295 /** 296 * Return the value at the given index in the array. 297 * @param index The desired index, must be between 0 and {@link #size()}-1. 298 * @return Returns the value stored at the given index. 299 */ 300 public E valueAt(int index) { 301 return (E)mArray[index]; 302 } 303 304 /** 305 * Return true if the array map contains no items. 306 */ 307 @Override 308 public boolean isEmpty() { 309 return mSize <= 0; 310 } 311 312 /** 313 * Adds the specified object to this set. The set is not modified if it 314 * already contains the object. 315 * 316 * @param value the object to add. 317 * @return {@code true} if this set is modified, {@code false} otherwise. 318 * @throws ClassCastException 319 * when the class of the object is inappropriate for this set. 320 */ 321 @Override 322 public boolean add(E value) { 323 final int hash; 324 int index; 325 if (value == null) { 326 hash = 0; 327 index = indexOfNull(); 328 } else { 329 hash = value.hashCode(); 330 index = indexOf(value, hash); 331 } 332 if (index >= 0) { 333 return false; 334 } 335 336 index = ~index; 337 if (mSize >= mHashes.length) { 338 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 339 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 340 341 if (DEBUG) Log.d(TAG, "add: grow from " + mHashes.length + " to " + n); 342 343 final int[] ohashes = mHashes; 344 final Object[] oarray = mArray; 345 allocArrays(n); 346 347 if (mHashes.length > 0) { 348 if (DEBUG) Log.d(TAG, "add: copy 0-" + mSize + " to 0"); 349 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 350 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 351 } 352 353 freeArrays(ohashes, oarray, mSize); 354 } 355 356 if (index < mSize) { 357 if (DEBUG) Log.d(TAG, "add: move " + index + "-" + (mSize-index) 358 + " to " + (index+1)); 359 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 360 System.arraycopy(mArray, index, mArray, index + 1, mSize - index); 361 } 362 363 mHashes[index] = hash; 364 mArray[index] = value; 365 mSize++; 366 return true; 367 } 368 369 /** 370 * Perform a {@link #add(Object)} of all values in <var>array</var> 371 * @param array The array whose contents are to be retrieved. 372 */ 373 public void putAll(ArraySet<? extends E> array) { 374 final int N = array.mSize; 375 ensureCapacity(mSize + N); 376 if (mSize == 0) { 377 if (N > 0) { 378 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 379 System.arraycopy(array.mArray, 0, mArray, 0, N); 380 mSize = N; 381 } 382 } else { 383 for (int i=0; i<N; i++) { 384 add(array.valueAt(i)); 385 } 386 } 387 } 388 389 /** 390 * Removes the specified object from this set. 391 * 392 * @param object the object to remove. 393 * @return {@code true} if this set was modified, {@code false} otherwise. 394 */ 395 @Override 396 public boolean remove(Object object) { 397 int index = object == null ? indexOfNull() : indexOf(object, object.hashCode()); 398 if (index >= 0) { 399 removeAt(index); 400 return true; 401 } 402 return false; 403 } 404 405 /** 406 * Remove the key/value mapping at the given index. 407 * @param index The desired index, must be between 0 and {@link #size()}-1. 408 * @return Returns the value that was stored at this index. 409 */ 410 public E removeAt(int index) { 411 final Object old = mArray[index]; 412 if (mSize <= 1) { 413 // Now empty. 414 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 415 freeArrays(mHashes, mArray, mSize); 416 mHashes = ContainerHelpers.EMPTY_INTS; 417 mArray = ContainerHelpers.EMPTY_OBJECTS; 418 mSize = 0; 419 } else { 420 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 421 // Shrunk enough to reduce size of arrays. We don't allow it to 422 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 423 // that and BASE_SIZE. 424 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 425 426 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 427 428 final int[] ohashes = mHashes; 429 final Object[] oarray = mArray; 430 allocArrays(n); 431 432 mSize--; 433 if (index > 0) { 434 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 435 System.arraycopy(ohashes, 0, mHashes, 0, index); 436 System.arraycopy(oarray, 0, mArray, 0, index); 437 } 438 if (index < mSize) { 439 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 440 + " to " + index); 441 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 442 System.arraycopy(oarray, index + 1, mArray, index, mSize - index); 443 } 444 } else { 445 mSize--; 446 if (index < mSize) { 447 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 448 + " to " + index); 449 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 450 System.arraycopy(mArray, index + 1, mArray, index, mSize - index); 451 } 452 mArray[mSize] = null; 453 } 454 } 455 return (E)old; 456 } 457 458 /** 459 * Return the number of items in this array map. 460 */ 461 @Override 462 public int size() { 463 return mSize; 464 } 465 466 @Override 467 public Object[] toArray() { 468 Object[] result = new Object[mSize]; 469 System.arraycopy(mArray, 0, result, 0, mSize); 470 return result; 471 } 472 473 @Override 474 public <T> T[] toArray(T[] array) { 475 if (array.length < mSize) { 476 @SuppressWarnings("unchecked") T[] newArray 477 = (T[]) Array.newInstance(array.getClass().getComponentType(), mSize); 478 array = newArray; 479 } 480 System.arraycopy(mArray, 0, array, 0, mSize); 481 if (array.length > mSize) { 482 array[mSize] = null; 483 } 484 return array; 485 } 486 487 /** 488 * {@inheritDoc} 489 * 490 * <p>This implementation returns false if the object is not a set, or 491 * if the sets have different sizes. Otherwise, for each value in this 492 * set, it checks to make sure the value also exists in the other set. 493 * If any value doesn't exist, the method returns false; otherwise, it 494 * returns true. 495 */ 496 @Override 497 public boolean equals(Object object) { 498 if (this == object) { 499 return true; 500 } 501 if (object instanceof Set) { 502 Set<?> set = (Set<?>) object; 503 if (size() != set.size()) { 504 return false; 505 } 506 507 try { 508 for (int i=0; i<mSize; i++) { 509 E mine = valueAt(i); 510 if (!set.contains(mine)) { 511 return false; 512 } 513 } 514 } catch (NullPointerException ignored) { 515 return false; 516 } catch (ClassCastException ignored) { 517 return false; 518 } 519 return true; 520 } 521 return false; 522 } 523 524 /** 525 * {@inheritDoc} 526 */ 527 @Override 528 public int hashCode() { 529 final int[] hashes = mHashes; 530 int result = 0; 531 for (int i = 0, s = mSize; i < s; i++) { 532 result += hashes[i]; 533 } 534 return result; 535 } 536 537 /** 538 * {@inheritDoc} 539 * 540 * <p>This implementation composes a string by iterating over its values. If 541 * this set contains itself as a value, the string "(this Set)" 542 * will appear in its place. 543 */ 544 @Override 545 public String toString() { 546 if (isEmpty()) { 547 return "{}"; 548 } 549 550 StringBuilder buffer = new StringBuilder(mSize * 14); 551 buffer.append('{'); 552 for (int i=0; i<mSize; i++) { 553 if (i > 0) { 554 buffer.append(", "); 555 } 556 Object value = valueAt(i); 557 if (value != this) { 558 buffer.append(value); 559 } else { 560 buffer.append("(this Set)"); 561 } 562 } 563 buffer.append('}'); 564 return buffer.toString(); 565 } 566 567 // ------------------------------------------------------------------------ 568 // Interop with traditional Java containers. Not as efficient as using 569 // specialized collection APIs. 570 // ------------------------------------------------------------------------ 571 572 private MapCollections<E, E> getCollection() { 573 if (mCollections == null) { 574 mCollections = new MapCollections<E, E>() { 575 @Override 576 protected int colGetSize() { 577 return mSize; 578 } 579 580 @Override 581 protected Object colGetEntry(int index, int offset) { 582 return mArray[index]; 583 } 584 585 @Override 586 protected int colIndexOfKey(Object key) { 587 return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 588 } 589 590 @Override 591 protected int colIndexOfValue(Object value) { 592 return value == null ? indexOfNull() : indexOf(value, value.hashCode()); 593 } 594 595 @Override 596 protected Map<E, E> colGetMap() { 597 throw new UnsupportedOperationException("not a map"); 598 } 599 600 @Override 601 protected void colPut(E key, E value) { 602 add(key); 603 } 604 605 @Override 606 protected E colSetValue(int index, E value) { 607 throw new UnsupportedOperationException("not a map"); 608 } 609 610 @Override 611 protected void colRemoveAt(int index) { 612 removeAt(index); 613 } 614 615 @Override 616 protected void colClear() { 617 clear(); 618 } 619 }; 620 } 621 return mCollections; 622 } 623 624 @Override 625 public Iterator<E> iterator() { 626 return getCollection().getKeySet().iterator(); 627 } 628 629 @Override 630 public boolean containsAll(Collection<?> collection) { 631 Iterator<?> it = collection.iterator(); 632 while (it.hasNext()) { 633 if (!contains(it.next())) { 634 return false; 635 } 636 } 637 return true; 638 } 639 640 @Override 641 public boolean addAll(Collection<? extends E> collection) { 642 ensureCapacity(mSize + collection.size()); 643 boolean added = false; 644 for (E value : collection) { 645 added |= add(value); 646 } 647 return added; 648 } 649 650 @Override 651 public boolean removeAll(Collection<?> collection) { 652 boolean removed = false; 653 for (Object value : collection) { 654 removed |= remove(value); 655 } 656 return removed; 657 } 658 659 @Override 660 public boolean retainAll(Collection<?> collection) { 661 boolean removed = false; 662 for (int i=mSize-1; i>=0; i--) { 663 if (!collection.contains(mArray[i])) { 664 removeAt(i); 665 removed = true; 666 } 667 } 668 return removed; 669 } 670} 671