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
|
package mru
import (
"container/list"
)
// Cache is used a MRU (Most recently used) cache replacement policy.
//
// In contrast to Least Recently Used (LRU), MRU discards the most recently used items first.
type Cache[K comparable, V any] struct {
cap int
list *list.List
items map[K]*list.Element
}
type entry[K comparable, V any] struct {
key K
val V
}
// Option is an option for MRU 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 MRU 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,
list: list.New(),
items: make(map[K]*list.Element, 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
}
// updates cache order
c.list.MoveToBack(e)
return e.Value.(*entry[K, V]).val, true
}
// Set sets a value to the cache with key. replacing any existing value.
func (c *Cache[K, V]) Set(key K, val V) {
if e, ok := c.items[key]; ok {
// updates cache order
c.list.MoveToBack(e)
entry := e.Value.(*entry[K, V])
entry.val = val
return
}
if c.list.Len() == c.cap {
c.deleteNewest()
}
newEntry := &entry[K, V]{
key: key,
val: val,
}
e := c.list.PushBack(newEntry)
c.items[key] = e
}
// Keys returns the keys of the cache. the order is from recently used.
func (c *Cache[K, V]) Keys() []K {
keys := make([]K, 0, len(c.items))
for ent := c.list.Back(); ent != nil; ent = ent.Prev() {
entry := ent.Value.(*entry[K, V])
keys = append(keys, entry.key)
}
return keys
}
// Len returns the number of items in the cache.
func (c *Cache[K, V]) Len() int {
return c.list.Len()
}
// 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 {
c.delete(e)
}
}
func (c *Cache[K, V]) deleteNewest() {
e := c.list.Front()
c.delete(e)
}
func (c *Cache[K, V]) delete(e *list.Element) {
c.list.Remove(e)
entry := e.Value.(*entry[K, V])
delete(c.items, entry.key)
}
|
