001 /* IdentityHashMap.java -- a class providing a hashtable data structure, 002 mapping Object --> Object, which uses object identity for hashing. 003 Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 004 005 This file is part of GNU Classpath. 006 007 GNU Classpath is free software; you can redistribute it and/or modify 008 it under the terms of the GNU General Public License as published by 009 the Free Software Foundation; either version 2, or (at your option) 010 any later version. 011 012 GNU Classpath is distributed in the hope that it will be useful, but 013 WITHOUT ANY WARRANTY; without even the implied warranty of 014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015 General Public License for more details. 016 017 You should have received a copy of the GNU General Public License 018 along with GNU Classpath; see the file COPYING. If not, write to the 019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 020 02110-1301 USA. 021 022 Linking this library statically or dynamically with other modules is 023 making a combined work based on this library. Thus, the terms and 024 conditions of the GNU General Public License cover the whole 025 combination. 026 027 As a special exception, the copyright holders of this library give you 028 permission to link this library with independent modules to produce an 029 executable, regardless of the license terms of these independent 030 modules, and to copy and distribute the resulting executable under 031 terms of your choice, provided that you also meet, for each linked 032 independent module, the terms and conditions of the license of that 033 module. An independent module is a module which is not derived from 034 or based on this library. If you modify this library, you may extend 035 this exception to your version of the library, but you are not 036 obligated to do so. If you do not wish to do so, delete this 037 exception statement from your version. */ 038 039 package java.util; 040 041 import java.io.IOException; 042 import java.io.ObjectInputStream; 043 import java.io.ObjectOutputStream; 044 import java.io.Serializable; 045 046 /** 047 * This class provides a hashtable-backed implementation of the 048 * Map interface, but uses object identity to do its hashing. In fact, 049 * it uses object identity for comparing values, as well. It uses a 050 * linear-probe hash table, which may have faster performance 051 * than the chaining employed by HashMap. 052 * <p> 053 * 054 * <em>WARNING: This is not a general purpose map. Because it uses 055 * System.identityHashCode and ==, instead of hashCode and equals, for 056 * comparison, it violated Map's general contract, and may cause 057 * undefined behavior when compared to other maps which are not 058 * IdentityHashMaps. This is designed only for the rare cases when 059 * identity semantics are needed.</em> An example use is 060 * topology-preserving graph transformations, such as deep cloning, 061 * or as proxy object mapping such as in debugging. 062 * <p> 063 * 064 * This map permits <code>null</code> keys and values, and does not 065 * guarantee that elements will stay in the same order over time. The 066 * basic operations (<code>get</code> and <code>put</code>) take 067 * constant time, provided System.identityHashCode is decent. You can 068 * tune the behavior by specifying the expected maximum size. As more 069 * elements are added, the map may need to allocate a larger table, 070 * which can be expensive. 071 * <p> 072 * 073 * This implementation is unsynchronized. If you want multi-thread 074 * access to be consistent, you must synchronize it, perhaps by using 075 * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>. 076 * The iterators are <i>fail-fast</i>, meaning that a structural modification 077 * made to the map outside of an iterator's remove method cause the 078 * iterator, and in the case of the entrySet, the Map.Entry, to 079 * fail with a {@link ConcurrentModificationException}. 080 * 081 * @author Tom Tromey (tromey@redhat.com) 082 * @author Eric Blake (ebb9@email.byu.edu) 083 * @see System#identityHashCode(Object) 084 * @see Collection 085 * @see Map 086 * @see HashMap 087 * @see TreeMap 088 * @see LinkedHashMap 089 * @see WeakHashMap 090 * @since 1.4 091 * @status updated to 1.4 092 */ 093 public class IdentityHashMap<K,V> extends AbstractMap<K,V> 094 implements Map<K,V>, Serializable, Cloneable 095 { 096 /** The default capacity. */ 097 private static final int DEFAULT_CAPACITY = 21; 098 099 /** 100 * This object is used to mark a slot whose key or value is 'null'. 101 * This is more efficient than using a special value to mark an empty 102 * slot, because null entries are rare, empty slots are common, and 103 * the JVM will clear new arrays for us. 104 * Package visible for use by nested classes. 105 */ 106 static final Object nullslot = new Object(); 107 108 /** 109 * Compatible with JDK 1.4. 110 */ 111 private static final long serialVersionUID = 8188218128353913216L; 112 113 /** 114 * The number of mappings in the table. Package visible for use by nested 115 * classes. 116 * @serial 117 */ 118 int size; 119 120 /** 121 * The table itself. Package visible for use by nested classes. 122 */ 123 transient Object[] table; 124 125 /** 126 * The number of structural modifications made so far. Package visible for 127 * use by nested classes. 128 */ 129 transient int modCount; 130 131 /** 132 * The cache for {@link #entrySet()}. 133 */ 134 private transient Set<Map.Entry<K,V>> entries; 135 136 /** 137 * The threshold for rehashing, which is 75% of (table.length / 2). 138 */ 139 private transient int threshold; 140 141 /** 142 * Create a new IdentityHashMap with the default capacity (21 entries). 143 */ 144 public IdentityHashMap() 145 { 146 this(DEFAULT_CAPACITY); 147 } 148 149 /** 150 * Create a new IdentityHashMap with the indicated number of 151 * entries. If the number of elements added to this hash map 152 * exceeds this maximum, the map will grow itself; however, that 153 * incurs a performance penalty. 154 * 155 * @param max initial size 156 * @throws IllegalArgumentException if max is negative 157 */ 158 public IdentityHashMap(int max) 159 { 160 if (max < 0) 161 throw new IllegalArgumentException(); 162 // Need at least two slots, or hash() will break. 163 if (max < 2) 164 max = 2; 165 table = new Object[max << 1]; 166 threshold = (max >> 2) * 3; 167 } 168 169 /** 170 * Create a new IdentityHashMap whose contents are taken from the 171 * given Map. 172 * 173 * @param m The map whose elements are to be put in this map 174 * @throws NullPointerException if m is null 175 */ 176 public IdentityHashMap(Map<? extends K, ? extends V> m) 177 { 178 this(Math.max(m.size() << 1, DEFAULT_CAPACITY)); 179 putAll(m); 180 } 181 182 /** 183 * Remove all mappings from this map. 184 */ 185 public void clear() 186 { 187 if (size != 0) 188 { 189 modCount++; 190 Arrays.fill(table, null); 191 size = 0; 192 } 193 } 194 195 /** 196 * Creates a shallow copy where keys and values are not cloned. 197 */ 198 public Object clone() 199 { 200 try 201 { 202 IdentityHashMap copy = (IdentityHashMap) super.clone(); 203 copy.table = (Object[]) table.clone(); 204 copy.entries = null; // invalidate the cache 205 return copy; 206 } 207 catch (CloneNotSupportedException e) 208 { 209 // Can't happen. 210 return null; 211 } 212 } 213 214 /** 215 * Tests whether the specified key is in this map. Unlike normal Maps, 216 * this test uses <code>entry == key</code> instead of 217 * <code>entry == null ? key == null : entry.equals(key)</code>. 218 * 219 * @param key the key to look for 220 * @return true if the key is contained in the map 221 * @see #containsValue(Object) 222 * @see #get(Object) 223 */ 224 public boolean containsKey(Object key) 225 { 226 key = xform(key); 227 return key == table[hash(key)]; 228 } 229 230 /** 231 * Returns true if this HashMap contains the value. Unlike normal maps, 232 * this test uses <code>entry == value</code> instead of 233 * <code>entry == null ? value == null : entry.equals(value)</code>. 234 * 235 * @param value the value to search for in this HashMap 236 * @return true if at least one key maps to the value 237 * @see #containsKey(Object) 238 */ 239 public boolean containsValue(Object value) 240 { 241 value = xform(value); 242 for (int i = table.length - 1; i > 0; i -= 2) 243 if (table[i] == value) 244 return true; 245 return false; 246 } 247 248 /** 249 * Returns a "set view" of this Map's entries. The set is backed by 250 * the Map, so changes in one show up in the other. The set supports 251 * element removal, but not element addition. 252 * <p> 253 * 254 * <em>The semantics of this set, and of its contained entries, are 255 * different from the contract of Set and Map.Entry in order to make 256 * IdentityHashMap work. This means that while you can compare these 257 * objects between IdentityHashMaps, comparing them with regular sets 258 * or entries is likely to have undefined behavior.</em> The entries 259 * in this set are reference-based, rather than the normal object 260 * equality. Therefore, <code>e1.equals(e2)</code> returns 261 * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>, 262 * and <code>e.hashCode()</code> returns 263 * <code>System.identityHashCode(e.getKey()) ^ 264 * System.identityHashCode(e.getValue())</code>. 265 * <p> 266 * 267 * Note that the iterators for all three views, from keySet(), entrySet(), 268 * and values(), traverse the Map in the same sequence. 269 * 270 * @return a set view of the entries 271 * @see #keySet() 272 * @see #values() 273 * @see Map.Entry 274 */ 275 public Set<Map.Entry<K,V>> entrySet() 276 { 277 if (entries == null) 278 entries = new AbstractSet<Map.Entry<K,V>>() 279 { 280 public int size() 281 { 282 return size; 283 } 284 285 public Iterator<Map.Entry<K,V>> iterator() 286 { 287 return new IdentityIterator<Map.Entry<K,V>>(ENTRIES); 288 } 289 290 public void clear() 291 { 292 IdentityHashMap.this.clear(); 293 } 294 295 public boolean contains(Object o) 296 { 297 if (! (o instanceof Map.Entry)) 298 return false; 299 Map.Entry m = (Map.Entry) o; 300 Object value = xform(m.getValue()); 301 Object key = xform(m.getKey()); 302 return value == table[hash(key) + 1]; 303 } 304 305 public int hashCode() 306 { 307 return IdentityHashMap.this.hashCode(); 308 } 309 310 public boolean remove(Object o) 311 { 312 if (! (o instanceof Map.Entry)) 313 return false; 314 Object key = xform(((Map.Entry) o).getKey()); 315 int h = hash(key); 316 if (table[h] == key) 317 { 318 size--; 319 modCount++; 320 IdentityHashMap.this.removeAtIndex(h); 321 return true; 322 } 323 return false; 324 } 325 }; 326 return entries; 327 } 328 329 /** 330 * Compares two maps for equality. This returns true only if both maps 331 * have the same reference-identity comparisons. While this returns 332 * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map, 333 * this will not work with normal maps, since the entry set compares 334 * with == instead of .equals. 335 * 336 * @param o the object to compare to 337 * @return true if it is equal 338 */ 339 public boolean equals(Object o) 340 { 341 // Why did Sun specify this one? The superclass does the right thing. 342 return super.equals(o); 343 } 344 345 /** 346 * Return the value in this Map associated with the supplied key, or 347 * <code>null</code> if the key maps to nothing. 348 * 349 * <p>NOTE: Since the value could also be null, you must use 350 * containsKey to see if this key actually maps to something. 351 * Unlike normal maps, this tests for the key with <code>entry == 352 * key</code> instead of <code>entry == null ? key == null : 353 * entry.equals(key)</code>. 354 * 355 * @param key the key for which to fetch an associated value 356 * @return what the key maps to, if present 357 * @see #put(Object, Object) 358 * @see #containsKey(Object) 359 */ 360 public V get(Object key) 361 { 362 key = xform(key); 363 int h = hash(key); 364 return (V) (table[h] == key ? unxform(table[h + 1]) : null); 365 } 366 367 /** 368 * Returns the hashcode of this map. This guarantees that two 369 * IdentityHashMaps that compare with equals() will have the same hash code, 370 * but may break with comparison to normal maps since it uses 371 * System.identityHashCode() instead of hashCode(). 372 * 373 * @return the hash code 374 */ 375 public int hashCode() 376 { 377 int hash = 0; 378 for (int i = table.length - 2; i >= 0; i -= 2) 379 { 380 Object key = table[i]; 381 if (key == null) 382 continue; 383 // FIXME: this is a lame computation. 384 hash += (System.identityHashCode(unxform(key)) 385 ^ System.identityHashCode(unxform(table[i + 1]))); 386 } 387 return hash; 388 } 389 390 /** 391 * Returns true if there are no key-value mappings currently in this Map 392 * @return <code>size() == 0</code> 393 */ 394 public boolean isEmpty() 395 { 396 return size == 0; 397 } 398 399 /** 400 * Returns a "set view" of this Map's keys. The set is backed by the 401 * Map, so changes in one show up in the other. The set supports 402 * element removal, but not element addition. 403 * <p> 404 * 405 * <em>The semantics of this set are different from the contract of Set 406 * in order to make IdentityHashMap work. This means that while you can 407 * compare these objects between IdentityHashMaps, comparing them with 408 * regular sets is likely to have undefined behavior.</em> The hashCode 409 * of the set is the sum of the identity hash codes, instead of the 410 * regular hashCodes, and equality is determined by reference instead 411 * of by the equals method. 412 * <p> 413 * 414 * @return a set view of the keys 415 * @see #values() 416 * @see #entrySet() 417 */ 418 public Set<K> keySet() 419 { 420 if (keys == null) 421 keys = new AbstractSet<K>() 422 { 423 public int size() 424 { 425 return size; 426 } 427 428 public Iterator<K> iterator() 429 { 430 return new IdentityIterator<K>(KEYS); 431 } 432 433 public void clear() 434 { 435 IdentityHashMap.this.clear(); 436 } 437 438 public boolean contains(Object o) 439 { 440 return containsKey(o); 441 } 442 443 public int hashCode() 444 { 445 int hash = 0; 446 for (int i = table.length - 2; i >= 0; i -= 2) 447 { 448 Object key = table[i]; 449 if (key == null) 450 continue; 451 hash += System.identityHashCode(unxform(key)); 452 } 453 return hash; 454 } 455 456 public boolean remove(Object o) 457 { 458 o = xform(o); 459 int h = hash(o); 460 if (table[h] == o) 461 { 462 size--; 463 modCount++; 464 removeAtIndex(h); 465 return true; 466 } 467 return false; 468 } 469 }; 470 return keys; 471 } 472 473 /** 474 * Puts the supplied value into the Map, mapped by the supplied key. 475 * The value may be retrieved by any object which <code>equals()</code> 476 * this key. NOTE: Since the prior value could also be null, you must 477 * first use containsKey if you want to see if you are replacing the 478 * key's mapping. Unlike normal maps, this tests for the key 479 * with <code>entry == key</code> instead of 480 * <code>entry == null ? key == null : entry.equals(key)</code>. 481 * 482 * @param key the key used to locate the value 483 * @param value the value to be stored in the HashMap 484 * @return the prior mapping of the key, or null if there was none 485 * @see #get(Object) 486 */ 487 public V put(K key, V value) 488 { 489 key = (K) xform(key); 490 value = (V) xform(value); 491 492 // We don't want to rehash if we're overwriting an existing slot. 493 int h = hash(key); 494 if (table[h] == key) 495 { 496 V r = (V) unxform(table[h + 1]); 497 table[h + 1] = value; 498 return r; 499 } 500 501 // Rehash if the load factor is too high. 502 if (size > threshold) 503 { 504 Object[] old = table; 505 // This isn't necessarily prime, but it is an odd number of key/value 506 // slots, which has a higher probability of fewer collisions. 507 table = new Object[(old.length * 2) + 2]; 508 size = 0; 509 threshold = (table.length >>> 3) * 3; 510 511 for (int i = old.length - 2; i >= 0; i -= 2) 512 { 513 K oldkey = (K) old[i]; 514 if (oldkey != null) 515 { 516 h = hash(oldkey); 517 table[h] = oldkey; 518 table[h + 1] = old[i + 1]; 519 ++size; 520 // No need to update modCount here, we'll do it 521 // just after the loop. 522 } 523 } 524 525 // Now that we've resize, recompute the hash value. 526 h = hash(key); 527 } 528 529 // At this point, we add a new mapping. 530 modCount++; 531 size++; 532 table[h] = key; 533 table[h + 1] = value; 534 return null; 535 } 536 537 /** 538 * Copies all of the mappings from the specified map to this. If a key 539 * is already in this map, its value is replaced. 540 * 541 * @param m the map to copy 542 * @throws NullPointerException if m is null 543 */ 544 public void putAll(Map<? extends K, ? extends V> m) 545 { 546 // Why did Sun specify this one? The superclass does the right thing. 547 super.putAll(m); 548 } 549 550 /** 551 * Remove the element at index and update the table to compensate. 552 * This is package-private for use by inner classes. 553 * @param i index of the removed element 554 */ 555 final void removeAtIndex(int i) 556 { 557 // This is Algorithm R from Knuth, section 6.4. 558 // Variable names are taken directly from the text. 559 while (true) 560 { 561 table[i] = null; 562 table[i + 1] = null; 563 int j = i; 564 int r; 565 do 566 { 567 i -= 2; 568 if (i < 0) 569 i = table.length - 2; 570 Object key = table[i]; 571 if (key == null) 572 return; 573 r = Math.abs(System.identityHashCode(key) 574 % (table.length >> 1)) << 1; 575 } 576 while ((i <= r && r < j) 577 || (r < j && j < i) 578 || (j < i && i <= r)); 579 table[j] = table[i]; 580 table[j + 1] = table[i + 1]; 581 } 582 } 583 584 /** 585 * Removes from the HashMap and returns the value which is mapped by 586 * the supplied key. If the key maps to nothing, then the HashMap 587 * remains unchanged, and <code>null</code> is returned. 588 * 589 * NOTE: Since the value could also be null, you must use 590 * containsKey to see if you are actually removing a mapping. 591 * Unlike normal maps, this tests for the key with <code>entry == 592 * key</code> instead of <code>entry == null ? key == null : 593 * entry.equals(key)</code>. 594 * 595 * @param key the key used to locate the value to remove 596 * @return whatever the key mapped to, if present 597 */ 598 public V remove(Object key) 599 { 600 key = xform(key); 601 int h = hash(key); 602 if (table[h] == key) 603 { 604 modCount++; 605 size--; 606 Object r = unxform(table[h + 1]); 607 removeAtIndex(h); 608 return (V) r; 609 } 610 return null; 611 } 612 613 /** 614 * Returns the number of kay-value mappings currently in this Map 615 * @return the size 616 */ 617 public int size() 618 { 619 return size; 620 } 621 622 /** 623 * Returns a "collection view" (or "bag view") of this Map's values. 624 * The collection is backed by the Map, so changes in one show up 625 * in the other. The collection supports element removal, but not element 626 * addition. 627 * <p> 628 * 629 * <em>The semantics of this set are different from the contract of 630 * Collection in order to make IdentityHashMap work. This means that 631 * while you can compare these objects between IdentityHashMaps, comparing 632 * them with regular sets is likely to have undefined behavior.</em> 633 * Likewise, contains and remove go by == instead of equals(). 634 * <p> 635 * 636 * @return a bag view of the values 637 * @see #keySet() 638 * @see #entrySet() 639 */ 640 public Collection<V> values() 641 { 642 if (values == null) 643 values = new AbstractCollection<V>() 644 { 645 public int size() 646 { 647 return size; 648 } 649 650 public Iterator<V> iterator() 651 { 652 return new IdentityIterator<V>(VALUES); 653 } 654 655 public void clear() 656 { 657 IdentityHashMap.this.clear(); 658 } 659 660 public boolean remove(Object o) 661 { 662 o = xform(o); 663 // This approach may look strange, but it is ok. 664 for (int i = table.length - 1; i > 0; i -= 2) 665 if (table[i] == o) 666 { 667 modCount++; 668 size--; 669 IdentityHashMap.this.removeAtIndex(i - 1); 670 return true; 671 } 672 return false; 673 } 674 }; 675 return values; 676 } 677 678 /** 679 * Transform a reference from its external form to its internal form. 680 * This is package-private for use by inner classes. 681 */ 682 final Object xform(Object o) 683 { 684 if (o == null) 685 o = nullslot; 686 return o; 687 } 688 689 /** 690 * Transform a reference from its internal form to its external form. 691 * This is package-private for use by inner classes. 692 */ 693 final Object unxform(Object o) 694 { 695 if (o == nullslot) 696 o = null; 697 return o; 698 } 699 700 /** 701 * Helper method which computes the hash code, then traverses the table 702 * until it finds the key, or the spot where the key would go. the key 703 * must already be in its internal form. 704 * 705 * @param key the key to check 706 * @return the index where the key belongs 707 * @see #IdentityHashMap(int) 708 * @see #put(Object, Object) 709 */ 710 // Package visible for use by nested classes. 711 final int hash(Object key) 712 { 713 int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1; 714 715 while (true) 716 { 717 // By requiring at least 2 key/value slots, and rehashing at 75% 718 // capacity, we guarantee that there will always be either an empty 719 // slot somewhere in the table. 720 if (table[h] == key || table[h] == null) 721 return h; 722 // We use linear probing as it is friendlier to the cache and 723 // it lets us efficiently remove entries. 724 h -= 2; 725 if (h < 0) 726 h = table.length - 2; 727 } 728 } 729 730 /** 731 * This class allows parameterized iteration over IdentityHashMaps. Based 732 * on its construction, it returns the key or value of a mapping, or 733 * creates the appropriate Map.Entry object with the correct fail-fast 734 * semantics and identity comparisons. 735 * 736 * @author Tom Tromey (tromey@redhat.com) 737 * @author Eric Blake (ebb9@email.byu.edu) 738 */ 739 private class IdentityIterator<I> implements Iterator<I> 740 { 741 /** 742 * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 743 * or {@link #ENTRIES}. 744 */ 745 final int type; 746 /** The number of modifications to the backing Map that we know about. */ 747 int knownMod = modCount; 748 /** The number of elements remaining to be returned by next(). */ 749 int count = size; 750 /** Location in the table. */ 751 int loc = table.length; 752 753 /** 754 * Construct a new Iterator with the supplied type. 755 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 756 */ 757 IdentityIterator(int type) 758 { 759 this.type = type; 760 } 761 762 /** 763 * Returns true if the Iterator has more elements. 764 * @return true if there are more elements 765 */ 766 public boolean hasNext() 767 { 768 return count > 0; 769 } 770 771 /** 772 * Returns the next element in the Iterator's sequential view. 773 * @return the next element 774 * @throws ConcurrentModificationException if the Map was modified 775 * @throws NoSuchElementException if there is none 776 */ 777 public I next() 778 { 779 if (knownMod != modCount) 780 throw new ConcurrentModificationException(); 781 if (count == 0) 782 throw new NoSuchElementException(); 783 count--; 784 785 Object key; 786 do 787 { 788 loc -= 2; 789 key = table[loc]; 790 } 791 while (key == null); 792 793 return (I) (type == KEYS ? unxform(key) 794 : (type == VALUES ? unxform(table[loc + 1]) 795 : new IdentityEntry(loc))); 796 } 797 798 /** 799 * Removes from the backing Map the last element which was fetched 800 * with the <code>next()</code> method. 801 * 802 * @throws ConcurrentModificationException if the Map was modified 803 * @throws IllegalStateException if called when there is no last element 804 */ 805 public void remove() 806 { 807 if (knownMod != modCount) 808 throw new ConcurrentModificationException(); 809 if (loc == table.length) 810 throw new IllegalStateException(); 811 modCount++; 812 size--; 813 removeAtIndex(loc); 814 knownMod++; 815 } 816 } // class IdentityIterator 817 818 /** 819 * This class provides Map.Entry objects for IdentityHashMaps. The entry 820 * is fail-fast, and will throw a ConcurrentModificationException if 821 * the underlying map is modified, or if remove is called on the iterator 822 * that generated this object. It is identity based, so it violates 823 * the general contract of Map.Entry, and is probably unsuitable for 824 * comparison to normal maps; but it works among other IdentityHashMaps. 825 * 826 * @author Eric Blake (ebb9@email.byu.edu) 827 */ 828 private final class IdentityEntry<EK,EV> implements Map.Entry<EK,EV> 829 { 830 /** The location of this entry. */ 831 final int loc; 832 /** The number of modifications to the backing Map that we know about. */ 833 final int knownMod = modCount; 834 835 /** 836 * Constructs the Entry. 837 * 838 * @param loc the location of this entry in table 839 */ 840 IdentityEntry(int loc) 841 { 842 this.loc = loc; 843 } 844 845 /** 846 * Compares the specified object with this entry, using identity 847 * semantics. Note that this can lead to undefined results with 848 * Entry objects created by normal maps. 849 * 850 * @param o the object to compare 851 * @return true if it is equal 852 * @throws ConcurrentModificationException if the entry was invalidated 853 * by modifying the Map or calling Iterator.remove() 854 */ 855 public boolean equals(Object o) 856 { 857 if (knownMod != modCount) 858 throw new ConcurrentModificationException(); 859 if (! (o instanceof Map.Entry)) 860 return false; 861 Map.Entry e = (Map.Entry) o; 862 return table[loc] == xform(e.getKey()) 863 && table[loc + 1] == xform(e.getValue()); 864 } 865 866 /** 867 * Returns the key of this entry. 868 * 869 * @return the key 870 * @throws ConcurrentModificationException if the entry was invalidated 871 * by modifying the Map or calling Iterator.remove() 872 */ 873 public EK getKey() 874 { 875 if (knownMod != modCount) 876 throw new ConcurrentModificationException(); 877 return (EK) unxform(table[loc]); 878 } 879 880 /** 881 * Returns the value of this entry. 882 * 883 * @return the value 884 * @throws ConcurrentModificationException if the entry was invalidated 885 * by modifying the Map or calling Iterator.remove() 886 */ 887 public EV getValue() 888 { 889 if (knownMod != modCount) 890 throw new ConcurrentModificationException(); 891 return (EV) unxform(table[loc + 1]); 892 } 893 894 /** 895 * Returns the hashcode of the entry, using identity semantics. 896 * Note that this can lead to undefined results with Entry objects 897 * created by normal maps. 898 * 899 * @return the hash code 900 * @throws ConcurrentModificationException if the entry was invalidated 901 * by modifying the Map or calling Iterator.remove() 902 */ 903 public int hashCode() 904 { 905 if (knownMod != modCount) 906 throw new ConcurrentModificationException(); 907 return (System.identityHashCode(unxform(table[loc])) 908 ^ System.identityHashCode(unxform(table[loc + 1]))); 909 } 910 911 /** 912 * Replaces the value of this mapping, and returns the old value. 913 * 914 * @param value the new value 915 * @return the old value 916 * @throws ConcurrentModificationException if the entry was invalidated 917 * by modifying the Map or calling Iterator.remove() 918 */ 919 public EV setValue(EV value) 920 { 921 if (knownMod != modCount) 922 throw new ConcurrentModificationException(); 923 EV r = (EV) unxform(table[loc + 1]); 924 table[loc + 1] = xform(value); 925 return r; 926 } 927 928 /** 929 * This provides a string representation of the entry. It is of the form 930 * "key=value", where string concatenation is used on key and value. 931 * 932 * @return the string representation 933 * @throws ConcurrentModificationException if the entry was invalidated 934 * by modifying the Map or calling Iterator.remove() 935 */ 936 public String toString() 937 { 938 if (knownMod != modCount) 939 throw new ConcurrentModificationException(); 940 return unxform(table[loc]) + "=" + unxform(table[loc + 1]); 941 } 942 } // class IdentityEntry 943 944 /** 945 * Reads the object from a serial stream. 946 * 947 * @param s the stream to read from 948 * @throws ClassNotFoundException if the underlying stream fails 949 * @throws IOException if the underlying stream fails 950 * @serialData expects the size (int), followed by that many key (Object) 951 * and value (Object) pairs, with the pairs in no particular 952 * order 953 */ 954 private void readObject(ObjectInputStream s) 955 throws IOException, ClassNotFoundException 956 { 957 s.defaultReadObject(); 958 959 int num = s.readInt(); 960 table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1]; 961 // Read key/value pairs. 962 while (--num >= 0) 963 put((K) s.readObject(), (V) s.readObject()); 964 } 965 966 /** 967 * Writes the object to a serial stream. 968 * 969 * @param s the stream to write to 970 * @throws IOException if the underlying stream fails 971 * @serialData outputs the size (int), followed by that many key (Object) 972 * and value (Object) pairs, with the pairs in no particular 973 * order 974 */ 975 private void writeObject(ObjectOutputStream s) 976 throws IOException 977 { 978 s.defaultWriteObject(); 979 s.writeInt(size); 980 for (int i = table.length - 2; i >= 0; i -= 2) 981 { 982 Object key = table[i]; 983 if (key != null) 984 { 985 s.writeObject(unxform(key)); 986 s.writeObject(unxform(table[i + 1])); 987 } 988 } 989 } 990 }