| /* |
| * 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.openjpa.util; |
| |
| import java.util.AbstractCollection; |
| import java.util.AbstractSet; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Iterator; |
| import java.util.Map; |
| import java.util.Set; |
| import java.util.concurrent.locks.Lock; |
| import java.util.concurrent.locks.ReentrantReadWriteLock; |
| import java.util.function.Predicate; |
| |
| import org.apache.openjpa.lib.util.LRUMap; |
| import org.apache.openjpa.lib.util.SizedMap; |
| import org.apache.openjpa.lib.util.collections.AbstractReferenceMap; |
| import org.apache.openjpa.lib.util.collections.FilterIterator; |
| import org.apache.openjpa.lib.util.collections.IteratorChain; |
| import org.apache.openjpa.lib.util.concurrent.ConcurrentHashMap; |
| import org.apache.openjpa.lib.util.concurrent.ConcurrentReferenceHashMap; |
| |
| /** |
| * Fixed-size map that has ability to pin/unpin entries and move overflow to |
| * a backing soft map. |
| * |
| * @author Patrick Linskey |
| * @author Abe White |
| */ |
| public class CacheMap |
| implements Map { |
| |
| /** |
| * The map for non-expired and non-pinned references. |
| */ |
| protected final SizedMap cacheMap; |
| |
| /** |
| * The map for expired references. |
| */ |
| protected final SizedMap softMap; |
| |
| /** |
| * The set of objects pinned into the cache. |
| */ |
| protected final Map pinnedMap; |
| |
| // number of pinned values (not including keys not mapped to values) |
| private int _pinnedSize = 0; |
| |
| private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(true); |
| private final Lock _readLock = rwl.readLock(); |
| private final Lock _writeLock = rwl.writeLock(); |
| |
| /** |
| * Create a non-LRU (and therefore highly concurrent) cache map with a |
| * size of 1000. |
| */ |
| public CacheMap() { |
| this(false, 1000); |
| } |
| |
| /** |
| * Create a cache map with a size of 1000. |
| * |
| * @param lru if true, create a LRU cache map otherwise a non-LRU map will be created. |
| */ |
| public CacheMap(boolean lru) { |
| this(lru, 1000); |
| } |
| |
| /** |
| * Create a cache map with the given properties. |
| */ |
| public CacheMap(boolean lru, int max) { |
| this(lru, max, max / 2, .75F); |
| } |
| |
| /** |
| * @deprecated use {@link CacheMap#CacheMap(boolean, int, int, float, int)} |
| * instead. |
| */ |
| @Deprecated |
| public CacheMap(boolean lru, int max, int size, float load) { |
| this(lru, max, size, load, 16); |
| } |
| |
| /** |
| * Create a cache map with the given properties. |
| * |
| * @since 1.1.0 |
| */ |
| public CacheMap(boolean lru, int max, int size, float load, |
| int concurrencyLevel) { |
| if (size < 0) |
| size = 500; |
| |
| softMap = new ConcurrentReferenceHashMap(AbstractReferenceMap.ReferenceStrength.HARD, |
| AbstractReferenceMap.ReferenceStrength.SOFT, size, load) { |
| @Override |
| public void overflowRemoved(Object key, Object value) { |
| softMapOverflowRemoved(key, value); |
| } |
| |
| @Override |
| public void valueExpired(Object key) { |
| softMapValueExpired(key); |
| } |
| }; |
| pinnedMap = new ConcurrentHashMap(); |
| |
| if (!lru) { |
| cacheMap = new ConcurrentHashMap(size, load) { |
| |
| private static final long serialVersionUID = 1L; |
| |
| @Override |
| public void overflowRemoved(Object key, Object value) { |
| cacheMapOverflowRemoved(key, value); |
| } |
| }; |
| } else { |
| cacheMap = new LRUMap(size, load) { |
| |
| private static final long serialVersionUID = 1L; |
| |
| @Override |
| public void overflowRemoved(Object key, Object value) { |
| cacheMapOverflowRemoved(key, value); |
| } |
| }; |
| } |
| if (max < 0) |
| max = Integer.MAX_VALUE; |
| cacheMap.setMaxSize(max); |
| } |
| |
| /** |
| * Called from {@link SizedMap#overflowRemoved} in the cache map. |
| */ |
| protected void cacheMapOverflowRemoved(Object key, Object value) { |
| if (softMap.size() < softMap.getMaxSize()) |
| put(softMap, key, value); |
| else |
| entryRemoved(key, value, true); |
| } |
| |
| /** |
| * Called from {@link SizedMap#overflowRemoved} in the soft map. |
| */ |
| protected void softMapOverflowRemoved(Object key, Object value) { |
| entryRemoved(key, value, true); |
| } |
| |
| /** |
| * Called when a value expires from the soft map. |
| */ |
| protected void softMapValueExpired(Object key) { |
| entryRemoved(key, null, true); |
| } |
| |
| /** |
| * Put the given entry into the given map. Allows subclasses to |
| * take additional actions. |
| */ |
| protected Object put(Map map, Object key, Object value) { |
| return map.put(key, value); |
| } |
| |
| /** |
| * Remove the given key from the given map. Allows subclasses to |
| * take additional actions. |
| */ |
| protected Object remove(Map map, Object key) { |
| return map.remove(key); |
| } |
| |
| /** |
| * Acquire read lock. |
| */ |
| public void readLock() { |
| _readLock.lock(); |
| } |
| |
| /** |
| * Release read lock. |
| */ |
| public void readUnlock() { |
| _readLock.unlock(); |
| } |
| |
| /** |
| * Acquire write lock. |
| */ |
| public void writeLock() { |
| _writeLock.lock(); |
| } |
| |
| /** |
| * Release write lock. |
| */ |
| public void writeUnlock() { |
| _writeLock.unlock(); |
| } |
| |
| /** |
| * Whether this cache map uses LRU eviction. |
| */ |
| public boolean isLRU() { |
| return cacheMap instanceof LRUMap; |
| } |
| |
| /** |
| * The maximum number of hard references to maintain, or -1 for no limit. |
| */ |
| public void setCacheSize(int size) { |
| writeLock(); |
| try { |
| cacheMap.setMaxSize((size < 0) ? Integer.MAX_VALUE : size); |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| /** |
| * The maximum number of hard references to maintain, or -1 for no limit. |
| */ |
| public int getCacheSize() { |
| int max = cacheMap.getMaxSize(); |
| return (max == Integer.MAX_VALUE) ? -1 : max; |
| } |
| |
| /** |
| * The maximum number of soft references to maintain, or -1 for no limit. |
| */ |
| public void setSoftReferenceSize(int size) { |
| writeLock(); |
| try { |
| softMap.setMaxSize((size < 0) ? Integer.MAX_VALUE : size); |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| /** |
| * The maximum number of soft references to maintain, or -1 for no limit. |
| */ |
| public int getSoftReferenceSize() { |
| int max = softMap.getMaxSize(); |
| return (max == Integer.MAX_VALUE) ? -1 : max; |
| } |
| |
| /** |
| * The keys pinned into the map. |
| */ |
| public Set getPinnedKeys() { |
| readLock(); |
| try { |
| return Collections.unmodifiableSet(pinnedMap.keySet()); |
| } finally { |
| readUnlock(); |
| } |
| } |
| |
| /** |
| * Locks the given key and its value into the map. Objects pinned into |
| * the map are not counted towards the maximum cache size, and are never |
| * evicted implicitly. You may pin keys for which no value is in the map. |
| * |
| * @return true if the givne key's value was pinned; false if no value |
| * for the given key is cached |
| */ |
| public boolean pin(Object key) { |
| writeLock(); |
| try { |
| // if we don't have a pinned map we need to create one; else if the |
| // pinned map already contains the key, nothing to do |
| if (pinnedMap.containsKey(key)) |
| return pinnedMap.get(key) != null; |
| |
| // check other maps for key |
| Object val = remove(cacheMap, key); |
| if (val == null) |
| val = remove(softMap, key); |
| |
| // pin key |
| put(pinnedMap, key, val); |
| if (val != null) { |
| _pinnedSize++; |
| return true; |
| } |
| return false; |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| /** |
| * Undo a pinning. |
| */ |
| public boolean unpin(Object key) { |
| writeLock(); |
| try { |
| Object val = remove(pinnedMap, key); |
| if (val != null) { |
| // put back into unpinned cache |
| put(key, val); |
| _pinnedSize--; |
| return true; |
| } |
| return false; |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| /** |
| * Invoked when a key-value pair is evicted from this data |
| * structure. This is invoked with <code>expired</code> set to |
| * <code>true</code> when an object is dropped because of space |
| * requirements or through garbage collection of soft references. |
| * It is invoked with <code>expired</code> set to <code>false</code> |
| * when an object is explicitly removed via the {@link #remove} or |
| * {@link #clear} methods. This may be invoked more than once for a |
| * given entry. |
| * |
| * @param value may be null if the value was a soft reference that has |
| * been GCd |
| * @since 0.2.5.0 |
| */ |
| protected void entryRemoved(Object key, Object value, boolean expired) { |
| } |
| |
| /** |
| * Invoked when an entry is added to the cache. This may be invoked |
| * more than once for an entry. |
| */ |
| protected void entryAdded(Object key, Object value) { |
| } |
| |
| @Override |
| public Object get(Object key) { |
| boolean putcache = false; |
| Object val = null; |
| readLock(); |
| try { |
| val = softMap.get(key); |
| if (val == null) { |
| val = cacheMap.get(key); |
| if (val == null) { |
| val = pinnedMap.get(key); |
| } |
| } else { |
| putcache = true; |
| } |
| return val; |
| } finally { |
| readUnlock(); |
| //cannot obtain a write lock while holding a read lock |
| //doing it this way prevents a deadlock |
| if (putcache) |
| put(key, val); |
| } |
| } |
| |
| @Override |
| public Object put(Object key, Object value) { |
| writeLock(); |
| try { |
| // if the key is pinned, just interact directly with the pinned map |
| Object val; |
| if (pinnedMap.containsKey(key)) { |
| val = put(pinnedMap, key, value); |
| if (val == null) { |
| _pinnedSize++; |
| entryAdded(key, value); |
| } else { |
| entryRemoved(key, val, false); |
| entryAdded(key, value); |
| } |
| return val; |
| } |
| |
| // if no hard refs, don't put anything |
| if (cacheMap.getMaxSize() == 0) |
| return null; |
| |
| // otherwise, put the value into the map and clear it from the |
| // soft map |
| val = put(cacheMap, key, value); |
| if (val == null) { |
| val = remove(softMap, key); |
| if (val == null) |
| entryAdded(key, value); |
| else { |
| entryRemoved(key, val, false); |
| entryAdded(key, value); |
| } |
| } else { |
| entryRemoved(key, val, false); |
| entryAdded(key, value); |
| } |
| return val; |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| @Override |
| public void putAll(Map map) { |
| putAll(map, true); |
| } |
| |
| public void putAll(Map map, boolean replaceExisting) { |
| Map.Entry entry; |
| for (Object o : map.entrySet()) { |
| entry = (Entry) o; |
| if (replaceExisting || !containsKey(entry.getKey())) { |
| put(entry.getKey(), entry.getValue()); |
| } |
| } |
| } |
| |
| /** |
| * If <code>key</code> is pinned into the cache, the pin is |
| * cleared and the object is removed. |
| */ |
| @Override |
| public Object remove(Object key) { |
| writeLock(); |
| try { |
| // if the key is pinned, just interact directly with the |
| // pinned map |
| Object val; |
| if (pinnedMap.containsKey(key)) { |
| // re-put with null value; we still want key pinned |
| val = put(pinnedMap, key, null); |
| if (val != null) { |
| _pinnedSize--; |
| entryRemoved(key, val, false); |
| } |
| return val; |
| } |
| |
| val = remove(cacheMap, key); |
| if (val == null) |
| val = softMap.remove(key); |
| if (val != null) |
| entryRemoved(key, val, false); |
| |
| return val; |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| /** |
| * Removes pinned objects as well as unpinned ones. |
| */ |
| @Override |
| public void clear() { |
| writeLock(); |
| try { |
| notifyEntryRemovals(pinnedMap.entrySet()); |
| pinnedMap.clear(); |
| _pinnedSize = 0; |
| |
| notifyEntryRemovals(cacheMap.entrySet()); |
| cacheMap.clear(); |
| |
| notifyEntryRemovals(softMap.entrySet()); |
| softMap.clear(); |
| } finally { |
| writeUnlock(); |
| } |
| } |
| |
| private void notifyEntryRemovals(Set set) { |
| Map.Entry entry; |
| for (Object o : set) { |
| entry = (Entry) o; |
| if (entry.getValue() != null) |
| entryRemoved(entry.getKey(), entry.getValue(), false); |
| } |
| } |
| |
| @Override |
| public int size() { |
| readLock(); |
| try { |
| return _pinnedSize + cacheMap.size() + softMap.size(); |
| } finally { |
| readUnlock(); |
| } |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return size() == 0; |
| } |
| |
| @Override |
| public boolean containsKey(Object key) { |
| readLock(); |
| try { |
| return cacheMap.containsKey(key) || pinnedMap.get(key) != null || softMap.containsKey(key); |
| } finally { |
| readUnlock(); |
| } |
| } |
| |
| @Override |
| public boolean containsValue(Object val) { |
| readLock(); |
| try { |
| return cacheMap.containsValue(val) || pinnedMap.containsValue(val) || softMap.containsValue(val); |
| } finally { |
| readUnlock(); |
| } |
| } |
| |
| @Override |
| public Set keySet() { |
| return new KeySet(); |
| } |
| |
| @Override |
| public Collection values() { |
| return new ValueCollection(); |
| } |
| |
| @Override |
| public Set entrySet() { |
| return new EntrySet(); |
| } |
| |
| @Override |
| public String toString() { |
| readLock(); |
| try { |
| return "CacheMap:" + cacheMap.toString() + "::" + softMap.toString(); |
| } finally { |
| readUnlock(); |
| } |
| } |
| |
| /** |
| * View of the entry set. |
| */ |
| private class EntrySet |
| extends AbstractSet { |
| |
| @Override |
| public int size() { |
| return CacheMap.this.size(); |
| } |
| |
| @Override |
| public boolean add(Object o) { |
| Map.Entry entry = (Map.Entry) o; |
| put(entry.getKey(), entry.getValue()); |
| return true; |
| } |
| |
| @Override |
| public Iterator iterator() { |
| return new EntryIterator(EntryIterator.ENTRY); |
| } |
| } |
| |
| /** |
| * View of the key set. |
| */ |
| private class KeySet |
| extends AbstractSet { |
| |
| @Override |
| public int size() { |
| return CacheMap.this.size(); |
| } |
| |
| @Override |
| public Iterator iterator() { |
| return new EntryIterator(EntryIterator.KEY); |
| } |
| } |
| |
| /** |
| * View of the value collection. |
| */ |
| private class ValueCollection |
| extends AbstractCollection { |
| |
| @Override |
| public int size() { |
| return CacheMap.this.size(); |
| } |
| |
| @Override |
| public Iterator iterator() { |
| return new EntryIterator(EntryIterator.VALUE); |
| } |
| } |
| |
| /** |
| * Iterator over all entries. |
| */ |
| private class EntryIterator |
| implements Iterator, Predicate { |
| |
| public static final int ENTRY = 0; |
| public static final int KEY = 1; |
| public static final int VALUE = 2; |
| |
| private final IteratorChain _itr = new IteratorChain(); |
| private final int _type; |
| |
| public EntryIterator(int type) { |
| _type = type; |
| _itr.addIterator(new FilterIterator(getView(pinnedMap), this)); |
| _itr.addIterator(getView(cacheMap)); |
| _itr.addIterator(getView(softMap)); |
| } |
| |
| /** |
| * Return an iterator over the appropriate view of the given map. |
| */ |
| private Iterator getView(Map m) { |
| if (m == null) |
| return null; |
| |
| switch (_type) { |
| case KEY: |
| return m.keySet().iterator(); |
| case VALUE: |
| return m.values().iterator(); |
| default: |
| return m.entrySet().iterator(); |
| } |
| } |
| |
| @Override |
| public boolean hasNext() { |
| return _itr.hasNext(); |
| } |
| |
| @Override |
| public Object next() { |
| return _itr.next(); |
| } |
| |
| @Override |
| public void remove() { |
| _itr.remove(); |
| } |
| |
| @Override |
| public boolean test(Object obj) { |
| switch (_type) { |
| case ENTRY: |
| return ((Map.Entry) obj).getValue() != null; |
| case VALUE: |
| return obj != null; |
| default: |
| return true; |
| } |
| } |
| } |
| } |
| |