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