maps

Imports

Imports #

"internal/abi"
"internal/race"
"internal/runtime/sys"
"unsafe"
"internal/abi"
"internal/race"
"internal/runtime/sys"
"unsafe"
"internal/abi"
"internal/goarch"
"internal/race"
"internal/runtime/sys"
"unsafe"
"internal/abi"
"unsafe"
"internal/abi"
"internal/goarch"
"unsafe"
"internal/abi"
"unsafe"
"internal/abi"
"internal/goarch"
"internal/runtime/sys"
"unsafe"
"internal/abi"
"internal/goarch"
"internal/runtime/math"
"internal/runtime/sys"
"unsafe"
"internal/abi"
"unsafe"
"internal/abi"
"internal/asan"
"internal/msan"
"internal/race"
"internal/runtime/sys"
"unsafe"

Constants & Variables

_ var #

Ensure the max capacity fits in uint16, used for capacity and growthLeft below.

var _ = *ast.CallExpr

bitsetDeleted const #

const bitsetDeleted = *ast.BinaryExpr

bitsetEmpty const #

const bitsetEmpty = *ast.BinaryExpr

bitsetLSB const #

const bitsetLSB = 0x0101010101010101

bitsetMSB const #

const bitsetMSB = 0x8080808080808080

ctrlDeleted const #

const ctrlDeleted ctrl = 0b11111110

ctrlEmpty const #

const ctrlEmpty ctrl = 0b10000000

ctrlGroupsSize const #

const ctrlGroupsSize = *ast.CallExpr

debugLog const #

const debugLog = false

errNilAssign var #

Pushed from runtime in order to use runtime.plainError go:linkname errNilAssign

var errNilAssign error

groupSlotsOffset const #

const groupSlotsOffset = ctrlGroupsSize

maxAvgGroupLoad const #

Maximum load factor prior to growing. 7/8 is the same load factor used by Abseil, but Abseil defaults to 16 slots per group, so they get two empty slots vs our one empty slot. We may want to reevaluate if this is best for us.

const maxAvgGroupLoad = 7

maxTableCapacity const #

Maximum size of a table before it is split at the directory level. TODO: Completely made up value. This should be tuned for performance vs grow latency. TODO: This should likely be based on byte size, as copying costs will dominate grow latency for large objects.

const maxTableCapacity = 1024

zeroVal var #

Pull from runtime. It is important that is this the exact same copy as the runtime because runtime.mapaccess1_fat compares the returned pointer with &runtime.zeroVal[0]. TODO: move zeroVal to internal/abi? go:linkname zeroVal runtime.zeroVal

var zeroVal [abi.ZeroValSize]byte

Type Aliases

bitset type #

bitset represents a set of slots within a group. The underlying representation depends on GOARCH. On AMD64, bitset uses one bit per slot, where the bit is set if the slot is part of the set. All of the ctrlGroup.match* methods are replaced with intrinsics that return this packed representation. On other architectures, bitset uses one byte per slot, where each byte is either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it convenient to calculate for an entire group at once using standard arithemetic instructions.

type bitset uint64

ctrl type #

Each slot in the hash table has a control byte which can have one of three states: empty, deleted, and full. They have the following bit patterns: empty: 1 0 0 0 0 0 0 0 deleted: 1 1 1 1 1 1 1 0 full: 0 h h h h h h h // h represents the H1 hash bits TODO(prattmic): Consider inverting the top bit so that the zero value is empty.

type ctrl uint8

ctrlGroup type #

ctrlGroup is a fixed size array of abi.SwissMapGroupSlots control bytes stored in a uint64.

type ctrlGroup uint64

Structs

Iter struct #

type Iter struct {
key unsafe.Pointer
elem unsafe.Pointer
typ *abi.SwissMapType
m *Map
entryOffset uint64
dirOffset uint64
clearSeq uint64
globalDepth uint8
dirIdx int
tab *table
group groupReference
entryIdx uint64
}

Map struct #

type Map struct {
used uint64
seed uintptr
dirPtr unsafe.Pointer
dirLen int
globalDepth uint8
globalShift uint8
writing uint8
clearSeq uint64
}

groupReference struct #

groupReference is a wrapper type representing a single slot group stored at data. A group holds abi.SwissMapGroupSlots slots (key/elem pairs) plus their control word.

type groupReference struct {
data unsafe.Pointer
}

groupsReference struct #

groupsReference is a wrapper type describing an array of groups stored at data.

type groupsReference struct {
data unsafe.Pointer
lengthMask uint64
}

probeSeq struct #

probeSeq maintains the state for a probe sequence that iterates through the groups in a table. The sequence is a triangular progression of the form p(i) := (i^2 + i)/2 + hash (mod mask+1) The sequence effectively outputs the indexes of *groups*. The group machinery allows us to check an entire group with minimal branching. It turns out that this probe sequence visits every group exactly once if the number of groups is a power of two, since (i^2+i)/2 is a bijection in Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probing

type probeSeq struct {
mask uint64
offset uint64
index uint64
}

table struct #

table is a Swiss table hash table structure. Each table is a complete hash table implementation. Map uses one or more tables to store entries. Extendible hashing (hash prefix) is used to select the table to use for a specific key. Using multiple tables enables incremental growth by growing only one table at a time.

type table struct {
used uint16
capacity uint16
growthLeft uint16
localDepth uint8
index int
groups groupsReference
}

Functions

Clear method #

Clear deletes all entries from the map resulting in an empty map.

func (m *Map) Clear(typ *abi.SwissMapType)

Clear method #

Clear deletes all entries from the map resulting in an empty map.

func (t *table) Clear(typ *abi.SwissMapType)

Delete method #

func (m *Map) Delete(typ *abi.SwissMapType, key unsafe.Pointer)

Delete method #

func (t *table) Delete(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer)

Elem method #

Key returns a pointer to the current element. nil indicates end of iteration. Must not be called prior to Next.

func (it *Iter) Elem() unsafe.Pointer

Get method #

Get performs a lookup of the key that key points to. It returns a pointer to the element, or false if the key doesn't exist.

func (m *Map) Get(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, bool)

Get method #

Get performs a lookup of the key that key points to. It returns a pointer to the element, or false if the key doesn't exist.

func (t *table) Get(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool)

Init method #

Init initializes Iter for iteration.

func (it *Iter) Init(typ *abi.SwissMapType, m *Map)

Initialized method #

func (it *Iter) Initialized() bool

Key method #

Key returns a pointer to the current key. nil indicates end of iteration. Must not be called prior to Next.

func (it *Iter) Key() unsafe.Pointer

Map method #

Map returns the map this iterator is iterating over.

func (it *Iter) Map() *Map

NewEmptyMap function #

func NewEmptyMap() *Map

NewMap function #

If m is non-nil, it should be used rather than allocating. maxAlloc should be runtime.maxAlloc. TODO(prattmic): Put maxAlloc somewhere accessible.

func NewMap(mt *abi.SwissMapType, hint uintptr, m *Map, maxAlloc uintptr) *Map

Next method #

Next proceeds to the next element in iteration, which can be accessed via the Key and Elem methods. The table can be mutated during iteration, though there is no guarantee that the mutations will be visible to the iteration. Init must be called prior to Next.

func (it *Iter) Next()

Print method #

func (t *table) Print(typ *abi.SwissMapType, m *Map)

Put method #

func (m *Map) Put(typ *abi.SwissMapType, key unsafe.Pointer, elem unsafe.Pointer)

PutSlot method #

PutSlot returns a pointer to the element slot where an inserted element should be written. PutSlot never returns nil.

func (m *Map) PutSlot(typ *abi.SwissMapType, key unsafe.Pointer) unsafe.Pointer

PutSlot method #

PutSlot returns a pointer to the element slot where an inserted element should be written, and ok if it returned a valid slot. PutSlot returns ok false if the table was split and the Map needs to find the new table. hash must be the hash of key.

func (t *table) PutSlot(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool)

Used method #

func (m *Map) Used() uint64

Used method #

func (t *table) Used() uint64

alignUp function #

alignUp rounds n up to a multiple of a. a must be a power of 2.

func alignUp(n uintptr, a uintptr) uintptr

alignUpPow2 function #

alignUpPow2 rounds n up to the next power of 2. Returns true if round up causes overflow.

func alignUpPow2(n uint64) (uint64, bool)

bitsetFirst function #

Portable implementation of first. On AMD64, this is replaced with an intrisic that simply does TrailingZeros64. There is no need to shift as the bitset is packed.

func bitsetFirst(b bitset) uintptr

bitsetLowestSet function #

Portable implementation of lowestSet. On AMD64, this is replaced with an intrisic that checks the lowest bit.

func bitsetLowestSet(b bitset) bool

bitsetRemoveBelow function #

Portable implementation of removeBelow. On AMD64, this is replaced with an intrisic that clears the lower i bits.

func bitsetRemoveBelow(b bitset, i uintptr) bitset

bitsetShiftOutLowest function #

Portable implementation of shiftOutLowest. On AMD64, this is replaced with an intrisic that shifts a single bit.

func bitsetShiftOutLowest(b bitset) bitset

checkInvariants method #

func (t *table) checkInvariants(typ *abi.SwissMapType, m *Map)

clearSmall method #

func (m *Map) clearSmall(typ *abi.SwissMapType)

ctrlGroupMatchEmpty function #

Portable implementation of matchEmpty. Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See note on bitset about the packed instrinsified return value.

func ctrlGroupMatchEmpty(g ctrlGroup) bitset

ctrlGroupMatchEmptyOrDeleted function #

Portable implementation of matchEmptyOrDeleted. Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See note on bitset about the packed instrinsified return value.

func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset

ctrlGroupMatchFull function #

Portable implementation of matchFull. Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See note on bitset about the packed instrinsified return value.

func ctrlGroupMatchFull(g ctrlGroup) bitset

ctrlGroupMatchH2 function #

Portable implementation of matchH2. Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See note on bitset about the packed instrinsified return value.

func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset

ctrls method #

ctrls returns the group control word.

func (g *groupReference) ctrls() *ctrlGroup

deleteSmall method #

func (m *Map) deleteSmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer)

depthToShift function #

func depthToShift(depth uint8) uint8

directoryAt method #

func (m *Map) directoryAt(i uintptr) *table

directoryIndex method #

func (m *Map) directoryIndex(hash uintptr) uintptr

directorySet method #

func (m *Map) directorySet(i uintptr, nt *table)

dump function #

TODO(prattmic): not in hex because print doesn't have a way to print in hex outside the runtime.

func dump(ptr unsafe.Pointer, size uintptr)

elem method #

elem returns a pointer to the element at index i.

func (g *groupReference) elem(typ *abi.SwissMapType, i uintptr) unsafe.Pointer

fatal function #

go:linkname fatal

func fatal(s string)

first method #

first returns the relative index of the first control byte in the group that is in the set. Preconditions: b is not 0 (empty).

func (b bitset) first() uintptr

get method #

get returns the i-th control byte.

func (g *ctrlGroup) get(i uintptr) ctrl

getWithKey method #

func (m *Map) getWithKey(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool)

getWithKey method #

getWithKey performs a lookup of key, returning a pointer to the version of the key in the map in addition to the element. This is relevant when multiple different key values compare equal (e.g., +0.0 and -0.0). When a grow occurs during iteration, iteration perform a lookup of keys from the old group in the new group in order to correctly expose updated elements. For NeedsKeyUpdate keys, iteration also must return the new key value, not the old key value. hash must be the hash of the key.

func (t *table) getWithKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool)

getWithKeySmall method #

func (m *Map) getWithKeySmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool)

getWithoutKey method #

func (t *table) getWithoutKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool)

getWithoutKey method #

func (m *Map) getWithoutKey(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, bool)

getWithoutKeySmallFastStr method #

func (m *Map) getWithoutKeySmallFastStr(typ *abi.SwissMapType, key string) unsafe.Pointer

group method #

group returns the group at index i.

func (g *groupsReference) group(typ *abi.SwissMapType, i uint64) groupReference

grow method #

grow the capacity of the table by allocating a new table with a bigger array and uncheckedPutting each element of the table into the new table (we know that no insertion here will Put an already-present value), and discard the old table.

func (t *table) grow(typ *abi.SwissMapType, m *Map, newCapacity uint16)

growToSmall method #

func (m *Map) growToSmall(typ *abi.SwissMapType)

growToTable method #

func (m *Map) growToTable(typ *abi.SwissMapType)

grownKeyElem method #

Return the appropriate key/elem for key at slotIdx index within it.group, if any.

func (it *Iter) grownKeyElem(key unsafe.Pointer, slotIdx uintptr) (unsafe.Pointer, unsafe.Pointer, bool)

h1 function #

Extracts the H1 portion of a hash: the 57 upper bits. TODO(prattmic): what about 32-bit systems?

func h1(h uintptr) uintptr

h2 function #

Extracts the H2 portion of a hash: the 7 bits not used for h1. These are used as an occupied control byte.

func h2(h uintptr) uintptr

installTableSplit method #

func (m *Map) installTableSplit(old *table, left *table, right *table)

key method #

key returns a pointer to the key at index i.

func (g *groupReference) key(typ *abi.SwissMapType, i uintptr) unsafe.Pointer

localDepthMask function #

Bitmask for the last selection bit at this depth.

func localDepthMask(localDepth uint8) uintptr

longStringQuickEqualityTest function #

Returns true if a and b might be equal. Returns false if a and b are definitely not equal. Requires len(a)>=8.

func longStringQuickEqualityTest(a string, b string) bool

lowestSet method #

lowestSet returns true if the bit is set for the lowest index in the bitset. This is intended for use with shiftOutLowest to loop over all entries in the bitset regardless of whether they are set.

func (b bitset) lowestSet() bool

makeProbeSeq function #

func makeProbeSeq(hash uintptr, mask uint64) probeSeq

mapKeyError function #

For testing, we don't ever need key errors.

func mapKeyError(typ *abi.SwissMapType, p unsafe.Pointer) error

mapKeyError function #

go:linkname mapKeyError

func mapKeyError(typ *abi.SwissMapType, p unsafe.Pointer) error

matchEmpty method #

matchEmpty returns the set of slots in the group that are empty.

func (g ctrlGroup) matchEmpty() bitset

matchEmptyOrDeleted method #

matchEmptyOrDeleted returns the set of slots in the group that are empty or deleted.

func (g ctrlGroup) matchEmptyOrDeleted() bitset

matchFull method #

matchFull returns the set of slots in the group that are full.

func (g ctrlGroup) matchFull() bitset

matchH2 method #

matchH2 returns the set of slots which are full and for which the 7-bit hash matches the given value. May return false positives.

func (g ctrlGroup) matchH2(h uintptr) bitset

newGroups function #

newGroups allocates a new array of length groups. Length must be a power of two.

func newGroups(typ *abi.SwissMapType, length uint64) groupsReference

newTable function #

func newTable(typ *abi.SwissMapType, capacity uint64, index int, localDepth uint8) *table

newarray function #

go:linkname newarray

func newarray(typ *abi.Type, n int) unsafe.Pointer

newobject function #

go:linkname newobject

func newobject(typ *abi.Type) unsafe.Pointer

next method #

func (s probeSeq) next() probeSeq

nextDirIdx method #

func (it *Iter) nextDirIdx()

putSlotSmall method #

func (m *Map) putSlotSmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer

putSlotSmallFast32 method #

func (m *Map) putSlotSmallFast32(typ *abi.SwissMapType, hash uintptr, key uint32) unsafe.Pointer

putSlotSmallFast64 method #

func (m *Map) putSlotSmallFast64(typ *abi.SwissMapType, hash uintptr, key uint64) unsafe.Pointer

putSlotSmallFastPtr method #

func (m *Map) putSlotSmallFastPtr(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer

putSlotSmallFastStr method #

func (m *Map) putSlotSmallFastStr(typ *abi.SwissMapType, hash uintptr, key string) unsafe.Pointer

rand function #

go:linkname rand

func rand() uint64

rehash method #

Replaces the table with one larger table or two split tables to fit more entries. Since the table is replaced, t is now stale and should not be modified.

func (t *table) rehash(typ *abi.SwissMapType, m *Map)

removeBelow method #

removeBelow clears all set bits below slot i (non-inclusive).

func (b bitset) removeBelow(i uintptr) bitset

removeFirst method #

removeFirst clears the first set bit (that is, resets the least significant set bit to 0).

func (b bitset) removeFirst() bitset

replaceTable method #

func (m *Map) replaceTable(nt *table)

reset method #

reset resets the table with new, empty groups with the specified new total capacity.

func (t *table) reset(typ *abi.SwissMapType, capacity uint16)

resetGrowthLeft method #

Preconditions: table must be empty.

func (t *table) resetGrowthLeft()

runtime_mapaccess1 function #

mapaccess1 returns a pointer to h[key]. Never returns nil, instead it will return a reference to the zero object for the elem type if the key is not in the map. NOTE: The returned pointer may keep the whole map live, so don't hold onto it for very long. go:linkname runtime_mapaccess1 runtime.mapaccess1

func runtime_mapaccess1(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer

runtime_mapaccess1_fast32 function #

go:linkname runtime_mapaccess1_fast32 runtime.mapaccess1_fast32

func runtime_mapaccess1_fast32(typ *abi.SwissMapType, m *Map, key uint32) unsafe.Pointer

runtime_mapaccess1_fast64 function #

go:linkname runtime_mapaccess1_fast64 runtime.mapaccess1_fast64

func runtime_mapaccess1_fast64(typ *abi.SwissMapType, m *Map, key uint64) unsafe.Pointer

runtime_mapaccess1_faststr function #

go:linkname runtime_mapaccess1_faststr runtime.mapaccess1_faststr

func runtime_mapaccess1_faststr(typ *abi.SwissMapType, m *Map, key string) unsafe.Pointer

runtime_mapaccess2 function #

go:linkname runtime_mapaccess2 runtime.mapaccess2

func runtime_mapaccess2(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool)

runtime_mapaccess2_fast32 function #

go:linkname runtime_mapaccess2_fast32 runtime.mapaccess2_fast32

func runtime_mapaccess2_fast32(typ *abi.SwissMapType, m *Map, key uint32) (unsafe.Pointer, bool)

runtime_mapaccess2_fast64 function #

go:linkname runtime_mapaccess2_fast64 runtime.mapaccess2_fast64

func runtime_mapaccess2_fast64(typ *abi.SwissMapType, m *Map, key uint64) (unsafe.Pointer, bool)

runtime_mapaccess2_faststr function #

go:linkname runtime_mapaccess2_faststr runtime.mapaccess2_faststr

func runtime_mapaccess2_faststr(typ *abi.SwissMapType, m *Map, key string) (unsafe.Pointer, bool)

runtime_mapassign function #

go:linkname runtime_mapassign runtime.mapassign

func runtime_mapassign(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer

runtime_mapassign_fast32 function #

go:linkname runtime_mapassign_fast32 runtime.mapassign_fast32

func runtime_mapassign_fast32(typ *abi.SwissMapType, m *Map, key uint32) unsafe.Pointer

runtime_mapassign_fast32ptr function #

Key is a 32-bit pointer (only called on 32-bit GOARCH). This source is identical to fast64ptr. TODO(prattmic): With some compiler refactoring we could avoid duplication of this function. go:linkname runtime_mapassign_fast32ptr runtime.mapassign_fast32ptr

func runtime_mapassign_fast32ptr(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer

runtime_mapassign_fast64 function #

go:linkname runtime_mapassign_fast64 runtime.mapassign_fast64

func runtime_mapassign_fast64(typ *abi.SwissMapType, m *Map, key uint64) unsafe.Pointer

runtime_mapassign_fast64ptr function #

Key is a 64-bit pointer (only called on 64-bit GOARCH). go:linkname runtime_mapassign_fast64ptr runtime.mapassign_fast64ptr

func runtime_mapassign_fast64ptr(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer

runtime_mapassign_faststr function #

go:linkname runtime_mapassign_faststr runtime.mapassign_faststr

func runtime_mapassign_faststr(typ *abi.SwissMapType, m *Map, key string) unsafe.Pointer

runtime_mapdelete_fast32 function #

go:linkname runtime_mapdelete_fast32 runtime.mapdelete_fast32

func runtime_mapdelete_fast32(typ *abi.SwissMapType, m *Map, key uint32)

runtime_mapdelete_fast64 function #

go:linkname runtime_mapdelete_fast64 runtime.mapdelete_fast64

func runtime_mapdelete_fast64(typ *abi.SwissMapType, m *Map, key uint64)

runtime_mapdelete_faststr function #

go:linkname runtime_mapdelete_faststr runtime.mapdelete_faststr

func runtime_mapdelete_faststr(typ *abi.SwissMapType, m *Map, key string)

set method #

set sets the i-th control byte.

func (g *ctrlGroup) set(i uintptr, c ctrl)

setEmpty method #

setEmpty sets all the control bytes to empty.

func (g *ctrlGroup) setEmpty()

shiftOutLowest method #

shiftOutLowest shifts the lowest entry out of the bitset. Afterwards, the lowest entry in the bitset corresponds to the next slot.

func (b bitset) shiftOutLowest() bitset

split method #

split the table into two, installing the new tables in the map directory.

func (t *table) split(typ *abi.SwissMapType, m *Map)

stringPtr function #

func stringPtr(s string) unsafe.Pointer

tombstones method #

tombstones returns the number of deleted (tombstone) entries in the table. A tombstone is a slot that has been deleted but is still considered occupied so as not to violate the probing invariant.

func (t *table) tombstones() uint16

typedmemclr function #

go:linkname typedmemclr

func typedmemclr(typ *abi.Type, ptr unsafe.Pointer)

typedmemmove function #

go:linkname typedmemmove

func typedmemmove(typ *abi.Type, dst unsafe.Pointer, src unsafe.Pointer)

uncheckedPutSlot method #

uncheckedPutSlot inserts an entry known not to be in the table. This is used for grow/split where we are making a new table from entries in an existing table. Decrements growthLeft and increments used. Requires that the entry does not exist in the table, and that the table has room for another element without rehashing. Requires that there are no deleted entries in the table. For indirect keys and/or elements, the key and elem pointers can be put directly into the map, they do not need to be copied. This requires the caller to ensure that the referenced memory never changes (by sourcing those pointers from another indirect key/elem map).

func (t *table) uncheckedPutSlot(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer, elem unsafe.Pointer)

Generated with Arrow