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}