summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--conn.go39
-rw-r--r--evict.go147
-rw-r--r--evict_test.go213
-rw-r--r--go.mod7
-rw-r--r--go.sum43
-rw-r--r--internal/pausedtimer/timer.go54
-rw-r--r--internal/pausedtimer/timer_test.go (renamed from utils_test.go)12
-rw-r--r--store.go (renamed from map.go)28
-rw-r--r--store_test.go (renamed from map_test.go)45
-rw-r--r--utils.go50
10 files changed, 432 insertions, 206 deletions
diff --git a/conn.go b/conn.go
index 784cc02..065bf7a 100644
--- a/conn.go
+++ b/conn.go
@@ -7,16 +7,15 @@ import (
"sync"
"time"
- "github.com/vmihailenco/msgpack"
+ "github.com/rogpeppe/go-internal/lockedfile"
+ "github.com/vmihailenco/msgpack/v5"
)
type db struct {
- File io.WriteSeeker
- Store store
- SnapshotTicker *pauseTimer
- CleanupTicker *pauseTimer
- Stop chan struct{}
- wg sync.WaitGroup
+ File io.WriteSeeker
+ Store store
+ Stop chan struct{}
+ wg sync.WaitGroup
}
type Option func(*db) error
@@ -26,7 +25,7 @@ func openFile(filename string, options ...Option) (*db, error) {
if err != nil {
return nil, err
}
- file, err := os.OpenFile(filename, os.O_RDWR|os.O_CREATE, 0666)
+ file, err := lockedfile.OpenFile(filename, os.O_RDWR|os.O_CREATE, 0666)
if err != nil {
return nil, err
}
@@ -49,10 +48,7 @@ func openFile(filename string, options ...Option) (*db, error) {
}
func openMem(options ...Option) (*db, error) {
- ret := &db{
- SnapshotTicker: newPauseTimerStopped(0),
- CleanupTicker: newPauseTimerStopped(10 * time.Second),
- }
+ ret := &db{}
ret.Store.Init()
ret.SetConfig(options...)
return ret, nil
@@ -65,6 +61,9 @@ func (d *db) Start() {
}
func (d *db) SetConfig(options ...Option) error {
+ d.Store.mu.Lock()
+ defer d.Store.mu.Unlock()
+
for _, opt := range options {
if err := opt(d); err != nil {
return err
@@ -88,14 +87,14 @@ func WithMaxCost(maxCost uint64) Option {
func SetSnapshotTime(t time.Duration) Option {
return func(d *db) error {
- d.SnapshotTicker.Reset(t)
+ d.Store.SnapshotTicker.Reset(t)
return nil
}
}
func SetCleanupTime(t time.Duration) Option {
return func(d *db) error {
- d.CleanupTicker.Reset(t)
+ d.Store.CleanupTicker.Reset(t)
return nil
}
}
@@ -103,19 +102,19 @@ func SetCleanupTime(t time.Duration) Option {
func (d *db) backgroundWorker() {
defer d.wg.Done()
- d.SnapshotTicker.Resume()
- defer d.SnapshotTicker.Stop()
+ d.Store.SnapshotTicker.Resume()
+ defer d.Store.SnapshotTicker.Stop()
- d.CleanupTicker.Resume()
- defer d.CleanupTicker.Stop()
+ d.Store.CleanupTicker.Resume()
+ defer d.Store.CleanupTicker.Stop()
for {
select {
case <-d.Stop:
return
- case <-d.SnapshotTicker.C:
+ case <-d.Store.SnapshotTicker.C:
d.Flush()
- case <-d.CleanupTicker.C:
+ case <-d.Store.CleanupTicker.C:
cleanup(&d.Store)
evict(&d.Store)
}
diff --git a/evict.go b/evict.go
index 27b6d54..73f2cec 100644
--- a/evict.go
+++ b/evict.go
@@ -1,6 +1,8 @@
package cache
-import "errors"
+import (
+ "errors"
+)
// EvictionPolicyType defines the type of eviction policy.
type EvictionPolicyType int
@@ -16,6 +18,7 @@ const (
// evictionStrategies interface defines the methods for eviction strategies.
type evictionStrategies interface {
OnInsert(n *node)
+ OnUpdate(n *node)
OnAccess(n *node)
Evict() *node
}
@@ -27,14 +30,21 @@ type evictionPolicy struct {
evict *node
}
+func pushEvict(node *node, sentinnel *node) {
+ node.EvictPrev = sentinnel
+ node.EvictNext = node.EvictPrev.EvictNext
+ node.EvictNext.EvictPrev = node
+ node.EvictPrev.EvictNext = 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 {
- return nonePolicy{evict: e.evict}
+ return fifoPolicy{evict: e.evict, shouldEvict: false}
},
PolicyFIFO: func() evictionStrategies {
- return fifoPolicy{evict: e.evict}
+ return fifoPolicy{evict: e.evict, shouldEvict: true}
},
PolicyLRU: func() evictionStrategies {
return lruPolicy{evict: e.evict}
@@ -42,6 +52,9 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
PolicyLFU: func() evictionStrategies {
return lfuPolicy{evict: e.evict}
},
+ PolicyLTR: func() evictionStrategies {
+ return ltrPolicy{evict: e.evict}
+ },
}
factory, ok := store[y]
if !ok {
@@ -51,48 +64,28 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
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
- node.EvictNext.EvictPrev = 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
+ evict *node
+ shouldEvict bool
}
// OnInsert adds a node to the eviction list.
func (s fifoPolicy) OnInsert(node *node) {
- node.EvictPrev = s.evict
- node.EvictNext = node.EvictPrev.EvictNext
- node.EvictNext.EvictPrev = node
- node.EvictPrev.EvictNext = node
+ pushEvict(node, s.evict)
}
// OnAccess is a no-op for fifoPolicy.
func (fifoPolicy) OnAccess(n *node) {
}
+// OnUpdate is a no-op for fifoPolicy.
+func (fifoPolicy) OnUpdate(n *node) {
+}
+
// Evict returns the oldest node for fifoPolicy.
func (s fifoPolicy) Evict() *node {
- if s.evict.EvictPrev != s.evict {
+ if s.shouldEvict && s.evict.EvictPrev != s.evict {
return s.evict.EvictPrev
} else {
return nil
@@ -106,21 +99,18 @@ type lruPolicy struct {
// OnInsert adds a node to the eviction list.
func (s lruPolicy) OnInsert(node *node) {
- node.EvictPrev = s.evict
- node.EvictNext = node.EvictPrev.EvictNext
- node.EvictNext.EvictPrev = node
- node.EvictPrev.EvictNext = node
+ pushEvict(node, s.evict)
+}
+
+func (s lruPolicy) OnUpdate(node *node) {
+ s.OnAccess(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
-
- node.EvictPrev = s.evict
- node.EvictNext = node.EvictPrev.EvictNext
- node.EvictNext.EvictPrev = node
- node.EvictPrev.EvictNext = node
+ s.OnInsert(node)
}
// Evict returns the least recently used node for lruPolicy.
@@ -139,11 +129,12 @@ type lfuPolicy struct {
// 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
- node.EvictNext.EvictPrev = node
- node.EvictPrev.EvictNext = node
- node.Access = 0
+ pushEvict(node, s.evict)
+}
+
+// OnUpdate increments the access count of the node and reorders the list.
+func (s lfuPolicy) OnUpdate(node *node) {
+ s.OnAccess(node)
}
// OnAccess increments the access count of the node and reorders the list.
@@ -179,3 +170,69 @@ func (s lfuPolicy) Evict() *node {
return nil
}
}
+
+// ltrPolicy struct represents the Least Remaining Time eviction policy.
+type ltrPolicy struct {
+ evict *node
+ 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(node *node) {
+ pushEvict(node, s.evict)
+
+ s.OnUpdate(node)
+}
+
+// OnAccess is a no-op for ltrPolicy.
+// It does not perform any action when a node is accessed.
+func (s ltrPolicy) OnAccess(node *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(node *node) {
+ if node.TTL() == 0 {
+ return
+ }
+ for v := node.EvictPrev; v.EvictPrev != s.evict; v = v.EvictPrev {
+ if v.TTL() == 0 {
+ continue
+ }
+ if v.TTL() < node.TTL() {
+ node.EvictNext.EvictPrev = node.EvictPrev
+ node.EvictPrev.EvictNext = node.EvictNext
+
+ node.EvictPrev = v
+ node.EvictNext = node.EvictPrev.EvictNext
+ node.EvictNext.EvictPrev = node
+ node.EvictPrev.EvictNext = node
+ return
+ }
+ }
+ for v := node.EvictNext; v.EvictNext != s.evict; v = v.EvictNext {
+ if v.TTL() == 0 {
+ continue
+ }
+ if v.TTL() > node.TTL() {
+ node.EvictNext.EvictPrev = node.EvictPrev
+ node.EvictPrev.EvictNext = node.EvictNext
+
+ node.EvictPrev = v
+ node.EvictNext = node.EvictPrev.EvictNext
+ node.EvictNext.EvictPrev = node
+ node.EvictPrev.EvictNext = node
+ return
+ }
+ }
+}
+
+// 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
+ }
+ return nil
+}
diff --git a/evict_test.go b/evict_test.go
index 3503be4..ba73c24 100644
--- a/evict_test.go
+++ b/evict_test.go
@@ -2,6 +2,7 @@ package cache
import (
"testing"
+ "time"
"github.com/stretchr/testify/assert"
)
@@ -29,44 +30,13 @@ func getListOrder(t testing.TB, evict *node) []*node {
return order
}
-func TestNonePolicy(t *testing.T) {
- t.Parallel()
-
- t.Run("OnInsert", func(t *testing.T) {
- t.Parallel()
-
- policy := nonePolicy{evict: createSentinel(t)}
-
- n0 := &node{Key: []byte("0")}
- n1 := &node{Key: []byte("1")}
-
- policy.OnInsert(n0)
- policy.OnInsert(n1)
-
- order := getListOrder(t, policy.evict)
- assert.Len(t, order, 2)
- assert.Contains(t, order, n0)
- assert.Contains(t, order, n1)
- })
-
- t.Run("Evict", func(t *testing.T) {
- t.Parallel()
-
- policy := nonePolicy{evict: createSentinel(t)}
-
- policy.OnInsert(&node{})
-
- assert.Nil(t, policy.Evict())
- })
-}
-
func TestFIFOPolicy(t *testing.T) {
t.Parallel()
t.Run("OnInsert", func(t *testing.T) {
t.Parallel()
- policy := fifoPolicy{evict: createSentinel(t)}
+ policy := fifoPolicy{evict: createSentinel(t), shouldEvict: true}
n0 := &node{Key: []byte("0")}
n1 := &node{Key: []byte("1")}
@@ -86,7 +56,7 @@ func TestFIFOPolicy(t *testing.T) {
t.Run("Evict", func(t *testing.T) {
t.Parallel()
- policy := fifoPolicy{evict: createSentinel(t)}
+ policy := fifoPolicy{evict: createSentinel(t), shouldEvict: true}
n0 := &node{Key: []byte("0")}
n1 := &node{Key: []byte("1")}
@@ -97,6 +67,17 @@ func TestFIFOPolicy(t *testing.T) {
evictedNode := policy.Evict()
assert.Same(t, n0, evictedNode)
})
+
+ t.Run("Evict noEvict", func(t *testing.T) {
+ t.Parallel()
+
+ policy := fifoPolicy{evict: createSentinel(t), shouldEvict: false}
+
+ policy.OnInsert(&node{})
+
+ assert.Nil(t, policy.Evict())
+ })
+
t.Run("Empty List", func(t *testing.T) {
t.Parallel()
@@ -269,7 +250,7 @@ func TestLFUPolicy(t *testing.T) {
policy := lfuPolicy{evict: createSentinel(t)}
- n0 := &node{Key: []byte("1")}
+ n0 := &node{Key: []byte("0")}
n1 := &node{Key: []byte("1")}
policy.OnInsert(n0)
@@ -293,3 +274,167 @@ func TestLFUPolicy(t *testing.T) {
})
})
}
+
+func TestLTRPolicy(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)
+
+ order := getListOrder(t, policy.evict)
+ assert.Len(t, order, 2)
+ assert.Same(t, n0, order[0])
+ assert.Same(t, n1, order[1])
+ })
+
+ 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)
+
+ order := getListOrder(t, policy.evict)
+ assert.Len(t, order, 2)
+ assert.Same(t, n1, order[0])
+ assert.Same(t, n0, order[1])
+ })
+ })
+
+ 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}
+
+ 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)
+
+ n0.Expiration = time.Now().Add(3 * time.Hour)
+ policy.OnUpdate(n0)
+
+ order := getListOrder(t, policy.evict)
+ assert.Len(t, order, 2)
+ assert.Same(t, n0, order[1])
+ assert.Same(t, n1, order[0])
+ })
+
+ t.Run("With TTL Decrease", 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)
+
+ n1.Expiration = time.Now().Add(30 * time.Minute)
+ policy.OnUpdate(n1)
+
+ order := getListOrder(t, policy.evict)
+ assert.Len(t, order, 2)
+ assert.Same(t, n1, order[1])
+ assert.Same(t, n0, order[0])
+ })
+ })
+
+ 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()
+ assert.Same(t, n0, evictedNode)
+ })
+
+ 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()
+ assert.Same(t, n1, evictedNode)
+ })
+
+ t.Run("Evict TTL Update", 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)
+
+ n0.Expiration = time.Now().Add(3 * time.Hour)
+ policy.OnUpdate(n0)
+
+ evictedNode := policy.Evict()
+ assert.Same(t, n0, evictedNode)
+ })
+
+ t.Run("Evict TTL Update Down", 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)
+
+ n1.Expiration = time.Now().Add(20 * time.Minute)
+ policy.OnUpdate(n1)
+
+ evictedNode := policy.Evict()
+ assert.Same(t, n1, evictedNode)
+ })
+
+ t.Run("Empty List", func(t *testing.T) {
+ t.Parallel()
+
+ policy := ltrPolicy{evict: createSentinel(t), evictZero: true}
+
+ assert.Nil(t, policy.Evict())
+ })
+ })
+}
diff --git a/go.mod b/go.mod
index e823a16..46270fd 100644
--- a/go.mod
+++ b/go.mod
@@ -3,15 +3,14 @@ module github.com/marcthe12/cache
go 1.24.0
require (
+ github.com/rogpeppe/go-internal v1.13.1
github.com/stretchr/testify v1.10.0
- github.com/vmihailenco/msgpack v4.0.4+incompatible
+ github.com/vmihailenco/msgpack/v5 v5.4.1
)
require (
github.com/davecgh/go-spew v1.1.1 // indirect
github.com/pmezard/go-difflib v1.0.0 // indirect
+ github.com/vmihailenco/tagparser/v2 v2.0.0 // indirect
gopkg.in/yaml.v3 v3.0.1 // indirect
- github.com/golang/protobuf v1.5.2 // indirect
- google.golang.org/appengine v1.6.8 // indirect
- google.golang.org/protobuf v1.26.0 // indirect
)
diff --git a/go.sum b/go.sum
index 3e0f159..6a0ab4b 100644
--- a/go.sum
+++ b/go.sum
@@ -1,45 +1,16 @@
github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
-github.com/golang/protobuf v1.5.0/go.mod h1:FsONVRAS9T7sI+LIUmWTfcYkHO4aIWwzhcaSAoJOfIk=
-github.com/golang/protobuf v1.5.2 h1:ROPKBNFfQgOUMifHyP+KYbvpjbdoFNs+aK7DXlji0Tw=
-github.com/golang/protobuf v1.5.2/go.mod h1:XVQd3VNwM+JqD3oG2Ue2ip4fOMUkwXdXDdiuN0vRsmY=
-github.com/google/go-cmp v0.5.5/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/rogpeppe/go-internal v1.13.1 h1:KvO1DLK/DRN07sQ1LQKScxyZJuNnedQ5/wKSR38lUII=
+github.com/rogpeppe/go-internal v1.13.1/go.mod h1:uMEvuHeurkdAXX61udpOXGD/AzZDWNMNyH2VO9fmH0o=
github.com/stretchr/testify v1.10.0 h1:Xv5erBjTwe/5IxqUQTdXv5kgmIvbHo3QQyRwhJsOfJA=
github.com/stretchr/testify v1.10.0/go.mod h1:r2ic/lqez/lEtzL7wO/rwa5dbSLXVDPFyf8C91i36aY=
-github.com/vmihailenco/msgpack v4.0.4+incompatible h1:dSLoQfGFAo3F6OoNhwUmLwVgaUXK79GlxNBwueZn0xI=
-github.com/vmihailenco/msgpack v4.0.4+incompatible/go.mod h1:fy3FlTQTDXWkZ7Bh6AcGMlsjHatGryHQYUTf1ShIgkk=
-github.com/yuin/goldmark v1.4.13/go.mod h1:6yULJ656Px+3vBD8DxQVa3kxgyrAnzto9xy5taEt/CY=
-golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
-golang.org/x/crypto v0.0.0-20210921155107-089bfa567519/go.mod h1:GvvjBRRGRdwPK5ydBHafDWAxML/pGHZbMvKqRZ5+Abc=
-golang.org/x/mod v0.6.0-dev.0.20220419223038-86c51ed26bb4/go.mod h1:jJ57K6gSWd91VN4djpZkiMVwK6gcyfeH4XE8wZrZaV4=
-golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
-golang.org/x/net v0.0.0-20210226172049-e18ecbb05110/go.mod h1:m0MpNAwzfU5UDzcl9v0D8zg8gWTRqZa9RBIspLL5mdg=
-golang.org/x/net v0.0.0-20220722155237-a158d28d115b/go.mod h1:XRhObCWvk6IyKnWLug+ECip1KBveYUHfp+8e9klMJ9c=
-golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
-golang.org/x/sync v0.0.0-20220722155255-886fb9371eb4/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
-golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
-golang.org/x/sys v0.0.0-20201119102817-f84b799fce68/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
-golang.org/x/sys v0.0.0-20210615035016-665e8c7367d1/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
-golang.org/x/sys v0.0.0-20220520151302-bc2c85ada10a/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
-golang.org/x/sys v0.0.0-20220722155257-8c9f86f7a55f/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
-golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
-golang.org/x/term v0.0.0-20210927222741-03fcf44c2211/go.mod h1:jbD1KX2456YbFQfuXm/mYQcufACuNUgVhRMnK/tPxf8=
-golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
-golang.org/x/text v0.3.3/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
-golang.org/x/text v0.3.7/go.mod h1:u+2+/6zg+i71rQMx5EYifcz6MCKuco9NR6JIITiCfzQ=
-golang.org/x/text v0.3.8/go.mod h1:E6s5w1FMmriuDzIBO73fBruAKo1PCIq6d2Q6DHfQ8WQ=
-golang.org/x/tools v0.0.0-20180917221912-90fa682c2a6e/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
-golang.org/x/tools v0.0.0-20191119224855-298f0cb1881e/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
-golang.org/x/tools v0.1.12/go.mod h1:hNGJHUnrk76NpqgfD5Aqm5Crs+Hm0VOH/i9J2+nxYbc=
-golang.org/x/xerrors v0.0.0-20190717185122-a985d3407aa7/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
-golang.org/x/xerrors v0.0.0-20191204190536-9bdfabe68543/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
-google.golang.org/appengine v1.6.8 h1:IhEN5q69dyKagZPYMSdIjS2HqprW324FRQZJcGqPAsM=
-google.golang.org/appengine v1.6.8/go.mod h1:1jJ3jBArFh5pcgW8gCtRJnepW8FzD1V44FJffLiz/Ds=
-google.golang.org/protobuf v1.26.0-rc.1/go.mod h1:jlhhOSvTdKEhbULTjvd4ARK9grFBp09yW+WbY/TyQbw=
-google.golang.org/protobuf v1.26.0 h1:bxAC2xTBsZGibn2RTntX0oH50xLsqy1OxA9tTL3p/lk=
-google.golang.org/protobuf v1.26.0/go.mod h1:9q0QmTI4eRPtz6boOQmLYwt+qCgq0jsYwAQnmE0givc=
+github.com/vmihailenco/msgpack/v5 v5.4.1 h1:cQriyiUvjTwOHg8QZaPihLWeRAAVoCpE00IUPn0Bjt8=
+github.com/vmihailenco/msgpack/v5 v5.4.1/go.mod h1:GaZTsDaehaPpQVyxrf5mtQlH+pc21PIudVV/E3rRQok=
+github.com/vmihailenco/tagparser/v2 v2.0.0 h1:y09buUbR+b5aycVFQs/g70pqKVZNBmxwAhO7/IwNM9g=
+github.com/vmihailenco/tagparser/v2 v2.0.0/go.mod h1:Wri+At7QHww0WTrCBeu4J6bNtoV6mEfg5OIWRZA9qds=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/internal/pausedtimer/timer.go b/internal/pausedtimer/timer.go
new file mode 100644
index 0000000..691c257
--- /dev/null
+++ b/internal/pausedtimer/timer.go
@@ -0,0 +1,54 @@
+package pausedtimer
+
+import (
+ "math"
+ "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
+}
+
+// New creates a new pauseTimer with the specified duration.
+func New(d time.Duration) *PauseTimer {
+ ret := &PauseTimer{duration: d}
+ if d != 0 {
+ ret.Ticker = time.NewTicker(d)
+ } else {
+ ret.Ticker = time.NewTicker(math.MaxInt64)
+ ret.Reset(0)
+ }
+ return ret
+}
+
+// NewStopped creates a new pauseTimer with the specified duration and stops it immediately.
+func NewStopped(d time.Duration) *PauseTimer {
+ ret := New(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 {
+ t.Stop()
+ } else {
+ t.Ticker.Reset(d)
+ }
+}
+
+// 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
+}
diff --git a/utils_test.go b/internal/pausedtimer/timer_test.go
index 329b166..6e15001 100644
--- a/utils_test.go
+++ b/internal/pausedtimer/timer_test.go
@@ -1,4 +1,4 @@
-package cache
+package pausedtimer
import (
"testing"
@@ -7,16 +7,16 @@ import (
"github.com/stretchr/testify/assert"
)
-func TestNewPauseTimer(t *testing.T) {
+func TestNew(t *testing.T) {
d := 1 * time.Second
- timer := newPauseTimer(d)
+ timer := New(d)
assert.Equal(t, d, timer.duration)
assert.NotNil(t, timer.Ticker)
}
func TestPauseTimerReset(t *testing.T) {
d := 1 * time.Second
- timer := newPauseTimer(d)
+ timer := New(d)
newD := 2 * time.Second
timer.Reset(newD)
assert.Equal(t, newD, timer.duration)
@@ -24,13 +24,13 @@ func TestPauseTimerReset(t *testing.T) {
func TestPauseTimerResume(t *testing.T) {
d := 1 * time.Second
- timer := newPauseTimerStopped(d)
+ timer := NewStopped(d)
timer.Resume()
assert.Equal(t, d, timer.duration)
}
func TestPauseTimerGetDuration(t *testing.T) {
d := 1 * time.Second
- timer := newPauseTimer(d)
+ timer := New(d)
assert.Equal(t, d, timer.GetDuration())
}
diff --git a/map.go b/store.go
index cfb0902..f4ba952 100644
--- a/map.go
+++ b/store.go
@@ -4,8 +4,12 @@ import (
"bytes"
"sync"
"time"
+
+ "github.com/marcthe12/cache/internal/pausedtimer"
)
+const initialBucketSize uint64 = 8
+
type node struct {
Hash uint64
Expiration time.Time
@@ -31,18 +35,22 @@ func (n *node) TTL() time.Duration {
}
type store struct {
- Bucket []node
- Length uint64
- Cost uint64
- Evict node
- MaxCost uint64
- Policy evictionPolicy
- mu sync.Mutex
+ Bucket []node
+ Length uint64
+ Cost uint64
+ Evict node
+ MaxCost uint64
+ SnapshotTicker *pausedtimer.PauseTimer
+ CleanupTicker *pausedtimer.PauseTimer
+ Policy evictionPolicy
+ mu sync.Mutex
}
func (s *store) Init() {
s.Clear()
s.Policy.evict = &s.Evict
+ s.SnapshotTicker = pausedtimer.NewStopped(0)
+ s.CleanupTicker = pausedtimer.NewStopped(10 * time.Second)
s.Policy.SetPolicy(PolicyNone)
}
@@ -50,7 +58,7 @@ func (s *store) Clear() {
s.mu.Lock()
defer s.mu.Unlock()
- s.Bucket = make([]node, 8)
+ s.Bucket = make([]node, initialBucketSize)
s.Length = 0
s.Cost = 0
@@ -112,6 +120,7 @@ func resize(s *store) {
for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext {
if !v.IsValid() {
+ deleteNode(s, v)
continue
}
idx := v.Hash % uint64(len(bucket))
@@ -153,13 +162,14 @@ func (s *store) set(key []byte, value []byte, ttl time.Duration) {
s.Cost = s.Cost + uint64(len(value)) - uint64(len(v.Value))
v.Value = value
v.Expiration = time.Now().Add(ttl)
- s.Policy.OnAccess(v)
+ s.Policy.OnUpdate(v)
}
bucket := &s.Bucket[idx]
if float64(s.Length)/float64(len(s.Bucket)) > 0.75 {
resize(s)
//resize may invidate pointer to bucket
+ _, idx, _ := s.lookup(key)
bucket = &s.Bucket[idx]
lazyInitBucket(bucket)
}
diff --git a/map_test.go b/store_test.go
index 5610d0a..3ad33e5 100644
--- a/map_test.go
+++ b/store_test.go
@@ -1,7 +1,9 @@
package cache
import (
+ "encoding/binary"
"testing"
+ "time"
"github.com/stretchr/testify/assert"
)
@@ -23,12 +25,26 @@ func TestStoreGetSet(t *testing.T) {
store := setupTestStore(t)
want := []byte("Value")
- store.Set([]byte("Key"), want, 0)
- got, _, ok := store.Get([]byte("Key"))
+ store.Set([]byte("Key"), want, 1*time.Hour)
+ got, ttl, ok := store.Get([]byte("Key"))
assert.Equal(t, want, got)
+
+ now := time.Now()
+ assert.WithinDuration(t, now.Add(ttl), now.Add(1*time.Hour), 1*time.Millisecond)
assert.True(t, ok)
})
+ t.Run("Exists TTL", func(t *testing.T) {
+ t.Parallel()
+
+ store := setupTestStore(t)
+
+ want := []byte("Value")
+ store.Set([]byte("Key"), want, time.Nanosecond)
+ _, _, ok := store.Get([]byte("Key"))
+ assert.False(t, ok)
+ })
+
t.Run("Not Exists", func(t *testing.T) {
t.Parallel()
@@ -50,6 +66,31 @@ func TestStoreGetSet(t *testing.T) {
assert.Equal(t, want, got)
assert.True(t, ok)
})
+
+ t.Run("Resize", func(t *testing.T) {
+ t.Parallel()
+
+ store := setupTestStore(t)
+
+ for i := range initialBucketSize {
+ key := binary.LittleEndian.AppendUint64(nil, i)
+ store.Set(key, key, 0)
+ }
+
+ for i := range store.Length {
+ key := binary.LittleEndian.AppendUint64(nil, i)
+ _, _, ok := store.Get(key)
+ assert.True(t, ok, i)
+ }
+
+ assert.Len(t, store.Bucket, int(initialBucketSize)*2)
+
+ for i := range store.Length {
+ key := binary.LittleEndian.AppendUint64(nil, i)
+ _, _, ok := store.Get(key)
+ assert.True(t, ok, i)
+ }
+ })
}
func TestStoreDelete(t *testing.T) {
diff --git a/utils.go b/utils.go
index e8dd696..c4ac9e5 100644
--- a/utils.go
+++ b/utils.go
@@ -2,58 +2,8 @@ package cache
import (
"hash/fnv"
- "math"
- "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 {
- ret.Ticker = time.NewTicker(d)
- } else {
- ret.Ticker = time.NewTicker(math.MaxInt64)
- ret.Reset(0)
- }
- 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 {
- t.Stop()
- } else {
- t.Ticker.Reset(d)
- }
-}
-
-// 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
generated by cgit v1.2.3-70-g09d2 (git 2.50.1) at 2025-08-17 20:14:31 +0000