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