Improved Concurency Part1

7 files changed, 451 insertions, 235 deletions

diff --git a/conn.go b/conn.go
index f34db81..ecd92aa 100644
--- a/conn.go
+++ b/conn.go
@@ -76,8 +76,8 @@ func (d *db) Start() {
 
 // SetConfig applies configuration options to the db.
 func (d *db) SetConfig(options ...Option) error {
-	d.Store.mu.Lock()
-	defer d.Store.mu.Unlock()
+	d.Store.Lock.Lock()
+	defer d.Store.Lock.Unlock()
 
 	for _, opt := range options {
 		if err := opt(d); err != nil {
diff --git a/encoding.go b/encoding.go
index 343e345..fe376b2 100644
--- a/encoding.go
+++ b/encoding.go
@@ -224,15 +224,15 @@ func (d *decoder) DecodeStore(s *store) error {
 		v.EvictNext.EvictPrev = v
 		v.EvictPrev.EvictNext = v
 
-		s.Cost = s.Cost + uint64(len(v.Key)) + uint64(len(v.Value))
+		s.Cost = s.Cost + v.Cost()
 	}
 
 	return nil
 }
 
 func (s *store) Snapshot(w io.WriteSeeker) error {
-	s.mu.Lock()
-	defer s.mu.Unlock()
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
 
 	if _, err := w.Seek(0, io.SeekStart); err != nil {
 		return err
diff --git a/encoding_test.go b/encoding_test.go
index 44104e4..dadde12 100644
--- a/encoding_test.go
+++ b/encoding_test.go
@@ -322,7 +322,7 @@ func TestEncodeDecodeStrorage(t *testing.T) {
 	}
 }
 
-func BenchmarkEncoder_EncodeStore(b *testing.B) {
+func BenchmarkStoreLoadSnapshot(b *testing.B) {
 	file, err := os.CreateTemp(b.TempDir(), "benchmark_test_")
 	if err != nil {
 		b.Fatal(err)
@@ -363,7 +363,7 @@ func BenchmarkEncoder_EncodeStore(b *testing.B) {
 	}
 }
 
-func BenchmarkDecoder_DecodeStore(b *testing.B) {
+func BenchmarkStoreLoadSnapsot(b *testing.B) {
 	file, err := os.CreateTemp(b.TempDir(), "benchmark_test_")
 
 	if err != nil {
diff --git a/evict.go b/evict.go
index 6b977b1..4ce577a 100644
--- a/evict.go
+++ b/evict.go
@@ -2,6 +2,7 @@ package cache
 
 import (
 	"errors"
+	"sync"
 )
 
 // EvictionPolicyType defines the type of eviction policy.
@@ -27,8 +28,9 @@ type evictionStrategies interface {
 // evictionPolicy struct holds the eviction strategy and its type.
 type evictionPolicy struct {
 	evictionStrategies
-	Type  EvictionPolicyType
-	evict *node
+	Type     EvictionPolicyType
+	Sentinel *node
+	ListLock *sync.RWMutex
 }
 
 // pushEvict adds a node to the eviction list.
@@ -43,19 +45,19 @@ func pushEvict(node *node, sentinnel *node) {
 func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
 	store := map[EvictionPolicyType]func() evictionStrategies{
 		PolicyNone: func() evictionStrategies {
-			return fifoPolicy{evict: e.evict, shouldEvict: false}
+			return fifoPolicy{List: e.Sentinel, ShouldEvict: false, Lock: e.ListLock}
 		},
 		PolicyFIFO: func() evictionStrategies {
-			return fifoPolicy{evict: e.evict, shouldEvict: true}
+			return fifoPolicy{List: e.Sentinel, Lock: e.ListLock}
 		},
 		PolicyLRU: func() evictionStrategies {
-			return lruPolicy{evict: e.evict}
+			return lruPolicy{List: e.Sentinel, Lock: e.ListLock}
 		},
 		PolicyLFU: func() evictionStrategies {
-			return lfuPolicy{evict: e.evict}
+			return lfuPolicy{List: e.Sentinel, Lock: e.ListLock}
 		},
 		PolicyLTR: func() evictionStrategies {
-			return ltrPolicy{evict: e.evict}
+			return ltrPolicy{List: e.Sentinel, EvictZero: true, Lock: e.ListLock}
 		},
 	}
 
@@ -75,13 +77,17 @@ type evictOrderedPolicy interface {
 }
 
 type fifoPolicy struct {
-	evict       *node
-	shouldEvict bool
+	List        *node
+	Lock        *sync.RWMutex
+	ShouldEvict bool
 }
 
 // OnInsert adds a node to the eviction list.
 func (s fifoPolicy) OnInsert(n *node) {
-	pushEvict(n, s.evict)
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
+
+	pushEvict(n, s.List)
 }
 
 // OnAccess is a no-op for fifoPolicy.
@@ -96,25 +102,29 @@ func (fifoPolicy) OnUpdate(n *node) {
 
 // Evict returns the oldest node for fifoPolicy.
 func (s fifoPolicy) Evict() *node {
-	if s.shouldEvict && s.evict.EvictPrev != s.evict {
-		return s.evict.EvictPrev
+	if s.ShouldEvict && s.List.EvictPrev != s.List {
+		return s.List.EvictPrev
 	} else {
 		return nil
 	}
 }
 
 func (s fifoPolicy) getEvict() *node {
-	return s.evict
+	return s.List
 }
 
 // lruPolicy struct represents the Least Recently Used eviction policy.
 type lruPolicy struct {
-	evict *node
+	List *node
+	Lock *sync.RWMutex
 }
 
 // OnInsert adds a node to the eviction list.
 func (s lruPolicy) OnInsert(n *node) {
-	pushEvict(n, s.evict)
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
+
+	pushEvict(n, s.List)
 }
 
 // OnUpdate moves the accessed node to the front of the eviction list.
@@ -124,6 +134,9 @@ func (s lruPolicy) OnUpdate(n *node) {
 
 // OnAccess moves the accessed node to the front of the eviction list.
 func (s lruPolicy) OnAccess(n *node) {
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
+
 	n.EvictNext.EvictPrev = n.EvictPrev
 	n.EvictPrev.EvictNext = n.EvictNext
 	s.OnInsert(n)
@@ -131,25 +144,29 @@ func (s lruPolicy) OnAccess(n *node) {
 
 // Evict returns the least recently used node for lruPolicy.
 func (s lruPolicy) Evict() *node {
-	if s.evict.EvictPrev != s.evict {
-		return s.evict.EvictPrev
+	if s.List.EvictPrev != s.List {
+		return s.List.EvictPrev
 	} else {
 		return nil
 	}
 }
 
 func (s lruPolicy) getEvict() *node {
-	return s.evict
+	return s.List
 }
 
 // lfuPolicy struct represents the Least Frequently Used eviction policy.
 type lfuPolicy struct {
-	evict *node
+	List *node
+	Lock *sync.RWMutex
 }
 
 // OnInsert adds a node to the eviction list and initializes its access count.
 func (s lfuPolicy) OnInsert(n *node) {
-	pushEvict(n, s.evict)
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
+
+	pushEvict(n, s.List)
 }
 
 // OnUpdate increments the access count of the node and reorders the list.
@@ -159,9 +176,12 @@ func (s lfuPolicy) OnUpdate(n *node) {
 
 // OnAccess increments the access count of the node and reorders the list.
 func (s lfuPolicy) OnAccess(n *node) {
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
+
 	n.Access++
 
-	for v := n.EvictPrev; v.EvictPrev != s.evict; v = v.EvictPrev {
+	for v := n.EvictPrev; v.EvictPrev != s.List; v = v.EvictPrev {
 		if v.Access <= n.Access {
 			n.EvictNext.EvictPrev = n.EvictPrev
 			n.EvictPrev.EvictNext = n.EvictNext
@@ -178,7 +198,7 @@ func (s lfuPolicy) OnAccess(n *node) {
 	n.EvictNext.EvictPrev = n.EvictPrev
 	n.EvictPrev.EvictNext = n.EvictNext
 
-	n.EvictPrev = s.evict
+	n.EvictPrev = s.List
 	n.EvictNext = n.EvictPrev.EvictNext
 	n.EvictNext.EvictPrev = n
 	n.EvictPrev.EvictNext = n
@@ -186,29 +206,33 @@ func (s lfuPolicy) OnAccess(n *node) {
 
 // Evict returns the least frequently used node for LFU.
 func (s lfuPolicy) Evict() *node {
-	if s.evict.EvictPrev != s.evict {
-		return s.evict.EvictPrev
+	if s.List.EvictPrev != s.List {
+		return s.List.EvictPrev
 	} else {
 		return nil
 	}
 }
 
-func (s ltrPolicy) getEvict() *node {
-	return s.evict
+func (s lfuPolicy) getEvict() *node {
+	return s.List
 }
 
 // ltrPolicy struct represents the Least Remaining Time eviction policy.
 type ltrPolicy struct {
-	evict     *node
-	evictZero bool
+	List      *node
+	Lock      *sync.RWMutex
+	EvictZero bool
 }
 
 // OnInsert adds a node to the eviction list based on its TTL (Time To Live).
 // It places the node in the correct position in the list based on TTL.
 func (s ltrPolicy) OnInsert(n *node) {
-	pushEvict(n, s.evict)
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
 
-	s.OnUpdate(n)
+	pushEvict(n, s.List)
+
+	s.update(n)
 }
 
 // OnAccess is a no-op for ltrPolicy.
@@ -220,11 +244,18 @@ func (s ltrPolicy) OnAccess(n *node) {
 // OnUpdate updates the position of the node in the eviction list based on its TTL.
 // It reorders the list to maintain the correct order based on TTL.
 func (s ltrPolicy) OnUpdate(n *node) {
+	s.Lock.Lock()
+	defer s.Lock.Unlock()
+
+	s.update(n)
+}
+
+func (s ltrPolicy) update(n *node) {
 	if n.TTL() == 0 {
 		return
 	}
 
-	for v := n.EvictPrev; v.EvictPrev != s.evict; v = v.EvictPrev {
+	for v := n.EvictPrev; v.EvictPrev != s.List; v = v.EvictPrev {
 		if v.TTL() == 0 {
 			continue
 		}
@@ -242,7 +273,7 @@ func (s ltrPolicy) OnUpdate(n *node) {
 		}
 	}
 
-	for v := n.EvictNext; v.EvictNext != s.evict; v = v.EvictNext {
+	for v := n.EvictNext; v.EvictNext != s.List; v = v.EvictNext {
 		if v.TTL() == 0 {
 			continue
 		}
@@ -264,13 +295,13 @@ func (s ltrPolicy) OnUpdate(n *node) {
 // Evict returns the node with the least remaining time to live for ltrPolicy.
 // It returns the node at the end of the eviction list.
 func (s ltrPolicy) Evict() *node {
-	if s.evict.EvictPrev != s.evict && (s.evict.EvictPrev.TTL() != 0 || s.evictZero) {
-		return s.evict.EvictPrev
+	if s.List.EvictPrev != s.List && (s.List.EvictPrev.TTL() != 0 || s.EvictZero) {
+		return s.List.EvictPrev
 	}
 
 	return nil
 }
 
-func (s lfuPolicy) getEvict() *node {
-	return s.evict
+func (s ltrPolicy) getEvict() *node {
+	return s.List
 }
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) {