Coverage Summary for Class: RegularImmutableMultiset (com.google.common.collect)

1 /*
2  * Copyright (C) 2011 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.annotations.VisibleForTesting;
21 import com.google.common.base.Objects;
22 import com.google.common.collect.Multisets.ImmutableEntry;
23 import com.google.common.primitives.Ints;
24 import com.google.errorprone.annotations.concurrent.LazyInit;
25 import java.util.Arrays;
26 import java.util.Collection;
27 import javax.annotation.CheckForNull;
28 import org.checkerframework.checker.nullness.qual.Nullable;
29 
30 /**
31  * Implementation of {@link ImmutableMultiset} with zero or more elements.
32  *
33  * @author Jared Levy
34  * @author Louis Wasserman
35  */
36 @GwtCompatible(emulated = true, serializable = true)
37 @SuppressWarnings("serial") // uses writeReplace(), not default serialization
38 @ElementTypesAreNonnullByDefault
39 class RegularImmutableMultiset<E> extends ImmutableMultiset<E> {
40   private static final ImmutableEntry<?>[] EMPTY_ARRAY = new ImmutableEntry<?>[0];
41   static final ImmutableMultiset<Object> EMPTY = create(ImmutableList.<Entry<Object>>of());
42 
43   static <E> ImmutableMultiset<E> create(Collection<? extends Entry<? extends E>> entries) {
44     int distinct = entries.size();
45     @SuppressWarnings({"unchecked", "rawtypes"})
46     ImmutableEntry<E>[] entryArray = new ImmutableEntry[distinct];
47     if (distinct == 0) {
48       return new RegularImmutableMultiset<>(entryArray, EMPTY_ARRAY, 0, 0, ImmutableSet.of());
49     }
50     int tableSize = Hashing.closedTableSize(distinct, MAX_LOAD_FACTOR);
51     int mask = tableSize - 1;
52     @SuppressWarnings({"unchecked", "rawtypes"})
53     @Nullable
54     ImmutableEntry<E>[] hashTable = new @Nullable ImmutableEntry[tableSize];
55 
56     int index = 0;
57     int hashCode = 0;
58     long size = 0;
59     for (Entry<? extends E> entryWithWildcard : entries) {
60       @SuppressWarnings("unchecked") // safe because we only read from it
61       Entry<E> entry = (Entry<E>) entryWithWildcard;
62       E element = checkNotNull(entry.getElement());
63       int count = entry.getCount();
64       int hash = element.hashCode();
65       int bucket = Hashing.smear(hash) & mask;
66       ImmutableEntry<E> bucketHead = hashTable[bucket];
67       ImmutableEntry<E> newEntry;
68       if (bucketHead == null) {
69         boolean canReuseEntry =
70             entry instanceof ImmutableEntry && !(entry instanceof NonTerminalEntry);
71         newEntry =
72             canReuseEntry ? (ImmutableEntry<E>) entry : new ImmutableEntry<E>(element, count);
73       } else {
74         newEntry = new NonTerminalEntry<E>(element, count, bucketHead);
75       }
76       hashCode += hash ^ count;
77       entryArray[index++] = newEntry;
78       hashTable[bucket] = newEntry;
79       size += count;
80     }
81 
82     return hashFloodingDetected(hashTable)
83         ? JdkBackedImmutableMultiset.create(ImmutableList.asImmutableList(entryArray))
84         : new RegularImmutableMultiset<E>(
85             entryArray, hashTable, Ints.saturatedCast(size), hashCode, null);
86   }
87 
88   private static boolean hashFloodingDetected(@Nullable ImmutableEntry<?>[] hashTable) {
89     for (int i = 0; i < hashTable.length; i++) {
90       int bucketLength = 0;
91       for (ImmutableEntry<?> entry = hashTable[i]; entry != null; entry = entry.nextInBucket()) {
92         bucketLength++;
93         if (bucketLength > MAX_HASH_BUCKET_LENGTH) {
94           return true;
95         }
96       }
97     }
98     return false;
99   }
100 
101   /**
102    * Closed addressing tends to perform well even with high load factors. Being conservative here
103    * ensures that the table is still likely to be relatively sparse (hence it misses fast) while
104    * saving space.
105    */
106   @VisibleForTesting static final double MAX_LOAD_FACTOR = 1.0;
107 
108   /**
109    * Maximum allowed false positive probability of detecting a hash flooding attack given random
110    * input.
111    */
112   @VisibleForTesting static final double HASH_FLOODING_FPP = 0.001;
113 
114   /**
115    * Maximum allowed length of a hash table bucket before falling back to a j.u.HashMap based
116    * implementation. Experimentally determined.
117    */
118   @VisibleForTesting static final int MAX_HASH_BUCKET_LENGTH = 9;
119 
120   private final transient ImmutableEntry<E>[] entries;
121   private final transient @Nullable ImmutableEntry<?>[] hashTable;
122   private final transient int size;
123   private final transient int hashCode;
124 
125   @LazyInit @CheckForNull private transient ImmutableSet<E> elementSet;
126 
127   private RegularImmutableMultiset(
128       ImmutableEntry<E>[] entries,
129       @Nullable ImmutableEntry<?>[] hashTable,
130       int size,
131       int hashCode,
132       @CheckForNull ImmutableSet<E> elementSet) {
133     this.entries = entries;
134     this.hashTable = hashTable;
135     this.size = size;
136     this.hashCode = hashCode;
137     this.elementSet = elementSet;
138   }
139 
140   private static final class NonTerminalEntry<E> extends ImmutableEntry<E> {
141     private final ImmutableEntry<E> nextInBucket;
142 
143     NonTerminalEntry(E element, int count, ImmutableEntry<E> nextInBucket) {
144       super(element, count);
145       this.nextInBucket = nextInBucket;
146     }
147 
148     @Override
149     public ImmutableEntry<E> nextInBucket() {
150       return nextInBucket;
151     }
152   }
153 
154   @Override
155   boolean isPartialView() {
156     return false;
157   }
158 
159   @Override
160   public int count(@CheckForNull Object element) {
161     @Nullable ImmutableEntry<?>[] hashTable = this.hashTable;
162     if (element == null || hashTable.length == 0) {
163       return 0;
164     }
165     int hash = Hashing.smearedHash(element);
166     int mask = hashTable.length - 1;
167     for (ImmutableEntry<?> entry = hashTable[hash & mask];
168         entry != null;
169         entry = entry.nextInBucket()) {
170       if (Objects.equal(element, entry.getElement())) {
171         return entry.getCount();
172       }
173     }
174     return 0;
175   }
176 
177   @Override
178   public int size() {
179     return size;
180   }
181 
182   @Override
183   public ImmutableSet<E> elementSet() {
184     ImmutableSet<E> result = elementSet;
185     return (result == null) ? elementSet = new ElementSet<E>(Arrays.asList(entries), this) : result;
186   }
187 
188   @Override
189   Entry<E> getEntry(int index) {
190     return entries[index];
191   }
192 
193   @Override
194   public int hashCode() {
195     return hashCode;
196   }
197 }