LRU cache example (non-concurrent)

lru.go

package main

import "time"

type entry struct {
	key                    string
	data                   []byte
	expiration             time.Time
	lessRecent, moreRecent *entry
}

type Cache struct {
	maxSize, available int
	lookup             map[string]*entry
	lru, mru           *entry
}

func (e *entry) size() int {
	return len(e.key) + len(e.data)
}

func New(maxSize int) *Cache {
	return &Cache{
		maxSize:   maxSize,
		available: maxSize,
		lookup:    make(map[string]*entry),
	}
}

func (c *Cache) remove(key string) *entry {
	e, ok := c.lookup[key]
	if !ok {
		return nil
	}

	c.available += e.size()
	delete(c.lookup, key)

	if c.lru == e {
		c.lru = e.moreRecent
	} else {
		e.lessRecent.moreRecent = e.moreRecent
	}

	if c.mru == e {
		c.mru = e.lessRecent
	}

	return e
}

func (c *Cache) append(e *entry) {
	s := e.size()
	c.available -= s
	for c.available < 0 {
		c.Del(c.lru.key)
	}

	c.lookup[e.key] = e

	e.moreRecent = nil
	if c.lru == nil {
		c.lru, c.mru, e.lessRecent = e, e, nil
	} else {
		c.mru.moreRecent, c.mru, e.lessRecent = e, e, c.mru
	}
}

func (c *Cache) Get(key string) ([]byte, bool) {
	e := c.remove(key)
	if e == nil {
		return nil, false
	}

	if e.expiration.Before(time.Now()) {
		return nil, false
	}

	c.append(e)
	return e.data, true
}

func (c *Cache) Set(key string, data []byte, ttl time.Duration) {
	e := c.remove(key)
	if e == nil {
		e = &entry{key: key}
	}

	e.data = data
	if e.size() > c.maxSize {
		return
	}

	e.expiration = time.Now().Add(ttl)
	c.append(e)
}

func (c *Cache) Del(key string) {
	c.remove(key)
}

func (c *Cache) Size() int {
	return c.maxSize - c.available
}

func (c *Cache) Len() int {
	return len(c.lookup)
}

func main() {
	c := New(16)

	c.Set("foo", []byte{1, 2, 3}, time.Second)
	if _, ok := c.Get("foo"); !ok {
		println("fail")
	}

	c.Set("foo", []byte{4, 5, 6}, time.Second)
	if _, ok := c.Get("foo"); !ok {
		println("fail")
	}

	c.Set("bar", []byte{7, 8, 9}, time.Second)
	if _, ok := c.Get("foo"); !ok {
		println("fail")
	}
	if _, ok := c.Get("bar"); !ok {
		println("fail")
	}

	c.Del("foo")
	if _, ok := c.Get("foo"); ok {
		println("fail")
	}
	if _, ok := c.Get("bar"); !ok {
		println("fail")
	}

	c.Set("foo", []byte{1, 2, 3}, time.Second)
	c.Set("bar", []byte{4, 5, 6}, 3*time.Second)
	time.Sleep(2 * time.Second)
	if _, ok := c.Get("foo"); ok {
		println("fail")
	}
	if _, ok := c.Get("bar"); !ok {
		println("fail")
	}

	c.Set("foo", []byte{1, 2, 3}, 2*time.Second)
	c.Set("bar", []byte{4, 5, 6}, 4*time.Second)
	time.Sleep(time.Second)
	c.Get("foo")
	c.Set("baz", []byte{7, 8, 9}, time.Second)
	if _, ok := c.Get("foo"); !ok {
		println("fail")
	}
	if _, ok := c.Get("bar"); ok {
		println("fail")
	}
	if _, ok := c.Get("baz"); !ok {
		println("fail")
	}
}