-
Notifications
You must be signed in to change notification settings - Fork 3
/
cache.go
101 lines (85 loc) · 1.66 KB
/
cache.go
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
package lm2
import (
"math/rand"
"sync"
)
type recordCache struct {
cache map[int64]*record
maxKeyRecord *record
size int
preventPurge bool
lock sync.RWMutex
}
func newCache(size int) *recordCache {
return &recordCache{
cache: map[int64]*record{},
maxKeyRecord: nil,
size: size,
}
}
func (rc *recordCache) findLastLessThan(key string) int64 {
rc.lock.RLock()
defer rc.lock.RUnlock()
if rc.maxKeyRecord != nil {
if rc.maxKeyRecord.Key < key {
return rc.maxKeyRecord.Offset
}
}
max := ""
maxOffset := int64(0)
for offset, record := range rc.cache {
if record.Key >= key {
continue
}
if record.Key > max {
max = record.Key
maxOffset = offset
}
}
return maxOffset
}
func (rc *recordCache) push(rec *record) {
rc.lock.RLock()
if rc.maxKeyRecord == nil || rc.maxKeyRecord.Key < rec.Key {
rc.lock.RUnlock()
rc.lock.Lock()
if rc.maxKeyRecord == nil || rc.maxKeyRecord.Key < rec.Key {
rc.maxKeyRecord = rec
}
rc.lock.Unlock()
return
}
if len(rc.cache) == rc.size && rand.Float32() >= cacheProb/float32(len(rec.Next)) {
rc.lock.RUnlock()
return
}
rc.lock.RUnlock()
rc.lock.Lock()
rc.cache[rec.Offset] = rec
if !rc.preventPurge {
rc.purge()
}
rc.lock.Unlock()
}
func (rc *recordCache) purge() {
purged := 0
for len(rc.cache) > rc.size {
deletedKey := int64(0)
for k := range rc.cache {
if k == rc.maxKeyRecord.Offset {
continue
}
deletedKey = k
break
}
delete(rc.cache, deletedKey)
purged++
}
}
func (rc *recordCache) flushOffsets(offsets []int64) {
rc.lock.Lock()
for _, offset := range offsets {
delete(rc.cache, offset)
}
rc.lock.Unlock()
}