LRU Cache with pruning thread

Objective: Create a generic LRU cache with prune mechanism in different thread.

Approach: LRU cache stand for least recently used cache. In java, it is very common to use LinkedHashMap to implement this functionality. But, pruning process is also important. If we will do pruning process in same thread as adding LRU cache, it will take time. So, here is multi-threaded solution for this problem. We will add item in LRU cache, and prune old item in other thread.

Download full source code: LRU cache complete source code

Solution: Java Code

	package com.vectordirection;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.Map;
	import java.util.concurrent.Semaphore;
	import java.util.concurrent.TimeUnit;
	/**
	* Created by adarshpandey on 1/12/15.
	*/
	public class LRUCache<Key, Item extends CacheableItem<Key>> implements Runnable {
	private final int maxSize;
	private final Integer mutex = 1;
	private Semaphore semaphore = new Semaphore(0);
	private final Map<Key, Item> cache;
	private boolean isKeepRunning = true;
	public LRUCache(int cacheSize) {
	cache = new HashMap<>();
	maxSize = cacheSize;
	isKeepRunning = true;
	Thread thread = new Thread(this);
	thread.start();
	}
	public int size() {
	return cache.size();
	}
	public Item getValue(Key key) {
	return cache.get(key);
	}
	public void add(Item item) {
	synchronized (mutex) {
	if (cache.containsKey(item.getKey())) {
	cache.remove(item.getKey());
	}
	cache.put(item.getKey(), item);
	semaphore.release();
	}
	}
	public void shutdown() {
	synchronized (mutex) {
	isKeepRunning = false;
	semaphore.release();
	}
	}
	public void prune() {
	synchronized (mutex) {
	Iterator<Map.Entry<Key, Item>> itemIterator = cache.entrySet().iterator();
	while (itemIterator.hasNext()) {
	itemIterator.next();
	if (cache.size() > maxSize) {
	itemIterator.remove();
	} else {
	break;
	}
	}
	}
	}
	@Override
	public void run() {
	while (isKeepRunning) {
	try {
	semaphore.tryAcquire(5000, TimeUnit.MILLISECONDS);
	semaphore.drainPermits();
	if (isKeepRunning) {
	prune();
	}
	} catch (InterruptedException e) {
	e.printStackTrace();
	}
	}
	}
	}

view raw LRUCache.java hosted with ❤ by GitHub

	package com.vectordirection;
	/**
	* Created by adarshpandey on 1/12/15.
	*/
	public interface CacheableItem<Key> {
	Key getKey();
	}

view raw CacheableItem.java hosted with ❤ by GitHub

	package com.verctordirection.test;
	import com.vectordirection.LRUCache;
	import org.junit.Test;
	/**
	* Created by adarshpandey on 1/13/15.
	*/
	public class CachingTest {
	@Test
	public void testLRU() {
	System.out.println("=========================================");
	System.out.println("*********** Caching Test Start **********");
	System.out.println("=========================================");
	LRUCache<Integer, Store> storeLRUCache = new LRUCache<>(3);
	storeLRUCache.add(new Store(1, 22));
	storeLRUCache.add(new Store(2, 23));
	storeLRUCache.add(new Store(3, 27));
	storeLRUCache.add(new Store(4, 29));
	storeLRUCache.add(new Store(5, 28));
	storeLRUCache.add(new Store(6, 21));
	storeLRUCache.add(new Store(7, 24));
	try {
	Thread.sleep(10);
	} catch (InterruptedException e) {
	e.printStackTrace();
	}
	assert storeLRUCache.size() == 3;
	assert storeLRUCache.getValue(1) == null;
	assert storeLRUCache.getValue(7).getValue() == 24;
	storeLRUCache.shutdown();
	}
	}

view raw CachingTest.java hosted with ❤ by GitHub

	package com.verctordirection.test;
	import com.vectordirection.CacheableItem;
	/**
	* Created by adarshpandey on 1/13/15.
	*/
	public class Store implements CacheableItem<Integer> {
	private Integer key;
	private Integer value;
	public Store(Integer key, Integer value) {
	this.key = key;
	this.value = value;
	}
	@Override
	public Integer getKey() {
	return key;
	}
	public void setKey(Integer key) {
	this.key = key;
	}
	public Integer getValue() {
	return value;
	}
	}

view raw Store.java hosted with ❤ by GitHub