aboutsummaryrefslogtreecommitdiff
path: root/internal/clock
diff options
context:
space:
mode:
Diffstat (limited to 'internal/clock')
-rw-r--r--internal/clock/bench_test.go109
-rw-r--r--internal/clock/cache.go86
-rw-r--r--internal/clock/cache_ops.go51
-rw-r--r--internal/clock/cache_test.go100
-rw-r--r--internal/clock/concurrent_test.go103
-rw-r--r--internal/clock/doc.go9
-rw-r--r--internal/clock/fuzz_test.go53
-rw-r--r--internal/clock/invariant_test.go88
-rw-r--r--internal/clock/shard.go67
-rw-r--r--internal/clock/shard_read.go33
-rw-r--r--internal/clock/shard_test.go149
-rw-r--r--internal/clock/shard_write.go105
12 files changed, 0 insertions, 953 deletions
diff --git a/internal/clock/bench_test.go b/internal/clock/bench_test.go
deleted file mode 100644
index 49d85cde..00000000
--- a/internal/clock/bench_test.go
+++ /dev/null
@@ -1,109 +0,0 @@
-package clock //nolint:testpackage
-
-import (
- "sync/atomic"
- "testing"
-)
-
-func benchWeight(_, _ int) uint64 { return 1 }
-
-// goroutineSeq hands each parallel worker a distinct starting offset
-// so workers don't go in lockstep over identical keys.
-var goroutineSeq atomic.Uint64
-
-func workerOffset() int {
- return int(goroutineSeq.Add(1) * 0x9E3779B1)
-}
-
-func BenchmarkReadHeavy(b *testing.B) {
- // ≈95% Get hits, ≈5% Add, and fits budget.
-
- const n = 100_000
-
- cache := New(n, benchWeight)
- for k := range n {
- cache.Add(k, k)
- }
-
- b.ResetTimer()
- b.RunParallel(func(pb *testing.PB) {
- i := workerOffset()
- for pb.Next() {
- i++
- key := i % n
- if i%20 == 0 {
- cache.Add(key, key)
- } else {
- _, _ = cache.Get(key)
- }
- }
- })
-}
-
-func BenchmarkHotKey(b *testing.B) {
- // Every worker does Get over a relatively small hot set.
-
- const (
- hot = 64
- maxWeight = 4096
- )
-
- cache := New(maxWeight, benchWeight)
- for k := range hot {
- cache.Add(k, k)
- }
-
- b.ResetTimer()
- b.RunParallel(func(pb *testing.PB) {
- i := workerOffset()
- for pb.Next() {
- i++
- _, _ = cache.Get(i % hot)
- }
- })
-}
-
-func BenchmarkMixed(b *testing.B) {
- // Even split of Get and Add over a working set that fits.
-
- const n = 100_000
-
- cache := New(n, benchWeight)
- for k := range n {
- cache.Add(k, k)
- }
-
- b.ResetTimer()
- b.RunParallel(func(pb *testing.PB) {
- i := workerOffset()
- for pb.Next() {
- i++
- key := i % n
- if i%2 == 0 {
- cache.Add(key, key)
- } else {
- _, _ = cache.Get(key)
- }
- }
- })
-}
-
-func BenchmarkChurn(b *testing.B) {
- // Every op inserts a fresh key into a small budget.
- // I don't think this is likely to happen for git delta caches,
- // but this may matter if we use this for other workloads later.
-
- const maxWeight = 4096
-
- cache := New(maxWeight, benchWeight)
-
- b.ResetTimer()
- b.RunParallel(func(pb *testing.PB) {
- base := workerOffset()
- i := 0
- for pb.Next() {
- i++
- cache.Add(base+i, i)
- }
- })
-}
diff --git a/internal/clock/cache.go b/internal/clock/cache.go
deleted file mode 100644
index 31d97082..00000000
--- a/internal/clock/cache.go
+++ /dev/null
@@ -1,86 +0,0 @@
-package clock
-
-import (
- "hash/maphash"
- "runtime"
-
- "lindenii.org/go/lgo/intconv"
-)
-
-// maxShards bounds the shard count.
-//
-// Keep it relatively modest
-// so the per-shard budget
-// stays large enough to admit sizable values.
-const maxShards = 16
-
-// WeightFunc reports one entry's weight, used for eviction budgeting.
-type WeightFunc[K comparable, V any] func(key K, value V) uint64
-
-// Cache is a concurrent, weight-bounded cache
-// with CLOCK eviction.
-//
-// Reads are lock-free;
-// writes lock only the shard that owns the key.
-//
-// Labels: MT-Safe.
-type Cache[K comparable, V any] struct {
- shards []*shard[K, V]
- seed maphash.Seed
- mask uint64
- weightFn WeightFunc[K, V]
-}
-
-// New returns a cache bounded to maxWeight total weight,
-// weighing entries with weightFn.
-//
-// New panics if weightFn is nil.
-func New[K comparable, V any](maxWeight uint64, weightFn WeightFunc[K, V]) *Cache[K, V] {
- if weightFn == nil {
- panic("internal/clock: nil weight function")
- }
-
- count, mask := shardLayout(maxWeight)
- perShard := maxWeight / (mask + 1)
-
- shards := make([]*shard[K, V], count)
- for i := range shards {
- shards[i] = newShard[K, V](perShard)
- }
-
- return &Cache[K, V]{
- shards: shards,
- seed: maphash.MakeSeed(),
- mask: mask,
- weightFn: weightFn,
- }
-}
-
-// shardLayout picks a power-of-two shard count and its address mask.
-//
-// Tracks GOMAXPROCS, capped at maxShards,
-// and is shrunk so the per-shard budget
-// stays at least one while maxWeight is nonzero.
-func shardLayout(maxWeight uint64) (int, uint64) {
- count := 1
- for count < runtime.GOMAXPROCS(0) && count < maxShards {
- count *= 2
- }
-
- countU, err := intconv.IntToUint64(count)
- if err != nil {
- return 1, 0
- }
-
- for countU > maxWeight && countU > 1 {
- count /= 2
- countU /= 2
- }
-
- return count, countU - 1
-}
-
-// shardFor returns the shard that owns key.
-func (cache *Cache[K, V]) shardFor(key K) *shard[K, V] {
- return cache.shards[maphash.Comparable(cache.seed, key)&cache.mask]
-}
diff --git a/internal/clock/cache_ops.go b/internal/clock/cache_ops.go
deleted file mode 100644
index 18958202..00000000
--- a/internal/clock/cache_ops.go
+++ /dev/null
@@ -1,51 +0,0 @@
-package clock
-
-// Add inserts or replaces key, marking it recently used.
-//
-// It reports whether the entry was admitted;
-// an entry heavier than the per-shard budget is rejected
-// and leaves the cache unchanged.
-func (cache *Cache[K, V]) Add(key K, value V) bool {
- return cache.shardFor(key).add(key, value, cache.weightFn(key, value))
-}
-
-// Get returns the value for key and marks it recently used.
-//
-//nolint:ireturn
-func (cache *Cache[K, V]) Get(key K) (V, bool) {
- return cache.shardFor(key).get(key)
-}
-
-// Peek returns the value for key without changing its recency.
-//
-//nolint:ireturn
-func (cache *Cache[K, V]) Peek(key K) (V, bool) {
- return cache.shardFor(key).peek(key)
-}
-
-// Len returns the number of cached entries.
-func (cache *Cache[K, V]) Len() int {
- total := 0
- for _, shard := range cache.shards {
- total += shard.len()
- }
-
- return total
-}
-
-// Weight returns the current total weight across all shards.
-func (cache *Cache[K, V]) Weight() uint64 {
- var total uint64
- for _, shard := range cache.shards {
- total += shard.loadWeight()
- }
-
- return total
-}
-
-// Clear removes all entries.
-func (cache *Cache[K, V]) Clear() {
- for _, shard := range cache.shards {
- shard.clear()
- }
-}
diff --git a/internal/clock/cache_test.go b/internal/clock/cache_test.go
deleted file mode 100644
index 116efdd3..00000000
--- a/internal/clock/cache_test.go
+++ /dev/null
@@ -1,100 +0,0 @@
-package clock_test
-
-import (
- "fmt"
- "strings"
- "testing"
-
- "lindenii.org/go/furgit/internal/clock"
- "lindenii.org/go/lgo/intconv"
-)
-
-func byteWeight(_ string, value string) uint64 {
- weight, err := intconv.IntToUint64(len(value))
- if err != nil {
- return 0
- }
-
- return weight
-}
-
-func TestCacheAddGetPeek(t *testing.T) {
- t.Parallel()
-
- cache := clock.New(1<<20, byteWeight)
-
- if !cache.Add("a", "alpha") {
- t.Fatalf("Add(a) should succeed")
- }
-
- if got, ok := cache.Get("a"); !ok || got != "alpha" {
- t.Fatalf("Get(a) = (%q, %v), want (alpha, true)", got, ok)
- }
-
- if got, ok := cache.Peek("a"); !ok || got != "alpha" {
- t.Fatalf("Peek(a) = (%q, %v), want (alpha, true)", got, ok)
- }
-
- if _, ok := cache.Get("missing"); ok {
- t.Fatalf("Get(missing) should miss")
- }
-}
-
-func TestCacheWeightStaysBounded(t *testing.T) {
- t.Parallel()
-
- const maxWeight = 4096
-
- cache := clock.New(maxWeight, byteWeight)
- value := strings.Repeat("x", 64)
-
- for i := range 1000 {
- cache.Add(fmt.Sprintf("key-%d", i), value)
- }
-
- if got := cache.Weight(); got > maxWeight {
- t.Fatalf("weight = %d, exceeds max %d", got, maxWeight)
- }
-}
-
-func TestCacheLenAndClear(t *testing.T) {
- t.Parallel()
-
- cache := clock.New(1<<20, byteWeight)
-
- for i := range 10 {
- cache.Add(fmt.Sprintf("key-%d", i), "v")
- }
-
- if got := cache.Len(); got != 10 {
- t.Fatalf("Len = %d, want 10", got)
- }
-
- cache.Clear()
-
- if got := cache.Len(); got != 0 {
- t.Fatalf("Len after Clear = %d, want 0", got)
- }
-
- if got := cache.Weight(); got != 0 {
- t.Fatalf("Weight after Clear = %d, want 0", got)
- }
-}
-
-func TestCacheRejectsOversized(t *testing.T) {
- t.Parallel()
-
- cache := clock.New(4, byteWeight)
-
- if cache.Add("a", "xxxxx") {
- t.Fatalf("oversized Add should report false")
- }
-
- if _, ok := cache.Get("a"); ok {
- t.Fatalf("oversized entry must not be cached")
- }
-
- if got := cache.Weight(); got != 0 {
- t.Fatalf("weight = %d, want 0", got)
- }
-}
diff --git a/internal/clock/concurrent_test.go b/internal/clock/concurrent_test.go
deleted file mode 100644
index 86283a9b..00000000
--- a/internal/clock/concurrent_test.go
+++ /dev/null
@@ -1,103 +0,0 @@
-package clock //nolint:testpackage
-
-import (
- "sync"
- "testing"
-)
-
-func keyValue(key int) int {
- return key*1000003 + 7
-}
-
-func TestConcurrentStress(t *testing.T) {
- t.Parallel()
-
- const (
- maxWeight = 512
- keys = 400
- workers = 8
- rounds = 5000
- )
-
- cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 })
-
- var wg sync.WaitGroup
-
- for worker := range workers {
- wg.Go(func() {
- for i := range rounds {
- key := (worker*7 + i) % keys
-
- switch i % 4 {
- case 0, 1:
- cache.Add(key, keyValue(key))
- case 2:
- if got, ok := cache.Get(key); ok && got != keyValue(key) {
- t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key))
- }
- case 3:
- if got, ok := cache.Peek(key); ok && got != keyValue(key) {
- t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key))
- }
- }
- }
- })
- }
-
- wg.Wait()
-
- checkCache(t, cache)
-
- if got := cache.Weight(); got > maxWeight {
- t.Fatalf("weight %d exceeds max %d", got, maxWeight)
- }
-}
-
-func TestReadDuringEviction(t *testing.T) {
- t.Parallel()
-
- const (
- maxWeight = 8
- hot = 64
- writers = 2
- readers = 6
- rounds = 20000
- )
-
- cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 })
-
- var wg sync.WaitGroup
-
- for range writers {
- wg.Go(func() {
- for i := range rounds {
- key := i % hot
- cache.Add(key, keyValue(key))
- }
- })
- }
-
- for range readers {
- wg.Go(func() {
- for i := range rounds {
- key := i % hot
-
- if got, ok := cache.Get(key); ok && got != keyValue(key) {
- t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key))
- }
-
- if got, ok := cache.Peek(key); ok && got != keyValue(key) {
- t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key))
- }
- }
- })
- }
-
- wg.Wait()
-
- checkCache(t, cache)
-
- if got := cache.Weight(); got > maxWeight {
- t.Fatalf("weight %d exceeds max %d", got, maxWeight)
- }
-}
diff --git a/internal/clock/doc.go b/internal/clock/doc.go
deleted file mode 100644
index 6f28805b..00000000
--- a/internal/clock/doc.go
+++ /dev/null
@@ -1,9 +0,0 @@
-// Package clock provides a concurrent, weight-bounded object cache.
-//
-// The cache is sharded by key,
-// and each shard owns an independent fraction of the total budget.
-// An entry heavier than that per-shard fraction is never admitted,
-// so callers should keep the total budget well above the largest value.
-//
-// Labels: MT-Safe.
-package clock
diff --git a/internal/clock/fuzz_test.go b/internal/clock/fuzz_test.go
deleted file mode 100644
index af0d4024..00000000
--- a/internal/clock/fuzz_test.go
+++ /dev/null
@@ -1,53 +0,0 @@
-package clock //nolint:testpackage
-
-import "testing"
-
-// FuzzShard replays a decoded op stream against one shard,
-// checking the value oracle and invariants after every op.
-func FuzzShard(f *testing.F) {
- f.Add([]byte{})
- f.Add([]byte{0, 1, 10, 0, 2, 10, 0, 3, 10, 0, 4, 10, 1, 1, 0, 0, 5, 10})
- f.Add([]byte{0, 7, 200, 0, 7, 5, 2, 7, 0, 3, 0, 0, 0, 8, 8})
-
- f.Fuzz(func(t *testing.T, program []byte) {
- const maxWeight = 32
-
- shard := newShard[uint8, uint64](maxWeight)
- shadow := make(map[uint8]uint64)
-
- var nonce uint64
-
- for i := 0; i+2 < len(program); i += 3 {
- key := program[i+1]
- weight := uint64(program[i+2])
-
- switch program[i] % 4 {
- case 0: // add
- nonce++
- value := nonce
-
- admitted := shard.add(key, value, weight)
- if admitted != (weight <= maxWeight) {
- t.Fatalf("add(%d, w=%d) admitted=%v, want %v", key, weight, admitted, weight <= maxWeight)
- }
-
- if admitted {
- shadow[key] = value
- }
- case 1: // get
- if got, ok := shard.get(key); ok && got != shadow[key] {
- t.Fatalf("get(%d) = %d, want %d", key, got, shadow[key])
- }
- case 2: // peek
- if got, ok := shard.peek(key); ok && got != shadow[key] {
- t.Fatalf("peek(%d) = %d, want %d", key, got, shadow[key])
- }
- case 3: // clear
- shard.clear()
- clear(shadow)
- }
-
- checkShard(t, shard)
- }
- })
-}
diff --git a/internal/clock/invariant_test.go b/internal/clock/invariant_test.go
deleted file mode 100644
index 2efd7ff9..00000000
--- a/internal/clock/invariant_test.go
+++ /dev/null
@@ -1,88 +0,0 @@
-package clock //nolint:testpackage
-
-import "testing"
-
-// checkShard verifies a shard's structural invariants at a quiescent point.
-//
-// It must be called with no concurrent operations in flight.
-func checkShard[K comparable, V any](t *testing.T, shard *shard[K, V]) {
- t.Helper()
-
- shard.mu.Lock()
- defer shard.mu.Unlock()
-
- ringLen := 0
-
- var ringWeight uint64
-
- seen := make(map[*entry[K, V]]struct{})
-
- if shard.hand != nil { //nolint:nestif
- for e := shard.hand; ; e = e.next {
- if e.prev == nil || e.next == nil {
- t.Fatalf("nil ring link at key %v", e.key)
- }
-
- if e.next.prev != e || e.prev.next != e {
- t.Fatalf("ring links not reciprocal at key %v", e.key)
- }
-
- if _, dup := seen[e]; dup {
- t.Fatalf("ring revisits a node before returning to the hand")
- }
-
- seen[e] = struct{}{}
- ringLen++
- ringWeight += e.weight
-
- if got, ok := shard.items.Load(e.key); !ok || got != e {
- t.Fatalf("ring node %v is not mapped to itself", e.key)
- }
-
- if e.next == shard.hand {
- break
- }
- }
- }
-
- if ringLen != shard.count {
- t.Fatalf("ring length %d != count %d", ringLen, shard.count)
- }
-
- if ringWeight != shard.weight {
- t.Fatalf("ring weight %d != shard weight %d", ringWeight, shard.weight)
- }
-
- if shard.weight > shard.maxWeight {
- t.Fatalf("weight %d exceeds budget %d", shard.weight, shard.maxWeight)
- }
-
- if (shard.hand == nil) != (shard.count == 0) {
- t.Fatalf("hand/count disagree: hand=%v count=%d", shard.hand, shard.count)
- }
-
- mapLen := 0
-
- shard.items.Range(func(_ K, e *entry[K, V]) bool {
- mapLen++
-
- if _, ok := seen[e]; !ok {
- t.Fatalf("mapped entry %v missing from ring", e.key)
- }
-
- return true
- })
-
- if mapLen != shard.count {
- t.Fatalf("map size %d != count %d", mapLen, shard.count)
- }
-}
-
-// checkCache verifies every shard's invariants.
-func checkCache[K comparable, V any](t *testing.T, cache *Cache[K, V]) {
- t.Helper()
-
- for _, shard := range cache.shards {
- checkShard(t, shard)
- }
-}
diff --git a/internal/clock/shard.go b/internal/clock/shard.go
deleted file mode 100644
index 22e58b2f..00000000
--- a/internal/clock/shard.go
+++ /dev/null
@@ -1,67 +0,0 @@
-package clock
-
-import (
- "sync"
- "sync/atomic"
-
- lsync "lindenii.org/go/lgo/sync"
-)
-
-// entry is one cached key/value with CLOCK.
-type entry[K comparable, V any] struct {
- key K
- value V
- weight uint64
- prev, next *entry[K, V]
-
- // referenced is set on access and cleared by the eviction sweep;
- // prev and next link the entry into its shard's ring.
- referenced atomic.Bool
-}
-
-// shard is an independently locked CLOCK cache.
-type shard[K comparable, V any] struct {
- items lsync.Map[K, *entry[K, V]]
-
- hand *entry[K, V]
- weight uint64
- count int
- maxWeight uint64
-
- // mu protects the ring, hand, totals, and writes.
- mu sync.Mutex
-}
-
-// newShard returns an empty shard with the given weight budget.
-func newShard[K comparable, V any](maxWeight uint64) *shard[K, V] {
- return &shard[K, V]{ //nolint:exhaustruct
- maxWeight: maxWeight,
- }
-}
-
-// len returns the shard's entry count.
-func (shard *shard[K, V]) len() int {
- shard.mu.Lock()
- defer shard.mu.Unlock()
-
- return shard.count
-}
-
-// loadWeight returns the shard's current total weight.
-func (shard *shard[K, V]) loadWeight() uint64 {
- shard.mu.Lock()
- defer shard.mu.Unlock()
-
- return shard.weight
-}
-
-// clear removes every entry.
-func (shard *shard[K, V]) clear() {
- shard.mu.Lock()
- defer shard.mu.Unlock()
-
- shard.items.Clear()
- shard.hand = nil
- shard.weight = 0
- shard.count = 0
-}
diff --git a/internal/clock/shard_read.go b/internal/clock/shard_read.go
deleted file mode 100644
index 624e3409..00000000
--- a/internal/clock/shard_read.go
+++ /dev/null
@@ -1,33 +0,0 @@
-package clock
-
-// get returns the value for key and marks it referenced.
-//
-//nolint:ireturn
-func (shard *shard[K, V]) get(key K) (V, bool) {
- e, ok := shard.items.Load(key)
- if !ok {
- var zero V
-
- return zero, false
- }
-
- if !e.referenced.Load() {
- e.referenced.Store(true)
- }
-
- return e.value, true
-}
-
-// peek returns the value for key without affecting eviction.
-//
-//nolint:ireturn
-func (shard *shard[K, V]) peek(key K) (V, bool) {
- e, ok := shard.items.Load(key)
- if !ok {
- var zero V
-
- return zero, false
- }
-
- return e.value, true
-}
diff --git a/internal/clock/shard_test.go b/internal/clock/shard_test.go
deleted file mode 100644
index d974a30e..00000000
--- a/internal/clock/shard_test.go
+++ /dev/null
@@ -1,149 +0,0 @@
-package clock //nolint:testpackage
-
-import "testing"
-
-func TestShardEvictsOldest(t *testing.T) {
- t.Parallel()
-
- shard := newShard[string, string](8)
- shard.add("a", "a", 4)
- shard.add("b", "b", 4)
- shard.add("c", "c", 4) // overflows, evicts
-
- if _, ok := shard.peek("a"); ok {
- t.Fatalf("a should have been evicted")
- }
-
- for _, key := range []string{"b", "c"} {
- if _, ok := shard.peek(key); !ok {
- t.Fatalf("%s should remain present", key)
- }
- }
-
- if got := shard.loadWeight(); got != 8 {
- t.Fatalf("weight = %d, want 8", got)
- }
-
- if got := shard.len(); got != 2 {
- t.Fatalf("len = %d, want 2", got)
- }
-}
-
-func TestShardGetGivesSecondChance(t *testing.T) {
- t.Parallel()
-
- shard := newShard[string, string](8)
- shard.add("a", "a", 4)
- shard.add("b", "b", 4)
- shard.add("c", "c", 4) // a evicted; b and c survive
-
- if _, ok := shard.get("b"); !ok {
- t.Fatalf("get(b) should hit")
- }
-
- shard.add("d", "d", 4) // b was just touched, so c is evicted instead
-
- if _, ok := shard.peek("c"); ok {
- t.Fatalf("c should have been evicted after b was touched")
- }
-
- for _, key := range []string{"b", "d"} {
- if _, ok := shard.peek(key); !ok {
- t.Fatalf("%s should remain present", key)
- }
- }
-}
-
-func TestShardPeekGivesNoSecondChance(t *testing.T) {
- t.Parallel()
-
- shard := newShard[string, string](8)
- shard.add("a", "a", 4)
- shard.add("b", "b", 4)
- shard.add("c", "c", 4) // a is evicted; b and c survive with cleared bits
-
- if _, ok := shard.peek("b"); !ok {
- t.Fatalf("peek(b) should hit")
- }
-
- shard.add("d", "d", 4) // peek did not refresh b, so b is evicted
-
- if _, ok := shard.peek("b"); ok {
- t.Fatalf("b should have been evicted; peek must not grant a second chance")
- }
-
- for _, key := range []string{"c", "d"} {
- if _, ok := shard.peek(key); !ok {
- t.Fatalf("%s should remain present", key)
- }
- }
-}
-
-func TestShardReplaceUpdatesWeight(t *testing.T) {
- t.Parallel()
-
- shard := newShard[string, string](100)
- shard.add("a", "old", 4)
- shard.add("a", "new", 6)
-
- if got, ok := shard.peek("a"); !ok || got != "new" {
- t.Fatalf("peek(a) = (%q, %v), want (new, true)", got, ok)
- }
-
- if got := shard.loadWeight(); got != 6 {
- t.Fatalf("weight = %d, want 6", got)
- }
-
- if got := shard.len(); got != 1 {
- t.Fatalf("len = %d, want 1", got)
- }
-}
-
-func TestShardRejectsOversized(t *testing.T) {
- t.Parallel()
-
- shard := newShard[string, string](5)
- shard.add("a", "x", 3)
-
- if shard.add("b", "big", 6) {
- t.Fatalf("oversized add should report false")
- }
-
- if shard.add("a", "huge", 6) {
- t.Fatalf("oversized replace should report false")
- }
-
- if got, ok := shard.peek("a"); !ok || got != "x" {
- t.Fatalf("peek(a) = (%q, %v), want (x, true); cache must be unchanged", got, ok)
- }
-
- if _, ok := shard.peek("b"); ok {
- t.Fatalf("b must not have been admitted")
- }
-
- if got := shard.loadWeight(); got != 3 {
- t.Fatalf("weight = %d, want 3", got)
- }
-}
-
-func TestShardClear(t *testing.T) {
- t.Parallel()
-
- shard := newShard[string, string](100)
- shard.add("a", "a", 4)
- shard.add("b", "b", 4)
-
- shard.clear()
-
- if got := shard.loadWeight(); got != 0 {
- t.Fatalf("weight = %d, want 0", got)
- }
-
- if got := shard.len(); got != 0 {
- t.Fatalf("len = %d, want 0", got)
- }
-
- if _, ok := shard.peek("a"); ok {
- t.Fatalf("a should be gone after clear")
- }
-}
diff --git a/internal/clock/shard_write.go b/internal/clock/shard_write.go
deleted file mode 100644
index 40ddabd0..00000000
--- a/internal/clock/shard_write.go
+++ /dev/null
@@ -1,105 +0,0 @@
-package clock
-
-// add inserts or replaces key, then evicts down to budget.
-//
-// It reports whether the entry was admitted;
-// an entry heavier than the shard budget is rejected
-// and leaves the shard unchanged.
-func (shard *shard[K, V]) add(key K, value V, weight uint64) bool {
- if weight > shard.maxWeight {
- return false
- }
-
- shard.mu.Lock()
- defer shard.mu.Unlock()
-
- if old, ok := shard.items.Load(key); ok {
- shard.unlink(old)
- shard.items.Delete(key)
- shard.weight -= old.weight
- shard.count--
- }
-
- e := &entry[K, V]{ //nolint:exhaustruct
- key: key,
- value: value,
- weight: weight,
- }
- e.referenced.Store(true)
-
- shard.linkBeforeHand(e)
- shard.items.Store(key, e)
- shard.weight += weight
- shard.count++
-
- shard.evict()
-
- return true
-}
-
-// evict advances the clock hand until the shard is within budget.
-//
-// A referenced entry is spared once, its bit cleared;
-// after a full rotation of spared entries the next is evicted regardless,
-// so a flood of concurrent reads cannot stall progress.
-func (shard *shard[K, V]) evict() {
- skips := 0
-
- for shard.weight > shard.maxWeight && shard.hand != nil {
- victim := shard.hand
-
- if victim.referenced.Load() && skips < shard.count {
- victim.referenced.Store(false)
- shard.hand = victim.next
- skips++
-
- continue
- }
-
- shard.unlink(victim)
- shard.items.Delete(victim.key)
- shard.weight -= victim.weight
- shard.count--
- skips = 0
- }
-}
-
-// linkBeforeHand inserts e just behind the hand,
-// so a full rotation passes before the sweep examines it.
-func (shard *shard[K, V]) linkBeforeHand(e *entry[K, V]) {
- if shard.hand == nil {
- e.prev = e
- e.next = e
- shard.hand = e
-
- return
- }
-
- tail := shard.hand.prev
- tail.next = e
- e.prev = tail
- e.next = shard.hand
- shard.hand.prev = e
-}
-
-// unlink removes e from the ring,
-// moving the hand off e when it points at it.
-func (shard *shard[K, V]) unlink(e *entry[K, V]) {
- if e.next == e {
- shard.hand = nil
- e.prev = nil
- e.next = nil
-
- return
- }
-
- e.prev.next = e.next
- e.next.prev = e.prev
-
- if shard.hand == e {
- shard.hand = e.next
- }
-
- e.prev = nil
- e.next = nil
-}