Improved Concurency Part1

1 files changed, 246 insertions, 165 deletions

diff --git a/evict_test.go b/evict_test.go
index 5938b51..f597537 100644
--- a/evict_test.go
+++ b/evict_test.go
@@ -1,6 +1,8 @@
 package cache
 
 import (
+	"strconv"
+	"sync"
 	"testing"
 	"time"
 )
@@ -15,15 +17,30 @@ func createSentinel(tb testing.TB) *node {
 	return n1
 }
 
+func createPolicy(tb testing.TB, policyType EvictionPolicyType, flag bool) evictOrderedPolicy {
+	tb.Helper()
+
+	switch policyType {
+	case PolicyFIFO:
+		return &fifoPolicy{List: createSentinel(tb), ShouldEvict: flag, Lock: &sync.RWMutex{}}
+	case PolicyLTR:
+		return &ltrPolicy{List: createSentinel(tb), EvictZero: flag, Lock: &sync.RWMutex{}}
+	case PolicyLRU:
+		return &lruPolicy{List: createSentinel(tb), Lock: &sync.RWMutex{}}
+	case PolicyLFU:
+		return &lfuPolicy{List: createSentinel(tb), Lock: &sync.RWMutex{}}
+	}
+	tb.Fatalf("unknown policy type: %v", policyType)
+	return nil
+}
+
 func getListOrder(tb testing.TB, evict *node) []*node {
 	tb.Helper()
 
 	var order []*node
 
-	current := evict.EvictNext
-	for current != evict {
+	for current := evict.EvictNext; current != evict; current = current.EvictNext {
 		order = append(order, current)
-		current = current.EvictNext
 	}
 
 	for _, n := range order {
@@ -47,7 +64,7 @@ func checkOrder(tb testing.TB, policy evictOrderedPolicy, expected []*node) {
 
 	for i, n := range expected {
 		if order[i] != n {
-			tb.Errorf("element %v did not match: \nexpected: %#v\n got: %#v", i, n, order[i])
+			tb.Errorf("element %v did not match: expected: %#v got: %#v", i, string(n.Key), string(order[i].Key))
 		}
 	}
 }
@@ -58,7 +75,7 @@ func TestFIFOPolicy(t *testing.T) {
 	t.Run("OnInsert", func(t *testing.T) {
 		t.Parallel()
 
-		policy := fifoPolicy{evict: createSentinel(t), shouldEvict: true}
+		policy := fifoPolicy{List: createSentinel(t), ShouldEvict: true, Lock: &sync.RWMutex{}}
 
 		n0 := &node{Key: []byte("0")}
 		n1 := &node{Key: []byte("1")}
@@ -75,7 +92,7 @@ func TestFIFOPolicy(t *testing.T) {
 		t.Run("Evict", func(t *testing.T) {
 			t.Parallel()
 
-			policy := fifoPolicy{evict: createSentinel(t), shouldEvict: true}
+			policy := fifoPolicy{List: createSentinel(t), ShouldEvict: true, Lock: &sync.RWMutex{}}
 
 			n0 := &node{Key: []byte("0")}
 			n1 := &node{Key: []byte("1")}
@@ -92,7 +109,7 @@ func TestFIFOPolicy(t *testing.T) {
 		t.Run("Evict noEvict", func(t *testing.T) {
 			t.Parallel()
 
-			policy := fifoPolicy{evict: createSentinel(t), shouldEvict: false}
+			policy := fifoPolicy{List: createSentinel(t), ShouldEvict: false, Lock: &sync.RWMutex{}}
 
 			policy.OnInsert(&node{})
 
@@ -104,7 +121,7 @@ func TestFIFOPolicy(t *testing.T) {
 		t.Run("Empty List", func(t *testing.T) {
 			t.Parallel()
 
-			policy := fifoPolicy{evict: createSentinel(t)}
+			policy := fifoPolicy{List: createSentinel(t), ShouldEvict: true, Lock: &sync.RWMutex{}}
 			if policy.Evict() != nil {
 				t.Errorf("expected nil, got %#v", policy.Evict())
 			}
@@ -118,7 +135,7 @@ func TestLRUPolicy(t *testing.T) {
 	t.Run("OnInsert", func(t *testing.T) {
 		t.Parallel()
 
-		policy := lruPolicy{evict: createSentinel(t)}
+		policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 		n0 := &node{Key: []byte("0")}
 		n1 := &node{Key: []byte("1")}
@@ -132,7 +149,7 @@ func TestLRUPolicy(t *testing.T) {
 	t.Run("OnAccess", func(t *testing.T) {
 		t.Parallel()
 
-		policy := lruPolicy{evict: createSentinel(t)}
+		policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 		n0 := &node{Key: []byte("0")}
 		n1 := &node{Key: []byte("1")}
@@ -151,7 +168,7 @@ func TestLRUPolicy(t *testing.T) {
 		t.Run("Evict", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lruPolicy{evict: createSentinel(t)}
+			policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 			n0 := &node{Key: []byte("0")}
 			n1 := &node{Key: []byte("1")}
@@ -168,7 +185,7 @@ func TestLRUPolicy(t *testing.T) {
 		t.Run("OnAccess End", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lruPolicy{evict: createSentinel(t)}
+			policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 			n0 := &node{Key: []byte("0")}
 			n1 := &node{Key: []byte("1")}
@@ -187,7 +204,7 @@ func TestLRUPolicy(t *testing.T) {
 		t.Run("OnAccess Interleaved", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lruPolicy{evict: createSentinel(t)}
+			policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 			n0 := &node{Key: []byte("0")}
 			n1 := &node{Key: []byte("1")}
@@ -206,7 +223,7 @@ func TestLRUPolicy(t *testing.T) {
 		t.Run("Empty", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lruPolicy{evict: createSentinel(t)}
+			policy := lruPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 			if policy.Evict() != nil {
 				t.Errorf("expected nil, got %#v", policy.Evict())
 			}
@@ -220,7 +237,7 @@ func TestLFUPolicy(t *testing.T) {
 	t.Run("OnInsert", func(t *testing.T) {
 		t.Parallel()
 
-		policy := lfuPolicy{evict: createSentinel(t)}
+		policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 		n0 := &node{Key: []byte("0")}
 		n1 := &node{Key: []byte("1")}
@@ -234,7 +251,7 @@ func TestLFUPolicy(t *testing.T) {
 	t.Run("OnAccess", func(t *testing.T) {
 		t.Parallel()
 
-		policy := lfuPolicy{evict: createSentinel(t)}
+		policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 		n0 := &node{Key: []byte("0")}
 		n1 := &node{Key: []byte("1")}
@@ -253,7 +270,7 @@ func TestLFUPolicy(t *testing.T) {
 		t.Run("Evict", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lfuPolicy{evict: createSentinel(t)}
+			policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 			n0 := &node{Key: []byte("0")}
 			n1 := &node{Key: []byte("1")}
@@ -272,7 +289,7 @@ func TestLFUPolicy(t *testing.T) {
 		t.Run("Evict After Multiple Accesses", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lfuPolicy{evict: createSentinel(t)}
+			policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 
 			n0 := &node{Key: []byte("0")}
 			n1 := &node{Key: []byte("1")}
@@ -295,7 +312,7 @@ func TestLFUPolicy(t *testing.T) {
 		t.Run("Empty List", func(t *testing.T) {
 			t.Parallel()
 
-			policy := lfuPolicy{evict: createSentinel(t)}
+			policy := lfuPolicy{List: createSentinel(t), Lock: &sync.RWMutex{}}
 			if policy.Evict() != nil {
 				t.Errorf("expected nil, got %#v", policy.Evict())
 			}
@@ -303,182 +320,246 @@ func TestLFUPolicy(t *testing.T) {
 	})
 }
 
-func TestLTRPolicy(t *testing.T) {
+func TestPolicyHooks(t *testing.T) {
 	t.Parallel()
 
-	t.Run("OnInsert", func(t *testing.T) {
-		t.Parallel()
-
-		t.Run("With TTL", func(t *testing.T) {
-			t.Parallel()
-
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
-
-			n0 := &node{Key: []byte("0"), Expiration: time.Now().Add(1 * time.Hour)}
-			n1 := &node{Key: []byte("1"), Expiration: time.Now().Add(2 * time.Hour)}
-
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
-
-			checkOrder(t, policy, []*node{n0, n1})
-		})
-
-		t.Run("Without TTL", func(t *testing.T) {
-			t.Parallel()
-
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
-
-			n0 := &node{Key: []byte("0")}
-			n1 := &node{Key: []byte("1")}
-
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
-
-			checkOrder(t, policy, []*node{n1, n0})
-		})
-	})
-
-	t.Run("OnUpdate", func(t *testing.T) {
-		t.Parallel()
-
-		t.Run("With TTL", func(t *testing.T) {
-			t.Parallel()
-
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
+	type test struct {
+		name       string
+		flag       bool
+		numOfNodes int
+		actions    func(policy evictOrderedPolicy, nodes []*node)
+		expected   func(nodes []*node) []*node
+	}
 
-			n0 := &node{Key: []byte("0"), Expiration: time.Now().Add(1 * time.Hour)}
-			n1 := &node{Key: []byte("1"), Expiration: time.Now().Add(2 * time.Hour)}
+	tests := []struct {
+		name       string
+		policyType EvictionPolicyType
+		tests      []test
+	}{
+		{
+			name:       "LTR",
+			policyType: PolicyLTR,
+			tests: []test{
+				{
+					name:       "OnInsert With TTL",
+					flag:       true,
+					numOfNodes: 2,
+					actions: func(policy evictOrderedPolicy, nodes []*node) {
+						nodes[0].Expiration = time.Now().Add(1 * time.Hour)
+						nodes[1].Expiration = time.Now().Add(2 * time.Hour)
 
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
+						policy.OnInsert(nodes[0])
+						policy.OnInsert(nodes[1])
+					},
+					expected: func(nodes []*node) []*node {
+						return []*node{nodes[0], nodes[1]}
+					},
+				},
+				{
+					name:       "OnInsert Without TTL",
+					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:       "OnUpdate With TTL",
+					flag:       true,
+					numOfNodes: 2,
+					actions: func(policy evictOrderedPolicy, nodes []*node) {
+						nodes[0].Expiration = time.Now().Add(1 * time.Hour)
+						nodes[1].Expiration = time.Now().Add(2 * time.Hour)
+						policy.OnInsert(nodes[0])
+						policy.OnInsert(nodes[1])
 
-			n0.Expiration = time.Now().Add(3 * time.Hour)
-			policy.OnUpdate(n0)
+						nodes[0].Expiration = time.Now().Add(3 * time.Hour)
+						policy.OnUpdate(nodes[0])
+					},
+					expected: func(nodes []*node) []*node {
+						return []*node{nodes[1], nodes[0]}
+					},
+				},
+				{
+					name:       "OnUpdate With TTL Decrease",
+					flag:       true,
+					numOfNodes: 2,
+					actions: func(policy evictOrderedPolicy, nodes []*node) {
+						nodes[0].Expiration = time.Now().Add(1 * time.Hour)
+						nodes[1].Expiration = time.Now().Add(2 * time.Hour)
+						policy.OnInsert(nodes[0])
+						policy.OnInsert(nodes[1])
 
-			checkOrder(t, policy, []*node{n1, n0})
-		})
+						nodes[0].Expiration = time.Now().Add(20 * time.Minute)
+						policy.OnUpdate(nodes[0])
+					},
+					expected: func(nodes []*node) []*node {
+						return []*node{nodes[0], nodes[1]}
+					},
+				},
+			},
+		},
+	}
 
-		t.Run("With TTL Decrease", func(t *testing.T) {
+	for _, ts := range tests {
+		t.Run(ts.name, func(t *testing.T) {
 			t.Parallel()
 
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
+			for _, tt := range ts.tests {
+				t.Run(tt.name, func(t *testing.T) {
+					t.Parallel()
 
-			n0 := &node{Key: []byte("0"), Expiration: time.Now().Add(1 * time.Hour)}
-			n1 := &node{Key: []byte("1"), Expiration: time.Now().Add(2 * time.Hour)}
+					policy := createPolicy(t, ts.policyType, tt.flag)
 
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
+					nodes := make([]*node, tt.numOfNodes)
+					for i := range nodes {
+						nodes[i] = &node{Key: []byte(strconv.Itoa(i))}
+					}
 
-			n1.Expiration = time.Now().Add(30 * time.Minute)
-			policy.OnUpdate(n1)
+					tt.actions(policy, nodes)
 
-			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 := ltrPolicy{evict: createSentinel(t), evictZero: true}
-
-			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("no evictZero", func(t *testing.T) {
-			t.Parallel()
-
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: false}
-
-			n0 := &node{Key: []byte("0")}
-			n1 := &node{Key: []byte("1")}
-
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
-
-			if policy.Evict() != nil {
-				t.Errorf("expected nil, got %#v", policy.Evict())
+					checkOrder(t, policy, tt.expected(nodes))
+				})
 			}
 		})
+	}
+}
 
-		t.Run("Evict TTL", func(t *testing.T) {
-			t.Parallel()
-
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
-
-			n0 := &node{Key: []byte("0"), Expiration: time.Now().Add(1 * time.Hour)}
-			n1 := &node{Key: []byte("1"), Expiration: time.Now().Add(2 * time.Hour)}
-
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
-
-			evictedNode := policy.Evict()
-
-			if n1 != evictedNode {
-				t.Errorf("expected %#v, got %#v", n0, evictedNode)
-			}
-		})
+func TestPolicyEvict(t *testing.T) {
+	t.Parallel()
 
-		t.Run("Evict TTL Update", func(t *testing.T) {
-			t.Parallel()
+	type test struct {
+		name       string
+		flag       bool
+		numOfNodes int
+		actions    func(policy evictOrderedPolicy, nodes []*node)
+		expected   func(nodes []*node) *node
+	}
 
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
+	tests := []struct {
+		name       string
+		policyType EvictionPolicyType
+		tests      []test
+	}{
+		{
+			name:       "LTR",
+			policyType: PolicyLTR,
+			tests: []test{
+				{
+					name:       "Evict",
+					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:       "no evictZero",
+					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:       "Evict TTL",
+					flag:       true,
+					numOfNodes: 2,
+					actions: func(policy evictOrderedPolicy, nodes []*node) {
+						nodes[0].Expiration = time.Now().Add(1 * time.Hour)
+						nodes[1].Expiration = time.Now().Add(2 * time.Hour)
 
-			n0 := &node{Key: []byte("0"), Expiration: time.Now().Add(1 * time.Hour)}
-			n1 := &node{Key: []byte("1"), Expiration: time.Now().Add(2 * time.Hour)}
+						policy.OnInsert(nodes[0])
+						policy.OnInsert(nodes[1])
+					},
+					expected: func(nodes []*node) *node {
+						return nodes[1]
+					},
+				},
+				{
+					name:       "Evict TTL Update",
+					flag:       true,
+					numOfNodes: 2,
+					actions: func(policy evictOrderedPolicy, nodes []*node) {
+						nodes[0].Expiration = time.Now().Add(1 * time.Hour)
+						nodes[1].Expiration = time.Now().Add(2 * time.Hour)
 
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
+						policy.OnInsert(nodes[0])
+						policy.OnInsert(nodes[1])
 
-			n0.Expiration = time.Now().Add(3 * time.Hour)
-			policy.OnUpdate(n0)
+						nodes[0].Expiration = time.Now().Add(3 * time.Hour)
+						policy.OnUpdate(nodes[0])
+					},
+					expected: func(nodes []*node) *node {
+						return nodes[0]
+					},
+				},
+				{
+					name:       "Evict TTL Update Down",
+					flag:       true,
+					numOfNodes: 2,
+					actions: func(policy evictOrderedPolicy, nodes []*node) {
+						nodes[0].Expiration = time.Now().Add(1 * time.Hour)
+						nodes[1].Expiration = time.Now().Add(2 * time.Hour)
 
-			evictedNode := policy.Evict()
+						policy.OnInsert(nodes[0])
+						policy.OnInsert(nodes[1])
 
-			if n0 != evictedNode {
-				t.Errorf("expected %#v, got %#v", n0, evictedNode)
-			}
-		})
+						nodes[0].Expiration = time.Now().Add(20 * time.Minute)
+						policy.OnUpdate(nodes[0])
+					},
+					expected: func(nodes []*node) *node {
+						return nodes[1]
+					},
+				},
+				{
+					name:       "Empty List",
+					flag:       true,
+					numOfNodes: 0,
+					actions:    func(policy evictOrderedPolicy, nodes []*node) {},
+					expected: func(nodes []*node) *node {
+						return nil
+					},
+				},
+			},
+		},
+	}
 
-		t.Run("Evict TTL Update Down", func(t *testing.T) {
+	for _, ts := range tests {
+		t.Run(ts.name, func(t *testing.T) {
 			t.Parallel()
 
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
-
-			n0 := &node{Key: []byte("0"), Expiration: time.Now().Add(1 * time.Hour)}
-			n1 := &node{Key: []byte("1"), Expiration: time.Now().Add(2 * time.Hour)}
-
-			policy.OnInsert(n0)
-			policy.OnInsert(n1)
+			for _, tt := range ts.tests {
+				t.Run(tt.name, func(t *testing.T) {
+					t.Parallel()
 
-			n1.Expiration = time.Now().Add(20 * time.Minute)
-			policy.OnUpdate(n1)
-
-			evictedNode := policy.Evict()
+					policy := createPolicy(t, ts.policyType, tt.flag)
 
-			if n1 != evictedNode {
-				t.Errorf("expected %#v, got %#v", n0, evictedNode)
-			}
-		})
+					nodes := make([]*node, tt.numOfNodes)
+					for i := range nodes {
+						nodes[i] = &node{Key: []byte(strconv.Itoa(i))}
+					}
 
-		t.Run("Empty List", func(t *testing.T) {
-			t.Parallel()
+					tt.actions(policy, nodes)
 
-			policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
-			if policy.Evict() != nil {
-				t.Errorf("expected nil, got %#v", policy.Evict())
+					evictedNode := policy.Evict()
+					if evictedNode != tt.expected(nodes) {
+						t.Errorf("expected %#v, got %#v", tt.expected(nodes), evictedNode)
+					}
+				})
 			}
 		})
-	})
+	}
 }