Concurrent write-order FIFO for caching: The cache uses a ConcurrentHashMap and a ConcurrentLinkedQueue; and atomic integers for timestamping accesses, writes, and the queue size. The map maintains the cached values, and the queue maintains an ordering of the elements in write-FIFO order. ConcurrentLRUCaches eschews locks in favor of lock-free d…

ConcurrentLRUCache.java

package memoizer;

import java.util.Arrays;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.atomic.AtomicLong;

public class ConcurrentLRUCache {
  private final int kCacheSize; 
  private final ConcurrentHashMap<Object, CachedValue> mMap;
  private final ConcurrentLinkedQueue<CachedValue> mQueue;
  private final AtomicLong mReadCounter = new AtomicLong(0);
  private final AtomicLong mWriteCounter = new AtomicLong(0);
  private final AtomicLong mSizeCounter = new AtomicLong(0);
  
  public ConcurrentLRUCache(int cacheSize) {
    this.kCacheSize = cacheSize;
    this.mMap = new ConcurrentHashMap<Object, CachedValue>(this.kCacheSize); 
    this.mQueue = new ConcurrentLinkedQueue<CachedValue>();
  }
  
  public Object get(Object key) {
    CachedValue value = mMap.get(key);
    if (value != null) {
      value.readEpoch = mReadCounter.incrementAndGet();
      return value.value;
    }
    return null;
  }
  
  public void put(Object key, Object val) {
    if (key == null || val == null) {
      return;
    }
    CachedValue next = new CachedValue(key, 
                                       val, 
                                       this.mWriteCounter.getAndIncrement(),
                                       this.mReadCounter.getAndIncrement());
    if (this.tryEvict() && this.mMap.putIfAbsent(key, next) == null) {
      this.mQueue.add(next);
      this.mSizeCounter.getAndIncrement();
    }
  }
  
  public long size() {
    return mSizeCounter.get();
  }

  private boolean tryEvict() {
    if (this.size() >= this.kCacheSize) {
      CachedValue entry = mQueue.poll();
      if (entry.key != null && this.mMap.remove(entry.key) != null) {
        this.mSizeCounter.getAndDecrement();
      } else {
        return false;
      }
    } 
    return true;
  }
  
  public String toString() {
    String queue = Arrays.toString(this.mQueue.toArray());
    String map = Arrays.toString(this.mMap.entrySet().toArray());
    return map + "\n" + queue;
  }
  
  private static class CachedValue implements Comparable<CachedValue> {
    public Object key;
    public Object value;
    public volatile long writeEpoch;
    public volatile long readEpoch;

    public CachedValue(Object key, Object value, long writeEpoch, long readEpoch) {
      this.key = key;
      this.value = value;
      this.writeEpoch = writeEpoch;
      this.readEpoch = readEpoch;
    }
    
    public boolean equals(Object value) {
      return this.value.equals(value);
    }
    
    public int compareTo(CachedValue value) {
      if (this.writeEpoch == value.writeEpoch) {
        return 0;
      } else {
        return this.writeEpoch < value.writeEpoch ? 1 : -1;
      }
    }

    public int hashCode() {
      return this.value.hashCode();
    }
    
    public String toString() {
      return "CacheValue<" + key.toString() + "," + value.toString() + ">";
    }
  }
}