148 lines
3.4 KiB
Go
148 lines
3.4 KiB
Go
// Copyright 2016 by Sascha L. Teichmann
|
|
// Use of this source code is governed by the MIT license
|
|
// that can be found in the LICENSE file.
|
|
|
|
package common
|
|
|
|
import (
|
|
"math/rand"
|
|
"testing"
|
|
)
|
|
|
|
func randomBaseTileHash(updates int) *BaseTileHash {
|
|
bth := NewBaseTileHash(256)
|
|
h1 := []byte{1}
|
|
h2 := []byte{2}
|
|
for i := 0; i < updates; i++ {
|
|
x, y := rand.Intn(100), rand.Intn(100)
|
|
var h []byte
|
|
if i%2 == 0 {
|
|
h = h1
|
|
} else {
|
|
h = h2
|
|
}
|
|
bth.Update(x, y, h)
|
|
}
|
|
return bth
|
|
}
|
|
|
|
func TestBaseTileHashLenList(t *testing.T) {
|
|
for _, updates := range []int{53, 111, 1345, 11261} {
|
|
bth := randomBaseTileHash(updates)
|
|
countNext := 0
|
|
for cur := bth.root.next; cur != &bth.root; cur = cur.next {
|
|
countNext++
|
|
}
|
|
countPrev := 0
|
|
for cur := bth.root.prev; cur != &bth.root; cur = cur.prev {
|
|
countPrev++
|
|
}
|
|
if countPrev != countNext {
|
|
t.Errorf("count prev != count next: %d %d", countPrev, countNext)
|
|
}
|
|
if countPrev != len(bth.hashes) {
|
|
t.Errorf("count prev != len(hash): %d %d", countPrev, len(bth.hashes))
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestBaseTileHashIntegrity(t *testing.T) {
|
|
for _, updates := range []int{10, 100, 1000, 10000} {
|
|
bth := randomBaseTileHash(updates)
|
|
entries := map[*btHashEntry]bool{}
|
|
|
|
for cur := bth.root.next; cur != &bth.root; cur = cur.next {
|
|
if entries[cur] {
|
|
t.Errorf("hash element found more than once: %d", updates)
|
|
}
|
|
entries[cur] = true
|
|
}
|
|
if len(entries) != len(bth.hashes) {
|
|
t.Errorf("List has differnt length than hashes: %d : %d",
|
|
len(entries), len(bth.hashes))
|
|
}
|
|
var already1 bool
|
|
var already2 bool
|
|
for k, v := range bth.hashes {
|
|
if !entries[v] {
|
|
if !already1 {
|
|
already1 = true
|
|
t.Errorf("Hash contains pointer to element not being in list: %d",
|
|
updates)
|
|
}
|
|
}
|
|
if k != v.btKey {
|
|
if !already2 {
|
|
already2 = true
|
|
t.Errorf("Key in entry does not match hash key: %d", updates)
|
|
}
|
|
}
|
|
delete(entries, v)
|
|
}
|
|
|
|
if len(entries) > 0 {
|
|
t.Error("There are more entries than indexed by hash")
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestBaseTileHashOverwrite(t *testing.T) {
|
|
bth := NewBaseTileHash(256)
|
|
h1 := []byte{1}
|
|
h2 := []byte{2}
|
|
|
|
if updated := bth.Update(0, 0, h1); !updated {
|
|
t.Error("First insert does not trigger update")
|
|
}
|
|
|
|
if updated := bth.Update(0, 0, h2); !updated {
|
|
t.Error("Second insert does not trigger update")
|
|
}
|
|
|
|
if updated := bth.Update(0, 0, h2); updated {
|
|
t.Error("Third insert does trigger update")
|
|
}
|
|
}
|
|
|
|
func TestBaseTileHashSeparate(t *testing.T) {
|
|
bth := NewBaseTileHash(256)
|
|
h1 := []byte{1}
|
|
|
|
if updated := bth.Update(0, 0, h1); !updated {
|
|
t.Error("First insert does not trigger update")
|
|
}
|
|
|
|
if updated := bth.Update(0, 1, h1); !updated {
|
|
t.Error("Second insert does not trigger update")
|
|
}
|
|
|
|
if updated := bth.Update(1, 0, h1); !updated {
|
|
t.Error("Third insert does trigger update")
|
|
}
|
|
|
|
if len(bth.hashes) != 3 {
|
|
t.Errorf("Expected size to be 3. Current size: %d", len(bth.hashes))
|
|
}
|
|
}
|
|
|
|
func TestBaseTileHashLRU(t *testing.T) {
|
|
bth := NewBaseTileHash(2)
|
|
h1 := []byte{1}
|
|
|
|
if updated := bth.Update(0, 0, h1); !updated {
|
|
t.Error("First insert does not trigger update")
|
|
}
|
|
|
|
if updated := bth.Update(0, 1, h1); !updated {
|
|
t.Error("Second insert does not trigger update")
|
|
}
|
|
|
|
if updated := bth.Update(1, 0, h1); !updated {
|
|
t.Error("Third insert does trigger update")
|
|
}
|
|
|
|
if len(bth.hashes) != 2 {
|
|
t.Errorf("Expected size to be 2. Current size: %d", len(bth.hashes))
|
|
}
|
|
}
|