GNU Classpath (0.20) | |
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 extends AbstractMap 94: implements Map, Serializable, Cloneable 95: { 96: /** The default capacity. */ 97: private static final int DEFAULT_CAPACITY = 21; 98: 99: /** 100: * This object is used to mark deleted items. Package visible for use by 101: * nested classes. 102: */ 103: static final Object tombstone = new Object(); 104: 105: /** 106: * This object is used to mark empty slots. We need this because 107: * using null is ambiguous. Package visible for use by nested classes. 108: */ 109: static final Object emptyslot = new Object(); 110: 111: /** 112: * Compatible with JDK 1.4. 113: */ 114: private static final long serialVersionUID = 8188218128353913216L; 115: 116: /** 117: * The number of mappings in the table. Package visible for use by nested 118: * classes. 119: * @serial 120: */ 121: int size; 122: 123: /** 124: * The table itself. Package visible for use by nested classes. 125: */ 126: transient Object[] table; 127: 128: /** 129: * The number of structural modifications made so far. Package visible for 130: * use by nested classes. 131: */ 132: transient int modCount; 133: 134: /** 135: * The cache for {@link #entrySet()}. 136: */ 137: private transient Set entries; 138: 139: /** 140: * The threshold for rehashing, which is 75% of (table.length / 2). 141: */ 142: private transient int threshold; 143: 144: /** 145: * Create a new IdentityHashMap with the default capacity (21 entries). 146: */ 147: public IdentityHashMap() 148: { 149: this(DEFAULT_CAPACITY); 150: } 151: 152: /** 153: * Create a new IdentityHashMap with the indicated number of 154: * entries. If the number of elements added to this hash map 155: * exceeds this maximum, the map will grow itself; however, that 156: * incurs a performance penalty. 157: * 158: * @param max initial size 159: * @throws IllegalArgumentException if max is negative 160: */ 161: public IdentityHashMap(int max) 162: { 163: if (max < 0) 164: throw new IllegalArgumentException(); 165: // Need at least two slots, or hash() will break. 166: if (max < 2) 167: max = 2; 168: table = new Object[max << 1]; 169: Arrays.fill(table, emptyslot); 170: threshold = (max >> 2) * 3; 171: } 172: 173: /** 174: * Create a new IdentityHashMap whose contents are taken from the 175: * given Map. 176: * 177: * @param m The map whose elements are to be put in this map 178: * @throws NullPointerException if m is null 179: */ 180: public IdentityHashMap(Map m) 181: { 182: this(Math.max(m.size() << 1, DEFAULT_CAPACITY)); 183: putAll(m); 184: } 185: 186: /** 187: * Remove all mappings from this map. 188: */ 189: public void clear() 190: { 191: if (size != 0) 192: { 193: modCount++; 194: Arrays.fill(table, emptyslot); 195: size = 0; 196: } 197: } 198: 199: /** 200: * Creates a shallow copy where keys and values are not cloned. 201: */ 202: public Object clone() 203: { 204: try 205: { 206: IdentityHashMap copy = (IdentityHashMap) super.clone(); 207: copy.table = (Object[]) table.clone(); 208: copy.entries = null; // invalidate the cache 209: return copy; 210: } 211: catch (CloneNotSupportedException e) 212: { 213: // Can't happen. 214: return null; 215: } 216: } 217: 218: /** 219: * Tests whether the specified key is in this map. Unlike normal Maps, 220: * this test uses <code>entry == key</code> instead of 221: * <code>entry == null ? key == null : entry.equals(key)</code>. 222: * 223: * @param key the key to look for 224: * @return true if the key is contained in the map 225: * @see #containsValue(Object) 226: * @see #get(Object) 227: */ 228: public boolean containsKey(Object key) 229: { 230: return key == table[hash(key)]; 231: } 232: 233: /** 234: * Returns true if this HashMap contains the value. Unlike normal maps, 235: * this test uses <code>entry == value</code> instead of 236: * <code>entry == null ? value == null : entry.equals(value)</code>. 237: * 238: * @param value the value to search for in this HashMap 239: * @return true if at least one key maps to the value 240: * @see #containsKey(Object) 241: */ 242: public boolean containsValue(Object value) 243: { 244: for (int i = table.length - 1; i > 0; i -= 2) 245: if (table[i] == value) 246: return true; 247: return false; 248: } 249: 250: /** 251: * Returns a "set view" of this Map's entries. The set is backed by 252: * the Map, so changes in one show up in the other. The set supports 253: * element removal, but not element addition. 254: * <p> 255: * 256: * <em>The semantics of this set, and of its contained entries, are 257: * different from the contract of Set and Map.Entry in order to make 258: * IdentityHashMap work. This means that while you can compare these 259: * objects between IdentityHashMaps, comparing them with regular sets 260: * or entries is likely to have undefined behavior.</em> The entries 261: * in this set are reference-based, rather than the normal object 262: * equality. Therefore, <code>e1.equals(e2)</code> returns 263: * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>, 264: * and <code>e.hashCode()</code> returns 265: * <code>System.identityHashCode(e.getKey()) ^ 266: * System.identityHashCode(e.getValue())</code>. 267: * <p> 268: * 269: * Note that the iterators for all three views, from keySet(), entrySet(), 270: * and values(), traverse the Map in the same sequence. 271: * 272: * @return a set view of the entries 273: * @see #keySet() 274: * @see #values() 275: * @see Map.Entry 276: */ 277: public Set entrySet() 278: { 279: if (entries == null) 280: entries = new AbstractSet() 281: { 282: public int size() 283: { 284: return size; 285: } 286: 287: public Iterator iterator() 288: { 289: return new IdentityIterator(ENTRIES); 290: } 291: 292: public void clear() 293: { 294: IdentityHashMap.this.clear(); 295: } 296: 297: public boolean contains(Object o) 298: { 299: if (! (o instanceof Map.Entry)) 300: return false; 301: Map.Entry m = (Map.Entry) o; 302: return m.getValue() == table[hash(m.getKey()) + 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 = ((Map.Entry) o).getKey(); 315: int h = hash(key); 316: if (table[h] == key) 317: { 318: size--; 319: modCount++; 320: table[h] = tombstone; 321: table[h + 1] = tombstone; 322: return true; 323: } 324: return false; 325: } 326: }; 327: return entries; 328: } 329: 330: /** 331: * Compares two maps for equality. This returns true only if both maps 332: * have the same reference-identity comparisons. While this returns 333: * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map, 334: * this will not work with normal maps, since the entry set compares 335: * with == instead of .equals. 336: * 337: * @param o the object to compare to 338: * @return true if it is equal 339: */ 340: public boolean equals(Object o) 341: { 342: // Why did Sun specify this one? The superclass does the right thing. 343: return super.equals(o); 344: } 345: 346: /** 347: * Return the value in this Map associated with the supplied key, or 348: * <code>null</code> if the key maps to nothing. 349: * 350: * <p>NOTE: Since the value could also be null, you must use 351: * containsKey to see if this key actually maps to something. 352: * Unlike normal maps, this tests for the key with <code>entry == 353: * key</code> instead of <code>entry == null ? key == null : 354: * entry.equals(key)</code>. 355: * 356: * @param key the key for which to fetch an associated value 357: * @return what the key maps to, if present 358: * @see #put(Object, Object) 359: * @see #containsKey(Object) 360: */ 361: public Object get(Object key) 362: { 363: int h = hash(key); 364: return table[h] == key ? 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 == emptyslot || key == tombstone) 382: continue; 383: hash += (System.identityHashCode(key) 384: ^ System.identityHashCode(table[i + 1])); 385: } 386: return hash; 387: } 388: 389: /** 390: * Returns true if there are no key-value mappings currently in this Map 391: * @return <code>size() == 0</code> 392: */ 393: public boolean isEmpty() 394: { 395: return size == 0; 396: } 397: 398: /** 399: * Returns a "set view" of this Map's keys. The set is backed by the 400: * Map, so changes in one show up in the other. The set supports 401: * element removal, but not element addition. 402: * <p> 403: * 404: * <em>The semantics of this set are different from the contract of Set 405: * in order to make IdentityHashMap work. This means that while you can 406: * compare these objects between IdentityHashMaps, comparing them with 407: * regular sets is likely to have undefined behavior.</em> The hashCode 408: * of the set is the sum of the identity hash codes, instead of the 409: * regular hashCodes, and equality is determined by reference instead 410: * of by the equals method. 411: * <p> 412: * 413: * @return a set view of the keys 414: * @see #values() 415: * @see #entrySet() 416: */ 417: public Set keySet() 418: { 419: if (keys == null) 420: keys = new AbstractSet() 421: { 422: public int size() 423: { 424: return size; 425: } 426: 427: public Iterator iterator() 428: { 429: return new IdentityIterator(KEYS); 430: } 431: 432: public void clear() 433: { 434: IdentityHashMap.this.clear(); 435: } 436: 437: public boolean contains(Object o) 438: { 439: return containsKey(o); 440: } 441: 442: public int hashCode() 443: { 444: int hash = 0; 445: for (int i = table.length - 2; i >= 0; i -= 2) 446: { 447: Object key = table[i]; 448: if (key == emptyslot || key == tombstone) 449: continue; 450: hash += System.identityHashCode(key); 451: } 452: return hash; 453: 454: } 455: 456: public boolean remove(Object o) 457: { 458: int h = hash(o); 459: if (table[h] == o) 460: { 461: size--; 462: modCount++; 463: table[h] = tombstone; 464: table[h + 1] = tombstone; 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 Object put(Object key, Object value) 488: { 489: // Rehash if the load factor is too high. 490: if (size > threshold) 491: { 492: Object[] old = table; 493: // This isn't necessarily prime, but it is an odd number of key/value 494: // slots, which has a higher probability of fewer collisions. 495: table = new Object[(old.length * 2) + 2]; 496: Arrays.fill(table, emptyslot); 497: size = 0; 498: threshold = (table.length >>> 3) * 3; 499: 500: for (int i = old.length - 2; i >= 0; i -= 2) 501: { 502: Object oldkey = old[i]; 503: if (oldkey != tombstone && oldkey != emptyslot) 504: // Just use put. This isn't very efficient, but it is ok. 505: put(oldkey, old[i + 1]); 506: } 507: } 508: 509: int h = hash(key); 510: if (table[h] == key) 511: { 512: Object r = table[h + 1]; 513: table[h + 1] = value; 514: return r; 515: } 516: 517: // At this point, we add a new mapping. 518: modCount++; 519: size++; 520: table[h] = key; 521: table[h + 1] = value; 522: return null; 523: } 524: 525: /** 526: * Copies all of the mappings from the specified map to this. If a key 527: * is already in this map, its value is replaced. 528: * 529: * @param m the map to copy 530: * @throws NullPointerException if m is null 531: */ 532: public void putAll(Map m) 533: { 534: // Why did Sun specify this one? The superclass does the right thing. 535: super.putAll(m); 536: } 537: 538: /** 539: * Removes from the HashMap and returns the value which is mapped by 540: * the supplied key. If the key maps to nothing, then the HashMap 541: * remains unchanged, and <code>null</code> is returned. 542: * 543: * NOTE: Since the value could also be null, you must use 544: * containsKey to see if you are actually removing a mapping. 545: * Unlike normal maps, this tests for the key with <code>entry == 546: * key</code> instead of <code>entry == null ? key == null : 547: * entry.equals(key)</code>. 548: * 549: * @param key the key used to locate the value to remove 550: * @return whatever the key mapped to, if present 551: */ 552: public Object remove(Object key) 553: { 554: int h = hash(key); 555: if (table[h] == key) 556: { 557: modCount++; 558: size--; 559: Object r = table[h + 1]; 560: table[h] = tombstone; 561: table[h + 1] = tombstone; 562: return r; 563: } 564: return null; 565: } 566: 567: /** 568: * Returns the number of kay-value mappings currently in this Map 569: * @return the size 570: */ 571: public int size() 572: { 573: return size; 574: } 575: 576: /** 577: * Returns a "collection view" (or "bag view") of this Map's values. 578: * The collection is backed by the Map, so changes in one show up 579: * in the other. The collection supports element removal, but not element 580: * addition. 581: * <p> 582: * 583: * <em>The semantics of this set are different from the contract of 584: * Collection in order to make IdentityHashMap work. This means that 585: * while you can compare these objects between IdentityHashMaps, comparing 586: * them with regular sets is likely to have undefined behavior.</em> 587: * Likewise, contains and remove go by == instead of equals(). 588: * <p> 589: * 590: * @return a bag view of the values 591: * @see #keySet() 592: * @see #entrySet() 593: */ 594: public Collection values() 595: { 596: if (values == null) 597: values = new AbstractCollection() 598: { 599: public int size() 600: { 601: return size; 602: } 603: 604: public Iterator iterator() 605: { 606: return new IdentityIterator(VALUES); 607: } 608: 609: public void clear() 610: { 611: IdentityHashMap.this.clear(); 612: } 613: 614: public boolean remove(Object o) 615: { 616: for (int i = table.length - 1; i > 0; i -= 2) 617: if (table[i] == o) 618: { 619: modCount++; 620: table[i - 1] = tombstone; 621: table[i] = tombstone; 622: size--; 623: return true; 624: } 625: return false; 626: } 627: }; 628: return values; 629: } 630: 631: /** 632: * Helper method which computes the hash code, then traverses the table 633: * until it finds the key, or the spot where the key would go. 634: * 635: * @param key the key to check 636: * @return the index where the key belongs 637: * @see #IdentityHashMap(int) 638: * @see #put(Object, Object) 639: */ 640: // Package visible for use by nested classes. 641: int hash(Object key) 642: { 643: // Implementation note: it is feasible for the table to have no 644: // emptyslots, if it is full with entries and tombstones, so we must 645: // remember where we started. If we encounter the key or an emptyslot, 646: // we are done. If we encounter a tombstone, the key may still be in 647: // the array. If we don't encounter the key, we use the first emptyslot 648: // or tombstone we encountered as the location where the key would go. 649: // By requiring at least 2 key/value slots, and rehashing at 75% 650: // capacity, we guarantee that there will always be either an emptyslot 651: // or a tombstone somewhere in the table. 652: int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1; 653: int del = -1; 654: int save = h; 655: 656: do 657: { 658: if (table[h] == key) 659: return h; 660: if (table[h] == emptyslot) 661: break; 662: if (table[h] == tombstone && del < 0) 663: del = h; 664: h -= 2; 665: if (h < 0) 666: h = table.length - 2; 667: } 668: while (h != save); 669: 670: return del < 0 ? h : del; 671: } 672: 673: /** 674: * This class allows parameterized iteration over IdentityHashMaps. Based 675: * on its construction, it returns the key or value of a mapping, or 676: * creates the appropriate Map.Entry object with the correct fail-fast 677: * semantics and identity comparisons. 678: * 679: * @author Tom Tromey (tromey@redhat.com) 680: * @author Eric Blake (ebb9@email.byu.edu) 681: */ 682: private class IdentityIterator implements Iterator 683: { 684: /** 685: * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 686: * or {@link #ENTRIES}. 687: */ 688: final int type; 689: /** The number of modifications to the backing Map that we know about. */ 690: int knownMod = modCount; 691: /** The number of elements remaining to be returned by next(). */ 692: int count = size; 693: /** Location in the table. */ 694: int loc = table.length; 695: 696: /** 697: * Construct a new Iterator with the supplied type. 698: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 699: */ 700: IdentityIterator(int type) 701: { 702: this.type = type; 703: } 704: 705: /** 706: * Returns true if the Iterator has more elements. 707: * @return true if there are more elements 708: * @throws ConcurrentModificationException if the Map was modified 709: */ 710: public boolean hasNext() 711: { 712: if (knownMod != modCount) 713: throw new ConcurrentModificationException(); 714: return count > 0; 715: } 716: 717: /** 718: * Returns the next element in the Iterator's sequential view. 719: * @return the next element 720: * @throws ConcurrentModificationException if the Map was modified 721: * @throws NoSuchElementException if there is none 722: */ 723: public Object next() 724: { 725: if (knownMod != modCount) 726: throw new ConcurrentModificationException(); 727: if (count == 0) 728: throw new NoSuchElementException(); 729: count--; 730: 731: Object key; 732: do 733: { 734: loc -= 2; 735: key = table[loc]; 736: } 737: while (key == emptyslot || key == tombstone); 738: 739: return type == KEYS ? key : (type == VALUES ? table[loc + 1] 740: : new IdentityEntry(loc)); 741: } 742: 743: /** 744: * Removes from the backing Map the last element which was fetched 745: * with the <code>next()</code> method. 746: * 747: * @throws ConcurrentModificationException if the Map was modified 748: * @throws IllegalStateException if called when there is no last element 749: */ 750: public void remove() 751: { 752: if (knownMod != modCount) 753: throw new ConcurrentModificationException(); 754: if (loc == table.length || table[loc] == tombstone) 755: throw new IllegalStateException(); 756: modCount++; 757: size--; 758: table[loc] = tombstone; 759: table[loc + 1] = tombstone; 760: knownMod++; 761: } 762: } // class IdentityIterator 763: 764: /** 765: * This class provides Map.Entry objects for IdentityHashMaps. The entry 766: * is fail-fast, and will throw a ConcurrentModificationException if 767: * the underlying map is modified, or if remove is called on the iterator 768: * that generated this object. It is identity based, so it violates 769: * the general contract of Map.Entry, and is probably unsuitable for 770: * comparison to normal maps; but it works among other IdentityHashMaps. 771: * 772: * @author Eric Blake (ebb9@email.byu.edu) 773: */ 774: private final class IdentityEntry implements Map.Entry 775: { 776: /** The location of this entry. */ 777: final int loc; 778: /** The number of modifications to the backing Map that we know about. */ 779: final int knownMod = modCount; 780: 781: /** 782: * Constructs the Entry. 783: * 784: * @param loc the location of this entry in table 785: */ 786: IdentityEntry(int loc) 787: { 788: this.loc = loc; 789: } 790: 791: /** 792: * Compares the specified object with this entry, using identity 793: * semantics. Note that this can lead to undefined results with 794: * Entry objects created by normal maps. 795: * 796: * @param o the object to compare 797: * @return true if it is equal 798: * @throws ConcurrentModificationException if the entry was invalidated 799: * by modifying the Map or calling Iterator.remove() 800: */ 801: public boolean equals(Object o) 802: { 803: if (knownMod != modCount || table[loc] == tombstone) 804: throw new ConcurrentModificationException(); 805: if (! (o instanceof Map.Entry)) 806: return false; 807: Map.Entry e = (Map.Entry) o; 808: return table[loc] == e.getKey() && table[loc + 1] == e.getValue(); 809: } 810: 811: /** 812: * Returns the key of this entry. 813: * 814: * @return the key 815: * @throws ConcurrentModificationException if the entry was invalidated 816: * by modifying the Map or calling Iterator.remove() 817: */ 818: public Object getKey() 819: { 820: if (knownMod != modCount || table[loc] == tombstone) 821: throw new ConcurrentModificationException(); 822: return table[loc]; 823: } 824: 825: /** 826: * Returns the value of this entry. 827: * 828: * @return the value 829: * @throws ConcurrentModificationException if the entry was invalidated 830: * by modifying the Map or calling Iterator.remove() 831: */ 832: public Object getValue() 833: { 834: if (knownMod != modCount || table[loc] == tombstone) 835: throw new ConcurrentModificationException(); 836: return table[loc + 1]; 837: } 838: 839: /** 840: * Returns the hashcode of the entry, using identity semantics. 841: * Note that this can lead to undefined results with Entry objects 842: * created by normal maps. 843: * 844: * @return the hash code 845: * @throws ConcurrentModificationException if the entry was invalidated 846: * by modifying the Map or calling Iterator.remove() 847: */ 848: public int hashCode() 849: { 850: if (knownMod != modCount || table[loc] == tombstone) 851: throw new ConcurrentModificationException(); 852: return (System.identityHashCode(table[loc]) 853: ^ System.identityHashCode(table[loc + 1])); 854: } 855: 856: /** 857: * Replaces the value of this mapping, and returns the old value. 858: * 859: * @param value the new value 860: * @return the old value 861: * @throws ConcurrentModificationException if the entry was invalidated 862: * by modifying the Map or calling Iterator.remove() 863: */ 864: public Object setValue(Object value) 865: { 866: if (knownMod != modCount || table[loc] == tombstone) 867: throw new ConcurrentModificationException(); 868: Object r = table[loc + 1]; 869: table[loc + 1] = value; 870: return r; 871: } 872: 873: /** 874: * This provides a string representation of the entry. It is of the form 875: * "key=value", where string concatenation is used on key and value. 876: * 877: * @return the string representation 878: * @throws ConcurrentModificationException if the entry was invalidated 879: * by modifying the Map or calling Iterator.remove() 880: */ 881: public String toString() 882: { 883: if (knownMod != modCount || table[loc] == tombstone) 884: throw new ConcurrentModificationException(); 885: return table[loc] + "=" + table[loc + 1]; 886: } 887: } // class IdentityEntry 888: 889: /** 890: * Reads the object from a serial stream. 891: * 892: * @param s the stream to read from 893: * @throws ClassNotFoundException if the underlying stream fails 894: * @throws IOException if the underlying stream fails 895: * @serialData expects the size (int), followed by that many key (Object) 896: * and value (Object) pairs, with the pairs in no particular 897: * order 898: */ 899: private void readObject(ObjectInputStream s) 900: throws IOException, ClassNotFoundException 901: { 902: s.defaultReadObject(); 903: 904: int num = s.readInt(); 905: table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1]; 906: // Read key/value pairs. 907: while (--num >= 0) 908: put(s.readObject(), s.readObject()); 909: } 910: 911: /** 912: * Writes the object to a serial stream. 913: * 914: * @param s the stream to write to 915: * @throws IOException if the underlying stream fails 916: * @serialData outputs the size (int), followed by that many key (Object) 917: * and value (Object) pairs, with the pairs in no particular 918: * order 919: */ 920: private void writeObject(ObjectOutputStream s) 921: throws IOException 922: { 923: s.defaultWriteObject(); 924: s.writeInt(size); 925: for (int i = table.length - 2; i >= 0; i -= 2) 926: { 927: Object key = table[i]; 928: if (key != tombstone && key != emptyslot) 929: { 930: s.writeObject(key); 931: s.writeObject(table[i + 1]); 932: } 933: } 934: } 935: }
GNU Classpath (0.20) |