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
|
// 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) uint32 {
h := fnv.New32()
h.Write(what)
return h.Sum32()
}
// Cache is cache.
type Cache struct {
shards [shardSize]*shard
}
// shard is a cache with random eviction.
type shard struct {
items map[uint32]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.
func (c *Cache) Add(key uint32, el interface{}) {
shard := key & (shardSize - 1)
c.shards[shard].Add(key, el)
}
// Get looks up element index under key.
func (c *Cache) Get(key uint32) (interface{}, bool) {
shard := key & (shardSize - 1)
return c.shards[shard].Get(key)
}
// Remove removes the element indexed with key.
func (c *Cache) Remove(key uint32) {
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
}
// newShard returns a new shard with size.
func newShard(size int) *shard { return &shard{items: make(map[uint32]interface{}), size: size} }
// Add adds element indexed by key into the cache. Any existing element is overwritten
func (s *shard) Add(key uint32, el interface{}) {
l := s.Len()
if l+1 > s.size {
s.Evict()
}
s.Lock()
s.items[key] = el
s.Unlock()
}
// Remove removes the element indexed by key from the cache.
func (s *shard) Remove(key uint32) {
s.Lock()
delete(s.items, key)
s.Unlock()
}
// Evict removes a random element from the cache.
func (s *shard) Evict() {
key := -1
s.RLock()
for k := range s.items {
key = int(k)
break
}
s.RUnlock()
if key == -1 {
// empty cache
return
}
// If this item is gone between the RUnlock and Lock race we don't care.
s.Remove(uint32(key))
}
// Get looks up the element indexed under key.
func (s *shard) Get(key uint32) (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
}
const shardSize = 256
|
