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