Prototype of a LRU Cache for string key/value pairs in Go.

LRUCache.go

package main

import (
	"fmt"
)

// LRUCache is the LRU string cache.
type LRUCache struct {
	table   map[string]entry
	queue   lruQueue
	maxSize int
}

type entry struct {
	value    string
	queueRef *queueElem
}

type lruQueue struct {
	head, tail *queueElem
}

type queueElem struct {
	key        string
	next, prev *queueElem
}

// NewLRUCache returns a new empty LRU cache with
// the specified maximum number of entries.
func NewLRUCache(maxSize int) *LRUCache {
	return &LRUCache{
		table:   make(map[string]entry, maxSize),
		maxSize: maxSize,
	}
}

// Insert inserts a new key/value string pair
// in the cache. If the cache is full
// this method deletes the oldest entry.
func (l *LRUCache) Insert(key, value string) {
	if len(l.table) == l.maxSize {
		l.removeOldest()
	}
	ref := l.pushQueue(key)
	l.table[key] = entry{
		value:    value,
		queueRef: ref,
	}
}

// Get returns the value associated to the input key.
func (l *LRUCache) Get(key string) (string, error) {
	if entry, ok := l.table[key]; ok {
		l.updateQueue(key)
		return entry.value, nil
	}
	return "", fmt.Errorf("key '%s' not found", key)
}

func (l *LRUCache) removeOldest() {
	qElem := l.queue.pop()
	delete(l.table, qElem.key)
}

func (l *LRUCache) pushQueue(key string) *queueElem {
	qElem := &queueElem{
		key: key,
	}
	l.queue.push(qElem)
	return qElem
}

func (l *LRUCache) updateQueue(key string) {
	entry := l.table[key]
	qElem := entry.queueRef
	l.queue.delete(qElem)
	qElem.prev = nil
	qElem.next = nil
	l.queue.push(qElem)
}

func (q *lruQueue) push(qElem *queueElem) {
	if q.tail != nil {
		q.tail.next = qElem
		qElem.prev = q.tail
	}
	q.tail = qElem
	if q.head == nil {
		q.head = qElem
	}
}

func (q *lruQueue) pop() *queueElem {
	if q.head == nil {
		return nil
	}
	qElem := q.head
	q.head = qElem.next
	if q.head != nil {
		q.head.prev = nil
	} else {
		q.tail = nil
	}
	return qElem
}

func (q *lruQueue) delete(qElem *queueElem) {
	if qElem.prev == nil {
		q.pop()
	} else if qElem.next == nil {
		q.tail = qElem.prev
		q.tail.next = nil
	} else {
		qElem.prev.next = qElem.next
		qElem.next.prev = qElem.prev
	}
}

func (l *LRUCache) Print() {
	for k, v := range l.table {
		fmt.Printf("%v -> %+v\n", k, v)
	}
}

func main() {
	lru := NewLRUCache(3)
	lru.Print()
	lru.Insert("key1", "value1")
	lru.Insert("key2", "value2")
	lru.Insert("key3", "value3")
	lru.Print()
	lru.Insert("key4", "value4")
	lru.Print()
	fmt.Println(lru.Get("key2"))
	lru.Insert("key5", "value5")
	lru.Print()
}