2
\$\begingroup\$

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())
        },
    })
}

Repository

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.