| /* IdentityHashMap.java -- a class providing a hashtable data structure, |
| mapping Object --> Object, which uses object identity for hashing. |
| Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. |
| |
| This file is part of GNU Classpath. |
| |
| GNU Classpath is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GNU Classpath is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GNU Classpath; see the file COPYING. If not, write to the |
| Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
| 02110-1301 USA. |
| |
| Linking this library statically or dynamically with other modules is |
| making a combined work based on this library. Thus, the terms and |
| conditions of the GNU General Public License cover the whole |
| combination. |
| |
| As a special exception, the copyright holders of this library give you |
| permission to link this library with independent modules to produce an |
| executable, regardless of the license terms of these independent |
| modules, and to copy and distribute the resulting executable under |
| terms of your choice, provided that you also meet, for each linked |
| independent module, the terms and conditions of the license of that |
| module. An independent module is a module which is not derived from |
| or based on this library. If you modify this library, you may extend |
| this exception to your version of the library, but you are not |
| obligated to do so. If you do not wish to do so, delete this |
| exception statement from your version. */ |
| |
| package java.util; |
| |
| import java.io.IOException; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.io.Serializable; |
| |
| /** |
| * This class provides a hashtable-backed implementation of the |
| * Map interface, but uses object identity to do its hashing. In fact, |
| * it uses object identity for comparing values, as well. It uses a |
| * linear-probe hash table, which may have faster performance |
| * than the chaining employed by HashMap. |
| * <p> |
| * |
| * <em>WARNING: This is not a general purpose map. Because it uses |
| * System.identityHashCode and ==, instead of hashCode and equals, for |
| * comparison, it violated Map's general contract, and may cause |
| * undefined behavior when compared to other maps which are not |
| * IdentityHashMaps. This is designed only for the rare cases when |
| * identity semantics are needed.</em> An example use is |
| * topology-preserving graph transformations, such as deep cloning, |
| * or as proxy object mapping such as in debugging. |
| * <p> |
| * |
| * This map permits <code>null</code> keys and values, and does not |
| * guarantee that elements will stay in the same order over time. The |
| * basic operations (<code>get</code> and <code>put</code>) take |
| * constant time, provided System.identityHashCode is decent. You can |
| * tune the behavior by specifying the expected maximum size. As more |
| * elements are added, the map may need to allocate a larger table, |
| * which can be expensive. |
| * <p> |
| * |
| * This implementation is unsynchronized. If you want multi-thread |
| * access to be consistent, you must synchronize it, perhaps by using |
| * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>. |
| * The iterators are <i>fail-fast</i>, meaning that a structural modification |
| * made to the map outside of an iterator's remove method cause the |
| * iterator, and in the case of the entrySet, the Map.Entry, to |
| * fail with a {@link ConcurrentModificationException}. |
| * |
| * @author Tom Tromey (tromey@redhat.com) |
| * @author Eric Blake (ebb9@email.byu.edu) |
| * @see System#identityHashCode(Object) |
| * @see Collection |
| * @see Map |
| * @see HashMap |
| * @see TreeMap |
| * @see LinkedHashMap |
| * @see WeakHashMap |
| * @since 1.4 |
| * @status updated to 1.4 |
| */ |
| public class IdentityHashMap extends AbstractMap |
| implements Map, Serializable, Cloneable |
| { |
| /** The default capacity. */ |
| private static final int DEFAULT_CAPACITY = 21; |
| |
| /** |
| * This object is used to mark deleted items. Package visible for use by |
| * nested classes. |
| */ |
| static final Object tombstone = new Object(); |
| |
| /** |
| * This object is used to mark empty slots. We need this because |
| * using null is ambiguous. Package visible for use by nested classes. |
| */ |
| static final Object emptyslot = new Object(); |
| |
| /** |
| * Compatible with JDK 1.4. |
| */ |
| private static final long serialVersionUID = 8188218128353913216L; |
| |
| /** |
| * The number of mappings in the table. Package visible for use by nested |
| * classes. |
| * @serial |
| */ |
| int size; |
| |
| /** |
| * The table itself. Package visible for use by nested classes. |
| */ |
| transient Object[] table; |
| |
| /** |
| * The number of structural modifications made so far. Package visible for |
| * use by nested classes. |
| */ |
| transient int modCount; |
| |
| /** |
| * The cache for {@link #entrySet()}. |
| */ |
| private transient Set entries; |
| |
| /** |
| * The threshold for rehashing, which is 75% of (table.length / 2). |
| */ |
| private transient int threshold; |
| |
| /** |
| * Create a new IdentityHashMap with the default capacity (21 entries). |
| */ |
| public IdentityHashMap() |
| { |
| this(DEFAULT_CAPACITY); |
| } |
| |
| /** |
| * Create a new IdentityHashMap with the indicated number of |
| * entries. If the number of elements added to this hash map |
| * exceeds this maximum, the map will grow itself; however, that |
| * incurs a performance penalty. |
| * |
| * @param max initial size |
| * @throws IllegalArgumentException if max is negative |
| */ |
| public IdentityHashMap(int max) |
| { |
| if (max < 0) |
| throw new IllegalArgumentException(); |
| // Need at least two slots, or hash() will break. |
| if (max < 2) |
| max = 2; |
| table = new Object[max << 1]; |
| Arrays.fill(table, emptyslot); |
| threshold = (max >> 2) * 3; |
| } |
| |
| /** |
| * Create a new IdentityHashMap whose contents are taken from the |
| * given Map. |
| * |
| * @param m The map whose elements are to be put in this map |
| * @throws NullPointerException if m is null |
| */ |
| public IdentityHashMap(Map m) |
| { |
| this(Math.max(m.size() << 1, DEFAULT_CAPACITY)); |
| putAll(m); |
| } |
| |
| /** |
| * Remove all mappings from this map. |
| */ |
| public void clear() |
| { |
| if (size != 0) |
| { |
| modCount++; |
| Arrays.fill(table, emptyslot); |
| size = 0; |
| } |
| } |
| |
| /** |
| * Creates a shallow copy where keys and values are not cloned. |
| */ |
| public Object clone() |
| { |
| try |
| { |
| IdentityHashMap copy = (IdentityHashMap) super.clone(); |
| copy.table = (Object[]) table.clone(); |
| copy.entries = null; // invalidate the cache |
| return copy; |
| } |
| catch (CloneNotSupportedException e) |
| { |
| // Can't happen. |
| return null; |
| } |
| } |
| |
| /** |
| * Tests whether the specified key is in this map. Unlike normal Maps, |
| * this test uses <code>entry == key</code> instead of |
| * <code>entry == null ? key == null : entry.equals(key)</code>. |
| * |
| * @param key the key to look for |
| * @return true if the key is contained in the map |
| * @see #containsValue(Object) |
| * @see #get(Object) |
| */ |
| public boolean containsKey(Object key) |
| { |
| return key == table[hash(key)]; |
| } |
| |
| /** |
| * Returns true if this HashMap contains the value. Unlike normal maps, |
| * this test uses <code>entry == value</code> instead of |
| * <code>entry == null ? value == null : entry.equals(value)</code>. |
| * |
| * @param value the value to search for in this HashMap |
| * @return true if at least one key maps to the value |
| * @see #containsKey(Object) |
| */ |
| public boolean containsValue(Object value) |
| { |
| for (int i = table.length - 1; i > 0; i -= 2) |
| if (table[i] == value) |
| return true; |
| return false; |
| } |
| |
| /** |
| * Returns a "set view" of this Map's entries. The set is backed by |
| * the Map, so changes in one show up in the other. The set supports |
| * element removal, but not element addition. |
| * <p> |
| * |
| * <em>The semantics of this set, and of its contained entries, are |
| * different from the contract of Set and Map.Entry in order to make |
| * IdentityHashMap work. This means that while you can compare these |
| * objects between IdentityHashMaps, comparing them with regular sets |
| * or entries is likely to have undefined behavior.</em> The entries |
| * in this set are reference-based, rather than the normal object |
| * equality. Therefore, <code>e1.equals(e2)</code> returns |
| * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>, |
| * and <code>e.hashCode()</code> returns |
| * <code>System.identityHashCode(e.getKey()) ^ |
| * System.identityHashCode(e.getValue())</code>. |
| * <p> |
| * |
| * Note that the iterators for all three views, from keySet(), entrySet(), |
| * and values(), traverse the Map in the same sequence. |
| * |
| * @return a set view of the entries |
| * @see #keySet() |
| * @see #values() |
| * @see Map.Entry |
| */ |
| public Set entrySet() |
| { |
| if (entries == null) |
| entries = new AbstractSet() |
| { |
| public int size() |
| { |
| return size; |
| } |
| |
| public Iterator iterator() |
| { |
| return new IdentityIterator(ENTRIES); |
| } |
| |
| public void clear() |
| { |
| IdentityHashMap.this.clear(); |
| } |
| |
| public boolean contains(Object o) |
| { |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Map.Entry m = (Map.Entry) o; |
| return m.getValue() == table[hash(m.getKey()) + 1]; |
| } |
| |
| public int hashCode() |
| { |
| return IdentityHashMap.this.hashCode(); |
| } |
| |
| public boolean remove(Object o) |
| { |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Object key = ((Map.Entry) o).getKey(); |
| int h = hash(key); |
| if (table[h] == key) |
| { |
| size--; |
| modCount++; |
| table[h] = tombstone; |
| table[h + 1] = tombstone; |
| return true; |
| } |
| return false; |
| } |
| }; |
| return entries; |
| } |
| |
| /** |
| * Compares two maps for equality. This returns true only if both maps |
| * have the same reference-identity comparisons. While this returns |
| * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map, |
| * this will not work with normal maps, since the entry set compares |
| * with == instead of .equals. |
| * |
| * @param o the object to compare to |
| * @return true if it is equal |
| */ |
| public boolean equals(Object o) |
| { |
| // Why did Sun specify this one? The superclass does the right thing. |
| return super.equals(o); |
| } |
| |
| /** |
| * Return the value in this Map associated with the supplied key, or |
| * <code>null</code> if the key maps to nothing. |
| * |
| * <p>NOTE: Since the value could also be null, you must use |
| * containsKey to see if this key actually maps to something. |
| * Unlike normal maps, this tests for the key with <code>entry == |
| * key</code> instead of <code>entry == null ? key == null : |
| * entry.equals(key)</code>. |
| * |
| * @param key the key for which to fetch an associated value |
| * @return what the key maps to, if present |
| * @see #put(Object, Object) |
| * @see #containsKey(Object) |
| */ |
| public Object get(Object key) |
| { |
| int h = hash(key); |
| return table[h] == key ? table[h + 1] : null; |
| } |
| |
| /** |
| * Returns the hashcode of this map. This guarantees that two |
| * IdentityHashMaps that compare with equals() will have the same hash code, |
| * but may break with comparison to normal maps since it uses |
| * System.identityHashCode() instead of hashCode(). |
| * |
| * @return the hash code |
| */ |
| public int hashCode() |
| { |
| int hash = 0; |
| for (int i = table.length - 2; i >= 0; i -= 2) |
| { |
| Object key = table[i]; |
| if (key == emptyslot || key == tombstone) |
| continue; |
| hash += (System.identityHashCode(key) |
| ^ System.identityHashCode(table[i + 1])); |
| } |
| return hash; |
| } |
| |
| /** |
| * Returns true if there are no key-value mappings currently in this Map |
| * @return <code>size() == 0</code> |
| */ |
| public boolean isEmpty() |
| { |
| return size == 0; |
| } |
| |
| /** |
| * Returns a "set view" of this Map's keys. The set is backed by the |
| * Map, so changes in one show up in the other. The set supports |
| * element removal, but not element addition. |
| * <p> |
| * |
| * <em>The semantics of this set are different from the contract of Set |
| * in order to make IdentityHashMap work. This means that while you can |
| * compare these objects between IdentityHashMaps, comparing them with |
| * regular sets is likely to have undefined behavior.</em> The hashCode |
| * of the set is the sum of the identity hash codes, instead of the |
| * regular hashCodes, and equality is determined by reference instead |
| * of by the equals method. |
| * <p> |
| * |
| * @return a set view of the keys |
| * @see #values() |
| * @see #entrySet() |
| */ |
| public Set keySet() |
| { |
| if (keys == null) |
| keys = new AbstractSet() |
| { |
| public int size() |
| { |
| return size; |
| } |
| |
| public Iterator iterator() |
| { |
| return new IdentityIterator(KEYS); |
| } |
| |
| public void clear() |
| { |
| IdentityHashMap.this.clear(); |
| } |
| |
| public boolean contains(Object o) |
| { |
| return containsKey(o); |
| } |
| |
| public int hashCode() |
| { |
| int hash = 0; |
| for (int i = table.length - 2; i >= 0; i -= 2) |
| { |
| Object key = table[i]; |
| if (key == emptyslot || key == tombstone) |
| continue; |
| hash += System.identityHashCode(key); |
| } |
| return hash; |
| |
| } |
| |
| public boolean remove(Object o) |
| { |
| int h = hash(o); |
| if (table[h] == o) |
| { |
| size--; |
| modCount++; |
| table[h] = tombstone; |
| table[h + 1] = tombstone; |
| return true; |
| } |
| return false; |
| } |
| }; |
| return keys; |
| } |
| |
| /** |
| * Puts the supplied value into the Map, mapped by the supplied key. |
| * The value may be retrieved by any object which <code>equals()</code> |
| * this key. NOTE: Since the prior value could also be null, you must |
| * first use containsKey if you want to see if you are replacing the |
| * key's mapping. Unlike normal maps, this tests for the key |
| * with <code>entry == key</code> instead of |
| * <code>entry == null ? key == null : entry.equals(key)</code>. |
| * |
| * @param key the key used to locate the value |
| * @param value the value to be stored in the HashMap |
| * @return the prior mapping of the key, or null if there was none |
| * @see #get(Object) |
| */ |
| public Object put(Object key, Object value) |
| { |
| // Rehash if the load factor is too high. |
| if (size > threshold) |
| { |
| Object[] old = table; |
| // This isn't necessarily prime, but it is an odd number of key/value |
| // slots, which has a higher probability of fewer collisions. |
| table = new Object[(old.length * 2) + 2]; |
| Arrays.fill(table, emptyslot); |
| size = 0; |
| threshold = (table.length >>> 3) * 3; |
| |
| for (int i = old.length - 2; i >= 0; i -= 2) |
| { |
| Object oldkey = old[i]; |
| if (oldkey != tombstone && oldkey != emptyslot) |
| // Just use put. This isn't very efficient, but it is ok. |
| put(oldkey, old[i + 1]); |
| } |
| } |
| |
| int h = hash(key); |
| if (table[h] == key) |
| { |
| Object r = table[h + 1]; |
| table[h + 1] = value; |
| return r; |
| } |
| |
| // At this point, we add a new mapping. |
| modCount++; |
| size++; |
| table[h] = key; |
| table[h + 1] = value; |
| return null; |
| } |
| |
| /** |
| * Copies all of the mappings from the specified map to this. If a key |
| * is already in this map, its value is replaced. |
| * |
| * @param m the map to copy |
| * @throws NullPointerException if m is null |
| */ |
| public void putAll(Map m) |
| { |
| // Why did Sun specify this one? The superclass does the right thing. |
| super.putAll(m); |
| } |
| |
| /** |
| * Removes from the HashMap and returns the value which is mapped by |
| * the supplied key. If the key maps to nothing, then the HashMap |
| * remains unchanged, and <code>null</code> is returned. |
| * |
| * NOTE: Since the value could also be null, you must use |
| * containsKey to see if you are actually removing a mapping. |
| * Unlike normal maps, this tests for the key with <code>entry == |
| * key</code> instead of <code>entry == null ? key == null : |
| * entry.equals(key)</code>. |
| * |
| * @param key the key used to locate the value to remove |
| * @return whatever the key mapped to, if present |
| */ |
| public Object remove(Object key) |
| { |
| int h = hash(key); |
| if (table[h] == key) |
| { |
| modCount++; |
| size--; |
| Object r = table[h + 1]; |
| table[h] = tombstone; |
| table[h + 1] = tombstone; |
| return r; |
| } |
| return null; |
| } |
| |
| /** |
| * Returns the number of kay-value mappings currently in this Map |
| * @return the size |
| */ |
| public int size() |
| { |
| return size; |
| } |
| |
| /** |
| * Returns a "collection view" (or "bag view") of this Map's values. |
| * The collection is backed by the Map, so changes in one show up |
| * in the other. The collection supports element removal, but not element |
| * addition. |
| * <p> |
| * |
| * <em>The semantics of this set are different from the contract of |
| * Collection in order to make IdentityHashMap work. This means that |
| * while you can compare these objects between IdentityHashMaps, comparing |
| * them with regular sets is likely to have undefined behavior.</em> |
| * Likewise, contains and remove go by == instead of equals(). |
| * <p> |
| * |
| * @return a bag view of the values |
| * @see #keySet() |
| * @see #entrySet() |
| */ |
| public Collection values() |
| { |
| if (values == null) |
| values = new AbstractCollection() |
| { |
| public int size() |
| { |
| return size; |
| } |
| |
| public Iterator iterator() |
| { |
| return new IdentityIterator(VALUES); |
| } |
| |
| public void clear() |
| { |
| IdentityHashMap.this.clear(); |
| } |
| |
| public boolean remove(Object o) |
| { |
| for (int i = table.length - 1; i > 0; i -= 2) |
| if (table[i] == o) |
| { |
| modCount++; |
| table[i - 1] = tombstone; |
| table[i] = tombstone; |
| size--; |
| return true; |
| } |
| return false; |
| } |
| }; |
| return values; |
| } |
| |
| /** |
| * Helper method which computes the hash code, then traverses the table |
| * until it finds the key, or the spot where the key would go. |
| * |
| * @param key the key to check |
| * @return the index where the key belongs |
| * @see #IdentityHashMap(int) |
| * @see #put(Object, Object) |
| */ |
| // Package visible for use by nested classes. |
| int hash(Object key) |
| { |
| // Implementation note: it is feasible for the table to have no |
| // emptyslots, if it is full with entries and tombstones, so we must |
| // remember where we started. If we encounter the key or an emptyslot, |
| // we are done. If we encounter a tombstone, the key may still be in |
| // the array. If we don't encounter the key, we use the first emptyslot |
| // or tombstone we encountered as the location where the key would go. |
| // By requiring at least 2 key/value slots, and rehashing at 75% |
| // capacity, we guarantee that there will always be either an emptyslot |
| // or a tombstone somewhere in the table. |
| int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1; |
| int del = -1; |
| int save = h; |
| |
| do |
| { |
| if (table[h] == key) |
| return h; |
| if (table[h] == emptyslot) |
| break; |
| if (table[h] == tombstone && del < 0) |
| del = h; |
| h -= 2; |
| if (h < 0) |
| h = table.length - 2; |
| } |
| while (h != save); |
| |
| return del < 0 ? h : del; |
| } |
| |
| /** |
| * This class allows parameterized iteration over IdentityHashMaps. Based |
| * on its construction, it returns the key or value of a mapping, or |
| * creates the appropriate Map.Entry object with the correct fail-fast |
| * semantics and identity comparisons. |
| * |
| * @author Tom Tromey (tromey@redhat.com) |
| * @author Eric Blake (ebb9@email.byu.edu) |
| */ |
| private class IdentityIterator implements Iterator |
| { |
| /** |
| * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, |
| * or {@link #ENTRIES}. |
| */ |
| final int type; |
| /** The number of modifications to the backing Map that we know about. */ |
| int knownMod = modCount; |
| /** The number of elements remaining to be returned by next(). */ |
| int count = size; |
| /** Location in the table. */ |
| int loc = table.length; |
| |
| /** |
| * Construct a new Iterator with the supplied type. |
| * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} |
| */ |
| IdentityIterator(int type) |
| { |
| this.type = type; |
| } |
| |
| /** |
| * Returns true if the Iterator has more elements. |
| * @return true if there are more elements |
| */ |
| public boolean hasNext() |
| { |
| return count > 0; |
| } |
| |
| /** |
| * Returns the next element in the Iterator's sequential view. |
| * @return the next element |
| * @throws ConcurrentModificationException if the Map was modified |
| * @throws NoSuchElementException if there is none |
| */ |
| public Object next() |
| { |
| if (knownMod != modCount) |
| throw new ConcurrentModificationException(); |
| if (count == 0) |
| throw new NoSuchElementException(); |
| count--; |
| |
| Object key; |
| do |
| { |
| loc -= 2; |
| key = table[loc]; |
| } |
| while (key == emptyslot || key == tombstone); |
| |
| return type == KEYS ? key : (type == VALUES ? table[loc + 1] |
| : new IdentityEntry(loc)); |
| } |
| |
| /** |
| * Removes from the backing Map the last element which was fetched |
| * with the <code>next()</code> method. |
| * |
| * @throws ConcurrentModificationException if the Map was modified |
| * @throws IllegalStateException if called when there is no last element |
| */ |
| public void remove() |
| { |
| if (knownMod != modCount) |
| throw new ConcurrentModificationException(); |
| if (loc == table.length || table[loc] == tombstone) |
| throw new IllegalStateException(); |
| modCount++; |
| size--; |
| table[loc] = tombstone; |
| table[loc + 1] = tombstone; |
| knownMod++; |
| } |
| } // class IdentityIterator |
| |
| /** |
| * This class provides Map.Entry objects for IdentityHashMaps. The entry |
| * is fail-fast, and will throw a ConcurrentModificationException if |
| * the underlying map is modified, or if remove is called on the iterator |
| * that generated this object. It is identity based, so it violates |
| * the general contract of Map.Entry, and is probably unsuitable for |
| * comparison to normal maps; but it works among other IdentityHashMaps. |
| * |
| * @author Eric Blake (ebb9@email.byu.edu) |
| */ |
| private final class IdentityEntry implements Map.Entry |
| { |
| /** The location of this entry. */ |
| final int loc; |
| /** The number of modifications to the backing Map that we know about. */ |
| final int knownMod = modCount; |
| |
| /** |
| * Constructs the Entry. |
| * |
| * @param loc the location of this entry in table |
| */ |
| IdentityEntry(int loc) |
| { |
| this.loc = loc; |
| } |
| |
| /** |
| * Compares the specified object with this entry, using identity |
| * semantics. Note that this can lead to undefined results with |
| * Entry objects created by normal maps. |
| * |
| * @param o the object to compare |
| * @return true if it is equal |
| * @throws ConcurrentModificationException if the entry was invalidated |
| * by modifying the Map or calling Iterator.remove() |
| */ |
| public boolean equals(Object o) |
| { |
| if (knownMod != modCount || table[loc] == tombstone) |
| throw new ConcurrentModificationException(); |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Map.Entry e = (Map.Entry) o; |
| return table[loc] == e.getKey() && table[loc + 1] == e.getValue(); |
| } |
| |
| /** |
| * Returns the key of this entry. |
| * |
| * @return the key |
| * @throws ConcurrentModificationException if the entry was invalidated |
| * by modifying the Map or calling Iterator.remove() |
| */ |
| public Object getKey() |
| { |
| if (knownMod != modCount || table[loc] == tombstone) |
| throw new ConcurrentModificationException(); |
| return table[loc]; |
| } |
| |
| /** |
| * Returns the value of this entry. |
| * |
| * @return the value |
| * @throws ConcurrentModificationException if the entry was invalidated |
| * by modifying the Map or calling Iterator.remove() |
| */ |
| public Object getValue() |
| { |
| if (knownMod != modCount || table[loc] == tombstone) |
| throw new ConcurrentModificationException(); |
| return table[loc + 1]; |
| } |
| |
| /** |
| * Returns the hashcode of the entry, using identity semantics. |
| * Note that this can lead to undefined results with Entry objects |
| * created by normal maps. |
| * |
| * @return the hash code |
| * @throws ConcurrentModificationException if the entry was invalidated |
| * by modifying the Map or calling Iterator.remove() |
| */ |
| public int hashCode() |
| { |
| if (knownMod != modCount || table[loc] == tombstone) |
| throw new ConcurrentModificationException(); |
| return (System.identityHashCode(table[loc]) |
| ^ System.identityHashCode(table[loc + 1])); |
| } |
| |
| /** |
| * Replaces the value of this mapping, and returns the old value. |
| * |
| * @param value the new value |
| * @return the old value |
| * @throws ConcurrentModificationException if the entry was invalidated |
| * by modifying the Map or calling Iterator.remove() |
| */ |
| public Object setValue(Object value) |
| { |
| if (knownMod != modCount || table[loc] == tombstone) |
| throw new ConcurrentModificationException(); |
| Object r = table[loc + 1]; |
| table[loc + 1] = value; |
| return r; |
| } |
| |
| /** |
| * This provides a string representation of the entry. It is of the form |
| * "key=value", where string concatenation is used on key and value. |
| * |
| * @return the string representation |
| * @throws ConcurrentModificationException if the entry was invalidated |
| * by modifying the Map or calling Iterator.remove() |
| */ |
| public String toString() |
| { |
| if (knownMod != modCount || table[loc] == tombstone) |
| throw new ConcurrentModificationException(); |
| return table[loc] + "=" + table[loc + 1]; |
| } |
| } // class IdentityEntry |
| |
| /** |
| * Reads the object from a serial stream. |
| * |
| * @param s the stream to read from |
| * @throws ClassNotFoundException if the underlying stream fails |
| * @throws IOException if the underlying stream fails |
| * @serialData expects the size (int), followed by that many key (Object) |
| * and value (Object) pairs, with the pairs in no particular |
| * order |
| */ |
| private void readObject(ObjectInputStream s) |
| throws IOException, ClassNotFoundException |
| { |
| s.defaultReadObject(); |
| |
| int num = s.readInt(); |
| table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1]; |
| // Read key/value pairs. |
| while (--num >= 0) |
| put(s.readObject(), s.readObject()); |
| } |
| |
| /** |
| * Writes the object to a serial stream. |
| * |
| * @param s the stream to write to |
| * @throws IOException if the underlying stream fails |
| * @serialData outputs the size (int), followed by that many key (Object) |
| * and value (Object) pairs, with the pairs in no particular |
| * order |
| */ |
| private void writeObject(ObjectOutputStream s) |
| throws IOException |
| { |
| s.defaultWriteObject(); |
| s.writeInt(size); |
| for (int i = table.length - 2; i >= 0; i -= 2) |
| { |
| Object key = table[i]; |
| if (key != tombstone && key != emptyslot) |
| { |
| s.writeObject(key); |
| s.writeObject(table[i + 1]); |
| } |
| } |
| } |
| } |