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}