vendor/github.com/hashicorp/golang-lru/simplelru/lru.go

   1 package simplelru
   2
   3 import (
   4         "container/list"
   5         "errors"
   6 )
   7
   8 // EvictCallback is used to get a callback when a cache entry is evicted
   9 type EvictCallback func(key interface{}, value interface{})
  10
  11 // LRU implements a non-thread safe fixed size LRU cache
  12 type 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
  20 type entry struct {
  21         key   interface{}
  22         value interface{}
  23 }
  24
  25 // NewLRU constructs an LRU of the given size
  26 func 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.
  40 func (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.
  51 func (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.
  73 func (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.
  83 func (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.
  90 func (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.
 100 func (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.
 109 func (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
 120 func (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.
 130 func (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.
 141 func (c *LRU) Len() int {
 142         return c.evictList.Len()
 143 }
 144
 145 // removeOldest removes the oldest item from the cache.
 146 func (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
 154 func (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 }