Created
November 5, 2015 18:38
-
-
Save ashwath10110/5908cb95e8fd76bf1414 to your computer and use it in GitHub Desktop.
Simple LRU Cache using Queue and Dictionary in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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