goext/dataext/lruMap_test.go

package dataext

import (
	"gogs.mikescher.com/BlackForestBytes/goext/langext"
	"math/rand"
	"strconv"
	"testing"
)

func init() {
	rand.Seed(0)
}

func TestResultCache1(t *testing.T) {
	cache := NewLRUMap[string, string](8)
	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")
	}
	if cacheval != val {
		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) {
	cache := NewLRUMap[string, string](8)
	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) {
	cache := NewLRUMap[string, string](8)
	verifyLRUList(cache, t)

	key1 := "key1"
	val1 := randomVal()
	val2 := randomVal()

	cache.Put(key1, val1)
	verifyLRUList(cache, t)

	if val, ok := cache.TryGet(key1); !ok || val != val1 {
		t.Errorf("Value in cache should be [val1]")
	}

	cache.Put(key1, val2)
	verifyLRUList(cache, t)

	if val, ok := cache.TryGet(key1); !ok || val != val2 {
		t.Errorf("Value in cache should be [val2]")
	}
}

// does a basic consistency check over the internal cache representation
func verifyLRUList[TKey comparable, TData any](cache *LRUMap[TKey, TData], t *testing.T) {
	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)
}

func randomVal() string {
	v, err := langext.NewHexUUID()
	if err != nil {
		panic(err)
	}
	return v
}