add cache and start using it in repo

2 files changed, 138 insertions, 0 deletions

diff --git a/cache/cache.go b/cache/cache.go
new file mode 100644
index 0000000..ff2c279
--- /dev/null
+++ b/cache/cache.go
@@ -0,0 +1,58 @@
+package cache
+
+import "sync"
+
+type Cacher interface {
+	Get(key interface{}) (value []byte, exists bool)
+	Set(key interface{}, value []byte)
+	Len() int
+}
+
+type FifoCache struct {
+	head, tail *fifoCacheEntry
+	data       map[interface{}][]byte
+	capacity   int
+	mutex      sync.RWMutex
+}
+
+type fifoCacheEntry struct {
+	Key  interface{}
+	Next *fifoCacheEntry
+}
+
+func NewFifoCache(capacity int) *FifoCache {
+	return &FifoCache{data: make(map[interface{}][]byte, capacity), capacity: capacity}
+}
+
+func (c *FifoCache) Get(key interface{}) (value []byte, exists bool) {
+	c.mutex.RLock()
+	defer c.mutex.RUnlock()
+	value, exists = c.data[key]
+	return
+}
+
+func (c *FifoCache) Set(key interface{}, value []byte) {
+	c.mutex.Lock()
+	defer c.mutex.Unlock()
+	if len(c.data) == c.capacity {
+		// Evict first entry
+		evicted := c.head
+		c.head = evicted.Next
+		delete(c.data, evicted.Key)
+	}
+	entry := &fifoCacheEntry{Key: key}
+	if c.head == nil {
+		c.head = entry
+	}
+	if c.tail == nil {
+		c.tail = entry
+	} else {
+		c.tail.Next = entry
+		c.tail = entry
+	}
+	c.data[key] = value
+}
+
+func (c *FifoCache) Len() int {
+	return len(c.data)
+}
diff --git a/cache/cache_test.go b/cache/cache_test.go
new file mode 100644
index 0000000..6b84b79
--- /dev/null
+++ b/cache/cache_test.go
@@ -0,0 +1,80 @@
+package cache
+
+import (
+	"bytes"
+	"testing"
+)
+
+func TestFifoChunkCache(t *testing.T) {
+	var v []byte
+	var e bool
+	var cache Cacher = NewFifoCache(3)
+	k0 := 0
+	k1 := 1
+	k2 := 2
+	k3 := 3
+	v0 := []byte{'0'}
+	v1 := []byte{'1'}
+	v2 := []byte{'2'}
+	v3 := []byte{'3'}
+
+	if cache.Len() != 0 {
+		t.Fatal("Cache should be of size 0")
+	}
+
+	v, e = cache.Get(k0)
+	if e {
+		t.Fatal("There should not be any value")
+	}
+
+	cache.Set(k0, v0)
+	cache.Set(k1, v1)
+	cache.Set(k2, v2)
+
+	if cache.Len() != 3 {
+		t.Fatal("Cache should be of size 3")
+	}
+
+	v, e = cache.Get(k0)
+	if !e {
+		t.Fatal("Value should exist for k0")
+	}
+	if bytes.Compare(v, v0) != 0 {
+		t.Fatal("Value for k0 does not match")
+	}
+
+	cache.Set(k3, v3)
+
+	if cache.Len() != 3 {
+		t.Fatal("Cache should still be of size 3")
+	}
+
+	v, e = cache.Get(k0)
+	if e {
+		t.Fatal("Value should not exist for k0")
+	}
+
+	v, e = cache.Get(k1)
+	if !e {
+		t.Fatal("Value should exist for k1")
+	}
+	if bytes.Compare(v, v1) != 0 {
+		t.Fatal("Value for k1 does not match")
+	}
+
+	v, e = cache.Get(k2)
+	if !e {
+		t.Fatal("Value should exist for k2")
+	}
+	if bytes.Compare(v, v2) != 0 {
+		t.Fatal("Value for k2 does not match")
+	}
+
+	v, e = cache.Get(k3)
+	if !e {
+		t.Fatal("Value should exist for k3")
+	}
+	if bytes.Compare(v, v3) != 0 {
+		t.Fatal("Value for k3 does not match")
+	}
+}