diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go')
-rw-r--r-- | Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go new file mode 100644 index 000000000..5f1e8a1af --- /dev/null +++ b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go @@ -0,0 +1,175 @@ +// This package provides a simple LRU cache. It is based on the +// LRU implementation in groupcache: +// https://github.com/golang/groupcache/tree/master/lru +package lru + +import ( + "container/list" + "errors" + "sync" +) + +// Cache is a thread-safe fixed size LRU cache. +type Cache struct { + size int + evictList *list.List + items map[interface{}]*list.Element + lock sync.RWMutex + onEvicted func(key interface{}, value interface{}) +} + +// entry is used to hold a value in the evictList +type entry struct { + key interface{} + value interface{} +} + +// New creates an LRU of the given size +func New(size int) (*Cache, error) { + return NewWithEvict(size, nil) +} + +func NewWithEvict(size int, onEvicted func(key interface{}, value interface{})) (*Cache, error) { + if size <= 0 { + return nil, errors.New("Must provide a positive size") + } + c := &Cache{ + size: size, + evictList: list.New(), + items: make(map[interface{}]*list.Element, size), + onEvicted: onEvicted, + } + return c, nil +} + +// Purge is used to completely clear the cache +func (c *Cache) Purge() { + c.lock.Lock() + defer c.lock.Unlock() + + if c.onEvicted != nil { + for k, v := range c.items { + c.onEvicted(k, v.Value.(*entry).value) + } + } + + c.evictList = list.New() + c.items = make(map[interface{}]*list.Element, c.size) +} + +// Add adds a value to the cache. Returns true if an eviction occured. +func (c *Cache) Add(key, value interface{}) bool { + c.lock.Lock() + defer c.lock.Unlock() + + // Check for existing item + if ent, ok := c.items[key]; ok { + c.evictList.MoveToFront(ent) + ent.Value.(*entry).value = value + return false + } + + // Add new item + ent := &entry{key, value} + entry := c.evictList.PushFront(ent) + c.items[key] = entry + + evict := c.evictList.Len() > c.size + // Verify size not exceeded + if evict { + c.removeOldest() + } + return evict +} + +// Get looks up a key's value from the cache. +func (c *Cache) Get(key interface{}) (value interface{}, ok bool) { + c.lock.Lock() + defer c.lock.Unlock() + + if ent, ok := c.items[key]; ok { + c.evictList.MoveToFront(ent) + return ent.Value.(*entry).value, true + } + return +} + +// Check if a key is in the cache, without updating the recent-ness or deleting it for being stale. +func (c *Cache) Contains(key interface{}) (ok bool) { + c.lock.RLock() + defer c.lock.RUnlock() + + _, ok = c.items[key] + return ok +} + +// Returns the key value (or undefined if not found) without updating the "recently used"-ness of the key. +// (If you find yourself using this a lot, you might be using the wrong sort of data structure, but there are some use cases where it's handy.) +func (c *Cache) Peek(key interface{}) (value interface{}, ok bool) { + c.lock.RLock() + defer c.lock.RUnlock() + + if ent, ok := c.items[key]; ok { + return ent.Value.(*entry).value, true + } + return nil, ok +} + +// Remove removes the provided key from the cache. +func (c *Cache) Remove(key interface{}) { + c.lock.Lock() + defer c.lock.Unlock() + + if ent, ok := c.items[key]; ok { + c.removeElement(ent) + } +} + +// RemoveOldest removes the oldest item from the cache. +func (c *Cache) RemoveOldest() { + c.lock.Lock() + defer c.lock.Unlock() + c.removeOldest() +} + +// Keys returns a slice of the keys in the cache, from oldest to newest. +func (c *Cache) Keys() []interface{} { + c.lock.RLock() + defer c.lock.RUnlock() + + keys := make([]interface{}, len(c.items)) + ent := c.evictList.Back() + i := 0 + for ent != nil { + keys[i] = ent.Value.(*entry).key + ent = ent.Prev() + i++ + } + + return keys +} + +// Len returns the number of items in the cache. +func (c *Cache) Len() int { + c.lock.RLock() + defer c.lock.RUnlock() + return c.evictList.Len() +} + +// removeOldest removes the oldest item from the cache. +func (c *Cache) removeOldest() { + ent := c.evictList.Back() + if ent != nil { + c.removeElement(ent) + } +} + +// removeElement is used to remove a given list element from the cache +func (c *Cache) removeElement(e *list.Element) { + c.evictList.Remove(e) + kv := e.Value.(*entry) + delete(c.items, kv.key) + if c.onEvicted != nil { + c.onEvicted(kv.key, kv.value) + } +} |