From 0b6df1549e53ca4747b070043ebc4a41c5a5f47c Mon Sep 17 00:00:00 2001 From: Marc Pervaz Boocha Date: Fri, 14 Feb 2025 18:06:02 +0530 Subject: First Commit --- conn.go | 138 ++++++++++++++++++++++++++++++++++++++++++ encoding.go | 194 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ evict.go | 132 +++++++++++++++++++++++++++++++++++++++++ go.mod | 17 ++++++ go.sum | 45 ++++++++++++++ map.go | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ map_test.go | 157 ++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 875 insertions(+) create mode 100644 conn.go create mode 100644 encoding.go create mode 100644 evict.go create mode 100644 go.mod create mode 100644 go.sum create mode 100644 map.go create mode 100644 map_test.go 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) + } + }) +} -- cgit v1.2.3-70-g09d2