From fec8b64975f952e2fa5fa8478b09dced87f0fa7b Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Fri, 6 Mar 2026 04:43:03 +0800 Subject: internal/lru: Split --- internal/lru/add.go | 35 +++++++++ internal/lru/cache.go | 16 +++++ internal/lru/clear.go | 10 +++ internal/lru/entries.go | 7 ++ internal/lru/evict.go | 17 +++++ internal/lru/get.go | 15 ++++ internal/lru/len.go | 6 ++ internal/lru/lru.go | 187 ------------------------------------------------ internal/lru/new.go | 23 ++++++ internal/lru/peek.go | 13 ++++ internal/lru/remove.go | 31 ++++++++ internal/lru/weight.go | 29 ++++++++ 12 files changed, 202 insertions(+), 187 deletions(-) create mode 100644 internal/lru/add.go create mode 100644 internal/lru/cache.go create mode 100644 internal/lru/clear.go create mode 100644 internal/lru/entries.go create mode 100644 internal/lru/evict.go create mode 100644 internal/lru/get.go create mode 100644 internal/lru/len.go create mode 100644 internal/lru/new.go create mode 100644 internal/lru/peek.go create mode 100644 internal/lru/remove.go create mode 100644 internal/lru/weight.go (limited to 'internal/lru') diff --git a/internal/lru/add.go b/internal/lru/add.go new file mode 100644 index 00000000..6c055ab5 --- /dev/null +++ b/internal/lru/add.go @@ -0,0 +1,35 @@ +package lru + +// Add inserts or replaces key and marks it most-recently-used. +// +// Add returns false when the entry's weight exceeds MaxWeight even for an empty +// cache. In that case the cache is unchanged. +// +// Add panics if weightFn returns a negative weight. +func (cache *Cache[K, V]) Add(key K, value V) bool { + w := cache.weightFn(key, value) + if w < 0 { + panic("lru: negative entry weight") + } + + if w > cache.maxWeight { + return false + } + + if elem, ok := cache.items[key]; ok { + cache.removeElem(elem) + } + + ent := &entry[K, V]{ + key: key, + value: value, + weight: w, + } + elem := cache.lru.PushBack(ent) + cache.items[key] = elem + cache.weight += w + + cache.evictOverBudget() + + return true +} diff --git a/internal/lru/cache.go b/internal/lru/cache.go new file mode 100644 index 00000000..1aa96c52 --- /dev/null +++ b/internal/lru/cache.go @@ -0,0 +1,16 @@ +package lru + +import "container/list" + +// Cache is a non-concurrent weighted LRU cache. +// +// Methods on Cache are not safe for concurrent use. +type Cache[K comparable, V any] struct { + maxWeight int64 + weightFn WeightFunc[K, V] + onEvict OnEvictFunc[K, V] + + weight int64 + items map[K]*list.Element + lru list.List +} diff --git a/internal/lru/clear.go b/internal/lru/clear.go new file mode 100644 index 00000000..42f9c50e --- /dev/null +++ b/internal/lru/clear.go @@ -0,0 +1,10 @@ +package lru + +// Clear removes all entries from the cache. +func (cache *Cache[K, V]) Clear() { + for elem := cache.lru.Front(); elem != nil; { + next := elem.Next() + cache.removeElem(elem) + elem = next + } +} diff --git a/internal/lru/entries.go b/internal/lru/entries.go new file mode 100644 index 00000000..132f8f7e --- /dev/null +++ b/internal/lru/entries.go @@ -0,0 +1,7 @@ +package lru + +type entry[K comparable, V any] struct { + key K + value V + weight int64 +} diff --git a/internal/lru/evict.go b/internal/lru/evict.go new file mode 100644 index 00000000..9659dd4f --- /dev/null +++ b/internal/lru/evict.go @@ -0,0 +1,17 @@ +package lru + +// OnEvictFunc runs when an entry leaves the cache. +// +// It is called for evictions, explicit removals, Clear, and replacement by Add. +type OnEvictFunc[K comparable, V any] func(key K, value V) + +func (cache *Cache[K, V]) evictOverBudget() { + for cache.weight > cache.maxWeight { + elem := cache.lru.Front() + if elem == nil { + return + } + + cache.removeElem(elem) + } +} diff --git a/internal/lru/get.go b/internal/lru/get.go new file mode 100644 index 00000000..92196003 --- /dev/null +++ b/internal/lru/get.go @@ -0,0 +1,15 @@ +package lru + +// Get returns value for key and marks it most-recently-used. +func (cache *Cache[K, V]) Get(key K) (V, bool) { + elem, ok := cache.items[key] + if !ok { + var zero V + + return zero, false + } + + cache.lru.MoveToBack(elem) + //nolint:forcetypeassert + return elem.Value.(*entry[K, V]).value, true +} diff --git a/internal/lru/len.go b/internal/lru/len.go new file mode 100644 index 00000000..bc05e362 --- /dev/null +++ b/internal/lru/len.go @@ -0,0 +1,6 @@ +package lru + +// Len returns the number of cached entries. +func (cache *Cache[K, V]) Len() int { + return len(cache.items) +} diff --git a/internal/lru/lru.go b/internal/lru/lru.go index fcbab646..119f31c1 100644 --- a/internal/lru/lru.go +++ b/internal/lru/lru.go @@ -1,189 +1,2 @@ // Package lru provides a size-cost bounded LRU cache. package lru - -import "container/list" - -// WeightFunc reports one entry's weight used for eviction budgeting. -// -// Returned weights MUST be non-negative. -type WeightFunc[K comparable, V any] func(key K, value V) int64 - -// OnEvictFunc runs when an entry leaves the cache. -// -// It is called for evictions, explicit removals, Clear, and replacement by Add. -type OnEvictFunc[K comparable, V any] func(key K, value V) - -// Cache is a non-concurrent weighted LRU cache. -// -// Methods on Cache are not safe for concurrent use. -type Cache[K comparable, V any] struct { - maxWeight int64 - weightFn WeightFunc[K, V] - onEvict OnEvictFunc[K, V] - - weight int64 - items map[K]*list.Element - lru list.List -} - -type entry[K comparable, V any] struct { - key K - value V - weight int64 -} - -// New creates a cache with a maximum total weight. -// -// New panics if maxWeight is negative or weightFn is nil. -func New[K comparable, V any](maxWeight int64, weightFn WeightFunc[K, V], onEvict OnEvictFunc[K, V]) *Cache[K, V] { - if maxWeight < 0 { - panic("lru: negative max weight") - } - - if weightFn == nil { - panic("lru: nil weight function") - } - - return &Cache[K, V]{ - maxWeight: maxWeight, - weightFn: weightFn, - onEvict: onEvict, - items: make(map[K]*list.Element), - } -} - -// Add inserts or replaces key and marks it most-recently-used. -// -// Add returns false when the entry's weight exceeds MaxWeight even for an empty -// cache. In that case the cache is unchanged. -// -// Add panics if weightFn returns a negative weight. -func (cache *Cache[K, V]) Add(key K, value V) bool { - w := cache.weightFn(key, value) - if w < 0 { - panic("lru: negative entry weight") - } - - if w > cache.maxWeight { - return false - } - - if elem, ok := cache.items[key]; ok { - cache.removeElem(elem) - } - - ent := &entry[K, V]{ - key: key, - value: value, - weight: w, - } - elem := cache.lru.PushBack(ent) - cache.items[key] = elem - cache.weight += w - - cache.evictOverBudget() - - return true -} - -// Get returns value for key and marks it most-recently-used. -func (cache *Cache[K, V]) Get(key K) (V, bool) { - elem, ok := cache.items[key] - if !ok { - var zero V - - return zero, false - } - - cache.lru.MoveToBack(elem) - //nolint:forcetypeassert - return elem.Value.(*entry[K, V]).value, true -} - -// Peek returns value for key without changing recency. -func (cache *Cache[K, V]) Peek(key K) (V, bool) { - elem, ok := cache.items[key] - if !ok { - var zero V - - return zero, false - } - //nolint:forcetypeassert - return elem.Value.(*entry[K, V]).value, true -} - -// Remove deletes key from the cache. -func (cache *Cache[K, V]) Remove(key K) (V, bool) { - elem, ok := cache.items[key] - if !ok { - var zero V - - return zero, false - } - - ent := cache.removeElem(elem) - - return ent.value, true -} - -// Clear removes all entries from the cache. -func (cache *Cache[K, V]) Clear() { - for elem := cache.lru.Front(); elem != nil; { - next := elem.Next() - cache.removeElem(elem) - elem = next - } -} - -// Len returns the number of cached entries. -func (cache *Cache[K, V]) Len() int { - return len(cache.items) -} - -// Weight returns the current total weight. -func (cache *Cache[K, V]) Weight() int64 { - return cache.weight -} - -// MaxWeight returns the configured total weight budget. -func (cache *Cache[K, V]) MaxWeight() int64 { - return cache.maxWeight -} - -// SetMaxWeight updates the total weight budget and evicts LRU entries as -// needed. -// -// SetMaxWeight panics if maxWeight is negative. -func (cache *Cache[K, V]) SetMaxWeight(maxWeight int64) { - if maxWeight < 0 { - panic("lru: negative max weight") - } - - cache.maxWeight = maxWeight - cache.evictOverBudget() -} - -func (cache *Cache[K, V]) evictOverBudget() { - for cache.weight > cache.maxWeight { - elem := cache.lru.Front() - if elem == nil { - return - } - - cache.removeElem(elem) - } -} - -func (cache *Cache[K, V]) removeElem(elem *list.Element) *entry[K, V] { - //nolint:forcetypeassert - ent := elem.Value.(*entry[K, V]) - cache.lru.Remove(elem) - delete(cache.items, ent.key) - - cache.weight -= ent.weight - if cache.onEvict != nil { - cache.onEvict(ent.key, ent.value) - } - - return ent -} diff --git a/internal/lru/new.go b/internal/lru/new.go new file mode 100644 index 00000000..f683416a --- /dev/null +++ b/internal/lru/new.go @@ -0,0 +1,23 @@ +package lru + +import "container/list" + +// New creates a cache with a maximum total weight. +// +// New panics if maxWeight is negative or weightFn is nil. +func New[K comparable, V any](maxWeight int64, weightFn WeightFunc[K, V], onEvict OnEvictFunc[K, V]) *Cache[K, V] { + if maxWeight < 0 { + panic("lru: negative max weight") + } + + if weightFn == nil { + panic("lru: nil weight function") + } + + return &Cache[K, V]{ + maxWeight: maxWeight, + weightFn: weightFn, + onEvict: onEvict, + items: make(map[K]*list.Element), + } +} diff --git a/internal/lru/peek.go b/internal/lru/peek.go new file mode 100644 index 00000000..3a308394 --- /dev/null +++ b/internal/lru/peek.go @@ -0,0 +1,13 @@ +package lru + +// Peek returns value for key without changing recency. +func (cache *Cache[K, V]) Peek(key K) (V, bool) { + elem, ok := cache.items[key] + if !ok { + var zero V + + return zero, false + } + //nolint:forcetypeassert + return elem.Value.(*entry[K, V]).value, true +} diff --git a/internal/lru/remove.go b/internal/lru/remove.go new file mode 100644 index 00000000..79735edf --- /dev/null +++ b/internal/lru/remove.go @@ -0,0 +1,31 @@ +package lru + +import "container/list" + +// Remove deletes key from the cache. +func (cache *Cache[K, V]) Remove(key K) (V, bool) { + elem, ok := cache.items[key] + if !ok { + var zero V + + return zero, false + } + + ent := cache.removeElem(elem) + + return ent.value, true +} + +func (cache *Cache[K, V]) removeElem(elem *list.Element) *entry[K, V] { + //nolint:forcetypeassert + ent := elem.Value.(*entry[K, V]) + cache.lru.Remove(elem) + delete(cache.items, ent.key) + + cache.weight -= ent.weight + if cache.onEvict != nil { + cache.onEvict(ent.key, ent.value) + } + + return ent +} diff --git a/internal/lru/weight.go b/internal/lru/weight.go new file mode 100644 index 00000000..5ef552a1 --- /dev/null +++ b/internal/lru/weight.go @@ -0,0 +1,29 @@ +package lru + +// WeightFunc reports one entry's weight used for eviction budgeting. +// +// Returned weights MUST be non-negative. +type WeightFunc[K comparable, V any] func(key K, value V) int64 + +// Weight returns the current total weight. +func (cache *Cache[K, V]) Weight() int64 { + return cache.weight +} + +// MaxWeight returns the configured total weight budget. +func (cache *Cache[K, V]) MaxWeight() int64 { + return cache.maxWeight +} + +// SetMaxWeight updates the total weight budget and evicts LRU entries as +// needed. +// +// SetMaxWeight panics if maxWeight is negative. +func (cache *Cache[K, V]) SetMaxWeight(maxWeight int64) { + if maxWeight < 0 { + panic("lru: negative max weight") + } + + cache.maxWeight = maxWeight + cache.evictOverBudget() +} -- cgit v1.3.1-10-gc9f91