SimpleLruCache.java
/*
* Copyright (C) 2019, Marc Strapetz <marc.strapetz@syntevo.com>
* Copyright (C) 2019, Matthias Sohn <matthias.sohn@sap.com>
* and other copyright owners as documented in the project's IP log.
*
* This program and the accompanying materials are made available
* under the terms of the Eclipse Distribution License v1.0 which
* accompanies this distribution, is reproduced below, and is
* available at http://www.eclipse.org/org/documents/edl-v10.php
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* - Neither the name of the Eclipse Foundation, Inc. nor the
* names of its contributors may be used to endorse or promote
* products derived from this software without specific prior
* written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package org.eclipse.jgit.util;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import org.eclipse.jgit.annotations.NonNull;
import org.eclipse.jgit.internal.JGitText;
/**
* Simple limited size cache based on ConcurrentHashMap purging entries in LRU
* order when reaching size limit
*
* @param <K>
* the type of keys maintained by this cache
* @param <V>
* the type of mapped values
*
* @since 5.1.9
*/
public class SimpleLruCache<K, V> {
private static class Entry<K, V> {
private final K key;
private final V value;
// pseudo clock timestamp of the last access to this entry
private volatile long lastAccessed;
private long lastAccessedSorting;
Entry(K key, V value, long lastAccessed) {
this.key = key;
this.value = value;
this.lastAccessed = lastAccessed;
}
void copyAccessTime() {
lastAccessedSorting = lastAccessed;
}
@SuppressWarnings("nls")
@Override
public String toString() {
return "Entry [lastAccessed=" + lastAccessed + ", key=" + key
+ ", value=" + value + "]";
}
}
private Lock lock = new ReentrantLock();
private Map<K, Entry<K,V>> map = new ConcurrentHashMap<>();
private volatile int maximumSize;
private int purgeSize;
// pseudo clock to implement LRU order of access to entries
private volatile long time = 0L;
private static void checkPurgeFactor(float purgeFactor) {
if (purgeFactor <= 0 || purgeFactor >= 1) {
throw new IllegalArgumentException(
MessageFormat.format(JGitText.get().invalidPurgeFactor,
Float.valueOf(purgeFactor)));
}
}
private static int purgeSize(int maxSize, float purgeFactor) {
return (int) ((1 - purgeFactor) * maxSize);
}
/**
* Create a new cache
*
* @param maxSize
* maximum size of the cache, to reduce need for synchronization
* this is not a hard limit. The real size of the cache could be
* slightly above this maximum if multiple threads put new values
* concurrently
* @param purgeFactor
* when the size of the map reaches maxSize the oldest entries
* will be purged to free up some space for new entries,
* {@code purgeFactor} is the fraction of {@code maxSize} to
* purge when this happens
*/
public SimpleLruCache(int maxSize, float purgeFactor) {
checkPurgeFactor(purgeFactor);
this.maximumSize = maxSize;
this.purgeSize = purgeSize(maxSize, purgeFactor);
}
/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
* <p>
* More formally, if this cache contains a mapping from a key {@code k} to a
* value {@code v} such that {@code key.equals(k)}, then this method returns
* {@code v}; otherwise it returns {@code null}. (There can be at most one
* such mapping.)
*
* @param key
* the key
*
* @throws NullPointerException
* if the specified key is null
*
* @return value mapped for this key, or {@code null} if no value is mapped
*/
@SuppressWarnings("NonAtomicVolatileUpdate")
public V get(Object key) {
Entry<K, V> entry = map.get(key);
if (entry != null) {
entry.lastAccessed = ++time;
return entry.value;
}
return null;
}
/**
* Maps the specified key to the specified value in this cache. Neither the
* key nor the value can be null.
*
* <p>
* The value can be retrieved by calling the {@code get} method with a key
* that is equal to the original key.
*
* @param key
* key with which the specified value is to be associated
* @param value
* value to be associated with the specified key
* @return the previous value associated with {@code key}, or {@code null}
* if there was no mapping for {@code key}
* @throws NullPointerException
* if the specified key or value is null
*/
@SuppressWarnings("NonAtomicVolatileUpdate")
public V put(@NonNull K key, @NonNull V value) {
map.put(key, new Entry<>(key, value, ++time));
if (map.size() > maximumSize) {
purge();
}
return value;
}
/**
* Returns the current size of this cache
*
* @return the number of key-value mappings in this cache
*/
public int size() {
return map.size();
}
/**
* Reconfigures the cache. If {@code maxSize} is reduced some entries will
* be purged.
*
* @param maxSize
* maximum size of the cache
*
* @param purgeFactor
* when the size of the map reaches maxSize the oldest entries
* will be purged to free up some space for new entries,
* {@code purgeFactor} is the fraction of {@code maxSize} to
* purge when this happens
*/
public void configure(int maxSize, float purgeFactor) {
lock.lock();
try {
checkPurgeFactor(purgeFactor);
this.maximumSize = maxSize;
this.purgeSize = purgeSize(maxSize, purgeFactor);
if (map.size() >= maximumSize) {
purge();
}
} finally {
lock.unlock();
}
}
private void purge() {
// don't try to compete if another thread already has the lock
if (lock.tryLock()) {
try {
List<Entry> entriesToPurge = new ArrayList<>(map.values());
// copy access times to avoid other threads interfere with
// sorting
for (Entry e : entriesToPurge) {
e.copyAccessTime();
}
Collections.sort(entriesToPurge,
Comparator.comparingLong(o -> -o.lastAccessedSorting));
for (int index = purgeSize; index < entriesToPurge
.size(); index++) {
map.remove(entriesToPurge.get(index).key);
}
} finally {
lock.unlock();
}
}
}
}