129 lines
2.2 KiB
Go
129 lines
2.2 KiB
Go
package mru
|
|
|
|
import (
|
|
"errors"
|
|
"fmt"
|
|
"sort"
|
|
|
|
"github.com/benbjohnson/clock"
|
|
)
|
|
|
|
type Item struct {
|
|
V interface{}
|
|
access int64
|
|
}
|
|
|
|
type Cache struct {
|
|
store map[string]*Item
|
|
access *timestamps
|
|
cap int
|
|
clock clock.Clock
|
|
}
|
|
|
|
func New(cap int) *Cache {
|
|
return &Cache{
|
|
store: map[string]*Item{},
|
|
access: newTimestamps(cap),
|
|
cap: cap,
|
|
clock: clock.New(),
|
|
}
|
|
}
|
|
|
|
func (c *Cache) Len() int {
|
|
return len(c.store)
|
|
}
|
|
|
|
// evict should remove the least-recently-used cache item.
|
|
func (c *Cache) evict() {
|
|
k := c.access.K(0)
|
|
c.evictKey(k)
|
|
}
|
|
|
|
// evictKey should remove the entry given by the key item.
|
|
func (c *Cache) evictKey(k string) {
|
|
delete(c.store, k)
|
|
i, ok := c.access.Find(k)
|
|
if !ok {
|
|
return
|
|
}
|
|
|
|
c.access.Delete(i)
|
|
}
|
|
|
|
func (c *Cache) sanityCheck() {
|
|
if len(c.store) != c.access.Len() {
|
|
panic(fmt.Sprintf("MRU cache is out of sync; store len = %d, access len = %d",
|
|
len(c.store), c.access.Len()))
|
|
}
|
|
}
|
|
|
|
func (c *Cache) ConsistencyCheck() error {
|
|
if err := c.access.ConsistencyCheck(); err != nil {
|
|
return err
|
|
}
|
|
|
|
if len(c.store) != c.access.Len() {
|
|
return fmt.Errorf("mru: cache is out of sync; store len = %d, access len = %d",
|
|
len(c.store), c.access.Len())
|
|
}
|
|
|
|
for i := range c.access.ts {
|
|
itm, ok := c.store[c.access.K(i)]
|
|
if !ok {
|
|
return errors.New("mru: key in access is not in store")
|
|
}
|
|
|
|
if c.access.T(i) != itm.access {
|
|
return fmt.Errorf("timestamps are out of sync (%d != %d)",
|
|
itm.access, c.access.T(i))
|
|
}
|
|
}
|
|
|
|
if !sort.IsSorted(c.access) {
|
|
return errors.New("mru: timestamps aren't sorted")
|
|
}
|
|
|
|
return nil
|
|
}
|
|
|
|
func (c *Cache) Store(k string, v interface{}) {
|
|
c.sanityCheck()
|
|
|
|
if len(c.store) == c.cap {
|
|
c.evict()
|
|
}
|
|
|
|
if _, ok := c.store[k]; ok {
|
|
c.evictKey(k)
|
|
}
|
|
|
|
itm := &Item{
|
|
V: v,
|
|
access: c.clock.Now().UnixNano(),
|
|
}
|
|
|
|
c.store[k] = itm
|
|
c.access.Update(k, itm.access)
|
|
}
|
|
|
|
func (c *Cache) Get(k string) (interface{}, bool) {
|
|
c.sanityCheck()
|
|
|
|
itm, ok := c.store[k]
|
|
if !ok {
|
|
return nil, false
|
|
}
|
|
|
|
c.store[k].access = c.clock.Now().UnixNano()
|
|
c.access.Update(k, itm.access)
|
|
return itm.V, true
|
|
}
|
|
|
|
// Has will not update the timestamp on the item.
|
|
func (c *Cache) Has(k string) bool {
|
|
c.sanityCheck()
|
|
|
|
_, ok := c.store[k]
|
|
return ok
|
|
}
|