LRU Cache Implementation – Algorithm – Data Structure.

Least Recently Used (LRU) is a family of caching algorithms, which discards the least recently used items first. This algorithm requires keeping track of when the item was used, which is expensive if one wants to make sure the algorithm always discards the least recently used item. A LRU cache is a container that ensures its maximum capacity is never exceeded by using a Least Recently Used strategy to discard elements. The LRU algorithm keeps track of the order used to access the cache elements in order to know the ones to discard when the container is full.

public interface ICacheRepository
{
    bool Add(string key, object cacheItem);
    object GetCacheItem(string key);
    bool Remove(string key);
}
 
public class LRUCacheNode
{
    public string Key { getset; }
    public object Value { getset; }
    public LRUCacheNode Next { getset; }
    public LRUCacheNode Previous { getset; }
}
 
public class LRUCacheRepository : ICacheRepository
{
    public LRUCacheRepository(int numberOfCacheItems)
    {
        this.capacity = numberOfCacheItems;
        this.cacheMap = new ConcurrentDictionary<stringLRUCacheNode>();
    }
    private ConcurrentDictionary<stringLRUCacheNode> cacheMap;
    private int capacity { getset; }
    private LRUCacheNode head;
    private LRUCacheNode tail;
 
    public bool Add(string key, object cacheItem)
    {
        LRUCacheNode cacheNode = null;
        if (cacheMap.TryGetValue(key, out cacheNode))
        {
            return false;
        }
        cacheNode = new LRUCacheNode()
        {
            Key = key,
            Value = cacheItem
        };
        if (head == null)
        {
            head = cacheNode;
            tail = cacheNode;
        }
        else
        {
            if (cacheMap.Count >= capacity)
            {
                this.RemoveTailNode();
            }
            cacheNode.Next = head;
            head.Previous = cacheNode;
            head = cacheNode;
        }
        return cacheMap.TryAdd(key, cacheNode);
    }
 
    public object GetCacheItem(string key)
    {
        LRUCacheNode cacheNode;
        if (this.cacheMap.TryGetValue(key, out cacheNode))
        {
            if (cacheNode.Previous != null)
                cacheNode.Previous.Next = cacheNode.Next;
 
            if (cacheNode.Next != null)
                cacheNode.Next.Previous = cacheNode.Previous;
 
            cacheNode.Next = head;
            head.Previous = cacheNode;
            head = cacheNode;
            return cacheNode.Value;
        }
        return null;
    }
 
    public bool Remove(string key)
    {
        LRUCacheNode cacheNode;
        if (this.cacheMap.TryGetValue(key, out cacheNode))
        {
            if (cacheNode.Previous != null)
                cacheNode.Previous.Next = cacheNode.Next;
            else
                head = cacheNode.Next;
 
            if (cacheNode.Next != null)
                cacheNode.Next.Previous = cacheNode.Previous;
            else
                tail = cacheNode.Previous;
 
            cacheNode.Next = null;
            cacheNode.Previous = null;
            return this.cacheMap.TryRemove(key, out cacheNode);
        }
        return false;
    }
 
    private void RemoveTailNode()
    {
        LRUCacheNode cacheNode;
        if (this.cacheMap.TryRemove(tail.Key, out cacheNode))
        {
            tail.Previous.Next = null;
            tail = tail.Previous;
        }
    }
 
    public void DisplayCacheMap()
    {
        StringBuilder sb = new StringBuilder();
        LRUCacheNode cacheNode = head;
        while (cacheNode != null)
        {
            sb.Append(cacheNode.Key);
            cacheNode = cacheNode.Next;
            if (cacheNode != null)
                sb.Append("==>");
        }
        Console.WriteLine(sb.ToString());
    }
}

Below is code snippet for adding items and verifying Cache Respository

class Program
{
    static void Main(string[] args)
    {
        LRUCacheRepository cacheRepository = new LRUCacheRepository(5);
        cacheRepository.Add("A""A");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("B""B");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("C""C");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("D""D");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("E""E");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("F""F");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("G""G");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("H""H");
        cacheRepository.DisplayCacheMap();
        object obj = cacheRepository.GetCacheItem("E");
        cacheRepository.DisplayCacheMap();
        obj = cacheRepository.GetCacheItem("F");
        cacheRepository.DisplayCacheMap();
        bool result = cacheRepository.Remove("G");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("A""A");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("B""B");
        cacheRepository.DisplayCacheMap();
        cacheRepository.Add("C""C");
        Console.ReadLine();
    }
}

Attached is the Source Code

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s