1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.collect.ImmutableMapEntry.TerminalEntry;
23
24 import java.io.Serializable;
25
26 import javax.annotation.Nullable;
27
28
29
30
31
32
33 @GwtCompatible(serializable = true, emulated = true)
34 @SuppressWarnings("serial")
35 class RegularImmutableBiMap<K, V> extends ImmutableBiMap<K, V> {
36
37 static final double MAX_LOAD_FACTOR = 1.2;
38
39 private final transient ImmutableMapEntry<K, V>[] keyTable;
40 private final transient ImmutableMapEntry<K, V>[] valueTable;
41 private final transient ImmutableMapEntry<K, V>[] entries;
42 private final transient int mask;
43 private final transient int hashCode;
44
45 RegularImmutableBiMap(TerminalEntry<?, ?>... entriesToAdd) {
46 this(entriesToAdd.length, entriesToAdd);
47 }
48
49
50
51
52
53
54
55 RegularImmutableBiMap(int n, TerminalEntry<?, ?>[] entriesToAdd) {
56 int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
57 this.mask = tableSize - 1;
58 ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
59 ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
60 ImmutableMapEntry<K, V>[] entries = createEntryArray(n);
61 int hashCode = 0;
62
63 for (int i = 0; i < n; i++) {
64 @SuppressWarnings("unchecked")
65 TerminalEntry<K, V> entry = (TerminalEntry<K, V>) entriesToAdd[i];
66 K key = entry.getKey();
67 V value = entry.getValue();
68
69 int keyHash = key.hashCode();
70 int valueHash = value.hashCode();
71 int keyBucket = Hashing.smear(keyHash) & mask;
72 int valueBucket = Hashing.smear(valueHash) & mask;
73
74 ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
75 for (ImmutableMapEntry<K, V> keyEntry = nextInKeyBucket; keyEntry != null;
76 keyEntry = keyEntry.getNextInKeyBucket()) {
77 checkNoConflict(!key.equals(keyEntry.getKey()), "key", entry, keyEntry);
78 }
79 ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
80 for (ImmutableMapEntry<K, V> valueEntry = nextInValueBucket; valueEntry != null;
81 valueEntry = valueEntry.getNextInValueBucket()) {
82 checkNoConflict(!value.equals(valueEntry.getValue()), "value", entry, valueEntry);
83 }
84 ImmutableMapEntry<K, V> newEntry =
85 (nextInKeyBucket == null && nextInValueBucket == null)
86 ? entry
87 : new NonTerminalBiMapEntry<K, V>(entry, nextInKeyBucket, nextInValueBucket);
88 keyTable[keyBucket] = newEntry;
89 valueTable[valueBucket] = newEntry;
90 entries[i] = newEntry;
91 hashCode += keyHash ^ valueHash;
92 }
93
94 this.keyTable = keyTable;
95 this.valueTable = valueTable;
96 this.entries = entries;
97 this.hashCode = hashCode;
98 }
99
100
101
102
103 RegularImmutableBiMap(Entry<?, ?>[] entriesToAdd) {
104 int n = entriesToAdd.length;
105 int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
106 this.mask = tableSize - 1;
107 ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
108 ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
109 ImmutableMapEntry<K, V>[] entries = createEntryArray(n);
110 int hashCode = 0;
111
112 for (int i = 0; i < n; i++) {
113 @SuppressWarnings("unchecked")
114 Entry<K, V> entry = (Entry<K, V>) entriesToAdd[i];
115 K key = entry.getKey();
116 V value = entry.getValue();
117 checkEntryNotNull(key, value);
118 int keyHash = key.hashCode();
119 int valueHash = value.hashCode();
120 int keyBucket = Hashing.smear(keyHash) & mask;
121 int valueBucket = Hashing.smear(valueHash) & mask;
122
123 ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
124 for (ImmutableMapEntry<K, V> keyEntry = nextInKeyBucket; keyEntry != null;
125 keyEntry = keyEntry.getNextInKeyBucket()) {
126 checkNoConflict(!key.equals(keyEntry.getKey()), "key", entry, keyEntry);
127 }
128 ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
129 for (ImmutableMapEntry<K, V> valueEntry = nextInValueBucket; valueEntry != null;
130 valueEntry = valueEntry.getNextInValueBucket()) {
131 checkNoConflict(!value.equals(valueEntry.getValue()), "value", entry, valueEntry);
132 }
133 ImmutableMapEntry<K, V> newEntry =
134 (nextInKeyBucket == null && nextInValueBucket == null)
135 ? new TerminalEntry<K, V>(key, value)
136 : new NonTerminalBiMapEntry<K, V>(key, value, nextInKeyBucket, nextInValueBucket);
137 keyTable[keyBucket] = newEntry;
138 valueTable[valueBucket] = newEntry;
139 entries[i] = newEntry;
140 hashCode += keyHash ^ valueHash;
141 }
142
143 this.keyTable = keyTable;
144 this.valueTable = valueTable;
145 this.entries = entries;
146 this.hashCode = hashCode;
147 }
148
149 private static final class NonTerminalBiMapEntry<K, V> extends ImmutableMapEntry<K, V> {
150 @Nullable private final ImmutableMapEntry<K, V> nextInKeyBucket;
151 @Nullable private final ImmutableMapEntry<K, V> nextInValueBucket;
152
153 NonTerminalBiMapEntry(K key, V value, @Nullable ImmutableMapEntry<K, V> nextInKeyBucket,
154 @Nullable ImmutableMapEntry<K, V> nextInValueBucket) {
155 super(key, value);
156 this.nextInKeyBucket = nextInKeyBucket;
157 this.nextInValueBucket = nextInValueBucket;
158 }
159
160 NonTerminalBiMapEntry(ImmutableMapEntry<K, V> contents,
161 @Nullable ImmutableMapEntry<K, V> nextInKeyBucket,
162 @Nullable ImmutableMapEntry<K, V> nextInValueBucket) {
163 super(contents);
164 this.nextInKeyBucket = nextInKeyBucket;
165 this.nextInValueBucket = nextInValueBucket;
166 }
167
168 @Override
169 @Nullable
170 ImmutableMapEntry<K, V> getNextInKeyBucket() {
171 return nextInKeyBucket;
172 }
173
174 @Override
175 @Nullable
176 ImmutableMapEntry<K, V> getNextInValueBucket() {
177 return nextInValueBucket;
178 }
179 }
180
181 @SuppressWarnings("unchecked")
182 private static <K, V> ImmutableMapEntry<K, V>[] createEntryArray(int length) {
183 return new ImmutableMapEntry[length];
184 }
185
186 @Override
187 @Nullable
188 public V get(@Nullable Object key) {
189 if (key == null) {
190 return null;
191 }
192 int bucket = Hashing.smear(key.hashCode()) & mask;
193 for (ImmutableMapEntry<K, V> entry = keyTable[bucket]; entry != null;
194 entry = entry.getNextInKeyBucket()) {
195 if (key.equals(entry.getKey())) {
196 return entry.getValue();
197 }
198 }
199 return null;
200 }
201
202 @Override
203 ImmutableSet<Entry<K, V>> createEntrySet() {
204 return new ImmutableMapEntrySet<K, V>() {
205 @Override
206 ImmutableMap<K, V> map() {
207 return RegularImmutableBiMap.this;
208 }
209
210 @Override
211 public UnmodifiableIterator<Entry<K, V>> iterator() {
212 return asList().iterator();
213 }
214
215 @Override
216 ImmutableList<Entry<K, V>> createAsList() {
217 return new RegularImmutableAsList<Entry<K, V>>(this, entries);
218 }
219
220 @Override
221 boolean isHashCodeFast() {
222 return true;
223 }
224
225 @Override
226 public int hashCode() {
227 return hashCode;
228 }
229 };
230 }
231
232 @Override
233 boolean isPartialView() {
234 return false;
235 }
236
237 @Override
238 public int size() {
239 return entries.length;
240 }
241
242 private transient ImmutableBiMap<V, K> inverse;
243
244 @Override
245 public ImmutableBiMap<V, K> inverse() {
246 ImmutableBiMap<V, K> result = inverse;
247 return (result == null) ? inverse = new Inverse() : result;
248 }
249
250 private final class Inverse extends ImmutableBiMap<V, K> {
251
252 @Override
253 public int size() {
254 return inverse().size();
255 }
256
257 @Override
258 public ImmutableBiMap<K, V> inverse() {
259 return RegularImmutableBiMap.this;
260 }
261
262 @Override
263 public K get(@Nullable Object value) {
264 if (value == null) {
265 return null;
266 }
267 int bucket = Hashing.smear(value.hashCode()) & mask;
268 for (ImmutableMapEntry<K, V> entry = valueTable[bucket]; entry != null;
269 entry = entry.getNextInValueBucket()) {
270 if (value.equals(entry.getValue())) {
271 return entry.getKey();
272 }
273 }
274 return null;
275 }
276
277 @Override
278 ImmutableSet<Entry<V, K>> createEntrySet() {
279 return new InverseEntrySet();
280 }
281
282 final class InverseEntrySet extends ImmutableMapEntrySet<V, K> {
283 @Override
284 ImmutableMap<V, K> map() {
285 return Inverse.this;
286 }
287
288 @Override
289 boolean isHashCodeFast() {
290 return true;
291 }
292
293 @Override
294 public int hashCode() {
295 return hashCode;
296 }
297
298 @Override
299 public UnmodifiableIterator<Entry<V, K>> iterator() {
300 return asList().iterator();
301 }
302
303 @Override
304 ImmutableList<Entry<V, K>> createAsList() {
305 return new ImmutableAsList<Entry<V, K>>() {
306 @Override
307 public Entry<V, K> get(int index) {
308 Entry<K, V> entry = entries[index];
309 return Maps.immutableEntry(entry.getValue(), entry.getKey());
310 }
311
312 @Override
313 ImmutableCollection<Entry<V, K>> delegateCollection() {
314 return InverseEntrySet.this;
315 }
316 };
317 }
318 }
319
320 @Override
321 boolean isPartialView() {
322 return false;
323 }
324
325 @Override
326 Object writeReplace() {
327 return new InverseSerializedForm<K, V>(RegularImmutableBiMap.this);
328 }
329 }
330
331 private static class InverseSerializedForm<K, V> implements Serializable {
332 private final ImmutableBiMap<K, V> forward;
333
334 InverseSerializedForm(ImmutableBiMap<K, V> forward) {
335 this.forward = forward;
336 }
337
338 Object readResolve() {
339 return forward.inverse();
340 }
341
342 private static final long serialVersionUID = 1;
343 }
344 }