-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
114 lines (87 loc) · 2.11 KB
/
main.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
package main
import (
"fmt"
"log"
"os"
)
var logr = log.New(os.Stderr, "ERROR:", 2)
type LRUCache struct {
head *CachedPair //leftmost item (last accessed item)
tail *CachedPair //rightmost item (least accesed item)
capacity int
cachedData map[string]*CachedPair
}
type CachedPair struct {
Key string
Value any
previous *CachedPair
next *CachedPair
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
capacity: capacity,
cachedData: make(map[string]*CachedPair),
}
}
func (c *LRUCache) Get(key string) (any, error) {
if c.head == nil {
return nil, fmt.Errorf(("can't retrieve data from empty cache"))
}
cachedPair, ok := c.cachedData[key]
if !ok {
return nil, fmt.Errorf("no value stored for the given key")
}
// last acessed item must be at the leftmost position (head)
c.setNewHead(c.cachedData[key])
//if a cached item exists for the given key, it's value is not nil
return cachedPair.Value, nil
}
func (c *LRUCache) setNewHead(newHead *CachedPair) {
if c.head.next == nil {
return
}
newHeadOldPrevious := newHead.previous
newHeadOldNext := newHead.next
newHeadOldPrevious.next = newHeadOldNext
if newHeadOldNext != nil {
newHeadOldNext.previous = newHeadOldPrevious
}
if newHead == c.tail {
c.tail = newHeadOldPrevious
}
newHead.next = c.head
newHead.previous = nil
c.head = newHead
}
func (c *LRUCache) Insert(key string, value any) error {
if c == nil {
return fmt.Errorf("non-initialized cache")
}
if value == nil {
return fmt.Errorf("cannot insert a nil value")
}
if c.head == nil {
c.head = &CachedPair{Key: key, Value: value, previous: nil, next: nil}
c.tail = c.head
c.cachedData[key] = c.head
return nil
}
if len(c.cachedData) == c.capacity {
delKey := c.tail.Key
c.tail = c.tail.previous
c.tail.next = nil
delete(c.cachedData, delKey)
}
oldTail := c.tail
c.tail = &CachedPair{Key: key, Value: value}
c.tail.previous = oldTail
c.tail.next = nil
oldTail.next = c.tail
return nil
}
func main() {
cache := NewLRUCache(3)
if err := cache.Insert("oi", nil); err != nil {
logr.Printf("%v", err)
}
}