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.checkNonnegative;
20 import static com.google.common.collect.CollectPreconditions.checkRemove;
21
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.common.annotations.GwtIncompatible;
24 import com.google.common.annotations.VisibleForTesting;
25 import com.google.common.base.Objects;
26
27 import java.io.IOException;
28 import java.io.ObjectInputStream;
29 import java.io.ObjectOutputStream;
30 import java.util.Arrays;
31 import java.util.Collection;
32 import java.util.ConcurrentModificationException;
33 import java.util.Iterator;
34 import java.util.LinkedHashMap;
35 import java.util.LinkedHashSet;
36 import java.util.Map;
37 import java.util.NoSuchElementException;
38 import java.util.Set;
39
40 import javax.annotation.Nullable;
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 @GwtCompatible(serializable = true, emulated = true)
82 public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
83
84
85
86
87
88 public static <K, V> LinkedHashMultimap<K, V> create() {
89 return new LinkedHashMultimap<K, V>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
90 }
91
92
93
94
95
96
97
98
99
100
101 public static <K, V> LinkedHashMultimap<K, V> create(
102 int expectedKeys, int expectedValuesPerKey) {
103 return new LinkedHashMultimap<K, V>(
104 Maps.capacity(expectedKeys),
105 Maps.capacity(expectedValuesPerKey));
106 }
107
108
109
110
111
112
113
114
115
116
117 public static <K, V> LinkedHashMultimap<K, V> create(
118 Multimap<? extends K, ? extends V> multimap) {
119 LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
120 result.putAll(multimap);
121 return result;
122 }
123
124 private interface ValueSetLink<K, V> {
125 ValueSetLink<K, V> getPredecessorInValueSet();
126 ValueSetLink<K, V> getSuccessorInValueSet();
127
128 void setPredecessorInValueSet(ValueSetLink<K, V> entry);
129 void setSuccessorInValueSet(ValueSetLink<K, V> entry);
130 }
131
132 private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
133 pred.setSuccessorInValueSet(succ);
134 succ.setPredecessorInValueSet(pred);
135 }
136
137 private static <K, V> void succeedsInMultimap(
138 ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
139 pred.setSuccessorInMultimap(succ);
140 succ.setPredecessorInMultimap(pred);
141 }
142
143 private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) {
144 succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
145 }
146
147 private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) {
148 succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
149 }
150
151
152
153
154
155
156
157 @VisibleForTesting
158 static final class ValueEntry<K, V> extends ImmutableEntry<K, V>
159 implements ValueSetLink<K, V> {
160 final int smearedValueHash;
161
162 @Nullable ValueEntry<K, V> nextInValueBucket;
163
164 ValueSetLink<K, V> predecessorInValueSet;
165 ValueSetLink<K, V> successorInValueSet;
166
167 ValueEntry<K, V> predecessorInMultimap;
168 ValueEntry<K, V> successorInMultimap;
169
170 ValueEntry(@Nullable K key, @Nullable V value, int smearedValueHash,
171 @Nullable ValueEntry<K, V> nextInValueBucket) {
172 super(key, value);
173 this.smearedValueHash = smearedValueHash;
174 this.nextInValueBucket = nextInValueBucket;
175 }
176
177 boolean matchesValue(@Nullable Object v, int smearedVHash) {
178 return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
179 }
180
181 @Override
182 public ValueSetLink<K, V> getPredecessorInValueSet() {
183 return predecessorInValueSet;
184 }
185
186 @Override
187 public ValueSetLink<K, V> getSuccessorInValueSet() {
188 return successorInValueSet;
189 }
190
191 @Override
192 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
193 predecessorInValueSet = entry;
194 }
195
196 @Override
197 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
198 successorInValueSet = entry;
199 }
200
201 public ValueEntry<K, V> getPredecessorInMultimap() {
202 return predecessorInMultimap;
203 }
204
205 public ValueEntry<K, V> getSuccessorInMultimap() {
206 return successorInMultimap;
207 }
208
209 public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
210 this.successorInMultimap = multimapSuccessor;
211 }
212
213 public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
214 this.predecessorInMultimap = multimapPredecessor;
215 }
216 }
217
218 private static final int DEFAULT_KEY_CAPACITY = 16;
219 private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
220 @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;
221
222 @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
223 private transient ValueEntry<K, V> multimapHeaderEntry;
224
225 private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
226 super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
227 checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
228
229 this.valueSetCapacity = valueSetCapacity;
230 this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
231 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
232 }
233
234
235
236
237
238
239
240
241
242
243 @Override
244 Set<V> createCollection() {
245 return new LinkedHashSet<V>(valueSetCapacity);
246 }
247
248
249
250
251
252
253
254
255
256
257 @Override
258 Collection<V> createCollection(K key) {
259 return new ValueSet(key, valueSetCapacity);
260 }
261
262
263
264
265
266
267
268
269
270 @Override
271 public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
272 return super.replaceValues(key, values);
273 }
274
275
276
277
278
279
280
281
282
283
284
285
286
287 @Override public Set<Map.Entry<K, V>> entries() {
288 return super.entries();
289 }
290
291
292
293
294
295
296
297
298 @Override public Collection<V> values() {
299 return super.values();
300 }
301
302 @VisibleForTesting
303 final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
304
305
306
307
308
309 private final K key;
310 @VisibleForTesting ValueEntry<K, V>[] hashTable;
311 private int size = 0;
312 private int modCount = 0;
313
314
315
316 private ValueSetLink<K, V> firstEntry;
317 private ValueSetLink<K, V> lastEntry;
318
319 ValueSet(K key, int expectedValues) {
320 this.key = key;
321 this.firstEntry = this;
322 this.lastEntry = this;
323
324 int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
325
326 @SuppressWarnings("unchecked")
327 ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
328 this.hashTable = hashTable;
329 }
330
331 private int mask() {
332 return hashTable.length - 1;
333 }
334
335 @Override
336 public ValueSetLink<K, V> getPredecessorInValueSet() {
337 return lastEntry;
338 }
339
340 @Override
341 public ValueSetLink<K, V> getSuccessorInValueSet() {
342 return firstEntry;
343 }
344
345 @Override
346 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
347 lastEntry = entry;
348 }
349
350 @Override
351 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
352 firstEntry = entry;
353 }
354
355 @Override
356 public Iterator<V> iterator() {
357 return new Iterator<V>() {
358 ValueSetLink<K, V> nextEntry = firstEntry;
359 ValueEntry<K, V> toRemove;
360 int expectedModCount = modCount;
361
362 private void checkForComodification() {
363 if (modCount != expectedModCount) {
364 throw new ConcurrentModificationException();
365 }
366 }
367
368 @Override
369 public boolean hasNext() {
370 checkForComodification();
371 return nextEntry != ValueSet.this;
372 }
373
374 @Override
375 public V next() {
376 if (!hasNext()) {
377 throw new NoSuchElementException();
378 }
379 ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
380 V result = entry.getValue();
381 toRemove = entry;
382 nextEntry = entry.getSuccessorInValueSet();
383 return result;
384 }
385
386 @Override
387 public void remove() {
388 checkForComodification();
389 checkRemove(toRemove != null);
390 ValueSet.this.remove(toRemove.getValue());
391 expectedModCount = modCount;
392 toRemove = null;
393 }
394 };
395 }
396
397 @Override
398 public int size() {
399 return size;
400 }
401
402 @Override
403 public boolean contains(@Nullable Object o) {
404 int smearedHash = Hashing.smearedHash(o);
405 for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()]; entry != null;
406 entry = entry.nextInValueBucket) {
407 if (entry.matchesValue(o, smearedHash)) {
408 return true;
409 }
410 }
411 return false;
412 }
413
414 @Override
415 public boolean add(@Nullable V value) {
416 int smearedHash = Hashing.smearedHash(value);
417 int bucket = smearedHash & mask();
418 ValueEntry<K, V> rowHead = hashTable[bucket];
419 for (ValueEntry<K, V> entry = rowHead; entry != null;
420 entry = entry.nextInValueBucket) {
421 if (entry.matchesValue(value, smearedHash)) {
422 return false;
423 }
424 }
425
426 ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead);
427 succeedsInValueSet(lastEntry, newEntry);
428 succeedsInValueSet(newEntry, this);
429 succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
430 succeedsInMultimap(newEntry, multimapHeaderEntry);
431 hashTable[bucket] = newEntry;
432 size++;
433 modCount++;
434 rehashIfNecessary();
435 return true;
436 }
437
438 private void rehashIfNecessary() {
439 if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
440 @SuppressWarnings("unchecked")
441 ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
442 this.hashTable = hashTable;
443 int mask = hashTable.length - 1;
444 for (ValueSetLink<K, V> entry = firstEntry;
445 entry != this; entry = entry.getSuccessorInValueSet()) {
446 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
447 int bucket = valueEntry.smearedValueHash & mask;
448 valueEntry.nextInValueBucket = hashTable[bucket];
449 hashTable[bucket] = valueEntry;
450 }
451 }
452 }
453
454 @Override
455 public boolean remove(@Nullable Object o) {
456 int smearedHash = Hashing.smearedHash(o);
457 int bucket = smearedHash & mask();
458 ValueEntry<K, V> prev = null;
459 for (ValueEntry<K, V> entry = hashTable[bucket]; entry != null;
460 prev = entry, entry = entry.nextInValueBucket) {
461 if (entry.matchesValue(o, smearedHash)) {
462 if (prev == null) {
463
464 hashTable[bucket] = entry.nextInValueBucket;
465 } else {
466 prev.nextInValueBucket = entry.nextInValueBucket;
467 }
468 deleteFromValueSet(entry);
469 deleteFromMultimap(entry);
470 size--;
471 modCount++;
472 return true;
473 }
474 }
475 return false;
476 }
477
478 @Override
479 public void clear() {
480 Arrays.fill(hashTable, null);
481 size = 0;
482 for (ValueSetLink<K, V> entry = firstEntry;
483 entry != this; entry = entry.getSuccessorInValueSet()) {
484 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
485 deleteFromMultimap(valueEntry);
486 }
487 succeedsInValueSet(this, this);
488 modCount++;
489 }
490 }
491
492 @Override
493 Iterator<Map.Entry<K, V>> entryIterator() {
494 return new Iterator<Map.Entry<K, V>>() {
495 ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
496 ValueEntry<K, V> toRemove;
497
498 @Override
499 public boolean hasNext() {
500 return nextEntry != multimapHeaderEntry;
501 }
502
503 @Override
504 public Map.Entry<K, V> next() {
505 if (!hasNext()) {
506 throw new NoSuchElementException();
507 }
508 ValueEntry<K, V> result = nextEntry;
509 toRemove = result;
510 nextEntry = nextEntry.successorInMultimap;
511 return result;
512 }
513
514 @Override
515 public void remove() {
516 checkRemove(toRemove != null);
517 LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
518 toRemove = null;
519 }
520 };
521 }
522
523 @Override
524 Iterator<V> valueIterator() {
525 return Maps.valueIterator(entryIterator());
526 }
527
528 @Override
529 public void clear() {
530 super.clear();
531 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
532 }
533
534
535
536
537
538 @GwtIncompatible("java.io.ObjectOutputStream")
539 private void writeObject(ObjectOutputStream stream) throws IOException {
540 stream.defaultWriteObject();
541 stream.writeInt(valueSetCapacity);
542 stream.writeInt(keySet().size());
543 for (K key : keySet()) {
544 stream.writeObject(key);
545 }
546 stream.writeInt(size());
547 for (Map.Entry<K, V> entry : entries()) {
548 stream.writeObject(entry.getKey());
549 stream.writeObject(entry.getValue());
550 }
551 }
552
553 @GwtIncompatible("java.io.ObjectInputStream")
554 private void readObject(ObjectInputStream stream)
555 throws IOException, ClassNotFoundException {
556 stream.defaultReadObject();
557 multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
558 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
559 valueSetCapacity = stream.readInt();
560 int distinctKeys = stream.readInt();
561 Map<K, Collection<V>> map =
562 new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys));
563 for (int i = 0; i < distinctKeys; i++) {
564 @SuppressWarnings("unchecked")
565 K key = (K) stream.readObject();
566 map.put(key, createCollection(key));
567 }
568 int entries = stream.readInt();
569 for (int i = 0; i < entries; i++) {
570 @SuppressWarnings("unchecked")
571 K key = (K) stream.readObject();
572 @SuppressWarnings("unchecked")
573 V value = (V) stream.readObject();
574 map.get(key).add(value);
575 }
576 setMap(map);
577 }
578
579 @GwtIncompatible("java serialization not supported")
580 private static final long serialVersionUID = 1;
581 }