001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkNonnegative; 022import static java.util.Objects.requireNonNull; 023 024import com.google.common.annotations.Beta; 025import com.google.common.annotations.GwtCompatible; 026import com.google.common.annotations.VisibleForTesting; 027import com.google.common.math.IntMath; 028import com.google.common.primitives.Ints; 029import com.google.errorprone.annotations.CanIgnoreReturnValue; 030import com.google.errorprone.annotations.concurrent.LazyInit; 031import com.google.j2objc.annotations.RetainedWith; 032import java.io.Serializable; 033import java.math.RoundingMode; 034import java.util.Arrays; 035import java.util.Collection; 036import java.util.Collections; 037import java.util.EnumSet; 038import java.util.Iterator; 039import java.util.Set; 040import java.util.SortedSet; 041import java.util.Spliterator; 042import java.util.function.Consumer; 043import java.util.stream.Collector; 044import javax.annotation.CheckForNull; 045import org.checkerframework.checker.nullness.qual.Nullable; 046 047/** 048 * A {@link Set} whose contents will never change, with many other important properties detailed at 049 * {@link ImmutableCollection}. 050 * 051 * @since 2.0 052 */ 053@GwtCompatible(serializable = true, emulated = true) 054@SuppressWarnings("serial") // we're overriding default serialization 055@ElementTypesAreNonnullByDefault 056public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> { 057 static final int SPLITERATOR_CHARACTERISTICS = 058 ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT; 059 060 /** 061 * Returns a {@code Collector} that accumulates the input elements into a new {@code 062 * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if 063 * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first 064 * duplicate in encounter order will appear in the result. 065 * 066 * @since 21.0 067 */ 068 public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() { 069 return CollectCollectors.toImmutableSet(); 070 } 071 072 /** 073 * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code 074 * consistency, and because the return type conveys the immutability guarantee. 075 * 076 * <p><b>Performance note:</b> the instance returned is a singleton. 077 */ 078 @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es) 079 public static <E> ImmutableSet<E> of() { 080 return (ImmutableSet<E>) RegularImmutableSet.EMPTY; 081 } 082 083 /** 084 * Returns an immutable set containing {@code element}. Preferred over {@link 085 * Collections#singleton} for code consistency, {@code null} rejection, and because the return 086 * type conveys the immutability guarantee. 087 */ 088 public static <E> ImmutableSet<E> of(E element) { 089 return new SingletonImmutableSet<E>(element); 090 } 091 092 /** 093 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 094 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 095 * the first are ignored. 096 */ 097 public static <E> ImmutableSet<E> of(E e1, E e2) { 098 return construct(2, 2, e1, e2); 099 } 100 101 /** 102 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 103 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 104 * the first are ignored. 105 */ 106 public static <E> ImmutableSet<E> of(E e1, E e2, E e3) { 107 return construct(3, 3, e1, e2, e3); 108 } 109 110 /** 111 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 112 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 113 * the first are ignored. 114 */ 115 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) { 116 return construct(4, 4, e1, e2, e3, e4); 117 } 118 119 /** 120 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 121 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 122 * the first are ignored. 123 */ 124 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) { 125 return construct(5, 5, e1, e2, e3, e4, e5); 126 } 127 128 /** 129 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 130 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 131 * the first are ignored. 132 * 133 * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}. 134 * 135 * @since 3.0 (source-compatible since 2.0) 136 */ 137 @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning. 138 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) { 139 checkArgument( 140 others.length <= Integer.MAX_VALUE - 6, "the total number of elements must fit in an int"); 141 final int paramCount = 6; 142 Object[] elements = new Object[paramCount + others.length]; 143 elements[0] = e1; 144 elements[1] = e2; 145 elements[2] = e3; 146 elements[3] = e4; 147 elements[4] = e5; 148 elements[5] = e6; 149 System.arraycopy(others, 0, elements, paramCount, others.length); 150 return construct(elements.length, elements.length, elements); 151 } 152 153 /** 154 * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array, 155 * which we have no particular reason to believe does or does not contain duplicates. If {@code k} 156 * is the size of the returned {@code ImmutableSet}, then the unique elements of {@code elements} 157 * will be in the first {@code k} positions, and {@code elements[i] == null} for {@code k <= i < 158 * n}. 159 * 160 * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code 161 * elements} contains no duplicates, {@code elements} may be used without copying in the returned 162 * {@code ImmutableSet}, in which case the caller must not modify it. 163 * 164 * <p>{@code elements} may contain only values of type {@code E}. 165 * 166 * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null 167 */ 168 private static <E> ImmutableSet<E> constructUnknownDuplication(int n, Object... elements) { 169 // Guess the size is "halfway between" all duplicates and no duplicates, on a log scale. 170 return construct( 171 n, 172 Math.max( 173 ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY, 174 IntMath.sqrt(n, RoundingMode.CEILING)), 175 elements); 176 } 177 178 /** 179 * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If 180 * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code 181 * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code 182 * k <= i < n}. 183 * 184 * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code 185 * elements} contains no duplicates, {@code elements} may be used without copying in the returned 186 * {@code ImmutableSet}, in which case it may no longer be modified. 187 * 188 * <p>{@code elements} may contain only values of type {@code E}. 189 * 190 * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null 191 */ 192 private static <E> ImmutableSet<E> construct(int n, int expectedSize, Object... elements) { 193 switch (n) { 194 case 0: 195 return of(); 196 case 1: 197 @SuppressWarnings("unchecked") // safe; elements contains only E's 198 E elem = (E) elements[0]; 199 return of(elem); 200 default: 201 SetBuilderImpl<E> builder = new RegularSetBuilderImpl<E>(expectedSize); 202 for (int i = 0; i < n; i++) { 203 @SuppressWarnings("unchecked") 204 E e = (E) checkNotNull(elements[i]); 205 builder = builder.add(e); 206 } 207 return builder.review().build(); 208 } 209 } 210 211 /** 212 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 213 * each appears first in the source collection. 214 * 215 * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation 216 * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once. 217 * This reduces the expense of habitually making defensive copies at API boundaries. However, the 218 * precise conditions for skipping the copy operation are undefined. 219 * 220 * @throws NullPointerException if any of {@code elements} is null 221 * @since 7.0 (source-compatible since 2.0) 222 */ 223 public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) { 224 /* 225 * TODO(lowasser): consider checking for ImmutableAsList here 226 * TODO(lowasser): consider checking for Multiset here 227 */ 228 // Don't refer to ImmutableSortedSet by name so it won't pull in all that code 229 if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) { 230 @SuppressWarnings("unchecked") // all supported methods are covariant 231 ImmutableSet<E> set = (ImmutableSet<E>) elements; 232 if (!set.isPartialView()) { 233 return set; 234 } 235 } else if (elements instanceof EnumSet) { 236 return copyOfEnumSet((EnumSet) elements); 237 } 238 Object[] array = elements.toArray(); 239 if (elements instanceof Set) { 240 // assume probably no duplicates (though it might be using different equality semantics) 241 return construct(array.length, array.length, array); 242 } else { 243 return constructUnknownDuplication(array.length, array); 244 } 245 } 246 247 /** 248 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 249 * each appears first in the source iterable. This method iterates over {@code elements} only 250 * once. 251 * 252 * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation 253 * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only 254 * once. This reduces the expense of habitually making defensive copies at API boundaries. 255 * However, the precise conditions for skipping the copy operation are undefined. 256 * 257 * @throws NullPointerException if any of {@code elements} is null 258 */ 259 public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) { 260 return (elements instanceof Collection) 261 ? copyOf((Collection<? extends E>) elements) 262 : copyOf(elements.iterator()); 263 } 264 265 /** 266 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 267 * each appears first in the source iterator. 268 * 269 * @throws NullPointerException if any of {@code elements} is null 270 */ 271 public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) { 272 // We special-case for 0 or 1 elements, but anything further is madness. 273 if (!elements.hasNext()) { 274 return of(); 275 } 276 E first = elements.next(); 277 if (!elements.hasNext()) { 278 return of(first); 279 } else { 280 return new ImmutableSet.Builder<E>().add(first).addAll(elements).build(); 281 } 282 } 283 284 /** 285 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 286 * each appears first in the source array. 287 * 288 * @throws NullPointerException if any of {@code elements} is null 289 * @since 3.0 290 */ 291 public static <E> ImmutableSet<E> copyOf(E[] elements) { 292 switch (elements.length) { 293 case 0: 294 return of(); 295 case 1: 296 return of(elements[0]); 297 default: 298 return constructUnknownDuplication(elements.length, elements.clone()); 299 } 300 } 301 302 @SuppressWarnings("rawtypes") // necessary to compile against Java 8 303 private static ImmutableSet copyOfEnumSet(EnumSet enumSet) { 304 return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet)); 305 } 306 307 ImmutableSet() {} 308 309 /** Returns {@code true} if the {@code hashCode()} method runs quickly. */ 310 boolean isHashCodeFast() { 311 return false; 312 } 313 314 @Override 315 public boolean equals(@CheckForNull Object object) { 316 if (object == this) { 317 return true; 318 } 319 if (object instanceof ImmutableSet 320 && isHashCodeFast() 321 && ((ImmutableSet<?>) object).isHashCodeFast() 322 && hashCode() != object.hashCode()) { 323 return false; 324 } 325 return Sets.equalsImpl(this, object); 326 } 327 328 @Override 329 public int hashCode() { 330 return Sets.hashCodeImpl(this); 331 } 332 333 // This declaration is needed to make Set.iterator() and 334 // ImmutableCollection.iterator() consistent. 335 @Override 336 public abstract UnmodifiableIterator<E> iterator(); 337 338 @GwtCompatible 339 abstract static class CachingAsList<E> extends ImmutableSet<E> { 340 @LazyInit @RetainedWith @CheckForNull private transient ImmutableList<E> asList; 341 342 @Override 343 public ImmutableList<E> asList() { 344 ImmutableList<E> result = asList; 345 if (result == null) { 346 return asList = createAsList(); 347 } else { 348 return result; 349 } 350 } 351 352 ImmutableList<E> createAsList() { 353 return new RegularImmutableAsList<E>(this, toArray()); 354 } 355 } 356 357 abstract static class Indexed<E> extends CachingAsList<E> { 358 abstract E get(int index); 359 360 @Override 361 public UnmodifiableIterator<E> iterator() { 362 return asList().iterator(); 363 } 364 365 @Override 366 public Spliterator<E> spliterator() { 367 return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get); 368 } 369 370 @Override 371 public void forEach(Consumer<? super E> consumer) { 372 checkNotNull(consumer); 373 int n = size(); 374 for (int i = 0; i < n; i++) { 375 consumer.accept(get(i)); 376 } 377 } 378 379 @Override 380 int copyIntoArray(@Nullable Object[] dst, int offset) { 381 return asList().copyIntoArray(dst, offset); 382 } 383 384 @Override 385 ImmutableList<E> createAsList() { 386 return new ImmutableAsList<E>() { 387 @Override 388 public E get(int index) { 389 return Indexed.this.get(index); 390 } 391 392 @Override 393 Indexed<E> delegateCollection() { 394 return Indexed.this; 395 } 396 }; 397 } 398 } 399 400 /* 401 * This class is used to serialize all ImmutableSet instances, except for 402 * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It 403 * captures their "logical contents" and they are reconstructed using public 404 * static factories. This is necessary to ensure that the existence of a 405 * particular implementation type is an implementation detail. 406 */ 407 private static class SerializedForm implements Serializable { 408 final Object[] elements; 409 410 SerializedForm(Object[] elements) { 411 this.elements = elements; 412 } 413 414 Object readResolve() { 415 return copyOf(elements); 416 } 417 418 private static final long serialVersionUID = 0; 419 } 420 421 @Override 422 Object writeReplace() { 423 return new SerializedForm(toArray()); 424 } 425 426 /** 427 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 428 * Builder} constructor. 429 */ 430 public static <E> Builder<E> builder() { 431 return new Builder<E>(); 432 } 433 434 /** 435 * Returns a new builder, expecting the specified number of distinct elements to be added. 436 * 437 * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder 438 * before {@link Builder#build} is called, the builder is likely to perform better than an unsized 439 * {@link #builder()} would have. 440 * 441 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, 442 * but not exactly, the number of distinct elements added to the builder. 443 * 444 * @since 23.1 445 */ 446 @Beta 447 public static <E> Builder<E> builderWithExpectedSize(int expectedSize) { 448 checkNonnegative(expectedSize, "expectedSize"); 449 return new Builder<E>(expectedSize); 450 } 451 452 /** 453 * A builder for creating {@code ImmutableSet} instances. Example: 454 * 455 * <pre>{@code 456 * static final ImmutableSet<Color> GOOGLE_COLORS = 457 * ImmutableSet.<Color>builder() 458 * .addAll(WEBSAFE_COLORS) 459 * .add(new Color(0, 191, 255)) 460 * .build(); 461 * }</pre> 462 * 463 * <p>Elements appear in the resulting set in the same order they were first added to the builder. 464 * 465 * <p>Building does not change the state of the builder, so it is still possible to add more 466 * elements and to build again. 467 * 468 * @since 2.0 469 */ 470 public static class Builder<E> extends ImmutableCollection.Builder<E> { 471 /* 472 * `impl` is null only for instances of the subclass, ImmutableSortedSet.Builder. That subclass 473 * overrides all the methods that access it here. Thus, all the methods here can safely assume 474 * that this field is non-null. 475 */ 476 @CheckForNull private SetBuilderImpl<E> impl; 477 boolean forceCopy; 478 479 public Builder() { 480 this(0); 481 } 482 483 Builder(int capacity) { 484 if (capacity > 0) { 485 impl = new RegularSetBuilderImpl<E>(capacity); 486 } else { 487 impl = EmptySetBuilderImpl.instance(); 488 } 489 } 490 491 Builder(@SuppressWarnings("unused") boolean subclass) { 492 this.impl = null; // unused 493 } 494 495 @VisibleForTesting 496 void forceJdk() { 497 requireNonNull(impl); // see the comment on the field 498 this.impl = new JdkBackedSetBuilderImpl<E>(impl); 499 } 500 501 final void copyIfNecessary() { 502 if (forceCopy) { 503 copy(); 504 forceCopy = false; 505 } 506 } 507 508 void copy() { 509 requireNonNull(impl); // see the comment on the field 510 impl = impl.copy(); 511 } 512 513 @Override 514 @CanIgnoreReturnValue 515 public Builder<E> add(E element) { 516 requireNonNull(impl); // see the comment on the field 517 checkNotNull(element); 518 copyIfNecessary(); 519 impl = impl.add(element); 520 return this; 521 } 522 523 @Override 524 @CanIgnoreReturnValue 525 public Builder<E> add(E... elements) { 526 super.add(elements); 527 return this; 528 } 529 530 /** 531 * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate 532 * elements (only the first duplicate element is added). 533 * 534 * @param elements the elements to add 535 * @return this {@code Builder} object 536 * @throws NullPointerException if {@code elements} is null or contains a null element 537 */ 538 @Override 539 @CanIgnoreReturnValue 540 public Builder<E> addAll(Iterable<? extends E> elements) { 541 super.addAll(elements); 542 return this; 543 } 544 545 @Override 546 @CanIgnoreReturnValue 547 public Builder<E> addAll(Iterator<? extends E> elements) { 548 super.addAll(elements); 549 return this; 550 } 551 552 Builder<E> combine(Builder<E> other) { 553 requireNonNull(impl); 554 requireNonNull(other.impl); 555 /* 556 * For discussion of requireNonNull, see the comment on the field. 557 * 558 * (And I don't believe there's any situation in which we call x.combine(y) when x is a plain 559 * ImmutableSet.Builder but y is an ImmutableSortedSet.Builder (or vice versa). Certainly 560 * ImmutableSortedSet.Builder.combine() is written as if its argument will never be a plain 561 * ImmutableSet.Builder: It casts immediately to ImmutableSortedSet.Builder.) 562 */ 563 copyIfNecessary(); 564 this.impl = this.impl.combine(other.impl); 565 return this; 566 } 567 568 @Override 569 public ImmutableSet<E> build() { 570 requireNonNull(impl); // see the comment on the field 571 forceCopy = true; 572 impl = impl.review(); 573 return impl.build(); 574 } 575 } 576 577 /** Swappable internal implementation of an ImmutableSet.Builder. */ 578 private abstract static class SetBuilderImpl<E> { 579 // The first `distinct` elements are non-null. 580 // Since we can never access null elements, we don't mark this nullable. 581 E[] dedupedElements; 582 int distinct; 583 584 @SuppressWarnings("unchecked") 585 SetBuilderImpl(int expectedCapacity) { 586 this.dedupedElements = (E[]) new Object[expectedCapacity]; 587 this.distinct = 0; 588 } 589 590 /** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */ 591 SetBuilderImpl(SetBuilderImpl<E> toCopy) { 592 this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length); 593 this.distinct = toCopy.distinct; 594 } 595 596 /** 597 * Resizes internal data structures if necessary to store the specified number of distinct 598 * elements. 599 */ 600 private void ensureCapacity(int minCapacity) { 601 if (minCapacity > dedupedElements.length) { 602 int newCapacity = 603 ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity); 604 dedupedElements = Arrays.copyOf(dedupedElements, newCapacity); 605 } 606 } 607 608 /** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */ 609 final void addDedupedElement(E e) { 610 ensureCapacity(distinct + 1); 611 dedupedElements[distinct++] = e; 612 } 613 614 /** 615 * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned 616 * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected. 617 */ 618 abstract SetBuilderImpl<E> add(E e); 619 620 /** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */ 621 final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) { 622 SetBuilderImpl<E> result = this; 623 for (int i = 0; i < other.distinct; i++) { 624 /* 625 * requireNonNull is safe because we ensure that the first `distinct` elements have been 626 * populated. 627 */ 628 result = result.add(requireNonNull(other.dedupedElements[i])); 629 } 630 return result; 631 } 632 633 /** 634 * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not 635 * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build(). 636 */ 637 abstract SetBuilderImpl<E> copy(); 638 639 /** 640 * Call this before build(). Does a final check on the internal data structures, e.g. shrinking 641 * unnecessarily large structures or detecting previously unnoticed hash flooding. 642 */ 643 SetBuilderImpl<E> review() { 644 return this; 645 } 646 647 abstract ImmutableSet<E> build(); 648 } 649 650 private static final class EmptySetBuilderImpl<E> extends SetBuilderImpl<E> { 651 private static final EmptySetBuilderImpl<Object> INSTANCE = new EmptySetBuilderImpl<>(); 652 653 @SuppressWarnings("unchecked") 654 static <E> SetBuilderImpl<E> instance() { 655 return (SetBuilderImpl<E>) INSTANCE; 656 } 657 658 private EmptySetBuilderImpl() { 659 super(0); 660 } 661 662 @Override 663 SetBuilderImpl<E> add(E e) { 664 return new RegularSetBuilderImpl<E>(Builder.DEFAULT_INITIAL_CAPACITY).add(e); 665 } 666 667 @Override 668 SetBuilderImpl<E> copy() { 669 return this; 670 } 671 672 @Override 673 ImmutableSet<E> build() { 674 return ImmutableSet.of(); 675 } 676 } 677 678 // We use power-of-2 tables, and this is the highest int that's a power of 2 679 static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO; 680 681 // Represents how tightly we can pack things, as a maximum. 682 private static final double DESIRED_LOAD_FACTOR = 0.7; 683 684 // If the set has this many elements, it will "max out" the table size 685 private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR); 686 687 /** 688 * Returns an array size suitable for the backing array of a hash table that uses open addressing 689 * with linear probing in its implementation. The returned size is the smallest power of two that 690 * can hold setSize elements with the desired load factor. Always returns at least setSize + 2. 691 */ 692 // TODO(cpovirk): Move to Hashing or something, since it's used elsewhere in the Android version. 693 static int chooseTableSize(int setSize) { 694 setSize = Math.max(setSize, 2); 695 // Correct the size for open addressing to match desired load factor. 696 if (setSize < CUTOFF) { 697 // Round up to the next highest power of 2. 698 int tableSize = Integer.highestOneBit(setSize - 1) << 1; 699 while (tableSize * DESIRED_LOAD_FACTOR < setSize) { 700 tableSize <<= 1; 701 } 702 return tableSize; 703 } 704 705 // The table can't be completely full or we'll get infinite reprobes 706 checkArgument(setSize < MAX_TABLE_SIZE, "collection too large"); 707 return MAX_TABLE_SIZE; 708 } 709 710 /** 711 * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash 712 * table and deduplicating elements as they come, so it only allocates O(max(distinct, 713 * expectedCapacity)) rather than O(calls to add). 714 * 715 * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to 716 * JdkBackedSetBuilderImpl. 717 */ 718 private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> { 719 // null until at least two elements are present 720 private @Nullable Object @Nullable [] hashTable; 721 private int maxRunBeforeFallback; 722 private int expandTableThreshold; 723 private int hashCode; 724 725 RegularSetBuilderImpl(int expectedCapacity) { 726 super(expectedCapacity); 727 this.hashTable = null; 728 this.maxRunBeforeFallback = 0; 729 this.expandTableThreshold = 0; 730 } 731 732 RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) { 733 super(toCopy); 734 this.hashTable = (toCopy.hashTable == null) ? null : toCopy.hashTable.clone(); 735 this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback; 736 this.expandTableThreshold = toCopy.expandTableThreshold; 737 this.hashCode = toCopy.hashCode; 738 } 739 740 @Override 741 SetBuilderImpl<E> add(E e) { 742 checkNotNull(e); 743 if (hashTable == null) { 744 if (distinct == 0) { 745 addDedupedElement(e); 746 return this; 747 } else { 748 ensureTableCapacity(dedupedElements.length); 749 E elem = dedupedElements[0]; 750 distinct--; 751 return insertInHashTable(elem).add(e); 752 } 753 } 754 return insertInHashTable(e); 755 } 756 757 private SetBuilderImpl<E> insertInHashTable(E e) { 758 requireNonNull(hashTable); 759 int eHash = e.hashCode(); 760 int i0 = Hashing.smear(eHash); 761 int mask = hashTable.length - 1; 762 for (int i = i0; i - i0 < maxRunBeforeFallback; i++) { 763 int index = i & mask; 764 Object tableEntry = hashTable[index]; 765 if (tableEntry == null) { 766 addDedupedElement(e); 767 hashTable[index] = e; 768 hashCode += eHash; 769 ensureTableCapacity(distinct); // rebuilds table if necessary 770 return this; 771 } else if (tableEntry.equals(e)) { // not a new element, ignore 772 return this; 773 } 774 } 775 // we fell out of the loop due to a long run; fall back to JDK impl 776 return new JdkBackedSetBuilderImpl<E>(this).add(e); 777 } 778 779 @Override 780 SetBuilderImpl<E> copy() { 781 return new RegularSetBuilderImpl<E>(this); 782 } 783 784 @Override 785 SetBuilderImpl<E> review() { 786 if (hashTable == null) { 787 return this; 788 } 789 int targetTableSize = chooseTableSize(distinct); 790 if (targetTableSize * 2 < hashTable.length) { 791 hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct); 792 maxRunBeforeFallback = maxRunBeforeFallback(targetTableSize); 793 expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * targetTableSize); 794 } 795 return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this; 796 } 797 798 @Override 799 ImmutableSet<E> build() { 800 switch (distinct) { 801 case 0: 802 return of(); 803 case 1: 804 /* 805 * requireNonNull is safe because we ensure that the first `distinct` elements have been 806 * populated. 807 */ 808 return of(requireNonNull(dedupedElements[0])); 809 default: 810 /* 811 * The suppression is safe because we ensure that the first `distinct` elements have been 812 * populated. 813 */ 814 @SuppressWarnings("nullness") 815 Object[] elements = 816 (distinct == dedupedElements.length) 817 ? dedupedElements 818 : Arrays.copyOf(dedupedElements, distinct); 819 return new RegularImmutableSet<E>( 820 elements, hashCode, requireNonNull(hashTable), hashTable.length - 1); 821 } 822 } 823 824 /** Builds a new open-addressed hash table from the first n objects in elements. */ 825 static @Nullable Object[] rebuildHashTable(int newTableSize, Object[] elements, int n) { 826 @Nullable Object[] hashTable = new @Nullable Object[newTableSize]; 827 int mask = hashTable.length - 1; 828 for (int i = 0; i < n; i++) { 829 // requireNonNull is safe because we ensure that the first n elements have been populated. 830 Object e = requireNonNull(elements[i]); 831 int j0 = Hashing.smear(e.hashCode()); 832 for (int j = j0; ; j++) { 833 int index = j & mask; 834 if (hashTable[index] == null) { 835 hashTable[index] = e; 836 break; 837 } 838 } 839 } 840 return hashTable; 841 } 842 843 void ensureTableCapacity(int minCapacity) { 844 int newTableSize; 845 if (hashTable == null) { 846 newTableSize = chooseTableSize(minCapacity); 847 hashTable = new Object[newTableSize]; 848 } else if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) { 849 newTableSize = hashTable.length * 2; 850 hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct); 851 } else { 852 return; 853 } 854 maxRunBeforeFallback = maxRunBeforeFallback(newTableSize); 855 expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize); 856 } 857 858 /** 859 * We attempt to detect deliberate hash flooding attempts. If one is detected, we fall back to a 860 * wrapper around j.u.HashSet, which has built in flooding protection. MAX_RUN_MULTIPLIER was 861 * determined experimentally to match our desired probability of false positives. 862 */ 863 // NB: yes, this is surprisingly high, but that's what the experiments said was necessary 864 // Raising this number slows the worst-case contains behavior, speeds up hashFloodingDetected, 865 // and reduces the false-positive probability. 866 static final int MAX_RUN_MULTIPLIER = 13; 867 868 /** 869 * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n / 870 * log n) on average. 871 * 872 * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many 873 * exactly matching hash codes, which would cause construction to take O(n^2), but can't detect 874 * e.g. hash codes adversarially designed to go into ascending table locations, which keeps 875 * construction O(n) (as desired) but then can have O(n) queries later. 876 * 877 * <p>If this returns false, then no query can take more than O(log n). 878 * 879 * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains 880 * operations take expected O(1) time but with high probability take O(log n) for at least some 881 * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis) 882 * 883 * <p>This method may return {@code true} even on truly random input, but {@code 884 * ImmutableSetTest} tests that the probability of that is low. 885 */ 886 static boolean hashFloodingDetected(@Nullable Object[] hashTable) { 887 int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length); 888 int mask = hashTable.length - 1; 889 890 // Invariant: all elements at indices in [knownRunStart, knownRunEnd) are nonnull. 891 // If knownRunStart == knownRunEnd, this is vacuously true. 892 // When knownRunEnd exceeds hashTable.length, it "wraps", detecting runs around the end 893 // of the table. 894 int knownRunStart = 0; 895 int knownRunEnd = 0; 896 897 outerLoop: 898 while (knownRunStart < hashTable.length) { 899 if (knownRunStart == knownRunEnd && hashTable[knownRunStart] == null) { 900 if (hashTable[(knownRunStart + maxRunBeforeFallback - 1) & mask] == null) { 901 // There are only maxRunBeforeFallback - 1 elements between here and there, 902 // so even if they were all nonnull, we wouldn't detect a hash flood. Therefore, 903 // we can skip them all. 904 knownRunStart += maxRunBeforeFallback; 905 } else { 906 knownRunStart++; // the only case in which maxRunEnd doesn't increase by mRBF 907 // happens about f * (1-f) for f = DESIRED_LOAD_FACTOR, so around 21% of the time 908 } 909 knownRunEnd = knownRunStart; 910 } else { 911 for (int j = knownRunStart + maxRunBeforeFallback - 1; j >= knownRunEnd; j--) { 912 if (hashTable[j & mask] == null) { 913 knownRunEnd = knownRunStart + maxRunBeforeFallback; 914 knownRunStart = j + 1; 915 continue outerLoop; 916 } 917 } 918 return true; 919 } 920 } 921 return false; 922 } 923 924 /** 925 * If more than this many consecutive positions are filled in a table of the specified size, 926 * report probable hash flooding. ({@link #hashFloodingDetected} may also report hash flooding 927 * if fewer consecutive positions are filled; see that method for details.) 928 */ 929 static int maxRunBeforeFallback(int tableSize) { 930 return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY); 931 } 932 } 933 934 /** 935 * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection. 936 */ 937 private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> { 938 private final Set<Object> delegate; 939 940 JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) { 941 super(toCopy); // initializes dedupedElements and distinct 942 delegate = Sets.newHashSetWithExpectedSize(distinct); 943 for (int i = 0; i < distinct; i++) { 944 /* 945 * requireNonNull is safe because we ensure that the first `distinct` elements have been 946 * populated. 947 */ 948 delegate.add(requireNonNull(dedupedElements[i])); 949 } 950 } 951 952 @Override 953 SetBuilderImpl<E> add(E e) { 954 checkNotNull(e); 955 if (delegate.add(e)) { 956 addDedupedElement(e); 957 } 958 return this; 959 } 960 961 @Override 962 SetBuilderImpl<E> copy() { 963 return new JdkBackedSetBuilderImpl<>(this); 964 } 965 966 @Override 967 ImmutableSet<E> build() { 968 switch (distinct) { 969 case 0: 970 return of(); 971 case 1: 972 /* 973 * requireNonNull is safe because we ensure that the first `distinct` elements have been 974 * populated. 975 */ 976 return of(requireNonNull(dedupedElements[0])); 977 default: 978 return new JdkBackedImmutableSet<E>( 979 delegate, ImmutableList.asImmutableList(dedupedElements, distinct)); 980 } 981 } 982 } 983}