| /* |
| * 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(); |
| } |
| } |
| } |
| } |