internal/runtime/maps: initial swiss table map implementation

Add a new package that will contain a new "Swiss Table"
(https://abseil.io/about/design/swisstables) map implementation, which
is intended to eventually replace the existing runtime map
implementation.

This implementation is based on the fabulous
github.com/cockroachdb/swiss package contributed by Peter Mattis.

This CL adds an hash map implementation. It supports all the core
operations, but does not have incremental growth.

For #54766.

Change-Id: I52cf371448c3817d471ddb1f5a78f3513565db41
Reviewed-on: https://go-review.googlesource.com/c/go/+/582415
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>

1 files changed, 56 insertions, 0 deletions

diff --git a/src/internal/runtime/maps/export_test.go b/src/internal/runtime/maps/export_test.go
new file mode 100644
index 0000000000..e2512d332a
--- /dev/null
+++ b/src/internal/runtime/maps/export_test.go
@@ -0,0 +1,56 @@
+// 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 maps
+
+import (
+	"internal/abi"
+	sabi "internal/runtime/maps/internal/abi"
+	"unsafe"
+)
+
+type CtrlGroup = ctrlGroup
+
+const DebugLog = debugLog
+
+var AlignUpPow2 = alignUpPow2
+
+type instantiatedGroup[K comparable, V any] struct {
+	ctrls ctrlGroup
+	slots [sabi.SwissMapGroupSlots]instantiatedSlot[K, V]
+}
+
+type instantiatedSlot[K comparable, V any] struct {
+	key  K
+	elem V
+}
+
+func NewTestTable[K comparable, V any](length uint64) *table {
+	var m map[K]V
+	mTyp := abi.TypeOf(m)
+	omt := (*abi.OldMapType)(unsafe.Pointer(mTyp))
+
+	var grp instantiatedGroup[K, V]
+	var slot instantiatedSlot[K, V]
+
+	mt := &sabi.SwissMapType{
+		Key:      omt.Key,
+		Elem:     omt.Elem,
+		Group:    abi.TypeOf(grp),
+		Hasher:   omt.Hasher,
+		SlotSize: unsafe.Sizeof(slot),
+		ElemOff:  unsafe.Offsetof(slot.elem),
+	}
+	if omt.NeedKeyUpdate() {
+		mt.Flags |= sabi.SwissMapNeedKeyUpdate
+	}
+	if omt.HashMightPanic() {
+		mt.Flags |= sabi.SwissMapHashMightPanic
+	}
+	return newTable(mt, length)
+}
+
+func (t *table) Type() *sabi.SwissMapType {
+	return t.typ
+}