| Frames | No Frames |
1: /* IdentityHashMap.java -- a class providing a hashtable data structure, 2: mapping Object --> Object, which uses object identity for hashing. 3: Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 4: 5: This file is part of GNU Classpath. 6: 7: GNU Classpath is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU Classpath is distributed in the hope that it will be useful, but 13: WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15: General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU Classpath; see the file COPYING. If not, write to the 19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20: 02110-1301 USA. 21: 22: Linking this library statically or dynamically with other modules is 23: making a combined work based on this library. Thus, the terms and 24: conditions of the GNU General Public License cover the whole 25: combination. 26: 27: As a special exception, the copyright holders of this library give you 28: permission to link this library with independent modules to produce an 29: executable, regardless of the license terms of these independent 30: modules, and to copy and distribute the resulting executable under 31: terms of your choice, provided that you also meet, for each linked 32: independent module, the terms and conditions of the license of that 33: module. An independent module is a module which is not derived from 34: or based on this library. If you modify this library, you may extend 35: this exception to your version of the library, but you are not 36: obligated to do so. If you do not wish to do so, delete this 37: exception statement from your version. */ 38: 39: package java.util; 40: 41: import java.io.IOException; 42: import java.io.ObjectInputStream; 43: import java.io.ObjectOutputStream; 44: import java.io.Serializable; 45: 46: /** 47: * This class provides a hashtable-backed implementation of the 48: * Map interface, but uses object identity to do its hashing. In fact, 49: * it uses object identity for comparing values, as well. It uses a 50: * linear-probe hash table, which may have faster performance 51: * than the chaining employed by HashMap. 52: * <p> 53: * 54: * <em>WARNING: This is not a general purpose map. Because it uses 55: * System.identityHashCode and ==, instead of hashCode and equals, for 56: * comparison, it violated Map's general contract, and may cause 57: * undefined behavior when compared to other maps which are not 58: * IdentityHashMaps. This is designed only for the rare cases when 59: * identity semantics are needed.</em> An example use is 60: * topology-preserving graph transformations, such as deep cloning, 61: * or as proxy object mapping such as in debugging. 62: * <p> 63: * 64: * This map permits <code>null</code> keys and values, and does not 65: * guarantee that elements will stay in the same order over time. The 66: * basic operations (<code>get</code> and <code>put</code>) take 67: * constant time, provided System.identityHashCode is decent. You can 68: * tune the behavior by specifying the expected maximum size. As more 69: * elements are added, the map may need to allocate a larger table, 70: * which can be expensive. 71: * <p> 72: * 73: * This implementation is unsynchronized. If you want multi-thread 74: * access to be consistent, you must synchronize it, perhaps by using 75: * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>. 76: * The iterators are <i>fail-fast</i>, meaning that a structural modification 77: * made to the map outside of an iterator's remove method cause the 78: * iterator, and in the case of the entrySet, the Map.Entry, to 79: * fail with a {@link ConcurrentModificationException}. 80: * 81: * @author Tom Tromey (tromey@redhat.com) 82: * @author Eric Blake (ebb9@email.byu.edu) 83: * @see System#identityHashCode(Object) 84: * @see Collection 85: * @see Map 86: * @see HashMap 87: * @see TreeMap 88: * @see LinkedHashMap 89: * @see WeakHashMap 90: * @since 1.4 91: * @status updated to 1.4 92: */ 93: public class IdentityHashMap<K,V> extends AbstractMap<K,V> 94: implements Map<K,V>, Serializable, Cloneable 95: { 96: /** The default capacity. */ 97: private static final int DEFAULT_CAPACITY = 21; 98: 99: /** 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: }