No public description PiperOrigin-RevId: 800942765 Change-Id: I77c58eafbf998eeafab1d3fd58b46d7294c5992a
diff --git a/2q.go b/2q.go index fa5780f..2ceae20 100644 --- a/2q.go +++ b/2q.go
@@ -44,7 +44,7 @@ // New2QParams creates a new TwoQueueCache using the provided // parameter values. -func New2QParams(size int, recentRatio float64, ghostRatio float64) (*TwoQueueCache, error) { +func New2QParams(size int, recentRatio, ghostRatio float64) (*TwoQueueCache, error) { if size <= 0 { return nil, fmt.Errorf("invalid size") } @@ -138,7 +138,6 @@ // 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
diff --git a/2q_test.go b/2q_test.go index 1b0f351..606384d 100644 --- a/2q_test.go +++ b/2q_test.go
@@ -1,7 +1,6 @@ package lru import ( - "math/rand" "testing" ) @@ -13,7 +12,7 @@ trace := make([]int64, b.N*2) for i := 0; i < b.N*2; i++ { - trace[i] = rand.Int63() % 32768 + trace[i] = getRand(b) % 32768 } b.ResetTimer() @@ -43,9 +42,9 @@ trace := make([]int64, b.N*2) for i := 0; i < b.N*2; i++ { if i%2 == 0 { - trace[i] = rand.Int63() % 16384 + trace[i] = getRand(b) % 16384 } else { - trace[i] = rand.Int63() % 32768 + trace[i] = getRand(b) % 32768 } } @@ -75,8 +74,8 @@ n := 200000 for i := 0; i < n; i++ { - key := rand.Int63() % 512 - r := rand.Int63() + key := getRand(t) % 512 + r := getRand(t) switch r % 3 { case 0: l.Add(key, key)
diff --git a/GOIMPORT/AUTOPATCHES/arc.go.patch b/GOIMPORT/AUTOPATCHES/arc.go.patch new file mode 100644 index 0000000..063079e --- /dev/null +++ b/GOIMPORT/AUTOPATCHES/arc.go.patch
@@ -0,0 +1,109 @@ +# This file reports differences detected by import.go since the last import. +# This is only for human review and not machine consumption. +# Please see go/thirdpartygo for more information. +# DO NOT EDIT. This must only be generated by //third_party/golang/import.go. + +@@ 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.LRUCache // T1 is the LRU for recently accessed items +- b1 simplelru.LRUCache // B1 is the LRU for evictions from t1 ++ t1 *simplelru.LRU // T1 is the LRU for recently accessed items ++ b1 *simplelru.LRU // B1 is the LRU for evictions from t1 + +- t2 simplelru.LRUCache // T2 is the LRU for frequently accessed items +- b2 simplelru.LRUCache // B2 is the LRU for evictions from t2 ++ 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) { ++ return NewARCWithEvict(size, nil) ++} ++ ++// NewARCWithEvict creates an ARC of the given size with onEvict callback. ++func NewARCWithEvict(size int, onEvicted func(key interface{}, value interface{})) (*ARCCache, error) { ++ callback := simplelru.EvictCallback(onEvicted) + // Create the sub LRUs + b1, err := simplelru.NewLRU(size, nil) + if err != nil { +@@ func NewARC(size int) (*ARCCache, error) { + if err != nil { + return nil, err + } +- t1, err := simplelru.NewLRU(size, nil) ++ t1, err := simplelru.NewLRU(size, callback) + if err != nil { + return nil, err + } +- t2, err := simplelru.NewLRU(size, nil) ++ t2, err := simplelru.NewLRU(size, callback) + if err != nil { + return nil, err + } +@@ func (c *ARCCache) Get(key interface{}) (value interface{}, ok bool) { + // If 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.t1.RemoveWithoutEvict(key) + c.t2.Add(key, val) + return val, ok + } +@@ func (c *ARCCache) Add(key, value interface{}) { + // 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.t1.RemoveWithoutEvict(key) + c.t2.Add(key, value) + return + } +@@ func (c *ARCCache) Keys() []interface{} { + return append(k1, k2...) + } + ++func (c *ARCCache) subcaches() [4]simplelru.LRUCache { ++ return [4]simplelru.LRUCache{c.t1, c.t2, c.b1, c.b2} ++} ++ + // 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 ++ for _, cache := range c.subcaches() { ++ if cache.Remove(key) { ++ return ++ } + } + } + +@@ func (c *ARCCache) Remove(key interface{}) { + func (c *ARCCache) Purge() { + c.lock.Lock() + defer c.lock.Unlock() +- c.t1.Purge() +- c.t2.Purge() +- c.b1.Purge() +- c.b2.Purge() ++ for _, cache := range c.subcaches() { ++ cache.Purge() ++ } + } + + // Contains is used to check if the cache contains a key
diff --git a/GOIMPORT/AUTOPATCHES/arc_test.go.patch b/GOIMPORT/AUTOPATCHES/arc_test.go.patch new file mode 100644 index 0000000..decf817 --- /dev/null +++ b/GOIMPORT/AUTOPATCHES/arc_test.go.patch
@@ -0,0 +1,81 @@ +# This file reports differences detected by import.go since the last import. +# This is only for human review and not machine consumption. +# Please see go/thirdpartygo for more information. +# DO NOT EDIT. This must only be generated by //third_party/golang/import.go. + +@@ import ( + "math/rand" + "testing" + "time" ++ ++ "google3/third_party/golang/cmp/cmp" + ) + + func init() { +@@ func TestARC_Peek(t *testing.T) { + t.Errorf("should not have updated recent-ness of 1") + } + } ++ ++func TestARC_OnEvictedCallback(t *testing.T) { ++ type testCase struct { ++ size int ++ data []int ++ evicted []int ++ } ++ ++ testCases := map[string]testCase{ ++ "basic-lru-like": { ++ size: 2, ++ data: []int{1, 2, 3, 4}, ++ evicted: []int{1, 2}, ++ }, ++ "t1-to-t2-promotion-simple": { ++ size: 4, ++ data: []int{1, 2, 1, 2, 3, 4, 5, 6}, ++ evicted: []int{3, 4}, ++ }, ++ "adaptive-replacement-simple": { ++ size: 4, ++ data: []int{1, 2, 3, 4, 5, 6, 1, 2, 7, 8}, ++ evicted: []int{1, 2, 3, 4, 1, 5}, ++ }, ++ "MFU-not-evicted-by-new-entries": { ++ size: 4, ++ data: []int{4, 4, 1, 2, 3, 4, 5, 6, 7, 8}, ++ evicted: []int{1, 2, 3, 5}, ++ }, ++ "t2-full-b2-empty-new-items": { ++ size: 4, ++ data: []int{ ++ // fill t2, b2 should be empty since its target size is zero ++ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ++ // insert "new" items ++ 1, 2, 3, 4, ++ }, ++ evicted: []int{1, 2, 3, 4, 5, 1, 2, 3}, ++ }, ++ } ++ ++ runTest := func(t *testing.T, tc testCase) { ++ evicted := []int{} ++ c, err := NewARCWithEvict(tc.size, func(key interface{}, _ interface{}) { ++ evicted = append(evicted, key.(int)) ++ }) ++ if err != nil { ++ t.Fatal(err) ++ } ++ ++ for _, val := range tc.data { ++ c.Add(val, val) ++ } ++ ++ if !cmp.Equal(tc.evicted, evicted) { ++ t.Errorf("Expectations mismatch.\nWant: %+v\nGot: %+v", tc.evicted, evicted) ++ } ++ } ++ ++ for name, tc := range testCases { ++ t.Run(name, func(t *testing.T) { runTest(t, tc) }) ++ } ++}
diff --git a/GOIMPORT/AUTOPATCHES/simplelru/lru.go.patch b/GOIMPORT/AUTOPATCHES/simplelru/lru.go.patch new file mode 100644 index 0000000..fb0a5bb --- /dev/null +++ b/GOIMPORT/AUTOPATCHES/simplelru/lru.go.patch
@@ -0,0 +1,56 @@ +# This file reports differences detected by import.go since the last import. +# This is only for human review and not machine consumption. +# Please see go/thirdpartygo for more information. +# DO NOT EDIT. This must only be generated by //third_party/golang/import.go. + +@@ ++// Package simplelru contains intefrace and implementation of linked-list based LRU cache. + package simplelru + + import ( +@@ func (c *LRU) Peek(key interface{}) (value interface{}, ok bool) { + // Remove removes the provided key from the cache, returning if the + // key was contained. + func (c *LRU) Remove(key interface{}) (present bool) { +- if ent, ok := c.items[key]; ok { ++ ent, present := c.items[key] ++ if present { + c.removeElement(ent) +- return true + } +- return false ++ return present ++} ++ ++// RemoveWithoutEvict removes the provided key from the cache without triggering ++// onEvict callback, returning if the key was contained. ++func (c *LRU) RemoveWithoutEvict(key interface{}) (present bool) { ++ ent, present := c.items[key] ++ if present { ++ c.removeWithoutEvict(ent) ++ } ++ return present + } + + // RemoveOldest removes the oldest item from the cache. +@@ func (c *LRU) removeOldest() { + + // 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) ++ kv := c.removeWithoutEvict(e) + if c.onEvict != nil { + c.onEvict(kv.key, kv.value) + } + } ++ ++// removeWithoutEvict is used to remove a given list element from the cache ++// without triggering onEvict callback to be called. ++func (c *LRU) removeWithoutEvict(e *list.Element) *entry { ++ c.evictList.Remove(e) ++ kv := e.Value.(*entry) ++ delete(c.items, kv.key) ++ return kv ++}
diff --git a/LICENSE b/LICENSE index be2cc4d..0e5d580 100644 --- a/LICENSE +++ b/LICENSE
@@ -1,3 +1,5 @@ +Copyright (c) 2014 HashiCorp, Inc. + Mozilla Public License, version 2.0 1. Definitions
diff --git a/README.md b/README.md index 33e58cf..03bcfb5 100644 --- a/README.md +++ b/README.md
@@ -1,25 +1,7 @@ golang-lru ========== -This provides the `lru` package which implements a fixed-size -thread safe LRU cache. It is based on the cache in Groupcache. - -Documentation -============= - -Full docs are available on [Godoc](http://godoc.org/github.com/hashicorp/golang-lru) - -Example -======= - -Using the LRU is very simple: - -```go -l, _ := New(128) -for i := 0; i < 256; i++ { - l.Add(i, nil) -} -if l.Len() != 128 { - panic(fmt.Sprintf("bad len: %v", l.Len())) -} -``` +Please upgrade to github.com/hashicorp/golang-lru/v2 for all new code as v1 will +not be updated anymore. The v2 version supports generics and is faster; old code +can specify a specific tag, e.g. github.com/hashicorp/golang-lru/v1.0.2 for +backwards compatibility.
diff --git a/arc.go b/arc.go index a5ed936..b33985d 100644 --- a/arc.go +++ b/arc.go
@@ -179,7 +179,6 @@ // Add to the recently seen list c.t1.Add(key, value) - return } // replace is used to adaptively evict from either T1 or T2
diff --git a/arc_test.go b/arc_test.go index e597eda..d58882a 100644 --- a/arc_test.go +++ b/arc_test.go
@@ -20,7 +20,7 @@ trace := make([]int64, b.N*2) for i := 0; i < b.N*2; i++ { - trace[i] = rand.Int63() % 32768 + trace[i] = getRand(b) % 32768 } b.ResetTimer() @@ -50,9 +50,9 @@ trace := make([]int64, b.N*2) for i := 0; i < b.N*2; i++ { if i%2 == 0 { - trace[i] = rand.Int63() % 16384 + trace[i] = getRand(b) % 16384 } else { - trace[i] = rand.Int63() % 32768 + trace[i] = getRand(b) % 32768 } } @@ -82,8 +82,8 @@ n := 200000 for i := 0; i < n; i++ { - key := rand.Int63() % 512 - r := rand.Int63() + key := getRand(t) % 512 + r := getRand(t) switch r % 3 { case 0: l.Add(key, key)
diff --git a/go.mod b/go.mod index 824cb97..8ad8826 100644 --- a/go.mod +++ b/go.mod
@@ -1 +1,3 @@ module github.com/hashicorp/golang-lru + +go 1.12
diff --git a/lru.go b/lru.go index e0d5a59..0600c53 100644 --- a/lru.go +++ b/lru.go
@@ -6,10 +6,17 @@ "google3/third_party/golang/lru/simplelru/simplelru" ) +const ( + // DefaultEvictedBufferSize defines the default buffer size to store evicted key/val + DefaultEvictedBufferSize = 16 +) + // Cache is a thread-safe fixed size LRU cache. type Cache struct { - lru simplelru.LRUCache - lock sync.RWMutex + lru *simplelru.LRU + evictedKeys, evictedVals []interface{} + onEvictedCB func(k, v interface{}) + lock sync.RWMutex } // New creates an LRU of the given size. @@ -19,30 +26,63 @@ // NewWithEvict constructs a fixed size cache with the given eviction // callback. -func NewWithEvict(size int, onEvicted func(key interface{}, value interface{})) (*Cache, error) { - lru, err := simplelru.NewLRU(size, simplelru.EvictCallback(onEvicted)) - if err != nil { - return nil, err +func NewWithEvict(size int, onEvicted func(key, value interface{})) (c *Cache, err error) { + // create a cache with default settings + c = &Cache{ + onEvictedCB: onEvicted, } - c := &Cache{ - lru: lru, + if onEvicted != nil { + c.initEvictBuffers() + onEvicted = c.onEvicted } - return c, nil + c.lru, err = simplelru.NewLRU(size, onEvicted) + return +} + +func (c *Cache) initEvictBuffers() { + c.evictedKeys = make([]interface{}, 0, DefaultEvictedBufferSize) + c.evictedVals = make([]interface{}, 0, DefaultEvictedBufferSize) +} + +// onEvicted save evicted key/val and sent in externally registered callback +// outside of critical section +func (c *Cache) onEvicted(k, v interface{}) { + c.evictedKeys = append(c.evictedKeys, k) + c.evictedVals = append(c.evictedVals, v) } // Purge is used to completely clear the cache. func (c *Cache) Purge() { + var ks, vs []interface{} c.lock.Lock() c.lru.Purge() + if c.onEvictedCB != nil && len(c.evictedKeys) > 0 { + ks, vs = c.evictedKeys, c.evictedVals + c.initEvictBuffers() + } c.lock.Unlock() + // invoke callback outside of critical section + if c.onEvictedCB != nil { + for i := 0; i < len(ks); i++ { + c.onEvictedCB(ks[i], vs[i]) + } + } } -// Add adds a value to the cache. Returns true if an eviction occurred. +// Add adds a value to the cache. Returns true if an eviction occurred. func (c *Cache) Add(key, value interface{}) (evicted bool) { + var k, v interface{} c.lock.Lock() evicted = c.lru.Add(key, value) + if c.onEvictedCB != nil && evicted { + k, v = c.evictedKeys[0], c.evictedVals[0] + c.evictedKeys, c.evictedVals = c.evictedKeys[:0], c.evictedVals[:0] + } c.lock.Unlock() - return evicted + if c.onEvictedCB != nil && evicted { + c.onEvictedCB(k, v) + } + return } // Get looks up a key's value from the cache. @@ -71,32 +111,107 @@ return value, ok } -// 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. +// 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, evicted bool) { + var k, v interface{} c.lock.Lock() - defer c.lock.Unlock() - if c.lru.Contains(key) { + c.lock.Unlock() return true, false } evicted = c.lru.Add(key, value) + if c.onEvictedCB != nil && evicted { + k, v = c.evictedKeys[0], c.evictedVals[0] + c.evictedKeys, c.evictedVals = c.evictedKeys[:0], c.evictedVals[:0] + } + c.lock.Unlock() + if c.onEvictedCB != nil && evicted { + c.onEvictedCB(k, v) + } return false, evicted } -// Remove removes the provided key from the cache. -func (c *Cache) Remove(key interface{}) { +// PeekOrAdd 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) PeekOrAdd(key, value interface{}) (previous interface{}, ok, evicted bool) { + var k, v interface{} c.lock.Lock() - c.lru.Remove(key) + previous, ok = c.lru.Peek(key) + if ok { + c.lock.Unlock() + return previous, true, false + } + evicted = c.lru.Add(key, value) + if c.onEvictedCB != nil && evicted { + k, v = c.evictedKeys[0], c.evictedVals[0] + c.evictedKeys, c.evictedVals = c.evictedKeys[:0], c.evictedVals[:0] + } c.lock.Unlock() + if c.onEvictedCB != nil && evicted { + c.onEvictedCB(k, v) + } + return nil, false, evicted +} + +// Remove removes the provided key from the cache. +func (c *Cache) Remove(key interface{}) (present bool) { + var k, v interface{} + c.lock.Lock() + present = c.lru.Remove(key) + if c.onEvictedCB != nil && present { + k, v = c.evictedKeys[0], c.evictedVals[0] + c.evictedKeys, c.evictedVals = c.evictedKeys[:0], c.evictedVals[:0] + } + c.lock.Unlock() + if c.onEvictedCB != nil && present { + c.onEvictedCB(k, v) + } + return +} + +// Resize changes the cache size. +func (c *Cache) Resize(size int) (evicted int) { + var ks, vs []interface{} + c.lock.Lock() + evicted = c.lru.Resize(size) + if c.onEvictedCB != nil && evicted > 0 { + ks, vs = c.evictedKeys, c.evictedVals + c.initEvictBuffers() + } + c.lock.Unlock() + if c.onEvictedCB != nil && evicted > 0 { + for i := 0; i < len(ks); i++ { + c.onEvictedCB(ks[i], vs[i]) + } + } + return evicted } // RemoveOldest removes the oldest item from the cache. -func (c *Cache) RemoveOldest() { +func (c *Cache) RemoveOldest() (key, value interface{}, ok bool) { + var k, v interface{} c.lock.Lock() - c.lru.RemoveOldest() + key, value, ok = c.lru.RemoveOldest() + if c.onEvictedCB != nil && ok { + k, v = c.evictedKeys[0], c.evictedVals[0] + c.evictedKeys, c.evictedVals = c.evictedKeys[:0], c.evictedVals[:0] + } c.lock.Unlock() + if c.onEvictedCB != nil && ok { + c.onEvictedCB(k, v) + } + return +} + +// GetOldest returns the oldest entry +func (c *Cache) GetOldest() (key, value interface{}, ok bool) { + c.lock.RLock() + key, value, ok = c.lru.GetOldest() + c.lock.RUnlock() + return } // Keys returns a slice of the keys in the cache, from oldest to newest.
diff --git a/lru_test.go b/lru_test.go index e7e2350..b81705b 100644 --- a/lru_test.go +++ b/lru_test.go
@@ -1,7 +1,6 @@ package lru import ( - "math/rand" "testing" ) @@ -13,7 +12,7 @@ trace := make([]int64, b.N*2) for i := 0; i < b.N*2; i++ { - trace[i] = rand.Int63() % 32768 + trace[i] = getRand(b) % 32768 } b.ResetTimer() @@ -43,9 +42,9 @@ trace := make([]int64, b.N*2) for i := 0; i < b.N*2; i++ { if i%2 == 0 { - trace[i] = rand.Int63() % 16384 + trace[i] = getRand(b) % 16384 } else { - trace[i] = rand.Int63() % 32768 + trace[i] = getRand(b) % 32768 } } @@ -171,7 +170,7 @@ } } -// test that Contains doesn't update recent-ness +// test that ContainsOrAdd doesn't update recent-ness func TestLRUContainsOrAdd(t *testing.T) { l, err := New(2) if err != nil { @@ -201,6 +200,39 @@ } } +// test that PeekOrAdd doesn't update recent-ness +func TestLRUPeekOrAdd(t *testing.T) { + l, err := New(2) + if err != nil { + t.Fatalf("err: %v", err) + } + + l.Add(1, 1) + l.Add(2, 2) + previous, contains, evict := l.PeekOrAdd(1, 1) + if !contains { + t.Errorf("1 should be contained") + } + if evict { + t.Errorf("nothing should be evicted here") + } + if previous != 1 { + t.Errorf("previous is not equal to 1") + } + + l.Add(3, 3) + contains, evict = l.ContainsOrAdd(1, 1) + if contains { + t.Errorf("1 should not have been contained") + } + if !evict { + t.Errorf("an eviction should have occurred") + } + if !l.Contains(1) { + t.Errorf("now 1 should be contained") + } +} + // test that Peek doesn't update recent-ness func TestLRUPeek(t *testing.T) { l, err := New(2) @@ -219,3 +251,42 @@ t.Errorf("should not have updated recent-ness of 1") } } + +// test that Resize can upsize and downsize +func TestLRUResize(t *testing.T) { + onEvictCounter := 0 + onEvicted := func(k interface{}, v interface{}) { + onEvictCounter++ + } + l, err := NewWithEvict(2, onEvicted) + if err != nil { + t.Fatalf("err: %v", err) + } + + // Downsize + l.Add(1, 1) + l.Add(2, 2) + evicted := l.Resize(1) + if evicted != 1 { + t.Errorf("1 element should have been evicted: %v", evicted) + } + if onEvictCounter != 1 { + t.Errorf("onEvicted should have been called 1 time: %v", onEvictCounter) + } + + l.Add(3, 3) + if l.Contains(1) { + t.Errorf("Element 1 should have been evicted") + } + + // Upsize + evicted = l.Resize(2) + if evicted != 0 { + t.Errorf("0 elements should have been evicted: %v", evicted) + } + + l.Add(4, 4) + if !l.Contains(3) || !l.Contains(4) { + t.Errorf("Cache should have contained 2 elements") + } +}
diff --git a/simplelru/lru.go b/simplelru/lru.go index 0b40413..6714943 100644 --- a/simplelru/lru.go +++ b/simplelru/lru.go
@@ -26,7 +26,7 @@ // 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") + return nil, errors.New("must provide a positive size") } c := &LRU{ size: size, @@ -74,6 +74,9 @@ func (c *LRU) Get(key interface{}) (value interface{}, ok bool) { if ent, ok := c.items[key]; ok { c.evictList.MoveToFront(ent) + if ent.Value.(*entry) == nil { + return nil, false + } return ent.Value.(*entry).value, true } return @@ -117,7 +120,7 @@ } // RemoveOldest removes the oldest item from the cache. -func (c *LRU) RemoveOldest() (key interface{}, value interface{}, ok bool) { +func (c *LRU) RemoveOldest() (key, value interface{}, ok bool) { ent := c.evictList.Back() if ent != nil { c.removeElement(ent) @@ -128,7 +131,7 @@ } // GetOldest returns the oldest entry -func (c *LRU) GetOldest() (key interface{}, value interface{}, ok bool) { +func (c *LRU) GetOldest() (key, value interface{}, ok bool) { ent := c.evictList.Back() if ent != nil { kv := ent.Value.(*entry) @@ -153,6 +156,19 @@ return c.evictList.Len() } +// Resize changes the cache size. +func (c *LRU) Resize(size int) (evicted int) { + diff := c.Len() - size + if diff < 0 { + diff = 0 + } + for i := 0; i < diff; i++ { + c.removeOldest() + } + c.size = size + return diff +} + // removeOldest removes the oldest item from the cache. func (c *LRU) removeOldest() { ent := c.evictList.Back()
diff --git a/simplelru/lru_interface.go b/simplelru/lru_interface.go index 74c7077..cb7f8ca 100644 --- a/simplelru/lru_interface.go +++ b/simplelru/lru_interface.go
@@ -1,3 +1,4 @@ +// Package simplelru provides simple LRU implementation based on build-in container/list. package simplelru // LRUCache is the interface for simple LRU cache. @@ -10,7 +11,7 @@ // updates the "recently used"-ness of the key. #value, isFound Get(key interface{}) (value interface{}, ok bool) - // Check if a key exsists in cache without updating the recent-ness. + // Checks if a key exists in cache without updating the recent-ness. Contains(key interface{}) (ok bool) // Returns key's value without updating the "recently used"-ness of the key. @@ -31,6 +32,9 @@ // Returns the number of items in the cache. Len() int - // Clear all cache entries + // Clears all cache entries. Purge() + + // Resizes cache, returning number evicted + Resize(int) int }
diff --git a/simplelru/lru_test.go b/simplelru/lru_test.go index ca5676e..a9ffcd5 100644 --- a/simplelru/lru_test.go +++ b/simplelru/lru_test.go
@@ -165,3 +165,42 @@ t.Errorf("should not have updated recent-ness of 1") } } + +// Test that Resize can upsize and downsize +func TestLRU_Resize(t *testing.T) { + onEvictCounter := 0 + onEvicted := func(k interface{}, v interface{}) { + onEvictCounter++ + } + l, err := NewLRU(2, onEvicted) + if err != nil { + t.Fatalf("err: %v", err) + } + + // Downsize + l.Add(1, 1) + l.Add(2, 2) + evicted := l.Resize(1) + if evicted != 1 { + t.Errorf("1 element should have been evicted: %v", evicted) + } + if onEvictCounter != 1 { + t.Errorf("onEvicted should have been called 1 time: %v", onEvictCounter) + } + + l.Add(3, 3) + if l.Contains(1) { + t.Errorf("Element 1 should have been evicted") + } + + // Upsize + evicted = l.Resize(2) + if evicted != 0 { + t.Errorf("0 elements should have been evicted: %v", evicted) + } + + l.Add(4, 4) + if !l.Contains(3) || !l.Contains(4) { + t.Errorf("Cache should have contained 2 elements") + } +}
diff --git a/testing.go b/testing.go new file mode 100644 index 0000000..4927607 --- /dev/null +++ b/testing.go
@@ -0,0 +1,16 @@ +package lru + +import ( + "crypto/rand" + "math" + "math/big" + "testing" +) + +func getRand(tb testing.TB) int64 { + out, err := rand.Int(rand.Reader, big.NewInt(math.MaxInt64)) + if err != nil { + tb.Fatal(err) + } + return out.Int64() +}