CAY-2351 Remove commons-collections usage completely Own ReferenceMap implementation
Project: http://git-wip-us.apache.org/repos/asf/cayenne/repo Commit: http://git-wip-us.apache.org/repos/asf/cayenne/commit/bc7399a3 Tree: http://git-wip-us.apache.org/repos/asf/cayenne/tree/bc7399a3 Diff: http://git-wip-us.apache.org/repos/asf/cayenne/diff/bc7399a3 Branch: refs/heads/master Commit: bc7399a313b4fa55f3f083106cbe2012c9397e97 Parents: 4e623e3 Author: Nikita Timofeev <stari...@gmail.com> Authored: Thu Aug 10 18:27:21 2017 +0300 Committer: Nikita Timofeev <stari...@gmail.com> Committed: Thu Aug 17 12:41:57 2017 +0300 ---------------------------------------------------------------------- .../org/apache/cayenne/util/ReferenceMap.java | 135 ++++++++++-- .../apache/cayenne/util/WeakValueMapTest.java | 203 +++++++++++++++++++ 2 files changed, 321 insertions(+), 17 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cayenne/blob/bc7399a3/cayenne-server/src/main/java/org/apache/cayenne/util/ReferenceMap.java ---------------------------------------------------------------------- diff --git a/cayenne-server/src/main/java/org/apache/cayenne/util/ReferenceMap.java b/cayenne-server/src/main/java/org/apache/cayenne/util/ReferenceMap.java index e441f86..530ea30 100644 --- a/cayenne-server/src/main/java/org/apache/cayenne/util/ReferenceMap.java +++ b/cayenne-server/src/main/java/org/apache/cayenne/util/ReferenceMap.java @@ -25,34 +25,69 @@ import java.io.ObjectOutputStream; import java.io.Serializable; import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; +import java.util.AbstractMap; +import java.util.AbstractSet; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; +import java.util.Iterator; import java.util.Map; import java.util.Set; /** * Map that transparently stores values as references and resolves them as needed. + * Though this implementation try to follow general {@link Map} contract (including equals() and hashCode()) + * it is not intended for general usage. * <p> - * This implementation supports serialization. + * There is no HardReferenceMap as simple HashMap can be used for that. * <p> - * Internally data stored in HashMap thus this class and all implementations are not thread safe. + * This map doesn't guaranties that value will be there even right after put(), as GC can remove it at any time. + * <p> + * This implementation supports proper serialization, concrete classes should use {@link #writeObjectInternal(ObjectOutputStream)} + * and {@link #readObjectInternal(ObjectInputStream)} methods to support it too. + * <p> + * + * @param <K> key type + * @param <V> value type + * @param <R> reference type that will be used to store values * - * @see WeakValueMap - * @see SoftValueMap + * @see WeakValueMap implementation that uses WeakReference to store values + * @see SoftValueMap implementation that uses SoftReference to store values * * @since 4.1 */ -public abstract class ReferenceMap<K, V, R extends Reference<V>> implements Map<K, V>, Serializable { +abstract class ReferenceMap<K, V, R extends Reference<V>> extends AbstractMap<K, V> implements Serializable { + + /* + * Implementation notes: + * - internally data stored in HashMap thus this class and all implementations are not thread safe; + * - to track references that were cleared ReferenceQueue is used; + * - this map stores not only direct key => ref map but also a reverse ref => key to be able + * effectively clear data that was removed by GC; + * - this map is abstract, all that required for the concrete implementation is + * to define newReference(Object) method; + * - all accessors/modifiers should call checkReferenceQueue() to clear all stale data + */ private static final long serialVersionUID = -3365744592038165092L; + /** + * This is a main data storage used for most operations + */ protected transient Map<K, R> map; + /** + * This is aux storage to faster remove cleared references + */ protected transient Map<R, K> reverseMap; protected transient ReferenceQueue<V> referenceQueue; + /** + * This is a lazily created set of entries that is essentially a view to actual data + */ + protected transient Set<Entry<K, V>> entrySet; + public ReferenceMap() { map = new HashMap<>(); reverseMap = new HashMap<>(); @@ -163,13 +198,12 @@ public abstract class ReferenceMap<K, V, R extends Reference<V>> implements Map< @Override public Collection<V> values() { checkReferenceQueue(); - Collection<V> values = new ArrayList<>(); - for(R v : map.values()) { + // this can be optimized by creating view instead of new heavyweight collection + Collection<R> referenceValues = map.values(); + Collection<V> values = new ArrayList<>(referenceValues.size()); + for(R v : referenceValues) { if(v != null) { - V value = v.get(); - if(value != null) { - values.add(value); - } + values.add(v.get()); } } return values; @@ -177,11 +211,17 @@ public abstract class ReferenceMap<K, V, R extends Reference<V>> implements Map< @Override public Set<Entry<K, V>> entrySet() { - throw new UnsupportedOperationException(); + checkReferenceQueue(); + // lazily create entry set view + Set<Entry<K, V>> es = entrySet; + if(es == null) { + entrySet = es = new ReferenceEntrySet(); + } + return es; } /** - * Cleanup all collected references + * Cleanup all references collected by GC so far */ protected void checkReferenceQueue() { Reference<? extends V> reference; @@ -212,7 +252,6 @@ public abstract class ReferenceMap<K, V, R extends Reference<V>> implements Map< writeObjectInternal(out); } - @SuppressWarnings("unchecked") private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { readObjectInternal(in); } @@ -235,8 +274,70 @@ public abstract class ReferenceMap<K, V, R extends Reference<V>> implements Map< reverseMap = new HashMap<>(replacement.size()); referenceQueue = new ReferenceQueue<>(); putAll(replacement); - map.forEach((k, v) -> { - reverseMap.put(v, k); - }); + map.forEach((k, v) -> reverseMap.put(v, k)); + } + + /** + * View over {@link #map} entry set + */ + class ReferenceEntrySet extends AbstractSet<Entry<K, V>> { + + @Override + public Iterator<Entry<K, V>> iterator() { + return new ReferenceEntryIterator(); + } + + @Override + public int size() { + return map.size(); + } + } + + /** + * Iterator used by entrySet. Wrapper around {@link #map} iterator + */ + class ReferenceEntryIterator implements Iterator<Entry<K, V>> { + + Iterator<Entry<K, R>> internalIterator; + + ReferenceEntryIterator() { + internalIterator = map.entrySet().iterator(); + } + + @Override + public boolean hasNext() { + return internalIterator.hasNext(); + } + + @Override + public Entry<K, V> next() { + return new ReferenceEntry(internalIterator.next()); + } + } + + /** + * View over {@link Map.Entry} that transparently resolves Reference + */ + class ReferenceEntry extends SimpleEntry<K, V> { + + private static final long serialVersionUID = -1795136249842496011L; + + Entry<K, R> refEntry; + + public ReferenceEntry(Entry<K, R> refEntry) { + super(refEntry.getKey(), refEntry.getValue() != null ? refEntry.getValue().get() : null); + this.refEntry = refEntry; + } + + @Override + public V setValue(V value) { + R newRef = newReference(value); + R oldRef = refEntry.setValue(newRef); + reverseMap.put(newRef, reverseMap.remove(oldRef)); + if(oldRef != null) { + return oldRef.get(); + } + return null; + } } } http://git-wip-us.apache.org/repos/asf/cayenne/blob/bc7399a3/cayenne-server/src/test/java/org/apache/cayenne/util/WeakValueMapTest.java ---------------------------------------------------------------------- diff --git a/cayenne-server/src/test/java/org/apache/cayenne/util/WeakValueMapTest.java b/cayenne-server/src/test/java/org/apache/cayenne/util/WeakValueMapTest.java new file mode 100644 index 0000000..e5a29f6 --- /dev/null +++ b/cayenne-server/src/test/java/org/apache/cayenne/util/WeakValueMapTest.java @@ -0,0 +1,203 @@ +/***************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + ****************************************************************/ + +package org.apache.cayenne.util; + +import java.util.ConcurrentModificationException; +import java.util.HashMap; +import java.util.Iterator; +import java.util.Map; + +import org.junit.Test; + +import static org.junit.Assert.*; + +/** + * As WeakValueMap and SoftValueMap share almost all code from their super class + * only one test is present for both of them. + * + * @since 4.1 + */ +public class WeakValueMapTest { + + @Test + public void testEmptyConstructor() { + Map<String, Integer> map = new WeakValueMap<>(); + + assertTrue(map.isEmpty()); + assertEquals(0, map.size()); + assertFalse(map.containsKey("nonexistent_key1")); + assertFalse(map.containsValue(42)); + assertNull(map.get("nonexistent_key2")); + assertEquals(new Integer(42), map.getOrDefault("nonexistent_key2", 42)); + + assertEquals(0, map.values().size()); + assertEquals(0, map.keySet().size()); + assertEquals(0, map.entrySet().size()); + } + + @Test + public void testCapacityConstructor() { + Map<String, Integer> map = new WeakValueMap<>(42); + + assertTrue(map.isEmpty()); + assertEquals(0, map.size()); + assertFalse(map.containsKey("nonexistent_key1")); + assertFalse(map.containsValue(42)); + assertNull(map.get("nonexistent_key2")); + assertEquals(new Integer(42), map.getOrDefault("nonexistent_key2", 42)); + + assertEquals(0, map.values().size()); + assertEquals(0, map.keySet().size()); + assertEquals(0, map.entrySet().size()); + } + + @Test + public void testMapConstructor() { + Map<String, Integer> data = new HashMap<>(); + data.put("key_1", 123); + data.put("key_2", 42); + data.put("key_3", null); + + Map<String, Integer> map = new WeakValueMap<>(data); + + assertFalse(map.isEmpty()); + assertEquals(data.size(), map.size()); + assertFalse(map.containsKey("nonexistent_key1")); + assertTrue(map.containsKey("key_3")); + assertFalse(map.containsValue(321)); + assertTrue(map.containsValue(42)); + assertNull(map.get("nonexistent_key2")); + assertNull(map.get("key_3")); + assertEquals(new Integer(123), map.getOrDefault("key_1", 42)); + + assertEquals(data.size(), map.values().size()); + assertEquals(data.size(), map.keySet().size()); + assertEquals(data.size(), map.entrySet().size()); + + assertTrue(map.values().containsAll(data.values())); + assertTrue(map.keySet().containsAll(data.keySet())); + assertTrue(map.entrySet().containsAll(data.entrySet())); + } + + @Test + public void testSimpleOperations() { + Map<String, Integer> data = new HashMap<>(); + data.put("key_1", 123); + data.put("key_2", 42); + data.put("key_3", null); + + Map<String, Integer> map = new WeakValueMap<>(data); + + map.put("key_4", 44); + assertEquals(new Integer(44), map.get("key_4")); + assertEquals(4, map.size()); + assertTrue(map.containsKey("key_4")); + assertTrue(map.containsValue(44)); + + int old = map.remove("key_4"); + assertEquals(44, old); + assertEquals(3, map.size()); + assertFalse(map.containsKey("key_4")); + assertFalse(map.containsValue(44)); + } + + @Test + public void testEntrySetUpdateValue() { + Map<String, Integer> map = new WeakValueMap<>(); + map.put("key_1", 123); + map.put("key_2", 42); + map.put("key_3", null); + assertEquals(3, map.size()); + + int counter = 0; + for(Map.Entry<String, Integer> entry : map.entrySet()) { + if("key_2".equals(entry.getKey())) { + int old = entry.setValue(24); + assertEquals(42, old); + } + counter++; + } + + assertEquals(3, counter); + assertEquals(new Integer(24), map.get("key_2")); + } + + @Test + public void testSerializationSupport() throws Exception { + WeakValueMap<String, Integer> map = new WeakValueMap<>(); + map.put("key_1", 123); + map.put("key_2", 42); + map.put("key_3", null); + assertEquals(3, map.size()); + + WeakValueMap<String, Integer> clone = Util.cloneViaSerialization(map); + + assertEquals(3, clone.size()); + assertEquals(new Integer(42), clone.get("key_2")); + assertTrue(clone.containsKey("key_3")); + assertTrue(clone.containsValue(123)); + } + + @Test + public void testEqualsAndHashCode() throws Exception { + Map<String, Integer> map1 = new WeakValueMap<>(); + map1.put("key_1", 123); + map1.put("key_2", 42); + map1.put("key_3", null); + assertEquals(3, map1.size()); + + Map<String, Integer> map2 = new HashMap<>(); + map2.put("key_1", 123); + map2.put("key_2", 42); + map2.put("key_3", null); + + assertEquals(map1, map2); + assertEquals(map1.hashCode(), map2.hashCode()); + } + + @Test(expected = ConcurrentModificationException.class) + public void testConcurrentModification() { + Map<String, Integer> map = new WeakValueMap<>(3); + map.put("key_1", 123); + map.put("key_2", 42); + map.put("key_3", null); + assertEquals(3, map.size()); + + for(Map.Entry<String, Integer> entry : map.entrySet()) { + if("key_2".equals(entry.getKey())) { + map.remove("key_2"); + } + } + } + + @Test(expected = UnsupportedOperationException.class) + public void testUnsupportedEntryIteratorRemoval() { + Map<String, Integer> map = new WeakValueMap<>(3); + map.put("key_1", 123); + map.put("key_2", 42); + map.put("key_3", null); + assertEquals(3, map.size()); + + Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator(); + while(iterator.hasNext()) { + iterator.remove(); + } + } +} \ No newline at end of file