1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.map;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.lang.ref.Reference;
23 import java.lang.ref.ReferenceQueue;
24 import java.lang.ref.SoftReference;
25 import java.lang.ref.WeakReference;
26 import java.util.ArrayList;
27 import java.util.Collection;
28 import java.util.ConcurrentModificationException;
29 import java.util.Iterator;
30 import java.util.List;
31 import java.util.Map;
32 import java.util.NoSuchElementException;
33 import java.util.Set;
34
35 import org.apache.commons.collections4.MapIterator;
36 import org.apache.commons.collections4.keyvalue.DefaultMapEntry;
37
38 /**
39 * An abstract implementation of a hash-based map that allows the entries to
40 * be removed by the garbage collector.
41 * <p>
42 * This class implements all the features necessary for a subclass reference
43 * hash-based map. Key-value entries are stored in instances of the
44 * <code>ReferenceEntry</code> class which can be overridden and replaced.
45 * The iterators can similarly be replaced, without the need to replace the KeySet,
46 * EntrySet and Values view classes.
47 * </p>
48 * <p>
49 * Overridable methods are provided to change the default hashing behaviour, and
50 * to change how entries are added to and removed from the map. Hopefully, all you
51 * need for unusual subclasses is here.
52 * </p>
53 * <p>
54 * When you construct an <code>AbstractReferenceMap</code>, you can specify what
55 * kind of references are used to store the map's keys and values.
56 * If non-hard references are used, then the garbage collector can remove
57 * mappings if a key or value becomes unreachable, or if the JVM's memory is
58 * running low. For information on how the different reference types behave,
59 * see {@link Reference}.
60 * </p>
61 * <p>
62 * Different types of references can be specified for keys and values.
63 * The keys can be configured to be weak but the values hard,
64 * in which case this class will behave like a
65 * <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
66 * <code>WeakHashMap</code></a>. However, you can also specify hard keys and
67 * weak values, or any other combination. The default constructor uses
68 * hard keys and soft values, providing a memory-sensitive cache.
69 * </p>
70 * <p>
71 * This {@link Map} implementation does <i>not</i> allow null elements.
72 * Attempting to add a null key or value to the map will raise a
73 * <code>NullPointerException</code>.
74 * </p>
75 * <p>
76 * All the available iterators can be reset back to the start by casting to
77 * <code>ResettableIterator</code> and calling <code>reset()</code>.
78 * </p>
79 * <p>
80 * This implementation is not synchronized.
81 * You can use {@link java.util.Collections#synchronizedMap} to
82 * provide synchronized access to a <code>ReferenceMap</code>.
83 * </p>
84 *
85 * @param <K> the type of the keys in this map
86 * @param <V> the type of the values in this map
87 *
88 * @see java.lang.ref.Reference
89 * @since 3.1 (extracted from ReferenceMap in 3.0)
90 */
91 public abstract class AbstractReferenceMap<K, V> extends AbstractHashedMap<K, V> {
92
93 /**
94 * Reference type enum.
95 */
96 public enum ReferenceStrength {
97 HARD(0), SOFT(1), WEAK(2);
98
99 /** value */
100 public final int value;
101
102 /**
103 * Resolve enum from int.
104 * @param value the int value
105 * @return ReferenceType
106 * @throws IllegalArgumentException if the specified value is invalid.
107 */
108 public static ReferenceStrength resolve(final int value) {
109 switch (value) {
110 case 0:
111 return HARD;
112 case 1:
113 return SOFT;
114 case 2:
115 return WEAK;
116 default:
117 throw new IllegalArgumentException();
118 }
119 }
120
121 ReferenceStrength(final int value) {
122 this.value = value;
123 }
124
125 }
126
127 /**
128 * The reference type for keys.
129 */
130 private ReferenceStrength keyType;
131
132 /**
133 * The reference type for values.
134 */
135 private ReferenceStrength valueType;
136
137 /**
138 * Should the value be automatically purged when the associated key has been collected?
139 */
140 private boolean purgeValues;
141
142 /**
143 * ReferenceQueue used to eliminate stale mappings.
144 * See purge.
145 */
146 private transient ReferenceQueue<Object> queue;
147
148 //-----------------------------------------------------------------------
149 /**
150 * Constructor used during deserialization.
151 */
152 protected AbstractReferenceMap() {
153 super();
154 }
155
156 /**
157 * Constructs a new empty map with the specified reference types,
158 * load factor and initial capacity.
159 *
160 * @param keyType the type of reference to use for keys;
161 * must be {@link ReferenceStrength#HARD HARD},
162 * {@link ReferenceStrength#SOFT SOFT},
163 * {@link ReferenceStrength#WEAK WEAK}
164 * @param valueType the type of reference to use for values;
165 * must be {@link ReferenceStrength#HARD},
166 * {@link ReferenceStrength#SOFT SOFT},
167 * {@link ReferenceStrength#WEAK WEAK}
168 * @param capacity the initial capacity for the map
169 * @param loadFactor the load factor for the map
170 * @param purgeValues should the value be automatically purged when the
171 * key is garbage collected
172 */
173 protected AbstractReferenceMap(
174 final ReferenceStrength keyType, final ReferenceStrength valueType, final int capacity,
175 final float loadFactor, final boolean purgeValues) {
176 super(capacity, loadFactor);
177 this.keyType = keyType;
178 this.valueType = valueType;
179 this.purgeValues = purgeValues;
180 }
181
182 /**
183 * Initialise this subclass during construction, cloning or deserialization.
184 */
185 @Override
186 protected void init() {
187 queue = new ReferenceQueue<>();
188 }
189
190 //-----------------------------------------------------------------------
191 /**
192 * Gets the size of the map.
193 *
194 * @return the size
195 */
196 @Override
197 public int size() {
198 purgeBeforeRead();
199 return super.size();
200 }
201
202 /**
203 * Checks whether the map is currently empty.
204 *
205 * @return true if the map is currently size zero
206 */
207 @Override
208 public boolean isEmpty() {
209 purgeBeforeRead();
210 return super.isEmpty();
211 }
212
213 /**
214 * Checks whether the map contains the specified key.
215 *
216 * @param key the key to search for
217 * @return true if the map contains the key
218 */
219 @Override
220 public boolean containsKey(final Object key) {
221 purgeBeforeRead();
222 final Entry<K, V> entry = getEntry(key);
223 if (entry == null) {
224 return false;
225 }
226 return entry.getValue() != null;
227 }
228
229 /**
230 * Checks whether the map contains the specified value.
231 *
232 * @param value the value to search for
233 * @return true if the map contains the value
234 */
235 @Override
236 public boolean containsValue(final Object value) {
237 purgeBeforeRead();
238 if (value == null) {
239 return false;
240 }
241 return super.containsValue(value);
242 }
243
244 /**
245 * Gets the value mapped to the key specified.
246 *
247 * @param key the key
248 * @return the mapped value, null if no match
249 */
250 @Override
251 public V get(final Object key) {
252 purgeBeforeRead();
253 final Entry<K, V> entry = getEntry(key);
254 if (entry == null) {
255 return null;
256 }
257 return entry.getValue();
258 }
259
260
261 /**
262 * Puts a key-value mapping into this map.
263 * Neither the key nor the value may be null.
264 *
265 * @param key the key to add, must not be null
266 * @param value the value to add, must not be null
267 * @return the value previously mapped to this key, null if none
268 * @throws NullPointerException if either the key or value is null
269 */
270 @Override
271 public V put(final K key, final V value) {
272 if (key == null) {
273 throw new NullPointerException("null keys not allowed");
274 }
275 if (value == null) {
276 throw new NullPointerException("null values not allowed");
277 }
278
279 purgeBeforeWrite();
280 return super.put(key, value);
281 }
282
283 /**
284 * Removes the specified mapping from this map.
285 *
286 * @param key the mapping to remove
287 * @return the value mapped to the removed key, null if key not in map
288 */
289 @Override
290 public V remove(final Object key) {
291 if (key == null) {
292 return null;
293 }
294 purgeBeforeWrite();
295 return super.remove(key);
296 }
297
298 /**
299 * Clears this map.
300 */
301 @Override
302 public void clear() {
303 super.clear();
304 // drain the queue
305 while (queue.poll() != null) {
306 // empty
307 }
308 }
309
310 //-----------------------------------------------------------------------
311 /**
312 * Gets a MapIterator over the reference map.
313 * The iterator only returns valid key/value pairs.
314 *
315 * @return a map iterator
316 */
317 @Override
318 public MapIterator<K, V> mapIterator() {
319 return new ReferenceMapIterator<>(this);
320 }
321
322 /**
323 * Returns a set view of this map's entries.
324 * An iterator returned entry is valid until <code>next()</code> is called again.
325 * The <code>setValue()</code> method on the <code>toArray</code> entries has no effect.
326 *
327 * @return a set view of this map's entries
328 */
329 @Override
330 public Set<Map.Entry<K, V>> entrySet() {
331 if (entrySet == null) {
332 entrySet = new ReferenceEntrySet<>(this);
333 }
334 return entrySet;
335 }
336
337 /**
338 * Returns a set view of this map's keys.
339 *
340 * @return a set view of this map's keys
341 */
342 @Override
343 public Set<K> keySet() {
344 if (keySet == null) {
345 keySet = new ReferenceKeySet<>(this);
346 }
347 return keySet;
348 }
349
350 /**
351 * Returns a collection view of this map's values.
352 *
353 * @return a set view of this map's values
354 */
355 @Override
356 public Collection<V> values() {
357 if (values == null) {
358 values = new ReferenceValues<>(this);
359 }
360 return values;
361 }
362
363 //-----------------------------------------------------------------------
364 /**
365 * Purges stale mappings from this map before read operations.
366 * <p>
367 * This implementation calls {@link #purge()} to maintain a consistent state.
368 */
369 protected void purgeBeforeRead() {
370 purge();
371 }
372
373 /**
374 * Purges stale mappings from this map before write operations.
375 * <p>
376 * This implementation calls {@link #purge()} to maintain a consistent state.
377 */
378 protected void purgeBeforeWrite() {
379 purge();
380 }
381
382 /**
383 * Purges stale mappings from this map.
384 * <p>
385 * Note that this method is not synchronized! Special
386 * care must be taken if, for instance, you want stale
387 * mappings to be removed on a periodic basis by some
388 * background thread.
389 */
390 protected void purge() {
391 Reference<?> ref = queue.poll();
392 while (ref != null) {
393 purge(ref);
394 ref = queue.poll();
395 }
396 }
397
398 /**
399 * Purges the specified reference.
400 *
401 * @param ref the reference to purge
402 */
403 protected void purge(final Reference<?> ref) {
404 // The hashCode of the reference is the hashCode of the
405 // mapping key, even if the reference refers to the
406 // mapping value...
407 final int hash = ref.hashCode();
408 final int index = hashIndex(hash, data.length);
409 HashEntry<K, V> previous = null;
410 HashEntry<K, V> entry = data[index];
411 while (entry != null) {
412 ReferenceEntry<K, V> refEntry = (ReferenceEntry<K, V>) entry;
413 if (refEntry.purge(ref)) {
414 if (previous == null) {
415 data[index] = entry.next;
416 } else {
417 previous.next = entry.next;
418 }
419 this.size--;
420 refEntry.onPurge();
421 return;
422 }
423 previous = entry;
424 entry = entry.next;
425 }
426
427 }
428
429 //-----------------------------------------------------------------------
430 /**
431 * Gets the entry mapped to the key specified.
432 *
433 * @param key the key
434 * @return the entry, null if no match
435 */
436 @Override
437 protected HashEntry<K, V> getEntry(final Object key) {
438 if (key == null) {
439 return null;
440 }
441 return super.getEntry(key);
442 }
443
444 /**
445 * Gets the hash code for a MapEntry.
446 * Subclasses can override this, for example to use the identityHashCode.
447 *
448 * @param key the key to get a hash code for, may be null
449 * @param value the value to get a hash code for, may be null
450 * @return the hash code, as per the MapEntry specification
451 */
452 protected int hashEntry(final Object key, final Object value) {
453 return (key == null ? 0 : key.hashCode()) ^
454 (value == null ? 0 : value.hashCode());
455 }
456
457 /**
458 * Compares two keys, in internal converted form, to see if they are equal.
459 * <p>
460 * This implementation converts the key from the entry to a real reference
461 * before comparison.
462 *
463 * @param key1 the first key to compare passed in from outside
464 * @param key2 the second key extracted from the entry via <code>entry.key</code>
465 * @return true if equal
466 */
467 @Override
468 @SuppressWarnings("unchecked")
469 protected boolean isEqualKey(final Object key1, Object key2) {
470 key2 = keyType == ReferenceStrength.HARD ? key2 : ((Reference<K>) key2).get();
471 return key1 == key2 || key1.equals(key2);
472 }
473
474 /**
475 * Creates a ReferenceEntry instead of a HashEntry.
476 *
477 * @param next the next entry in sequence
478 * @param hashCode the hash code to use
479 * @param key the key to store
480 * @param value the value to store
481 * @return the newly created entry
482 */
483 @Override
484 protected ReferenceEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode,
485 final K key, final V value) {
486 return new ReferenceEntry<>(this, next, hashCode, key, value);
487 }
488
489 /**
490 * Creates an entry set iterator.
491 *
492 * @return the entrySet iterator
493 */
494 @Override
495 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
496 return new ReferenceEntrySetIterator<>(this);
497 }
498
499 /**
500 * Creates an key set iterator.
501 *
502 * @return the keySet iterator
503 */
504 @Override
505 protected Iterator<K> createKeySetIterator() {
506 return new ReferenceKeySetIterator<>(this);
507 }
508
509 /**
510 * Creates an values iterator.
511 *
512 * @return the values iterator
513 */
514 @Override
515 protected Iterator<V> createValuesIterator() {
516 return new ReferenceValuesIterator<>(this);
517 }
518
519 //-----------------------------------------------------------------------
520 /**
521 * EntrySet implementation.
522 */
523 static class ReferenceEntrySet<K, V> extends EntrySet<K, V> {
524
525 protected ReferenceEntrySet(final AbstractHashedMap<K, V> parent) {
526 super(parent);
527 }
528
529 @Override
530 public Object[] toArray() {
531 return toArray(new Object[size()]);
532 }
533
534 @Override
535 public <T> T[] toArray(final T[] arr) {
536 // special implementation to handle disappearing entries
537 final ArrayList<Map.Entry<K, V>> list = new ArrayList<>(size());
538 for (final Map.Entry<K, V> entry : this) {
539 list.add(new DefaultMapEntry<>(entry));
540 }
541 return list.toArray(arr);
542 }
543 }
544
545 //-----------------------------------------------------------------------
546 /**
547 * KeySet implementation.
548 */
549 static class ReferenceKeySet<K> extends KeySet<K> {
550
551 protected ReferenceKeySet(final AbstractHashedMap<K, ?> parent) {
552 super(parent);
553 }
554
555 @Override
556 public Object[] toArray() {
557 return toArray(new Object[size()]);
558 }
559
560 @Override
561 public <T> T[] toArray(final T[] arr) {
562 // special implementation to handle disappearing keys
563 final List<K> list = new ArrayList<>(size());
564 for (final K key : this) {
565 list.add(key);
566 }
567 return list.toArray(arr);
568 }
569 }
570
571 //-----------------------------------------------------------------------
572 /**
573 * Values implementation.
574 */
575 static class ReferenceValues<V> extends Values<V> {
576
577 protected ReferenceValues(final AbstractHashedMap<?, V> parent) {
578 super(parent);
579 }
580
581 @Override
582 public Object[] toArray() {
583 return toArray(new Object[size()]);
584 }
585
586 @Override
587 public <T> T[] toArray(final T[] arr) {
588 // special implementation to handle disappearing values
589 final List<V> list = new ArrayList<>(size());
590 for (final V value : this) {
591 list.add(value);
592 }
593 return list.toArray(arr);
594 }
595 }
596
597 //-----------------------------------------------------------------------
598 /**
599 * A MapEntry implementation for the map.
600 * <p>
601 * If getKey() or getValue() returns null, it means
602 * the mapping is stale and should be removed.
603 *
604 * @since 3.1
605 */
606 protected static class ReferenceEntry<K, V> extends HashEntry<K, V> {
607 /** The parent map */
608 private final AbstractReferenceMap<K, V> parent;
609
610 /**
611 * Creates a new entry object for the ReferenceMap.
612 *
613 * @param parent the parent map
614 * @param next the next entry in the hash bucket
615 * @param hashCode the hash code of the key
616 * @param key the key
617 * @param value the value
618 */
619 public ReferenceEntry(final AbstractReferenceMap<K, V> parent, final HashEntry<K, V> next,
620 final int hashCode, final K key, final V value) {
621 super(next, hashCode, null, null);
622 this.parent = parent;
623 this.key = toReference(parent.keyType, key, hashCode);
624 this.value = toReference(parent.valueType, value, hashCode); // the key hashCode is passed in deliberately
625 }
626
627 /**
628 * Gets the key from the entry.
629 * This method dereferences weak and soft keys and thus may return null.
630 *
631 * @return the key, which may be null if it was garbage collected
632 */
633 @Override
634 @SuppressWarnings("unchecked")
635 public K getKey() {
636 return (K) (parent.keyType == ReferenceStrength.HARD ? key : ((Reference<K>) key).get());
637 }
638
639 /**
640 * Gets the value from the entry.
641 * This method dereferences weak and soft value and thus may return null.
642 *
643 * @return the value, which may be null if it was garbage collected
644 */
645 @Override
646 @SuppressWarnings("unchecked")
647 public V getValue() {
648 return (V) (parent.valueType == ReferenceStrength.HARD ? value : ((Reference<V>) value).get());
649 }
650
651 /**
652 * Sets the value of the entry.
653 *
654 * @param obj the object to store
655 * @return the previous value
656 */
657 @Override
658 @SuppressWarnings("unchecked")
659 public V setValue(final V obj) {
660 final V old = getValue();
661 if (parent.valueType != ReferenceStrength.HARD) {
662 ((Reference<V>) value).clear();
663 }
664 value = toReference(parent.valueType, obj, hashCode);
665 return old;
666 }
667
668 /**
669 * Compares this map entry to another.
670 * <p>
671 * This implementation uses <code>isEqualKey</code> and
672 * <code>isEqualValue</code> on the main map for comparison.
673 *
674 * @param obj the other map entry to compare to
675 * @return true if equal, false if not
676 */
677 @Override
678 public boolean equals(final Object obj) {
679 if (obj == this) {
680 return true;
681 }
682 if (obj instanceof Map.Entry == false) {
683 return false;
684 }
685
686 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>)obj;
687 final Object entryKey = entry.getKey(); // convert to hard reference
688 final Object entryValue = entry.getValue(); // convert to hard reference
689 if (entryKey == null || entryValue == null) {
690 return false;
691 }
692 // compare using map methods, aiding identity subclass
693 // note that key is direct access and value is via method
694 return parent.isEqualKey(entryKey, key) &&
695 parent.isEqualValue(entryValue, getValue());
696 }
697
698 /**
699 * Gets the hashcode of the entry using temporary hard references.
700 * <p>
701 * This implementation uses <code>hashEntry</code> on the main map.
702 *
703 * @return the hashcode of the entry
704 */
705 @Override
706 public int hashCode() {
707 return parent.hashEntry(getKey(), getValue());
708 }
709
710 /**
711 * Constructs a reference of the given type to the given referent.
712 * The reference is registered with the queue for later purging.
713 *
714 * @param <T> the type of the referenced object
715 * @param type HARD, SOFT or WEAK
716 * @param referent the object to refer to
717 * @param hash the hash code of the <i>key</i> of the mapping;
718 * this number might be different from referent.hashCode() if
719 * the referent represents a value and not a key
720 * @return the reference to the object
721 */
722 protected <T> Object toReference(final ReferenceStrength type, final T referent, final int hash) {
723 if (type == ReferenceStrength.HARD) {
724 return referent;
725 }
726 if (type == ReferenceStrength.SOFT) {
727 return new SoftRef<>(hash, referent, parent.queue);
728 }
729 if (type == ReferenceStrength.WEAK) {
730 return new WeakRef<>(hash, referent, parent.queue);
731 }
732 throw new Error();
733 }
734
735 /**
736 * This is the callback for custom "after purge" logic
737 */
738 protected void onPurge() {
739 // empty
740 }
741
742 /**
743 * Purges the specified reference
744 * @param ref the reference to purge
745 * @return true or false
746 */
747 protected boolean purge(final Reference<?> ref) {
748 boolean r = parent.keyType != ReferenceStrength.HARD && key == ref;
749 r = r || parent.valueType != ReferenceStrength.HARD && value == ref;
750 if (r) {
751 if (parent.keyType != ReferenceStrength.HARD) {
752 ((Reference<?>) key).clear();
753 }
754 if (parent.valueType != ReferenceStrength.HARD) {
755 ((Reference<?>) value).clear();
756 } else if (parent.purgeValues) {
757 nullValue();
758 }
759 }
760 return r;
761 }
762
763 /**
764 * Gets the next entry in the bucket.
765 *
766 * @return the next entry in the bucket
767 */
768 protected ReferenceEntry<K, V> next() {
769 return (ReferenceEntry<K, V>) next;
770 }
771
772 /**
773 * This method can be overriden to provide custom logic to purge value
774 */
775 protected void nullValue() {
776 value = null;
777 }
778 }
779
780 //-----------------------------------------------------------------------
781 /**
782 * Base iterator class.
783 */
784 static class ReferenceBaseIterator<K, V> {
785 /** The parent map */
786 final AbstractReferenceMap<K, V> parent;
787
788 // These fields keep track of where we are in the table.
789 int index;
790 ReferenceEntry<K, V> entry;
791 ReferenceEntry<K, V> previous;
792
793 // These Object fields provide hard references to the
794 // current and next entry; this assures that if hasNext()
795 // returns true, next() will actually return a valid element.
796 K currentKey, nextKey;
797 V currentValue, nextValue;
798
799 int expectedModCount;
800
801 public ReferenceBaseIterator(final AbstractReferenceMap<K, V> parent) {
802 super();
803 this.parent = parent;
804 index = parent.size() != 0 ? parent.data.length : 0;
805 // have to do this here! size() invocation above
806 // may have altered the modCount.
807 expectedModCount = parent.modCount;
808 }
809
810 public boolean hasNext() {
811 checkMod();
812 while (nextNull()) {
813 ReferenceEntry<K, V> e = entry;
814 int i = index;
815 while (e == null && i > 0) {
816 i--;
817 e = (ReferenceEntry<K, V>) parent.data[i];
818 }
819 entry = e;
820 index = i;
821 if (e == null) {
822 currentKey = null;
823 currentValue = null;
824 return false;
825 }
826 nextKey = e.getKey();
827 nextValue = e.getValue();
828 if (nextNull()) {
829 entry = entry.next();
830 }
831 }
832 return true;
833 }
834
835 private void checkMod() {
836 if (parent.modCount != expectedModCount) {
837 throw new ConcurrentModificationException();
838 }
839 }
840
841 private boolean nextNull() {
842 return nextKey == null || nextValue == null;
843 }
844
845 protected ReferenceEntry<K, V> nextEntry() {
846 checkMod();
847 if (nextNull() && !hasNext()) {
848 throw new NoSuchElementException();
849 }
850 previous = entry;
851 entry = entry.next();
852 currentKey = nextKey;
853 currentValue = nextValue;
854 nextKey = null;
855 nextValue = null;
856 return previous;
857 }
858
859 protected ReferenceEntry<K, V> currentEntry() {
860 checkMod();
861 return previous;
862 }
863
864 public void remove() {
865 checkMod();
866 if (previous == null) {
867 throw new IllegalStateException();
868 }
869 parent.remove(currentKey);
870 previous = null;
871 currentKey = null;
872 currentValue = null;
873 expectedModCount = parent.modCount;
874 }
875 }
876
877 /**
878 * The EntrySet iterator.
879 */
880 static class ReferenceEntrySetIterator<K, V>
881 extends ReferenceBaseIterator<K, V> implements Iterator<Map.Entry<K, V>> {
882
883 public ReferenceEntrySetIterator(final AbstractReferenceMap<K, V> parent) {
884 super(parent);
885 }
886
887 @Override
888 public Map.Entry<K, V> next() {
889 return nextEntry();
890 }
891
892 }
893
894 /**
895 * The keySet iterator.
896 */
897 static class ReferenceKeySetIterator<K> extends ReferenceBaseIterator<K, Object> implements Iterator<K> {
898
899 @SuppressWarnings("unchecked")
900 ReferenceKeySetIterator(final AbstractReferenceMap<K, ?> parent) {
901 super((AbstractReferenceMap<K, Object>) parent);
902 }
903
904 @Override
905 public K next() {
906 return nextEntry().getKey();
907 }
908 }
909
910 /**
911 * The values iterator.
912 */
913 static class ReferenceValuesIterator<V> extends ReferenceBaseIterator<Object, V> implements Iterator<V> {
914
915 @SuppressWarnings("unchecked")
916 ReferenceValuesIterator(final AbstractReferenceMap<?, V> parent) {
917 super((AbstractReferenceMap<Object, V>) parent);
918 }
919
920 @Override
921 public V next() {
922 return nextEntry().getValue();
923 }
924 }
925
926 /**
927 * The MapIterator implementation.
928 */
929 static class ReferenceMapIterator<K, V> extends ReferenceBaseIterator<K, V> implements MapIterator<K, V> {
930
931 protected ReferenceMapIterator(final AbstractReferenceMap<K, V> parent) {
932 super(parent);
933 }
934
935 @Override
936 public K next() {
937 return nextEntry().getKey();
938 }
939
940 @Override
941 public K getKey() {
942 final HashEntry<K, V> current = currentEntry();
943 if (current == null) {
944 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
945 }
946 return current.getKey();
947 }
948
949 @Override
950 public V getValue() {
951 final HashEntry<K, V> current = currentEntry();
952 if (current == null) {
953 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
954 }
955 return current.getValue();
956 }
957
958 @Override
959 public V setValue(final V value) {
960 final HashEntry<K, V> current = currentEntry();
961 if (current == null) {
962 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
963 }
964 return current.setValue(value);
965 }
966 }
967
968 //-----------------------------------------------------------------------
969 // These two classes store the hashCode of the key of
970 // of the mapping, so that after they're dequeued a quick
971 // lookup of the bucket in the table can occur.
972
973 /**
974 * A soft reference holder.
975 */
976 static class SoftRef<T> extends SoftReference<T> {
977 /** the hashCode of the key (even if the reference points to a value) */
978 private final int hash;
979
980 public SoftRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
981 super(r, q);
982 this.hash = hash;
983 }
984
985 @Override
986 public int hashCode() {
987 return hash;
988 }
989 }
990
991 /**
992 * A weak reference holder.
993 */
994 static class WeakRef<T> extends WeakReference<T> {
995 /** the hashCode of the key (even if the reference points to a value) */
996 private final int hash;
997
998 public WeakRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
999 super(r, q);
1000 this.hash = hash;
1001 }
1002
1003 @Override
1004 public int hashCode() {
1005 return hash;
1006 }
1007 }
1008
1009 //-----------------------------------------------------------------------
1010 /**
1011 * Replaces the superclass method to store the state of this class.
1012 * <p>
1013 * Serialization is not one of the JDK's nicest topics. Normal serialization will
1014 * initialise the superclass before the subclass. Sometimes however, this isn't
1015 * what you want, as in this case the <code>put()</code> method on read can be
1016 * affected by subclass state.
1017 * <p>
1018 * The solution adopted here is to serialize the state data of this class in
1019 * this protected method. This method must be called by the
1020 * <code>writeObject()</code> of the first serializable subclass.
1021 * <p>
1022 * Subclasses may override if they have a specific field that must be present
1023 * on read before this implementation will work. Generally, the read determines
1024 * what must be serialized here, if anything.
1025 *
1026 * @param out the output stream
1027 * @throws IOException if an error occurs while writing to the stream
1028 */
1029 @Override
1030 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
1031 out.writeInt(keyType.value);
1032 out.writeInt(valueType.value);
1033 out.writeBoolean(purgeValues);
1034 out.writeFloat(loadFactor);
1035 out.writeInt(data.length);
1036 for (final MapIterator<K, V> it = mapIterator(); it.hasNext();) {
1037 out.writeObject(it.next());
1038 out.writeObject(it.getValue());
1039 }
1040 out.writeObject(null); // null terminate map
1041 // do not call super.doWriteObject() as code there doesn't work for reference map
1042 }
1043
1044 /**
1045 * Replaces the superclass method to read the state of this class.
1046 * <p>
1047 * Serialization is not one of the JDK's nicest topics. Normal serialization will
1048 * initialise the superclass before the subclass. Sometimes however, this isn't
1049 * what you want, as in this case the <code>put()</code> method on read can be
1050 * affected by subclass state.
1051 * <p>
1052 * The solution adopted here is to deserialize the state data of this class in
1053 * this protected method. This method must be called by the
1054 * <code>readObject()</code> of the first serializable subclass.
1055 * <p>
1056 * Subclasses may override if the subclass has a specific field that must be present
1057 * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1058 *
1059 * @param in the input stream
1060 * @throws IOException if an error occurs while reading from the stream
1061 * @throws ClassNotFoundException if an object read from the stream can not be loaded
1062 */
1063 @Override
1064 @SuppressWarnings("unchecked")
1065 protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
1066 this.keyType = ReferenceStrength.resolve(in.readInt());
1067 this.valueType = ReferenceStrength.resolve(in.readInt());
1068 this.purgeValues = in.readBoolean();
1069 this.loadFactor = in.readFloat();
1070 final int capacity = in.readInt();
1071 init();
1072 data = new HashEntry[capacity];
1073
1074 // COLLECTIONS-599: Calculate threshold before populating, otherwise it will be 0
1075 // when it hits AbstractHashedMap.checkCapacity() and so will unnecessarily
1076 // double up the size of the "data" array during population.
1077 //
1078 // NB: AbstractHashedMap.doReadObject() DOES calculate the threshold before populating.
1079 //
1080 threshold = calculateThreshold(data.length, loadFactor);
1081
1082 while (true) {
1083 final K key = (K) in.readObject();
1084 if (key == null) {
1085 break;
1086 }
1087 final V value = (V) in.readObject();
1088 put(key, value);
1089 }
1090 // do not call super.doReadObject() as code there doesn't work for reference map
1091 }
1092
1093 /**
1094 * Provided protected read-only access to the key type.
1095 * @param type the type to check against.
1096 * @return true if keyType has the specified type
1097 */
1098 protected boolean isKeyType(final ReferenceStrength type) {
1099 return this.keyType == type;
1100 }
1101
1102 /**
1103 * Provided protected read-only access to the value type.
1104 * @param type the type to check against.
1105 * @return true if valueType has the specified type
1106 */
1107 protected boolean isValueType(final ReferenceStrength type) {
1108 return this.valueType == type;
1109 }
1110 }
1111