1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
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)
}
}
|
