I am new to golang and I tried to implement various cache replacement algorithms (FIFO, FILO, LRU, MRU, LFU) in a generic or flexible fashion. I added some tests as well. My implementation uses the golang list package, which is a doubly-linked list.
I appreciate any feedback or review. Thank you.
==> cache.go <==
package cache_replacement_golang
import (
"container/list"
"fmt"
)
type Cache struct {
IsEmpty func() bool
Clear func()
Get func(key string) (interface{}, error)
Add func(key string, value interface{})
}
type Ctx struct {
List *list.List
Limit int
}
type Environment struct {
*Ctx
*Spec
}
func (ctx Ctx) clear() {
ctx.List = list.New()
}
func (ctx Ctx) isEmpty() bool {
return ctx.List.Len() == 0
}
type Node interface {
Key() string
Value() interface{}
}
type NodeImpl struct {
key string
value interface{}
}
func (node *NodeImpl) Key() string {
return node.key
}
func (node *NodeImpl) Value() interface{} {
return node.value
}
type Spec struct {
Wrap func(key string, value interface{}) Node
Evict func(ctx *Ctx)
Found func(ctx *Ctx, item *list.Element)
}
func (env *Environment) get(key string) (interface{}, error) {
if env.List.Len() == 0 {
return nil, fmt.Errorf("cache miss '%s': cache is empty", key)
}
var currentUntyped = env.List.Front()
for currentUntyped != nil {
current := currentUntyped.Value.(Node)
if current.Key() == key {
value := current.Value()
env.Spec.Found(env.Ctx, currentUntyped)
return value, nil
}
currentUntyped = currentUntyped.Next()
}
return nil, fmt.Errorf("cache miss '%s': unable to find a match", key)
}
func (env *Environment) add(key string, value interface{}) {
var currentUntyped = env.List.Front()
for currentUntyped != nil {
current := currentUntyped.Value.(Node)
if current.Key() == key {
// Nodes are immutable, just remove the node and add it back
env.List.Remove(currentUntyped)
}
currentUntyped = currentUntyped.Next()
}
if env.List.Len()+1 > env.Limit {
env.Spec.Evict(env.Ctx)
}
env.List.PushFront(env.Spec.Wrap(key, value))
}
func Build(spec Spec) func(int) Cache {
return func(limit int) Cache {
ctx := Ctx{Limit: limit, List: list.New()}
env := Environment{Ctx: &ctx, Spec: &spec}
return Cache{
IsEmpty: func() bool {
return env.isEmpty()
},
Clear: func() {
env.clear()
},
Get: func(key string) (interface{}, error) {
return env.get(key)
},
Add: func(key string, value interface{}) {
env.add(key, value)
},
}
}
}
==> cache_test.go <==
package cache_replacement_golang
import (
"strconv"
"testing"
)
func validate(t *testing.T, key string, err error, expected interface{}, actual interface{}) {
if err != nil {
t.Errorf("Failed to find cached value %s", key)
} else if expected != actual {
t.Errorf("Mismatch value for a key %s", key)
}
}
func CacheGenericTesting(t *testing.T, makeCache func(int) Cache) {
size := 256
cache := makeCache(size)
// Test add and immediate get
for i := 0; i < size; i++ {
key := strconv.Itoa(i)
cache.Add(key, i)
value, err := cache.Get(key)
validate(t, key, err, i, value)
}
// Test get afterward
for i := 0; i < size; i++ {
key := strconv.Itoa(i)
value, err := cache.Get(key)
validate(t, key, err, i, value)
}
// Test update
for i := 0; i < size; i++ {
key := strconv.Itoa(i)
cache.Add(key, i+i)
value, err := cache.Get(key)
validate(t, key, err, i+i, value)
}
}
func TestFIFO(t *testing.T) {
CacheGenericTesting(t, FIFO())
}
func TestFILO(t *testing.T) {
CacheGenericTesting(t, FILO())
}
func TestLRU(t *testing.T) {
CacheGenericTesting(t, LRU())
}
func TestMRU(t *testing.T) {
CacheGenericTesting(t, MRU())
}
func TestLFU(t *testing.T) {
CacheGenericTesting(t, LFU())
}
==> fifo.go <==
package cache_replacement_golang
import "container/list"
func FIFO() func(int) Cache {
return Build(Spec{
Wrap: func(key string, value interface{}) Node {
return &NodeImpl{key, value}
},
Evict: func(ctx *Ctx) {
ctx.List.Remove(ctx.List.Back())
},
Found: func(ctx *Ctx, item *list.Element) {
},
})
}
==> filo.go <==
package cache_replacement_golang
import "container/list"
func FILO() func(int) Cache {
return Build(Spec{
Wrap: func(key string, value interface{}) Node {
return &NodeImpl{key: key, value: value}
},
Evict: func(ctx *Ctx) {
ctx.List.Remove(ctx.List.Front())
},
Found: func(ctx *Ctx, item *list.Element) {
},
})
}
==> lfu.go <==
package cache_replacement_golang
import (
"container/list"
"math"
)
type NodeCounted struct {
key string
value interface{}
frequency int
}
func (node *NodeCounted) Key() string {
return node.key
}
func (node *NodeCounted) Value() interface{} {
return node.value
}
func (node *NodeCounted) Frequency() int {
return node.frequency
}
func LFU() func(int) Cache {
return Build(Spec{
Wrap: func(key string, value interface{}) Node {
return &NodeCounted{key: key, value: value, frequency: 0}
},
Evict: func(ctx *Ctx) {
currentFrequency := math.MaxInt
var element *list.Element = nil
var currentUntyped = ctx.List.Front()
for currentUntyped != nil {
current := currentUntyped.Value.(NodeCounted)
if current.frequency <= currentFrequency {
element = currentUntyped
currentFrequency = current.frequency
}
currentUntyped = currentUntyped.Next()
}
ctx.List.Remove(element)
},
Found: func(ctx *Ctx, item *list.Element) {
node := item.Value.(*NodeCounted)
node.frequency++
},
})
}
==> lru.go <==
package cache_replacement_golang
import "container/list"
func LRU() func(int) Cache {
return Build(Spec{
Wrap: func(key string, value interface{}) Node {
return &NodeImpl{key: key, value: value}
},
Evict: func(ctx *Ctx) {
ctx.List.Remove(ctx.List.Back())
},
Found: func(ctx *Ctx, item *list.Element) {
ctx.List.MoveBefore(item, ctx.List.Front())
},
})
}
==> mru.go <==
package cache_replacement_golang
import "container/list"
func MRU() func(int) Cache {
return Build(Spec{
Wrap: func(key string, value interface{}) Node {
return &NodeImpl{key: key, value: value}
},
Evict: func(ctx *Ctx) {
ctx.List.Remove(ctx.List.Front())
},
Found: func(ctx *Ctx, item *list.Element) {
ctx.List.MoveBefore(item, ctx.List.Front())
},
})
}
