Skip to content

Instantly share code, notes, and snippets.

@cgillum
Last active June 13, 2023 00:14
Show Gist options
  • Save cgillum/9a569312fa1a56393010307ef18c04ee to your computer and use it in GitHub Desktop.
Save cgillum/9a569312fa1a56393010307ef18c04ee to your computer and use it in GitHub Desktop.
Simple LRU cache implementation
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