101 lines
1.7 KiB
Go
101 lines
1.7 KiB
Go
package lru
|
|
|
|
import (
|
|
"sync"
|
|
)
|
|
|
|
type node struct {
|
|
key, value any
|
|
prev, next *node
|
|
}
|
|
|
|
type LRUCache struct {
|
|
capacity int
|
|
cache map[any]*node
|
|
head *node
|
|
tail *node
|
|
mu sync.RWMutex
|
|
}
|
|
|
|
func NewLRUCache(capacity int) *LRUCache {
|
|
head := &node{}
|
|
tail := &node{}
|
|
head.next = tail
|
|
tail.prev = head
|
|
|
|
return &LRUCache{
|
|
capacity: capacity,
|
|
cache: make(map[any]*node, capacity),
|
|
head: head,
|
|
tail: tail,
|
|
}
|
|
}
|
|
|
|
func (lru *LRUCache) Get(key any) (any, bool) {
|
|
lru.mu.Lock()
|
|
defer lru.mu.Unlock()
|
|
|
|
if node, exists := lru.cache[key]; exists {
|
|
lru.moveToHead(node)
|
|
return node.value, true
|
|
}
|
|
return nil, false
|
|
}
|
|
|
|
func (lru *LRUCache) Put(key, value any) {
|
|
lru.mu.Lock()
|
|
defer lru.mu.Unlock()
|
|
|
|
if node, exists := lru.cache[key]; exists {
|
|
node.value = value
|
|
lru.moveToHead(node)
|
|
return
|
|
}
|
|
|
|
newNode := &node{key: key, value: value}
|
|
lru.cache[key] = newNode
|
|
lru.addToHead(newNode)
|
|
|
|
if len(lru.cache) > lru.capacity {
|
|
removed := lru.removeTail()
|
|
delete(lru.cache, removed.key)
|
|
}
|
|
}
|
|
|
|
func (lru *LRUCache) moveToHead(node *node) {
|
|
lru.removeNode(node)
|
|
lru.addToHead(node)
|
|
}
|
|
|
|
func (lru *LRUCache) removeNode(node *node) {
|
|
node.prev.next = node.next
|
|
node.next.prev = node.prev
|
|
}
|
|
|
|
func (lru *LRUCache) addToHead(node *node) {
|
|
node.prev = lru.head
|
|
node.next = lru.head.next
|
|
lru.head.next.prev = node
|
|
lru.head.next = node
|
|
}
|
|
|
|
func (lru *LRUCache) removeTail() *node {
|
|
node := lru.tail.prev
|
|
lru.removeNode(node)
|
|
return node
|
|
}
|
|
|
|
func (lru *LRUCache) Len() int {
|
|
lru.mu.RLock()
|
|
defer lru.mu.RUnlock()
|
|
return len(lru.cache)
|
|
}
|
|
|
|
func (lru *LRUCache) Clear() {
|
|
lru.mu.Lock()
|
|
defer lru.mu.Unlock()
|
|
lru.cache = make(map[any]*node, lru.capacity)
|
|
lru.head.next = lru.tail
|
|
lru.tail.prev = lru.head
|
|
}
|