diff options
| author | 2026-03-04 08:26:56 +0800 | |
|---|---|---|
| committer | 2026-03-04 08:59:53 +0800 | |
| commit | ab7501be34032fb9e5c48726a68ae90a917af9eb (patch) | |
| tree | 20d005647569befea8133e953c3270e8fd2a2a5b /internal/lru | |
| parent | *: gofumpt (diff) | |
| signature | No signature | |
*: Lint
Diffstat (limited to 'internal/lru')
| -rw-r--r-- | internal/lru/lru.go | 14 | ||||
| -rw-r--r-- | internal/lru/lru_test.go | 31 |
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) }) } |
