File size: 2,752 Bytes
e36aeda | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | // 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"
"unsafe"
)
type CtrlGroup = ctrlGroup
const DebugLog = debugLog
var AlignUpPow2 = alignUpPow2
const MaxTableCapacity = maxTableCapacity
const MaxAvgGroupLoad = maxAvgGroupLoad
// This isn't equivalent to runtime.maxAlloc. It is fine for basic testing but
// we can't properly test hint alloc overflows with this.
const maxAllocTest = 1 << 30
func newTestMapType[K comparable, V any]() *abi.MapType {
var m map[K]V
mTyp := abi.TypeOf(m)
mt := (*abi.MapType)(unsafe.Pointer(mTyp))
return mt
}
func NewTestMap[K comparable, V any](hint uintptr) (*Map, *abi.MapType) {
mt := newTestMapType[K, V]()
return NewMap(mt, hint, nil, maxAllocTest), mt
}
func (m *Map) TableCount() int {
if m.dirLen <= 0 {
return 0
}
return m.dirLen
}
// Total group count, summed across all tables.
func (m *Map) GroupCount() uint64 {
if m.dirLen <= 0 {
if m.dirPtr == nil {
return 0
}
return 1
}
var n uint64
var lastTab *table
for i := range m.dirLen {
t := m.directoryAt(uintptr(i))
if t == lastTab {
continue
}
lastTab = t
n += t.groups.lengthMask + 1
}
return n
}
// Return a key from a group containing no empty slots.
//
// Returns nil if there are no full groups.
// Returns nil if a group is full but contains entirely deleted slots.
// Returns nil if the map is small.
func (m *Map) KeyFromFullGroup(typ *abi.MapType) unsafe.Pointer {
if m.dirLen <= 0 {
return nil
}
var lastTab *table
for i := range m.dirLen {
t := m.directoryAt(uintptr(i))
if t == lastTab {
continue
}
lastTab = t
for i := uint64(0); i <= t.groups.lengthMask; i++ {
g := t.groups.group(typ, i)
match := g.ctrls().matchEmpty()
if match != 0 {
continue
}
// All full or deleted slots.
for j := uintptr(0); j < abi.MapGroupSlots; j++ {
if g.ctrls().get(j) == ctrlDeleted {
continue
}
slotKey := g.key(typ, j)
if typ.IndirectKey() {
slotKey = *((*unsafe.Pointer)(slotKey))
}
return slotKey
}
}
}
return nil
}
// Returns nil if the map is small.
func (m *Map) TableFor(typ *abi.MapType, key unsafe.Pointer) *table {
if m.dirLen <= 0 {
return nil
}
hash := typ.Hasher(key, m.seed)
idx := m.directoryIndex(hash)
return m.directoryAt(idx)
}
func (t *table) GrowthLeft() uint64 {
return uint64(t.growthLeft)
}
// Returns the start address of the groups array.
func (t *table) GroupsStart() unsafe.Pointer {
return t.groups.data
}
// Returns the length of the groups array.
func (t *table) GroupsLength() uintptr {
return uintptr(t.groups.lengthMask + 1)
}
|