-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
lfu.go
152 lines (126 loc) · 3.04 KB
/
lfu.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
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package eviction
// Least Frequently Used (LFU) eviction algorithm implementation
import (
"container/heap"
"sync"
"github.com/hyp3rd/hypercache/errors"
)
// LFUAlgorithm is an eviction algorithm that uses the Least Frequently Used (LFU) policy to select items for eviction.
type LFUAlgorithm struct {
items map[string]*Node
freqs *FrequencyHeap
mutex sync.RWMutex
length int
cap int
}
// Node is a node in the LFUAlgorithm.
type Node struct {
key string
value any
count int
index int
}
// FrequencyHeap is a heap of Nodes.
type FrequencyHeap []*Node
// Len returns the length of the heap.
func (fh FrequencyHeap) Len() int { return len(fh) }
// Less returns true if the node at index i has a lower frequency than the node at index j.
func (fh FrequencyHeap) Less(i, j int) bool {
if fh[i].count == fh[j].count {
return fh[i].index < fh[j].index
}
return fh[i].count < fh[j].count
}
// Swap swaps the nodes at index i and j.
func (fh FrequencyHeap) Swap(i, j int) {
fh[i], fh[j] = fh[j], fh[i]
fh[i].index = i
fh[j].index = j
}
// Push adds a node to the heap.
func (fh *FrequencyHeap) Push(x interface{}) {
n := len(*fh)
node := x.(*Node)
node.index = n
*fh = append(*fh, node)
}
// Pop removes the last node from the heap.
func (fh *FrequencyHeap) Pop() interface{} {
old := *fh
n := len(old)
node := old[n-1]
node.index = -1
*fh = old[0 : n-1]
return node
}
// NewLFUAlgorithm creates a new LFUAlgorithm with the given capacity.
func NewLFUAlgorithm(capacity int) (*LFUAlgorithm, error) {
if capacity < 0 {
return nil, errors.ErrInvalidCapacity
}
return &LFUAlgorithm{
items: make(map[string]*Node, capacity),
freqs: &FrequencyHeap{},
length: 0,
cap: capacity,
}, nil
}
// internalEvict evicts an item from the cache based on the LFU algorithm.
func (l *LFUAlgorithm) internalEvict() (string, bool) {
if l.length == 0 {
return "", false
}
node := heap.Pop(l.freqs).(*Node)
delete(l.items, node.key)
l.length--
return node.key, true
}
// Evict evicts an item from the cache based on the LFU algorithm.
func (l *LFUAlgorithm) Evict() (string, bool) {
l.mutex.Lock()
defer l.mutex.Unlock()
return l.internalEvict()
}
// Set sets a key-value pair in the cache.
func (l *LFUAlgorithm) Set(key string, value any) {
l.mutex.Lock()
defer l.mutex.Unlock()
if l.length == l.cap {
_, _ = l.internalEvict()
}
node := &Node{
key: key,
value: value,
count: 1,
}
l.items[key] = node
heap.Push(l.freqs, node)
l.length++
}
// Get gets a value from the cache.
func (l *LFUAlgorithm) Get(key string) (any, bool) {
l.mutex.Lock()
defer l.mutex.Unlock()
node, ok := l.items[key]
if !ok {
return nil, false
}
node.count++
heap.Fix(l.freqs, node.index)
return node.value, true
}
// Delete deletes a key-value pair from the cache.
func (l *LFUAlgorithm) Delete(key string) {
l.mutex.Lock()
defer l.mutex.Unlock()
node, ok := l.items[key]
if !ok {
return
}
heap.Remove(l.freqs, node.index)
for i := node.index; i < len(*l.freqs); i++ {
(*l.freqs)[i].index--
}
delete(l.items, key)
l.length--
}