Repository: NethermindEth/juno
Pull request #282 (2022-07-14 03:18:50)

Add missing lru functionality, behaviour tests and refactor


## Changes:
- A pointer to RWMutex is used so that when LRUCache is passed the mutex
doesn't cause a panic, since mutexes cannot be copied. Also, by using
RWMutex we allow read operations to be executed concurrently, while only
write operations are protected.

- Move LRUCache into its own package and rename the LRUCache struct to
Cache.

- Rename start and end cacheNodes to front and back, respectively.

- Add behaviour tests to assert lru behaviour.

- Cache of capacity less than 1 cannot be created.

- If a user calls put with a node whose key already exists in the cache
but the value is different then the existing node in the cache be
deleted and replaced with the new node. This will not change the size of
the cache

## Types of changes

What types of changes does your code introduce?
_Put an `x` in the boxes that apply_

- [x] Bugfix (non-breaking change which fixes an issue)
- [ ] New feature (non-breaking change which adds functionality)
- [ ] Breaking change (fix or feature that would cause existing functionality to not work as expected)
- [ ] Documentation Update
- [x] Code style update (formatting, renaming)
- [x] Refactoring (no functional changes, no api changes)
- [ ] Build related changes
- [ ] Other (please describe): 

## Testing
**Requires testing**

- [x] Yes
- [ ] No

**In case you checked yes, did you write tests??**

- [x] Yes
- [ ] No

codecov[bot]: # [Codecov](https://codecov.io/gh/NethermindEth/juno/pull/282?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) Report
> Merging [#282](https://codecov.io/gh/NethermindEth/juno/pull/282?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) (3f26bf9) into [main](https://codecov.io/gh/NethermindEth/juno/commit/a5adfc3b7e08ce1cd63702d73fe623925289046c?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) (a5adfc3) will **not change** coverage.
> The diff coverage is `100.00%`.

```diff
@@            Coverage Diff            @@
##              main      #282   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files           66        66           
  Lines         6026      6067   +41     
=========================================
+ Hits          6026      6067   +41     
```

| Flag | Coverage Δ | |
|---|---|---|
| unittests | `100.00% <100.00%> (ø)` | |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/NethermindEth/juno/pull/282?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) | Coverage Δ | |
|---|---|---|
| [internal/cache/lru/lru.go](https://codecov.io/gh/NethermindEth/juno/pull/282/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-aW50ZXJuYWwvY2FjaGUvbHJ1L2xydS5nbw==) | `100.00% <100.00%> (ø)` | |
| [pkg/rpc/server.go](https://codecov.io/gh/NethermindEth/juno/pull/282/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-cGtnL3JwYy9zZXJ2ZXIuZ28=) | `100.00% <0.00%> (ø)` | |
| [pkg/crypto/weierstrass/weierstrass.go](https://codecov.io/gh/NethermindEth/juno/pull/282/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-cGtnL2NyeXB0by93ZWllcnN0cmFzcy93ZWllcnN0cmFzcy5nbw==) | `100.00% <0.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/NethermindEth/juno/pull/282?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/NethermindEth/juno/pull/282?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth). Last update [a5adfc3...3f26bf9](https://codecov.io/gh/NethermindEth/juno/pull/282?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth).


Patch:
diff --git a/internal/cache/lru.go b/internal/cache/lru.go
deleted file mode 100644
index 58135947..00000000
--- a/internal/cache/lru.go
+++ /dev/null
@@ -1,135 +0,0 @@
-package cache
-
-import (
-	"hash/maphash"
-	"sync"
-)
-
-type cacheNode struct {
-	key   uint64
-	value []byte
-	next  *cacheNode
-	prev  *cacheNode
-}
-
-// LRUCache is a cache with the least-recently-used policy.
-type LRUCache struct {
-	// hashMap contaiins the current cache contents that can be accessed by the key
-	hashMap map[uint64]*cacheNode
-	// start is a reference to the first node in the cache queue
-	start *cacheNode
-	// end is a reference to the last node in the cache queue
-	end *cacheNode
-	// count is the current ammount of items in the cache
-	count int
-	// capacity is the max ammount of items that can be stored in the cache
-	capacity int
-	// hash is used to hash the key
-	hash maphash.Hash
-	// lock is used to protect the cache from concurrent access
-	lock sync.RWMutex
-}
-
-// NewLRUCache creates a new LRUCache instance with the given capacity.
-func NewLRUCache(capacity int) *LRUCache {
-	return &LRUCache{
-		hashMap:  make(map[uint64]*cacheNode, capacity),
-		capacity: capacity,
-		hash:     maphash.Hash{},
-	}
-}
-
-// Put adds a new key-value pair to the cache. If the cache is full then
-// the least-recently-used key-value pair is removed.
-func (c *LRUCache) Put(k []byte, v []byte) {
-	c.lock.Lock()
-	defer c.lock.Unlock()
-
-	// Build the cache key and node
-	key := c.key(k)
-	node := &cacheNode{key: key, value: v}
-
-	// Cache is empty
-	if c.count == 0 {
-		c.hashMap[key] = node
-		c.start = node
-		c.end = node
-		c.count = 1
-		return
-	}
-
-	// Put the new node at the start of the queue
-	c.hashMap[key] = node
-	c.start.prev = node
-	node.next = c.start
-	c.start = node
-	c.count++
-
-	// Remove the last node if the cache is full
-	if c.count > c.capacity {
-		delete(c.hashMap, c.end.key)
-		c.end = c.end.prev
-		c.end.next.prev = nil
-		c.end.next = nil
-		c.count--
-	}
-}
-
-// Get returns the value for the given key. If the key is not found then
-// returns nil.
-func (c *LRUCache) Get(k []byte) []byte {
-	c.lock.Lock()
-	defer c.lock.Unlock()
-
-	key := c.key(k)
-	if node, ok := c.hashMap[key]; ok {
-		if node != c.start {
-			// Move the node to the start of the queue
-			node.prev.next = node.next
-			if node == c.end {
-				c.end = node.prev
-			} else {
-				node.next.prev = node.prev
-			}
-			c.start.prev = node
-			node.next = c.start
-			node.prev = nil
-			c.start = node
-		}
-		return node.value
-	}
-	return nil
-}
-
-// Len returns the current ammount of items in the cache.
-func (c *LRUCache) Len() int {
-	c.lock.RLock()
-	defer c.lock.RUnlock()
-
-	return c.count
-}
-
-// Cap returns the max ammount of items that can be stored in the cache.
-func (c *LRUCache) Cap() int {
-	c.lock.RLock()
-	defer c.lock.RUnlock()
-
-	return c.capacity
-}
-
-// Clear removes all items from the cache.
-func (c *LRUCache) Clear() {
-	c.lock.Lock()
-	defer c.lock.Unlock()
-
-	c.hashMap = make(map[uint64]*cacheNode, c.capacity)
-	c.start = nil
-	c.end = nil
-	c.count = 0
-}
-
-func (c *LRUCache) key(v []byte) uint64 {
-	c.hash.Reset()
-	c.hash.Write(v)
-	return c.hash.Sum64()
-}
diff --git a/internal/cache/lru/lru.go b/internal/cache/lru/lru.go
new file mode 100644
index 00000000..27346604
--- /dev/null
+++ b/internal/cache/lru/lru.go
@@ -0,0 +1,193 @@
+package lru
+
+import (
+	"hash/maphash"
+	"sync"
+)
+
+type cacheNode struct {
+	key   uint64
+	value []byte
+	next  *cacheNode
+	prev  *cacheNode
+}
+
+// Cache is a cache with the least-recently-used policy.
+type Cache struct {
+	*sync.RWMutex
+
+	// hashMap contaiins the current cache contents that can be accessed by the key
+	hashMap map[uint64]*cacheNode
+	// front is a reference to the first node in the cache queue
+	front *cacheNode
+	// back is a reference to the last node in the cache queue
+	back *cacheNode
+	// len is the current amount of items in the cache
+	len int
+	// cap is the max amount of items that can be stored in the cache
+	cap int
+	// hash is used to hash the key
+	hash maphash.Hash
+}
+
+// NewCache creates a new Cache instance with the given cap. If cap == 0, nil is
+// returned.
+func NewCache(cap int) *Cache {
+	if cap < 1 {
+		return nil
+	}
+	return &Cache{
+		RWMutex: new(sync.RWMutex),
+		hashMap: make(map[uint64]*cacheNode, cap),
+		cap:     cap,
+		hash:    maphash.Hash{},
+	}
+}
+
+// Put adds a new key-value pair to the cache. If the cache is full then
+// the least-recently-used key-value pair is removed. If the key already exist
+// in the cache then the node will be replaced and put at the front of the
+// cache.
+func (c *Cache) Put(k []byte, v []byte) {
+	c.Lock()
+	defer c.Unlock()
+
+	key := c.key(k)
+	newN := &cacheNode{key: key, value: v}
+
+	if c.len == 0 {
+		c.hashMap[key] = newN
+		c.front = newN
+		c.back = newN
+		c.len++
+		return
+	}
+
+	node, ok := c.hashMap[key]
+
+	// key doesn't already exist in cache so add the node to the front and
+	// delete the last node if cache is full
+	if !ok {
+		c.hashMap[key] = newN
+		c.front.prev = newN
+		newN.next = c.front
+		c.front = newN
+		c.len++
+
+		if c.len > c.cap {
+			delete(c.hashMap, c.back.key)
+			c.back = c.back.prev
+			c.back.next.prev = nil
+			c.back.next = nil
+			c.len--
+		}
+		return
+	}
+
+	// key already exists in the cache so replace the map reference, delete the
+	// old node from the cache and add the new node to the front of the cache.
+	c.hashMap[key] = newN
+	if node == c.front {
+		newN.next = c.front.next
+		c.front.next.prev = newN
+		c.front = newN
+		node.next = nil
+		return
+	} else if node == c.back {
+		c.back = node.prev
+		node.prev = nil
+	} else {
+		node.prev.next = node.next
+		node.next.prev = node.prev
+		node.next = nil
+		node.prev = nil
+	}
+	c.front.prev = newN
+	newN.next = c.front
+	c.front = newN
+}
+
+// Get returns the value for the given key. If the key is not found then
+// returns nil.
+func (c *Cache) Get(k []byte) []byte {
+	c.Lock()
+	defer c.Unlock()
+
+	key := c.key(k)
+	if node, ok := c.hashMap[key]; ok {
+		if node != c.front {
+			// Move the node to the front of the queue
+			node.prev.next = node.next
+			if node == c.back {
+				c.back = node.prev
+			} else {
+				node.next.prev = node.prev
+			}
+			c.front.prev = node
+			node.next = c.front
+			node.prev = nil
+			c.front = node
+		}
+		v := make([]byte, len(node.value))
+		copy(v, node.value)
+		return v
+	}
+	return nil
+}
+
+// Front returns a copy of the value at front of the cache
+func (c Cache) Front() []byte {
+	c.RLock()
+	defer c.RUnlock()
+
+	if c.front != nil {
+		v := make([]byte, len(c.front.value))
+		copy(v, c.front.value)
+		return v
+	}
+	return nil
+}
+
+// Back returns a copy of value at the back of the cache
+func (c Cache) Back() []byte {
+	c.RLock()
+	defer c.RUnlock()
+
+	if c.back != nil {
+		v := make([]byte, len(c.back.value))
+		copy(v, c.back.value)
+		return v
+	}
+	return nil
+}
+
+// Len returns the current amount of items in the cache.
+func (c *Cache) Len() int {
+	c.RLock()
+	defer c.RUnlock()
+	return c.len
+}
+
+// Cap returns the max amount of items that can be stored in the cache.
+func (c *Cache) Cap() int {
+	c.RLock()
+	defer c.RUnlock()
+	return c.cap
+}
+
+// Clear removes all items from the cache.
+func (c *Cache) Clear() {
+	c.Lock()
+	defer c.Unlock()
+
+	c.hashMap = make(map[uint64]*cacheNode, c.cap)
+	c.front = nil
+	c.back = nil
+	c.len = 0
+}
+
+func (c *Cache) key(v []byte) uint64 {
+	c.hash.Reset()
+	c.hash.Write(v)
+	return c.hash.Sum64()
+}


Test patch:
diff --git a/internal/cache/lru/lru_test.go b/internal/cache/lru/lru_test.go
new file mode 100644
index 00000000..2b4565c5
--- /dev/null
+++ b/internal/cache/lru/lru_test.go
@@ -0,0 +1,281 @@
+package lru
+
+import (
+	"bytes"
+	"fmt"
+	"testing"
+)
+
+func TestNewCache(t *testing.T) {
+	tc := []int{1, 5, 10, 100, 500, 1000, 5000, 10000}
+
+	t.Run("cannot create lru cache with cap=0", func(t *testing.T) {
+		c := NewCache(0)
+		if c != nil {
+			t.Fatalf("expected c to be nil but go \"%v\"", c)
+		}
+	})
+
+	for _, i := range tc {
+		t.Run(fmt.Sprintf("create cache with cap=%d", i), func(t *testing.T) {
+			c := NewCache(i)
+			if c == nil {
+				t.Error("did not expect cache to be nil")
+			}
+			if c.Cap() != i || c.Len() != 0 {
+				t.Fatalf("expected cap: \"%d\" and len: \"%d\" but got cap: \"%d\" and len: \"%d\"", i, 0, c.Cap(), c.Len())
+			}
+		})
+	}
+}
+
+func TestCache_Put(t *testing.T) {
+	t.Run("single key value pair in empty cache", func(t *testing.T) {
+		wantCap, wantLen := 5, 1
+		k, v := keyValuePair(1)
+		c := NewCache(wantCap)
+		c.Put(k, v)
+		checkCache(t, c, wantCap, wantLen, v, v)
+	})
+	t.Run("multiple distinct key value pairs in empty cache", func(t *testing.T) {
+		wantCap := 5
+		var b []byte
+		c := NewCache(wantCap)
+
+		for i := 0; i < wantCap; i++ {
+			wantLen := i + 1
+			k, v := keyValuePair(i)
+			if i == 0 {
+				b = v
+			}
+			c.Put(k, v)
+			checkCache(t, c, wantCap, wantLen, v, b)
+		}
+	})
+	t.Run("multiple distinct key value pairs in full cache", func(t *testing.T) {
+		wantCap := 5
+		c := createFullCache(wantCap)
+
+		for i := 0; i < wantCap; i++ {
+			j := i + wantCap
+			k, v := keyValuePair(j)
+			c.Put(k, v)
+
+			_, wantV := keyValuePair(i + 1)
+			deletedK, _ := keyValuePair(i)
+
+			checkCache(t, c, wantCap, wantCap, v, wantV)
+			if v := c.Get(deletedK); v != nil {
+				t.Errorf("expected value to be nil, got %s", v)
+			}
+		}
+	})
+	t.Run("node with same key but different value at the front of the full cache", func(t *testing.T) {
+		wantCap := 5
+		c := createFullCache(wantCap)
+
+		k, _ := keyValuePair(4)
+		_, wantV := keyValuePair(5)
+		_, wantB := keyValuePair(0)
+		c.Put(k, wantV)
+
+		checkCache(t, c, wantCap, wantCap, wantV, wantB)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+	})
+	t.Run("node with same key but different value at the back of the full cache", func(t *testing.T) {
+		wantCap := 5
+		c := createFullCache(wantCap)
+
+		k, _ := keyValuePair(0)
+		_, wantV := keyValuePair(5)
+		_, wantB := keyValuePair(1)
+		c.Put(k, wantV)
+
+		checkCache(t, c, wantCap, wantCap, wantV, wantB)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+	})
+	t.Run("node with same key but different value in the middle of the full cache", func(t *testing.T) {
+		wantCap := 5
+		c := createFullCache(wantCap)
+
+		k, _ := keyValuePair(3)
+		_, wantV := keyValuePair(5)
+		_, wantB := keyValuePair(0)
+		c.Put(k, wantV)
+
+		checkCache(t, c, wantCap, wantCap, wantV, wantB)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+	})
+	t.Run("node with same key but different value at the front of the sparse cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 5
+		c := createSparseCache(wantCap, wantLen)
+
+		k, _ := keyValuePair(4)
+		_, wantV := keyValuePair(5)
+		_, wantB := keyValuePair(0)
+		c.Put(k, wantV)
+
+		checkCache(t, c, wantCap, wantLen, wantV, wantB)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+	})
+	t.Run("node with same key but different value at the back of the sparse cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 5
+		c := createSparseCache(wantCap, wantLen)
+
+		k, _ := keyValuePair(0)
+		_, wantV := keyValuePair(5)
+		_, wantB := keyValuePair(1)
+		c.Put(k, wantV)
+
+		checkCache(t, c, wantCap, wantLen, wantV, wantB)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+	})
+	t.Run("node with same key but different value in the middle of the sparse cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 5
+		c := createSparseCache(wantCap, wantLen)
+
+		k, _ := keyValuePair(3)
+		_, wantV := keyValuePair(5)
+		_, wantB := keyValuePair(0)
+		c.Put(k, wantV)
+
+		checkCache(t, c, wantCap, wantLen, wantV, wantB)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+	})
+}
+
+func TestCache_Get(t *testing.T) {
+	t.Run("value from front of a cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 8
+		c := createSparseCache(wantCap, wantLen)
+
+		k, wantV := keyValuePair(7)
+		_, wantB := keyValuePair(0)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+		checkCache(t, c, wantCap, wantLen, wantV, wantB)
+	})
+	t.Run("value from back of a cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 8
+		c := createSparseCache(wantCap, wantLen)
+
+		k, wantV := keyValuePair(0)
+		_, wantB := keyValuePair(1)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+		checkCache(t, c, wantCap, wantLen, wantV, wantB)
+	})
+	t.Run("value from middle of a cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 8
+		c := createSparseCache(wantCap, wantLen)
+
+		k, wantV := keyValuePair(4)
+		_, wantB := keyValuePair(0)
+		gotV := c.Get(k)
+		if res := bytes.Compare(wantV, gotV); res != 0 {
+			t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+		}
+		checkCache(t, c, wantCap, wantLen, wantV, wantB)
+	})
+	t.Run("multiple values from a back of cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 8
+		c := createSparseCache(wantCap, wantLen)
+
+		for i := 0; i < wantLen; i++ {
+			k, wantV := keyValuePair(i)
+			_, wantB := keyValuePair((i + 1) % wantLen)
+			gotV := c.Get(k)
+			if res := bytes.Compare(wantV, gotV); res != 0 {
+				t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+			}
+			checkCache(t, c, wantCap, wantLen, wantV, wantB)
+		}
+	})
+	t.Run("multiple values from a front of cache", func(t *testing.T) {
+		wantCap, wantLen := 10, 8
+		c := createSparseCache(wantCap, wantLen)
+
+		for i := wantLen - 1; i >= 0; i-- {
+			k, wantV := keyValuePair(i)
+			_, wantB := keyValuePair(0)
+			gotV := c.Get(k)
+			if res := bytes.Compare(wantV, gotV); res != 0 {
+				t.Fatalf("expected value \"%s\" for key \"%s\" but got \"%s\"", wantV, k, gotV)
+			}
+			if i == 0 {
+				_, wantB = keyValuePair(7)
+			}
+			checkCache(t, c, wantCap, wantLen, wantV, wantB)
+		}
+	})
+}
+
+func TestCache_Clear(t *testing.T) {
+	wantCap := 10
+	c := NewCache(wantCap)
+	for i := 0; i < wantCap; i++ {
+		k, v := keyValuePair(i)
+		c.Put(k, v)
+	}
+	c.Clear()
+	checkCache(t, c, wantCap, 0, nil, nil)
+}
+
+func checkCache(t *testing.T, c *Cache, wantCap, wantLen int, f, b []byte) {
+	if c.Cap() != wantCap || c.Len() != wantLen {
+		t.Fatalf("expected Cap: \"%d\" and len: \"%d\" but got Cap: \"%d\" and len: \"%d\"", wantCap, wantLen,
+			c.Cap(), c.Len())
+	}
+
+	if res := bytes.Compare(f, c.Front()); res != 0 {
+		t.Fatalf("expected front of cache: \"%s\" but got \"%s\"", f, c.Front())
+	}
+
+	if res := bytes.Compare(b, c.Back()); res != 0 {
+		t.Fatalf("expected back of cache: \"%s\" but got \"%s\"", b, c.Back())
+	}
+}
+
+func createFullCache(cap int) *Cache {
+	c := NewCache(cap)
+	for i := 0; i < cap; i++ {
+		k, v := keyValuePair(i)
+		c.Put(k, v)
+	}
+	return c
+}
+
+func createSparseCache(cap int, len int) *Cache {
+	c := NewCache(cap)
+	for i := 0; i < len; i++ {
+		k, v := keyValuePair(i)
+		c.Put(k, v)
+	}
+	return c
+}
+
+func keyValuePair(i int) ([]byte, []byte) {
+	return []byte(fmt.Sprintf("key%d", i)), []byte(fmt.Sprintf("value%d", i))
+}
diff --git a/internal/cache/lru_test.go b/internal/cache/lru_test.go
deleted file mode 100644
index 0dc2487f..00000000
--- a/internal/cache/lru_test.go
+++ /dev/null
@@ -1,100 +0,0 @@
-package cache
-
-import (
-	"bytes"
-	"fmt"
-	"testing"
-)
-
-func TestNewLRUCache(t *testing.T) {
-	c := NewLRUCache(10)
-	if c.Cap() != 10 {
-		t.Errorf("Expected capacity to be 10, got %d", c.Cap())
-	}
-	if c.Len() != 0 {
-		t.Errorf("Expected count to be 0, got %d", c.Len())
-	}
-}
-
-func TestLRUCache_Put(t *testing.T) {
-	c := NewLRUCache(10)
-	// Fill the cache
-	for i := 0; i < 10; i++ {
-		key := []byte(fmt.Sprintf("key%d", i))
-		value := []byte(fmt.Sprintf("value%d", i))
-		c.Put(key, value)
-		if c.Len() != i+1 {
-			t.Errorf("Expected count to be %d, got %d", i+1, c.Len())
-		}
-	}
-	for i := 0; i < 10; i++ {
-		key := []byte(fmt.Sprintf("key%d", 10+i))
-		value := []byte(fmt.Sprintf("value%d", 10+i))
-		c.Put(key, value)
-		if c.Len() != 10 {
-			t.Errorf("Expected count to be 10, got %d", c.Len())
-		}
-		deletedKey := []byte(fmt.Sprintf("key%d", i))
-		if v := c.Get(deletedKey); v != nil {
-			t.Errorf("Expected value to be nil, got %s", v)
-		}
-	}
-}
-
-func TestLRUCache_Get(t *testing.T) {
-	c := NewLRUCache(10)
-	for i := 0; i < 3; i++ {
-		key := []byte(fmt.Sprintf("key%d", i))
-		value := []byte(fmt.Sprintf("value%d", i))
-		c.Put(key, value)
-	}
-	for _, i := range []int{2, 1, 0} {
-		key := []byte(fmt.Sprintf("key%d", i))
-		want := []byte(fmt.Sprintf("value%d", i))
-		value := c.Get(key)
-		if !bytes.Equal(value, want) {
-			t.Errorf("Expected value to be %s, got %s", want, value)
-		}
-	}
-	if value := c.Get([]byte("key4")); value != nil {
-		t.Errorf("Expected value to be nil, got %s", value)
-	}
-}
-
-func TestLRUCache_Count(t *testing.T) {
-	c := NewLRUCache(10)
-	if c.Len() != 0 {
-		t.Errorf("Expected count to be 0, got %d", c.Len())
-	}
-	for i := 0; i < 10; i++ {
-		key := []byte(fmt.Sprintf("key%d", i))
-		value := []byte(fmt.Sprintf("value%d", i))
-		c.Put(key, value)
-		if c.Len() != i+1 {
-			t.Errorf("Expected count to be %d, got %d", i+1, c.Len())
-		}
-	}
-}
-
-func TestLRUCache_Capacity(t *testing.T) {
-	c := NewLRUCache(100)
-	if c.Cap() != 100 {
-		t.Errorf("Expected capacity to be 100, got %d", c.Cap())
-	}
-}
-
-func TestLRUCache_Clear(t *testing.T) {
-	c := NewLRUCache(10)
-	for i := 0; i < 10; i++ {
-		key := []byte(fmt.Sprintf("key%d", i))
-		value := []byte(fmt.Sprintf("value%d", i))
-		c.Put(key, value)
-	}
-	if c.Len() != 10 {
-		t.Errorf("Expected count to be 10, got %d", c.Len())
-	}
-	c.Clear()
-	if c.Len() != 0 {
-		t.Errorf("Expected count to be 0, got %d", c.Len())
-	}
-}