Simple LRU

lru.go

package main

import (
	"fmt"
	"sync"
)

type item struct {
	next     *item
	previous *item
	k        interface{}
	v        interface{}
}

type LRU interface {
	Get(k interface{}) interface{}
	Put(k, v interface{})
	Print()
}

func newLRU(size int) LRU {
	return &defaultLRU{
		lock:   &sync.Mutex{},
		size:   size,
		direct: map[interface{}]*item{},
	}
}

type defaultLRU struct {
	lock   *sync.Mutex
	size   int
	count  int
	head   *item
	tail   *item
	direct map[interface{}]*item
}

func (d *defaultLRU) Print() {
	fmt.Println(fmt.Sprintf("total item %d", d.count))
	nextItem := d.head
	for {
		fmt.Println(fmt.Sprintf("%v = %v", nextItem.k, nextItem.v))
		if nextItem.next != nil {
			nextItem = nextItem.next
		} else {
			break
		}
	}
}

func (d *defaultLRU) Get(k interface{}) interface{} {
	d.lock.Lock()
	defer d.lock.Unlock()
	existing := d.direct[k]
	if existing == nil {
		return nil
	}
	d.setHead(existing)
	return existing.v
}

func (d *defaultLRU) setHead(headItem *item) {
	if d.head == headItem {
		fmt.Println("NOT updating head from", d.head, "to", headItem)
		return
	}
	if headItem.next != nil {
		headItem.next.previous = headItem.previous
	}
	if headItem.previous != nil {
		headItem.previous.next = headItem.next
	}
	currentHead := d.head
	currentHead.previous = headItem
	fmt.Println("updating head from", currentHead, "to", headItem, "with ")
	headItem.next = currentHead
	headItem.previous = nil
	d.head = headItem
}

func (d *defaultLRU) Put(k, v interface{}) {
	d.lock.Lock()
	defer d.lock.Unlock()
	existing := d.direct[k]
	if existing == nil {
		newItem := &item{k: k, v: v}
		if d.head == nil {
			d.head = newItem
			d.tail = newItem
			d.count = 1
			d.direct[k] = newItem
			return
		}
		d.count = d.count + 1
		d.direct[k] = newItem
		d.setHead(newItem)
		d.evict()
		return
	}
	if existing != nil {
		existing.v = v
		d.setHead(existing)
	}
}

func (d *defaultLRU) evict() {
	if d.count > d.size {
		tailItem := d.tail
		fmt.Println("removing tail", tailItem)
		delete(d.direct, tailItem.k)
		tailItem.previous.next = nil
		d.tail = tailItem.previous
		d.count = d.count - 1
	}
}

func main() {
	inst := newLRU(3)
	inst.Put("a", 1)
	inst.Put("b", 2)
	inst.Put("c", 3)
	fmt.Println(" ====> ", inst.Get("b"))
	inst.Put("b", 4)
	inst.Print()
	fmt.Println(" ====> ", inst.Get("b"))
	inst.Put("b", 5)
	inst.Print()
	fmt.Println(" ====> ", inst.Get("b"))
}