Last active
June 13, 2023 00:14
-
-
Save cgillum/9a569312fa1a56393010307ef18c04ee to your computer and use it in GitHub Desktop.
Simple LRU cache implementation
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
public class LRUCache<TKey, TValue> | |
{ | |
readonly int capacity; | |
readonly Dictionary<TKey, LinkedListNode<(TKey key, TValue value)>> cache; | |
readonly LinkedList<(TKey key, TValue value)> list; | |
readonly object syncLock = new object(); | |
public LRUCache(int capacity) | |
{ | |
this.capacity = capacity; | |
this.cache = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>(); | |
this.list = new LinkedList<(TKey, TValue)>(); | |
} | |
public void Add(TKey key, TValue value) | |
{ | |
lock (this.syncLock) | |
{ | |
if (this.cache.TryGetValue(key, out var node)) | |
{ | |
this.list.Remove(node); | |
this.list.AddFirst(node); | |
node.Value = (key, value); | |
} | |
else | |
{ | |
if (this.cache.Count == capacity) | |
{ | |
var last = this.list.Last; | |
this.list.RemoveLast(); | |
this.cache.Remove(last.Value.key); | |
} | |
var newNode = new LinkedListNode<(TKey, TValue)>((key, value)); | |
this.list.AddFirst(newNode); | |
this.cache[key] = newNode; | |
} | |
} | |
} | |
public bool TryGet(TKey key, out TValue value) | |
{ | |
lock (this.syncLock) | |
{ | |
if (this.cache.TryGetValue(key, out var node)) | |
{ | |
this.list.Remove(node); | |
this.list.AddFirst(node); | |
value = node.Value.value; | |
return true; | |
} | |
else | |
{ | |
value = default(TValue); | |
return false; | |
} | |
} | |
} | |
public bool TryRemove(TKey key) | |
{ | |
lock (this.syncLock) | |
{ | |
if (this.cache.Remove(key, out var node)) | |
{ | |
this.list.Remove(node); | |
return true; | |
} | |
return false; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment