summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--evict.go6
-rw-r--r--evict_test.go487
-rw-r--r--store.go4
-rw-r--r--store_test.go1
4 files changed, 241 insertions, 257 deletions
diff --git a/evict.go b/evict.go
index 4ce577a..6b0aabc 100644
--- a/evict.go
+++ b/evict.go
@@ -48,7 +48,7 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
return fifoPolicy{List: e.Sentinel, ShouldEvict: false, Lock: e.ListLock}
},
PolicyFIFO: func() evictionStrategies {
- return fifoPolicy{List: e.Sentinel, Lock: e.ListLock}
+ return fifoPolicy{List: e.Sentinel, ShouldEvict: true, Lock: e.ListLock}
},
PolicyLRU: func() evictionStrategies {
return lruPolicy{List: e.Sentinel, Lock: e.ListLock}
@@ -67,6 +67,7 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
}
e.evictionStrategies = factory()
+ e.Type = y
return nil
}
@@ -139,7 +140,8 @@ func (s lruPolicy) OnAccess(n *node) {
n.EvictNext.EvictPrev = n.EvictPrev
n.EvictPrev.EvictNext = n.EvictNext
- s.OnInsert(n)
+
+ pushEvict(n, s.List)
}
// Evict returns the least recently used node for lruPolicy.
diff --git a/evict_test.go b/evict_test.go
index f597537..e26315e 100644
--- a/evict_test.go
+++ b/evict_test.go
@@ -69,257 +69,6 @@ func checkOrder(tb testing.TB, policy evictOrderedPolicy, expected []*node) {
}
}
-func TestFIFOPolicy(t *testing.T) {
- t.Parallel()
-
- t.Run("OnInsert", func(t *testing.T) {
- t.Parallel()
-
- policy := fifoPolicy{List: createSentinel(t), ShouldEvict: true, Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n1)
- policy.OnInsert(n0)
-
- checkOrder(t, policy, []*node{n0, n1})
- })
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- policy := fifoPolicy{List: createSentinel(t), ShouldEvict: true, Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- evictedNode := policy.Evict()
- if n0 != evictedNode {
- t.Errorf("expected %#v, got %#v", n0, evictedNode)
- }
- })
-
- t.Run("Evict noEvict", func(t *testing.T) {
- t.Parallel()
-
- policy := fifoPolicy{List: createSentinel(t), ShouldEvict: false, Lock: &sync.RWMutex{}}
-
- policy.OnInsert(&node{})
-
- if policy.Evict() != nil {
- t.Errorf("expected nil, got %#v", policy.Evict())
- }
- })
-
- t.Run("Empty List", func(t *testing.T) {
- t.Parallel()
-
- policy := fifoPolicy{List: createSentinel(t), ShouldEvict: true, Lock: &sync.RWMutex{}}
- if policy.Evict() != nil {
- t.Errorf("expected nil, got %#v", policy.Evict())
- }
- })
- })
-}
-
-func TestLRUPolicy(t *testing.T) {
- t.Parallel()
-
- t.Run("OnInsert", func(t *testing.T) {
- t.Parallel()
-
- policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- checkOrder(t, policy, []*node{n1, n0})
- })
-
- t.Run("OnAccess", func(t *testing.T) {
- t.Parallel()
-
- policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- policy.OnAccess(n0)
-
- checkOrder(t, policy, []*node{n0, n1})
- })
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- evictedNode := policy.Evict()
- if n0 != evictedNode {
- t.Errorf("expected %#v, got %#v", n0, evictedNode)
- }
- })
-
- t.Run("OnAccess End", func(t *testing.T) {
- t.Parallel()
-
- policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- policy.OnAccess(n0)
-
- evictedNode := policy.Evict()
- if n1 != evictedNode {
- t.Errorf("expected %#v, got %#v", n1, evictedNode)
- }
- })
-
- t.Run("OnAccess Interleaved", func(t *testing.T) {
- t.Parallel()
-
- policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnAccess(n0)
- policy.OnInsert(n1)
-
- evictedNode := policy.Evict()
-
- if n0 != evictedNode {
- t.Errorf("expected %#v, got %#v", n0, evictedNode)
- }
- })
-
- t.Run("Empty", func(t *testing.T) {
- t.Parallel()
-
- policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
- if policy.Evict() != nil {
- t.Errorf("expected nil, got %#v", policy.Evict())
- }
- })
- })
-}
-
-func TestLFUPolicy(t *testing.T) {
- t.Parallel()
-
- t.Run("OnInsert", func(t *testing.T) {
- t.Parallel()
-
- policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- checkOrder(t, policy, []*node{n1, n0})
- })
-
- t.Run("OnAccess", func(t *testing.T) {
- t.Parallel()
-
- policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- policy.OnAccess(n0)
-
- checkOrder(t, policy, []*node{n0, n1})
- })
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- policy.OnAccess(n0)
-
- evictedNode := policy.Evict()
- if n1 != evictedNode {
- t.Errorf("expected %#v, got %#v", n1, evictedNode)
- }
- })
-
- t.Run("Evict After Multiple Accesses", func(t *testing.T) {
- t.Parallel()
-
- policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- policy.OnAccess(n0)
-
- policy.OnAccess(n1)
- policy.OnAccess(n1)
-
- evictedNode := policy.Evict()
-
- if n0 != evictedNode {
- t.Errorf("expected %#v, got %#v", n0, evictedNode)
- }
- })
-
- t.Run("Empty List", func(t *testing.T) {
- t.Parallel()
-
- policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
- if policy.Evict() != nil {
- t.Errorf("expected nil, got %#v", policy.Evict())
- }
- })
- })
-}
-
func TestPolicyHooks(t *testing.T) {
t.Parallel()
@@ -337,6 +86,87 @@ func TestPolicyHooks(t *testing.T) {
tests []test
}{
{
+ name: "FIFO",
+ policyType: PolicyFIFO,
+ tests: []test{
+ {
+ name: "OnInsert",
+ flag: true,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+ },
+ expected: func(nodes []*node) []*node {
+ return []*node{nodes[1], nodes[0]}
+ },
+ },
+ },
+ },
+ {
+ name: "LRU",
+ policyType: PolicyLRU,
+ tests: []test{
+ {
+ name: "OnInsert",
+ flag: true,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+ },
+ expected: func(nodes []*node) []*node {
+ return []*node{nodes[1], nodes[0]}
+ },
+ },
+ {
+ name: "OnAccess",
+ flag: true,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ policy.OnAccess(nodes[0])
+ },
+ expected: func(nodes []*node) []*node {
+ return []*node{nodes[0], nodes[1]}
+ },
+ },
+ },
+ },
+ {
+ name: "LFU",
+ policyType: PolicyLFU,
+ tests: []test{
+ {
+ name: "OnInsert",
+ flag: true,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+ },
+ expected: func(nodes []*node) []*node {
+ return []*node{nodes[1], nodes[0]}
+ },
+ },
+ {
+ name: "OnAccess",
+ flag: true,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+ policy.OnAccess(nodes[0])
+ },
+ expected: func(nodes []*node) []*node {
+ return []*node{nodes[0], nodes[1]}
+ },
+ },
+ },
+ },
+ {
name: "LTR",
policyType: PolicyLTR,
tests: []test{
@@ -446,11 +276,162 @@ func TestPolicyEvict(t *testing.T) {
tests []test
}{
{
+ name: "FIFO",
+ policyType: PolicyFIFO,
+ tests: []test{
+ {
+ name: "",
+ flag: true,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[0]
+ },
+ },
+ {
+ name: "Policy None",
+ flag: false,
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ },
+ expected: func(nodes []*node) *node {
+ return nil
+ },
+ },
+ {
+ name: "Empty List",
+ flag: true,
+ numOfNodes: 0,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {},
+ expected: func(nodes []*node) *node {
+ return nil
+ },
+ },
+ },
+ },
+ {
+ name: "LFU",
+ policyType: PolicyLFU,
+ tests: []test{
+ {
+ name: "",
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[0]
+ },
+ },
+ {
+ name: "Access",
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ policy.OnAccess(nodes[0])
+
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[1]
+ },
+ },
+ {
+ name: "Access Interleved",
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+
+ policy.OnAccess(nodes[0])
+
+ policy.OnInsert(nodes[1])
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[0]
+ },
+ },
+ {
+ name: "Empty List",
+ numOfNodes: 0,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {},
+ expected: func(nodes []*node) *node {
+ return nil
+ },
+ },
+ },
+ },
+ {
+ name: "LRU",
+ policyType: PolicyLRU,
+ tests: []test{
+ {
+ name: "",
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[0]
+ },
+ },
+ {
+ name: "Access",
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ policy.OnAccess(nodes[0])
+
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[1]
+ },
+ },
+ {
+ name: "Multiple Access",
+ numOfNodes: 2,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {
+ policy.OnInsert(nodes[0])
+ policy.OnInsert(nodes[1])
+
+ policy.OnAccess(nodes[0])
+
+ policy.OnAccess(nodes[1])
+ policy.OnAccess(nodes[1])
+ },
+ expected: func(nodes []*node) *node {
+ return nodes[0]
+ },
+ },
+ {
+ name: "Empty List",
+ numOfNodes: 0,
+ actions: func(policy evictOrderedPolicy, nodes []*node) {},
+ expected: func(nodes []*node) *node {
+ return nil
+ },
+ },
+ },
+ },
+ {
name: "LTR",
policyType: PolicyLTR,
tests: []test{
{
- name: "Evict",
+ name: "",
flag: true,
numOfNodes: 2,
actions: func(policy evictOrderedPolicy, nodes []*node) {
@@ -556,7 +537,7 @@ func TestPolicyEvict(t *testing.T) {
evictedNode := policy.Evict()
if evictedNode != tt.expected(nodes) {
- t.Errorf("expected %#v, got %#v", tt.expected(nodes), evictedNode)
+ t.Errorf("expected\n %#v\n got %#v", tt.expected(nodes), evictedNode)
}
})
}
diff --git a/store.go b/store.go
index 366bbd3..20241ac 100644
--- a/store.go
+++ b/store.go
@@ -136,8 +136,8 @@ func (s *store) lookup(key []byte) (*node, uint64, uint64) {
// Get retrieves a value from the store by key with locking.
func (s *store) Get(key []byte) ([]byte, time.Duration, bool) {
- s.Lock.Lock()
- defer s.Lock.Unlock()
+ s.Lock.RLock()
+ defer s.Lock.RUnlock()
v, _, _ := s.lookup(key)
if v != nil {
diff --git a/store_test.go b/store_test.go
index 01af0c3..f6cccc9 100644
--- a/store_test.go
+++ b/store_test.go
@@ -317,6 +317,7 @@ func TestStoreEvict(t *testing.T) {
if err := store.Policy.SetPolicy(PolicyFIFO); err != nil {
t.Fatalf("unexpected error: %v", err)
}
+
store.MaxCost = 5
store.Set([]byte("1"), []byte("1"), 0)
generated by cgit v1.2.3-70-g09d2 (git 2.50.1) at 2025-08-17 16:36:09 +0000