First Commit

7 files changed, 875 insertions, 0 deletions

diff --git a/conn.go b/conn.go
new file mode 100644
index 0000000..d88744c
--- /dev/null
+++ b/conn.go
@@ -0,0 +1,138 @@
+package cache
+
+import (
+	"errors"
+	"os"
+	"sync"
+	"time"
+
+	"github.com/vmihailenco/msgpack"
+)
+
+type DB[K any, V any] struct {
+	file  *os.File
+	Store Store
+	stop  chan struct{}
+	wg    sync.WaitGroup
+}
+
+func OpenFile[K any, V any](filename string) (*DB[K, V], error) {
+	ret := &DB[K, V]{}
+	file, err := os.OpenFile(filename, os.O_RDWR, 0)
+	if errors.Is(err, os.ErrNotExist) {
+		file, err := os.Create(filename)
+		if err != nil {
+			return nil, err
+		}
+		ret.file = file
+		ret.SetStratergy(StrategyNone)
+		ret.Clear()
+		ret.Flush()
+	} else if err == nil {
+		ret.Clear()
+		ret.file = file
+		ret.Store.LoadSnapshot(ret.file)
+	} else {
+		return nil, err
+	}
+	ret.wg.Add(1)
+	go ret.backgroundWorker()
+	return ret, nil
+}
+
+func OpenMem[K any, V any]() *DB[K, V] {
+	ret := &DB[K, V]{}
+	ret.SetStratergy(StrategyNone)
+	ret.Clear()
+	return ret
+}
+
+func (d *DB[K, V]) SetStratergy(e EvictionPolicy) error {
+	strategy, err := e.ToStratergy(&d.Store.evict)
+	if err != nil {
+		return err
+	}
+	d.Store.strategy = strategy
+	return nil
+}
+
+func (d *DB[K, V]) SetMaxCost(e EvictionPolicy) {
+	d.Store.max_cost = d.Store.max_cost
+}
+
+func (d *DB[K, V]) backgroundWorker() {
+	defer d.wg.Done()
+	for {
+		select {
+		case <-d.stop:
+			return
+			// TODO: Do house keeping
+		}
+	}
+}
+
+func (d *DB[K, V]) Close() {
+	close(d.stop)
+	d.wg.Wait()
+	d.Flush()
+	d.Clear()
+	if d.file != nil {
+		d.file.Close()
+	}
+}
+
+func (d *DB[K, V]) Flush() error {
+	if d.file != nil {
+		return d.Store.Snapshot(d.file)
+	}
+	return nil
+}
+
+func (d *DB[K, V]) Clear() {
+	d.Store.Clear()
+}
+
+var ErrKeyNotFound = errors.New("key not found")
+
+func (h *DB[K, V]) Get(key K) (V, time.Duration, error) {
+	keyData, err := msgpack.Marshal(key)
+	if err != nil {
+		return zero[V](), 0, err
+	}
+
+	v, ttl, ok := h.Store.Get(keyData)
+	if !ok {
+		return zero[V](), 0, ErrKeyNotFound
+	}
+
+	var ret V
+	if err = msgpack.Unmarshal(v, &ret); err != nil {
+		return zero[V](), 0, err
+	}
+	return ret, ttl, err
+}
+
+func (h *DB[K, V]) Set(key K, value V, ttl time.Duration) error {
+	keyData, err := msgpack.Marshal(key)
+	if err != nil {
+		return err
+	}
+	valueData, err := msgpack.Marshal(value)
+	if err != nil {
+		return err
+	}
+	h.Store.Set(keyData, valueData, ttl)
+	return nil
+}
+
+func (h *DB[K, V]) Delete(key K) error {
+	keyData, err := msgpack.Marshal(key)
+	if err != nil {
+		return err
+	}
+	ok := h.Store.Delete(keyData)
+	if !ok {
+		return ErrKeyNotFound
+	}
+	return nil
+}
diff --git a/encoding.go b/encoding.go
new file mode 100644
index 0000000..ff07d2d
--- /dev/null
+++ b/encoding.go
@@ -0,0 +1,194 @@
+package cache
+
+import (
+	"bufio"
+	"encoding/binary"
+	"io"
+	"time"
+)
+
+type Encoder struct {
+	*bufio.Writer
+	buf []byte
+}
+
+func NewEncoder(w io.Writer) *Encoder {
+	return &Encoder{
+		Writer: bufio.NewWriter(w),
+		buf:    make([]byte, 8),
+	}
+}
+
+func (e *Encoder) EncodeUint64(val uint64) error {
+	binary.LittleEndian.PutUint64(e.buf, val)
+	_, err := e.Write(e.buf)
+	return err
+}
+
+func (e *Encoder) EncodeTime(val time.Time) error {
+	return e.EncodeUint64(uint64(val.Unix()))
+}
+
+func (e *Encoder) EncodeBytes(val []byte) error {
+	if err := e.EncodeUint64(uint64(len(val))); err != nil {
+		return err
+	}
+
+	_, err := e.Write(val)
+	return err
+}
+
+func (e *Encoder) EncodeNode(n *Node) error {
+	if err := e.EncodeUint64(n.Hash); err != nil {
+		return err
+	}
+
+	if err := e.EncodeTime(n.Expiration); err != nil {
+		return err
+	}
+
+	if err := e.EncodeUint64(n.Access); err != nil {
+		return err
+	}
+
+	if err := e.EncodeBytes(n.Key); err != nil {
+		return err
+	}
+
+	if err := e.EncodeBytes(n.Value); err != nil {
+		return err
+	}
+
+	return nil
+}
+
+type Decoder struct {
+	*bufio.Reader
+	buf []byte
+}
+
+func NewDecoder(r io.Reader) *Decoder {
+	return &Decoder{
+		Reader: bufio.NewReader(r),
+		buf:    make([]byte, 8),
+	}
+}
+
+func (d *Decoder) DecodeUint64() (uint64, error) {
+	_, err := io.ReadFull(d, d.buf)
+	if err != nil {
+		return 0, err
+	}
+	return binary.LittleEndian.Uint64(d.buf), nil
+}
+
+func (d *Decoder) DecodeTime() (time.Time, error) {
+	ts, err := d.DecodeUint64()
+	if err != nil {
+		return zero[time.Time](), err
+	}
+	return time.Unix(int64(ts), 0), nil
+}
+
+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)
+	return data, err
+}
+
+func (d *Decoder) DecodeNodes() (*Node, error) {
+	n := &Node{}
+
+	hash, err := d.DecodeUint64()
+	if err != nil {
+		return nil, err
+	}
+	n.Hash = hash
+
+	expiration, err := d.DecodeTime()
+	if err != nil {
+		return nil, err
+	}
+	n.Expiration = expiration
+
+	access, err := d.DecodeUint64()
+	if err != nil {
+		return nil, err
+	}
+	n.Access = access
+
+	n.Key, err = d.DecodeBytes()
+	if err != nil {
+		return nil, err
+	}
+
+	n.Value, err = d.DecodeBytes()
+	if err != nil {
+		return nil, err
+	}
+	return n, err
+}
+
+func (s *Store) Snapshot(w io.WriteSeeker) error {
+	s.mu.RLock()
+	defer s.mu.RUnlock()
+
+	w.Seek(0, io.SeekStart)
+	wr := NewEncoder(w)
+
+	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.Flush()
+	return nil
+}
+
+func (s *Store) LoadSnapshot(r io.ReadSeeker) error {
+	r.Seek(0, io.SeekStart)
+	rr := NewDecoder(r)
+
+	lenght, err := rr.DecodeUint64()
+	if err != nil {
+		return err
+	}
+	s.lenght = lenght
+
+	k := 128
+	for k < int(s.lenght) {
+		k = k << 1
+	}
+
+	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))
+
+		bucket := &s.bucket[idx]
+		lazyInitBucket(bucket)
+
+		v.HashPrev = bucket
+		v.HashNext = v.HashPrev.HashNext
+		v.HashNext.HashPrev = v
+		v.HashPrev.HashNext = v
+
+		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))
+	}
+	return nil
+}
diff --git a/evict.go b/evict.go
new file mode 100644
index 0000000..987aa04
--- /dev/null
+++ b/evict.go
@@ -0,0 +1,132 @@
+package cache
+
+import "errors"
+
+type EvictionPolicy int
+
+const (
+	StrategyNone EvictionPolicy = iota
+	StrategyFIFO
+	StrategyLRU
+	StrategyLFU
+)
+
+type EvictionStrategies interface {
+	OnInsert(n *Node)
+	OnAccess(n *Node)
+	Evict() *Node
+}
+
+func (e EvictionPolicy) ToStratergy(evict *Node) (EvictionStrategies, error) {
+	store := map[EvictionPolicy]func() EvictionStrategies{
+		StrategyNone: func() EvictionStrategies {
+			return NoneStrategies{evict: evict}
+		},
+		StrategyFIFO: func() EvictionStrategies {
+			return FIFOStrategies{evict: evict}
+		},
+		StrategyLRU: func() EvictionStrategies {
+			return LRUStrategies{evict: evict}
+		},
+	}
+	factory, ok := store[e]
+	if !ok {
+		return nil, errors.New("Invalid Policy")
+	}
+	return factory(), nil
+}
+
+type NoneStrategies struct {
+	evict *Node
+}
+
+func (s NoneStrategies) 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 (NoneStrategies) Evict() *Node {
+	return nil
+}
+
+type FIFOStrategies struct {
+	evict *Node
+}
+
+func (s FIFOStrategies) 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 (s FIFOStrategies) Evict() *Node {
+	return s.evict.EvictPrev
+}
+
+type LRUStrategies struct {
+	evict *Node
+}
+
+func (s LRUStrategies) OnInsert(node *Node) {
+}
+
+func (s LRUStrategies) 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
+}
+
+func (s LRUStrategies) Evict() *Node {
+	return s.evict.EvictPrev
+}
+
+type LFUStrategies struct {
+	evict *Node
+}
+
+func (s LFUStrategies) OnInsert(node *Node) {
+	node.EvictPrev = s.evict
+	node.EvictNext = node.EvictPrev.EvictNext
+	node.EvictNext.EvictPrev = node
+	node.EvictPrev.EvictNext = node
+
+}
+
+func (s LFUStrategies) OnAccess(node *Node) {
+	node.Access += 1
+
+	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
+		}
+	}
+
+	node.EvictPrev = s.evict
+	node.EvictNext = node.EvictPrev.EvictNext
+	node.EvictNext.EvictPrev = node
+	node.EvictPrev.EvictNext = node
+}
+
+func (s LFUStrategies) Evict() *Node {
+	return s.evict.EvictPrev
+}
diff --git a/go.mod b/go.mod
new file mode 100644
index 0000000..e823a16
--- /dev/null
+++ b/go.mod
@@ -0,0 +1,17 @@
+module github.com/marcthe12/cache
+
+go 1.24.0
+
+require (
+	github.com/stretchr/testify v1.10.0
+	github.com/vmihailenco/msgpack v4.0.4+incompatible
+)
+
+require (
+	github.com/davecgh/go-spew v1.1.1 // indirect
+	github.com/pmezard/go-difflib v1.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
new file mode 100644
index 0000000..3e0f159
--- /dev/null
+++ b/go.sum
@@ -0,0 +1,45 @@
+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/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=
+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/map.go b/map.go
new file mode 100644
index 0000000..71bc16b
--- /dev/null
+++ b/map.go
@@ -0,0 +1,192 @@
+package cache
+
+import (
+	"bytes"
+	"hash/fnv"
+	"iter"
+	"sync"
+	"time"
+)
+
+func zero[T any]() T {
+	var ret T
+	return ret
+}
+
+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 {
+	Hash       uint64
+	Expiration time.Time
+	Access     uint64
+	Key        []byte
+	Value      []byte
+	HashNext   *Node
+	HashPrev   *Node
+	EvictNext  *Node
+	EvictPrev  *Node
+}
+
+type Store struct {
+	bucket   []Node
+	lenght   uint64
+	cost     uint64
+	evict    Node
+	max_cost uint64
+	strategy EvictionStrategies
+	mu       sync.RWMutex
+}
+
+func (s *Store) Clear() {
+	s.mu.Lock()
+	defer s.mu.Unlock()
+
+	s.bucket = make([]Node, 8)
+	s.lenght = 0
+	s.cost = 0
+
+	s.evict.EvictNext = &s.evict
+	s.evict.EvictPrev = &s.evict
+}
+
+func hash(data []byte) uint64 {
+	hasher := fnv.New64()
+	if _, err := hasher.Write(data); err != nil {
+		panic(err)
+	}
+	return hasher.Sum64()
+}
+
+func lookup(s *Store, key []byte) (uint64, uint64) {
+	hash := hash(key)
+	return hash % uint64(len(s.bucket)), hash
+}
+
+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)
+
+	bucket := &s.bucket[idx]
+
+	lazyInitBucket(bucket)
+
+	for v := bucket.HashNext; v != bucket; v = v.HashNext {
+		if bytes.Equal(key, v.Key) {
+			s.strategy.OnAccess(v)
+			return v.Value, 0, true
+		}
+	}
+
+	return nil, 0, false
+}
+
+func resize(s *Store) {
+	bucket := make([]Node, 2*len(s.bucket))
+
+	for v := s.evict.EvictNext; v != &s.evict; v = v.EvictNext {
+		idx := v.Hash % uint64(len(bucket))
+
+		n := &bucket[idx]
+		lazyInitBucket(n)
+
+		v.HashPrev = n
+		v.HashNext = v.HashPrev.HashNext
+		v.HashNext.HashPrev = v
+		v.HashPrev.HashNext = v
+	}
+
+	s.bucket = bucket
+}
+
+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)
+		}
+	}
+
+	if float64(s.lenght)/float64(len(s.bucket)) > 0.75 {
+		resize(s)
+		//resize may invidate pointer to bucket
+		bucket = &s.bucket[idx]
+		lazyInitBucket(bucket)
+	}
+
+	node := &Node{
+		Hash:       hash,
+		Key:        key,
+		Value:      value,
+		Expiration: time.Now().Add(ttl),
+	}
+
+	node.HashPrev = bucket
+	node.HashNext = node.HashPrev.HashNext
+	node.HashNext.HashPrev = node
+	node.HashPrev.HashNext = node
+
+	s.strategy.OnInsert(node)
+	s.strategy.OnAccess(node)
+
+	s.cost = s.cost + uint64(len(key)) + uint64(len(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) {
+			v.HashNext.HashPrev = v.HashPrev
+			v.HashPrev.HashNext = v.HashNext
+			v.HashNext = nil
+			v.HashPrev = nil
+
+			v.EvictNext.EvictPrev = v.EvictPrev
+			v.EvictPrev.EvictNext = v.EvictNext
+			v.EvictNext = nil
+			v.EvictPrev = nil
+
+			s.cost = s.cost - (uint64(len(v.Key)) + uint64(len(v.Value)))
+			s.lenght = s.lenght - 1
+			return true
+		}
+	}
+
+	return false
+}
+
+func (s *Store) Cost() uint64 {
+	return s.cost
+}
diff --git a/map_test.go b/map_test.go
new file mode 100644
index 0000000..b829fac
--- /dev/null
+++ b/map_test.go
@@ -0,0 +1,157 @@
+package cache
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestStoreGetSet(t *testing.T) {
+	t.Parallel()
+
+	t.Run("Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := &New[any, any]().Store
+		want := []byte("Value")
+		store.Set([]byte("Key"), want, 0)
+		got, _, ok := store.Get([]byte("Key"))
+		assert.Equal(t, want, got)
+		assert.True(t, ok)
+	})
+
+	t.Run("Not Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := &New[any, any]().Store
+		_, _, ok := store.Get([]byte("Key"))
+		assert.False(t, ok)
+	})
+
+	t.Run("Update", func(t *testing.T) {
+		t.Parallel()
+
+		store := &New[any, any]().Store
+		store.Set([]byte("Key"), []byte("Other"), 0)
+		want := []byte("Value")
+		store.Set([]byte("Key"), want, 0)
+		got, _, ok := store.Get([]byte("Key"))
+		assert.Equal(t, want, got)
+		assert.True(t, ok)
+	})
+}
+
+func TestStoreDelete(t *testing.T) {
+	t.Parallel()
+
+	t.Run("Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := &New[any, any]().Store
+		want := []byte("Value")
+		store.Set([]byte("Key"), want, 0)
+		ok := store.Delete([]byte("Key"))
+		assert.True(t, ok)
+		_, _, ok = store.Get([]byte("Key"))
+		assert.False(t, ok)
+	})
+
+	t.Run("Not Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := &New[any, any]().Store
+		ok := store.Delete([]byte("Key"))
+		assert.False(t, ok)
+	})
+}
+
+func TestStoreClear(t *testing.T) {
+	t.Parallel()
+
+	store := &New[any, any]().Store
+	want := []byte("Value")
+	store.Set([]byte("Key"), want, 0)
+	store.Clear()
+	_, _, ok := store.Get([]byte("Key"))
+	assert.False(t, ok)
+}
+
+func TestHashMapGetSet(t *testing.T) {
+	t.Parallel()
+
+	t.Run("Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := New[string, string]()
+		want := "Value"
+		store.Set("Key", want, 0)
+		got, _, err := store.Get("Key")
+		assert.Equal(t, want, got)
+		assert.NoError(t, err)
+	})
+
+	t.Run("Not Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := New[string, string]()
+		_, _, err := store.Get("Key")
+		assert.ErrorIs(t, err, ErrKeyNotFound)
+	})
+
+	t.Run("Update", func(t *testing.T) {
+		t.Parallel()
+
+		store := New[string, string]()
+		store.Set("Key", "Other", 0)
+		want := "Value"
+		store.Set("Key", want, 0)
+		got, _, err := store.Get("Key")
+		assert.Equal(t, want, got)
+		assert.NoError(t, err)
+	})
+}
+
+func TestHashMapDelete(t *testing.T) {
+	t.Parallel()
+
+	t.Run("Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := New[string, string]()
+		want := "Value"
+		store.Set("Key", want, 0)
+		err := store.Delete("Key")
+		assert.NoError(t, err)
+	})
+
+	t.Run("Not Exists", func(t *testing.T) {
+		t.Parallel()
+
+		store := New[string, string]()
+		err := store.Delete("Key")
+		assert.ErrorIs(t, err, ErrKeyNotFound)
+	})
+}
+
+func BenchmarkStoreGet(b *testing.B) {
+	store := &New[any, any]().Store
+	key := []byte("Key")
+	store.Set(key, []byte("Store"), 0)
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			store.Get(key)
+		}
+	})
+}
+
+func BenchmarkStoreSet(b *testing.B) {
+	store := &New[any, any]().Store
+	key := []byte("Key")
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			store.Set(key, []byte("Store"), 0)
+		}
+	})
+}