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()
+}
