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