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