common/collect/RegularImmutableMultiset.java

/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Objects;
import com.google.common.collect.Multisets.ImmutableEntry;
import com.google.common.primitives.Ints;
import com.google.errorprone.annotations.concurrent.LazyInit;
import java.util.Arrays;
import java.util.Collection;
import javax.annotation.CheckForNull;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Implementation of {@link ImmutableMultiset} with zero or more elements.
 *
 * @author Jared Levy
 * @author Louis Wasserman
 */
@GwtCompatible(emulated = true, serializable = true)
@SuppressWarnings("serial") // uses writeReplace(), not default serialization
@ElementTypesAreNonnullByDefault
class RegularImmutableMultiset<E> extends ImmutableMultiset<E> {
  private static final ImmutableEntry<?>[] EMPTY_ARRAY = new ImmutableEntry<?>[0];
  static final ImmutableMultiset<Object> EMPTY = create(ImmutableList.<Entry<Object>>of());

  static <E> ImmutableMultiset<E> create(Collection<? extends Entry<? extends E>> entries) {
    int distinct = entries.size();
    @SuppressWarnings({"unchecked", "rawtypes"})
    ImmutableEntry<E>[] entryArray = new ImmutableEntry[distinct];
    if (distinct == 0) {
      return new RegularImmutableMultiset<>(entryArray, EMPTY_ARRAY, 0, 0, ImmutableSet.of());
    }
    int tableSize = Hashing.closedTableSize(distinct, MAX_LOAD_FACTOR);
    int mask = tableSize - 1;
    @SuppressWarnings({"unchecked", "rawtypes"})
    @Nullable
    ImmutableEntry<E>[] hashTable = new @Nullable ImmutableEntry[tableSize];

    int index = 0;
    int hashCode = 0;
    long size = 0;
    for (Entry<? extends E> entryWithWildcard : entries) {
      @SuppressWarnings("unchecked") // safe because we only read from it
      Entry<E> entry = (Entry<E>) entryWithWildcard;
      E element = checkNotNull(entry.getElement());
      int count = entry.getCount();
      int hash = element.hashCode();
      int bucket = Hashing.smear(hash) & mask;
      ImmutableEntry<E> bucketHead = hashTable[bucket];
      ImmutableEntry<E> newEntry;
      if (bucketHead == null) {
        boolean canReuseEntry =
            entry instanceof ImmutableEntry && !(entry instanceof NonTerminalEntry);
        newEntry =
            canReuseEntry ? (ImmutableEntry<E>) entry : new ImmutableEntry<E>(element, count);
      } else {
        newEntry = new NonTerminalEntry<E>(element, count, bucketHead);
      }
      hashCode += hash ^ count;
      entryArray[index++] = newEntry;
      hashTable[bucket] = newEntry;
      size += count;
    }

    return hashFloodingDetected(hashTable)
        ? JdkBackedImmutableMultiset.create(ImmutableList.asImmutableList(entryArray))
        : new RegularImmutableMultiset<E>(
            entryArray, hashTable, Ints.saturatedCast(size), hashCode, null);
  }

  private static boolean hashFloodingDetected(@Nullable ImmutableEntry<?>[] hashTable) {
    for (int i = 0; i < hashTable.length; i++) {
      int bucketLength = 0;
      for (ImmutableEntry<?> entry = hashTable[i]; entry != null; entry = entry.nextInBucket()) {
        bucketLength++;
        if (bucketLength > MAX_HASH_BUCKET_LENGTH) {
          return true;
        }
      }
    }
    return false;
  }

  /**
   * Closed addressing tends to perform well even with high load factors. Being conservative here
   * ensures that the table is still likely to be relatively sparse (hence it misses fast) while
   * saving space.
   */
  @VisibleForTesting static final double MAX_LOAD_FACTOR = 1.0;

  /**
   * Maximum allowed false positive probability of detecting a hash flooding attack given random
   * input.
   */
  @VisibleForTesting static final double HASH_FLOODING_FPP = 0.001;

  /**
   * Maximum allowed length of a hash table bucket before falling back to a j.u.HashMap based
   * implementation. Experimentally determined.
   */
  @VisibleForTesting static final int MAX_HASH_BUCKET_LENGTH = 9;

  private final transient ImmutableEntry<E>[] entries;
  private final transient @Nullable ImmutableEntry<?>[] hashTable;
  private final transient int size;
  private final transient int hashCode;

  @LazyInit @CheckForNull private transient ImmutableSet<E> elementSet;

  private RegularImmutableMultiset(
      ImmutableEntry<E>[] entries,
      @Nullable ImmutableEntry<?>[] hashTable,
      int size,
      int hashCode,
      @CheckForNull ImmutableSet<E> elementSet) {
    this.entries = entries;
    this.hashTable = hashTable;
    this.size = size;
    this.hashCode = hashCode;
    this.elementSet = elementSet;
  }

  private static final class NonTerminalEntry<E> extends ImmutableEntry<E> {
    private final ImmutableEntry<E> nextInBucket;

    NonTerminalEntry(E element, int count, ImmutableEntry<E> nextInBucket) {
      super(element, count);
      this.nextInBucket = nextInBucket;
    }

    @Override
    public ImmutableEntry<E> nextInBucket() {
      return nextInBucket;
    }
  }

  @Override
  boolean isPartialView() {
    return false;
  }

  @Override
  public int count(@CheckForNull Object element) {
    @Nullable ImmutableEntry<?>[] hashTable = this.hashTable;
    if (element == null || hashTable.length == 0) {
      return 0;
    }
    int hash = Hashing.smearedHash(element);
    int mask = hashTable.length - 1;
    for (ImmutableEntry<?> entry = hashTable[hash & mask];
        entry != null;
        entry = entry.nextInBucket()) {
      if (Objects.equal(element, entry.getElement())) {
        return entry.getCount();
      }
    }
    return 0;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public ImmutableSet<E> elementSet() {
    ImmutableSet<E> result = elementSet;
    return (result == null) ? elementSet = new ElementSet<E>(Arrays.asList(entries), this) : result;
  }

  @Override
  Entry<E> getEntry(int index) {
    return entries[index];
  }

  @Override
  public int hashCode() {
    return hashCode;
  }
}