aboutsummaryrefslogtreecommitdiff
path: root/internal/lru
diff options
context:
space:
mode:
authorGravatar Runxi Yu2026-03-04 08:26:56 +0800
committerGravatar Runxi Yu2026-03-04 08:59:53 +0800
commitab7501be34032fb9e5c48726a68ae90a917af9eb (patch)
tree20d005647569befea8133e953c3270e8fd2a2a5b /internal/lru
parent*: gofumpt (diff)
signatureNo signature
*: Lint
Diffstat (limited to 'internal/lru')
-rw-r--r--internal/lru/lru.go14
-rw-r--r--internal/lru/lru_test.go31
2 files changed, 45 insertions, 0 deletions
diff --git a/internal/lru/lru.go b/internal/lru/lru.go
index 585aaa3f..fcbab646 100644
--- a/internal/lru/lru.go
+++ b/internal/lru/lru.go
@@ -39,9 +39,11 @@ func New[K comparable, V any](maxWeight int64, weightFn WeightFunc[K, V], onEvic
if maxWeight < 0 {
panic("lru: negative max weight")
}
+
if weightFn == nil {
panic("lru: nil weight function")
}
+
return &Cache[K, V]{
maxWeight: maxWeight,
weightFn: weightFn,
@@ -61,6 +63,7 @@ func (cache *Cache[K, V]) Add(key K, value V) bool {
if w < 0 {
panic("lru: negative entry weight")
}
+
if w > cache.maxWeight {
return false
}
@@ -79,6 +82,7 @@ func (cache *Cache[K, V]) Add(key K, value V) bool {
cache.weight += w
cache.evictOverBudget()
+
return true
}
@@ -87,8 +91,10 @@ 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
@@ -99,6 +105,7 @@ 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
@@ -110,9 +117,12 @@ 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
}
@@ -148,6 +158,7 @@ func (cache *Cache[K, V]) SetMaxWeight(maxWeight int64) {
if maxWeight < 0 {
panic("lru: negative max weight")
}
+
cache.maxWeight = maxWeight
cache.evictOverBudget()
}
@@ -158,6 +169,7 @@ func (cache *Cache[K, V]) evictOverBudget() {
if elem == nil {
return
}
+
cache.removeElem(elem)
}
}
@@ -167,9 +179,11 @@ func (cache *Cache[K, V]) removeElem(elem *list.Element) *entry[K, V] {
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/lru_test.go b/internal/lru/lru_test.go
index adfec403..006a32b8 100644
--- a/internal/lru/lru_test.go
+++ b/internal/lru/lru_test.go
@@ -27,9 +27,11 @@ func TestCacheEvictsLRUAndGetUpdatesRecency(t *testing.T) {
if _, ok := cache.Peek("a"); ok {
t.Fatalf("expected a to be evicted")
}
+
if _, ok := cache.Peek("b"); !ok {
t.Fatalf("expected b to be present")
}
+
if _, ok := cache.Peek("c"); !ok {
t.Fatalf("expected c to be present")
}
@@ -37,14 +39,17 @@ func TestCacheEvictsLRUAndGetUpdatesRecency(t *testing.T) {
if _, ok := cache.Get("b"); !ok {
t.Fatalf("Get(b) should hit")
}
+
cache.Add("d", testValue{weight: 4, label: "d"})
if _, ok := cache.Peek("c"); ok {
t.Fatalf("expected c to be evicted after b was touched")
}
+
if _, ok := cache.Peek("b"); !ok {
t.Fatalf("expected b to remain present")
}
+
if _, ok := cache.Peek("d"); !ok {
t.Fatalf("expected d to be present")
}
@@ -60,11 +65,13 @@ func TestCachePeekDoesNotUpdateRecency(t *testing.T) {
if _, ok := cache.Peek("a"); !ok {
t.Fatalf("Peek(a) should hit")
}
+
cache.Add("c", testValue{weight: 2, label: "c"})
if _, ok := cache.Peek("a"); ok {
t.Fatalf("expected a to be evicted; Peek must not update recency")
}
+
if _, ok := cache.Peek("b"); !ok {
t.Fatalf("expected b to remain present")
}
@@ -74,6 +81,7 @@ func TestCacheReplaceAndResize(t *testing.T) {
t.Parallel()
var evicted []string
+
cache := lru.New[string, testValue](10, weightFn, func(key string, value testValue) {
evicted = append(evicted, key+":"+value.label)
})
@@ -85,17 +93,21 @@ func TestCacheReplaceAndResize(t *testing.T) {
if cache.Weight() != 10 {
t.Fatalf("Weight() = %d, want 10", cache.Weight())
}
+
if got, ok := cache.Peek("a"); !ok || got.label != "new" {
t.Fatalf("Peek(a) = (%+v,%v), want new,true", got, ok)
}
+
if !slices.Equal(evicted, []string{"a:old"}) {
t.Fatalf("evicted = %v, want [a:old]", evicted)
}
cache.SetMaxWeight(8)
+
if _, ok := cache.Peek("b"); ok {
t.Fatalf("expected b to be evicted after shrinking max weight")
}
+
if !slices.Equal(evicted, []string{"a:old", "b:b"}) {
t.Fatalf("evicted = %v, want [a:old b:b]", evicted)
}
@@ -105,6 +117,7 @@ func TestCacheRejectsOversizedWithoutMutation(t *testing.T) {
t.Parallel()
var evicted []string
+
cache := lru.New[string, testValue](5, weightFn, func(key string, value testValue) {
evicted = append(evicted, key)
})
@@ -113,12 +126,15 @@ func TestCacheRejectsOversizedWithoutMutation(t *testing.T) {
if ok := cache.Add("b", testValue{weight: 6, label: "b"}); ok {
t.Fatalf("Add oversized should return false")
}
+
if got, ok := cache.Peek("a"); !ok || got.label != "a" {
t.Fatalf("cache should remain unchanged after oversized add")
}
+
if cache.Weight() != 3 {
t.Fatalf("Weight() = %d, want 3", cache.Weight())
}
+
if len(evicted) != 0 {
t.Fatalf("evicted = %v, want none", evicted)
}
@@ -126,9 +142,11 @@ func TestCacheRejectsOversizedWithoutMutation(t *testing.T) {
if ok := cache.Add("a", testValue{weight: 6, label: "new"}); ok {
t.Fatalf("oversized replace should return false")
}
+
if got, ok := cache.Peek("a"); !ok || got.label != "a" {
t.Fatalf("existing key should remain unchanged after oversized replace")
}
+
if len(evicted) != 0 {
t.Fatalf("evicted = %v, want none", evicted)
}
@@ -138,6 +156,7 @@ func TestCacheRemoveAndClear(t *testing.T) {
t.Parallel()
var evicted []string
+
cache := lru.New[string, testValue](10, weightFn, func(key string, value testValue) {
evicted = append(evicted, key)
})
@@ -150,11 +169,13 @@ func TestCacheRemoveAndClear(t *testing.T) {
if !ok || removed.label != "b" {
t.Fatalf("Remove(b) = (%+v,%v), want b,true", removed, ok)
}
+
if cache.Len() != 2 || cache.Weight() != 6 {
t.Fatalf("post-remove Len/Weight = %d/%d, want 2/6", cache.Len(), cache.Weight())
}
cache.Clear()
+
if cache.Len() != 0 || cache.Weight() != 0 {
t.Fatalf("post-clear Len/Weight = %d/%d, want 0/0", cache.Len(), cache.Weight())
}
@@ -170,45 +191,55 @@ func TestCachePanicsForInvalidConfiguration(t *testing.T) {
t.Run("negative max", func(t *testing.T) {
t.Parallel()
+
defer func() {
if recover() == nil {
t.Fatalf("expected panic")
}
}()
+
_ = lru.New[string, testValue](-1, weightFn, nil)
})
t.Run("nil weight function", func(t *testing.T) {
t.Parallel()
+
defer func() {
if recover() == nil {
t.Fatalf("expected panic")
}
}()
+
_ = lru.New[string, testValue](1, nil, nil)
})
t.Run("negative entry weight", func(t *testing.T) {
t.Parallel()
+
cache := lru.New[string, testValue](10, func(_ string, _ testValue) int64 {
return -1
}, nil)
+
defer func() {
if recover() == nil {
t.Fatalf("expected panic")
}
}()
+
cache.Add("x", testValue{weight: 1, label: "x"})
})
t.Run("set negative max", func(t *testing.T) {
t.Parallel()
+
cache := lru.New[string, testValue](10, weightFn, nil)
+
defer func() {
if recover() == nil {
t.Fatalf("expected panic")
}
}()
+
cache.SetMaxWeight(-1)
})
}