final class CacheLRU<Key: Hashable, Value> { | |
private struct CachePayload { | |
let key: Key | |
let value: Value | |
} | |
private let capacity: Int | |
private let list = DoublyLinkedList<CachePayload>() | |
private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]() | |
init(capacity: Int) { | |
self.capacity = max(0, capacity) | |
} | |
func setValue(_ value: Value, for key: Key) { | |
let payload = CachePayload(key: key, value: value) | |
if let node = nodesDict[key] { | |
node.payload = payload | |
list.moveToHead(node) | |
} else { | |
let node = list.addHead(payload) | |
nodesDict[key] = node | |
} | |
if list.count > capacity { | |
let nodeRemoved = list.removeLast() | |
if let key = nodeRemoved?.payload.key { | |
nodesDict[key] = nil | |
} | |
} | |
} | |
func getValue(for key: Key) -> Value? { | |
guard let node = nodesDict[key] else { return nil } | |
list.moveToHead(node) | |
return node.payload.value | |
} | |
} |
typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T> | |
final class DoublyLinkedList<T> { | |
final class Node<T> { | |
var payload: T | |
var previous: Node<T>? | |
var next: Node<T>? | |
init(payload: T) { | |
self.payload = payload | |
} | |
} | |
private(set) var count: Int = 0 | |
private var head: Node<T>? | |
private var tail: Node<T>? | |
func addHead(_ payload: T) -> Node<T> { | |
let node = Node(payload: payload) | |
defer { | |
head = node | |
count += 1 | |
} | |
guard let head = head else { | |
tail = node | |
return node | |
} | |
head.previous = node | |
node.previous = nil | |
node.next = head | |
return node | |
} | |
func moveToHead(_ node: Node<T>) { | |
guard node !== head else { return } | |
let previous = node.previous | |
let next = node.next | |
previous?.next = next | |
next?.previous = previous | |
node.next = head | |
node.previous = nil | |
if node === tail { | |
tail = previous | |
} | |
self.head = node | |
} | |
func removeLast() -> Node<T>? { | |
guard let tail = self.tail else { return nil } | |
let previous = tail.previous | |
previous?.next = nil | |
self.tail = previous | |
if count == 1 { | |
head = nil | |
} | |
count -= 1 | |
return tail | |
} | |
} |
This comment has been minimized.
This comment has been minimized.
There is a bug in the DoublyLinkedList
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
It looks like there might be a memory leak in the
LRUCache
class. You can fix by adding adeinit
toLRUCache