SimpleLruCache.java

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