Coverage Summary for Class: RegularImmutableBiMap (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 import static com.google.common.collect.RegularImmutableMap.checkNoConflictInKeyBucket;
24 
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.common.annotations.VisibleForTesting;
27 import com.google.common.collect.ImmutableMapEntry.NonTerminalImmutableBiMapEntry;
28 import com.google.errorprone.annotations.CanIgnoreReturnValue;
29 import com.google.errorprone.annotations.concurrent.LazyInit;
30 import com.google.j2objc.annotations.RetainedWith;
31 import java.io.Serializable;
32 import java.util.function.BiConsumer;
33 import java.util.function.Consumer;
34 import org.checkerframework.checker.nullness.qual.Nullable;
35 
36 /**
37  * Bimap with zero or more mappings.
38  *
39  * @author Louis Wasserman
40  */
41 @GwtCompatible(serializable = true, emulated = true)
42 @SuppressWarnings("serial") // uses writeReplace(), not default serialization
43 class RegularImmutableBiMap<K, V> extends ImmutableBiMap<K, V> {
44   static final RegularImmutableBiMap<Object, Object> EMPTY =
45       new RegularImmutableBiMap<>(
46           null, null, (Entry<Object, Object>[]) ImmutableMap.EMPTY_ENTRY_ARRAY, 0, 0);
47 
48   static final double MAX_LOAD_FACTOR = 1.2;
49 
50   private final transient ImmutableMapEntry<K, V>[] keyTable;
51   private final transient ImmutableMapEntry<K, V>[] valueTable;
52   @VisibleForTesting final transient Entry<K, V>[] entries;
53   private final transient int mask;
54   private final transient int hashCode;
55 
56   static <K, V> ImmutableBiMap<K, V> fromEntries(Entry<K, V>... entries) {
57     return fromEntryArray(entries.length, entries);
58   }
59 
60   static <K, V> ImmutableBiMap<K, V> fromEntryArray(int n, Entry<K, V>[] entryArray) {
61     checkPositionIndex(n, entryArray.length);
62     int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
63     int mask = tableSize - 1;
64     ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
65     ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
66     Entry<K, V>[] entries;
67     if (n == entryArray.length) {
68       entries = entryArray;
69     } else {
70       entries = createEntryArray(n);
71     }
72     int hashCode = 0;
73 
74     for (int i = 0; i < n; i++) {
75       @SuppressWarnings("unchecked")
76       Entry<K, V> entry = entryArray[i];
77       K key = entry.getKey();
78       V value = entry.getValue();
79       checkEntryNotNull(key, value);
80       int keyHash = key.hashCode();
81       int valueHash = value.hashCode();
82       int keyBucket = Hashing.smear(keyHash) & mask;
83       int valueBucket = Hashing.smear(valueHash) & mask;
84 
85       ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
86       int keyBucketLength = checkNoConflictInKeyBucket(key, entry, nextInKeyBucket);
87       ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
88       int valueBucketLength = checkNoConflictInValueBucket(value, entry, nextInValueBucket);
89       if (keyBucketLength > RegularImmutableMap.MAX_HASH_BUCKET_LENGTH
90           || valueBucketLength > RegularImmutableMap.MAX_HASH_BUCKET_LENGTH) {
91         return JdkBackedImmutableBiMap.create(n, entryArray);
92       }
93       ImmutableMapEntry<K, V> newEntry =
94           (nextInValueBucket == null && nextInKeyBucket == null)
95               ? RegularImmutableMap.makeImmutable(entry, key, value)
96               : new NonTerminalImmutableBiMapEntry<>(
97                   key, value, nextInKeyBucket, nextInValueBucket);
98       keyTable[keyBucket] = newEntry;
99       valueTable[valueBucket] = newEntry;
100       entries[i] = newEntry;
101       hashCode += keyHash ^ valueHash;
102     }
103     return new RegularImmutableBiMap<>(keyTable, valueTable, entries, mask, hashCode);
104   }
105 
106   private RegularImmutableBiMap(
107       ImmutableMapEntry<K, V>[] keyTable,
108       ImmutableMapEntry<K, V>[] valueTable,
109       Entry<K, V>[] entries,
110       int mask,
111       int hashCode) {
112     this.keyTable = keyTable;
113     this.valueTable = valueTable;
114     this.entries = entries;
115     this.mask = mask;
116     this.hashCode = hashCode;
117   }
118 
119   // checkNoConflictInKeyBucket is static imported from RegularImmutableMap
120 
121   /**
122    * @return number of entries in this bucket
123    * @throws IllegalArgumentException if another entry in the bucket has the same key
124    */
125   @CanIgnoreReturnValue
126   private static int checkNoConflictInValueBucket(
127       Object value, Entry<?, ?> entry, @Nullable ImmutableMapEntry<?, ?> valueBucketHead) {
128     int bucketSize = 0;
129     for (; valueBucketHead != null; valueBucketHead = valueBucketHead.getNextInValueBucket()) {
130       checkNoConflict(!value.equals(valueBucketHead.getValue()), "value", entry, valueBucketHead);
131       bucketSize++;
132     }
133     return bucketSize;
134   }
135 
136   @Override
137   public @Nullable V get(@Nullable Object key) {
138     return (keyTable == null) ? null : RegularImmutableMap.get(key, keyTable, mask);
139   }
140 
141   @Override
142   ImmutableSet<Entry<K, V>> createEntrySet() {
143     return isEmpty()
144         ? ImmutableSet.<Entry<K, V>>of()
145         : new ImmutableMapEntrySet.RegularEntrySet<K, V>(this, entries);
146   }
147 
148   @Override
149   ImmutableSet<K> createKeySet() {
150     return new ImmutableMapKeySet<>(this);
151   }
152 
153   @Override
154   public void forEach(BiConsumer<? super K, ? super V> action) {
155     checkNotNull(action);
156     for (Entry<K, V> entry : entries) {
157       action.accept(entry.getKey(), entry.getValue());
158     }
159   }
160 
161   @Override
162   boolean isHashCodeFast() {
163     return true;
164   }
165 
166   @Override
167   public int hashCode() {
168     return hashCode;
169   }
170 
171   @Override
172   boolean isPartialView() {
173     return false;
174   }
175 
176   @Override
177   public int size() {
178     return entries.length;
179   }
180 
181   @LazyInit @RetainedWith private transient ImmutableBiMap<V, K> inverse;
182 
183   @Override
184   public ImmutableBiMap<V, K> inverse() {
185     if (isEmpty()) {
186       return ImmutableBiMap.of();
187     }
188     ImmutableBiMap<V, K> result = inverse;
189     return (result == null) ? inverse = new Inverse() : result;
190   }
191 
192   private final class Inverse extends ImmutableBiMap<V, K> {
193 
194     @Override
195     public int size() {
196       return inverse().size();
197     }
198 
199     @Override
200     public ImmutableBiMap<K, V> inverse() {
201       return RegularImmutableBiMap.this;
202     }
203 
204     @Override
205     public void forEach(BiConsumer<? super V, ? super K> action) {
206       checkNotNull(action);
207       RegularImmutableBiMap.this.forEach((k, v) -> action.accept(v, k));
208     }
209 
210     @Override
211     public K get(@Nullable Object value) {
212       if (value == null || valueTable == null) {
213         return null;
214       }
215       int bucket = Hashing.smear(value.hashCode()) & mask;
216       for (ImmutableMapEntry<K, V> entry = valueTable[bucket];
217           entry != null;
218           entry = entry.getNextInValueBucket()) {
219         if (value.equals(entry.getValue())) {
220           return entry.getKey();
221         }
222       }
223       return null;
224     }
225 
226     @Override
227     ImmutableSet<V> createKeySet() {
228       return new ImmutableMapKeySet<>(this);
229     }
230 
231     @Override
232     ImmutableSet<Entry<V, K>> createEntrySet() {
233       return new InverseEntrySet();
234     }
235 
236     final class InverseEntrySet extends ImmutableMapEntrySet<V, K> {
237       @Override
238       ImmutableMap<V, K> map() {
239         return Inverse.this;
240       }
241 
242       @Override
243       boolean isHashCodeFast() {
244         return true;
245       }
246 
247       @Override
248       public int hashCode() {
249         return hashCode;
250       }
251 
252       @Override
253       public UnmodifiableIterator<Entry<V, K>> iterator() {
254         return asList().iterator();
255       }
256 
257       @Override
258       public void forEach(Consumer<? super Entry<V, K>> action) {
259         asList().forEach(action);
260       }
261 
262       @Override
263       ImmutableList<Entry<V, K>> createAsList() {
264         return new ImmutableAsList<Entry<V, K>>() {
265           @Override
266           public Entry<V, K> get(int index) {
267             Entry<K, V> entry = entries[index];
268             return Maps.immutableEntry(entry.getValue(), entry.getKey());
269           }
270 
271           @Override
272           ImmutableCollection<Entry<V, K>> delegateCollection() {
273             return InverseEntrySet.this;
274           }
275         };
276       }
277     }
278 
279     @Override
280     boolean isPartialView() {
281       return false;
282     }
283 
284     @Override
285     Object writeReplace() {
286       return new InverseSerializedForm<>(RegularImmutableBiMap.this);
287     }
288   }
289 
290   private static class InverseSerializedForm<K, V> implements Serializable {
291     private final ImmutableBiMap<K, V> forward;
292 
293     InverseSerializedForm(ImmutableBiMap<K, V> forward) {
294       this.forward = forward;
295     }
296 
297     Object readResolve() {
298       return forward.inverse();
299     }
300 
301     private static final long serialVersionUID = 1;
302   }
303 }