diff options
Diffstat (limited to 'guava/src/com/google/common/collect/ImmutableSet.java')
| -rw-r--r-- | guava/src/com/google/common/collect/ImmutableSet.java | 907 |
1 files changed, 298 insertions, 609 deletions
diff --git a/guava/src/com/google/common/collect/ImmutableSet.java b/guava/src/com/google/common/collect/ImmutableSet.java index cd55c8b86..c23618241 100644 --- a/guava/src/com/google/common/collect/ImmutableSet.java +++ b/guava/src/com/google/common/collect/ImmutableSet.java @@ -17,122 +17,137 @@ package com.google.common.collect; import static com.google.common.base.Preconditions.checkArgument; -import static com.google.common.base.Preconditions.checkNotNull; -import static com.google.common.collect.CollectPreconditions.checkNonnegative; +import static com.google.common.collect.ObjectArrays.checkElementNotNull; -import com.google.common.annotations.Beta; import com.google.common.annotations.GwtCompatible; import com.google.common.annotations.VisibleForTesting; -import com.google.common.math.IntMath; import com.google.common.primitives.Ints; -import com.google.errorprone.annotations.CanIgnoreReturnValue; -import com.google.errorprone.annotations.concurrent.LazyInit; -import com.google.j2objc.annotations.RetainedWith; + import java.io.Serializable; -import java.math.RoundingMode; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.EnumSet; +import java.util.HashSet; import java.util.Iterator; import java.util.Set; -import java.util.SortedSet; -import java.util.Spliterator; -import java.util.function.Consumer; -import java.util.stream.Collector; -import org.checkerframework.checker.nullness.qual.Nullable; + +import javax.annotation.Nullable; /** - * A {@link Set} whose contents will never change, with many other important properties detailed at - * {@link ImmutableCollection}. + * A high-performance, immutable {@code Set} with reliable, user-specified + * iteration order. Does not permit null elements. + * + * <p>Unlike {@link Collections#unmodifiableSet}, which is a <i>view</i> of a + * separate collection that can still change, an instance of this class contains + * its own private data and will <i>never</i> change. This class is convenient + * for {@code public static final} sets ("constant sets") and also lets you + * easily make a "defensive copy" of a set provided to your class by a caller. + * + * <p><b>Warning:</b> Like most sets, an {@code ImmutableSet} will not function + * correctly if an element is modified after being placed in the set. For this + * reason, and to avoid general confusion, it is strongly recommended to place + * only immutable objects into this collection. + * + * <p>This class has been observed to perform significantly better than {@link + * HashSet} for objects with very fast {@link Object#hashCode} implementations + * (as a well-behaved immutable object should). While this class's factory + * methods create hash-based instances, the {@link ImmutableSortedSet} subclass + * performs binary searches instead. * - * @since 2.0 + * <p><b>Note:</b> Although this class is not final, it cannot be subclassed + * outside its package as it has no public or protected constructors. Thus, + * instances of this type are guaranteed to be immutable. + * + * <p>See the Guava User Guide article on <a href= + * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained"> + * immutable collections</a>. + * + * @see ImmutableList + * @see ImmutableMap + * @author Kevin Bourrillion + * @author Nick Kralevich + * @since 2.0 (imported from Google Collections Library) */ @GwtCompatible(serializable = true, emulated = true) @SuppressWarnings("serial") // we're overriding default serialization -public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> { - static final int SPLITERATOR_CHARACTERISTICS = - ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT; - - /** - * Returns a {@code Collector} that accumulates the input elements into a new {@code - * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if - * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first - * duplicate in encounter order will appear in the result. - * - * @since 21.0 - */ - public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() { - return CollectCollectors.toImmutableSet(); - } - +public abstract class ImmutableSet<E> extends ImmutableCollection<E> + implements Set<E> { /** - * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code - * consistency, and because the return type conveys the immutability guarantee. + * Returns the empty immutable set. This set behaves and performs comparably + * to {@link Collections#emptySet}, and is preferable mainly for consistency + * and maintainability of your code. */ - @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es) + // Casting to any type is safe because the set will never hold any elements. + @SuppressWarnings({"unchecked"}) public static <E> ImmutableSet<E> of() { - return (ImmutableSet<E>) RegularImmutableSet.EMPTY; + return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE; } /** - * Returns an immutable set containing {@code element}. Preferred over {@link - * Collections#singleton} for code consistency, {@code null} rejection, and because the return - * type conveys the immutability guarantee. + * Returns an immutable set containing a single element. This set behaves and + * performs comparably to {@link Collections#singleton}, but will not accept + * a null element. It is preferable mainly for consistency and + * maintainability of your code. */ public static <E> ImmutableSet<E> of(E element) { return new SingletonImmutableSet<E>(element); } /** - * Returns an immutable set containing the given elements, minus duplicates, in the order each was - * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except - * the first are ignored. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. + * + * @throws NullPointerException if any element is null */ public static <E> ImmutableSet<E> of(E e1, E e2) { return construct(2, e1, e2); } /** - * Returns an immutable set containing the given elements, minus duplicates, in the order each was - * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except - * the first are ignored. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. + * + * @throws NullPointerException if any element is null */ public static <E> ImmutableSet<E> of(E e1, E e2, E e3) { return construct(3, e1, e2, e3); } /** - * Returns an immutable set containing the given elements, minus duplicates, in the order each was - * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except - * the first are ignored. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. + * + * @throws NullPointerException if any element is null */ public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) { return construct(4, e1, e2, e3, e4); } /** - * Returns an immutable set containing the given elements, minus duplicates, in the order each was - * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except - * the first are ignored. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. + * + * @throws NullPointerException if any element is null */ public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) { return construct(5, e1, e2, e3, e4, e5); } /** - * Returns an immutable set containing the given elements, minus duplicates, in the order each was - * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except - * the first are ignored. - * - * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. * + * @throws NullPointerException if any element is null * @since 3.0 (source-compatible since 2.0) */ - @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning. - public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) { - checkArgument( - others.length <= Integer.MAX_VALUE - 6, "the total number of elements must fit in an int"); + public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, + E... others) { final int paramCount = 6; Object[] elements = new Object[paramCount + others.length]; elements[0] = e1; @@ -146,18 +161,19 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements } /** - * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If - * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code - * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code - * k <= i < n}. + * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. + * If {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of + * {@code elements} will be in the first {@code k} positions, and {@code elements[i] == null} for + * {@code k <= i < n}. * - * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code - * elements} contains no duplicates, {@code elements} may be used without copying in the returned - * {@code ImmutableSet}, in which case it may no longer be modified. + * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and + * {@code elements} contains no duplicates, {@code elements} may be used without copying in the + * returned {@code ImmutableSet}, in which case it may no longer be modified. * * <p>{@code elements} may contain only values of type {@code E}. * - * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null + * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is + * null */ private static <E> ImmutableSet<E> construct(int n, Object... elements) { switch (n) { @@ -168,57 +184,115 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements E elem = (E) elements[0]; return of(elem); default: - SetBuilderImpl<E> builder = - new RegularSetBuilderImpl<E>(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY); - for (int i = 0; i < n; i++) { - @SuppressWarnings("unchecked") - E e = (E) checkNotNull(elements[i]); - builder = builder.add(e); + // continue below to handle the general case + } + int tableSize = chooseTableSize(n); + Object[] table = new Object[tableSize]; + int mask = tableSize - 1; + int hashCode = 0; + int uniques = 0; + for (int i = 0; i < n; i++) { + Object element = checkElementNotNull(elements[i], i); + int hash = element.hashCode(); + for (int j = Hashing.smear(hash); ; j++) { + int index = j & mask; + Object value = table[index]; + if (value == null) { + // Came to an empty slot. Put the element here. + elements[uniques++] = element; + table[index] = element; + hashCode += hash; + break; + } else if (value.equals(element)) { + break; } - return builder.review().build(); + } + } + Arrays.fill(elements, uniques, n, null); + if (uniques == 1) { + // There is only one element or elements are all duplicates + @SuppressWarnings("unchecked") // we are careful to only pass in E + E element = (E) elements[0]; + return new SingletonImmutableSet<E>(element, hashCode); + } else if (tableSize != chooseTableSize(uniques)) { + // Resize the table when the array includes too many duplicates. + // when this happens, we have already made a copy + return construct(uniques, elements); + } else { + Object[] uniqueElements = (uniques < elements.length) + ? ObjectArrays.arraysCopyOf(elements, uniques) + : elements; + return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask); } } + // We use power-of-2 tables, and this is the highest int that's a power of 2 + static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO; + + // Represents how tightly we can pack things, as a maximum. + private static final double DESIRED_LOAD_FACTOR = 0.7; + + // If the set has this many elements, it will "max out" the table size + private static final int CUTOFF = + (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR); + /** - * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order - * each appears first in the source collection. + * Returns an array size suitable for the backing array of a hash table that + * uses open addressing with linear probing in its implementation. The + * returned size is the smallest power of two that can hold setSize elements + * with the desired load factor. * - * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation - * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once. - * This reduces the expense of habitually making defensive copies at API boundaries. However, the - * precise conditions for skipping the copy operation are undefined. + * <p>Do not call this method with setSize < 2. + */ + @VisibleForTesting static int chooseTableSize(int setSize) { + // Correct the size for open addressing to match desired load factor. + if (setSize < CUTOFF) { + // Round up to the next highest power of 2. + int tableSize = Integer.highestOneBit(setSize - 1) << 1; + while (tableSize * DESIRED_LOAD_FACTOR < setSize) { + tableSize <<= 1; + } + return tableSize; + } + + // The table can't be completely full or we'll get infinite reprobes + checkArgument(setSize < MAX_TABLE_SIZE, "collection too large"); + return MAX_TABLE_SIZE; + } + + /** + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. * * @throws NullPointerException if any of {@code elements} is null - * @since 7.0 (source-compatible since 2.0) + * @since 3.0 */ - public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) { - /* - * TODO(lowasser): consider checking for ImmutableAsList here - * TODO(lowasser): consider checking for Multiset here - */ - // Don't refer to ImmutableSortedSet by name so it won't pull in all that code - if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) { - @SuppressWarnings("unchecked") // all supported methods are covariant - ImmutableSet<E> set = (ImmutableSet<E>) elements; - if (!set.isPartialView()) { - return set; - } - } else if (elements instanceof EnumSet) { - return copyOfEnumSet((EnumSet) elements); + public static <E> ImmutableSet<E> copyOf(E[] elements) { + switch (elements.length) { + case 0: + return of(); + case 1: + return of(elements[0]); + default: + return construct(elements.length, elements.clone()); } - Object[] array = elements.toArray(); - return construct(array.length, array); } /** - * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order - * each appears first in the source iterable. This method iterates over {@code elements} only - * once. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. This method iterates over {@code elements} at most once. + * + * <p>Note that if {@code s} is a {@code Set<String>}, then {@code + * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing + * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns + * a {@code ImmutableSet<Set<String>>} containing one element (the given set + * itself). * - * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation - * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only - * once. This reduces the expense of habitually making defensive copies at API boundaries. - * However, the precise conditions for skipping the copy operation are undefined. + * <p>Despite the method name, this method attempts to avoid actually copying + * the data when it is safe to do so. The exact circumstances under which a + * copy will or will not be performed are undocumented and subject to change. * * @throws NullPointerException if any of {@code elements} is null */ @@ -229,8 +303,9 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements } /** - * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order - * each appears first in the source iterator. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. * * @throws NullPointerException if any of {@code elements} is null */ @@ -243,30 +318,65 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements if (!elements.hasNext()) { return of(first); } else { - return new ImmutableSet.Builder<E>().add(first).addAll(elements).build(); + return new ImmutableSet.Builder<E>() + .add(first) + .addAll(elements) + .build(); } } /** - * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order - * each appears first in the source array. + * Returns an immutable set containing the given elements, in order. Repeated + * occurrences of an element (according to {@link Object#equals}) after the + * first are ignored. This method iterates over {@code elements} at most + * once. + * + * <p>Note that if {@code s} is a {@code Set<String>}, then {@code + * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing + * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns + * a {@code ImmutableSet<Set<String>>} containing one element (the given set + * itself). + * + * <p><b>Note:</b> Despite what the method name suggests, {@code copyOf} will + * return constant-space views, rather than linear-space copies, of some + * inputs known to be immutable. For some other immutable inputs, such as key + * sets of an {@code ImmutableMap}, it still performs a copy in order to avoid + * holding references to the values of the map. The heuristics used in this + * decision are undocumented and subject to change except that: + * <ul> + * <li>A full copy will be done of any {@code ImmutableSortedSet}.</li> + * <li>{@code ImmutableSet.copyOf()} is idempotent with respect to pointer + * equality.</li> + * </ul> + * + * <p>This method is safe to use even when {@code elements} is a synchronized + * or concurrent collection that is currently being modified by another + * thread. * * @throws NullPointerException if any of {@code elements} is null - * @since 3.0 + * @since 7.0 (source-compatible since 2.0) */ - public static <E> ImmutableSet<E> copyOf(E[] elements) { - switch (elements.length) { - case 0: - return of(); - case 1: - return of(elements[0]); - default: - return construct(elements.length, elements.clone()); + public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) { + /* + * TODO(user): consider checking for ImmutableAsList here + * TODO(user): consider checking for Multiset here + */ + if (elements instanceof ImmutableSet + && !(elements instanceof ImmutableSortedSet)) { + @SuppressWarnings("unchecked") // all supported methods are covariant + ImmutableSet<E> set = (ImmutableSet<E>) elements; + if (!set.isPartialView()) { + return set; + } + } else if (elements instanceof EnumSet) { + return copyOfEnumSet((EnumSet) elements); } + Object[] array = elements.toArray(); + return construct(array.length, array); } - @SuppressWarnings("rawtypes") // necessary to compile against Java 8 - private static ImmutableSet copyOfEnumSet(EnumSet enumSet) { + private static <E extends Enum<E>> ImmutableSet<E> copyOfEnumSet( + EnumSet<E> enumSet) { return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet)); } @@ -277,8 +387,7 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements return false; } - @Override - public boolean equals(@Nullable Object object) { + @Override public boolean equals(@Nullable Object object) { if (object == this) { return true; } else if (object instanceof ImmutableSet @@ -290,70 +399,13 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements return Sets.equalsImpl(this, object); } - @Override - public int hashCode() { + @Override public int hashCode() { return Sets.hashCodeImpl(this); } // This declaration is needed to make Set.iterator() and // ImmutableCollection.iterator() consistent. - @Override - public abstract UnmodifiableIterator<E> iterator(); - - @LazyInit @RetainedWith private transient @Nullable ImmutableList<E> asList; - - @Override - public ImmutableList<E> asList() { - ImmutableList<E> result = asList; - return (result == null) ? asList = createAsList() : result; - } - - ImmutableList<E> createAsList() { - return new RegularImmutableAsList<E>(this, toArray()); - } - - abstract static class Indexed<E> extends ImmutableSet<E> { - abstract E get(int index); - - @Override - public UnmodifiableIterator<E> iterator() { - return asList().iterator(); - } - - @Override - public Spliterator<E> spliterator() { - return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get); - } - - @Override - public void forEach(Consumer<? super E> consumer) { - checkNotNull(consumer); - int n = size(); - for (int i = 0; i < n; i++) { - consumer.accept(get(i)); - } - } - - @Override - int copyIntoArray(Object[] dst, int offset) { - return asList().copyIntoArray(dst, offset); - } - - @Override - ImmutableList<E> createAsList() { - return new ImmutableAsList<E>() { - @Override - public E get(int index) { - return Indexed.this.get(index); - } - - @Override - Indexed<E> delegateCollection() { - return Indexed.this; - } - }; - } - } + @Override public abstract UnmodifiableIterator<E> iterator(); /* * This class is used to serialize all ImmutableSet instances, except for @@ -364,486 +416,123 @@ public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements */ private static class SerializedForm implements Serializable { final Object[] elements; - SerializedForm(Object[] elements) { this.elements = elements; } - Object readResolve() { return copyOf(elements); } - private static final long serialVersionUID = 0; } - @Override - Object writeReplace() { + @Override Object writeReplace() { return new SerializedForm(toArray()); } /** - * Returns a new builder. The generated builder is equivalent to the builder created by the {@link - * Builder} constructor. + * Returns a new builder. The generated builder is equivalent to the builder + * created by the {@link Builder} constructor. */ public static <E> Builder<E> builder() { return new Builder<E>(); } /** - * Returns a new builder, expecting the specified number of distinct elements to be added. - * - * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder - * before {@link Builder#build} is called, the builder is likely to perform better than an unsized - * {@link #builder()} would have. - * - * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, - * but not exactly, the number of distinct elements added to the builder. - * - * @since 23.1 - */ - @Beta - public static <E> Builder<E> builderWithExpectedSize(int expectedSize) { - checkNonnegative(expectedSize, "expectedSize"); - return new Builder<E>(expectedSize); - } - - /** Builds a new open-addressed hash table from the first n objects in elements. */ - static Object[] rebuildHashTable(int newTableSize, Object[] elements, int n) { - Object[] hashTable = new Object[newTableSize]; - int mask = hashTable.length - 1; - for (int i = 0; i < n; i++) { - Object e = elements[i]; - int j0 = Hashing.smear(e.hashCode()); - for (int j = j0; ; j++) { - int index = j & mask; - if (hashTable[index] == null) { - hashTable[index] = e; - break; - } - } - } - return hashTable; - } - - /** - * A builder for creating {@code ImmutableSet} instances. Example: + * A builder for creating immutable set instances, especially {@code public + * static final} sets ("constant sets"). Example: <pre> {@code * - * <pre>{@code - * static final ImmutableSet<Color> GOOGLE_COLORS = - * ImmutableSet.<Color>builder() - * .addAll(WEBSAFE_COLORS) - * .add(new Color(0, 191, 255)) - * .build(); - * }</pre> + * public static final ImmutableSet<Color> GOOGLE_COLORS = + * new ImmutableSet.Builder<Color>() + * .addAll(WEBSAFE_COLORS) + * .add(new Color(0, 191, 255)) + * .build();}</pre> * - * <p>Elements appear in the resulting set in the same order they were first added to the builder. + * <p>Builder instances can be reused; it is safe to call {@link #build} multiple + * times to build multiple sets in series. Each set is a superset of the set + * created before it. * - * <p>Building does not change the state of the builder, so it is still possible to add more - * elements and to build again. - * - * @since 2.0 + * @since 2.0 (imported from Google Collections Library) */ - public static class Builder<E> extends ImmutableCollection.Builder<E> { - private SetBuilderImpl<E> impl; - boolean forceCopy; + public static class Builder<E> extends ImmutableCollection.ArrayBasedBuilder<E> { + /** + * Creates a new builder. The returned builder is equivalent to the builder + * generated by {@link ImmutableSet#builder}. + */ public Builder() { this(DEFAULT_INITIAL_CAPACITY); } Builder(int capacity) { - impl = new RegularSetBuilderImpl<E>(capacity); - } - - Builder(@SuppressWarnings("unused") boolean subclass) { - this.impl = null; // unused - } - - @VisibleForTesting - void forceJdk() { - this.impl = new JdkBackedSetBuilderImpl<E>(impl); - } - - final void copyIfNecessary() { - if (forceCopy) { - copy(); - forceCopy = false; - } - } - - void copy() { - impl = impl.copy(); - } - - @Override - @CanIgnoreReturnValue - public Builder<E> add(E element) { - checkNotNull(element); - copyIfNecessary(); - impl = impl.add(element); - return this; + super(capacity); } - @Override - @CanIgnoreReturnValue - public Builder<E> add(E... elements) { - super.add(elements); + /** + * Adds {@code element} to the {@code ImmutableSet}. If the {@code + * ImmutableSet} already contains {@code element}, then {@code add} has no + * effect (only the previously added element is retained). + * + * @param element the element to add + * @return this {@code Builder} object + * @throws NullPointerException if {@code element} is null + */ + @Override public Builder<E> add(E element) { + super.add(element); return this; } - @Override /** - * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate - * elements (only the first duplicate element is added). + * Adds each element of {@code elements} to the {@code ImmutableSet}, + * ignoring duplicate elements (only the first duplicate element is added). * * @param elements the elements to add * @return this {@code Builder} object - * @throws NullPointerException if {@code elements} is null or contains a null element + * @throws NullPointerException if {@code elements} is null or contains a + * null element */ - @CanIgnoreReturnValue - public Builder<E> addAll(Iterable<? extends E> elements) { - super.addAll(elements); + @Override public Builder<E> add(E... elements) { + super.add(elements); return this; } - @Override - @CanIgnoreReturnValue - public Builder<E> addAll(Iterator<? extends E> elements) { + /** + * Adds each element of {@code elements} to the {@code ImmutableSet}, + * ignoring duplicate elements (only the first duplicate element is added). + * + * @param elements the {@code Iterable} to add to the {@code ImmutableSet} + * @return this {@code Builder} object + * @throws NullPointerException if {@code elements} is null or contains a + * null element + */ + @Override public Builder<E> addAll(Iterable<? extends E> elements) { super.addAll(elements); return this; } - Builder<E> combine(Builder<E> other) { - copyIfNecessary(); - this.impl = this.impl.combine(other.impl); - return this; - } - - @Override - public ImmutableSet<E> build() { - forceCopy = true; - impl = impl.review(); - return impl.build(); - } - } - - /** Swappable internal implementation of an ImmutableSet.Builder. */ - private abstract static class SetBuilderImpl<E> { - E[] dedupedElements; - int distinct; - - @SuppressWarnings("unchecked") - SetBuilderImpl(int expectedCapacity) { - this.dedupedElements = (E[]) new Object[expectedCapacity]; - this.distinct = 0; - } - - /** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */ - SetBuilderImpl(SetBuilderImpl<E> toCopy) { - this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length); - this.distinct = toCopy.distinct; - } - /** - * Resizes internal data structures if necessary to store the specified number of distinct - * elements. + * Adds each element of {@code elements} to the {@code ImmutableSet}, + * ignoring duplicate elements (only the first duplicate element is added). + * + * @param elements the elements to add to the {@code ImmutableSet} + * @return this {@code Builder} object + * @throws NullPointerException if {@code elements} is null or contains a + * null element */ - private void ensureCapacity(int minCapacity) { - if (minCapacity > dedupedElements.length) { - int newCapacity = - ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity); - dedupedElements = Arrays.copyOf(dedupedElements, newCapacity); - } - } - - /** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */ - final void addDedupedElement(E e) { - ensureCapacity(distinct + 1); - dedupedElements[distinct++] = e; + @Override public Builder<E> addAll(Iterator<? extends E> elements) { + super.addAll(elements); + return this; } /** - * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned - * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected. + * Returns a newly-created {@code ImmutableSet} based on the contents of + * the {@code Builder}. */ - abstract SetBuilderImpl<E> add(E e); - - /** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */ - final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) { - SetBuilderImpl<E> result = this; - for (int i = 0; i < other.distinct; i++) { - result = result.add(other.dedupedElements[i]); - } + @Override public ImmutableSet<E> build() { + ImmutableSet<E> result = construct(size, contents); + // construct has the side effect of deduping contents, so we update size + // accordingly. + size = result.size(); return result; } - - /** - * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not - * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build(). - */ - abstract SetBuilderImpl<E> copy(); - - /** - * Call this before build(). Does a final check on the internal data structures, e.g. shrinking - * unnecessarily large structures or detecting previously unnoticed hash flooding. - */ - SetBuilderImpl<E> review() { - return this; - } - - abstract ImmutableSet<E> build(); - } - - // We use power-of-2 tables, and this is the highest int that's a power of 2 - static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO; - - // Represents how tightly we can pack things, as a maximum. - private static final double DESIRED_LOAD_FACTOR = 0.7; - - // If the set has this many elements, it will "max out" the table size - private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR); - - /** - * Returns an array size suitable for the backing array of a hash table that uses open addressing - * with linear probing in its implementation. The returned size is the smallest power of two that - * can hold setSize elements with the desired load factor. Always returns at least setSize + 2. - */ - @VisibleForTesting - static int chooseTableSize(int setSize) { - setSize = Math.max(setSize, 2); - // Correct the size for open addressing to match desired load factor. - if (setSize < CUTOFF) { - // Round up to the next highest power of 2. - int tableSize = Integer.highestOneBit(setSize - 1) << 1; - while (tableSize * DESIRED_LOAD_FACTOR < setSize) { - tableSize <<= 1; - } - return tableSize; - } - - // The table can't be completely full or we'll get infinite reprobes - checkArgument(setSize < MAX_TABLE_SIZE, "collection too large"); - return MAX_TABLE_SIZE; - } - - /** - * We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a - * wrapper around j.u.HashSet, which has built in flooding protection. HASH_FLOODING_FPP is the - * maximum allowed probability of falsely detecting a hash flooding attack if the input is - * randomly generated. - * - * <p>MAX_RUN_MULTIPLIER was determined experimentally to match this FPP. - */ - static final double HASH_FLOODING_FPP = 0.001; - - // NB: yes, this is surprisingly high, but that's what the experiments said was necessary - // The higher it is, the worse constant factors we are willing to accept. - static final int MAX_RUN_MULTIPLIER = 13; - - /** - * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n / log - * n) on average. - * - * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many exactly - * matching hash codes, which would cause construction to take O(n^2), but can't detect e.g. hash - * codes adversarially designed to go into ascending table locations, which keeps construction - * O(n) (as desired) but then can have O(n) queries later. - * - * <p>If this returns false, then no query can take more than O(log n). - * - * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains - * operations take expected O(1) time but with high probability take O(log n) for at least some - * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis) - * - * <p>This method may return {@code true} up to {@link #HASH_FLOODING_FPP} of the time even on - * truly random input. - * - * <p>If this method returns false, there are definitely no runs of length at least {@code - * maxRunBeforeFallback(hashTable.length)} nonnull elements. If there are no runs of length at - * least {@code maxRunBeforeFallback(hashTable.length) / 2} nonnull elements, this method - * definitely returns false. In between those constraints, the result of this method is undefined, - * subject to the above {@link #HASH_FLOODING_FPP} constraint. - */ - static boolean hashFloodingDetected(Object[] hashTable) { - int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length); - - // Test for a run wrapping around the end of the table of length at least maxRunBeforeFallback. - int endOfStartRun; - for (endOfStartRun = 0; endOfStartRun < hashTable.length; ) { - if (hashTable[endOfStartRun] == null) { - break; - } - endOfStartRun++; - if (endOfStartRun > maxRunBeforeFallback) { - return true; - } - } - int startOfEndRun; - for (startOfEndRun = hashTable.length - 1; startOfEndRun > endOfStartRun; startOfEndRun--) { - if (hashTable[startOfEndRun] == null) { - break; - } - if (endOfStartRun + (hashTable.length - 1 - startOfEndRun) > maxRunBeforeFallback) { - return true; - } - } - - // Now, break the remainder of the table into blocks of maxRunBeforeFallback/2 elements and - // check that each has at least one null. - int testBlockSize = maxRunBeforeFallback / 2; - blockLoop: - for (int i = endOfStartRun + 1; i + testBlockSize <= startOfEndRun; i += testBlockSize) { - for (int j = 0; j < testBlockSize; j++) { - if (hashTable[i + j] == null) { - continue blockLoop; - } - } - return true; - } - return false; - } - - /** - * If more than this many consecutive positions are filled in a table of the specified size, - * report probable hash flooding. ({@link #hashFloodingDetected} may also report hash flooding if - * fewer consecutive positions are filled; see that method for details.) - */ - private static int maxRunBeforeFallback(int tableSize) { - return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY); - } - - /** - * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash - * table and deduplicating elements as they come, so it only allocates O(max(distinct, - * expectedCapacity)) rather than O(calls to add). - * - * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to - * JdkBackedSetBuilderImpl. - */ - private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> { - private Object[] hashTable; - private int maxRunBeforeFallback; - private int expandTableThreshold; - private int hashCode; - - RegularSetBuilderImpl(int expectedCapacity) { - super(expectedCapacity); - int tableSize = chooseTableSize(expectedCapacity); - this.hashTable = new Object[tableSize]; - this.maxRunBeforeFallback = maxRunBeforeFallback(tableSize); - this.expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * tableSize); - } - - RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) { - super(toCopy); - this.hashTable = Arrays.copyOf(toCopy.hashTable, toCopy.hashTable.length); - this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback; - this.expandTableThreshold = toCopy.expandTableThreshold; - this.hashCode = toCopy.hashCode; - } - - void ensureTableCapacity(int minCapacity) { - if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) { - int newTableSize = hashTable.length * 2; - hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct); - maxRunBeforeFallback = maxRunBeforeFallback(newTableSize); - expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize); - } - } - - @Override - SetBuilderImpl<E> add(E e) { - checkNotNull(e); - int eHash = e.hashCode(); - int i0 = Hashing.smear(eHash); - int mask = hashTable.length - 1; - for (int i = i0; i - i0 < maxRunBeforeFallback; i++) { - int index = i & mask; - Object tableEntry = hashTable[index]; - if (tableEntry == null) { - addDedupedElement(e); - hashTable[index] = e; - hashCode += eHash; - ensureTableCapacity(distinct); // rebuilds table if necessary - return this; - } else if (tableEntry.equals(e)) { // not a new element, ignore - return this; - } - } - // we fell out of the loop due to a long run; fall back to JDK impl - return new JdkBackedSetBuilderImpl<E>(this).add(e); - } - - @Override - SetBuilderImpl<E> copy() { - return new RegularSetBuilderImpl<E>(this); - } - - @Override - SetBuilderImpl<E> review() { - int targetTableSize = chooseTableSize(distinct); - if (targetTableSize * 2 < hashTable.length) { - hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct); - } - return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this; - } - - @Override - ImmutableSet<E> build() { - switch (distinct) { - case 0: - return of(); - case 1: - return of(dedupedElements[0]); - default: - Object[] elements = - (distinct == dedupedElements.length) - ? dedupedElements - : Arrays.copyOf(dedupedElements, distinct); - return new RegularImmutableSet<E>(elements, hashCode, hashTable, hashTable.length - 1); - } - } - } - - /** - * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection. - */ - private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> { - private final Set<Object> delegate; - - JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) { - super(toCopy); // initializes dedupedElements and distinct - delegate = Sets.newHashSetWithExpectedSize(distinct); - for (int i = 0; i < distinct; i++) { - delegate.add(dedupedElements[i]); - } - } - - @Override - SetBuilderImpl<E> add(E e) { - checkNotNull(e); - if (delegate.add(e)) { - addDedupedElement(e); - } - return this; - } - - @Override - SetBuilderImpl<E> copy() { - return new JdkBackedSetBuilderImpl<>(this); - } - - @Override - ImmutableSet<E> build() { - switch (distinct) { - case 0: - return of(); - case 1: - return of(dedupedElements[0]); - default: - return new JdkBackedImmutableSet<E>( - delegate, ImmutableList.asImmutableList(dedupedElements, distinct)); - } - } } } |