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}
162