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