Skip to content

Instantly share code, notes, and snippets.

@ashwath10110
Created November 5, 2015 18:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ashwath10110/5908cb95e8fd76bf1414 to your computer and use it in GitHub Desktop.
Save ashwath10110/5908cb95e8fd76bf1414 to your computer and use it in GitHub Desktop.
Simple LRU Cache using Queue and Dictionary in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DS
{
public class LRU
{
public class DNode
{
public DNode Prev { get; set; }
public DNode Next { get; set; }
public int Key { get; set; }
public int Data { get; set; }
public DNode(int Data)
{
this.Data = Data;
}
public DNode(int Key, int Data)
{
this.Key = Key;
this.Data = Data;
}
public int GetKey()
{
return this.Key;
}
}
public Dictionary<int, DNode> Entries;
public int Capacity { get; set; }
public DNode Head { get; set; }
public DNode End { get; set; }
public int Length { get; set; }
public LRU(int Capacity)
{
this.Capacity = Capacity;
this.Length = 0;
Entries = new Dictionary<int, DNode>();
}
public void SetValue(int key, int value)
{
if (Entries.ContainsKey(key))
{
DNode n = Entries[key];
n.Data = value;
Remove(ref n);
SetHead(ref n);
}
else //If Page Not found in Memory.
{
if (Length < Capacity)
{
DNode n = new DNode(key, value);
SetHead(ref n);
//Attach node to start.
Length++;
Entries.Add(key, n);
}
else //Page size full,remove least recently use i.e from tail of List
{
Entries.Remove(End.Key);
var p1 = End;
Remove(ref p1);
DNode n = new DNode(key, value);
SetHead(ref n);
Entries.Add(key, n);
}
}
}
public int GetValue(int key)
{
if (Entries.ContainsKey(key))
{
DNode n = Entries[key];
Remove(ref n);
SetHead(ref n);
return n.Data;
}
else
{
return -1;
}
}
public void SetHead(ref DNode n)
{
if (Head == null)
{
Head = n;
End = n;
}
else
{
Head.Prev = n;
n.Next = Head;
Head = n;
}
}
public void Remove(ref DNode n)
{
DNode pre = n.Prev;
DNode post = n.Next;
if (pre == null)
{
Head = post;
}
else
{
pre.Next = post;
}
if (post == null)
{
End = pre;
}
else
{
post.Prev = pre;
}
}
public void PrintCache()
{
DNode n = Head;
while (n != null)
{
Console.WriteLine(n.Data);
n = n.Next;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment