goext/dataext/lruMap_test.go

260 lines
5.4 KiB
Go
Raw Permalink Normal View History

2022-10-27 16:00:57 +02:00
package dataext
import (
2022-10-27 16:48:26 +02:00
"gogs.mikescher.com/BlackForestBytes/goext/langext"
2022-10-27 16:00:57 +02:00
"math/rand"
"strconv"
"testing"
)
func init() {
rand.Seed(0)
}
func TestResultCache1(t *testing.T) {
2023-02-09 15:06:37 +01:00
cache := NewLRUMap[string, string](8)
2022-10-27 16:00:57 +02:00
verifyLRUList(cache, t)
key := randomKey()
val := randomVal()
if cache.Size() != 0 {
t.Errorf("cache size expected == 0, actual == %v", cache.Size())
}
if _, ok := cache.TryGet(key); ok {
t.Errorf("empty cache TryGet returned value")
}
verifyLRUList(cache, t)
cache.Put(key, val)
verifyLRUList(cache, t)
if cache.Size() != 1 {
t.Errorf("cache size expected == 1, actual == %v", cache.Size())
}
cacheval, ok := cache.TryGet(key)
verifyLRUList(cache, t)
if !ok {
t.Errorf("cache TryGet returned no value")
}
2022-12-22 10:06:25 +01:00
if cacheval != val {
2022-10-27 16:00:57 +02:00
t.Errorf("cache TryGet returned different value (%+v <> %+v)", cacheval, val)
}
if _, ok := cache.TryGet(randomKey()); ok {
t.Errorf("cache TryGet returned a value for non-existant key")
}
verifyLRUList(cache, t)
}
func TestResultCache2(t *testing.T) {
2023-02-09 15:06:37 +01:00
cache := NewLRUMap[string, string](8)
2022-10-27 16:00:57 +02:00
verifyLRUList(cache, t)
key1 := "key1"
val1 := randomVal()
cache.Put(key1, val1)
verifyLRUList(cache, t)
key2 := "key2"
val2 := randomVal()
cache.Put(key2, val2)
verifyLRUList(cache, t)
key3 := "key3"
val3 := randomVal()
cache.Put(key3, val3)
verifyLRUList(cache, t)
key4 := "key4"
val4 := randomVal()
cache.Put(key4, val4)
verifyLRUList(cache, t)
if _, ok := cache.TryGet(key1); !ok {
t.Errorf("cache TryGet returned no value")
}
verifyLRUList(cache, t)
if _, ok := cache.TryGet(key2); !ok {
t.Errorf("cache TryGet returned no value")
}
verifyLRUList(cache, t)
if _, ok := cache.TryGet(key3); !ok {
t.Errorf("cache TryGet returned no value")
}
verifyLRUList(cache, t)
if _, ok := cache.TryGet(key4); !ok {
t.Errorf("cache TryGet returned no value")
}
verifyLRUList(cache, t)
if _, ok := cache.TryGet(randomKey()); ok {
t.Errorf("cache TryGet returned a value for non-existant key")
}
verifyLRUList(cache, t)
if cache.Size() != 4 {
t.Errorf("cache size expected == 4, actual == %v", cache.Size())
}
verifyLRUList(cache, t)
cache.Put(key4, val4) // same key again
verifyLRUList(cache, t)
if cache.Size() != 4 {
t.Errorf("cache size expected == 4, actual == %v", cache.Size())
}
cache.Put(randomKey(), randomVal())
verifyLRUList(cache, t)
cache.Put(randomKey(), randomVal())
verifyLRUList(cache, t)
cache.Put(randomKey(), randomVal())
verifyLRUList(cache, t)
cache.Put(randomKey(), randomVal())
verifyLRUList(cache, t)
if cache.Size() != 8 {
t.Errorf("cache size expected == 8, actual == %v", cache.Size())
}
cache.Put(randomKey(), randomVal()) // drops key1
verifyLRUList(cache, t)
if cache.Size() != 8 {
t.Errorf("cache size expected == 8, actual == %v", cache.Size())
}
if _, ok := cache.TryGet(key1); ok {
t.Errorf("[key1] should be dropped from cache")
}
verifyLRUList(cache, t)
if _, ok := cache.TryGet(key2); !ok { // moves key2 to most-recently used
t.Errorf("[key2] should still be in cache")
}
verifyLRUList(cache, t)
cache.Put(randomKey(), randomVal()) // drops key3
verifyLRUList(cache, t)
if cache.Size() != 8 {
t.Errorf("cache size expected == 8, actual == %v", cache.Size())
}
if _, ok := cache.TryGet(key3); ok {
t.Errorf("[key3] should be dropped from cache")
}
if _, ok := cache.TryGet(key2); !ok {
t.Errorf("[key2] should still be in cache")
}
}
func TestResultCache3(t *testing.T) {
2023-02-09 15:06:37 +01:00
cache := NewLRUMap[string, string](8)
2022-10-27 16:00:57 +02:00
verifyLRUList(cache, t)
key1 := "key1"
val1 := randomVal()
val2 := randomVal()
cache.Put(key1, val1)
verifyLRUList(cache, t)
2022-12-22 10:06:25 +01:00
if val, ok := cache.TryGet(key1); !ok || val != val1 {
2022-10-27 16:00:57 +02:00
t.Errorf("Value in cache should be [val1]")
}
cache.Put(key1, val2)
verifyLRUList(cache, t)
2022-12-22 10:06:25 +01:00
if val, ok := cache.TryGet(key1); !ok || val != val2 {
2022-10-27 16:00:57 +02:00
t.Errorf("Value in cache should be [val2]")
}
}
// does a basic consistency check over the internal cache representation
2023-02-09 15:06:37 +01:00
func verifyLRUList[TKey comparable, TData any](cache *LRUMap[TKey, TData], t *testing.T) {
2022-10-27 16:00:57 +02:00
size := 0
tailFound := false
headFound := false
curr := cache.lfuHead
for curr != nil {
size++
if curr.parent == nil {
headFound = true
if curr != cache.lfuHead {
t.Errorf("head != lfuHead")
return
}
}
if curr.child == nil {
tailFound = true
if curr != cache.lfuTail {
t.Errorf("tail != lfuTail")
return
}
}
if curr.child != nil {
if curr.child.parent != curr {
t.Errorf("error in child <-> parent link")
return
}
}
if curr.parent != nil {
if curr.parent.child != curr {
t.Errorf("error in parent <-> child link")
return
}
}
curr = curr.child
}
if cache.Size() > 0 && cache.lfuHead == nil {
t.Errorf("no head in cache")
}
if cache.Size() > 0 && cache.lfuTail == nil {
t.Errorf("no tail in cache")
}
if cache.Size() == 0 && cache.lfuHead != nil {
t.Errorf("dangling head in cache")
}
if cache.Size() == 0 && cache.lfuTail != nil {
t.Errorf("dangling tail in cache")
}
if cache.Size() > 0 && !headFound {
t.Errorf("head not found")
}
if cache.Size() > 0 && !tailFound {
t.Errorf("tail not found")
}
if size != cache.Size() {
t.Errorf("error size mismatch (%v <> %v)", size, cache.Size())
}
if cache.Size() > cache.maxsize {
t.Errorf("too many items: %v", cache.Size())
}
}
func randomKey() string {
return strconv.FormatInt(rand.Int63(), 16)
}
2022-12-22 10:06:25 +01:00
func randomVal() string {
2022-10-27 16:48:26 +02:00
v, err := langext.NewHexUUID()
if err != nil {
panic(err)
}
2022-12-22 10:06:25 +01:00
return v
2022-10-27 16:00:57 +02:00
}