-
Notifications
You must be signed in to change notification settings - Fork 1
/
lfu.go
78 lines (70 loc) · 1.87 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
package lfu
import (
"errors"
"fmt"
"sync"
)
// Cache used to call core cache methods off of
type Cache struct {
sync.RWMutex
frequencies map[interface{}]*lfuItem
head *freqNode
}
// NewLFU initializes a new LFU cache and returns it
func NewLFU() *Cache {
return &Cache{
frequencies: make(map[interface{}]*lfuItem),
head: newFreqNode(),
}
}
// Insert takes a key and a value to insert into the cache
// Returns a boolean for successful insert and an error if failed
func (c *Cache) Insert(key interface{}, value interface{}) (bool, error) {
c.Lock()
defer c.Unlock()
_, found := c.frequencies[key]
if found {
return false, errors.New("Key already exists in cache")
}
freq := c.head.next
if freq.value != 1 {
freq = getNewNode(1, c.head, freq)
}
freq.items.Add(key)
c.frequencies[key] = newlfuItem(value, freq)
return true, nil
}
// Get takes a key for an item in the cache to look up
// Returns the data associated with that key and an
func (c *Cache) Get(key interface{}) (interface{}, error) {
c.RLock()
defer c.RUnlock()
item, existing := c.frequencies[key]
if !existing {
return nil, fmt.Errorf("Key: %+v not found in cache", key)
}
freq := item.parent
nextFreq := freq.next
if nextFreq == c.head || nextFreq.value != freq.value+1 {
nextFreq = getNewNode(freq.value+1, freq, nextFreq)
}
nextFreq.items.Add(key)
item.parent = nextFreq
freq.items.Remove(key)
if freq.items.Cardinality() == 0 {
freq.remove()
}
return item.data, nil
}
// GetLFUItem returns the key and data of the least
// frequently updated item in the cache or -1 and nil for not found
func (c *Cache) GetLFUItem() (value interface{}, data interface{}) {
c.RLock()
defer c.RUnlock()
if len(c.frequencies) == 0 {
return -1, nil
}
// TODO: Try to avoid ToSlice on all items
item := c.frequencies[c.head.next.items.ToSlice()[0]]
return item.parent.value, item.data
}