001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.collect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT; 019import static com.google.common.collect.NullnessCasts.unsafeNull; 020 021import com.google.common.annotations.GwtCompatible; 022import com.google.common.annotations.GwtIncompatible; 023import com.google.common.base.Objects; 024import com.google.errorprone.annotations.CanIgnoreReturnValue; 025import com.google.errorprone.annotations.concurrent.LazyInit; 026import com.google.j2objc.annotations.RetainedWith; 027import java.io.IOException; 028import java.io.ObjectInputStream; 029import java.io.ObjectOutputStream; 030import java.io.Serializable; 031import java.util.AbstractMap; 032import java.util.AbstractSet; 033import java.util.Arrays; 034import java.util.ConcurrentModificationException; 035import java.util.Iterator; 036import java.util.Map; 037import java.util.NoSuchElementException; 038import java.util.Set; 039import javax.annotation.CheckForNull; 040import org.checkerframework.checker.nullness.qual.Nullable; 041 042/** 043 * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A 044 * {@code HashBiMap} and its inverse are both serializable. 045 * 046 * <p>This implementation guarantees insertion-based iteration order of its keys. 047 * 048 * <p>See the Guava User Guide article on <a href= 049 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap"> {@code BiMap} </a>. 050 * 051 * @author Louis Wasserman 052 * @author Mike Bostock 053 * @since 2.0 054 */ 055@GwtCompatible 056@ElementTypesAreNonnullByDefault 057public final class HashBiMap<K extends @Nullable Object, V extends @Nullable Object> 058 extends AbstractMap<K, V> implements BiMap<K, V>, Serializable { 059 060 /** Returns a new, empty {@code HashBiMap} with the default initial capacity (16). */ 061 public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create() { 062 return create(16); 063 } 064 065 /** 066 * Constructs a new, empty bimap with the specified expected size. 067 * 068 * @param expectedSize the expected number of entries 069 * @throws IllegalArgumentException if the specified expected size is negative 070 */ 071 public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create( 072 int expectedSize) { 073 return new HashBiMap<>(expectedSize); 074 } 075 076 /** 077 * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an 078 * initial capacity sufficient to hold the mappings in the specified map. 079 */ 080 public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create( 081 Map<? extends K, ? extends V> map) { 082 HashBiMap<K, V> bimap = create(map.size()); 083 bimap.putAll(map); 084 return bimap; 085 } 086 087 private static final int ABSENT = -1; 088 private static final int ENDPOINT = -2; 089 090 /** Maps an "entry" to the key of that entry. */ 091 transient @Nullable K[] keys; 092 /** Maps an "entry" to the value of that entry. */ 093 transient @Nullable V[] values; 094 095 transient int size; 096 transient int modCount; 097 /** Maps a bucket to the "entry" of its first element. */ 098 private transient int[] hashTableKToV; 099 /** Maps a bucket to the "entry" of its first element. */ 100 private transient int[] hashTableVToK; 101 /** Maps an "entry" to the "entry" that follows it in its bucket. */ 102 private transient int[] nextInBucketKToV; 103 /** Maps an "entry" to the "entry" that follows it in its bucket. */ 104 private transient int[] nextInBucketVToK; 105 /** The "entry" of the first element in insertion order. */ 106 private transient int firstInInsertionOrder; 107 /** The "entry" of the last element in insertion order. */ 108 private transient int lastInInsertionOrder; 109 /** Maps an "entry" to the "entry" that precedes it in insertion order. */ 110 private transient int[] prevInInsertionOrder; 111 /** Maps an "entry" to the "entry" that follows it in insertion order. */ 112 private transient int[] nextInInsertionOrder; 113 114 private HashBiMap(int expectedSize) { 115 init(expectedSize); 116 } 117 118 @SuppressWarnings("unchecked") 119 void init(int expectedSize) { 120 CollectPreconditions.checkNonnegative(expectedSize, "expectedSize"); 121 int tableSize = Hashing.closedTableSize(expectedSize, 1.0); 122 size = 0; 123 124 keys = (K[]) new Object[expectedSize]; 125 values = (V[]) new Object[expectedSize]; 126 127 hashTableKToV = createFilledWithAbsent(tableSize); 128 hashTableVToK = createFilledWithAbsent(tableSize); 129 nextInBucketKToV = createFilledWithAbsent(expectedSize); 130 nextInBucketVToK = createFilledWithAbsent(expectedSize); 131 132 firstInInsertionOrder = ENDPOINT; 133 lastInInsertionOrder = ENDPOINT; 134 135 prevInInsertionOrder = createFilledWithAbsent(expectedSize); 136 nextInInsertionOrder = createFilledWithAbsent(expectedSize); 137 } 138 139 /** Returns an int array of the specified size, filled with ABSENT. */ 140 private static int[] createFilledWithAbsent(int size) { 141 int[] array = new int[size]; 142 Arrays.fill(array, ABSENT); 143 return array; 144 } 145 146 /** Equivalent to {@code Arrays.copyOf(array, newSize)}, save that the new elements are ABSENT. */ 147 private static int[] expandAndFillWithAbsent(int[] array, int newSize) { 148 int oldSize = array.length; 149 int[] result = Arrays.copyOf(array, newSize); 150 Arrays.fill(result, oldSize, newSize, ABSENT); 151 return result; 152 } 153 154 @Override 155 public int size() { 156 return size; 157 } 158 159 /** 160 * Ensures that all of the internal structures in the HashBiMap are ready for this many elements. 161 */ 162 private void ensureCapacity(int minCapacity) { 163 if (nextInBucketKToV.length < minCapacity) { 164 int oldCapacity = nextInBucketKToV.length; 165 int newCapacity = ImmutableCollection.Builder.expandedCapacity(oldCapacity, minCapacity); 166 167 keys = Arrays.copyOf(keys, newCapacity); 168 values = Arrays.copyOf(values, newCapacity); 169 nextInBucketKToV = expandAndFillWithAbsent(nextInBucketKToV, newCapacity); 170 nextInBucketVToK = expandAndFillWithAbsent(nextInBucketVToK, newCapacity); 171 prevInInsertionOrder = expandAndFillWithAbsent(prevInInsertionOrder, newCapacity); 172 nextInInsertionOrder = expandAndFillWithAbsent(nextInInsertionOrder, newCapacity); 173 } 174 175 if (hashTableKToV.length < minCapacity) { 176 int newTableSize = Hashing.closedTableSize(minCapacity, 1.0); 177 hashTableKToV = createFilledWithAbsent(newTableSize); 178 hashTableVToK = createFilledWithAbsent(newTableSize); 179 180 for (int entryToRehash = 0; entryToRehash < size; entryToRehash++) { 181 int keyHash = Hashing.smearedHash(keys[entryToRehash]); 182 int keyBucket = bucket(keyHash); 183 nextInBucketKToV[entryToRehash] = hashTableKToV[keyBucket]; 184 hashTableKToV[keyBucket] = entryToRehash; 185 186 int valueHash = Hashing.smearedHash(values[entryToRehash]); 187 int valueBucket = bucket(valueHash); 188 nextInBucketVToK[entryToRehash] = hashTableVToK[valueBucket]; 189 hashTableVToK[valueBucket] = entryToRehash; 190 } 191 } 192 } 193 194 /** 195 * Returns the bucket (in either the K-to-V or V-to-K tables) where elements with the specified 196 * hash could be found, if present, or could be inserted. 197 */ 198 private int bucket(int hash) { 199 return hash & (hashTableKToV.length - 1); 200 } 201 202 /** Given a key, returns the index of the entry in the tables, or ABSENT if not found. */ 203 int findEntryByKey(@CheckForNull Object key) { 204 return findEntryByKey(key, Hashing.smearedHash(key)); 205 } 206 207 /** 208 * Given a key and its hash, returns the index of the entry in the tables, or ABSENT if not found. 209 */ 210 int findEntryByKey(@CheckForNull Object key, int keyHash) { 211 return findEntry(key, keyHash, hashTableKToV, nextInBucketKToV, keys); 212 } 213 214 /** Given a value, returns the index of the entry in the tables, or ABSENT if not found. */ 215 int findEntryByValue(@CheckForNull Object value) { 216 return findEntryByValue(value, Hashing.smearedHash(value)); 217 } 218 219 /** 220 * Given a value and its hash, returns the index of the entry in the tables, or ABSENT if not 221 * found. 222 */ 223 int findEntryByValue(@CheckForNull Object value, int valueHash) { 224 return findEntry(value, valueHash, hashTableVToK, nextInBucketVToK, values); 225 } 226 227 int findEntry( 228 @CheckForNull Object o, 229 int oHash, 230 int[] hashTable, 231 int[] nextInBucket, 232 @Nullable Object[] array) { 233 for (int entry = hashTable[bucket(oHash)]; entry != ABSENT; entry = nextInBucket[entry]) { 234 if (Objects.equal(array[entry], o)) { 235 return entry; 236 } 237 } 238 return ABSENT; 239 } 240 241 @Override 242 public boolean containsKey(@CheckForNull Object key) { 243 return findEntryByKey(key) != ABSENT; 244 } 245 246 /** 247 * Returns {@code true} if this BiMap contains an entry whose value is equal to {@code value} (or, 248 * equivalently, if this inverse view contains a key that is equal to {@code value}). 249 * 250 * <p>Due to the property that values in a BiMap are unique, this will tend to execute in 251 * faster-than-linear time. 252 * 253 * @param value the object to search for in the values of this BiMap 254 * @return true if a mapping exists from a key to the specified value 255 */ 256 @Override 257 public boolean containsValue(@CheckForNull Object value) { 258 return findEntryByValue(value) != ABSENT; 259 } 260 261 @Override 262 @CheckForNull 263 public V get(@CheckForNull Object key) { 264 int entry = findEntryByKey(key); 265 return (entry == ABSENT) ? null : values[entry]; 266 } 267 268 @CheckForNull 269 K getInverse(@CheckForNull Object value) { 270 int entry = findEntryByValue(value); 271 return (entry == ABSENT) ? null : keys[entry]; 272 } 273 274 @Override 275 @CanIgnoreReturnValue 276 @CheckForNull 277 public V put(@ParametricNullness K key, @ParametricNullness V value) { 278 return put(key, value, false); 279 } 280 281 @CheckForNull 282 V put(@ParametricNullness K key, @ParametricNullness V value, boolean force) { 283 int keyHash = Hashing.smearedHash(key); 284 int entryForKey = findEntryByKey(key, keyHash); 285 if (entryForKey != ABSENT) { 286 V oldValue = values[entryForKey]; 287 if (Objects.equal(oldValue, value)) { 288 return value; 289 } else { 290 replaceValueInEntry(entryForKey, value, force); 291 return oldValue; 292 } 293 } 294 295 int valueHash = Hashing.smearedHash(value); 296 int valueEntry = findEntryByValue(value, valueHash); 297 if (force) { 298 if (valueEntry != ABSENT) { 299 removeEntryValueHashKnown(valueEntry, valueHash); 300 } 301 } else { 302 checkArgument(valueEntry == ABSENT, "Value already present: %s", value); 303 } 304 305 ensureCapacity(size + 1); 306 keys[size] = key; 307 values[size] = value; 308 309 insertIntoTableKToV(size, keyHash); 310 insertIntoTableVToK(size, valueHash); 311 312 setSucceeds(lastInInsertionOrder, size); 313 setSucceeds(size, ENDPOINT); 314 size++; 315 modCount++; 316 return null; 317 } 318 319 @Override 320 @CanIgnoreReturnValue 321 @CheckForNull 322 public V forcePut(@ParametricNullness K key, @ParametricNullness V value) { 323 return put(key, value, true); 324 } 325 326 @CanIgnoreReturnValue 327 @CheckForNull 328 K putInverse(@ParametricNullness V value, @ParametricNullness K key, boolean force) { 329 int valueHash = Hashing.smearedHash(value); 330 int entryForValue = findEntryByValue(value, valueHash); 331 if (entryForValue != ABSENT) { 332 K oldKey = keys[entryForValue]; 333 if (Objects.equal(oldKey, key)) { 334 return key; 335 } else { 336 replaceKeyInEntry(entryForValue, key, force); 337 return oldKey; 338 } 339 } 340 341 int predecessor = lastInInsertionOrder; 342 int keyHash = Hashing.smearedHash(key); 343 int keyEntry = findEntryByKey(key, keyHash); 344 if (force) { 345 if (keyEntry != ABSENT) { 346 predecessor = prevInInsertionOrder[keyEntry]; 347 removeEntryKeyHashKnown(keyEntry, keyHash); 348 } 349 } else { 350 checkArgument(keyEntry == ABSENT, "Key already present: %s", key); 351 } 352 353 // insertion point for new entry is after predecessor 354 // note predecessor must still be a valid entry: either we deleted an entry that was *not* 355 // predecessor, or we didn't delete anything 356 357 ensureCapacity(size + 1); 358 keys[size] = key; 359 values[size] = value; 360 361 insertIntoTableKToV(size, keyHash); 362 insertIntoTableVToK(size, valueHash); 363 364 int successor = 365 (predecessor == ENDPOINT) ? firstInInsertionOrder : nextInInsertionOrder[predecessor]; 366 setSucceeds(predecessor, size); 367 setSucceeds(size, successor); 368 size++; 369 modCount++; 370 return null; 371 } 372 373 /** 374 * Updates the pointers of the insertion order linked list so that {@code next} follows {@code 375 * prev}. {@code ENDPOINT} represents either the first or last entry in the entire map (as 376 * appropriate). 377 */ 378 private void setSucceeds(int prev, int next) { 379 if (prev == ENDPOINT) { 380 firstInInsertionOrder = next; 381 } else { 382 nextInInsertionOrder[prev] = next; 383 } 384 if (next == ENDPOINT) { 385 lastInInsertionOrder = prev; 386 } else { 387 prevInInsertionOrder[next] = prev; 388 } 389 } 390 391 /** 392 * Updates the K-to-V hash table to include the entry at the specified index, which is assumed to 393 * have not yet been added. 394 */ 395 private void insertIntoTableKToV(int entry, int keyHash) { 396 checkArgument(entry != ABSENT); 397 int keyBucket = bucket(keyHash); 398 nextInBucketKToV[entry] = hashTableKToV[keyBucket]; 399 hashTableKToV[keyBucket] = entry; 400 } 401 402 /** 403 * Updates the V-to-K hash table to include the entry at the specified index, which is assumed to 404 * have not yet been added. 405 */ 406 private void insertIntoTableVToK(int entry, int valueHash) { 407 checkArgument(entry != ABSENT); 408 int valueBucket = bucket(valueHash); 409 nextInBucketVToK[entry] = hashTableVToK[valueBucket]; 410 hashTableVToK[valueBucket] = entry; 411 } 412 413 /** 414 * Updates the K-to-V hash table to remove the entry at the specified index, which is assumed to 415 * be present. Does not update any other data structures. 416 */ 417 private void deleteFromTableKToV(int entry, int keyHash) { 418 checkArgument(entry != ABSENT); 419 int keyBucket = bucket(keyHash); 420 421 if (hashTableKToV[keyBucket] == entry) { 422 hashTableKToV[keyBucket] = nextInBucketKToV[entry]; 423 nextInBucketKToV[entry] = ABSENT; 424 return; 425 } 426 427 int prevInBucket = hashTableKToV[keyBucket]; 428 for (int entryInBucket = nextInBucketKToV[prevInBucket]; 429 entryInBucket != ABSENT; 430 entryInBucket = nextInBucketKToV[entryInBucket]) { 431 if (entryInBucket == entry) { 432 nextInBucketKToV[prevInBucket] = nextInBucketKToV[entry]; 433 nextInBucketKToV[entry] = ABSENT; 434 return; 435 } 436 prevInBucket = entryInBucket; 437 } 438 throw new AssertionError("Expected to find entry with key " + keys[entry]); 439 } 440 441 /** 442 * Updates the V-to-K hash table to remove the entry at the specified index, which is assumed to 443 * be present. Does not update any other data structures. 444 */ 445 private void deleteFromTableVToK(int entry, int valueHash) { 446 checkArgument(entry != ABSENT); 447 int valueBucket = bucket(valueHash); 448 449 if (hashTableVToK[valueBucket] == entry) { 450 hashTableVToK[valueBucket] = nextInBucketVToK[entry]; 451 nextInBucketVToK[entry] = ABSENT; 452 return; 453 } 454 455 int prevInBucket = hashTableVToK[valueBucket]; 456 for (int entryInBucket = nextInBucketVToK[prevInBucket]; 457 entryInBucket != ABSENT; 458 entryInBucket = nextInBucketVToK[entryInBucket]) { 459 if (entryInBucket == entry) { 460 nextInBucketVToK[prevInBucket] = nextInBucketVToK[entry]; 461 nextInBucketVToK[entry] = ABSENT; 462 return; 463 } 464 prevInBucket = entryInBucket; 465 } 466 throw new AssertionError("Expected to find entry with value " + values[entry]); 467 } 468 469 /** 470 * Updates the specified entry to point to the new value: removes the old value from the V-to-K 471 * mapping and puts the new one in. The entry does not move in the insertion order of the bimap. 472 */ 473 private void replaceValueInEntry(int entry, @ParametricNullness V newValue, boolean force) { 474 checkArgument(entry != ABSENT); 475 int newValueHash = Hashing.smearedHash(newValue); 476 int newValueIndex = findEntryByValue(newValue, newValueHash); 477 if (newValueIndex != ABSENT) { 478 if (force) { 479 removeEntryValueHashKnown(newValueIndex, newValueHash); 480 if (entry == size) { // this entry got moved to newValueIndex 481 entry = newValueIndex; 482 } 483 } else { 484 throw new IllegalArgumentException("Value already present in map: " + newValue); 485 } 486 } 487 // we do *not* update insertion order, and it isn't a structural modification! 488 deleteFromTableVToK(entry, Hashing.smearedHash(values[entry])); 489 values[entry] = newValue; 490 insertIntoTableVToK(entry, newValueHash); 491 } 492 493 /** 494 * Updates the specified entry to point to the new value: removes the old value from the V-to-K 495 * mapping and puts the new one in. The entry is moved to the end of the insertion order, or to 496 * the position of the new key if it was previously present. 497 */ 498 private void replaceKeyInEntry(int entry, @ParametricNullness K newKey, boolean force) { 499 checkArgument(entry != ABSENT); 500 int newKeyHash = Hashing.smearedHash(newKey); 501 int newKeyIndex = findEntryByKey(newKey, newKeyHash); 502 503 int newPredecessor = lastInInsertionOrder; 504 int newSuccessor = ENDPOINT; 505 if (newKeyIndex != ABSENT) { 506 if (force) { 507 newPredecessor = prevInInsertionOrder[newKeyIndex]; 508 newSuccessor = nextInInsertionOrder[newKeyIndex]; 509 removeEntryKeyHashKnown(newKeyIndex, newKeyHash); 510 if (entry == size) { // this entry got moved to newKeyIndex 511 entry = newKeyIndex; 512 } 513 } else { 514 throw new IllegalArgumentException("Key already present in map: " + newKey); 515 } 516 } 517 if (newPredecessor == entry) { 518 newPredecessor = prevInInsertionOrder[entry]; 519 } else if (newPredecessor == size) { 520 newPredecessor = newKeyIndex; 521 } 522 523 if (newSuccessor == entry) { 524 newSuccessor = nextInInsertionOrder[entry]; 525 } else if (newSuccessor == size) { 526 newSuccessor = newKeyIndex; 527 } 528 529 int oldPredecessor = prevInInsertionOrder[entry]; 530 int oldSuccessor = nextInInsertionOrder[entry]; 531 setSucceeds(oldPredecessor, oldSuccessor); // remove from insertion order linked list 532 533 deleteFromTableKToV(entry, Hashing.smearedHash(keys[entry])); 534 keys[entry] = newKey; 535 insertIntoTableKToV(entry, Hashing.smearedHash(newKey)); 536 537 // insert into insertion order linked list, usually at the end 538 setSucceeds(newPredecessor, entry); 539 setSucceeds(entry, newSuccessor); 540 } 541 542 @Override 543 @CanIgnoreReturnValue 544 @CheckForNull 545 public V remove(@CheckForNull Object key) { 546 int keyHash = Hashing.smearedHash(key); 547 int entry = findEntryByKey(key, keyHash); 548 if (entry == ABSENT) { 549 return null; 550 } else { 551 V value = values[entry]; 552 removeEntryKeyHashKnown(entry, keyHash); 553 return value; 554 } 555 } 556 557 @CheckForNull 558 K removeInverse(@CheckForNull Object value) { 559 int valueHash = Hashing.smearedHash(value); 560 int entry = findEntryByValue(value, valueHash); 561 if (entry == ABSENT) { 562 return null; 563 } else { 564 K key = keys[entry]; 565 removeEntryValueHashKnown(entry, valueHash); 566 return key; 567 } 568 } 569 570 /** Removes the entry at the specified index with no additional data. */ 571 void removeEntry(int entry) { 572 removeEntryKeyHashKnown(entry, Hashing.smearedHash(keys[entry])); 573 } 574 575 /** Removes the entry at the specified index, given the hash of its key and value. */ 576 private void removeEntry(int entry, int keyHash, int valueHash) { 577 checkArgument(entry != ABSENT); 578 deleteFromTableKToV(entry, keyHash); 579 deleteFromTableVToK(entry, valueHash); 580 581 int oldPredecessor = prevInInsertionOrder[entry]; 582 int oldSuccessor = nextInInsertionOrder[entry]; 583 setSucceeds(oldPredecessor, oldSuccessor); 584 585 moveEntryToIndex(size - 1, entry); 586 keys[size - 1] = null; 587 values[size - 1] = null; 588 size--; 589 modCount++; 590 } 591 592 /** Removes the entry at the specified index, given the hash of its key. */ 593 void removeEntryKeyHashKnown(int entry, int keyHash) { 594 removeEntry(entry, keyHash, Hashing.smearedHash(values[entry])); 595 } 596 597 /** Removes the entry at the specified index, given the hash of its value. */ 598 void removeEntryValueHashKnown(int entry, int valueHash) { 599 removeEntry(entry, Hashing.smearedHash(keys[entry]), valueHash); 600 } 601 602 /** 603 * Moves the entry previously positioned at {@code src} to {@code dest}. Assumes the entry 604 * previously at {@code src} has already been removed from the data structures. 605 */ 606 private void moveEntryToIndex(int src, int dest) { 607 if (src == dest) { 608 return; 609 } 610 int predecessor = prevInInsertionOrder[src]; 611 int successor = nextInInsertionOrder[src]; 612 setSucceeds(predecessor, dest); 613 setSucceeds(dest, successor); 614 615 K key = keys[src]; 616 V value = values[src]; 617 618 keys[dest] = key; 619 values[dest] = value; 620 621 // update pointers in hashTableKToV 622 int keyHash = Hashing.smearedHash(key); 623 int keyBucket = bucket(keyHash); 624 if (hashTableKToV[keyBucket] == src) { 625 hashTableKToV[keyBucket] = dest; 626 } else { 627 int prevInBucket = hashTableKToV[keyBucket]; 628 for (int entryInBucket = nextInBucketKToV[prevInBucket]; 629 /* should never reach end */ ; 630 entryInBucket = nextInBucketKToV[entryInBucket]) { 631 if (entryInBucket == src) { 632 nextInBucketKToV[prevInBucket] = dest; 633 break; 634 } 635 prevInBucket = entryInBucket; 636 } 637 } 638 nextInBucketKToV[dest] = nextInBucketKToV[src]; 639 nextInBucketKToV[src] = ABSENT; 640 641 // update pointers in hashTableVToK 642 int valueHash = Hashing.smearedHash(value); 643 int valueBucket = bucket(valueHash); 644 if (hashTableVToK[valueBucket] == src) { 645 hashTableVToK[valueBucket] = dest; 646 } else { 647 int prevInBucket = hashTableVToK[valueBucket]; 648 for (int entryInBucket = nextInBucketVToK[prevInBucket]; 649 /* should never reach end*/ ; 650 entryInBucket = nextInBucketVToK[entryInBucket]) { 651 if (entryInBucket == src) { 652 nextInBucketVToK[prevInBucket] = dest; 653 break; 654 } 655 prevInBucket = entryInBucket; 656 } 657 } 658 nextInBucketVToK[dest] = nextInBucketVToK[src]; 659 nextInBucketVToK[src] = ABSENT; 660 } 661 662 @Override 663 public void clear() { 664 Arrays.fill(keys, 0, size, null); 665 Arrays.fill(values, 0, size, null); 666 Arrays.fill(hashTableKToV, ABSENT); 667 Arrays.fill(hashTableVToK, ABSENT); 668 Arrays.fill(nextInBucketKToV, 0, size, ABSENT); 669 Arrays.fill(nextInBucketVToK, 0, size, ABSENT); 670 Arrays.fill(prevInInsertionOrder, 0, size, ABSENT); 671 Arrays.fill(nextInInsertionOrder, 0, size, ABSENT); 672 size = 0; 673 firstInInsertionOrder = ENDPOINT; 674 lastInInsertionOrder = ENDPOINT; 675 modCount++; 676 } 677 678 /** Shared supertype of keySet, values, entrySet, and inverse.entrySet. */ 679 abstract static class View< 680 K extends @Nullable Object, V extends @Nullable Object, T extends @Nullable Object> 681 extends AbstractSet<T> { 682 final HashBiMap<K, V> biMap; 683 684 View(HashBiMap<K, V> biMap) { 685 this.biMap = biMap; 686 } 687 688 @ParametricNullness 689 abstract T forEntry(int entry); 690 691 @Override 692 public Iterator<T> iterator() { 693 return new Iterator<T>() { 694 private int index = biMap.firstInInsertionOrder; 695 private int indexToRemove = ABSENT; 696 private int expectedModCount = biMap.modCount; 697 698 // Calls to setValue on inverse entries can move already-visited entries to the end. 699 // Make sure we don't visit those. 700 private int remaining = biMap.size; 701 702 private void checkForComodification() { 703 if (biMap.modCount != expectedModCount) { 704 throw new ConcurrentModificationException(); 705 } 706 } 707 708 @Override 709 public boolean hasNext() { 710 checkForComodification(); 711 return index != ENDPOINT && remaining > 0; 712 } 713 714 @Override 715 @ParametricNullness 716 public T next() { 717 if (!hasNext()) { 718 throw new NoSuchElementException(); 719 } 720 T result = forEntry(index); 721 indexToRemove = index; 722 index = biMap.nextInInsertionOrder[index]; 723 remaining--; 724 return result; 725 } 726 727 @Override 728 public void remove() { 729 checkForComodification(); 730 CollectPreconditions.checkRemove(indexToRemove != ABSENT); 731 biMap.removeEntry(indexToRemove); 732 if (index == biMap.size) { 733 index = indexToRemove; 734 } 735 indexToRemove = ABSENT; 736 expectedModCount = biMap.modCount; 737 } 738 }; 739 } 740 741 @Override 742 public int size() { 743 return biMap.size; 744 } 745 746 @Override 747 public void clear() { 748 biMap.clear(); 749 } 750 } 751 752 private transient Set<K> keySet; 753 754 @Override 755 public Set<K> keySet() { 756 Set<K> result = keySet; 757 return (result == null) ? keySet = new KeySet() : result; 758 } 759 760 final class KeySet extends View<K, V, K> { 761 KeySet() { 762 super(HashBiMap.this); 763 } 764 765 @Override 766 @ParametricNullness 767 K forEntry(int entry) { 768 // The cast is safe because we call forEntry only for indexes that contain entries. 769 return uncheckedCastNullableTToT(keys[entry]); 770 } 771 772 @Override 773 public boolean contains(@CheckForNull Object o) { 774 return HashBiMap.this.containsKey(o); 775 } 776 777 @Override 778 public boolean remove(@CheckForNull Object o) { 779 int oHash = Hashing.smearedHash(o); 780 int entry = findEntryByKey(o, oHash); 781 if (entry != ABSENT) { 782 removeEntryKeyHashKnown(entry, oHash); 783 return true; 784 } else { 785 return false; 786 } 787 } 788 } 789 790 private transient Set<V> valueSet; 791 792 @Override 793 public Set<V> values() { 794 Set<V> result = valueSet; 795 return (result == null) ? valueSet = new ValueSet() : result; 796 } 797 798 final class ValueSet extends View<K, V, V> { 799 ValueSet() { 800 super(HashBiMap.this); 801 } 802 803 @Override 804 @ParametricNullness 805 V forEntry(int entry) { 806 // The cast is safe because we call forEntry only for indexes that contain entries. 807 return uncheckedCastNullableTToT(values[entry]); 808 } 809 810 @Override 811 public boolean contains(@CheckForNull Object o) { 812 return HashBiMap.this.containsValue(o); 813 } 814 815 @Override 816 public boolean remove(@CheckForNull Object o) { 817 int oHash = Hashing.smearedHash(o); 818 int entry = findEntryByValue(o, oHash); 819 if (entry != ABSENT) { 820 removeEntryValueHashKnown(entry, oHash); 821 return true; 822 } else { 823 return false; 824 } 825 } 826 } 827 828 private transient Set<Entry<K, V>> entrySet; 829 830 @Override 831 public Set<Entry<K, V>> entrySet() { 832 Set<Entry<K, V>> result = entrySet; 833 return (result == null) ? entrySet = new EntrySet() : result; 834 } 835 836 final class EntrySet extends View<K, V, Entry<K, V>> { 837 EntrySet() { 838 super(HashBiMap.this); 839 } 840 841 @Override 842 public boolean contains(@CheckForNull Object o) { 843 if (o instanceof Entry) { 844 Entry<?, ?> e = (Entry<?, ?>) o; 845 Object k = e.getKey(); 846 Object v = e.getValue(); 847 int eIndex = findEntryByKey(k); 848 return eIndex != ABSENT && Objects.equal(v, values[eIndex]); 849 } 850 return false; 851 } 852 853 @Override 854 @CanIgnoreReturnValue 855 public boolean remove(@CheckForNull Object o) { 856 if (o instanceof Entry) { 857 Entry<?, ?> e = (Entry<?, ?>) o; 858 Object k = e.getKey(); 859 Object v = e.getValue(); 860 int kHash = Hashing.smearedHash(k); 861 int eIndex = findEntryByKey(k, kHash); 862 if (eIndex != ABSENT && Objects.equal(v, values[eIndex])) { 863 removeEntryKeyHashKnown(eIndex, kHash); 864 return true; 865 } 866 } 867 return false; 868 } 869 870 @Override 871 Entry<K, V> forEntry(int entry) { 872 return new EntryForKey(entry); 873 } 874 } 875 876 /** 877 * An {@code Entry} implementation that attempts to follow its key around the map -- that is, if 878 * the key is moved, deleted, or reinserted, it will account for that -- while not doing any extra 879 * work if the key has not moved. One quirk: The {@link #getValue()} method can return {@code 880 * null} even for a map which supposedly does not contain null elements, if the key is not present 881 * when {@code getValue()} is called. 882 */ 883 final class EntryForKey extends AbstractMapEntry<K, V> { 884 @ParametricNullness final K key; 885 int index; 886 887 EntryForKey(int index) { 888 // The cast is safe because we call forEntry only for indexes that contain entries. 889 this.key = uncheckedCastNullableTToT(keys[index]); 890 this.index = index; 891 } 892 893 void updateIndex() { 894 if (index == ABSENT || index > size || !Objects.equal(keys[index], key)) { 895 index = findEntryByKey(key); 896 } 897 } 898 899 @Override 900 @ParametricNullness 901 public K getKey() { 902 return key; 903 } 904 905 @Override 906 @ParametricNullness 907 public V getValue() { 908 updateIndex(); 909 /* 910 * If the entry has been removed from the map, we return null, even though that might not be a 911 * valid value. That's the best we can do, short of holding a reference to the most recently 912 * seen value. And while we *could* do that, we aren't required to: Map.Entry explicitly says 913 * that behavior is undefined when the backing map is modified through another API. (It even 914 * permits us to throw IllegalStateException. Maybe we should have done that, but we probably 915 * shouldn't change now for fear of breaking people.) 916 * 917 * If the entry is still in the map, then updateIndex ensured that `index` points to the right 918 * element. Because that element is present, uncheckedCastNullableTToT is safe. 919 */ 920 return (index == ABSENT) ? unsafeNull() : uncheckedCastNullableTToT(values[index]); 921 } 922 923 @Override 924 @ParametricNullness 925 public V setValue(@ParametricNullness V value) { 926 updateIndex(); 927 if (index == ABSENT) { 928 HashBiMap.this.put(key, value); 929 return unsafeNull(); // See the discussion in getValue(). 930 } 931 /* 932 * The cast is safe because updateIndex found the entry for this key. (If it hadn't, then we 933 * would have returned above.) Thus, we know that it and its corresponding value are in 934 * position `index`. 935 */ 936 V oldValue = uncheckedCastNullableTToT(values[index]); 937 if (Objects.equal(oldValue, value)) { 938 return value; 939 } 940 replaceValueInEntry(index, value, false); 941 return oldValue; 942 } 943 } 944 945 @LazyInit @RetainedWith @CheckForNull private transient BiMap<V, K> inverse; 946 947 @Override 948 public BiMap<V, K> inverse() { 949 BiMap<V, K> result = inverse; 950 return (result == null) ? inverse = new Inverse<K, V>(this) : result; 951 } 952 953 static class Inverse<K extends @Nullable Object, V extends @Nullable Object> 954 extends AbstractMap<V, K> implements BiMap<V, K>, Serializable { 955 private final HashBiMap<K, V> forward; 956 957 Inverse(HashBiMap<K, V> forward) { 958 this.forward = forward; 959 } 960 961 @Override 962 public int size() { 963 return forward.size; 964 } 965 966 @Override 967 public boolean containsKey(@CheckForNull Object key) { 968 return forward.containsValue(key); 969 } 970 971 @Override 972 @CheckForNull 973 public K get(@CheckForNull Object key) { 974 return forward.getInverse(key); 975 } 976 977 @Override 978 public boolean containsValue(@CheckForNull Object value) { 979 return forward.containsKey(value); 980 } 981 982 @Override 983 @CanIgnoreReturnValue 984 @CheckForNull 985 public K put(@ParametricNullness V value, @ParametricNullness K key) { 986 return forward.putInverse(value, key, false); 987 } 988 989 @Override 990 @CanIgnoreReturnValue 991 @CheckForNull 992 public K forcePut(@ParametricNullness V value, @ParametricNullness K key) { 993 return forward.putInverse(value, key, true); 994 } 995 996 @Override 997 public BiMap<K, V> inverse() { 998 return forward; 999 } 1000 1001 @Override 1002 @CanIgnoreReturnValue 1003 @CheckForNull 1004 public K remove(@CheckForNull Object value) { 1005 return forward.removeInverse(value); 1006 } 1007 1008 @Override 1009 public void clear() { 1010 forward.clear(); 1011 } 1012 1013 @Override 1014 public Set<V> keySet() { 1015 return forward.values(); 1016 } 1017 1018 @Override 1019 public Set<K> values() { 1020 return forward.keySet(); 1021 } 1022 1023 private transient Set<Entry<V, K>> inverseEntrySet; 1024 1025 @Override 1026 public Set<Entry<V, K>> entrySet() { 1027 Set<Entry<V, K>> result = inverseEntrySet; 1028 return (result == null) ? inverseEntrySet = new InverseEntrySet<K, V>(forward) : result; 1029 } 1030 1031 @GwtIncompatible("serialization") 1032 private void readObject(ObjectInputStream in) throws ClassNotFoundException, IOException { 1033 in.defaultReadObject(); 1034 this.forward.inverse = this; 1035 } 1036 } 1037 1038 static class InverseEntrySet<K extends @Nullable Object, V extends @Nullable Object> 1039 extends View<K, V, Entry<V, K>> { 1040 InverseEntrySet(HashBiMap<K, V> biMap) { 1041 super(biMap); 1042 } 1043 1044 @Override 1045 public boolean contains(@CheckForNull Object o) { 1046 if (o instanceof Entry) { 1047 Entry<?, ?> e = (Entry<?, ?>) o; 1048 Object v = e.getKey(); 1049 Object k = e.getValue(); 1050 int eIndex = biMap.findEntryByValue(v); 1051 return eIndex != ABSENT && Objects.equal(biMap.keys[eIndex], k); 1052 } 1053 return false; 1054 } 1055 1056 @Override 1057 public boolean remove(@CheckForNull Object o) { 1058 if (o instanceof Entry) { 1059 Entry<?, ?> e = (Entry<?, ?>) o; 1060 Object v = e.getKey(); 1061 Object k = e.getValue(); 1062 int vHash = Hashing.smearedHash(v); 1063 int eIndex = biMap.findEntryByValue(v, vHash); 1064 if (eIndex != ABSENT && Objects.equal(biMap.keys[eIndex], k)) { 1065 biMap.removeEntryValueHashKnown(eIndex, vHash); 1066 return true; 1067 } 1068 } 1069 return false; 1070 } 1071 1072 @Override 1073 Entry<V, K> forEntry(int entry) { 1074 return new EntryForValue<K, V>(biMap, entry); 1075 } 1076 } 1077 1078 /** 1079 * An {@code Entry} implementation that attempts to follow its value around the map -- that is, if 1080 * the value is moved, deleted, or reinserted, it will account for that -- while not doing any 1081 * extra work if the value has not moved. 1082 */ 1083 static final class EntryForValue<K extends @Nullable Object, V extends @Nullable Object> 1084 extends AbstractMapEntry<V, K> { 1085 final HashBiMap<K, V> biMap; 1086 @ParametricNullness final V value; 1087 int index; 1088 1089 EntryForValue(HashBiMap<K, V> biMap, int index) { 1090 this.biMap = biMap; 1091 // The cast is safe because we call forEntry only for indexes that contain entries. 1092 this.value = uncheckedCastNullableTToT(biMap.values[index]); 1093 this.index = index; 1094 } 1095 1096 private void updateIndex() { 1097 if (index == ABSENT || index > biMap.size || !Objects.equal(value, biMap.values[index])) { 1098 index = biMap.findEntryByValue(value); 1099 } 1100 } 1101 1102 @Override 1103 @ParametricNullness 1104 public V getKey() { 1105 return value; 1106 } 1107 1108 @Override 1109 @ParametricNullness 1110 public K getValue() { 1111 updateIndex(); 1112 // For discussion of unsafeNull() and uncheckedCastNullableTToT(), see EntryForKey.getValue(). 1113 return (index == ABSENT) ? unsafeNull() : uncheckedCastNullableTToT(biMap.keys[index]); 1114 } 1115 1116 @Override 1117 @ParametricNullness 1118 public K setValue(@ParametricNullness K key) { 1119 updateIndex(); 1120 if (index == ABSENT) { 1121 biMap.putInverse(value, key, false); 1122 return unsafeNull(); // see EntryForKey.setValue() 1123 } 1124 K oldKey = uncheckedCastNullableTToT(biMap.keys[index]); // see EntryForKey.setValue() 1125 if (Objects.equal(oldKey, key)) { 1126 return key; 1127 } 1128 biMap.replaceKeyInEntry(index, key, false); 1129 return oldKey; 1130 } 1131 } 1132 1133 /** 1134 * @serialData the number of entries, first key, first value, second key, second value, and so on. 1135 */ 1136 @GwtIncompatible // java.io.ObjectOutputStream 1137 private void writeObject(ObjectOutputStream stream) throws IOException { 1138 stream.defaultWriteObject(); 1139 Serialization.writeMap(this, stream); 1140 } 1141 1142 @GwtIncompatible // java.io.ObjectInputStream 1143 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 1144 stream.defaultReadObject(); 1145 int size = Serialization.readCount(stream); 1146 init(16); // resist hostile attempts to allocate gratuitous heap 1147 Serialization.populateMap(this, stream, size); 1148 } 1149}