diff options
Diffstat (limited to 'libjava/java/util/IdentityHashMap.java')
| -rw-r--r-- | libjava/java/util/IdentityHashMap.java | 1043 |
1 files changed, 764 insertions, 279 deletions
diff --git a/libjava/java/util/IdentityHashMap.java b/libjava/java/util/IdentityHashMap.java index da028ed..d6a2f7c 100644 --- a/libjava/java/util/IdentityHashMap.java +++ b/libjava/java/util/IdentityHashMap.java @@ -31,403 +31,888 @@ import java.io.*; /** * This class provides a hashtable-backed implementation of the - * Map interface. Unlike HashMap, it uses object identity to - * do its hashing. Also, it uses a linear-probe hash table. + * 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; - /** Create a new IdentityHashMap with the default capacity (21 - * entries). + /** + * 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. */ - public IdentityHashMap () + 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); + this(DEFAULT_CAPACITY); } - /** Create a new IdentityHashMap with the indicated number of + /** + * 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 + * + * @param max initial size + * @throws IllegalArgumentException if max is negative */ - public IdentityHashMap (int max) + public IdentityHashMap(int max) { if (max < 0) - throw new IllegalArgumentException (); + throw new IllegalArgumentException(); + // Need at least two slots, or hash() will break. + if (max < 2) + max = 2; table = new Object[2 * max]; - Arrays.fill (table, emptyslot); - size = 0; + Arrays.fill(table, emptyslot); + // This is automatically set. + // size = 0; + threshold = max / 4 * 3; } - /** Create a new IdentityHashMap whose contents are taken from the + /** + * 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. + * + * @param m The map whose elements are to be put in this map + * @throws NullPointerException if m is null */ - public IdentityHashMap (Map m) + public IdentityHashMap(Map m) { - int len = 2 * Math.max (m.size (), DEFAULT_CAPACITY); - table = new Object[len]; - Arrays.fill (table, emptyslot); - putAll (m); + this(Math.max(m.size() * 2, DEFAULT_CAPACITY)); + putAll(m); } - public void clear () + /** + * Remove all mappings from this map. + */ + public void clear() { - Arrays.fill (table, emptyslot); - size = 0; + if (size != 0) + { + modCount++; + Arrays.fill(table, emptyslot); + size = 0; + } } /** * Creates a shallow copy where keys and values are not cloned. */ - public Object clone () + public Object clone() { - try + try { - IdentityHashMap copy = (IdentityHashMap) super.clone (); - copy.table = (Object[]) table.clone (); - return copy; + IdentityHashMap copy = (IdentityHashMap) super.clone(); + copy.table = (Object[]) table.clone(); + copy.entries = null; // invalidate the cache + return copy; } - catch (CloneNotSupportedException e) + catch (CloneNotSupportedException e) { - // Can't happen. - return null; + // Can't happen. + return null; } } - public boolean containsKey (Object key) + /** + * 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) { - int h = getHash (key); - int save = h; - while (true) - { - if (table[h] == key) - return true; - if (table[h] == emptyslot) - return false; - h += 2; - if (h >= table.length) - h = 0; - if (h == save) - return false; - } + return key == table[hash(key)]; } - public boolean containsValue (Object value) + /** + * 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 = 1; i < table.length; i += 2) + for (int i = table.length - 1; i > 0; i -= 2) if (table[i] == value) - return true; + return true; return false; } - public Set entrySet () + /** + * 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() { - return new AbstractSet () - { - public int size () + if (entries == null) + entries = new AbstractSet() { - return size; - } - - public Iterator iterator () - { - return new IdentityIterator (IdentityIterator.ENTRIES); - } - - public void clear () - { - IdentityHashMap.this.clear (); - } + 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; + } - public boolean contains (Object o) - { - if (! (o instanceof Map.Entry)) - return false; - Map.Entry m = (Map.Entry) o; - return (IdentityHashMap.this.containsKey (m.getKey ()) - && IdentityHashMap.this.get (m.getKey ()) == m.getValue ()); - } + /** + * 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); + } - public boolean remove (Object o) - { - if (! (o instanceof Map.Entry)) - return false; - Map.Entry m = (Map.Entry) o; - if (IdentityHashMap.this.containsKey (m.getKey ()) - && IdentityHashMap.this.get (m.getKey ()) == m.getValue ()) - { - int oldsize = size; - IdentityHashMap.this.remove (m.getKey ()); - return oldsize != size; - } - return false; - } - }; + /** + * Return the value in this Map associated with the supplied key, + * or <pre>null</pre> if the key maps to nothing. 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; } - public Object get (Object key) + /** + * 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 h = getHash (key); - int save = h; - while (true) + int hash = 0; + for (int i = table.length - 2; i >= 0; i -= 2) { - if (table[h] == key) - return table[h + 1]; - if (table[h] == emptyslot) - return null; - h += 2; - if (h >= table.length) - h = 0; - if (h == save) - return null; + Object key = table[i]; + if (key == emptyslot || key == tombstone) + continue; + hash += (System.identityHashCode(key) + ^ System.identityHashCode(table[i + 1])); } + return hash; } - public boolean isEmpty () + /** + * Returns true if there are no key-value mappings currently in this Map + * @return <code>size() == 0</code> + */ + public boolean isEmpty() { return size == 0; } - public Set keySet () + /** + * 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() { - return new AbstractSet () - { - public int size () - { - return size; - } - - public Iterator iterator () - { - return new IdentityIterator (IdentityIterator.KEYS); - } - - public void clear () + if (keys == null) + keys = new AbstractSet() { - IdentityHashMap.this.clear (); - } - - public boolean contains (Object o) - { - return IdentityHashMap.this.containsKey (o); - } - - public boolean remove (Object o) - { - int oldsize = size; - IdentityHashMap.this.remove (o); - return oldsize != size; - } - }; + 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; } - public Object put (Object key, Object value) + /** + * 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. We use a factor of 1.5 - // -- the division by 2 is implicit on both sides. - if (size * 3 > table.length) - { - Object[] old = table; - table = new Object[old.length * 2]; - Arrays.fill (table, emptyslot); - size = 0; - for (int i = 0; i < old.length; i += 2) - { - if (old[i] != tombstone && old[i] != emptyslot) - { - // Just use put. This isn't very efficient, but it is - // ok. - put (old[i], old[i + 1]); - } - } - } - - int h = getHash (key); - int save = h; - int del = -1; - while (true) + // Rehash if the load factor is too high. + if (size > threshold) { - if (table[h] == key) - { - Object r = table[h + 1]; - table[h + 1] = value; - return r; - } - else if (table[h] == tombstone && del == -1) - del = h; - else if (table[h] == emptyslot) - { - if (del == -1) - del = h; - break; - } - h += 2; - if (h >= table.length) - h = 0; - if (h == save) - break; + 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 / 4 * 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]); + } } - if (del != -1) + int h = hash(key); + if (table[h] == key) { - table[del] = key; - table[del + 1] = value; - ++size; - return null; + Object r = table[h + 1]; + table[h + 1] = value; + return r; } - // This is an error. + // At this point, we add a new mapping. + modCount++; + size++; + table[h] = key; + table[h + 1] = value; return null; } - public Object remove (Object key) + /** + * 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) { - int h = getHash (key); - int save = h; - while (true) + // 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 <pre>null</pre> 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) { - if (table[h] == key) - { - Object r = table[h + 1]; - table[h] = tombstone; - table[h + 1] = tombstone; - --size; - return r; - } - h += 2; - if (h >= table.length) - h = 0; - if (h == save) - break; + modCount++; + size--; + Object r = table[h + 1]; + table[h] = tombstone; + table[h + 1] = tombstone; + return r; } - return null; } - public int size () + /** + * Returns the number of kay-value mappings currently in this Map + * @return the size + */ + public int size() { return size; } - public Collection values () + /** + * 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() { - return new AbstractCollection () - { - public int size () + if (values == null) + values = new AbstractCollection() { - return size; - } + 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; + } - public Iterator iterator () - { - return new IdentityIterator (IdentityIterator.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 = 2 * Math.abs(System.identityHashCode(key) % table.length); + int del = -1; + int save = h; - public void clear () + do { - IdentityHashMap.this.clear (); + 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; } - private class IdentityIterator implements Iterator + /** + * 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 final class IdentityIterator implements Iterator { - static final int KEYS = 0; - static final int VALUES = 1; - static final int ENTRIES = 2; - - // Type of iterator. - int type; - // Location in the table. - int loc; - // How many items we've seen. - int seen; - - IdentityIterator (int type) + /** + * 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; - loc = 0; - seen = 0; } - public boolean hasNext () + /** + * Returns true if the Iterator has more elements. + * @return true if there are more elements + * @throws ConcurrentModificationException if the Map was modified + */ + public boolean hasNext() { - return seen < size; + if (knownMod != modCount) + throw new ConcurrentModificationException(); + return count > 0; } - public Object next () + /** + * 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() { - while (true) - { - loc += 2; - if (loc >= table.length) - throw new NoSuchElementException (); - if (table[loc] != tombstone && table[loc] != emptyslot) - { - ++seen; - return table[loc]; - } - } + 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)); } - public void remove () + /** + * Removes from the backing Map the last element which was fetched + * with the <pre>next()</pre> method. + * @throws ConcurrentModificationException if the Map was modified + * @throws IllegalStateException if called when there is no last element + */ + public void remove() { - if (loc >= table.length - || table[loc] == tombstone - || table[loc] == emptyslot) - throw new IllegalStateException (); + 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; - --size; + 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 final String toString() + { + if (knownMod != modCount || table[loc] == tombstone) + throw new ConcurrentModificationException(); + return table[loc] + "=" + table[loc + 1]; + } + } // class IdentityEntry - private void readObject (ObjectInputStream s) + /** + * 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 { - int num = s.readInt (); - for (int i = 0; i < num; ++i) - { - Object key = s.readObject (); - Object value = s.readObject (); - put (key, value); - } + s.defaultReadObject(); + + int num = s.readInt(); + table = new Object[2 * Math.max(num * 2, DEFAULT_CAPACITY)]; + // Read key/value pairs. + while (--num >= 0) + put(s.readObject(), s.readObject()); } - private void writeObject (ObjectOutputStream s) + /** + * 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.writeInt (size); - Iterator it = entrySet ().iterator (); - while (it.hasNext ()) + s.defaultWriteObject(); + s.writeInt(size); + for (int i = table.length - 2; i >= 0; i -= 2) { - Map.Entry entry = (Map.Entry) it.next (); - s.writeObject (entry.getKey ()); - s.writeObject (entry.getValue ()); + Object key = table[i]; + if (key != tombstone && key != emptyslot) + { + s.writeObject(key); + s.writeObject(table[i + 1]); + } } } - - // Compute the hash value we will use for an object. - private int getHash (Object o) - { - return 2 * Math.abs (System.identityHashCode (o) % (table.length / 2)); - } - - // Number of items in hash table. - private int size; - // The table itself. - private Object[] table; - - // This object is used to mark deleted items. - private static final Object tombstone = new Object (); - // This object is used to mark empty slots. We need this because - // using null is ambiguous. - private static final Object emptyslot = new Object (); } |