blob: 5e753421e38f54959e23a3e201e3afca5c973a87 (
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
133
134
135
136
137
138
|
package cache
import "errors"
type EvictionPolicyType int
const (
StrategyNone EvictionPolicyType = iota
StrategyFIFO
StrategyLRU
StrategyLFU
)
type EvictionStrategies interface {
OnInsert(n *Node)
OnAccess(n *Node)
Evict() *Node
}
type EvictionPolicy struct {
EvictionStrategies
Type EvictionPolicyType
evict *Node
}
func (e *EvictionPolicy) SetPolicy(y EvictionPolicyType) error {
store := map[EvictionPolicyType]func() EvictionStrategies{
StrategyNone: func() EvictionStrategies {
return NoneStrategies{evict: e.evict}
},
StrategyFIFO: func() EvictionStrategies {
return FIFOStrategies{evict: e.evict}
},
StrategyLRU: func() EvictionStrategies {
return LRUStrategies{evict: e.evict}
},
}
factory, ok := store[y]
if !ok {
return errors.New("Invalid Policy")
}
e.EvictionStrategies = factory()
return 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
}
|
