aboutsummaryrefslogtreecommitdiffstats
path: root/evict.go
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
}