1package simplelru
2
3import (
4 "container/list"
5 "errors"
6)
7
8// EvictCallback is used to get a callback when a cache entry is evicted
9type EvictCallback func(key interface{}, value interface{})
10
11// LRU implements a non-thread safe fixed size LRU cache
12type LRU struct {
13 size int
14 evictList *list.List
15 items map[interface{}]*list.Element
16 onEvict EvictCallback
17}
18
19// entry is used to hold a value in the evictList
20type entry struct {
21 key interface{}
22 value interface{}
23}
24
25// NewLRU constructs an LRU of the given size
26func NewLRU(size int, onEvict EvictCallback) (*LRU, error) {
27 if size <= 0 {
28 return nil, errors.New("Must provide a positive size")
29 }
30 c := &LRU{
31 size: size,
32 evictList: list.New(),
33 items: make(map[interface{}]*list.Element),
34 onEvict: onEvict,
35 }
36 return c, nil
37}
38
39// Purge is used to completely clear the cache.
40func (c *LRU) Purge() {
41 for k, v := range c.items {
42 if c.onEvict != nil {
43 c.onEvict(k, v.Value.(*entry).value)
44 }
45 delete(c.items, k)
46 }
47 c.evictList.Init()
48}
49
50// Add adds a value to the cache. Returns true if an eviction occurred.
51func (c *LRU) Add(key, value interface{}) (evicted bool) {
52 // Check for existing item
53 if ent, ok := c.items[key]; ok {
54 c.evictList.MoveToFront(ent)
55 ent.Value.(*entry).value = value
56 return false
57 }
58
59 // Add new item
60 ent := &entry{key, value}
61 entry := c.evictList.PushFront(ent)
62 c.items[key] = entry
63
64 evict := c.evictList.Len() > c.size
65 // Verify size not exceeded
66 if evict {
67 c.removeOldest()
68 }
69 return evict
70}
71
72// Get looks up a key's value from the cache.
73func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {
74 if ent, ok := c.items[key]; ok {
75 c.evictList.MoveToFront(ent)
76 return ent.Value.(*entry).value, true
77 }
78 return
79}
80
81// Contains checks if a key is in the cache, without updating the recent-ness
82// or deleting it for being stale.
83func (c *LRU) Contains(key interface{}) (ok bool) {
84 _, ok = c.items[key]
85 return ok
86}
87
88// Peek returns the key value (or undefined if not found) without updating
89// the "recently used"-ness of the key.
90func (c *LRU) Peek(key interface{}) (value interface{}, ok bool) {
91 var ent *list.Element
92 if ent, ok = c.items[key]; ok {
93 return ent.Value.(*entry).value, true
94 }
95 return nil, ok
96}
97
98// Remove removes the provided key from the cache, returning if the
99// key was contained.
100func (c *LRU) Remove(key interface{}) (present bool) {
101 if ent, ok := c.items[key]; ok {
102 c.removeElement(ent)
103 return true
104 }
105 return false
106}
107
108// RemoveOldest removes the oldest item from the cache.
109func (c *LRU) RemoveOldest() (key interface{}, value interface{}, ok bool) {
110 ent := c.evictList.Back()
111 if ent != nil {
112 c.removeElement(ent)
113 kv := ent.Value.(*entry)
114 return kv.key, kv.value, true
115 }
116 return nil, nil, false
117}
118
119// GetOldest returns the oldest entry
120func (c *LRU) GetOldest() (key interface{}, value interface{}, ok bool) {
121 ent := c.evictList.Back()
122 if ent != nil {
123 kv := ent.Value.(*entry)
124 return kv.key, kv.value, true
125 }
126 return nil, nil, false
127}
128
129// Keys returns a slice of the keys in the cache, from oldest to newest.
130func (c *LRU) Keys() []interface{} {
131 keys := make([]interface{}, len(c.items))
132 i := 0
133 for ent := c.evictList.Back(); ent != nil; ent = ent.Prev() {
134 keys[i] = ent.Value.(*entry).key
135 i++
136 }
137 return keys
138}
139
140// Len returns the number of items in the cache.
141func (c *LRU) Len() int {
142 return c.evictList.Len()
143}
144
145// removeOldest removes the oldest item from the cache.
146func (c *LRU) removeOldest() {
147 ent := c.evictList.Back()
148 if ent != nil {
149 c.removeElement(ent)
150 }
151}
152
153// removeElement is used to remove a given list element from the cache
154func (c *LRU) removeElement(e *list.Element) {
155 c.evictList.Remove(e)
156 kv := e.Value.(*entry)
157 delete(c.items, kv.key)
158 if c.onEvict != nil {
159 c.onEvict(kv.key, kv.value)
160 }
161}