1 /*
2 * Copyright (C) 2007 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.collect.CollectPreconditions.checkNonnegative;
21 import static com.google.common.collect.CollectPreconditions.checkRemove;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.common.annotations.VisibleForTesting;
26 import com.google.common.base.Objects;
27 import com.google.errorprone.annotations.CanIgnoreReturnValue;
28 import com.google.j2objc.annotations.WeakOuter;
29 import java.io.IOException;
30 import java.io.ObjectInputStream;
31 import java.io.ObjectOutputStream;
32 import java.util.Arrays;
33 import java.util.Collection;
34 import java.util.ConcurrentModificationException;
35 import java.util.Iterator;
36 import java.util.Map;
37 import java.util.Map.Entry;
38 import java.util.NoSuchElementException;
39 import java.util.Set;
40 import java.util.Spliterator;
41 import java.util.Spliterators;
42 import java.util.function.Consumer;
43 import org.checkerframework.checker.nullness.qual.Nullable;
44
45 /**
46 * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that
47 * returns collections whose iterators follow the ordering in which the data was added to the
48 * multimap.
49 *
50 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through
51 * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code
52 * removeAll}, and {@code replaceValues} return collections that iterate through the values in the
53 * order they were added. The collections generated by {@code entries} and {@code values} iterate
54 * across the key-value mappings in the order they were added to the multimap.
55 *
56 * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and
57 * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or
58 * removing mappings does not affect the key iteration order. However, if you remove all values
59 * associated with a key and then add the key back to the multimap, that key will come last in the
60 * key iteration order.
61 *
62 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an
63 * existing key-value pair has no effect.
64 *
65 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
66 * views are modifiable.
67 *
68 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
69 * read operations will work correctly. To allow concurrent update operations, wrap your multimap
70 * with a call to {@link Multimaps#synchronizedSetMultimap}.
71 *
72 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code LinkedHashMultimap}
73 * in a way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will
74 * result.
75 *
76 * <p>See the Guava User Guide article on <a href=
77 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> {@code
78 * Multimap}</a>.
79 *
80 * @author Jared Levy
81 * @author Louis Wasserman
82 * @since 2.0
83 */
84 @GwtCompatible(serializable = true, emulated = true)
85 public final class LinkedHashMultimap<K, V>
86 extends LinkedHashMultimapGwtSerializationDependencies<K, V> {
87
88 /** Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities. */
89 public static <K, V> LinkedHashMultimap<K, V> create() {
90 return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
91 }
92
93 /**
94 * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified
95 * numbers of keys and values without rehashing.
96 *
97 * @param expectedKeys the expected number of distinct keys
98 * @param expectedValuesPerKey the expected average number of values per key
99 * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
100 * negative
101 */
102 public static <K, V> LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
103 return new LinkedHashMultimap<>(
104 Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey));
105 }
106
107 /**
108 * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a
109 * key-value mapping appears multiple times in the input multimap, it only appears once in the
110 * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order
111 * as the input multimap, except for excluding duplicate mappings.
112 *
113 * @param multimap the multimap whose contents are copied to this multimap
114 */
115 public static <K, V> LinkedHashMultimap<K, V> create(
116 Multimap<? extends K, ? extends V> multimap) {
117 LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
118 result.putAll(multimap);
119 return result;
120 }
121
122 private interface ValueSetLink<K, V> {
123 ValueSetLink<K, V> getPredecessorInValueSet();
124
125 ValueSetLink<K, V> getSuccessorInValueSet();
126
127 void setPredecessorInValueSet(ValueSetLink<K, V> entry);
128
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(ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
138 pred.setSuccessorInMultimap(succ);
139 succ.setPredecessorInMultimap(pred);
140 }
141
142 private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) {
143 succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
144 }
145
146 private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) {
147 succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
148 }
149
150 /**
151 * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the
152 * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered
153 * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a
154 * whole.
155 */
156 @VisibleForTesting
157 static final class ValueEntry<K, V> extends ImmutableEntry<K, V> implements ValueSetLink<K, V> {
158 final int smearedValueHash;
159
160 @Nullable ValueEntry<K, V> nextInValueBucket;
161
162 @Nullable ValueSetLink<K, V> predecessorInValueSet;
163 @Nullable ValueSetLink<K, V> successorInValueSet;
164
165 @Nullable ValueEntry<K, V> predecessorInMultimap;
166 @Nullable ValueEntry<K, V> successorInMultimap;
167
168 ValueEntry(
169 @Nullable K key,
170 @Nullable V value,
171 int smearedValueHash,
172 @Nullable ValueEntry<K, V> nextInValueBucket) {
173 super(key, value);
174 this.smearedValueHash = smearedValueHash;
175 this.nextInValueBucket = nextInValueBucket;
176 }
177
178 boolean matchesValue(@Nullable Object v, int smearedVHash) {
179 return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
180 }
181
182 @Override
183 public ValueSetLink<K, V> getPredecessorInValueSet() {
184 return predecessorInValueSet;
185 }
186
187 @Override
188 public ValueSetLink<K, V> getSuccessorInValueSet() {
189 return successorInValueSet;
190 }
191
192 @Override
193 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
194 predecessorInValueSet = entry;
195 }
196
197 @Override
198 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
199 successorInValueSet = entry;
200 }
201
202 public ValueEntry<K, V> getPredecessorInMultimap() {
203 return predecessorInMultimap;
204 }
205
206 public ValueEntry<K, V> getSuccessorInMultimap() {
207 return successorInMultimap;
208 }
209
210 public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
211 this.successorInMultimap = multimapSuccessor;
212 }
213
214 public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
215 this.predecessorInMultimap = multimapPredecessor;
216 }
217 }
218
219 private static final int DEFAULT_KEY_CAPACITY = 16;
220 private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
221 @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;
222
223 @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
224 private transient ValueEntry<K, V> multimapHeaderEntry;
225
226 private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
227 super(Platform.<K, Collection<V>>newLinkedHashMapWithExpectedSize(keyCapacity));
228 checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
229
230 this.valueSetCapacity = valueSetCapacity;
231 this.multimapHeaderEntry = new ValueEntry<>(null, null, 0, null);
232 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
233 }
234
235 /**
236 * {@inheritDoc}
237 *
238 * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key.
239 *
240 * @return a new {@code LinkedHashSet} containing a collection of values for one key
241 */
242 @Override
243 Set<V> createCollection() {
244 return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity);
245 }
246
247 /**
248 * {@inheritDoc}
249 *
250 * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which
251 * key-value pairs are added to the multimap.
252 *
253 * @param key key to associate with values in the collection
254 * @return a new decorated set containing a collection of values for one key
255 */
256 @Override
257 Collection<V> createCollection(K key) {
258 return new ValueSet(key, valueSetCapacity);
259 }
260
261 /**
262 * {@inheritDoc}
263 *
264 * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key},
265 * the {@code keySet()} ordering is unchanged. However, the provided values always come last in
266 * the {@link #entries()} and {@link #values()} iteration orderings.
267 */
268 @CanIgnoreReturnValue
269 @Override
270 public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
271 return super.replaceValues(key, values);
272 }
273
274 /**
275 * Returns a set of all key-value pairs. Changes to the returned set will update the underlying
276 * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll}
277 * operations.
278 *
279 * <p>The iterator generated by the returned set traverses the entries in the order they were
280 * added to the multimap.
281 *
282 * <p>Each entry is an immutable snapshot of a key-value mapping in the multimap, taken at the
283 * time the entry is returned by a method call to the collection or its iterator.
284 */
285 @Override
286 public Set<Entry<K, V>> entries() {
287 return super.entries();
288 }
289
290 /**
291 * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
292 * key set contains a key if and only if this multimap maps that key to at least one value.
293 *
294 * <p>The iterator generated by the returned set traverses the keys in the order they were first
295 * added to the multimap.
296 *
297 * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
298 * <i>adding</i> to the returned set is not possible.
299 */
300 @Override
301 public Set<K> keySet() {
302 return super.keySet();
303 }
304
305 /**
306 * Returns a collection of all values in the multimap. Changes to the returned collection will
307 * update the underlying multimap, and vice versa.
308 *
309 * <p>The iterator generated by the returned collection traverses the values in the order they
310 * were added to the multimap.
311 */
312 @Override
313 public Collection<V> values() {
314 return super.values();
315 }
316
317 @VisibleForTesting
318 @WeakOuter
319 final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
320 /*
321 * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
322 * consumption.
323 */
324
325 private final K key;
326 @VisibleForTesting ValueEntry<K, V>[] hashTable;
327 private int size = 0;
328 private int modCount = 0;
329
330 // We use the set object itself as the end of the linked list, avoiding an unnecessary
331 // entry object per key.
332 private ValueSetLink<K, V> firstEntry;
333 private ValueSetLink<K, V> lastEntry;
334
335 ValueSet(K key, int expectedValues) {
336 this.key = key;
337 this.firstEntry = this;
338 this.lastEntry = this;
339 // Round expected values up to a power of 2 to get the table size.
340 int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
341
342 @SuppressWarnings("unchecked")
343 ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
344 this.hashTable = hashTable;
345 }
346
347 private int mask() {
348 return hashTable.length - 1;
349 }
350
351 @Override
352 public ValueSetLink<K, V> getPredecessorInValueSet() {
353 return lastEntry;
354 }
355
356 @Override
357 public ValueSetLink<K, V> getSuccessorInValueSet() {
358 return firstEntry;
359 }
360
361 @Override
362 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
363 lastEntry = entry;
364 }
365
366 @Override
367 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
368 firstEntry = entry;
369 }
370
371 @Override
372 public Iterator<V> iterator() {
373 return new Iterator<V>() {
374 ValueSetLink<K, V> nextEntry = firstEntry;
375 @Nullable ValueEntry<K, V> toRemove;
376 int expectedModCount = modCount;
377
378 private void checkForComodification() {
379 if (modCount != expectedModCount) {
380 throw new ConcurrentModificationException();
381 }
382 }
383
384 @Override
385 public boolean hasNext() {
386 checkForComodification();
387 return nextEntry != ValueSet.this;
388 }
389
390 @Override
391 public V next() {
392 if (!hasNext()) {
393 throw new NoSuchElementException();
394 }
395 ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
396 V result = entry.getValue();
397 toRemove = entry;
398 nextEntry = entry.getSuccessorInValueSet();
399 return result;
400 }
401
402 @Override
403 public void remove() {
404 checkForComodification();
405 checkRemove(toRemove != null);
406 ValueSet.this.remove(toRemove.getValue());
407 expectedModCount = modCount;
408 toRemove = null;
409 }
410 };
411 }
412
413 @Override
414 public void forEach(Consumer<? super V> action) {
415 checkNotNull(action);
416 for (ValueSetLink<K, V> entry = firstEntry;
417 entry != ValueSet.this;
418 entry = entry.getSuccessorInValueSet()) {
419 action.accept(((ValueEntry<K, V>) entry).getValue());
420 }
421 }
422
423 @Override
424 public int size() {
425 return size;
426 }
427
428 @Override
429 public boolean contains(@Nullable Object o) {
430 int smearedHash = Hashing.smearedHash(o);
431 for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
432 entry != null;
433 entry = entry.nextInValueBucket) {
434 if (entry.matchesValue(o, smearedHash)) {
435 return true;
436 }
437 }
438 return false;
439 }
440
441 @Override
442 public boolean add(@Nullable V value) {
443 int smearedHash = Hashing.smearedHash(value);
444 int bucket = smearedHash & mask();
445 ValueEntry<K, V> rowHead = hashTable[bucket];
446 for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
447 if (entry.matchesValue(value, smearedHash)) {
448 return false;
449 }
450 }
451
452 ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, rowHead);
453 succeedsInValueSet(lastEntry, newEntry);
454 succeedsInValueSet(newEntry, this);
455 succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
456 succeedsInMultimap(newEntry, multimapHeaderEntry);
457 hashTable[bucket] = newEntry;
458 size++;
459 modCount++;
460 rehashIfNecessary();
461 return true;
462 }
463
464 private void rehashIfNecessary() {
465 if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
466 @SuppressWarnings("unchecked")
467 ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
468 this.hashTable = hashTable;
469 int mask = hashTable.length - 1;
470 for (ValueSetLink<K, V> entry = firstEntry;
471 entry != this;
472 entry = entry.getSuccessorInValueSet()) {
473 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
474 int bucket = valueEntry.smearedValueHash & mask;
475 valueEntry.nextInValueBucket = hashTable[bucket];
476 hashTable[bucket] = valueEntry;
477 }
478 }
479 }
480
481 @CanIgnoreReturnValue
482 @Override
483 public boolean remove(@Nullable Object o) {
484 int smearedHash = Hashing.smearedHash(o);
485 int bucket = smearedHash & mask();
486 ValueEntry<K, V> prev = null;
487 for (ValueEntry<K, V> entry = hashTable[bucket];
488 entry != null;
489 prev = entry, entry = entry.nextInValueBucket) {
490 if (entry.matchesValue(o, smearedHash)) {
491 if (prev == null) {
492 // first entry in the bucket
493 hashTable[bucket] = entry.nextInValueBucket;
494 } else {
495 prev.nextInValueBucket = entry.nextInValueBucket;
496 }
497 deleteFromValueSet(entry);
498 deleteFromMultimap(entry);
499 size--;
500 modCount++;
501 return true;
502 }
503 }
504 return false;
505 }
506
507 @Override
508 public void clear() {
509 Arrays.fill(hashTable, null);
510 size = 0;
511 for (ValueSetLink<K, V> entry = firstEntry;
512 entry != this;
513 entry = entry.getSuccessorInValueSet()) {
514 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
515 deleteFromMultimap(valueEntry);
516 }
517 succeedsInValueSet(this, this);
518 modCount++;
519 }
520 }
521
522 @Override
523 Iterator<Entry<K, V>> entryIterator() {
524 return new Iterator<Entry<K, V>>() {
525 ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
526 @Nullable ValueEntry<K, V> toRemove;
527
528 @Override
529 public boolean hasNext() {
530 return nextEntry != multimapHeaderEntry;
531 }
532
533 @Override
534 public Entry<K, V> next() {
535 if (!hasNext()) {
536 throw new NoSuchElementException();
537 }
538 ValueEntry<K, V> result = nextEntry;
539 toRemove = result;
540 nextEntry = nextEntry.successorInMultimap;
541 return result;
542 }
543
544 @Override
545 public void remove() {
546 checkRemove(toRemove != null);
547 LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
548 toRemove = null;
549 }
550 };
551 }
552
553 @Override
554 Spliterator<Entry<K, V>> entrySpliterator() {
555 return Spliterators.spliterator(entries(), Spliterator.DISTINCT | Spliterator.ORDERED);
556 }
557
558 @Override
559 Iterator<V> valueIterator() {
560 return Maps.valueIterator(entryIterator());
561 }
562
563 @Override
564 Spliterator<V> valueSpliterator() {
565 return CollectSpliterators.map(entrySpliterator(), Entry::getValue);
566 }
567
568 @Override
569 public void clear() {
570 super.clear();
571 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
572 }
573
574 /**
575 * @serialData the expected values per key, the number of distinct keys, the number of entries,
576 * and the entries in order
577 */
578 @GwtIncompatible // java.io.ObjectOutputStream
579 private void writeObject(ObjectOutputStream stream) throws IOException {
580 stream.defaultWriteObject();
581 stream.writeInt(keySet().size());
582 for (K key : keySet()) {
583 stream.writeObject(key);
584 }
585 stream.writeInt(size());
586 for (Entry<K, V> entry : entries()) {
587 stream.writeObject(entry.getKey());
588 stream.writeObject(entry.getValue());
589 }
590 }
591
592 @GwtIncompatible // java.io.ObjectInputStream
593 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
594 stream.defaultReadObject();
595 multimapHeaderEntry = new ValueEntry<>(null, null, 0, null);
596 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
597 valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
598 int distinctKeys = stream.readInt();
599 Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12);
600 for (int i = 0; i < distinctKeys; i++) {
601 @SuppressWarnings("unchecked")
602 K key = (K) stream.readObject();
603 map.put(key, createCollection(key));
604 }
605 int entries = stream.readInt();
606 for (int i = 0; i < entries; i++) {
607 @SuppressWarnings("unchecked")
608 K key = (K) stream.readObject();
609 @SuppressWarnings("unchecked")
610 V value = (V) stream.readObject();
611 map.get(key).add(value);
612 }
613 setMap(map);
614 }
615
616 @GwtIncompatible // java serialization not supported
617 private static final long serialVersionUID = 1;
618 }