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\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.