blob: 987aa04a95413cc678e64c31f4e07a4704fcef4f (
plain) (
blame)
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
import "errors"
type EvictionPolicy int
const (
StrategyNone EvictionPolicy = iota
StrategyFIFO
StrategyLRU
StrategyLFU
)
type EvictionStrategies interface {
OnInsert(n *Node)
OnAccess(n *Node)
Evict() *Node
}
func (e EvictionPolicy) ToStratergy(evict *Node) (EvictionStrategies, error) {
store := map[EvictionPolicy]func() EvictionStrategies{
StrategyNone: func() EvictionStrategies {
return NoneStrategies{evict: evict}
},
StrategyFIFO: func() EvictionStrategies {
return FIFOStrategies{evict: evict}
},
StrategyLRU: func() EvictionStrategies {
return LRUStrategies{evict: evict}
},
}
factory, ok := store[e]
if !ok {
return nil, errors.New("Invalid Policy")
}
return factory(), nil
}
type NoneStrategies struct {
evict *Node
}
func (s NoneStrategies) OnInsert(node *Node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
func (NoneStrategies) OnAccess(n *Node) {
}
func (NoneStrategies) Evict() *Node {
return nil
}
type FIFOStrategies struct {
evict *Node
}
func (s FIFOStrategies) OnInsert(node *Node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
func (FIFOStrategies) OnAccess(n *Node) {
}
func (s FIFOStrategies) Evict() *Node {
return s.evict.EvictPrev
}
type LRUStrategies struct {
evict *Node
}
func (s LRUStrategies) OnInsert(node *Node) {
}
func (s LRUStrategies) OnAccess(node *Node) {
node.EvictNext.EvictPrev = node.EvictPrev
node.EvictPrev.EvictNext = node.EvictNext
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
func (s LRUStrategies) Evict() *Node {
return s.evict.EvictPrev
}
type LFUStrategies struct {
evict *Node
}
func (s LFUStrategies) OnInsert(node *Node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
func (s LFUStrategies) OnAccess(node *Node) {
node.Access += 1
node.EvictNext.EvictPrev = node.EvictPrev
node.EvictPrev.EvictNext = node.EvictNext
for v := node.EvictPrev; v != s.evict; v = v.EvictPrev {
if v.Access >= node.Access {
node.EvictPrev = v
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
break
}
}
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
func (s LFUStrategies) Evict() *Node {
return s.evict.EvictPrev
}
|
