Class LinkedHashLruCache

rls/src/main/java/io/grpc/rls/LinkedHashLruCache.java:42–329

A LinkedHashLruCache implements least recently used caching where it supports access order lru cache eviction while allowing entry level expiration time. When the cache reaches max capacity, LruCache try to remove up to one already expired entries. If it doesn't find any expired entries, it will rem

 * {@link #cleanupExpiredEntries()} (e.g., via a recurring timer).
 */
abstract class LinkedHashLruCache<K, V> implements LruCache<K, V> {

  private final LinkedHashMap<K, SizedValue> delegate;
  private final Ticker ticker;
  @Nullable
  private final EvictionListener<K, V> evictionListener;
  private long estimatedSizeBytes;
  private long estimatedMaxSizeBytes;

  LinkedHashLruCache(
      final long estimatedMaxSizeBytes,
      @Nullable final EvictionListener<K, V> evictionListener,
      final Ticker ticker) {
    checkState(estimatedMaxSizeBytes > 0, "max estimated cache size should be positive");
    this.estimatedMaxSizeBytes = estimatedMaxSizeBytes;
    this.evictionListener = evictionListener;
    this.ticker = checkNotNull(ticker, "ticker");
    delegate = new LinkedHashMap<K, SizedValue>(
        // rough estimate or minimum hashmap default
        Math.max((int) (estimatedMaxSizeBytes / 1000), 16),
        /* loadFactor= */ 0.75f,
        /* accessOrder= */ true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, SizedValue> eldest) {
        if (estimatedSizeBytes <= LinkedHashLruCache.this.estimatedMaxSizeBytes) {
          return false;
        }

        // first, remove at most 1 expired entry
        boolean removed = cleanupExpiredEntries(1, ticker.read());
        // handles size based eviction if necessary no expired entry
        boolean shouldRemove = !removed
            && shouldInvalidateEldestEntry(eldest.getKey(), eldest.getValue().value, ticker.read());
        if (shouldRemove) {
          // remove entry by us to make sure lruIterator and cache is in sync
          LinkedHashLruCache.this.invalidate(eldest.getKey(), EvictionType.SIZE);
        }
        return false;
      }
    };
  }

  /**
   * Determines if the eldest entry should be kept or not when the cache size limit is reached. Note
   * that LruCache is access level and the eldest is determined by access pattern.
   */
  @SuppressWarnings("unused")
  protected boolean shouldInvalidateEldestEntry(K eldestKey, V eldestValue, long now) {
    return true;
  }

  /** Determines if the entry is already expired or not. */
  protected abstract boolean isExpired(K key, V value, long nowNanos);

  /**
   * Returns estimated size of entry to keep track. If it always returns 1, the max size bytes
   * behaves like max number of entry (default behavior).
   */