1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 package org.jaxen.util;
63 import java.io.IOException;
64 import java.util.AbstractCollection;
65 import java.util.AbstractMap;
66 import java.util.AbstractSet;
67 import java.util.Collection;
68 import java.util.ConcurrentModificationException;
69 import java.util.Iterator;
70 import java.util.Map;
71 import java.util.NoSuchElementException;
72 import java.util.Set;
73
74 import org.jaxen.JaxenConstants;
75
76 public class IdentityHashMap extends AbstractMap implements Map, Cloneable,
77 java.io.Serializable {
78 /***
79 * The hash table data.
80 */
81 private transient Entry table[];
82
83 /***
84 * The total number of mappings in the hash table.
85 */
86 private transient int count;
87
88 /***
89 * The table is rehashed when its size exceeds this threshold. (The
90 * value of this field is (int)(capacity * loadFactor).)
91 *
92 * @serial
93 */
94 private int threshold;
95
96 /***
97 * The load factor for the hashtable.
98 *
99 * @serial
100 */
101 private float loadFactor;
102
103 /***
104 * The number of times this HashMap has been structurally modified
105 * Structural modifications are those that change the number of mappings in
106 * the HashMap or otherwise modify its internal structure (e.g.,
107 * rehash). This field is used to make iterators on Collection-views of
108 * the HashMap fail-fast. (See ConcurrentModificationException).
109 */
110 private transient int modCount = 0;
111
112 /***
113 * Constructs a new, empty map with the specified initial
114 * capacity and the specified load factor.
115 *
116 * @param initialCapacity the initial capacity of the HashMap
117 * @param loadFactor the load factor of the HashMap
118 * @throws IllegalArgumentException if the initial capacity is less
119 * than zero, or if the load factor is non-positive
120 */
121 public IdentityHashMap(int initialCapacity, float loadFactor) {
122 if (initialCapacity < 0)
123 throw new IllegalArgumentException("Illegal Initial Capacity: "+
124 initialCapacity);
125 if (loadFactor <= 0 || Float.isNaN(loadFactor))
126 throw new IllegalArgumentException("Illegal Load factor: "+
127 loadFactor);
128 if (initialCapacity==0)
129 initialCapacity = 1;
130 this.loadFactor = loadFactor;
131 table = new Entry[initialCapacity];
132 threshold = (int)(initialCapacity * loadFactor);
133 }
134
135 /***
136 * Constructs a new, empty map with the specified initial capacity
137 * and default load factor, which is <code>0.75</code>.
138 *
139 * @param initialCapacity the initial capacity of the HashMap
140 * @throws IllegalArgumentException if the initial capacity is less
141 * than zero
142 */
143 public IdentityHashMap(int initialCapacity) {
144 this(initialCapacity, 0.75f);
145 }
146
147 /***
148 * Constructs a new, empty map with a default capacity and load
149 * factor, which is <code>0.75</code>.
150 */
151 public IdentityHashMap() {
152 this(11, 0.75f);
153 }
154
155 /***
156 * Constructs a new map with the same mappings as the given map. The
157 * map is created with a capacity of twice the number of mappings in
158 * the given map or 11 (whichever is greater), and a default load factor,
159 * which is <code>0.75</code>.
160 *
161 * @param t the map whose mappings are to be placed in this map
162 */
163 public IdentityHashMap(Map t) {
164 this(Math.max(2*t.size(), 11), 0.75f);
165 putAll(t);
166 }
167
168 /***
169 * Returns the number of key-value mappings in this map
170 *
171 * @return the number of key-value mappings in this map
172 */
173 public int size() {
174 return count;
175 }
176
177 /***
178 * Returns <code>true</code> if this map contains no key-value mappings
179 *
180 * @return <code>true</code> if this map contains no key-value mappings
181 */
182 public boolean isEmpty() {
183 return count == 0;
184 }
185
186 /***
187 * Returns <code>true</code> if this map maps one or more keys to the
188 * specified value.
189 *
190 * @param value value whose presence in this map is to be tested.
191 * @return <code>true</code> if this map maps one or more keys to the
192 * specified value
193 */
194 public boolean containsValue(Object value) {
195 Entry tab[] = table;
196
197 if (value==null) {
198 for (int i = tab.length ; i > 0 ; i--)
199 for (Entry e = tab[i] ; e != null ; e = e.next)
200 if (e.value==null)
201 return true;
202 } else {
203 for (int i = tab.length ; i > 0 ; i--)
204 for (Entry e = tab[i] ; e != null ; e = e.next)
205 if (value.equals(e.value))
206 return true;
207 }
208
209 return false;
210 }
211
212 /***
213 * Returns <code>true</code> if this map contains a mapping for the specified
214 * key.
215 *
216 * @return <code>true</code> if this map contains a mapping for the specified
217 * key
218 * @param key key whose presence in this Map is to be tested
219 */
220 public boolean containsKey(Object key) {
221 Entry tab[] = table;
222 if (key != null) {
223
224 int hash = System.identityHashCode( key );
225 int index = (hash & 0x7FFFFFFF) % tab.length;
226 for (Entry e = tab[index]; e != null; e = e.next)
227
228 if (e.hash==hash && ( key == e.key ) )
229 return true;
230 } else {
231 for (Entry e = tab[0]; e != null; e = e.next)
232 if (e.key==null) return true;
233 }
234
235 return false;
236 }
237
238 /***
239 * Returns the value to which this map maps the specified key. Returns
240 * <code>null</code> if the map contains no mapping for this key. A return
241 * value of <code>null</code> does not <i>necessarily</i> indicate that the
242 * map contains no mapping for the key; it's also possible that the map
243 * explicitly maps the key to <code>null</code>. The <code>containsKey</code>
244 * operation may be used to distinguish these two cases.
245 *
246 * @return the value to which this map maps the specified key
247 * @param key key whose associated value is to be returned
248 */
249 public Object get(Object key) {
250 Entry tab[] = table;
251
252 if (key != null) {
253
254 int hash = System.identityHashCode( key );
255 int index = (hash & 0x7FFFFFFF) % tab.length;
256 for (Entry e = tab[index]; e != null; e = e.next)
257
258 if ((e.hash == hash) && ( key == e.key ) )
259 return e.value;
260 } else {
261 for (Entry e = tab[0]; e != null; e = e.next)
262 if (e.key==null)
263 return e.value;
264 }
265
266 return null;
267 }
268
269 /***
270 * Rehashes the contents of this map into a new <code>IdentityHashMap</code> instance
271 * with a larger capacity. This method is called automatically when the
272 * number of keys in this map exceeds its capacity and load factor.
273 */
274 private void rehash() {
275 int oldCapacity = table.length;
276 Entry oldMap[] = table;
277
278 int newCapacity = oldCapacity * 2 + 1;
279 Entry newMap[] = new Entry[newCapacity];
280
281 modCount++;
282 threshold = (int)(newCapacity * loadFactor);
283 table = newMap;
284
285 for (int i = oldCapacity ; i-- > 0 ;) {
286 for (Entry old = oldMap[i] ; old != null ; ) {
287 Entry e = old;
288 old = old.next;
289
290 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
291 e.next = newMap[index];
292 newMap[index] = e;
293 }
294 }
295 }
296
297 /***
298 * Associates the specified value with the specified key in this map.
299 * If the map previously contained a mapping for this key, the old
300 * value is replaced.
301 *
302 * @param key key with which the specified value is to be associated
303 * @param value value to be associated with the specified key
304 * @return previous value associated with specified key, or <code>null</code>
305 * if there was no mapping for key. A <code>null</code> return can
306 * also indicate that the IdentityHashMap previously associated
307 * <code>null</code> with the specified key.
308 */
309 public Object put(Object key, Object value) {
310
311
312
313
314
315
316 Entry tab[] = table;
317 int hash = 0;
318 int index = 0;
319
320 if (key != null) {
321 hash = System.identityHashCode( key );
322 index = (hash & 0x7FFFFFFF) % tab.length;
323 for (Entry e = tab[index] ; e != null ; e = e.next) {
324 if ((e.hash == hash) && ( key == e.key ) ) {
325 Object old = e.value;
326 e.value = value;
327 return old;
328 }
329 }
330 } else {
331 for (Entry e = tab[0] ; e != null ; e = e.next) {
332 if (e.key == null) {
333 Object old = e.value;
334 e.value = value;
335 return old;
336 }
337 }
338 }
339
340 modCount++;
341 if (count >= threshold) {
342
343 rehash();
344
345 tab = table;
346 index = (hash & 0x7FFFFFFF) % tab.length;
347 }
348
349
350 Entry e = new Entry(hash, key, value, tab[index]);
351 tab[index] = e;
352 count++;
353 return null;
354 }
355
356 /***
357 * Removes the mapping for this key from this map if present.
358 *
359 * @param key key whose mapping is to be removed from the map
360 * @return previous value associated with specified key, or <code>null</code>
361 * if there was no mapping for key. A <code>null</code> return can
362 * also indicate that the map previously associated <code>null</code>
363 * with the specified key.
364 */
365 public Object remove(Object key) {
366 Entry tab[] = table;
367
368 if (key != null) {
369
370 int hash = System.identityHashCode( key );
371 int index = (hash & 0x7FFFFFFF) % tab.length;
372
373 for (Entry e = tab[index], prev = null; e != null;
374 prev = e, e = e.next) {
375
376 if ((e.hash == hash) && ( key == e.key ) ) {
377 modCount++;
378 if (prev != null)
379 prev.next = e.next;
380 else
381 tab[index] = e.next;
382
383 count--;
384 Object oldValue = e.value;
385 e.value = null;
386 return oldValue;
387 }
388 }
389 } else {
390 for (Entry e = tab[0], prev = null; e != null;
391 prev = e, e = e.next) {
392 if (e.key == null) {
393 modCount++;
394 if (prev != null)
395 prev.next = e.next;
396 else
397 tab[0] = e.next;
398
399 count--;
400 Object oldValue = e.value;
401 e.value = null;
402 return oldValue;
403 }
404 }
405 }
406
407 return null;
408 }
409
410 /***
411 * Copies all of the mappings from the specified map to this one.
412 *
413 * These mappings replace any mappings that this map had for any of the
414 * keys currently in the specified Map.
415 *
416 * @param t mappings to be stored in this map
417 */
418 public void putAll(Map t) {
419 Iterator i = t.entrySet().iterator();
420 while (i.hasNext()) {
421 Map.Entry e = (Map.Entry) i.next();
422 put(e.getKey(), e.getValue());
423 }
424 }
425
426 /***
427 * Removes all mappings from this map.
428 */
429 public void clear() {
430 Entry tab[] = table;
431 modCount++;
432 for (int index = tab.length; --index >= 0; )
433 tab[index] = null;
434 count = 0;
435 }
436
437 /***
438 * Returns a shallow copy of this <code>IdentityHashMap</code> instance: the keys and
439 * values themselves are not cloned.
440 *
441 * @return a shallow copy of this map
442 */
443 public Object clone() {
444 try {
445 IdentityHashMap t = (IdentityHashMap)super.clone();
446 t.table = new Entry[table.length];
447 for (int i = table.length ; i-- > 0 ; ) {
448 t.table[i] = (table[i] != null)
449 ? (Entry)table[i].clone() : null;
450 }
451 t.keySet = null;
452 t.entrySet = null;
453 t.values = null;
454 t.modCount = 0;
455 return t;
456 } catch (CloneNotSupportedException e) {
457
458 throw new InternalError();
459 }
460 }
461
462
463
464 private transient Set keySet = null;
465 private transient Set entrySet = null;
466 private transient Collection values = null;
467
468 /***
469 * Returns a set view of the keys contained in this map. The set is
470 * backed by the map, so changes to the map are reflected in the set, and
471 * vice-versa. The set supports element removal, which removes the
472 * corresponding mapping from this map, via the <code>Iterator.remove</code>,
473 * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, and
474 * <code>clear</code> operations. It does not support the <code>add</code> or
475 * <code>addAll</code> operations.
476 *
477 * @return a set view of the keys contained in this map
478 */
479 public Set keySet() {
480 if (keySet == null) {
481 keySet = new AbstractSet() {
482 public Iterator iterator() {
483 return getHashIterator(KEYS);
484 }
485 public int size() {
486 return count;
487 }
488 public boolean contains(Object o) {
489 return containsKey(o);
490 }
491 public boolean remove(Object o) {
492 int oldSize = count;
493 IdentityHashMap.this.remove(o);
494 return count != oldSize;
495 }
496 public void clear() {
497 IdentityHashMap.this.clear();
498 }
499 };
500 }
501 return keySet;
502 }
503
504 /***
505 * Returns a collection view of the values contained in this map. The
506 * collection is backed by the map, so changes to the map are reflected in
507 * the collection, and vice-versa. The collection supports element
508 * removal, which removes the corresponding mapping from this map, via the
509 * <code>Iterator.remove</code>, <code>Collection.remove</code>,
510 * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations.
511 * It does not support the <code>add</code> or <code>addAll</code> operations.
512 *
513 * @return a collection view of the values contained in this map
514 */
515 public Collection values() {
516 if (values==null) {
517 values = new AbstractCollection() {
518 public Iterator iterator() {
519 return getHashIterator(VALUES);
520 }
521 public int size() {
522 return count;
523 }
524 public boolean contains(Object o) {
525 return containsValue(o);
526 }
527 public void clear() {
528 IdentityHashMap.this.clear();
529 }
530 };
531 }
532 return values;
533 }
534
535 /***
536 * Returns a collection view of the mappings contained in this map. Each
537 * element in the returned collection is a <code>Map.Entry</code>. The
538 * collection is backed by the map, so changes to the map are reflected in
539 * the collection, and vice-versa. The collection supports element
540 * removal, which removes the corresponding mapping from the map, via the
541 * <code>Iterator.remove</code>, <code>Collection.remove</code>,
542 * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations.
543 * It does not support the <code>add</code> or <code>addAll</code> operations.
544 *
545 * @return a collection view of the mappings contained in this map
546 * @see Map.Entry
547 */
548 public Set entrySet() {
549 if (entrySet==null) {
550 entrySet = new AbstractSet() {
551 public Iterator iterator() {
552 return getHashIterator(ENTRIES);
553 }
554
555 public boolean contains(Object o) {
556 if (!(o instanceof Map.Entry))
557 return false;
558 Map.Entry entry = (Map.Entry)o;
559 Object key = entry.getKey();
560 Entry tab[] = table;
561
562 int hash = (key==null ? 0 : System.identityHashCode( key ) );
563 int index = (hash & 0x7FFFFFFF) % tab.length;
564
565 for (Entry e = tab[index]; e != null; e = e.next)
566 if (e.hash==hash && e.equals(entry))
567 return true;
568 return false;
569 }
570
571 public boolean remove(Object o) {
572 if (!(o instanceof Map.Entry))
573 return false;
574 Map.Entry entry = (Map.Entry)o;
575 Object key = entry.getKey();
576 Entry tab[] = table;
577
578 int hash = (key==null ? 0 : System.identityHashCode( key ) );
579 int index = (hash & 0x7FFFFFFF) % tab.length;
580
581 for (Entry e = tab[index], prev = null; e != null;
582 prev = e, e = e.next) {
583 if (e.hash==hash && e.equals(entry)) {
584 modCount++;
585 if (prev != null)
586 prev.next = e.next;
587 else
588 tab[index] = e.next;
589
590 count--;
591 e.value = null;
592 return true;
593 }
594 }
595 return false;
596 }
597
598 public int size() {
599 return count;
600 }
601
602 public void clear() {
603 IdentityHashMap.this.clear();
604 }
605 };
606 }
607
608 return entrySet;
609 }
610
611 private Iterator getHashIterator(int type) {
612 if (count == 0) {
613 return JaxenConstants.EMPTY_ITERATOR;
614 } else {
615 return new HashIterator(type);
616 }
617 }
618
619 /***
620 * IdentityHashMap collision list entry.
621 */
622 private static class Entry implements Map.Entry {
623 int hash;
624 Object key;
625 Object value;
626 Entry next;
627
628 Entry(int hash, Object key, Object value, Entry next) {
629 this.hash = hash;
630 this.key = key;
631 this.value = value;
632 this.next = next;
633 }
634
635 protected Object clone() {
636 return new Entry(hash, key, value,
637 (next==null ? null : (Entry)next.clone()));
638 }
639
640
641
642 public Object getKey() {
643 return key;
644 }
645
646 public Object getValue() {
647 return value;
648 }
649
650 public Object setValue(Object value) {
651 Object oldValue = this.value;
652 this.value = value;
653 return oldValue;
654 }
655
656 public boolean equals(Object o) {
657 if (!(o instanceof Map.Entry))
658 return false;
659 Map.Entry e = (Map.Entry)o;
660
661 return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
662 (value==null ? e.getValue()==null : value.equals(e.getValue()));
663 }
664
665 public int hashCode() {
666 return hash ^ (value==null ? 0 : value.hashCode());
667 }
668
669 public String toString() {
670 return key+"="+value;
671 }
672 }
673
674
675 private static final int KEYS = 0;
676 private static final int VALUES = 1;
677 private static final int ENTRIES = 2;
678
679 private class HashIterator implements Iterator {
680 Entry[] table = IdentityHashMap.this.table;
681 int index = table.length;
682 Entry entry = null;
683 Entry lastReturned = null;
684 int type;
685
686 /***
687 * The modCount value that the iterator believes that the backing
688 * List should have. If this expectation is violated, the iterator
689 * has detected concurrent modification.
690 */
691 private int expectedModCount = modCount;
692
693 HashIterator(int type) {
694 this.type = type;
695 }
696
697 public boolean hasNext() {
698 Entry e = entry;
699 int i = index;
700 Entry t[] = table;
701
702 while (e == null && i > 0)
703 e = t[--i];
704 entry = e;
705 index = i;
706 return e != null;
707 }
708
709 public Object next() {
710 if (modCount != expectedModCount)
711 throw new ConcurrentModificationException();
712
713 Entry et = entry;
714 int i = index;
715 Entry t[] = table;
716
717
718 while (et == null && i > 0)
719 et = t[--i];
720
721 entry = et;
722 index = i;
723 if (et != null) {
724 Entry e = lastReturned = entry;
725 entry = e.next;
726 return type == KEYS ? e.key : (type == VALUES ? e.value : e);
727 }
728 throw new NoSuchElementException();
729 }
730
731 public void remove() {
732 if (lastReturned == null)
733 throw new IllegalStateException();
734 if (modCount != expectedModCount)
735 throw new ConcurrentModificationException();
736
737 Entry[] tab = IdentityHashMap.this.table;
738 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
739
740 for (Entry e = tab[index], prev = null; e != null;
741 prev = e, e = e.next) {
742 if (e == lastReturned) {
743 modCount++;
744 expectedModCount++;
745 if (prev == null)
746 tab[index] = e.next;
747 else
748 prev.next = e.next;
749 count--;
750 lastReturned = null;
751 return;
752 }
753 }
754 throw new ConcurrentModificationException();
755 }
756 }
757
758 /***
759 * Save the state of the <code>IdentityHashMap</code> instance to a stream (i.e.,
760 * serialize it).
761 *
762 * @serialData the <em>capacity</em> of the IdentityHashMap (the length of the
763 * bucket array) is emitted (int), followed by the
764 * <em>size</em> of the IdentityHashMap (the number of key-value
765 * mappings), followed by the key (Object) and value (Object)
766 * for each key-value mapping represented by the IdentityHashMap.
767 * The key-value mappings are emitted in no particular order.
768 */
769 private void writeObject(java.io.ObjectOutputStream s)
770 throws IOException
771 {
772
773 s.defaultWriteObject();
774
775
776 s.writeInt(table.length);
777
778
779 s.writeInt(count);
780
781
782 for (int index = table.length-1; index >= 0; index--) {
783 Entry entry = table[index];
784
785 while (entry != null) {
786 s.writeObject(entry.key);
787 s.writeObject(entry.value);
788 entry = entry.next;
789 }
790 }
791 }
792
793 private static final long serialVersionUID = 362498820763181265L;
794
795 /***
796 * Reconstitute the <code>IdentityHashMap</code> instance from a stream (i.e.,
797 * deserialize it).
798 */
799 private void readObject(java.io.ObjectInputStream s)
800 throws IOException, ClassNotFoundException
801 {
802
803 s.defaultReadObject();
804
805
806 int numBuckets = s.readInt();
807 table = new Entry[numBuckets];
808
809
810 int size = s.readInt();
811
812
813 for (int i=0; i<size; i++) {
814 Object key = s.readObject();
815 Object value = s.readObject();
816 put(key, value);
817 }
818 }
819
820 int capacity() {
821 return table.length;
822 }
823
824 float loadFactor() {
825 return loadFactor;
826 }
827 }