001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.collect.CollectPreconditions.checkNonnegative; 021import static com.google.common.collect.CollectPreconditions.checkRemove; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.GwtIncompatible; 025import com.google.common.annotations.VisibleForTesting; 026import com.google.common.base.Objects; 027import com.google.errorprone.annotations.CanIgnoreReturnValue; 028import com.google.j2objc.annotations.WeakOuter; 029import java.io.IOException; 030import java.io.ObjectInputStream; 031import java.io.ObjectOutputStream; 032import java.util.Arrays; 033import java.util.Collection; 034import java.util.ConcurrentModificationException; 035import java.util.Iterator; 036import java.util.Map; 037import java.util.Map.Entry; 038import java.util.NoSuchElementException; 039import java.util.Set; 040import java.util.Spliterator; 041import java.util.Spliterators; 042import java.util.function.Consumer; 043import org.checkerframework.checker.nullness.qual.Nullable; 044 045/** 046 * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that 047 * returns collections whose iterators follow the ordering in which the data was added to the 048 * multimap. 049 * 050 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through 051 * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code 052 * removeAll}, and {@code replaceValues} return collections that iterate through the values in the 053 * order they were added. The collections generated by {@code entries} and {@code values} iterate 054 * across the key-value mappings in the order they were added to the multimap. 055 * 056 * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and 057 * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or 058 * removing mappings does not affect the key iteration order. However, if you remove all values 059 * associated with a key and then add the key back to the multimap, that key will come last in the 060 * key iteration order. 061 * 062 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an 063 * existing key-value pair has no effect. 064 * 065 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned 066 * views are modifiable. 067 * 068 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent 069 * read operations will work correctly. To allow concurrent update operations, wrap your multimap 070 * with a call to {@link Multimaps#synchronizedSetMultimap}. 071 * 072 * <p>See the Guava User Guide article on <a href= 073 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> {@code 074 * Multimap}</a>. 075 * 076 * @author Jared Levy 077 * @author Louis Wasserman 078 * @since 2.0 079 */ 080@GwtCompatible(serializable = true, emulated = true) 081public final class LinkedHashMultimap<K, V> 082 extends LinkedHashMultimapGwtSerializationDependencies<K, V> { 083 084 /** Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities. */ 085 public static <K, V> LinkedHashMultimap<K, V> create() { 086 return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY); 087 } 088 089 /** 090 * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified 091 * numbers of keys and values without rehashing. 092 * 093 * @param expectedKeys the expected number of distinct keys 094 * @param expectedValuesPerKey the expected average number of values per key 095 * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is 096 * negative 097 */ 098 public static <K, V> LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) { 099 return new LinkedHashMultimap<>( 100 Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey)); 101 } 102 103 /** 104 * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a 105 * key-value mapping appears multiple times in the input multimap, it only appears once in the 106 * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order 107 * as the input multimap, except for excluding duplicate mappings. 108 * 109 * @param multimap the multimap whose contents are copied to this multimap 110 */ 111 public static <K, V> LinkedHashMultimap<K, V> create( 112 Multimap<? extends K, ? extends V> multimap) { 113 LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY); 114 result.putAll(multimap); 115 return result; 116 } 117 118 private interface ValueSetLink<K, V> { 119 ValueSetLink<K, V> getPredecessorInValueSet(); 120 121 ValueSetLink<K, V> getSuccessorInValueSet(); 122 123 void setPredecessorInValueSet(ValueSetLink<K, V> entry); 124 125 void setSuccessorInValueSet(ValueSetLink<K, V> entry); 126 } 127 128 private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) { 129 pred.setSuccessorInValueSet(succ); 130 succ.setPredecessorInValueSet(pred); 131 } 132 133 private static <K, V> void succeedsInMultimap(ValueEntry<K, V> pred, ValueEntry<K, V> succ) { 134 pred.setSuccessorInMultimap(succ); 135 succ.setPredecessorInMultimap(pred); 136 } 137 138 private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) { 139 succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet()); 140 } 141 142 private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) { 143 succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap()); 144 } 145 146 /** 147 * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the 148 * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered 149 * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a 150 * whole. 151 */ 152 @VisibleForTesting 153 static final class ValueEntry<K, V> extends ImmutableEntry<K, V> implements ValueSetLink<K, V> { 154 final int smearedValueHash; 155 156 @Nullable ValueEntry<K, V> nextInValueBucket; 157 158 @Nullable ValueSetLink<K, V> predecessorInValueSet; 159 @Nullable ValueSetLink<K, V> successorInValueSet; 160 161 @Nullable ValueEntry<K, V> predecessorInMultimap; 162 @Nullable ValueEntry<K, V> successorInMultimap; 163 164 ValueEntry( 165 @Nullable K key, 166 @Nullable V value, 167 int smearedValueHash, 168 @Nullable ValueEntry<K, V> nextInValueBucket) { 169 super(key, value); 170 this.smearedValueHash = smearedValueHash; 171 this.nextInValueBucket = nextInValueBucket; 172 } 173 174 boolean matchesValue(@Nullable Object v, int smearedVHash) { 175 return smearedValueHash == smearedVHash && Objects.equal(getValue(), v); 176 } 177 178 @Override 179 public ValueSetLink<K, V> getPredecessorInValueSet() { 180 return predecessorInValueSet; 181 } 182 183 @Override 184 public ValueSetLink<K, V> getSuccessorInValueSet() { 185 return successorInValueSet; 186 } 187 188 @Override 189 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) { 190 predecessorInValueSet = entry; 191 } 192 193 @Override 194 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) { 195 successorInValueSet = entry; 196 } 197 198 public ValueEntry<K, V> getPredecessorInMultimap() { 199 return predecessorInMultimap; 200 } 201 202 public ValueEntry<K, V> getSuccessorInMultimap() { 203 return successorInMultimap; 204 } 205 206 public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) { 207 this.successorInMultimap = multimapSuccessor; 208 } 209 210 public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) { 211 this.predecessorInMultimap = multimapPredecessor; 212 } 213 } 214 215 private static final int DEFAULT_KEY_CAPACITY = 16; 216 private static final int DEFAULT_VALUE_SET_CAPACITY = 2; 217 @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0; 218 219 @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY; 220 private transient ValueEntry<K, V> multimapHeaderEntry; 221 222 private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) { 223 super(Platform.<K, Collection<V>>newLinkedHashMapWithExpectedSize(keyCapacity)); 224 checkNonnegative(valueSetCapacity, "expectedValuesPerKey"); 225 226 this.valueSetCapacity = valueSetCapacity; 227 this.multimapHeaderEntry = new ValueEntry<>(null, null, 0, null); 228 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 229 } 230 231 /** 232 * {@inheritDoc} 233 * 234 * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key. 235 * 236 * @return a new {@code LinkedHashSet} containing a collection of values for one key 237 */ 238 @Override 239 Set<V> createCollection() { 240 return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity); 241 } 242 243 /** 244 * {@inheritDoc} 245 * 246 * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which 247 * key-value pairs are added to the multimap. 248 * 249 * @param key key to associate with values in the collection 250 * @return a new decorated set containing a collection of values for one key 251 */ 252 @Override 253 Collection<V> createCollection(K key) { 254 return new ValueSet(key, valueSetCapacity); 255 } 256 257 /** 258 * {@inheritDoc} 259 * 260 * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key}, 261 * the {@code keySet()} ordering is unchanged. However, the provided values always come last in 262 * the {@link #entries()} and {@link #values()} iteration orderings. 263 */ 264 @CanIgnoreReturnValue 265 @Override 266 public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 267 return super.replaceValues(key, values); 268 } 269 270 /** 271 * Returns a set of all key-value pairs. Changes to the returned set will update the underlying 272 * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll} 273 * operations. 274 * 275 * <p>The iterator generated by the returned set traverses the entries in the order they were 276 * added to the multimap. 277 * 278 * <p>Each entry is an immutable snapshot of a key-value mapping in the multimap, taken at the 279 * time the entry is returned by a method call to the collection or its iterator. 280 */ 281 @Override 282 public Set<Entry<K, V>> entries() { 283 return super.entries(); 284 } 285 286 /** 287 * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the 288 * key set contains a key if and only if this multimap maps that key to at least one value. 289 * 290 * <p>The iterator generated by the returned set traverses the keys in the order they were first 291 * added to the multimap. 292 * 293 * <p>Changes to the returned set will update the underlying multimap, and vice versa. However, 294 * <i>adding</i> to the returned set is not possible. 295 */ 296 @Override 297 public Set<K> keySet() { 298 return super.keySet(); 299 } 300 301 /** 302 * Returns a collection of all values in the multimap. Changes to the returned collection will 303 * update the underlying multimap, and vice versa. 304 * 305 * <p>The iterator generated by the returned collection traverses the values in the order they 306 * were added to the multimap. 307 */ 308 @Override 309 public Collection<V> values() { 310 return super.values(); 311 } 312 313 @VisibleForTesting 314 @WeakOuter 315 final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> { 316 /* 317 * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory 318 * consumption. 319 */ 320 321 private final K key; 322 @VisibleForTesting ValueEntry<K, V>[] hashTable; 323 private int size = 0; 324 private int modCount = 0; 325 326 // We use the set object itself as the end of the linked list, avoiding an unnecessary 327 // entry object per key. 328 private ValueSetLink<K, V> firstEntry; 329 private ValueSetLink<K, V> lastEntry; 330 331 ValueSet(K key, int expectedValues) { 332 this.key = key; 333 this.firstEntry = this; 334 this.lastEntry = this; 335 // Round expected values up to a power of 2 to get the table size. 336 int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR); 337 338 @SuppressWarnings("unchecked") 339 ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize]; 340 this.hashTable = hashTable; 341 } 342 343 private int mask() { 344 return hashTable.length - 1; 345 } 346 347 @Override 348 public ValueSetLink<K, V> getPredecessorInValueSet() { 349 return lastEntry; 350 } 351 352 @Override 353 public ValueSetLink<K, V> getSuccessorInValueSet() { 354 return firstEntry; 355 } 356 357 @Override 358 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) { 359 lastEntry = entry; 360 } 361 362 @Override 363 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) { 364 firstEntry = entry; 365 } 366 367 @Override 368 public Iterator<V> iterator() { 369 return new Iterator<V>() { 370 ValueSetLink<K, V> nextEntry = firstEntry; 371 @Nullable ValueEntry<K, V> toRemove; 372 int expectedModCount = modCount; 373 374 private void checkForComodification() { 375 if (modCount != expectedModCount) { 376 throw new ConcurrentModificationException(); 377 } 378 } 379 380 @Override 381 public boolean hasNext() { 382 checkForComodification(); 383 return nextEntry != ValueSet.this; 384 } 385 386 @Override 387 public V next() { 388 if (!hasNext()) { 389 throw new NoSuchElementException(); 390 } 391 ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry; 392 V result = entry.getValue(); 393 toRemove = entry; 394 nextEntry = entry.getSuccessorInValueSet(); 395 return result; 396 } 397 398 @Override 399 public void remove() { 400 checkForComodification(); 401 checkRemove(toRemove != null); 402 ValueSet.this.remove(toRemove.getValue()); 403 expectedModCount = modCount; 404 toRemove = null; 405 } 406 }; 407 } 408 409 @Override 410 public void forEach(Consumer<? super V> action) { 411 checkNotNull(action); 412 for (ValueSetLink<K, V> entry = firstEntry; 413 entry != ValueSet.this; 414 entry = entry.getSuccessorInValueSet()) { 415 action.accept(((ValueEntry<K, V>) entry).getValue()); 416 } 417 } 418 419 @Override 420 public int size() { 421 return size; 422 } 423 424 @Override 425 public boolean contains(@Nullable Object o) { 426 int smearedHash = Hashing.smearedHash(o); 427 for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()]; 428 entry != null; 429 entry = entry.nextInValueBucket) { 430 if (entry.matchesValue(o, smearedHash)) { 431 return true; 432 } 433 } 434 return false; 435 } 436 437 @Override 438 public boolean add(@Nullable V value) { 439 int smearedHash = Hashing.smearedHash(value); 440 int bucket = smearedHash & mask(); 441 ValueEntry<K, V> rowHead = hashTable[bucket]; 442 for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) { 443 if (entry.matchesValue(value, smearedHash)) { 444 return false; 445 } 446 } 447 448 ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, rowHead); 449 succeedsInValueSet(lastEntry, newEntry); 450 succeedsInValueSet(newEntry, this); 451 succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry); 452 succeedsInMultimap(newEntry, multimapHeaderEntry); 453 hashTable[bucket] = newEntry; 454 size++; 455 modCount++; 456 rehashIfNecessary(); 457 return true; 458 } 459 460 private void rehashIfNecessary() { 461 if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) { 462 @SuppressWarnings("unchecked") 463 ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2]; 464 this.hashTable = hashTable; 465 int mask = hashTable.length - 1; 466 for (ValueSetLink<K, V> entry = firstEntry; 467 entry != this; 468 entry = entry.getSuccessorInValueSet()) { 469 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry; 470 int bucket = valueEntry.smearedValueHash & mask; 471 valueEntry.nextInValueBucket = hashTable[bucket]; 472 hashTable[bucket] = valueEntry; 473 } 474 } 475 } 476 477 @CanIgnoreReturnValue 478 @Override 479 public boolean remove(@Nullable Object o) { 480 int smearedHash = Hashing.smearedHash(o); 481 int bucket = smearedHash & mask(); 482 ValueEntry<K, V> prev = null; 483 for (ValueEntry<K, V> entry = hashTable[bucket]; 484 entry != null; 485 prev = entry, entry = entry.nextInValueBucket) { 486 if (entry.matchesValue(o, smearedHash)) { 487 if (prev == null) { 488 // first entry in the bucket 489 hashTable[bucket] = entry.nextInValueBucket; 490 } else { 491 prev.nextInValueBucket = entry.nextInValueBucket; 492 } 493 deleteFromValueSet(entry); 494 deleteFromMultimap(entry); 495 size--; 496 modCount++; 497 return true; 498 } 499 } 500 return false; 501 } 502 503 @Override 504 public void clear() { 505 Arrays.fill(hashTable, null); 506 size = 0; 507 for (ValueSetLink<K, V> entry = firstEntry; 508 entry != this; 509 entry = entry.getSuccessorInValueSet()) { 510 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry; 511 deleteFromMultimap(valueEntry); 512 } 513 succeedsInValueSet(this, this); 514 modCount++; 515 } 516 } 517 518 @Override 519 Iterator<Entry<K, V>> entryIterator() { 520 return new Iterator<Entry<K, V>>() { 521 ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap; 522 @Nullable ValueEntry<K, V> toRemove; 523 524 @Override 525 public boolean hasNext() { 526 return nextEntry != multimapHeaderEntry; 527 } 528 529 @Override 530 public Entry<K, V> next() { 531 if (!hasNext()) { 532 throw new NoSuchElementException(); 533 } 534 ValueEntry<K, V> result = nextEntry; 535 toRemove = result; 536 nextEntry = nextEntry.successorInMultimap; 537 return result; 538 } 539 540 @Override 541 public void remove() { 542 checkRemove(toRemove != null); 543 LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue()); 544 toRemove = null; 545 } 546 }; 547 } 548 549 @Override 550 Spliterator<Entry<K, V>> entrySpliterator() { 551 return Spliterators.spliterator(entries(), Spliterator.DISTINCT | Spliterator.ORDERED); 552 } 553 554 @Override 555 Iterator<V> valueIterator() { 556 return Maps.valueIterator(entryIterator()); 557 } 558 559 @Override 560 Spliterator<V> valueSpliterator() { 561 return CollectSpliterators.map(entrySpliterator(), Entry::getValue); 562 } 563 564 @Override 565 public void clear() { 566 super.clear(); 567 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 568 } 569 570 /** 571 * @serialData the expected values per key, the number of distinct keys, the number of entries, 572 * and the entries in order 573 */ 574 @GwtIncompatible // java.io.ObjectOutputStream 575 private void writeObject(ObjectOutputStream stream) throws IOException { 576 stream.defaultWriteObject(); 577 stream.writeInt(keySet().size()); 578 for (K key : keySet()) { 579 stream.writeObject(key); 580 } 581 stream.writeInt(size()); 582 for (Entry<K, V> entry : entries()) { 583 stream.writeObject(entry.getKey()); 584 stream.writeObject(entry.getValue()); 585 } 586 } 587 588 @GwtIncompatible // java.io.ObjectInputStream 589 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 590 stream.defaultReadObject(); 591 multimapHeaderEntry = new ValueEntry<>(null, null, 0, null); 592 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 593 valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY; 594 int distinctKeys = stream.readInt(); 595 Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12); 596 for (int i = 0; i < distinctKeys; i++) { 597 @SuppressWarnings("unchecked") 598 K key = (K) stream.readObject(); 599 map.put(key, createCollection(key)); 600 } 601 int entries = stream.readInt(); 602 for (int i = 0; i < entries; i++) { 603 @SuppressWarnings("unchecked") 604 K key = (K) stream.readObject(); 605 @SuppressWarnings("unchecked") 606 V value = (V) stream.readObject(); 607 map.get(key).add(value); 608 } 609 setMap(map); 610 } 611 612 @GwtIncompatible // java serialization not supported 613 private static final long serialVersionUID = 1; 614}