aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--conn.go4
-rw-r--r--encoding.go87
-rw-r--r--encoding_test.go202
-rw-r--r--evict.go22
-rw-r--r--map.go10
-rw-r--r--map_test.go22
-rw-r--r--utils.go11
-rw-r--r--utils_test.go36
8 files changed, 322 insertions, 72 deletions
diff --git a/conn.go b/conn.go
index 5df57a3..784cc02 100644
--- a/conn.go
+++ b/conn.go
@@ -188,6 +188,10 @@ func (h *DB[K, V]) Get(key K, value V) (V, time.Duration, error) {
return value, ttl, err
}
+func (h *DB[K, V]) GetValue(key K) (V, time.Duration, error) {
+ return h.Get(key, zero[V]())
+}
+
func (h *DB[K, V]) Set(key K, value V, ttl time.Duration) error {
keyData, err := msgpack.Marshal(key)
if err != nil {
diff --git a/encoding.go b/encoding.go
index 09645ab..bc68d2f 100644
--- a/encoding.go
+++ b/encoding.go
@@ -66,6 +66,27 @@ func (e *encoder) EncodeNode(n *node) error {
return nil
}
+func (e *encoder) EncodeStore(s *store) error {
+ if err := e.EncodeUint64(s.MaxCost); err != nil {
+ return err
+ }
+
+ if err := e.EncodeUint64(uint64(s.Policy.Type)); err != nil {
+ return err
+ }
+
+ if err := e.EncodeUint64(s.Length); err != nil {
+ return err
+ }
+
+ for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext {
+ if err := e.EncodeNode(v); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
type decoder struct {
r *bufio.Reader
buf []byte
@@ -137,56 +158,33 @@ func (d *decoder) DecodeNodes() (*node, error) {
return n, err
}
-func (s *store) Snapshot(w io.WriteSeeker) error {
- s.mu.Lock()
- defer s.mu.Unlock()
-
- w.Seek(0, io.SeekStart)
- wr := newEncoder(w)
-
- wr.EncodeUint64(s.MaxCost)
- wr.EncodeUint64(uint64(s.Policy.Type))
- wr.EncodeUint64(s.Lenght)
-
- for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext {
- if err := wr.EncodeNode(v); err != nil {
- return err
- }
- }
- wr.w.Flush()
- return nil
-}
-
-func (s *store) LoadSnapshot(r io.ReadSeeker) error {
- r.Seek(0, io.SeekStart)
- rr := newDecoder(r)
-
- maxCost, err := rr.DecodeUint64()
+func (d *decoder) DecodeStore(s *store) error {
+ maxCost, err := d.DecodeUint64()
if err != nil {
return err
}
s.MaxCost = maxCost
- policy, err := rr.DecodeUint64()
+ policy, err := d.DecodeUint64()
if err != nil {
return err
}
s.Policy.SetPolicy(EvictionPolicyType(policy))
- lenght, err := rr.DecodeUint64()
+ length, err := d.DecodeUint64()
if err != nil {
return err
}
- s.Lenght = lenght
+ s.Length = length
k := 128
- for k < int(s.Lenght) {
+ for k < int(s.Length) {
k = k << 1
}
s.Bucket = make([]node, k)
- for range s.Lenght {
- v, err := rr.DecodeNodes()
+ for range s.Length {
+ v, err := d.DecodeNodes()
if err != nil {
return err
}
@@ -201,8 +199,8 @@ func (s *store) LoadSnapshot(r io.ReadSeeker) error {
v.HashNext.HashPrev = v
v.HashPrev.HashNext = v
- v.EvictPrev = &s.Evict
- v.EvictNext = v.EvictPrev.EvictNext
+ v.EvictNext = &s.Evict
+ v.EvictPrev = v.EvictNext.EvictPrev
v.EvictNext.EvictPrev = v
v.EvictPrev.EvictNext = v
@@ -210,3 +208,26 @@ func (s *store) LoadSnapshot(r io.ReadSeeker) error {
}
return nil
}
+
+func (s *store) Snapshot(w io.WriteSeeker) error {
+ s.mu.Lock()
+ defer s.mu.Unlock()
+
+ if _, err := w.Seek(0, io.SeekStart); err != nil {
+ return err
+ }
+
+ wr := newEncoder(w)
+ defer wr.Flush()
+
+ return wr.EncodeStore(s)
+}
+
+func (s *store) LoadSnapshot(r io.ReadSeeker) error {
+ if _, err := r.Seek(0, io.SeekStart); err != nil {
+ return err
+ }
+ d := newDecoder(r)
+
+ return d.DecodeStore(s)
+}
diff --git a/encoding_test.go b/encoding_test.go
index d48d2fd..6ca50cb 100644
--- a/encoding_test.go
+++ b/encoding_test.go
@@ -2,10 +2,14 @@ package cache
import (
"bytes"
+ "encoding/binary"
+ "fmt"
+ "os"
"testing"
"time"
"github.com/stretchr/testify/assert"
+ "github.com/stretchr/testify/require"
)
func TestEncodeDecodeUint64(t *testing.T) {
@@ -102,27 +106,36 @@ func TestEncodeDecodeNode(t *testing.T) {
name string
value *node
}{
- {name: "Empty", value: &node{
- Hash: 1234567890,
- Expiration: time.Now(),
- Access: 987654321,
- Key: []byte("testKey"),
- Value: []byte("testValue"),
- }},
- {name: "Non-Empty", value: &node{
- Hash: 1234567890,
- Expiration: time.Now(),
- Access: 987654321,
- Key: []byte("testKey"),
- Value: []byte("testValue"),
- }},
- {name: "Bytes Large", value: &node{
- Hash: 1234567890,
- Expiration: time.Now(),
- Access: 987654321,
- Key: []byte("testKey"),
- Value: []byte("testValue"),
- }},
+ {
+ name: "Empty",
+ value: &node{
+ Hash: 1234567890,
+ Expiration: time.Now(),
+ Access: 987654321,
+ Key: []byte("testKey"),
+ Value: []byte("testValue"),
+ },
+ },
+ {
+ name: "Non-Empty",
+ value: &node{
+ Hash: 1234567890,
+ Expiration: time.Now(),
+ Access: 987654321,
+ Key: []byte("testKey"),
+ Value: []byte("testValue"),
+ },
+ },
+ {
+ name: "Bytes Large",
+ value: &node{
+ Hash: 1234567890,
+ Expiration: time.Now(),
+ Access: 987654321,
+ Key: []byte("testKey"),
+ Value: []byte("testValue"),
+ },
+ },
}
for _, tt := range tests {
@@ -148,3 +161,150 @@ func TestEncodeDecodeNode(t *testing.T) {
})
}
}
+
+func TestEncodeDecodeStrorage(t *testing.T) {
+ tests := []struct {
+ name string
+ store map[string]string
+ policy EvictionPolicyType
+ maxCost int
+ }{
+ {
+ name: "Empty",
+ store: map[string]string{},
+ policy: PolicyNone,
+ maxCost: 0,
+ },
+ {
+ name: "Single Item",
+ store: map[string]string{
+ "Test": "Test",
+ },
+ policy: PolicyNone,
+ maxCost: 0,
+ },
+ {
+ name: "Many Items",
+ store: map[string]string{
+ "Test1": "Test",
+ "Test2": "Test",
+ "Test3": "Test",
+ "Test4": "Test",
+ },
+ policy: PolicyNone,
+ maxCost: 0,
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ var buf bytes.Buffer
+ e := newEncoder(&buf)
+
+ want := setupTestStore(t)
+ want.MaxCost = uint64(tt.maxCost)
+ err := want.Policy.SetPolicy(tt.policy)
+ assert.NoError(t, err)
+
+ for k, v := range tt.store {
+ want.Set([]byte(k), []byte(v), 0)
+ }
+
+ err = e.EncodeStore(want)
+ assert.NoError(t, err)
+ err = e.Flush()
+ assert.NoError(t, err)
+
+ decoder := newDecoder(bytes.NewReader(buf.Bytes()))
+ got := setupTestStore(t)
+
+ err = decoder.DecodeStore(got)
+ assert.NoError(t, err)
+
+ assert.Equal(t, want.MaxCost, got.MaxCost)
+ assert.Equal(t, want.Length, got.Length)
+ assert.Equal(t, want.Policy.Type, got.Policy.Type)
+
+ gotOrder := getListOrder(t, &got.Evict)
+ for i, v := range getListOrder(t, &want.Evict) {
+ assert.Equal(t, v.Key, gotOrder[i].Key)
+ }
+
+ for k, v := range tt.store {
+ gotVal, _, ok := want.Get([]byte(k))
+ require.True(t, ok)
+ require.Equal(t, []byte(v), gotVal)
+ }
+ })
+ }
+}
+
+type MockSeeker struct {
+ *bytes.Buffer
+}
+
+func BenchmarkEncoder_EncodeStore(b *testing.B) {
+ file, err := os.CreateTemp("", "benchmark_test_")
+ if err != nil {
+ b.Fatal(err)
+ }
+ defer os.Remove(file.Name())
+ defer file.Close()
+
+ for n := 1; n <= 10000; n *= 10 {
+ b.Run(fmt.Sprint(n), func(b *testing.B) {
+ want := setupTestStore(b)
+
+ for i := range n {
+ buf := make([]byte, 8)
+ binary.LittleEndian.PutUint64(buf, uint64(i))
+ want.Set(buf, buf, 0)
+ }
+
+ err = want.Snapshot(file)
+ require.NoError(b, err)
+
+ fileInfo, err := file.Stat()
+ require.NoError(b, err)
+ b.SetBytes(int64(fileInfo.Size()))
+ b.ReportAllocs()
+
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ want.Snapshot(file)
+ }
+ })
+ }
+
+}
+
+func BenchmarkDecoder_DecodeStore(b *testing.B) {
+
+ file, err := os.CreateTemp("", "benchmark_test_")
+ require.NoError(b, err)
+ defer os.Remove(file.Name())
+ defer file.Close()
+
+ for n := 1; n <= 10000; n *= 10 {
+ b.Run(fmt.Sprint(n), func(b *testing.B) {
+ want := setupTestStore(b)
+ for i := range 100 {
+ buf := make([]byte, 8)
+ binary.LittleEndian.PutUint64(buf, uint64(i))
+ want.Set(buf, buf, 0)
+ }
+
+ err = want.Snapshot(file)
+ require.NoError(b, err)
+ fileInfo, err := file.Stat()
+ require.NoError(b, err)
+ b.SetBytes(int64(fileInfo.Size()))
+ b.ReportAllocs()
+
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ want.LoadSnapshot(file)
+ }
+ })
+ }
+}
diff --git a/evict.go b/evict.go
index dabbe6a..27b6d54 100644
--- a/evict.go
+++ b/evict.go
@@ -2,6 +2,7 @@ package cache
import "errors"
+// EvictionPolicyType defines the type of eviction policy.
type EvictionPolicyType int
const (
@@ -12,18 +13,21 @@ const (
PolicyLTR
)
+// evictionStrategies interface defines the methods for eviction strategies.
type evictionStrategies interface {
OnInsert(n *node)
OnAccess(n *node)
Evict() *node
}
+// evictionPolicy struct holds the eviction strategy and its type.
type evictionPolicy struct {
evictionStrategies
Type EvictionPolicyType
evict *node
}
+// SetPolicy sets the eviction policy based on the given type.
func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
store := map[EvictionPolicyType]func() evictionStrategies{
PolicyNone: func() evictionStrategies {
@@ -41,16 +45,18 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
}
factory, ok := store[y]
if !ok {
- return errors.New("invalid olicy")
+ return errors.New("invalid policy")
}
e.evictionStrategies = factory()
return nil
}
+// nonePolicy struct represents the no eviction policy.
type nonePolicy struct {
evict *node
}
+// OnInsert adds a node to the eviction list.
func (s nonePolicy) OnInsert(node *node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
@@ -58,17 +64,21 @@ func (s nonePolicy) OnInsert(node *node) {
node.EvictPrev.EvictNext = node
}
+// OnAccess is a no-op for nonePolicy.
func (nonePolicy) OnAccess(n *node) {
}
+// Evict returns nil for nonePolicy.
func (nonePolicy) Evict() *node {
return nil
}
+// fifoPolicy struct represents the First-In-First-Out eviction policy.
type fifoPolicy struct {
evict *node
}
+// OnInsert adds a node to the eviction list.
func (s fifoPolicy) OnInsert(node *node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
@@ -76,9 +86,11 @@ func (s fifoPolicy) OnInsert(node *node) {
node.EvictPrev.EvictNext = node
}
+// OnAccess is a no-op for fifoPolicy.
func (fifoPolicy) OnAccess(n *node) {
}
+// Evict returns the oldest node for fifoPolicy.
func (s fifoPolicy) Evict() *node {
if s.evict.EvictPrev != s.evict {
return s.evict.EvictPrev
@@ -87,10 +99,12 @@ func (s fifoPolicy) Evict() *node {
}
}
+// lruPolicy struct represents the Least Recently Used eviction policy.
type lruPolicy struct {
evict *node
}
+// OnInsert adds a node to the eviction list.
func (s lruPolicy) OnInsert(node *node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
@@ -98,6 +112,7 @@ func (s lruPolicy) OnInsert(node *node) {
node.EvictPrev.EvictNext = node
}
+// OnAccess moves the accessed node to the front of the eviction list.
func (s lruPolicy) OnAccess(node *node) {
node.EvictNext.EvictPrev = node.EvictPrev
node.EvictPrev.EvictNext = node.EvictNext
@@ -108,6 +123,7 @@ func (s lruPolicy) OnAccess(node *node) {
node.EvictPrev.EvictNext = 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
@@ -116,10 +132,12 @@ func (s lruPolicy) Evict() *node {
}
}
+// lfuPolicy struct represents the Least Frequently Used eviction policy.
type lfuPolicy struct {
evict *node
}
+// OnInsert adds a node to the eviction list and initializes its access count.
func (s lfuPolicy) OnInsert(node *node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
@@ -128,6 +146,7 @@ func (s lfuPolicy) OnInsert(node *node) {
node.Access = 0
}
+// OnAccess increments the access count of the node and reorders the list.
func (s lfuPolicy) OnAccess(node *node) {
node.Access++
@@ -152,6 +171,7 @@ func (s lfuPolicy) OnAccess(node *node) {
node.EvictPrev.EvictNext = 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
diff --git a/map.go b/map.go
index b71df2a..cfb0902 100644
--- a/map.go
+++ b/map.go
@@ -32,7 +32,7 @@ func (n *node) TTL() time.Duration {
type store struct {
Bucket []node
- Lenght uint64
+ Length uint64
Cost uint64
Evict node
MaxCost uint64
@@ -51,7 +51,7 @@ func (s *store) Clear() {
defer s.mu.Unlock()
s.Bucket = make([]node, 8)
- s.Lenght = 0
+ s.Length = 0
s.Cost = 0
s.Evict.EvictNext = &s.Evict
@@ -157,7 +157,7 @@ func (s *store) set(key []byte, value []byte, ttl time.Duration) {
}
bucket := &s.Bucket[idx]
- if float64(s.Lenght)/float64(len(s.Bucket)) > 0.75 {
+ if float64(s.Length)/float64(len(s.Bucket)) > 0.75 {
resize(s)
//resize may invidate pointer to bucket
bucket = &s.Bucket[idx]
@@ -182,7 +182,7 @@ func (s *store) set(key []byte, value []byte, ttl time.Duration) {
s.Policy.OnInsert(node)
s.Cost = s.Cost + uint64(len(key)) + uint64(len(value))
- s.Lenght = s.Lenght + 1
+ s.Length = s.Length + 1
}
func (s *store) Set(key []byte, value []byte, ttl time.Duration) {
@@ -204,7 +204,7 @@ func deleteNode(s *store, v *node) {
v.EvictPrev = nil
s.Cost = s.Cost - (uint64(len(v.Key)) + uint64(len(v.Value)))
- s.Lenght = s.Lenght - 1
+ s.Length = s.Length - 1
}
func (s *store) delete(key []byte) bool {
diff --git a/map_test.go b/map_test.go
index 328e03f..5610d0a 100644
--- a/map_test.go
+++ b/map_test.go
@@ -95,22 +95,20 @@ func BenchmarkStoreGet(b *testing.B) {
key := []byte("Key")
store.Set(key, []byte("Store"), 0)
- b.SetBytes(1)
- b.RunParallel(func(pb *testing.PB) {
- for pb.Next() {
- store.Get(key)
- }
- })
+ b.ReportAllocs()
+
+ for i := 0; i < b.N; i++ {
+ store.Get(key)
+ }
}
func BenchmarkStoreSet(b *testing.B) {
store := setupTestStore(b)
key := []byte("Key")
- b.SetBytes(1)
- b.RunParallel(func(pb *testing.PB) {
- for pb.Next() {
- store.Set(key, []byte("Store"), 0)
- }
- })
+ b.ReportAllocs()
+
+ for i := 0; i < b.N; i++ {
+ store.Set(key, []byte("Store"), 0)
+ }
}
diff --git a/utils.go b/utils.go
index dd8be5f..e8dd696 100644
--- a/utils.go
+++ b/utils.go
@@ -6,11 +6,15 @@ import (
"time"
)
+// pauseTimer is a struct that wraps a time.Ticker and provides additional functionality
+// to pause and resume the ticker.
+// If the duration is 0, the timer is created in a stopped state.
type pauseTimer struct {
*time.Ticker
duration time.Duration
}
+// newPauseTimer creates a new pauseTimer with the specified duration.
func newPauseTimer(d time.Duration) *pauseTimer {
ret := &pauseTimer{duration: d}
if d != 0 {
@@ -22,12 +26,15 @@ func newPauseTimer(d time.Duration) *pauseTimer {
return ret
}
+// newPauseTimerStopped creates a new pauseTimer with the specified duration and stops it immediately.
func newPauseTimerStopped(d time.Duration) *pauseTimer {
ret := newPauseTimer(d)
ret.Stop()
return ret
}
+// Reset sets the timer to the specified duration and starts it.
+// If the duration is 0, the timer is stopped.
func (t *pauseTimer) Reset(d time.Duration) {
t.duration = d
if t.duration == 0 {
@@ -37,19 +44,23 @@ func (t *pauseTimer) Reset(d time.Duration) {
}
}
+// Resume resumes the timer with its last set duration.
func (t *pauseTimer) Resume() {
t.Reset(t.GetDuration())
}
+// GetDuration returns the current duration of the timer.
func (t *pauseTimer) GetDuration() time.Duration {
return t.duration
}
+// zero returns the zero value for the specified type.
func zero[T any]() T {
var ret T
return ret
}
+// hash computes the 64-bit FNV-1a hash of the provided data.
func hash(data []byte) uint64 {
hasher := fnv.New64()
if _, err := hasher.Write(data); err != nil {
diff --git a/utils_test.go b/utils_test.go
new file mode 100644
index 0000000..329b166
--- /dev/null
+++ b/utils_test.go
@@ -0,0 +1,36 @@
+package cache
+
+import (
+ "testing"
+ "time"
+
+ "github.com/stretchr/testify/assert"
+)
+
+func TestNewPauseTimer(t *testing.T) {
+ d := 1 * time.Second
+ timer := newPauseTimer(d)
+ assert.Equal(t, d, timer.duration)
+ assert.NotNil(t, timer.Ticker)
+}
+
+func TestPauseTimerReset(t *testing.T) {
+ d := 1 * time.Second
+ timer := newPauseTimer(d)
+ newD := 2 * time.Second
+ timer.Reset(newD)
+ assert.Equal(t, newD, timer.duration)
+}
+
+func TestPauseTimerResume(t *testing.T) {
+ d := 1 * time.Second
+ timer := newPauseTimerStopped(d)
+ timer.Resume()
+ assert.Equal(t, d, timer.duration)
+}
+
+func TestPauseTimerGetDuration(t *testing.T) {
+ d := 1 * time.Second
+ timer := newPauseTimer(d)
+ assert.Equal(t, d, timer.GetDuration())
+}
generated by cgit v1.2.3-70-g09d2 (git 2.50.1) at 2025-08-17 04:40:59 +0000