diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/hashicorp/golang-lru')
5 files changed, 672 insertions, 231 deletions
diff --git a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/2q.go b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/2q.go new file mode 100644 index 000000000..337d96329 --- /dev/null +++ b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/2q.go @@ -0,0 +1,212 @@ +package lru + +import ( + "fmt" + "sync" + + "github.com/hashicorp/golang-lru/simplelru" +) + +const ( + // Default2QRecentRatio is the ratio of the 2Q cache dedicated + // to recently added entries that have only been accessed once. + Default2QRecentRatio = 0.25 + + // Default2QGhostEntries is the default ratio of ghost + // entries kept to track entries recently evicted + Default2QGhostEntries = 0.50 +) + +// TwoQueueCache is a thread-safe fixed size 2Q cache. +// 2Q is an enhancement over the standard LRU cache +// in that it tracks both frequently and recently used +// entries separately. This avoids a burst in access to new +// entries from evicting frequently used entries. It adds some +// additional tracking overhead to the standard LRU cache, and is +// computationally about 2x the cost, and adds some metadata over +// head. The ARCCache is similar, but does not require setting any +// parameters. +type TwoQueueCache struct { + size int + recentSize int + + recent *simplelru.LRU + frequent *simplelru.LRU + recentEvict *simplelru.LRU + lock sync.RWMutex +} + +// New2Q creates a new TwoQueueCache using the default +// values for the parameters. +func New2Q(size int) (*TwoQueueCache, error) { + return New2QParams(size, Default2QRecentRatio, Default2QGhostEntries) +} + +// New2QParams creates a new TwoQueueCache using the provided +// parameter values. +func New2QParams(size int, recentRatio float64, ghostRatio float64) (*TwoQueueCache, error) { + if size <= 0 { + return nil, fmt.Errorf("invalid size") + } + if recentRatio < 0.0 || recentRatio > 1.0 { + return nil, fmt.Errorf("invalid recent ratio") + } + if ghostRatio < 0.0 || ghostRatio > 1.0 { + return nil, fmt.Errorf("invalid ghost ratio") + } + + // Determine the sub-sizes + recentSize := int(float64(size) * recentRatio) + evictSize := int(float64(size) * ghostRatio) + + // Allocate the LRUs + recent, err := simplelru.NewLRU(size, nil) + if err != nil { + return nil, err + } + frequent, err := simplelru.NewLRU(size, nil) + if err != nil { + return nil, err + } + recentEvict, err := simplelru.NewLRU(evictSize, nil) + if err != nil { + return nil, err + } + + // Initialize the cache + c := &TwoQueueCache{ + size: size, + recentSize: recentSize, + recent: recent, + frequent: frequent, + recentEvict: recentEvict, + } + return c, nil +} + +func (c *TwoQueueCache) Get(key interface{}) (interface{}, bool) { + c.lock.Lock() + defer c.lock.Unlock() + + // Check if this is a frequent value + if val, ok := c.frequent.Get(key); ok { + return val, ok + } + + // If the value is contained in recent, then we + // promote it to frequent + if val, ok := c.recent.Peek(key); ok { + c.recent.Remove(key) + c.frequent.Add(key, val) + return val, ok + } + + // No hit + return nil, false +} + +func (c *TwoQueueCache) Add(key, value interface{}) { + c.lock.Lock() + defer c.lock.Unlock() + + // Check if the value is frequently used already, + // and just update the value + if c.frequent.Contains(key) { + c.frequent.Add(key, value) + return + } + + // Check if the value is recently used, and promote + // the value into the frequent list + if c.recent.Contains(key) { + c.recent.Remove(key) + c.frequent.Add(key, value) + return + } + + // If the value was recently evicted, add it to the + // frequently used list + if c.recentEvict.Contains(key) { + c.ensureSpace(true) + c.recentEvict.Remove(key) + c.frequent.Add(key, value) + return + } + + // Add to the recently seen list + c.ensureSpace(false) + c.recent.Add(key, value) + return +} + +// ensureSpace is used to ensure we have space in the cache +func (c *TwoQueueCache) ensureSpace(recentEvict bool) { + // If we have space, nothing to do + recentLen := c.recent.Len() + freqLen := c.frequent.Len() + if recentLen+freqLen < c.size { + return + } + + // If the recent buffer is larger than + // the target, evict from there + if recentLen > 0 && (recentLen > c.recentSize || (recentLen == c.recentSize && !recentEvict)) { + k, _, _ := c.recent.RemoveOldest() + c.recentEvict.Add(k, nil) + return + } + + // Remove from the frequent list otherwise + c.frequent.RemoveOldest() +} + +func (c *TwoQueueCache) Len() int { + c.lock.RLock() + defer c.lock.RUnlock() + return c.recent.Len() + c.frequent.Len() +} + +func (c *TwoQueueCache) Keys() []interface{} { + c.lock.RLock() + defer c.lock.RUnlock() + k1 := c.frequent.Keys() + k2 := c.recent.Keys() + return append(k1, k2...) +} + +func (c *TwoQueueCache) Remove(key interface{}) { + c.lock.Lock() + defer c.lock.Unlock() + if c.frequent.Remove(key) { + return + } + if c.recent.Remove(key) { + return + } + if c.recentEvict.Remove(key) { + return + } +} + +func (c *TwoQueueCache) Purge() { + c.lock.Lock() + defer c.lock.Unlock() + c.recent.Purge() + c.frequent.Purge() + c.recentEvict.Purge() +} + +func (c *TwoQueueCache) Contains(key interface{}) bool { + c.lock.RLock() + defer c.lock.RUnlock() + return c.frequent.Contains(key) || c.recent.Contains(key) +} + +func (c *TwoQueueCache) Peek(key interface{}) (interface{}, bool) { + c.lock.RLock() + defer c.lock.RUnlock() + if val, ok := c.frequent.Peek(key); ok { + return val, ok + } + return c.recent.Peek(key) +} diff --git a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/arc.go b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/arc.go new file mode 100644 index 000000000..a2a252817 --- /dev/null +++ b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/arc.go @@ -0,0 +1,257 @@ +package lru + +import ( + "sync" + + "github.com/hashicorp/golang-lru/simplelru" +) + +// ARCCache is a thread-safe fixed size Adaptive Replacement Cache (ARC). +// ARC is an enhancement over the standard LRU cache in that tracks both +// frequency and recency of use. This avoids a burst in access to new +// entries from evicting the frequently used older entries. It adds some +// additional tracking overhead to a standard LRU cache, computationally +// it is roughly 2x the cost, and the extra memory overhead is linear +// with the size of the cache. ARC has been patented by IBM, but is +// similar to the TwoQueueCache (2Q) which requires setting parameters. +type ARCCache struct { + size int // Size is the total capacity of the cache + p int // P is the dynamic preference towards T1 or T2 + + t1 *simplelru.LRU // T1 is the LRU for recently accessed items + b1 *simplelru.LRU // B1 is the LRU for evictions from t1 + + t2 *simplelru.LRU // T2 is the LRU for frequently accessed items + b2 *simplelru.LRU // B2 is the LRU for evictions from t2 + + lock sync.RWMutex +} + +// NewARC creates an ARC of the given size +func NewARC(size int) (*ARCCache, error) { + // Create the sub LRUs + b1, err := simplelru.NewLRU(size, nil) + if err != nil { + return nil, err + } + b2, err := simplelru.NewLRU(size, nil) + if err != nil { + return nil, err + } + t1, err := simplelru.NewLRU(size, nil) + if err != nil { + return nil, err + } + t2, err := simplelru.NewLRU(size, nil) + if err != nil { + return nil, err + } + + // Initialize the ARC + c := &ARCCache{ + size: size, + p: 0, + t1: t1, + b1: b1, + t2: t2, + b2: b2, + } + return c, nil +} + +// Get looks up a key's value from the cache. +func (c *ARCCache) Get(key interface{}) (interface{}, bool) { + c.lock.Lock() + defer c.lock.Unlock() + + // Ff the value is contained in T1 (recent), then + // promote it to T2 (frequent) + if val, ok := c.t1.Peek(key); ok { + c.t1.Remove(key) + c.t2.Add(key, val) + return val, ok + } + + // Check if the value is contained in T2 (frequent) + if val, ok := c.t2.Get(key); ok { + return val, ok + } + + // No hit + return nil, false +} + +// Add adds a value to the cache. +func (c *ARCCache) Add(key, value interface{}) { + c.lock.Lock() + defer c.lock.Unlock() + + // Check if the value is contained in T1 (recent), and potentially + // promote it to frequent T2 + if c.t1.Contains(key) { + c.t1.Remove(key) + c.t2.Add(key, value) + return + } + + // Check if the value is already in T2 (frequent) and update it + if c.t2.Contains(key) { + c.t2.Add(key, value) + return + } + + // Check if this value was recently evicted as part of the + // recently used list + if c.b1.Contains(key) { + // T1 set is too small, increase P appropriately + delta := 1 + b1Len := c.b1.Len() + b2Len := c.b2.Len() + if b2Len > b1Len { + delta = b2Len / b1Len + } + if c.p+delta >= c.size { + c.p = c.size + } else { + c.p += delta + } + + // Potentially need to make room in the cache + if c.t1.Len()+c.t2.Len() >= c.size { + c.replace(false) + } + + // Remove from B1 + c.b1.Remove(key) + + // Add the key to the frequently used list + c.t2.Add(key, value) + return + } + + // Check if this value was recently evicted as part of the + // frequently used list + if c.b2.Contains(key) { + // T2 set is too small, decrease P appropriately + delta := 1 + b1Len := c.b1.Len() + b2Len := c.b2.Len() + if b1Len > b2Len { + delta = b1Len / b2Len + } + if delta >= c.p { + c.p = 0 + } else { + c.p -= delta + } + + // Potentially need to make room in the cache + if c.t1.Len()+c.t2.Len() >= c.size { + c.replace(true) + } + + // Remove from B2 + c.b2.Remove(key) + + // Add the key to the frequntly used list + c.t2.Add(key, value) + return + } + + // Potentially need to make room in the cache + if c.t1.Len()+c.t2.Len() >= c.size { + c.replace(false) + } + + // Keep the size of the ghost buffers trim + if c.b1.Len() > c.size-c.p { + c.b1.RemoveOldest() + } + if c.b2.Len() > c.p { + c.b2.RemoveOldest() + } + + // Add to the recently seen list + c.t1.Add(key, value) + return +} + +// replace is used to adaptively evict from either T1 or T2 +// based on the current learned value of P +func (c *ARCCache) replace(b2ContainsKey bool) { + t1Len := c.t1.Len() + if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) { + k, _, ok := c.t1.RemoveOldest() + if ok { + c.b1.Add(k, nil) + } + } else { + k, _, ok := c.t2.RemoveOldest() + if ok { + c.b2.Add(k, nil) + } + } +} + +// Len returns the number of cached entries +func (c *ARCCache) Len() int { + c.lock.RLock() + defer c.lock.RUnlock() + return c.t1.Len() + c.t2.Len() +} + +// Keys returns all the cached keys +func (c *ARCCache) Keys() []interface{} { + c.lock.RLock() + defer c.lock.RUnlock() + k1 := c.t1.Keys() + k2 := c.t2.Keys() + return append(k1, k2...) +} + +// Remove is used to purge a key from the cache +func (c *ARCCache) Remove(key interface{}) { + c.lock.Lock() + defer c.lock.Unlock() + if c.t1.Remove(key) { + return + } + if c.t2.Remove(key) { + return + } + if c.b1.Remove(key) { + return + } + if c.b2.Remove(key) { + return + } +} + +// Purge is used to clear the cache +func (c *ARCCache) Purge() { + c.lock.Lock() + defer c.lock.Unlock() + c.t1.Purge() + c.t2.Purge() + c.b1.Purge() + c.b2.Purge() +} + +// Contains is used to check if the cache contains a key +// without updating recency or frequency. +func (c *ARCCache) Contains(key interface{}) bool { + c.lock.RLock() + defer c.lock.RUnlock() + return c.t1.Contains(key) || c.t2.Contains(key) +} + +// Peek is used to inspect the cache value of a key +// without updating recency or frequency. +func (c *ARCCache) Peek(key interface{}) (interface{}, bool) { + c.lock.RLock() + defer c.lock.RUnlock() + if val, ok := c.t1.Peek(key); ok { + return val, ok + } + return c.t2.Peek(key) +} diff --git a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go index 5f1e8a1af..a6285f989 100644 --- a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go +++ b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru.go @@ -4,24 +4,15 @@ package lru import ( - "container/list" - "errors" "sync" + + "github.com/hashicorp/golang-lru/simplelru" ) // 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{} + lru *simplelru.LRU + lock sync.RWMutex } // New creates an LRU of the given size @@ -29,15 +20,15 @@ func New(size int) (*Cache, error) { return NewWithEvict(size, nil) } +// NewWithEvict constructs a fixed size cache with the given eviction +// callback. func NewWithEvict(size int, onEvicted func(key interface{}, value interface{})) (*Cache, error) { - if size <= 0 { - return nil, errors.New("Must provide a positive size") + lru, err := simplelru.NewLRU(size, simplelru.EvictCallback(onEvicted)) + if err != nil { + return nil, err } c := &Cache{ - size: size, - evictList: list.New(), - items: make(map[interface{}]*list.Element, size), - onEvicted: onEvicted, + lru: lru, } return c, nil } @@ -45,131 +36,79 @@ func NewWithEvict(size int, onEvicted func(key interface{}, value interface{})) // 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) + c.lru.Purge() + c.lock.Unlock() } -// Add adds a value to the cache. Returns true if an eviction occured. +// Add adds a value to the cache. Returns true if an eviction occurred. 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 + return c.lru.Add(key, value) } // Get looks up a key's value from the cache. -func (c *Cache) Get(key interface{}) (value interface{}, ok bool) { +func (c *Cache) Get(key interface{}) (interface{}, 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 + return c.lru.Get(key) } -// 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) { +// 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{}) bool { c.lock.RLock() defer c.lock.RUnlock() - - _, ok = c.items[key] - return ok + return c.lru.Contains(key) } -// 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) { +// Returns the key value (or undefined if not found) without updating +// the "recently used"-ness of the key. +func (c *Cache) Peek(key interface{}) (interface{}, bool) { c.lock.RLock() defer c.lock.RUnlock() + return c.lru.Peek(key) +} - if ent, ok := c.items[key]; ok { - return ent.Value.(*entry).value, true +// ContainsOrAdd checks if a key is in the cache without updating the +// recent-ness or deleting it for being stale, and if not, adds the value. +// Returns whether found and whether an eviction occurred. +func (c *Cache) ContainsOrAdd(key, value interface{}) (ok, evict bool) { + c.lock.Lock() + defer c.lock.Unlock() + + if c.lru.Contains(key) { + return true, false + } else { + evict := c.lru.Add(key, value) + return false, evict } - 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) - } + c.lru.Remove(key) + c.lock.Unlock() } // RemoveOldest removes the oldest item from the cache. func (c *Cache) RemoveOldest() { c.lock.Lock() - defer c.lock.Unlock() - c.removeOldest() + c.lru.RemoveOldest() + c.lock.Unlock() } // 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 + return c.lru.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) - } + return c.lru.Len() } diff --git a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru_test.go b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru_test.go deleted file mode 100644 index b676cfd9d..000000000 --- a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/lru_test.go +++ /dev/null @@ -1,127 +0,0 @@ -package lru - -import "testing" - -func TestLRU(t *testing.T) { - evictCounter := 0 - onEvicted := func(k interface{}, v interface{}) { - if k != v { - t.Fatalf("Evict values not equal (%v!=%v)", k, v) - } - evictCounter += 1 - } - l, err := NewWithEvict(128, onEvicted) - if err != nil { - t.Fatalf("err: %v", err) - } - - for i := 0; i < 256; i++ { - l.Add(i, i) - } - if l.Len() != 128 { - t.Fatalf("bad len: %v", l.Len()) - } - - if evictCounter != 128 { - t.Fatalf("bad evict count: %v", evictCounter) - } - - for i, k := range l.Keys() { - if v, ok := l.Get(k); !ok || v != k || v != i+128 { - t.Fatalf("bad key: %v", k) - } - } - for i := 0; i < 128; i++ { - _, ok := l.Get(i) - if ok { - t.Fatalf("should be evicted") - } - } - for i := 128; i < 256; i++ { - _, ok := l.Get(i) - if !ok { - t.Fatalf("should not be evicted") - } - } - for i := 128; i < 192; i++ { - l.Remove(i) - _, ok := l.Get(i) - if ok { - t.Fatalf("should be deleted") - } - } - - l.Get(192) // expect 192 to be last key in l.Keys() - - for i, k := range l.Keys() { - if (i < 63 && k != i+193) || (i == 63 && k != 192) { - t.Fatalf("out of order key: %v", k) - } - } - - l.Purge() - if l.Len() != 0 { - t.Fatalf("bad len: %v", l.Len()) - } - if _, ok := l.Get(200); ok { - t.Fatalf("should contain nothing") - } -} - -// test that Add returns true/false if an eviction occured -func TestLRUAdd(t *testing.T) { - evictCounter := 0 - onEvicted := func(k interface{}, v interface{}) { - evictCounter += 1 - } - - l, err := NewWithEvict(1, onEvicted) - if err != nil { - t.Fatalf("err: %v", err) - } - - if l.Add(1, 1) == true || evictCounter != 0 { - t.Errorf("should not have an eviction") - } - if l.Add(2, 2) == false || evictCounter != 1 { - t.Errorf("should have an eviction") - } -} - -// test that Contains doesn't update recent-ness -func TestLRUContains(t *testing.T) { - l, err := New(2) - if err != nil { - t.Fatalf("err: %v", err) - } - - l.Add(1, 1) - l.Add(2, 2) - if !l.Contains(1) { - t.Errorf("1 should be contained") - } - - l.Add(3, 3) - if l.Contains(1) { - t.Errorf("Contains should not have updated recent-ness of 1") - } -} - -// test that Peek doesn't update recent-ness -func TestLRUPeek(t *testing.T) { - l, err := New(2) - if err != nil { - t.Fatalf("err: %v", err) - } - - l.Add(1, 1) - l.Add(2, 2) - if v, ok := l.Peek(1); !ok || v != 1 { - t.Errorf("1 should be set to 1: %v, %v", v, ok) - } - - l.Add(3, 3) - if l.Contains(1) { - t.Errorf("should not have updated recent-ness of 1") - } -} diff --git a/Godeps/_workspace/src/github.com/hashicorp/golang-lru/simplelru/lru.go b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/simplelru/lru.go new file mode 100644 index 000000000..68d097a1c --- /dev/null +++ b/Godeps/_workspace/src/github.com/hashicorp/golang-lru/simplelru/lru.go @@ -0,0 +1,160 @@ +package simplelru + +import ( + "container/list" + "errors" +) + +// EvictCallback is used to get a callback when a cache entry is evicted +type EvictCallback func(key interface{}, value interface{}) + +// LRU implements a non-thread safe fixed size LRU cache +type LRU struct { + size int + evictList *list.List + items map[interface{}]*list.Element + onEvict EvictCallback +} + +// entry is used to hold a value in the evictList +type entry struct { + key interface{} + value interface{} +} + +// NewLRU constructs an LRU of the given size +func NewLRU(size int, onEvict EvictCallback) (*LRU, error) { + if size <= 0 { + return nil, errors.New("Must provide a positive size") + } + c := &LRU{ + size: size, + evictList: list.New(), + items: make(map[interface{}]*list.Element), + onEvict: onEvict, + } + return c, nil +} + +// Purge is used to completely clear the cache +func (c *LRU) Purge() { + for k, v := range c.items { + if c.onEvict != nil { + c.onEvict(k, v.Value.(*entry).value) + } + delete(c.items, k) + } + c.evictList.Init() +} + +// Add adds a value to the cache. Returns true if an eviction occured. +func (c *LRU) Add(key, value interface{}) bool { + // 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 *LRU) Get(key interface{}) (value interface{}, ok bool) { + 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 *LRU) Contains(key interface{}) (ok bool) { + _, ok = c.items[key] + return ok +} + +// Returns the key value (or undefined if not found) without updating +// the "recently used"-ness of the key. +func (c *LRU) Peek(key interface{}) (value interface{}, ok bool) { + if ent, ok := c.items[key]; ok { + return ent.Value.(*entry).value, true + } + return nil, ok +} + +// Remove removes the provided key from the cache, returning if the +// key was contained. +func (c *LRU) Remove(key interface{}) bool { + if ent, ok := c.items[key]; ok { + c.removeElement(ent) + return true + } + return false +} + +// RemoveOldest removes the oldest item from the cache. +func (c *LRU) RemoveOldest() (interface{}, interface{}, bool) { + ent := c.evictList.Back() + if ent != nil { + c.removeElement(ent) + kv := ent.Value.(*entry) + return kv.key, kv.value, true + } + return nil, nil, false +} + +// GetOldest returns the oldest entry +func (c *LRU) GetOldest() (interface{}, interface{}, bool) { + ent := c.evictList.Back() + if ent != nil { + kv := ent.Value.(*entry) + return kv.key, kv.value, true + } + return nil, nil, false +} + +// Keys returns a slice of the keys in the cache, from oldest to newest. +func (c *LRU) Keys() []interface{} { + keys := make([]interface{}, len(c.items)) + i := 0 + for ent := c.evictList.Back(); ent != nil; ent = ent.Prev() { + keys[i] = ent.Value.(*entry).key + i++ + } + return keys +} + +// Len returns the number of items in the cache. +func (c *LRU) Len() int { + return c.evictList.Len() +} + +// removeOldest removes the oldest item from the cache. +func (c *LRU) 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 *LRU) removeElement(e *list.Element) { + c.evictList.Remove(e) + kv := e.Value.(*entry) + delete(c.items, kv.key) + if c.onEvict != nil { + c.onEvict(kv.key, kv.value) + } +} |