1 /* 2 * Copyright (C) 2018 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static com.google.common.base.Preconditions.checkNotNull; 18 19 import com.google.common.annotations.GwtCompatible; 20 import com.google.common.primitives.Ints; 21 import java.util.Collection; 22 import java.util.Map; 23 import org.checkerframework.checker.nullness.qual.Nullable; 24 25 /** 26 * An implementation of ImmutableMultiset backed by a JDK Map and a list of entries. Used to protect 27 * against hash flooding attacks. 28 * 29 * @author Louis Wasserman 30 */ 31 @GwtCompatible 32 final class JdkBackedImmutableMultiset<E> extends ImmutableMultiset<E> { 33 private final Map<E, Integer> delegateMap; 34 private final ImmutableList<Entry<E>> entries; 35 private final long size; 36 create(Collection<? extends Entry<? extends E>> entries)37 static <E> ImmutableMultiset<E> create(Collection<? extends Entry<? extends E>> entries) { 38 @SuppressWarnings("unchecked") 39 Entry<E>[] entriesArray = entries.toArray(new Entry[0]); 40 Map<E, Integer> delegateMap = Maps.newHashMapWithExpectedSize(entriesArray.length); 41 long size = 0; 42 for (int i = 0; i < entriesArray.length; i++) { 43 Entry<E> entry = entriesArray[i]; 44 int count = entry.getCount(); 45 size += count; 46 E element = checkNotNull(entry.getElement()); 47 delegateMap.put(element, count); 48 if (!(entry instanceof Multisets.ImmutableEntry)) { 49 entriesArray[i] = Multisets.immutableEntry(element, count); 50 } 51 } 52 return new JdkBackedImmutableMultiset<>( 53 delegateMap, ImmutableList.asImmutableList(entriesArray), size); 54 } 55 JdkBackedImmutableMultiset( Map<E, Integer> delegateMap, ImmutableList<Entry<E>> entries, long size)56 private JdkBackedImmutableMultiset( 57 Map<E, Integer> delegateMap, ImmutableList<Entry<E>> entries, long size) { 58 this.delegateMap = delegateMap; 59 this.entries = entries; 60 this.size = size; 61 } 62 63 @Override count(@ullable Object element)64 public int count(@Nullable Object element) { 65 return delegateMap.getOrDefault(element, 0); 66 } 67 68 private transient ImmutableSet<E> elementSet; 69 70 @Override elementSet()71 public ImmutableSet<E> elementSet() { 72 ImmutableSet<E> result = elementSet; 73 return (result == null) ? elementSet = new ElementSet<E>(entries, this) : result; 74 } 75 76 @Override getEntry(int index)77 Entry<E> getEntry(int index) { 78 return entries.get(index); 79 } 80 81 @Override isPartialView()82 boolean isPartialView() { 83 return false; 84 } 85 86 @Override size()87 public int size() { 88 return Ints.saturatedCast(size); 89 } 90 } 91