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

1 /*
2  * Copyright (C) 2008 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.google.common.collect;
18 
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.base.Preconditions.checkPositionIndex;
21 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
22 import static com.google.common.collect.ImmutableMapEntry.createEntryArray;
23 
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.annotations.GwtIncompatible;
26 import com.google.common.annotations.VisibleForTesting;
27 import com.google.common.collect.ImmutableMapEntry.NonTerminalImmutableMapEntry;
28 import com.google.errorprone.annotations.CanIgnoreReturnValue;
29 import java.io.Serializable;
30 import java.util.function.BiConsumer;
31 import org.checkerframework.checker.nullness.qual.Nullable;
32 
33 /**
34  * Implementation of {@link ImmutableMap} with two or more entries.
35  *
36  * @author Jesse Wilson
37  * @author Kevin Bourrillion
38  * @author Gregory Kick
39  */
40 @GwtCompatible(serializable = true, emulated = true)
41 final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
42   @SuppressWarnings("unchecked")
43   static final ImmutableMap<Object, Object> EMPTY =
44       new RegularImmutableMap<>((Entry<Object, Object>[]) ImmutableMap.EMPTY_ENTRY_ARRAY, null, 0);
45 
46   /**
47    * Closed addressing tends to perform well even with high load factors. Being conservative here
48    * ensures that the table is still likely to be relatively sparse (hence it misses fast) while
49    * saving space.
50    */
51   @VisibleForTesting static final double MAX_LOAD_FACTOR = 1.2;
52 
53   /**
54    * Maximum allowed false positive probability of detecting a hash flooding attack given random
55    * input.
56    */
57   @VisibleForTesting static final double HASH_FLOODING_FPP = 0.001;
58 
59   /**
60    * Maximum allowed length of a hash table bucket before falling back to a j.u.HashMap based
61    * implementation. Experimentally determined.
62    */
63   @VisibleForTesting static final int MAX_HASH_BUCKET_LENGTH = 8;
64 
65   // entries in insertion order
66   @VisibleForTesting final transient Entry<K, V>[] entries;
67   // array of linked lists of entries
68   private final transient ImmutableMapEntry<K, V>[] table;
69   // 'and' with an int to get a table index
70   private final transient int mask;
71 
72   static <K, V> ImmutableMap<K, V> fromEntries(Entry<K, V>... entries) {
73     return fromEntryArray(entries.length, entries);
74   }
75 
76   /**
77    * Creates an ImmutableMap from the first n entries in entryArray. This implementation may replace
78    * the entries in entryArray with its own entry objects (though they will have the same key/value
79    * contents), and may take ownership of entryArray.
80    */
81   static <K, V> ImmutableMap<K, V> fromEntryArray(int n, Entry<K, V>[] entryArray) {
82     checkPositionIndex(n, entryArray.length);
83     if (n == 0) {
84       return (RegularImmutableMap<K, V>) EMPTY;
85     }
86     Entry<K, V>[] entries;
87     if (n == entryArray.length) {
88       entries = entryArray;
89     } else {
90       entries = createEntryArray(n);
91     }
92     int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
93     ImmutableMapEntry<K, V>[] table = createEntryArray(tableSize);
94     int mask = tableSize - 1;
95     for (int entryIndex = 0; entryIndex < n; entryIndex++) {
96       Entry<K, V> entry = entryArray[entryIndex];
97       K key = entry.getKey();
98       V value = entry.getValue();
99       checkEntryNotNull(key, value);
100       int tableIndex = Hashing.smear(key.hashCode()) & mask;
101       @Nullable ImmutableMapEntry<K, V> existing = table[tableIndex];
102       // prepend, not append, so the entries can be immutable
103       ImmutableMapEntry<K, V> newEntry =
104           (existing == null)
105               ? makeImmutable(entry, key, value)
106               : new NonTerminalImmutableMapEntry<K, V>(key, value, existing);
107       table[tableIndex] = newEntry;
108       entries[entryIndex] = newEntry;
109       int bucketSize = checkNoConflictInKeyBucket(key, newEntry, existing);
110       if (bucketSize > MAX_HASH_BUCKET_LENGTH) {
111         // probable hash flooding attack, fall back to j.u.HM based implementation and use its
112         // implementation of hash flooding protection
113         return JdkBackedImmutableMap.create(n, entryArray);
114       }
115     }
116     return new RegularImmutableMap<>(entries, table, mask);
117   }
118 
119   /** Makes an entry usable internally by a new ImmutableMap without rereading its contents. */
120   static <K, V> ImmutableMapEntry<K, V> makeImmutable(Entry<K, V> entry, K key, V value) {
121     boolean reusable =
122         entry instanceof ImmutableMapEntry && ((ImmutableMapEntry<K, V>) entry).isReusable();
123     return reusable ? (ImmutableMapEntry<K, V>) entry : new ImmutableMapEntry<K, V>(key, value);
124   }
125 
126   /** Makes an entry usable internally by a new ImmutableMap. */
127   static <K, V> ImmutableMapEntry<K, V> makeImmutable(Entry<K, V> entry) {
128     return makeImmutable(entry, entry.getKey(), entry.getValue());
129   }
130 
131   private RegularImmutableMap(Entry<K, V>[] entries, ImmutableMapEntry<K, V>[] table, int mask) {
132     this.entries = entries;
133     this.table = table;
134     this.mask = mask;
135   }
136 
137   /**
138    * @return number of entries in this bucket
139    * @throws IllegalArgumentException if another entry in the bucket has the same key
140    */
141   @CanIgnoreReturnValue
142   static int checkNoConflictInKeyBucket(
143       Object key, Entry<?, ?> entry, @Nullable ImmutableMapEntry<?, ?> keyBucketHead) {
144     int bucketSize = 0;
145     for (; keyBucketHead != null; keyBucketHead = keyBucketHead.getNextInKeyBucket()) {
146       checkNoConflict(!key.equals(keyBucketHead.getKey()), "key", entry, keyBucketHead);
147       bucketSize++;
148     }
149     return bucketSize;
150   }
151 
152   @Override
153   public V get(@Nullable Object key) {
154     return get(key, table, mask);
155   }
156 
157   static <V> @Nullable V get(
158       @Nullable Object key, ImmutableMapEntry<?, V> @Nullable [] keyTable, int mask) {
159     if (key == null || keyTable == null) {
160       return null;
161     }
162     int index = Hashing.smear(key.hashCode()) & mask;
163     for (ImmutableMapEntry<?, V> entry = keyTable[index];
164         entry != null;
165         entry = entry.getNextInKeyBucket()) {
166       Object candidateKey = entry.getKey();
167 
168       /*
169        * Assume that equals uses the == optimization when appropriate, and that
170        * it would check hash codes as an optimization when appropriate. If we
171        * did these things, it would just make things worse for the most
172        * performance-conscious users.
173        */
174       if (key.equals(candidateKey)) {
175         return entry.getValue();
176       }
177     }
178     return null;
179   }
180 
181   @Override
182   public void forEach(BiConsumer<? super K, ? super V> action) {
183     checkNotNull(action);
184     for (Entry<K, V> entry : entries) {
185       action.accept(entry.getKey(), entry.getValue());
186     }
187   }
188 
189   @Override
190   public int size() {
191     return entries.length;
192   }
193 
194   @Override
195   boolean isPartialView() {
196     return false;
197   }
198 
199   @Override
200   ImmutableSet<Entry<K, V>> createEntrySet() {
201     return new ImmutableMapEntrySet.RegularEntrySet<>(this, entries);
202   }
203 
204   @Override
205   ImmutableSet<K> createKeySet() {
206     return new KeySet<>(this);
207   }
208 
209   @GwtCompatible(emulated = true)
210   private static final class KeySet<K> extends IndexedImmutableSet<K> {
211     private final RegularImmutableMap<K, ?> map;
212 
213     KeySet(RegularImmutableMap<K, ?> map) {
214       this.map = map;
215     }
216 
217     @Override
218     K get(int index) {
219       return map.entries[index].getKey();
220     }
221 
222     @Override
223     public boolean contains(Object object) {
224       return map.containsKey(object);
225     }
226 
227     @Override
228     boolean isPartialView() {
229       return true;
230     }
231 
232     @Override
233     public int size() {
234       return map.size();
235     }
236 
237     // No longer used for new writes, but kept so that old data can still be read.
238     @GwtIncompatible // serialization
239     @SuppressWarnings("unused")
240     private static class SerializedForm<K> implements Serializable {
241       final ImmutableMap<K, ?> map;
242 
243       SerializedForm(ImmutableMap<K, ?> map) {
244         this.map = map;
245       }
246 
247       Object readResolve() {
248         return map.keySet();
249       }
250 
251       private static final long serialVersionUID = 0;
252     }
253   }
254 
255   @Override
256   ImmutableCollection<V> createValues() {
257     return new Values<>(this);
258   }
259 
260   @GwtCompatible(emulated = true)
261   private static final class Values<K, V> extends ImmutableList<V> {
262     final RegularImmutableMap<K, V> map;
263 
264     Values(RegularImmutableMap<K, V> map) {
265       this.map = map;
266     }
267 
268     @Override
269     public V get(int index) {
270       return map.entries[index].getValue();
271     }
272 
273     @Override
274     public int size() {
275       return map.size();
276     }
277 
278     @Override
279     boolean isPartialView() {
280       return true;
281     }
282 
283     // No longer used for new writes, but kept so that old data can still be read.
284     @GwtIncompatible // serialization
285     @SuppressWarnings("unused")
286     private static class SerializedForm<V> implements Serializable {
287       final ImmutableMap<?, V> map;
288 
289       SerializedForm(ImmutableMap<?, V> map) {
290         this.map = map;
291       }
292 
293       Object readResolve() {
294         return map.values();
295       }
296 
297       private static final long serialVersionUID = 0;
298     }
299   }
300 
301   // This class is never actually serialized directly, but we have to make the
302   // warning go away (and suppressing would suppress for all nested classes too)
303   private static final long serialVersionUID = 0;
304 }