From 2a7a1e8c95025da4fbd6c398a5e51672fb1a8bd2 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Sun, 22 Feb 2026 12:30:20 +0800 Subject: internal/lru: Rename from internal/cache/lru --- internal/cache/cache.go | 2 - internal/cache/lru/lru.go | 175 --------------------------------- internal/cache/lru/lru_test.go | 214 ----------------------------------------- 3 files changed, 391 deletions(-) delete mode 100644 internal/cache/cache.go delete mode 100644 internal/cache/lru/lru.go delete mode 100644 internal/cache/lru/lru_test.go (limited to 'internal/cache') diff --git a/internal/cache/cache.go b/internal/cache/cache.go deleted file mode 100644 index 17633906..00000000 --- a/internal/cache/cache.go +++ /dev/null @@ -1,2 +0,0 @@ -// Package cache encapsulates cache-providing subpackages for direct use. -package cache diff --git a/internal/cache/lru/lru.go b/internal/cache/lru/lru.go deleted file mode 100644 index 585aaa3f..00000000 --- a/internal/cache/lru/lru.go +++ /dev/null @@ -1,175 +0,0 @@ -// 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/cache/lru/lru_test.go b/internal/cache/lru/lru_test.go deleted file mode 100644 index fbd20f0b..00000000 --- a/internal/cache/lru/lru_test.go +++ /dev/null @@ -1,214 +0,0 @@ -package lru_test - -import ( - "slices" - "testing" - - "codeberg.org/lindenii/furgit/internal/cache/lru" -) - -type testValue struct { - weight int64 - label string -} - -func weightFn(key string, value testValue) int64 { - return value.weight -} - -func TestCacheEvictsLRUAndGetUpdatesRecency(t *testing.T) { - t.Parallel() - - cache := lru.New[string, testValue](8, weightFn, nil) - cache.Add("a", testValue{weight: 4, label: "a"}) - cache.Add("b", testValue{weight: 4, label: "b"}) - cache.Add("c", testValue{weight: 4, label: "c"}) - - 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") - } - - 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") - } -} - -func TestCachePeekDoesNotUpdateRecency(t *testing.T) { - t.Parallel() - - cache := lru.New[string, testValue](4, weightFn, nil) - cache.Add("a", testValue{weight: 2, label: "a"}) - cache.Add("b", testValue{weight: 2, label: "b"}) - - 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") - } -} - -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) - }) - - cache.Add("a", testValue{weight: 4, label: "old"}) - cache.Add("b", testValue{weight: 4, label: "b"}) - cache.Add("a", testValue{weight: 6, label: "new"}) - - 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) - } -} - -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) - }) - cache.Add("a", testValue{weight: 3, label: "a"}) - - 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) - } - - 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) - } -} - -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) - }) - - cache.Add("a", testValue{weight: 2, label: "a"}) - cache.Add("b", testValue{weight: 3, label: "b"}) - cache.Add("c", testValue{weight: 4, label: "c"}) - - removed, ok := cache.Remove("b") - 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()) - } - - // Remove emits b, then Clear emits oldest-to-newest among remaining: a, c. - if !slices.Equal(evicted, []string{"b", "a", "c"}) { - t.Fatalf("evicted = %v, want [b a c]", evicted) - } -} - -func TestCachePanicsForInvalidConfiguration(t *testing.T) { - t.Parallel() - - 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) - }) -} -- cgit v1.3.1-10-gc9f91