diff options
Diffstat (limited to 'org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java')
| -rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java new file mode 100644 index 0000000000..a715a26a9e --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java @@ -0,0 +1,227 @@ +/* + * Copyright (C) 2019, Marc Strapetz <marc.strapetz@syntevo.com> + * Copyright (C) 2019, Matthias Sohn <matthias.sohn@sap.com> and others + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +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 = tick(); + 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, tick())); + if (map.size() > maximumSize) { + purge(); + } + return value; + } + + @SuppressWarnings("NonAtomicVolatileUpdate") + private long tick() { + return ++time; + } + + /** + * 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(); + } + } + } +} |