go-mru/mru.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
}