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
|
package lfu
import (
"container/heap"
)
// Cache is used a LFU (Least-frequently used) cache replacement policy.
//
// Counts how often an item is needed. Those that are used least often are discarded first.
// This works very similar to LRU except that instead of storing the value of how recently
// a block was accessed, we store the value of how many times it was accessed. So of course
// while running an access sequence we will replace a block which was used fewest times from our cache.
type Cache[K comparable, V any] struct {
cap int
queue *priorityQueue[K, V]
items map[K]*entry[K, V]
}
// Option is an option for LFU cache.
type Option func(*options)
type options struct {
capacity int
}
func newOptions() *options {
return &options{
capacity: 128,
}
}
// WithCapacity is an option to set cache capacity.
func WithCapacity(cap int) Option {
return func(o *options) {
o.capacity = cap
}
}
// NewCache creates a new non-thread safe LFU cache whose capacity is the default size (128).
func NewCache[K comparable, V any](opts ...Option) *Cache[K, V] {
o := newOptions()
for _, optFunc := range opts {
optFunc(o)
}
return &Cache[K, V]{
cap: o.capacity,
queue: newPriorityQueue[K, V](o.capacity),
items: make(map[K]*entry[K, V], o.capacity),
}
}
// Get looks up a key's value from the cache.
func (c *Cache[K, V]) Get(key K) (zero V, _ bool) {
e, ok := c.items[key]
if !ok {
return
}
e.referenced()
heap.Fix(c.queue, e.index)
return e.val, true
}
// Set sets a value to the cache with key. replacing any existing value.
//
// If value satisfies "interface{ GetReferenceCount() int }", the value of
// the GetReferenceCount() method is used to set the initial value of reference count.
func (c *Cache[K, V]) Set(key K, val V) {
if e, ok := c.items[key]; ok {
c.queue.update(e, val)
return
}
if len(c.items) == c.cap {
evictedEntry := heap.Pop(c.queue)
if evictedEntry != nil {
delete(c.items, evictedEntry.(*entry[K, V]).key)
}
}
e := newEntry(key, val)
heap.Push(c.queue, e)
c.items[key] = e
}
// Keys returns the keys of the cache. the order is from oldest to newest.
func (c *Cache[K, V]) Keys() []K {
keys := make([]K, 0, len(c.items))
for _, entry := range *c.queue {
keys = append(keys, entry.key)
}
return keys
}
// Delete deletes the item with provided key from the cache.
func (c *Cache[K, V]) Delete(key K) {
if e, ok := c.items[key]; ok {
heap.Remove(c.queue, e.index)
delete(c.items, key)
}
}
// Len returns the number of items in the cache.
func (c *Cache[K, V]) Len() int {
return c.queue.Len()
}
|
