1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.Objects;
34 import java.util.Set;
35
36 import org.apache.commons.collections4.MapIterator;
37 import org.apache.commons.collections4.keyvalue.DefaultMapEntry;
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92 public abstract class AbstractReferenceMap<K, V> extends AbstractHashedMap<K, V> {
93
94
95
96
97 static class ReferenceBaseIterator<K, V> {
98
99 final AbstractReferenceMap<K, V> parent;
100
101
102 int index;
103 ReferenceEntry<K, V> next;
104 ReferenceEntry<K, V> current;
105
106
107
108
109 K currentKey, nextKey;
110 V currentValue, nextValue;
111
112 int expectedModCount;
113
114 ReferenceBaseIterator(final AbstractReferenceMap<K, V> parent) {
115 this.parent = parent;
116 index = !parent.isEmpty() ? parent.data.length : 0;
117
118
119 expectedModCount = parent.modCount;
120 }
121
122 private void checkMod() {
123 if (parent.modCount != expectedModCount) {
124 throw new ConcurrentModificationException();
125 }
126 }
127
128 protected ReferenceEntry<K, V> currentEntry() {
129 checkMod();
130 return current;
131 }
132
133 public boolean hasNext() {
134 checkMod();
135 while (nextNull()) {
136 ReferenceEntry<K, V> e = next;
137 int i = index;
138 while (e == null && i > 0) {
139 i--;
140 e = (ReferenceEntry<K, V>) parent.data[i];
141 }
142 next = e;
143 index = i;
144 if (e == null) {
145 return false;
146 }
147 nextKey = e.getKey();
148 nextValue = e.getValue();
149 if (nextNull()) {
150 next = next.next();
151 }
152 }
153 return true;
154 }
155
156 protected ReferenceEntry<K, V> nextEntry() {
157 checkMod();
158 if (nextNull() && !hasNext()) {
159 throw new NoSuchElementException();
160 }
161 current = next;
162 next = next.next();
163 currentKey = nextKey;
164 currentValue = nextValue;
165 nextKey = null;
166 nextValue = null;
167 return current;
168 }
169
170 private boolean nextNull() {
171 return nextKey == null || nextValue == null;
172 }
173
174 public void remove() {
175 checkMod();
176 if (current == null) {
177 throw new IllegalStateException();
178 }
179 parent.remove(currentKey);
180 current = null;
181 currentKey = null;
182 currentValue = null;
183 expectedModCount = parent.modCount;
184 }
185 }
186
187
188
189
190
191
192
193
194
195
196
197
198 protected static class ReferenceEntry<K, V> extends HashEntry<K, V> {
199
200 private final AbstractReferenceMap<K, V> parent;
201
202
203
204
205
206
207
208
209
210
211 public ReferenceEntry(final AbstractReferenceMap<K, V> parent, final HashEntry<K, V> next,
212 final int hashCode, final K key, final V value) {
213 super(next, hashCode, null, null);
214 this.parent = parent;
215 this.key = toReference(parent.keyType, key, hashCode);
216 this.value = toReference(parent.valueType, value, hashCode);
217 }
218
219
220
221
222
223
224
225
226
227
228 @Override
229 public boolean equals(final Object obj) {
230 if (obj == this) {
231 return true;
232 }
233 if (!(obj instanceof Map.Entry)) {
234 return false;
235 }
236
237 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
238 final Object entryKey = entry.getKey();
239 final Object entryValue = entry.getValue();
240 if (entryKey == null || entryValue == null) {
241 return false;
242 }
243
244
245 return parent.isEqualKey(entryKey, key) &&
246 parent.isEqualValue(entryValue, getValue());
247 }
248
249
250
251
252
253
254
255 @Override
256 @SuppressWarnings("unchecked")
257 public K getKey() {
258 return (K) (parent.keyType == ReferenceStrength.HARD ? key : ((Reference<K>) key).get());
259 }
260
261
262
263
264
265
266
267 @Override
268 @SuppressWarnings("unchecked")
269 public V getValue() {
270 return (V) (parent.valueType == ReferenceStrength.HARD ? value : ((Reference<V>) value).get());
271 }
272
273
274
275
276
277
278
279
280 @Override
281 public int hashCode() {
282 return parent.hashEntry(getKey(), getValue());
283 }
284
285
286
287
288
289
290 protected ReferenceEntry<K, V> next() {
291 return (ReferenceEntry<K, V>) next;
292 }
293
294
295
296
297 protected void nullValue() {
298 value = null;
299 }
300
301
302
303
304 protected void onPurge() {
305
306 }
307
308
309
310
311
312
313 protected boolean purge(final Reference<?> ref) {
314 boolean r = parent.keyType != ReferenceStrength.HARD && key == ref;
315 r = r || parent.valueType != ReferenceStrength.HARD && value == ref;
316 if (r) {
317 if (parent.keyType != ReferenceStrength.HARD) {
318 ((Reference<?>) key).clear();
319 }
320 if (parent.valueType != ReferenceStrength.HARD) {
321 ((Reference<?>) value).clear();
322 } else if (parent.purgeValues) {
323 nullValue();
324 }
325 }
326 return r;
327 }
328
329
330
331
332
333
334
335 @Override
336 @SuppressWarnings("unchecked")
337 public V setValue(final V obj) {
338 final V old = getValue();
339 if (parent.valueType != ReferenceStrength.HARD) {
340 ((Reference<V>) value).clear();
341 }
342 value = toReference(parent.valueType, obj, hashCode);
343 return old;
344 }
345
346
347
348
349
350
351
352
353
354
355
356
357
358 protected <T> Object toReference(final ReferenceStrength type, final T referent, final int hash) {
359 if (type == ReferenceStrength.HARD) {
360 return referent;
361 }
362 if (type == ReferenceStrength.SOFT) {
363 return new SoftRef<>(hash, referent, parent.queue);
364 }
365 if (type == ReferenceStrength.WEAK) {
366 return new WeakRef<>(hash, referent, parent.queue);
367 }
368 throw new Error();
369 }
370 }
371
372
373
374
375 static class ReferenceEntrySet<K, V> extends EntrySet<K, V> {
376
377 protected ReferenceEntrySet(final AbstractHashedMap<K, V> parent) {
378 super(parent);
379 }
380
381 @Override
382 public Object[] toArray() {
383 return toArray(new Object[size()]);
384 }
385
386 @Override
387 public <T> T[] toArray(final T[] arr) {
388
389 final ArrayList<Map.Entry<K, V>> list = new ArrayList<>(size());
390 for (final Map.Entry<K, V> entry : this) {
391 list.add(new DefaultMapEntry<>(entry));
392 }
393 return list.toArray(arr);
394 }
395 }
396
397
398
399
400 static class ReferenceEntrySetIterator<K, V>
401 extends ReferenceBaseIterator<K, V> implements Iterator<Map.Entry<K, V>> {
402
403 ReferenceEntrySetIterator(final AbstractReferenceMap<K, V> parent) {
404 super(parent);
405 }
406
407 @Override
408 public Map.Entry<K, V> next() {
409 return nextEntry();
410 }
411
412 }
413
414
415
416
417 static class ReferenceKeySet<K> extends KeySet<K> {
418
419 protected ReferenceKeySet(final AbstractHashedMap<K, ?> parent) {
420 super(parent);
421 }
422
423 @Override
424 public Object[] toArray() {
425 return toArray(new Object[size()]);
426 }
427
428 @Override
429 public <T> T[] toArray(final T[] arr) {
430
431 final List<K> list = new ArrayList<>(size());
432 for (final K key : this) {
433 list.add(key);
434 }
435 return list.toArray(arr);
436 }
437 }
438
439
440
441
442 static class ReferenceKeySetIterator<K> extends ReferenceBaseIterator<K, Object> implements Iterator<K> {
443
444 @SuppressWarnings("unchecked")
445 ReferenceKeySetIterator(final AbstractReferenceMap<K, ?> parent) {
446 super((AbstractReferenceMap<K, Object>) parent);
447 }
448
449 @Override
450 public K next() {
451 return nextEntry().getKey();
452 }
453 }
454
455
456
457
458 static class ReferenceMapIterator<K, V> extends ReferenceBaseIterator<K, V> implements MapIterator<K, V> {
459
460 protected ReferenceMapIterator(final AbstractReferenceMap<K, V> parent) {
461 super(parent);
462 }
463
464 @Override
465 public K getKey() {
466 final HashEntry<K, V> current = currentEntry();
467 if (current == null) {
468 throw new IllegalStateException(GETKEY_INVALID);
469 }
470 return current.getKey();
471 }
472
473 @Override
474 public V getValue() {
475 final HashEntry<K, V> current = currentEntry();
476 if (current == null) {
477 throw new IllegalStateException(GETVALUE_INVALID);
478 }
479 return current.getValue();
480 }
481
482 @Override
483 public K next() {
484 return nextEntry().getKey();
485 }
486
487 @Override
488 public V setValue(final V value) {
489 final HashEntry<K, V> current = currentEntry();
490 if (current == null) {
491 throw new IllegalStateException(SETVALUE_INVALID);
492 }
493 return current.setValue(value);
494 }
495 }
496
497
498
499
500 public enum ReferenceStrength {
501 HARD(0), SOFT(1), WEAK(2);
502
503
504
505
506
507
508
509 public static ReferenceStrength resolve(final int value) {
510 switch (value) {
511 case 0:
512 return HARD;
513 case 1:
514 return SOFT;
515 case 2:
516 return WEAK;
517 default:
518 throw new IllegalArgumentException();
519 }
520 }
521
522
523 public final int value;
524
525 ReferenceStrength(final int value) {
526 this.value = value;
527 }
528
529 }
530
531
532
533
534 static class ReferenceValues<V> extends Values<V> {
535
536 protected ReferenceValues(final AbstractHashedMap<?, V> parent) {
537 super(parent);
538 }
539
540 @Override
541 public Object[] toArray() {
542 return toArray(new Object[size()]);
543 }
544
545 @Override
546 public <T> T[] toArray(final T[] arr) {
547
548 final List<V> list = new ArrayList<>(size());
549 for (final V value : this) {
550 list.add(value);
551 }
552 return list.toArray(arr);
553 }
554 }
555
556
557
558
559 static class ReferenceValuesIterator<V> extends ReferenceBaseIterator<Object, V> implements Iterator<V> {
560
561 @SuppressWarnings("unchecked")
562 ReferenceValuesIterator(final AbstractReferenceMap<?, V> parent) {
563 super((AbstractReferenceMap<Object, V>) parent);
564 }
565
566 @Override
567 public V next() {
568 return nextEntry().getValue();
569 }
570 }
571
572
573
574
575 static class SoftRef<T> extends SoftReference<T> {
576
577 private final int hash;
578
579 SoftRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
580 super(r, q);
581 this.hash = hash;
582 }
583
584 @Override
585 public boolean equals(final Object obj) {
586 if (this == obj) {
587 return true;
588 }
589 if (obj == null) {
590 return false;
591 }
592 if (getClass() != obj.getClass()) {
593 return false;
594 }
595 final SoftRef<?> other = (SoftRef<?>) obj;
596 return hash == other.hash;
597 }
598
599 @Override
600 public int hashCode() {
601 return hash;
602 }
603 }
604
605
606
607
608 static class WeakRef<T> extends WeakReference<T> {
609
610 private final int hash;
611
612 WeakRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
613 super(r, q);
614 this.hash = hash;
615 }
616
617 @Override
618 public boolean equals(final Object obj) {
619 if (this == obj) {
620 return true;
621 }
622 if (obj == null) {
623 return false;
624 }
625 if (getClass() != obj.getClass()) {
626 return false;
627 }
628 final WeakRef<?> other = (WeakRef<?>) obj;
629 return hash == other.hash;
630 }
631
632 @Override
633 public int hashCode() {
634 return hash;
635 }
636 }
637
638
639
640
641 private ReferenceStrength keyType;
642
643
644
645
646 private ReferenceStrength valueType;
647
648
649
650
651 private boolean purgeValues;
652
653
654
655
656
657 private transient ReferenceQueue<Object> queue;
658
659
660
661
662 protected AbstractReferenceMap() {
663 }
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682 protected AbstractReferenceMap(
683 final ReferenceStrength keyType, final ReferenceStrength valueType, final int capacity,
684 final float loadFactor, final boolean purgeValues) {
685 super(capacity, loadFactor);
686 this.keyType = keyType;
687 this.valueType = valueType;
688 this.purgeValues = purgeValues;
689 }
690
691
692
693
694 @Override
695 public void clear() {
696 super.clear();
697
698 while (queue.poll() != null) {
699 }
700 }
701
702
703
704
705
706
707
708 @Override
709 public boolean containsKey(final Object key) {
710 purgeBeforeRead();
711 final Entry<K, V> entry = getEntry(key);
712 if (entry == null) {
713 return false;
714 }
715 return entry.getValue() != null;
716 }
717
718
719
720
721
722
723
724 @Override
725 public boolean containsValue(final Object value) {
726 purgeBeforeRead();
727 if (value == null) {
728 return false;
729 }
730 return super.containsValue(value);
731 }
732
733
734
735
736
737
738
739
740
741
742 @Override
743 protected ReferenceEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode,
744 final K key, final V value) {
745 return new ReferenceEntry<>(this, next, hashCode, key, value);
746 }
747
748
749
750
751
752
753 @Override
754 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
755 return new ReferenceEntrySetIterator<>(this);
756 }
757
758
759
760
761
762
763 @Override
764 protected Iterator<K> createKeySetIterator() {
765 return new ReferenceKeySetIterator<>(this);
766 }
767
768
769
770
771
772
773 @Override
774 protected Iterator<V> createValuesIterator() {
775 return new ReferenceValuesIterator<>(this);
776 }
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797 @Override
798 @SuppressWarnings("unchecked")
799 protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
800 this.keyType = ReferenceStrength.resolve(in.readInt());
801 this.valueType = ReferenceStrength.resolve(in.readInt());
802 this.purgeValues = in.readBoolean();
803 this.loadFactor = in.readFloat();
804 final int capacity = in.readInt();
805 init();
806 data = new HashEntry[capacity];
807
808
809
810
811
812
813
814 threshold = calculateThreshold(data.length, loadFactor);
815
816 while (true) {
817 final K key = (K) in.readObject();
818 if (key == null) {
819 break;
820 }
821 final V value = (V) in.readObject();
822 put(key, value);
823 }
824
825 }
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846 @Override
847 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
848 out.writeInt(keyType.value);
849 out.writeInt(valueType.value);
850 out.writeBoolean(purgeValues);
851 out.writeFloat(loadFactor);
852 out.writeInt(data.length);
853 for (final MapIterator<K, V> it = mapIterator(); it.hasNext();) {
854 out.writeObject(it.next());
855 out.writeObject(it.getValue());
856 }
857 out.writeObject(null);
858
859 }
860
861
862
863
864
865
866
867
868 @Override
869 public Set<Map.Entry<K, V>> entrySet() {
870 if (entrySet == null) {
871 entrySet = new ReferenceEntrySet<>(this);
872 }
873 return entrySet;
874 }
875
876
877
878
879
880
881
882 @Override
883 public V get(final Object key) {
884 purgeBeforeRead();
885 final Entry<K, V> entry = getEntry(key);
886 if (entry == null) {
887 return null;
888 }
889 return entry.getValue();
890 }
891
892
893
894
895
896
897
898 @Override
899 protected HashEntry<K, V> getEntry(final Object key) {
900 if (key == null) {
901 return null;
902 }
903 return super.getEntry(key);
904 }
905
906
907
908
909
910
911
912
913
914 protected int hashEntry(final Object key, final Object value) {
915 return (key == null ? 0 : key.hashCode()) ^
916 (value == null ? 0 : value.hashCode());
917 }
918
919
920
921
922 @Override
923 protected void init() {
924 queue = new ReferenceQueue<>();
925 }
926
927
928
929
930
931
932 @Override
933 public boolean isEmpty() {
934 purgeBeforeRead();
935 return super.isEmpty();
936 }
937
938
939
940
941
942
943
944
945
946
947
948 @Override
949 @SuppressWarnings("unchecked")
950 protected boolean isEqualKey(final Object key1, Object key2) {
951 key2 = keyType == ReferenceStrength.HARD ? key2 : ((Reference<K>) key2).get();
952 return key1 == key2 || key1.equals(key2);
953 }
954
955
956
957
958
959
960 protected boolean isKeyType(final ReferenceStrength type) {
961 return this.keyType == type;
962 }
963
964
965
966
967
968
969 protected boolean isValueType(final ReferenceStrength type) {
970 return this.valueType == type;
971 }
972
973
974
975
976
977
978 @Override
979 public Set<K> keySet() {
980 if (keySet == null) {
981 keySet = new ReferenceKeySet<>(this);
982 }
983 return keySet;
984 }
985
986
987
988
989
990
991
992 @Override
993 public MapIterator<K, V> mapIterator() {
994 return new ReferenceMapIterator<>(this);
995 }
996
997
998
999
1000
1001
1002
1003
1004
1005 protected void purge() {
1006 Reference<?> ref = queue.poll();
1007 while (ref != null) {
1008 purge(ref);
1009 ref = queue.poll();
1010 }
1011 }
1012
1013
1014
1015
1016
1017
1018 protected void purge(final Reference<?> ref) {
1019
1020
1021
1022 final int hash = ref.hashCode();
1023 final int index = hashIndex(hash, data.length);
1024 HashEntry<K, V> previous = null;
1025 HashEntry<K, V> entry = data[index];
1026 while (entry != null) {
1027 final ReferenceEntry<K, V> refEntry = (ReferenceEntry<K, V>) entry;
1028 if (refEntry.purge(ref)) {
1029 if (previous == null) {
1030 data[index] = entry.next;
1031 } else {
1032 previous.next = entry.next;
1033 }
1034 this.size--;
1035 refEntry.onPurge();
1036 return;
1037 }
1038 previous = entry;
1039 entry = entry.next;
1040 }
1041
1042 }
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053 protected void purgeBeforeRead() {
1054 purge();
1055 }
1056
1057
1058
1059
1060
1061
1062 protected void purgeBeforeWrite() {
1063 purge();
1064 }
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075 @Override
1076 public V put(final K key, final V value) {
1077 Objects.requireNonNull(key, "key");
1078 Objects.requireNonNull(value, "value");
1079 purgeBeforeWrite();
1080 return super.put(key, value);
1081 }
1082
1083
1084
1085
1086
1087
1088
1089 @Override
1090 public V remove(final Object key) {
1091 if (key == null) {
1092 return null;
1093 }
1094 purgeBeforeWrite();
1095 return super.remove(key);
1096 }
1097
1098
1099
1100
1101
1102
1103 @Override
1104 public int size() {
1105 purgeBeforeRead();
1106 return super.size();
1107 }
1108
1109
1110
1111
1112
1113
1114 @Override
1115 public Collection<V> values() {
1116 if (values == null) {
1117 values = new ReferenceValues<>(this);
1118 }
1119 return values;
1120 }
1121 }