src/internal/concurrent/hashtriemap_test.go

// Copyright 2024 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package concurrent

import (
	"fmt"
	"math"
	"runtime"
	"strconv"
	"strings"
	"sync"
	"testing"
	"unsafe"
)

func TestHashTrieMap(t *testing.T) {
	testHashTrieMap(t, func() *HashTrieMap[string, int] {
		return NewHashTrieMap[string, int]()
	})
}

func TestHashTrieMapBadHash(t *testing.T) {
	testHashTrieMap(t, func() *HashTrieMap[string, int] {
		// Stub out the good hash function with a terrible one.
		// Everything should still work as expected.
		m := NewHashTrieMap[string, int]()
		m.keyHash = func(_ unsafe.Pointer, _ uintptr) uintptr {
			return 0
		}
		return m
	})
}

func testHashTrieMap(t *testing.T, newMap func() *HashTrieMap[string, int]) {
	t.Run("LoadEmpty", func(t *testing.T) {
		m := newMap()

		for _, s := range testData {
			expectMissing(t, s, 0)(m.Load(s))
		}
	})
	t.Run("LoadOrStore", func(t *testing.T) {
		m := newMap()

		for i, s := range testData {
			expectMissing(t, s, 0)(m.Load(s))
			expectStored(t, s, i)(m.LoadOrStore(s, i))
			expectPresent(t, s, i)(m.Load(s))
			expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
		}
		for i, s := range testData {
			expectPresent(t, s, i)(m.Load(s))
			expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
		}
	})
	t.Run("CompareAndDeleteAll", func(t *testing.T) {
		m := newMap()

		for range 3 {
			for i, s := range testData {
				expectMissing(t, s, 0)(m.Load(s))
				expectStored(t, s, i)(m.LoadOrStore(s, i))
				expectPresent(t, s, i)(m.Load(s))
				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
			}
			for i, s := range testData {
				expectPresent(t, s, i)(m.Load(s))
				expectNotDeleted(t, s, math.MaxInt)(m.CompareAndDelete(s, math.MaxInt))
				expectDeleted(t, s, i)(m.CompareAndDelete(s, i))
				expectNotDeleted(t, s, i)(m.CompareAndDelete(s, i))
				expectMissing(t, s, 0)(m.Load(s))
			}
			for _, s := range testData {
				expectMissing(t, s, 0)(m.Load(s))
			}
		}
	})
	t.Run("CompareAndDeleteOne", func(t *testing.T) {
		m := newMap()

		for i, s := range testData {
			expectMissing(t, s, 0)(m.Load(s))
			expectStored(t, s, i)(m.LoadOrStore(s, i))
			expectPresent(t, s, i)(m.Load(s))
			expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
		}
		expectNotDeleted(t, testData[15], math.MaxInt)(m.CompareAndDelete(testData[15], math.MaxInt))
		expectDeleted(t, testData[15], 15)(m.CompareAndDelete(testData[15], 15))
		expectNotDeleted(t, testData[15], 15)(m.CompareAndDelete(testData[15], 15))
		for i, s := range testData {
			if i == 15 {
				expectMissing(t, s, 0)(m.Load(s))
			} else {
				expectPresent(t, s, i)(m.Load(s))
			}
		}
	})
	t.Run("DeleteMultiple", func(t *testing.T) {
		m := newMap()

		for i, s := range testData {
			expectMissing(t, s, 0)(m.Load(s))
			expectStored(t, s, i)(m.LoadOrStore(s, i))
			expectPresent(t, s, i)(m.Load(s))
			expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
		}
		for _, i := range []int{1, 105, 6, 85} {
			expectNotDeleted(t, testData[i], math.MaxInt)(m.CompareAndDelete(testData[i], math.MaxInt))
			expectDeleted(t, testData[i], i)(m.CompareAndDelete(testData[i], i))
			expectNotDeleted(t, testData[i], i)(m.CompareAndDelete(testData[i], i))
		}
		for i, s := range testData {
			if i == 1 || i == 105 || i == 6 || i == 85 {
				expectMissing(t, s, 0)(m.Load(s))
			} else {
				expectPresent(t, s, i)(m.Load(s))
			}
		}
	})
	t.Run("Enumerate", func(t *testing.T) {
		m := newMap()

		testEnumerate(t, m, testDataMap(testData[:]), func(_ string, _ int) bool {
			return true
		})
	})
	t.Run("EnumerateDelete", func(t *testing.T) {
		m := newMap()

		testEnumerate(t, m, testDataMap(testData[:]), func(s string, i int) bool {
			expectDeleted(t, s, i)(m.CompareAndDelete(s, i))
			return true
		})
		for _, s := range testData {
			expectMissing(t, s, 0)(m.Load(s))
		}
	})
	t.Run("ConcurrentLifecycleUnsharedKeys", func(t *testing.T) {
		m := newMap()

		gmp := runtime.GOMAXPROCS(-1)
		var wg sync.WaitGroup
		for i := range gmp {
			wg.Add(1)
			go func(id int) {
				defer wg.Done()

				makeKey := func(s string) string {
					return s + "-" + strconv.Itoa(id)
				}
				for _, s := range testData {
					key := makeKey(s)
					expectMissing(t, key, 0)(m.Load(key))
					expectStored(t, key, id)(m.LoadOrStore(key, id))
					expectPresent(t, key, id)(m.Load(key))
					expectLoaded(t, key, id)(m.LoadOrStore(key, 0))
				}
				for _, s := range testData {
					key := makeKey(s)
					expectPresent(t, key, id)(m.Load(key))
					expectDeleted(t, key, id)(m.CompareAndDelete(key, id))
					expectMissing(t, key, 0)(m.Load(key))
				}
				for _, s := range testData {
					key := makeKey(s)
					expectMissing(t, key, 0)(m.Load(key))
				}
			}(i)
		}
		wg.Wait()
	})
	t.Run("ConcurrentDeleteSharedKeys", func(t *testing.T) {
		m := newMap()

		// Load up the map.
		for i, s := range testData {
			expectMissing(t, s, 0)(m.Load(s))
			expectStored(t, s, i)(m.LoadOrStore(s, i))
		}
		gmp := runtime.GOMAXPROCS(-1)
		var wg sync.WaitGroup
		for i := range gmp {
			wg.Add(1)
			go func(id int) {
				defer wg.Done()

				for i, s := range testData {
					expectNotDeleted(t, s, math.MaxInt)(m.CompareAndDelete(s, math.MaxInt))
					m.CompareAndDelete(s, i)
					expectMissing(t, s, 0)(m.Load(s))
				}
				for _, s := range testData {
					expectMissing(t, s, 0)(m.Load(s))
				}
			}(i)
		}
		wg.Wait()
	})
}

func testEnumerate[K, V comparable](t *testing.T, m *HashTrieMap[K, V], testData map[K]V, yield func(K, V) bool) {
	for k, v := range testData {
		expectStored(t, k, v)(m.LoadOrStore(k, v))
	}
	visited := make(map[K]int)
	m.Enumerate(func(key K, got V) bool {
		want, ok := testData[key]
		if !ok {
			t.Errorf("unexpected key %v in map", key)
			return false
		}
		if got != want {
			t.Errorf("expected key %v to have value %v, got %v", key, want, got)
			return false
		}
		visited[key]++
		return yield(key, got)
	})
	for key, n := range visited {
		if n > 1 {
			t.Errorf("visited key %v more than once", key)
		}
	}
}

func expectPresent[K, V comparable](t *testing.T, key K, want V) func(got V, ok bool) {
	t.Helper()
	return func(got V, ok bool) {
		t.Helper()

		if !ok {
			t.Errorf("expected key %v to be present in map", key)
		}
		if ok && got != want {
			t.Errorf("expected key %v to have value %v, got %v", key, want, got)
		}
	}
}

func expectMissing[K, V comparable](t *testing.T, key K, want V) func(got V, ok bool) {
	t.Helper()
	if want != *new(V) {
		// This is awkward, but the want argument is necessary to smooth over type inference.
		// Just make sure the want argument always looks the same.
		panic("expectMissing must always have a zero value variable")
	}
	return func(got V, ok bool) {
		t.Helper()

		if ok {
			t.Errorf("expected key %v to be missing from map, got value %v", key, got)
		}
		if !ok && got != want {
			t.Errorf("expected missing key %v to be paired with the zero value; got %v", key, got)
		}
	}
}

func expectLoaded[K, V comparable](t *testing.T, key K, want V) func(got V, loaded bool) {
	t.Helper()
	return func(got V, loaded bool) {
		t.Helper()

		if !loaded {
			t.Errorf("expected key %v to have been loaded, not stored", key)
		}
		if got != want {
			t.Errorf("expected key %v to have value %v, got %v", key, want, got)
		}
	}
}

func expectStored[K, V comparable](t *testing.T, key K, want V) func(got V, loaded bool) {
	t.Helper()
	return func(got V, loaded bool) {
		t.Helper()

		if loaded {
			t.Errorf("expected inserted key %v to have been stored, not loaded", key)
		}
		if got != want {
			t.Errorf("expected inserted key %v to have value %v, got %v", key, want, got)
		}
	}
}

func expectDeleted[K, V comparable](t *testing.T, key K, old V) func(deleted bool) {
	t.Helper()
	return func(deleted bool) {
		t.Helper()

		if !deleted {
			t.Errorf("expected key %v with value %v to be in map and deleted", key, old)
		}
	}
}

func expectNotDeleted[K, V comparable](t *testing.T, key K, old V) func(deleted bool) {
	t.Helper()
	return func(deleted bool) {
		t.Helper()

		if deleted {
			t.Errorf("expected key %v with value %v to not be in map and thus not deleted", key, old)
		}
	}
}

func testDataMap(data []string) map[string]int {
	m := make(map[string]int)
	for i, s := range data {
		m[s] = i
	}
	return m
}

var (
	testDataSmall [8]string
	testData      [128]string
	testDataLarge [128 << 10]string
)

func init() {
	for i := range testDataSmall {
		testDataSmall[i] = fmt.Sprintf("%b", i)
	}
	for i := range testData {
		testData[i] = fmt.Sprintf("%b", i)
	}
	for i := range testDataLarge {
		testDataLarge[i] = fmt.Sprintf("%b", i)
	}
}

func dumpMap[K, V comparable](ht *HashTrieMap[K, V]) {
	dumpNode(ht, &ht.root.node, 0)
}

func dumpNode[K, V comparable](ht *HashTrieMap[K, V], n *node[K, V], depth int) {
	var sb strings.Builder
	for range depth {
		fmt.Fprintf(&sb, "\t")
	}
	prefix := sb.String()
	if n.isEntry {
		e := n.entry()
		for e != nil {
			fmt.Printf("%s%p [Entry Key=%v Value=%v Overflow=%p, Hash=%016x]\n", prefix, e, e.key, e.value, e.overflow.Load(), ht.keyHash(unsafe.Pointer(&e.key), ht.seed))
			e = e.overflow.Load()
		}
		return
	}
	i := n.indirect()
	fmt.Printf("%s%p [Indirect Parent=%p Dead=%t Children=[", prefix, i, i.parent, i.dead.Load())
	for j := range i.children {
		c := i.children[j].Load()
		fmt.Printf("%p", c)
		if j != len(i.children)-1 {
			fmt.Printf(", ")
		}
	}
	fmt.Printf("]]\n")
	for j := range i.children {
		c := i.children[j].Load()
		if c != nil {
			dumpNode(ht, c, depth+1)
		}
	}
}