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