View Javadoc
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.concurrent.LazyInit;
29  import com.google.j2objc.annotations.RetainedWith;
30  import com.google.j2objc.annotations.WeakOuter;
31  import java.io.Serializable;
32  import java.util.function.BiConsumer;
33  import java.util.function.Consumer;
34  import javax.annotation.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
53    final transient Entry<K, V>[] entries;
54    private final transient int mask;
55    private final transient int hashCode;
56  
57    static <K, V> RegularImmutableBiMap<K, V> fromEntries(Entry<K, V>... entries) {
58      return fromEntryArray(entries.length, entries);
59    }
60  
61    static <K, V> RegularImmutableBiMap<K, V> fromEntryArray(int n, Entry<K, V>[] entryArray) {
62      checkPositionIndex(n, entryArray.length);
63      int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
64      int mask = tableSize - 1;
65      ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
66      ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
67      Entry<K, V>[] entries;
68      if (n == entryArray.length) {
69        entries = entryArray;
70      } else {
71        entries = createEntryArray(n);
72      }
73      int hashCode = 0;
74  
75      for (int i = 0; i < n; i++) {
76        @SuppressWarnings("unchecked")
77        Entry<K, V> entry = entryArray[i];
78        K key = entry.getKey();
79        V value = entry.getValue();
80        checkEntryNotNull(key, value);
81        int keyHash = key.hashCode();
82        int valueHash = value.hashCode();
83        int keyBucket = Hashing.smear(keyHash) & mask;
84        int valueBucket = Hashing.smear(valueHash) & mask;
85  
86        ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
87        checkNoConflictInKeyBucket(key, entry, nextInKeyBucket);
88        ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
89        checkNoConflictInValueBucket(value, entry, nextInValueBucket);
90        ImmutableMapEntry<K, V> newEntry;
91        if (nextInValueBucket == null && nextInKeyBucket == null) {
92          /*
93           * TODO(lowasser): consider using a NonTerminalImmutableMapEntry when nextInKeyBucket is
94           * nonnull but nextInValueBucket is null.  This may save a few bytes on some platforms, but
95           * 2-morphic call sites are often optimized much better than 3-morphic, so it'd require
96           * benchmarking.
97           */
98          boolean reusable =
99              entry instanceof ImmutableMapEntry && ((ImmutableMapEntry<K, V>) entry).isReusable();
100         newEntry =
101             reusable ? (ImmutableMapEntry<K, V>) entry : new ImmutableMapEntry<K, V>(key, value);
102       } else {
103         newEntry =
104             new NonTerminalImmutableBiMapEntry<>(key, value, nextInKeyBucket, nextInValueBucket);
105       }
106       keyTable[keyBucket] = newEntry;
107       valueTable[valueBucket] = newEntry;
108       entries[i] = newEntry;
109       hashCode += keyHash ^ valueHash;
110     }
111     return new RegularImmutableBiMap<>(keyTable, valueTable, entries, mask, hashCode);
112   }
113 
114   private RegularImmutableBiMap(
115       ImmutableMapEntry<K, V>[] keyTable,
116       ImmutableMapEntry<K, V>[] valueTable,
117       Entry<K, V>[] entries,
118       int mask,
119       int hashCode) {
120     this.keyTable = keyTable;
121     this.valueTable = valueTable;
122     this.entries = entries;
123     this.mask = mask;
124     this.hashCode = hashCode;
125   }
126 
127   // checkNoConflictInKeyBucket is static imported from RegularImmutableMap
128 
129   private static void checkNoConflictInValueBucket(
130       Object value, Entry<?, ?> entry, @Nullable ImmutableMapEntry<?, ?> valueBucketHead) {
131     for (; valueBucketHead != null; valueBucketHead = valueBucketHead.getNextInValueBucket()) {
132       checkNoConflict(!value.equals(valueBucketHead.getValue()), "value", entry, valueBucketHead);
133     }
134   }
135 
136   @Override
137   @Nullable
138   public V get(@Nullable Object key) {
139     return (keyTable == null) ? null : RegularImmutableMap.get(key, keyTable, mask);
140   }
141 
142   @Override
143   ImmutableSet<Entry<K, V>> createEntrySet() {
144     return isEmpty()
145         ? ImmutableSet.<Entry<K, V>>of()
146         : new ImmutableMapEntrySet.RegularEntrySet<K, V>(this, entries);
147   }
148 
149   @Override
150   ImmutableSet<K> createKeySet() {
151     return new ImmutableMapKeySet<>(this);
152   }
153 
154   @Override
155   public void forEach(BiConsumer<? super K, ? super V> action) {
156     checkNotNull(action);
157     for (Entry<K, V> entry : entries) {
158       action.accept(entry.getKey(), entry.getValue());
159     }
160   }
161 
162   @Override
163   boolean isHashCodeFast() {
164     return true;
165   }
166 
167   @Override
168   public int hashCode() {
169     return hashCode;
170   }
171 
172   @Override
173   boolean isPartialView() {
174     return false;
175   }
176 
177   @Override
178   public int size() {
179     return entries.length;
180   }
181 
182   @LazyInit
183   @RetainedWith
184   private transient ImmutableBiMap<V, K> inverse;
185 
186   @Override
187   public ImmutableBiMap<V, K> inverse() {
188     if (isEmpty()) {
189       return ImmutableBiMap.of();
190     }
191     ImmutableBiMap<V, K> result = inverse;
192     return (result == null) ? inverse = new Inverse() : result;
193   }
194 
195   private final class Inverse extends ImmutableBiMap<V, K> {
196 
197     @Override
198     public int size() {
199       return inverse().size();
200     }
201 
202     @Override
203     public ImmutableBiMap<K, V> inverse() {
204       return RegularImmutableBiMap.this;
205     }
206 
207     @Override
208     public void forEach(BiConsumer<? super V, ? super K> action) {
209       checkNotNull(action);
210       RegularImmutableBiMap.this.forEach((k, v) -> action.accept(v, k));
211     }
212 
213     @Override
214     public K get(@Nullable Object value) {
215       if (value == null || valueTable == null) {
216         return null;
217       }
218       int bucket = Hashing.smear(value.hashCode()) & mask;
219       for (ImmutableMapEntry<K, V> entry = valueTable[bucket];
220           entry != null;
221           entry = entry.getNextInValueBucket()) {
222         if (value.equals(entry.getValue())) {
223           return entry.getKey();
224         }
225       }
226       return null;
227     }
228 
229     @Override
230     ImmutableSet<V> createKeySet() {
231       return new ImmutableMapKeySet<>(this);
232     }
233 
234     @Override
235     ImmutableSet<Entry<V, K>> createEntrySet() {
236       return new InverseEntrySet();
237     }
238 
239     @WeakOuter
240     final class InverseEntrySet extends ImmutableMapEntrySet<V, K> {
241       @Override
242       ImmutableMap<V, K> map() {
243         return Inverse.this;
244       }
245 
246       @Override
247       boolean isHashCodeFast() {
248         return true;
249       }
250 
251       @Override
252       public int hashCode() {
253         return hashCode;
254       }
255 
256       @Override
257       public UnmodifiableIterator<Entry<V, K>> iterator() {
258         return asList().iterator();
259       }
260 
261       @Override
262       public void forEach(Consumer<? super Entry<V, K>> action) {
263         asList().forEach(action);
264       }
265 
266       @Override
267       ImmutableList<Entry<V, K>> createAsList() {
268         return new ImmutableAsList<Entry<V, K>>() {
269           @Override
270           public Entry<V, K> get(int index) {
271             Entry<K, V> entry = entries[index];
272             return Maps.immutableEntry(entry.getValue(), entry.getKey());
273           }
274 
275           @Override
276           ImmutableCollection<Entry<V, K>> delegateCollection() {
277             return InverseEntrySet.this;
278           }
279         };
280       }
281     }
282 
283     @Override
284     boolean isPartialView() {
285       return false;
286     }
287 
288     @Override
289     Object writeReplace() {
290       return new InverseSerializedForm<>(RegularImmutableBiMap.this);
291     }
292   }
293 
294   private static class InverseSerializedForm<K, V> implements Serializable {
295     private final ImmutableBiMap<K, V> forward;
296 
297     InverseSerializedForm(ImmutableBiMap<K, V> forward) {
298       this.forward = forward;
299     }
300 
301     Object readResolve() {
302       return forward.inverse();
303     }
304 
305     private static final long serialVersionUID = 1;
306   }
307 }