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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
// Package cache implements a cache. The cache hold 256 shards, each shard
// holds a cache: a map with a mutex. There is no fancy expunge algorithm, it
// just randomly evicts elements when it gets full.
package cache
import (
"hash/fnv"
"sync"
)
// Hash returns the FNV hash of what.
func Hash(what []byte) uint64 {
h := fnv.New64()
h.Write(what)
return h.Sum64()
}
// Cache is cache.
type Cache struct {
shards [shardSize]*shard
}
// shard is a cache with random eviction.
type shard struct {
items map[uint64]interface{}
size int
sync.RWMutex
}
// New returns a new cache.
func New(size int) *Cache {
ssize := size / shardSize
if ssize < 4 {
ssize = 4
}
c := &Cache{}
// Initialize all the shards
for i := 0; i < shardSize; i++ {
c.shards[i] = newShard(ssize)
}
return c
}
// Add adds a new element to the cache. If the element already exists it is overwritten.
// Returns true if an existing element was evicted to make room for this element.
func (c *Cache) Add(key uint64, el interface{}) bool {
shard := key & (shardSize - 1)
return c.shards[shard].Add(key, el)
}
// Get looks up element index under key.
func (c *Cache) Get(key uint64) (interface{}, bool) {
shard := key & (shardSize - 1)
return c.shards[shard].Get(key)
}
// Remove removes the element indexed with key.
func (c *Cache) Remove(key uint64) {
shard := key & (shardSize - 1)
c.shards[shard].Remove(key)
}
// Len returns the number of elements in the cache.
func (c *Cache) Len() int {
l := 0
for _, s := range c.shards {
l += s.Len()
}
return l
}
// Walk walks each shard in the cache.
func (c *Cache) Walk(f func(map[uint64]interface{}, uint64) bool) {
for _, s := range c.shards {
s.Walk(f)
}
}
// newShard returns a new shard with size.
func newShard(size int) *shard { return &shard{items: make(map[uint64]interface{}), size: size} }
// Add adds element indexed by key into the cache. Any existing element is overwritten
// Returns true if an existing element was evicted to make room for this element.
func (s *shard) Add(key uint64, el interface{}) bool {
eviction := false
s.Lock()
if len(s.items) >= s.size {
if _, ok := s.items[key]; !ok {
for k := range s.items {
delete(s.items, k)
eviction = true
break
}
}
}
s.items[key] = el
s.Unlock()
return eviction
}
// Remove removes the element indexed by key from the cache.
func (s *shard) Remove(key uint64) {
s.Lock()
delete(s.items, key)
s.Unlock()
}
// Evict removes a random element from the cache.
func (s *shard) Evict() {
s.Lock()
for k := range s.items {
delete(s.items, k)
break
}
s.Unlock()
}
// Get looks up the element indexed under key.
func (s *shard) Get(key uint64) (interface{}, bool) {
s.RLock()
el, found := s.items[key]
s.RUnlock()
return el, found
}
// Len returns the current length of the cache.
func (s *shard) Len() int {
s.RLock()
l := len(s.items)
s.RUnlock()
return l
}
// Walk walks the shard for each element the function f is executed while holding a write lock.
func (s *shard) Walk(f func(map[uint64]interface{}, uint64) bool) {
items := make([]uint64, len(s.items))
s.RLock()
i := 0
for k := range s.items {
items[i] = k
i++
}
s.RUnlock()
for _, k := range items {
s.Lock()
ok := f(s.items, k)
s.Unlock()
if !ok {
return
}
}
}
const shardSize = 256
|
