cmd/compile,internal/runtime/maps: add extendible hashing

Extendible hashing splits a swisstable map into many swisstables. This
keeps grow operations small.

For #54766.

Cq-Include-Trybots: luci.golang.try:gotip-linux-ppc64_power10,gotip-linux-amd64-longtest-swissmap
Change-Id: Id91f34af9e686bf35eb8882ee479956ece89e821
Reviewed-on: https://go-review.googlesource.com/c/go/+/604936
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@google.com>

1 files changed, 25 insertions, 2 deletions

diff --git a/src/internal/runtime/maps/export_test.go b/src/internal/runtime/maps/export_test.go
index 2856a7314e..369ef1f2fe 100644
--- a/src/internal/runtime/maps/export_test.go
+++ b/src/internal/runtime/maps/export_test.go
@@ -15,8 +15,31 @@ const DebugLog = debugLog
 
 var AlignUpPow2 = alignUpPow2
 
-func (t *table) Type() *abi.SwissMapType {
-	return t.typ
+const MaxTableCapacity = maxTableCapacity
+const MaxAvgGroupLoad = maxAvgGroupLoad
+
+func NewTestMap[K comparable, V any](length uint64) (*Map, *abi.SwissMapType) {
+	mt := newTestMapType[K, V]()
+	return NewMap(mt, length), mt
+}
+
+func (m *Map) TableCount() int {
+	return len(m.directory)
+}
+
+// Total group count, summed across all tables.
+func (m *Map) GroupCount() uint64 {
+	var n uint64
+	for _, t := range m.directory {
+		n += t.groups.lengthMask + 1
+	}
+	return n
+}
+
+func (m *Map) TableFor(key unsafe.Pointer) *table {
+	hash := m.typ.Hasher(key, m.seed)
+	idx := m.directoryIndex(hash)
+	return m.directory[idx]
 }
 
 // Returns the start address of the groups array.