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