I am trying to implement a thread-safe LRU cache algorithm, please review my code and would really appreciate some criticism or suggestion.
Some assumptions:
- capacity will be larger than 0
Some questions I have:
I know it is better to encapsulate variables in a class and declare them private, but since DDLNode is simply a data class, is it acceptable to make the variables public ?
I am considering to extract the following block of code (inside
put) into a function (something likeaddEntry(key, value)DDLNode<K, V> node = new DDLNode<>(key, value); addNode(node); entries.put(key, node);do you think it's neccesary? or the original code is self-explanatory enough?
Here is the code, Thanks in advance!!
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
interface CacheAlgorithm<K, V> {
public V get(K key);
public void put(K key, V value);
}
class DDLNode<K, V> {
public V value;
public K key;
public DDLNode<K, V> prev;
public DDLNode<K, V> next;
public DDLNode() {}
public DDLNode(K key, V value) {
this.key = key;
this.value = value;
}
}
public class LRU<K, V> implements CacheAlgorithm<K, V> {
private final ReentrantLock lock;
private final int capacity;
private final Map<K, DDLNode<K, V>> entries;
private final DDLNode<K, V> head;
private final DDLNode<K, V> tail;
public LRU(int capacity) {
this.capacity = capacity;
lock = new ReentrantLock();
head = new DDLNode<>();
tail = new DDLNode<>();
entries = new HashMap<>(capacity);
head.next = tail;
tail.prev = head;
}
@Override
public V get(K key) {
lock.lock();
try {
if (!entries.containsKey(key)) {
return null;
}
DDLNode<K, V> node = entries.get(key);
moveToMostRecent(node);
return node.value;
} finally {
lock.unlock();
}
}
@Override
public void put(K key, V value) {
lock.lock();
try {
if (entries.containsKey(key)) {
DDLNode<K, V> node = entries.get(key);
node.value = value;
moveToMostRecent(node);
} else {
if (entries.size() == capacity) {
removeLeastRecentEntry();
}
DDLNode<K, V> node = new DDLNode<>(key, value);
addNode(node);
entries.put(key, node);
}
} finally {
lock.unlock();
}
}
private void removeLeastRecentEntry() {
entries.remove(tail.prev.key);
removeNode(tail.prev);
}
private void moveToMostRecent(DDLNode<K, V> node) {
removeNode(node);
addNode(node);
}
private void removeNode(DDLNode<K, V> node) {
DDLNode<K, V> prev = node.prev;
DDLNode<K, V> next = node.next;
prev.next = next;
next.prev = prev;
}
private void addNode(DDLNode<K, V> node) {
DDLNode<K, V> headNext = head.next;
head.next = node;
node.prev = head;
headNext.prev = node;
node.next = headNext;
}
}
```