summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--conn.go170
-rw-r--r--encoding.go96
-rw-r--r--encoding_test.go150
-rw-r--r--evict.go123
-rw-r--r--evict_test.go295
-rw-r--r--map.go204
-rw-r--r--map_test.go4
-rw-r--r--utils.go6
8 files changed, 794 insertions, 254 deletions
diff --git a/conn.go b/conn.go
index 422342f..5df57a3 100644
--- a/conn.go
+++ b/conn.go
@@ -10,124 +10,182 @@ import (
"github.com/vmihailenco/msgpack"
)
-type DB[K any, V any] struct {
- file io.WriteSeeker
- Store Store
- snapshotTicker *pauseTimer
- cleanupTicker *pauseTimer
- stop chan struct{}
+type db struct {
+ File io.WriteSeeker
+ Store store
+ SnapshotTicker *pauseTimer
+ CleanupTicker *pauseTimer
+ Stop chan struct{}
wg sync.WaitGroup
}
-func OpenFile[K any, V any](filename string) (*DB[K, V], error) {
- ret := OpenMem[K, V]()
- file, err := os.OpenFile(filename, os.O_RDWR, 0)
- if errors.Is(err, os.ErrNotExist) {
- file, err := os.Create(filename)
+type Option func(*db) error
+
+func openFile(filename string, options ...Option) (*db, error) {
+ ret, err := openMem(options...)
+ if err != nil {
+ return nil, err
+ }
+ file, err := os.OpenFile(filename, os.O_RDWR|os.O_CREATE, 0666)
+ if err != nil {
+ return nil, err
+ }
+ fileInfo, err := file.Stat()
+ if err != nil {
+ return nil, err
+ }
+ if fileInfo.Size() == 0 {
+ ret.File = file
+ ret.Flush()
+ } else {
+ err := ret.Store.LoadSnapshot(file)
if err != nil {
return nil, err
}
- ret.file = file
- ret.Flush()
- } else if err == nil {
- ret.Store.LoadSnapshot(file)
- ret.file = file
- } else {
- return nil, err
+ ret.File = file
}
return ret, nil
}
-func OpenMem[K any, V any]() *DB[K, V] {
- ret := &DB[K, V]{
- snapshotTicker: newPauseTimer(0),
+func openMem(options ...Option) (*db, error) {
+ ret := &db{
+ SnapshotTicker: newPauseTimerStopped(0),
+ CleanupTicker: newPauseTimerStopped(10 * time.Second),
}
- ret.snapshotTicker.Stop()
- ret.Clear()
- ret.Store.strategy.evict = &ret.Store.evict
- ret.SetStratergy(StrategyNone)
- return ret
+ ret.Store.Init()
+ ret.SetConfig(options...)
+ return ret, nil
}
-func (d *DB[K, V]) Start() {
- d.stop = make(chan struct{})
+func (d *db) Start() {
+ d.Stop = make(chan struct{})
d.wg.Add(1)
go d.backgroundWorker()
}
-func (d *DB[K, V]) SetStratergy(e EvictionPolicyType) error {
- return d.Store.strategy.SetPolicy(e)
+func (d *db) SetConfig(options ...Option) error {
+ for _, opt := range options {
+ if err := opt(d); err != nil {
+ return err
+ }
+ }
+ return nil
}
-func (d *DB[K, V]) SetMaxCost(e EvictionPolicyType) {
- d.Store.maxCost = d.Store.maxCost
+func WithPolicy(e EvictionPolicyType) Option {
+ return func(d *db) error {
+ return d.Store.Policy.SetPolicy(e)
+ }
}
-func (d *DB[K, V]) SetSnapshotTime(t time.Duration) {
- d.snapshotTicker.Reset(t)
+func WithMaxCost(maxCost uint64) Option {
+ return func(d *db) error {
+ d.Store.MaxCost = maxCost
+ return nil
+ }
+}
+
+func SetSnapshotTime(t time.Duration) Option {
+ return func(d *db) error {
+ d.SnapshotTicker.Reset(t)
+ return nil
+ }
+}
+
+func SetCleanupTime(t time.Duration) Option {
+ return func(d *db) error {
+ d.CleanupTicker.Reset(t)
+ return nil
+ }
}
-func (d *DB[K, V]) backgroundWorker() {
+func (d *db) backgroundWorker() {
defer d.wg.Done()
- d.snapshotTicker.Resume()
- defer d.snapshotTicker.Stop()
+ d.SnapshotTicker.Resume()
+ defer d.SnapshotTicker.Stop()
+
+ d.CleanupTicker.Resume()
+ defer d.CleanupTicker.Stop()
for {
select {
- case <-d.stop:
+ case <-d.Stop:
return
- case <-d.snapshotTicker.C:
- d.Flush()
- case <-d.snapshotTicker.C:
+ case <-d.SnapshotTicker.C:
d.Flush()
+ case <-d.CleanupTicker.C:
+ cleanup(&d.Store)
+ evict(&d.Store)
}
}
}
-func (d *DB[K, V]) Close() {
- close(d.stop)
+func (d *db) Close() {
+ close(d.Stop)
d.wg.Wait()
d.Flush()
d.Clear()
- if d.file != nil {
- closer, ok := d.file.(io.Closer)
+ if d.File != nil {
+ closer, ok := d.File.(io.Closer)
if ok {
closer.Close()
}
}
}
-func (d *DB[K, V]) Flush() error {
- if d.file != nil {
- return d.Store.Snapshot(d.file)
+func (d *db) Flush() error {
+ if d.File != nil {
+ return d.Store.Snapshot(d.File)
}
return nil
}
-func (d *DB[K, V]) Clear() {
+func (d *db) Clear() {
d.Store.Clear()
}
var ErrKeyNotFound = errors.New("key not found")
-func (h *DB[K, V]) Get(key K) (V, time.Duration, error) {
+// The Cache database. Can be initialized by either OpenFile or OpenMem. Uses per DB Locks.
+type DB[K any, V any] struct {
+ *db
+}
+
+func OpenFile[K any, V any](filename string, options ...Option) (DB[K, V], error) {
+ ret, err := openFile(filename, options...)
+ if err != nil {
+ return zero[DB[K, V]](), err
+ }
+ ret.Start()
+ return DB[K, V]{db: ret}, nil
+}
+
+func OpenMem[K any, V any](filename string, options ...Option) (DB[K, V], error) {
+ ret, err := openMem(options...)
+ if err != nil {
+ return zero[DB[K, V]](), err
+ }
+ ret.Start()
+ return DB[K, V]{db: ret}, nil
+}
+
+func (h *DB[K, V]) Get(key K, value V) (V, time.Duration, error) {
keyData, err := msgpack.Marshal(key)
if err != nil {
- return zero[V](), 0, err
+ return value, 0, err
}
v, ttl, ok := h.Store.Get(keyData)
if !ok {
- return zero[V](), 0, ErrKeyNotFound
+ return value, 0, ErrKeyNotFound
}
- var ret V
- if err = msgpack.Unmarshal(v, &ret); err != nil {
- return zero[V](), 0, err
+ if err = msgpack.Unmarshal(v, value); err != nil {
+ return value, 0, err
}
- return ret, ttl, err
+ return value, ttl, err
}
func (h *DB[K, V]) Set(key K, value V, ttl time.Duration) error {
diff --git a/encoding.go b/encoding.go
index bd2d4b7..09645ab 100644
--- a/encoding.go
+++ b/encoding.go
@@ -7,38 +7,42 @@ import (
"time"
)
-type Encoder struct {
- *bufio.Writer
+type encoder struct {
+ w *bufio.Writer
buf []byte
}
-func NewEncoder(w io.Writer) *Encoder {
- return &Encoder{
- Writer: bufio.NewWriter(w),
- buf: make([]byte, 8),
+func newEncoder(w io.Writer) *encoder {
+ return &encoder{
+ w: bufio.NewWriter(w),
+ buf: make([]byte, 8),
}
}
-func (e *Encoder) EncodeUint64(val uint64) error {
+func (e *encoder) Flush() error {
+ return e.w.Flush()
+}
+
+func (e *encoder) EncodeUint64(val uint64) error {
binary.LittleEndian.PutUint64(e.buf, val)
- _, err := e.Write(e.buf)
+ _, err := e.w.Write(e.buf)
return err
}
-func (e *Encoder) EncodeTime(val time.Time) error {
+func (e *encoder) EncodeTime(val time.Time) error {
return e.EncodeUint64(uint64(val.Unix()))
}
-func (e *Encoder) EncodeBytes(val []byte) error {
+func (e *encoder) EncodeBytes(val []byte) error {
if err := e.EncodeUint64(uint64(len(val))); err != nil {
return err
}
- _, err := e.Write(val)
+ _, err := e.w.Write(val)
return err
}
-func (e *Encoder) EncodeNode(n *Node) error {
+func (e *encoder) EncodeNode(n *node) error {
if err := e.EncodeUint64(n.Hash); err != nil {
return err
}
@@ -62,27 +66,27 @@ func (e *Encoder) EncodeNode(n *Node) error {
return nil
}
-type Decoder struct {
- *bufio.Reader
+type decoder struct {
+ r *bufio.Reader
buf []byte
}
-func NewDecoder(r io.Reader) *Decoder {
- return &Decoder{
- Reader: bufio.NewReader(r),
- buf: make([]byte, 8),
+func newDecoder(r io.Reader) *decoder {
+ return &decoder{
+ r: bufio.NewReader(r),
+ buf: make([]byte, 8),
}
}
-func (d *Decoder) DecodeUint64() (uint64, error) {
- _, err := io.ReadFull(d, d.buf)
+func (d *decoder) DecodeUint64() (uint64, error) {
+ _, err := io.ReadFull(d.r, d.buf)
if err != nil {
return 0, err
}
return binary.LittleEndian.Uint64(d.buf), nil
}
-func (d *Decoder) DecodeTime() (time.Time, error) {
+func (d *decoder) DecodeTime() (time.Time, error) {
ts, err := d.DecodeUint64()
if err != nil {
return zero[time.Time](), err
@@ -90,18 +94,18 @@ func (d *Decoder) DecodeTime() (time.Time, error) {
return time.Unix(int64(ts), 0), nil
}
-func (d *Decoder) DecodeBytes() ([]byte, error) {
+func (d *decoder) DecodeBytes() ([]byte, error) {
lenVal, err := d.DecodeUint64()
if err != nil {
return nil, err
}
data := make([]byte, lenVal)
- _, err = io.ReadFull(d, data)
+ _, err = io.ReadFull(d.r, data)
return data, err
}
-func (d *Decoder) DecodeNodes() (*Node, error) {
- n := &Node{}
+func (d *decoder) DecodeNodes() (*node, error) {
+ n := &node{}
hash, err := d.DecodeUint64()
if err != nil {
@@ -133,63 +137,63 @@ func (d *Decoder) DecodeNodes() (*Node, error) {
return n, err
}
-func (s *Store) Snapshot(w io.WriteSeeker) error {
- s.mu.RLock()
- defer s.mu.RUnlock()
+func (s *store) Snapshot(w io.WriteSeeker) error {
+ s.mu.Lock()
+ defer s.mu.Unlock()
w.Seek(0, io.SeekStart)
- wr := NewEncoder(w)
+ wr := newEncoder(w)
- wr.EncodeUint64(s.maxCost)
- wr.EncodeUint64(uint64(s.strategy.Type))
- wr.EncodeUint64(s.lenght)
+ 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 {
+ for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext {
if err := wr.EncodeNode(v); err != nil {
return err
}
}
- wr.Flush()
+ wr.w.Flush()
return nil
}
-func (s *Store) LoadSnapshot(r io.ReadSeeker) error {
+func (s *store) LoadSnapshot(r io.ReadSeeker) error {
r.Seek(0, io.SeekStart)
- rr := NewDecoder(r)
+ rr := newDecoder(r)
maxCost, err := rr.DecodeUint64()
if err != nil {
return err
}
- s.maxCost = maxCost
+ s.MaxCost = maxCost
policy, err := rr.DecodeUint64()
if err != nil {
return err
}
- s.strategy.SetPolicy(EvictionPolicyType(policy))
+ s.Policy.SetPolicy(EvictionPolicyType(policy))
lenght, err := rr.DecodeUint64()
if err != nil {
return err
}
- s.lenght = lenght
+ s.Lenght = lenght
k := 128
- for k < int(s.lenght) {
+ for k < int(s.Lenght) {
k = k << 1
}
- s.bucket = make([]Node, k)
- for range s.lenght {
+ s.Bucket = make([]node, k)
+ for range s.Lenght {
v, err := rr.DecodeNodes()
if err != nil {
return err
}
- idx := v.Hash % uint64(len(s.bucket))
+ idx := v.Hash % uint64(len(s.Bucket))
- bucket := &s.bucket[idx]
+ bucket := &s.Bucket[idx]
lazyInitBucket(bucket)
v.HashPrev = bucket
@@ -197,12 +201,12 @@ func (s *Store) LoadSnapshot(r io.ReadSeeker) error {
v.HashNext.HashPrev = v
v.HashPrev.HashNext = v
- v.EvictPrev = &s.evict
+ v.EvictPrev = &s.Evict
v.EvictNext = v.EvictPrev.EvictNext
v.EvictNext.EvictPrev = v
v.EvictPrev.EvictNext = v
- s.cost = s.cost + uint64(len(v.Key)) + uint64(len(v.Value))
+ s.Cost = s.Cost + uint64(len(v.Key)) + uint64(len(v.Value))
}
return nil
}
diff --git a/encoding_test.go b/encoding_test.go
new file mode 100644
index 0000000..d48d2fd
--- /dev/null
+++ b/encoding_test.go
@@ -0,0 +1,150 @@
+package cache
+
+import (
+ "bytes"
+ "testing"
+ "time"
+
+ "github.com/stretchr/testify/assert"
+)
+
+func TestEncodeDecodeUint64(t *testing.T) {
+ tests := []struct {
+ name string
+ value uint64
+ }{
+ {name: "Positive", value: 1234567890},
+ {name: "Zero", value: 0},
+ {name: "Max", value: ^uint64(0)},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ var buf bytes.Buffer
+ e := newEncoder(&buf)
+
+ err := e.EncodeUint64(tt.value)
+ assert.NoError(t, err)
+ err = e.Flush()
+ assert.NoError(t, err)
+
+ decoder := newDecoder(bytes.NewReader(buf.Bytes()))
+
+ decodedValue, err := decoder.DecodeUint64()
+ assert.NoError(t, err)
+
+ assert.Equal(t, tt.value, decodedValue)
+ })
+ }
+}
+
+func TestEncodeDecodeTime(t *testing.T) {
+ tests := []struct {
+ name string
+ value time.Time
+ }{
+ {name: "Time Now", value: time.Now()},
+ {name: "Time Zero", value: time.Time{}},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ var buf bytes.Buffer
+ e := newEncoder(&buf)
+
+ err := e.EncodeTime(tt.value)
+ assert.NoError(t, err)
+ err = e.Flush()
+ assert.NoError(t, err)
+
+ decoder := newDecoder(bytes.NewReader(buf.Bytes()))
+
+ decodedValue, err := decoder.DecodeTime()
+ assert.NoError(t, err)
+
+ assert.WithinDuration(t, tt.value, decodedValue, time.Second)
+ })
+ }
+}
+
+func TestEncodeDecodeBytes(t *testing.T) {
+ tests := []struct {
+ name string
+ value []byte
+ }{
+ {name: "Empty", value: []byte{}},
+ {name: "Non-Empty", value: []byte("hello world")},
+ {name: "Bytes Large", value: []byte("A very long string of characters to test large data")},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ var buf bytes.Buffer
+ e := newEncoder(&buf)
+
+ err := e.EncodeBytes(tt.value)
+ assert.NoError(t, err)
+ err = e.Flush()
+ assert.NoError(t, err)
+
+ decoder := newDecoder(bytes.NewReader(buf.Bytes()))
+
+ decodedValue, err := decoder.DecodeBytes()
+ assert.NoError(t, err)
+
+ assert.Equal(t, tt.value, decodedValue)
+ })
+ }
+}
+
+func TestEncodeDecodeNode(t *testing.T) {
+ tests := []struct {
+ 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"),
+ }},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ var buf bytes.Buffer
+ e := newEncoder(&buf)
+
+ err := e.EncodeNode(tt.value)
+ assert.NoError(t, err)
+ err = e.Flush()
+ assert.NoError(t, err)
+
+ decoder := newDecoder(bytes.NewReader(buf.Bytes()))
+
+ decodedValue, err := decoder.DecodeNodes()
+ assert.NoError(t, err)
+
+ assert.Equal(t, tt.value.Hash, decodedValue.Hash)
+ assert.WithinDuration(t, tt.value.Expiration, decodedValue.Expiration, 1*time.Second)
+ assert.Equal(t, tt.value.Access, decodedValue.Access)
+ assert.Equal(t, tt.value.Key, decodedValue.Key)
+ assert.Equal(t, tt.value.Value, decodedValue.Value)
+ })
+ }
+}
diff --git a/evict.go b/evict.go
index 5e75342..dabbe6a 100644
--- a/evict.go
+++ b/evict.go
@@ -5,88 +5,100 @@ import "errors"
type EvictionPolicyType int
const (
- StrategyNone EvictionPolicyType = iota
- StrategyFIFO
- StrategyLRU
- StrategyLFU
+ PolicyNone EvictionPolicyType = iota
+ PolicyFIFO
+ PolicyLRU
+ PolicyLFU
+ PolicyLTR
)
-type EvictionStrategies interface {
- OnInsert(n *Node)
- OnAccess(n *Node)
- Evict() *Node
+type evictionStrategies interface {
+ OnInsert(n *node)
+ OnAccess(n *node)
+ Evict() *node
}
-type EvictionPolicy struct {
- EvictionStrategies
+type evictionPolicy struct {
+ evictionStrategies
Type EvictionPolicyType
- evict *Node
+ evict *node
}
-func (e *EvictionPolicy) SetPolicy(y EvictionPolicyType) error {
- store := map[EvictionPolicyType]func() EvictionStrategies{
- StrategyNone: func() EvictionStrategies {
- return NoneStrategies{evict: e.evict}
+func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error {
+ store := map[EvictionPolicyType]func() evictionStrategies{
+ PolicyNone: func() evictionStrategies {
+ return nonePolicy{evict: e.evict}
},
- StrategyFIFO: func() EvictionStrategies {
- return FIFOStrategies{evict: e.evict}
+ PolicyFIFO: func() evictionStrategies {
+ return fifoPolicy{evict: e.evict}
},
- StrategyLRU: func() EvictionStrategies {
- return LRUStrategies{evict: e.evict}
+ PolicyLRU: func() evictionStrategies {
+ return lruPolicy{evict: e.evict}
+ },
+ PolicyLFU: func() evictionStrategies {
+ return lfuPolicy{evict: e.evict}
},
}
factory, ok := store[y]
if !ok {
- return errors.New("Invalid Policy")
+ return errors.New("invalid olicy")
}
- e.EvictionStrategies = factory()
+ e.evictionStrategies = factory()
return nil
}
-type NoneStrategies struct {
- evict *Node
+type nonePolicy struct {
+ evict *node
}
-func (s NoneStrategies) OnInsert(node *Node) {
+func (s nonePolicy) OnInsert(node *node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
-func (NoneStrategies) OnAccess(n *Node) {
+func (nonePolicy) OnAccess(n *node) {
}
-func (NoneStrategies) Evict() *Node {
+func (nonePolicy) Evict() *node {
return nil
}
-type FIFOStrategies struct {
- evict *Node
+type fifoPolicy struct {
+ evict *node
}
-func (s FIFOStrategies) OnInsert(node *Node) {
+func (s fifoPolicy) OnInsert(node *node) {
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
}
-func (FIFOStrategies) OnAccess(n *Node) {
+func (fifoPolicy) OnAccess(n *node) {
}
-func (s FIFOStrategies) Evict() *Node {
- return s.evict.EvictPrev
+func (s fifoPolicy) Evict() *node {
+ if s.evict.EvictPrev != s.evict {
+ return s.evict.EvictPrev
+ } else {
+ return nil
+ }
}
-type LRUStrategies struct {
- evict *Node
+type lruPolicy struct {
+ evict *node
}
-func (s LRUStrategies) OnInsert(node *Node) {
+func (s lruPolicy) OnInsert(node *node) {
+ node.EvictPrev = s.evict
+ node.EvictNext = node.EvictPrev.EvictNext
+ node.EvictNext.EvictPrev = node
+ node.EvictPrev.EvictNext = node
}
-func (s LRUStrategies) OnAccess(node *Node) {
+func (s lruPolicy) OnAccess(node *node) {
node.EvictNext.EvictPrev = node.EvictPrev
node.EvictPrev.EvictNext = node.EvictNext
@@ -96,36 +108,43 @@ func (s LRUStrategies) OnAccess(node *Node) {
node.EvictPrev.EvictNext = node
}
-func (s LRUStrategies) Evict() *Node {
- return s.evict.EvictPrev
+func (s lruPolicy) Evict() *node {
+ if s.evict.EvictPrev != s.evict {
+ return s.evict.EvictPrev
+ } else {
+ return nil
+ }
}
-type LFUStrategies struct {
- evict *Node
+type lfuPolicy struct {
+ evict *node
}
-func (s LFUStrategies) OnInsert(node *Node) {
+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
}
-func (s LFUStrategies) OnAccess(node *Node) {
- node.Access += 1
+func (s lfuPolicy) OnAccess(node *node) {
+ node.Access++
- node.EvictNext.EvictPrev = node.EvictPrev
- node.EvictPrev.EvictNext = node.EvictNext
+ for v := node.EvictPrev; v.EvictPrev != s.evict; v = v.EvictPrev {
+ if v.Access <= node.Access {
+ node.EvictNext.EvictPrev = node.EvictPrev
+ node.EvictPrev.EvictNext = node.EvictNext
- for v := node.EvictPrev; v != s.evict; v = v.EvictPrev {
- if v.Access >= node.Access {
node.EvictPrev = v
node.EvictNext = node.EvictPrev.EvictNext
node.EvictNext.EvictPrev = node
node.EvictPrev.EvictNext = node
- break
+ return
}
}
+ node.EvictNext.EvictPrev = node.EvictPrev
+ node.EvictPrev.EvictNext = node.EvictNext
node.EvictPrev = s.evict
node.EvictNext = node.EvictPrev.EvictNext
@@ -133,6 +152,10 @@ func (s LFUStrategies) OnAccess(node *Node) {
node.EvictPrev.EvictNext = node
}
-func (s LFUStrategies) Evict() *Node {
- return s.evict.EvictPrev
+func (s lfuPolicy) Evict() *node {
+ if s.evict.EvictPrev != s.evict {
+ return s.evict.EvictPrev
+ } else {
+ return nil
+ }
}
diff --git a/evict_test.go b/evict_test.go
new file mode 100644
index 0000000..3503be4
--- /dev/null
+++ b/evict_test.go
@@ -0,0 +1,295 @@
+package cache
+
+import (
+ "testing"
+
+ "github.com/stretchr/testify/assert"
+)
+
+func createSentinel(t testing.TB) *node {
+ t.Helper()
+ n1 := &node{Key: []byte("Sentinel")}
+ n1.EvictNext = n1
+ n1.EvictPrev = n1
+ return n1
+}
+
+func getListOrder(t testing.TB, evict *node) []*node {
+ t.Helper()
+
+ var order []*node
+ current := evict.EvictNext
+ for current != evict {
+ order = append(order, current)
+ current = current.EvictNext
+ }
+ for _, n := range order {
+ assert.Same(t, n, n.EvictPrev.EvictNext)
+ }
+ 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)}
+
+ 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, order[0], n1)
+ assert.Same(t, order[1], n0)
+ })
+
+ t.Run("Evict", func(t *testing.T) {
+ t.Parallel()
+
+ t.Run("Evict", func(t *testing.T) {
+ t.Parallel()
+
+ policy := fifoPolicy{evict: createSentinel(t)}
+
+ 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("Empty List", func(t *testing.T) {
+ t.Parallel()
+
+ policy := fifoPolicy{evict: createSentinel(t)}
+
+ assert.Nil(t, policy.Evict())
+ })
+ })
+}
+
+func TestLRUPolicy(t *testing.T) {
+ t.Run("OnInsert", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lruPolicy{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.Same(t, order[0], n1)
+ assert.Same(t, order[1], n0)
+ })
+
+ t.Run("OnAccess", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lruPolicy{evict: createSentinel(t)}
+
+ n0 := &node{Key: []byte("0")}
+ n1 := &node{Key: []byte("1")}
+
+ policy.OnInsert(n0)
+ policy.OnInsert(n1)
+
+ policy.OnAccess(n0)
+
+ order := getListOrder(t, policy.evict)
+ assert.Len(t, order, 2)
+ assert.Same(t, order[0], n0)
+ assert.Same(t, order[1], n1)
+ })
+
+ t.Run("Evict", func(t *testing.T) {
+ t.Parallel()
+
+ t.Run("Evict", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lruPolicy{evict: createSentinel(t)}
+
+ 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("OnAccess End", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lruPolicy{evict: createSentinel(t)}
+
+ n0 := &node{Key: []byte("0")}
+ n1 := &node{Key: []byte("1")}
+
+ policy.OnInsert(n0)
+ policy.OnInsert(n1)
+
+ policy.OnAccess(n0)
+
+ evictedNode := policy.Evict()
+ assert.Same(t, n1, evictedNode)
+ })
+
+ t.Run("OnAccess Interleaved", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lruPolicy{evict: createSentinel(t)}
+
+ n0 := &node{Key: []byte("0")}
+ n1 := &node{Key: []byte("1")}
+
+ policy.OnInsert(n0)
+ policy.OnAccess(n0)
+ policy.OnInsert(n1)
+
+ evictedNode := policy.Evict()
+ assert.Same(t, n0, evictedNode)
+ })
+
+ t.Run("Empty", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lruPolicy{evict: createSentinel(t)}
+
+ assert.Nil(t, policy.Evict())
+ })
+ })
+}
+
+func TestLFUPolicy(t *testing.T) {
+ t.Parallel()
+
+ t.Run("OnInsert", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lfuPolicy{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("OnAccess", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lfuPolicy{evict: createSentinel(t)}
+
+ n0 := &node{Key: []byte("0")}
+ n1 := &node{Key: []byte("1")}
+
+ policy.OnInsert(n0)
+ policy.OnInsert(n1)
+
+ policy.OnAccess(n0)
+
+ order := getListOrder(t, policy.evict)
+ assert.Len(t, order, 2)
+ assert.Same(t, order[0], n0)
+ assert.Same(t, order[1], n1)
+ })
+
+ t.Run("Evict", func(t *testing.T) {
+ t.Parallel()
+
+ t.Run("Evict", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lfuPolicy{evict: createSentinel(t)}
+
+ n0 := &node{Key: []byte("0")}
+ n1 := &node{Key: []byte("1")}
+
+ policy.OnInsert(n0)
+ policy.OnInsert(n1)
+
+ policy.OnAccess(n0)
+
+ evictedNode := policy.Evict()
+ assert.Same(t, n1, evictedNode)
+ })
+
+ t.Run("Evict After Multiple Accesses", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lfuPolicy{evict: createSentinel(t)}
+
+ n0 := &node{Key: []byte("1")}
+ n1 := &node{Key: []byte("1")}
+
+ policy.OnInsert(n0)
+ policy.OnInsert(n1)
+
+ policy.OnAccess(n0)
+
+ policy.OnAccess(n1)
+ policy.OnAccess(n1)
+
+ evictedNode := policy.Evict()
+ assert.Same(t, n0, evictedNode)
+ })
+
+ t.Run("Empty List", func(t *testing.T) {
+ t.Parallel()
+
+ policy := lfuPolicy{evict: createSentinel(t)}
+
+ assert.Nil(t, policy.Evict())
+ })
+ })
+}
diff --git a/map.go b/map.go
index cc55272..b71df2a 100644
--- a/map.go
+++ b/map.go
@@ -2,104 +2,115 @@ package cache
import (
"bytes"
- "iter"
"sync"
"time"
)
-type Map[K any, V any] interface {
- Set(key K, value V, ttl time.Duration) error
- Get(key K) (V, time.Duration, error)
- Delete(key K) error
- Clear() iter.Seq2[K, V]
-}
-
-type Node struct {
+type node struct {
Hash uint64
Expiration time.Time
Access uint64
Key []byte
Value []byte
- HashNext *Node
- HashPrev *Node
- EvictNext *Node
- EvictPrev *Node
+ HashNext *node
+ HashPrev *node
+ EvictNext *node
+ EvictPrev *node
}
-func (n *Node) IsValid() bool {
+func (n *node) IsValid() bool {
return n.Expiration.IsZero() || n.Expiration.After(time.Now())
}
-func (n *Node) Detach() {
+func (n *node) TTL() time.Duration {
+ if n.Expiration.IsZero() {
+ return 0
+ } else {
+ return time.Until(n.Expiration)
+ }
}
-type Store struct {
- bucket []Node
- lenght uint64
- cost uint64
- evict Node
- maxCost uint64
- strategy EvictionPolicy
- mu sync.RWMutex
+type store struct {
+ Bucket []node
+ Lenght uint64
+ Cost uint64
+ Evict node
+ MaxCost uint64
+ Policy evictionPolicy
+ mu sync.Mutex
}
-func (s *Store) Init() {
+func (s *store) Init() {
s.Clear()
- s.strategy.evict = &s.evict
- s.strategy.SetPolicy(StrategyNone)
+ s.Policy.evict = &s.Evict
+ s.Policy.SetPolicy(PolicyNone)
}
-func (s *Store) Clear() {
+func (s *store) Clear() {
s.mu.Lock()
defer s.mu.Unlock()
- s.bucket = make([]Node, 8)
- s.lenght = 0
- s.cost = 0
+ s.Bucket = make([]node, 8)
+ s.Lenght = 0
+ s.Cost = 0
- s.evict.EvictNext = &s.evict
- s.evict.EvictPrev = &s.evict
+ s.Evict.EvictNext = &s.Evict
+ s.Evict.EvictPrev = &s.Evict
}
-func lookup(s *Store, key []byte) (uint64, uint64) {
+func lookup(s *store, key []byte) (uint64, uint64) {
hash := hash(key)
- return hash % uint64(len(s.bucket)), hash
+ return hash % uint64(len(s.Bucket)), hash
}
-func lazyInitBucket(n *Node) {
+func lazyInitBucket(n *node) {
if n.HashNext == nil {
n.HashNext = n
n.HashPrev = n
}
}
-func (s *Store) Get(key []byte) ([]byte, time.Duration, bool) {
- s.mu.RLock()
- defer s.mu.RUnlock()
-
- idx, _ := lookup(s, key)
+func (s *store) lookup(key []byte) (*node, uint64, uint64) {
+ idx, hash := lookup(s, key)
- bucket := &s.bucket[idx]
+ bucket := &s.Bucket[idx]
lazyInitBucket(bucket)
for v := bucket.HashNext; v != bucket; v = v.HashNext {
if bytes.Equal(key, v.Key) {
- if !v.IsValid() {
- return nil, 0, false
- }
- s.strategy.OnAccess(v)
- return v.Value, time.Until(v.Expiration), true
+ return v, idx, hash
+ }
+ }
+
+ return nil, idx, hash
+}
+
+func (s *store) get(key []byte) ([]byte, time.Duration, bool) {
+ v, _, _ := s.lookup(key)
+ if v != nil {
+ if !v.IsValid() {
+ deleteNode(s, v)
+ return nil, 0, false
}
+ s.Policy.OnAccess(v)
+ return v.Value, v.TTL(), true
}
return nil, 0, false
}
-func resize(s *Store) {
- bucket := make([]Node, 2*len(s.bucket))
+func (s *store) Get(key []byte) ([]byte, time.Duration, bool) {
+ s.mu.Lock()
+ defer s.mu.Unlock()
+
+ return s.get(key)
+}
+
+func resize(s *store) {
+ bucket := make([]node, 2*len(s.Bucket))
- for v := s.evict.EvictNext; v != &s.evict; v = v.EvictNext {
+ for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext {
if !v.IsValid() {
continue
}
@@ -114,52 +125,46 @@ func resize(s *Store) {
v.HashPrev.HashNext = v
}
- s.bucket = bucket
+ s.Bucket = bucket
}
-func cleanup(s *Store) {
- for v := s.evict.EvictNext; v != &s.evict; v = v.EvictNext {
+func cleanup(s *store) {
+ for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext {
if !v.IsValid() {
deleteNode(s, v)
}
}
}
-func evict(s *Store) bool {
- n := s.strategy.Evict()
- if n == nil {
- return false
+func evict(s *store) bool {
+ for s.MaxCost != 0 && s.MaxCost < s.Cost {
+ n := s.Policy.Evict()
+ if n == nil {
+ break
+ }
+ deleteNode(s, n)
}
- deleteNode(s, n)
return true
}
-func (s *Store) Set(key []byte, value []byte, ttl time.Duration) {
- s.mu.Lock()
- defer s.mu.Unlock()
-
- idx, hash := lookup(s, key)
- bucket := &s.bucket[idx]
-
- lazyInitBucket(bucket)
-
- for v := bucket.HashNext; v != bucket; v = v.HashNext {
- if bytes.Equal(key, v.Key) {
- s.cost = s.cost + uint64(len(value)) - uint64(len(v.Value))
- v.Value = value
- v.Expiration = time.Now().Add(ttl)
- s.strategy.OnAccess(v)
- }
+func (s *store) set(key []byte, value []byte, ttl time.Duration) {
+ v, idx, hash := s.lookup(key)
+ if v != nil {
+ s.Cost = s.Cost + uint64(len(value)) - uint64(len(v.Value))
+ v.Value = value
+ v.Expiration = time.Now().Add(ttl)
+ s.Policy.OnAccess(v)
}
- if float64(s.lenght)/float64(len(s.bucket)) > 0.75 {
+ bucket := &s.Bucket[idx]
+ if float64(s.Lenght)/float64(len(s.Bucket)) > 0.75 {
resize(s)
//resize may invidate pointer to bucket
- bucket = &s.bucket[idx]
+ bucket = &s.Bucket[idx]
lazyInitBucket(bucket)
}
- node := &Node{
+ node := &node{
Hash: hash,
Key: key,
Value: value,
@@ -174,14 +179,20 @@ func (s *Store) Set(key []byte, value []byte, ttl time.Duration) {
node.HashNext.HashPrev = node
node.HashPrev.HashNext = node
- s.strategy.OnInsert(node)
- s.strategy.OnAccess(node)
+ s.Policy.OnInsert(node)
+
+ s.Cost = s.Cost + uint64(len(key)) + uint64(len(value))
+ s.Lenght = s.Lenght + 1
+}
+
+func (s *store) Set(key []byte, value []byte, ttl time.Duration) {
+ s.mu.Lock()
+ defer s.mu.Unlock()
- s.cost = s.cost + uint64(len(key)) + uint64(len(value))
- s.lenght = s.lenght + 1
+ s.set(key, value, ttl)
}
-func deleteNode(s *Store, v *Node) {
+func deleteNode(s *store, v *node) {
v.HashNext.HashPrev = v.HashPrev
v.HashPrev.HashNext = v.HashNext
v.HashNext = nil
@@ -192,30 +203,23 @@ func deleteNode(s *Store, v *Node) {
v.EvictNext = nil
v.EvictPrev = nil
- s.cost = s.cost - (uint64(len(v.Key)) + uint64(len(v.Value)))
- s.lenght = s.lenght - 1
+ s.Cost = s.Cost - (uint64(len(v.Key)) + uint64(len(v.Value)))
+ s.Lenght = s.Lenght - 1
}
-func (s *Store) Delete(key []byte) bool {
- s.mu.Lock()
- defer s.mu.Unlock()
-
- idx, _ := lookup(s, key)
-
- bucket := &s.bucket[idx]
-
- lazyInitBucket(bucket)
-
- for v := bucket.HashNext; v != bucket; v = v.HashNext {
- if bytes.Equal(key, v.Key) {
- deleteNode(s, v)
- return true
- }
+func (s *store) delete(key []byte) bool {
+ v, _, _ := s.lookup(key)
+ if v != nil {
+ deleteNode(s, v)
+ return true
}
return false
}
-func (s *Store) Cost() uint64 {
- return s.cost
+func (s *store) Delete(key []byte) bool {
+ s.mu.Lock()
+ defer s.mu.Unlock()
+
+ return s.delete(key)
}
diff --git a/map_test.go b/map_test.go
index 0a758d0..328e03f 100644
--- a/map_test.go
+++ b/map_test.go
@@ -6,10 +6,10 @@ import (
"github.com/stretchr/testify/assert"
)
-func setupTestStore(t testing.TB) *Store {
+func setupTestStore(t testing.TB) *store {
t.Helper()
- store := &Store{}
+ store := &store{}
store.Init()
return store
}
diff --git a/utils.go b/utils.go
index 9d1408e..dd8be5f 100644
--- a/utils.go
+++ b/utils.go
@@ -22,6 +22,12 @@ func newPauseTimer(d time.Duration) *pauseTimer {
return ret
}
+func newPauseTimerStopped(d time.Duration) *pauseTimer {
+ ret := newPauseTimer(d)
+ ret.Stop()
+ return ret
+}
+
func (t *pauseTimer) Reset(d time.Duration) {
t.duration = d
if t.duration == 0 {
generated by cgit v1.2.3-70-g09d2 (git 2.50.1) at 2025-08-17 20:14:27 +0000