// 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 (
	
	
	
	
)

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.
	maxAvgGroupLoad = 7

	ctrlEmpty   ctrl = 0b10000000
	ctrlDeleted ctrl = 0b11111110

	bitsetLSB     = 0x0101010101010101
	bitsetMSB     = 0x8080808080808080
	bitsetEmpty   = bitsetLSB * uint64(ctrlEmpty)
	bitsetDeleted = bitsetLSB * uint64(ctrlDeleted)
)

// 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

// 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 ( bitset) () uintptr {
	return bitsetFirst()
}

// 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( bitset) uintptr {
	return uintptr(sys.TrailingZeros64(uint64())) >> 3
}

// removeFirst clears the first set bit (that is, resets the least significant
// set bit to 0).
func ( bitset) () bitset {
	return  & ( - 1)
}

// removeBelow clears all set bits below slot i (non-inclusive).
func ( bitset) ( uintptr) bitset {
	return bitsetRemoveBelow(, )
}

// Portable implementation of removeBelow.
//
// On AMD64, this is replaced with an intrisic that clears the lower i bits.
func bitsetRemoveBelow( bitset,  uintptr) bitset {
	// Clear all bits below slot i's byte.
	 := (uint64(1) << (8 * uint64())) - 1
	return  &^ bitset()
}

// 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 ( bitset) () bool {
	return bitsetLowestSet()
}

// Portable implementation of lowestSet.
//
// On AMD64, this is replaced with an intrisic that checks the lowest bit.
func bitsetLowestSet( bitset) bool {
	return &(1<<7) != 0
}

// shiftOutLowest shifts the lowest entry out of the bitset. Afterwards, the
// lowest entry in the bitset corresponds to the next slot.
func ( bitset) () bitset {
	return bitsetShiftOutLowest()
}

// Portable implementation of shiftOutLowest.
//
// On AMD64, this is replaced with an intrisic that shifts a single bit.
func bitsetShiftOutLowest( bitset) bitset {
	return  >> 8
}

// 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 is a fixed size array of abi.SwissMapGroupSlots control bytes
// stored in a uint64.
type ctrlGroup uint64

// get returns the i-th control byte.
func ( *ctrlGroup) ( uintptr) ctrl {
	if goarch.BigEndian {
		return *(*ctrl)(unsafe.Add(unsafe.Pointer(), 7-))
	}
	return *(*ctrl)(unsafe.Add(unsafe.Pointer(), ))
}

// set sets the i-th control byte.
func ( *ctrlGroup) ( uintptr,  ctrl) {
	if goarch.BigEndian {
		*(*ctrl)(unsafe.Add(unsafe.Pointer(), 7-)) = 
		return
	}
	*(*ctrl)(unsafe.Add(unsafe.Pointer(), )) = 
}

// setEmpty sets all the control bytes to empty.
func ( *ctrlGroup) () {
	* = ctrlGroup(bitsetEmpty)
}

// 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 ( ctrlGroup) ( uintptr) bitset {
	return ctrlGroupMatchH2(, )
}

// 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( ctrlGroup,  uintptr) bitset {
	// NB: This generic matching routine produces false positive matches when
	// h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For
	// example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we
	// subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be
	// considered matches of h. The false positive matches are not a problem,
	// just a rare inefficiency. Note that they only occur if there is a real
	// match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key
	// comparisons ensure that there is no correctness issue.
	 := uint64() ^ (bitsetLSB * uint64())
	return bitset((( - bitsetLSB) &^ ) & bitsetMSB)
}

// matchEmpty returns the set of slots in the group that are empty.
func ( ctrlGroup) () bitset {
	return ctrlGroupMatchEmpty()
}

// 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( ctrlGroup) bitset {
	// An empty slot is   1000 0000
	// A deleted slot is  1111 1110
	// A full slot is     0??? ????
	//
	// A slot is empty iff bit 7 is set and bit 1 is not. We could select any
	// of the other bits here (e.g. v << 1 would also work).
	 := uint64()
	return bitset(( &^ ( << 6)) & bitsetMSB)
}

// matchEmptyOrDeleted returns the set of slots in the group that are empty or
// deleted.
func ( ctrlGroup) () bitset {
	return ctrlGroupMatchEmptyOrDeleted()
}

// 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( ctrlGroup) bitset {
	// An empty slot is  1000 0000
	// A deleted slot is 1111 1110
	// A full slot is    0??? ????
	//
	// A slot is empty or deleted iff bit 7 is set.
	 := uint64()
	return bitset( & bitsetMSB)
}

// matchFull returns the set of slots in the group that are full.
func ( ctrlGroup) () bitset {
	return ctrlGroupMatchFull()
}

// 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( ctrlGroup) bitset {
	// An empty slot is  1000 0000
	// A deleted slot is 1111 1110
	// A full slot is    0??? ????
	//
	// A slot is full iff bit 7 is unset.
	 := uint64()
	return bitset(^ & bitsetMSB)
}

// 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 points to the group, which is described by typ.Group and has
	// layout:
	//
	// type group struct {
	// 	ctrls ctrlGroup
	// 	slots [abi.SwissMapGroupSlots]slot
	// }
	//
	// type slot struct {
	// 	key  typ.Key
	// 	elem typ.Elem
	// }
	data unsafe.Pointer // data *typ.Group
}

const (
	ctrlGroupsSize   = unsafe.Sizeof(ctrlGroup(0))
	groupSlotsOffset = ctrlGroupsSize
)

// alignUp rounds n up to a multiple of a. a must be a power of 2.
func alignUp(,  uintptr) uintptr {
	return ( +  - 1) &^ ( - 1)
}

// alignUpPow2 rounds n up to the next power of 2.
//
// Returns true if round up causes overflow.
func alignUpPow2( uint64) (uint64, bool) {
	if  == 0 {
		return 0, false
	}
	 := (uint64(1) << sys.Len64(-1))
	if  == 0 {
		return 0, true
	}
	return , false
}

// ctrls returns the group control word.
func ( *groupReference) () *ctrlGroup {
	return (*ctrlGroup)(.data)
}

// key returns a pointer to the key at index i.
func ( *groupReference) ( *abi.SwissMapType,  uintptr) unsafe.Pointer {
	 := groupSlotsOffset + *.SlotSize

	return unsafe.Pointer(uintptr(.data) + )
}

// elem returns a pointer to the element at index i.
func ( *groupReference) ( *abi.SwissMapType,  uintptr) unsafe.Pointer {
	 := groupSlotsOffset + *.SlotSize + .ElemOff

	return unsafe.Pointer(uintptr(.data) + )
}

// groupsReference is a wrapper type describing an array of groups stored at
// data.
type groupsReference struct {
	// data points to an array of groups. See groupReference above for the
	// definition of group.
	data unsafe.Pointer // data *[length]typ.Group

	// lengthMask is the number of groups in data minus one (note that
	// length must be a power of two). This allows computing i%length
	// quickly using bitwise AND.
	lengthMask uint64
}

// newGroups allocates a new array of length groups.
//
// Length must be a power of two.
func newGroups( *abi.SwissMapType,  uint64) groupsReference {
	return groupsReference{
		// TODO: make the length type the same throughout.
		data:       newarray(.Group, int()),
		lengthMask:  - 1,
	}
}

// group returns the group at index i.
func ( *groupsReference) ( *abi.SwissMapType,  uint64) groupReference {
	// TODO(prattmic): Do something here about truncation on cast to
	// uintptr on 32-bit systems?
	 := uintptr() * .GroupSize

	return groupReference{
		data: unsafe.Pointer(uintptr(.data) + ),
	}
}