group.go

     1  // Copyright 2024 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package maps
     6  
     7  import (
     8  	"internal/abi"
     9  	"internal/goarch"
    10  	"internal/runtime/sys"
    11  	"unsafe"
    12  )
    13  
    14  const (
    15  	// Maximum load factor prior to growing.
    16  	//
    17  	// 7/8 is the same load factor used by Abseil, but Abseil defaults to
    18  	// 16 slots per group, so they get two empty slots vs our one empty
    19  	// slot. We may want to reevaluate if this is best for us.
    20  	maxAvgGroupLoad = 7
    21  
    22  	ctrlEmpty   ctrl = 0b10000000
    23  	ctrlDeleted ctrl = 0b11111110
    24  
    25  	bitsetLSB     = 0x0101010101010101
    26  	bitsetMSB     = 0x8080808080808080
    27  	bitsetEmpty   = bitsetLSB * uint64(ctrlEmpty)
    28  	bitsetDeleted = bitsetLSB * uint64(ctrlDeleted)
    29  )
    30  
    31  // bitset represents a set of slots within a group.
    32  //
    33  // The underlying representation uses one byte per slot, where each byte is
    34  // either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it
    35  // convenient to calculate for an entire group at once (e.g. see matchEmpty).
    36  type bitset uint64
    37  
    38  // first assumes that only the MSB of each control byte can be set (e.g. bitset
    39  // is the result of matchEmpty or similar) and returns the relative index of the
    40  // first control byte in the group that has the MSB set.
    41  //
    42  // Returns abi.SwissMapGroupSlots if the bitset is empty.
    43  func (b bitset) first() uintptr {
    44  	return uintptr(sys.TrailingZeros64(uint64(b))) >> 3
    45  }
    46  
    47  // removeFirst removes the first set bit (that is, resets the least significant
    48  // set bit to 0).
    49  func (b bitset) removeFirst() bitset {
    50  	return b & (b - 1)
    51  }
    52  
    53  // removeBelow removes all set bits below slot i (non-inclusive).
    54  func (b bitset) removeBelow(i uintptr) bitset {
    55  	// Clear all bits below slot i's byte.
    56  	mask := (uint64(1) << (8*uint64(i))) - 1
    57  	return b &^ bitset(mask)
    58  }
    59  
    60  // Each slot in the hash table has a control byte which can have one of three
    61  // states: empty, deleted, and full. They have the following bit patterns:
    62  //
    63  //	  empty: 1 0 0 0 0 0 0 0
    64  //	deleted: 1 1 1 1 1 1 1 0
    65  //	   full: 0 h h h h h h h  // h represents the H1 hash bits
    66  //
    67  // TODO(prattmic): Consider inverting the top bit so that the zero value is empty.
    68  type ctrl uint8
    69  
    70  // ctrlGroup is a fixed size array of abi.SwissMapGroupSlots control bytes
    71  // stored in a uint64.
    72  type ctrlGroup uint64
    73  
    74  // get returns the i-th control byte.
    75  func (g *ctrlGroup) get(i uintptr) ctrl {
    76  	if goarch.BigEndian {
    77  		return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i))
    78  	}
    79  	return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i))
    80  }
    81  
    82  // set sets the i-th control byte.
    83  func (g *ctrlGroup) set(i uintptr, c ctrl) {
    84  	if goarch.BigEndian {
    85  		*(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i)) = c
    86  		return
    87  	}
    88  	*(*ctrl)(unsafe.Add(unsafe.Pointer(g), i)) = c
    89  }
    90  
    91  // setEmpty sets all the control bytes to empty.
    92  func (g *ctrlGroup) setEmpty() {
    93  	*g = ctrlGroup(bitsetEmpty)
    94  }
    95  
    96  // matchH2 returns the set of slots which are full and for which the 7-bit hash
    97  // matches the given value. May return false positives.
    98  func (g ctrlGroup) matchH2(h uintptr) bitset {
    99  	// NB: This generic matching routine produces false positive matches when
   100  	// h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For
   101  	// example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we
   102  	// subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be
   103  	// considered matches of h. The false positive matches are not a problem,
   104  	// just a rare inefficiency. Note that they only occur if there is a real
   105  	// match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key
   106  	// comparisons ensure that there is no correctness issue.
   107  	v := uint64(g) ^ (bitsetLSB * uint64(h))
   108  	return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)
   109  }
   110  
   111  // matchEmpty returns the set of slots in the group that are empty.
   112  func (g ctrlGroup) matchEmpty() bitset {
   113  	// An empty slot is   1000 0000
   114  	// A deleted slot is  1111 1110
   115  	// A full slot is     0??? ????
   116  	//
   117  	// A slot is empty iff bit 7 is set and bit 1 is not. We could select any
   118  	// of the other bits here (e.g. v << 1 would also work).
   119  	v := uint64(g)
   120  	return bitset((v &^ (v << 6)) & bitsetMSB)
   121  }
   122  
   123  // matchEmptyOrDeleted returns the set of slots in the group that are empty or
   124  // deleted.
   125  func (g ctrlGroup) matchEmptyOrDeleted() bitset {
   126  	// An empty slot is  1000 0000
   127  	// A deleted slot is 1111 1110
   128  	// A full slot is    0??? ????
   129  	//
   130  	// A slot is empty or deleted iff bit 7 is set.
   131  	v := uint64(g)
   132  	return bitset(v & bitsetMSB)
   133  }
   134  
   135  // matchFull returns the set of slots in the group that are full.
   136  func (g ctrlGroup) matchFull() bitset {
   137  	// An empty slot is  1000 0000
   138  	// A deleted slot is 1111 1110
   139  	// A full slot is    0??? ????
   140  	//
   141  	// A slot is full iff bit 7 is unset.
   142  	v := uint64(g)
   143  	return bitset(^v & bitsetMSB)
   144  }
   145  
   146  // groupReference is a wrapper type representing a single slot group stored at
   147  // data.
   148  //
   149  // A group holds abi.SwissMapGroupSlots slots (key/elem pairs) plus their
   150  // control word.
   151  type groupReference struct {
   152  	// data points to the group, which is described by typ.Group and has
   153  	// layout:
   154  	//
   155  	// type group struct {
   156  	// 	ctrls ctrlGroup
   157  	// 	slots [abi.SwissMapGroupSlots]slot
   158  	// }
   159  	//
   160  	// type slot struct {
   161  	// 	key  typ.Key
   162  	// 	elem typ.Elem
   163  	// }
   164  	data unsafe.Pointer // data *typ.Group
   165  }
   166  
   167  const (
   168  	ctrlGroupsSize   = unsafe.Sizeof(ctrlGroup(0))
   169  	groupSlotsOffset = ctrlGroupsSize
   170  )
   171  
   172  // alignUp rounds n up to a multiple of a. a must be a power of 2.
   173  func alignUp(n, a uintptr) uintptr {
   174  	return (n + a - 1) &^ (a - 1)
   175  }
   176  
   177  // alignUpPow2 rounds n up to the next power of 2.
   178  //
   179  // Returns true if round up causes overflow.
   180  func alignUpPow2(n uint64) (uint64, bool) {
   181  	if n == 0 {
   182  		return 0, false
   183  	}
   184  	v := (uint64(1) << sys.Len64(n-1))
   185  	if v == 0 {
   186  		return 0, true
   187  	}
   188  	return v, false
   189  }
   190  
   191  // ctrls returns the group control word.
   192  func (g *groupReference) ctrls() *ctrlGroup {
   193  	return (*ctrlGroup)(g.data)
   194  }
   195  
   196  // key returns a pointer to the key at index i.
   197  func (g *groupReference) key(typ *abi.SwissMapType, i uintptr) unsafe.Pointer {
   198  	offset := groupSlotsOffset + i*typ.SlotSize
   199  
   200  	return unsafe.Pointer(uintptr(g.data) + offset)
   201  }
   202  
   203  // elem returns a pointer to the element at index i.
   204  func (g *groupReference) elem(typ *abi.SwissMapType, i uintptr) unsafe.Pointer {
   205  	offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff
   206  
   207  	return unsafe.Pointer(uintptr(g.data) + offset)
   208  }
   209  
   210  // groupsReference is a wrapper type describing an array of groups stored at
   211  // data.
   212  type groupsReference struct {
   213  	// data points to an array of groups. See groupReference above for the
   214  	// definition of group.
   215  	data unsafe.Pointer // data *[length]typ.Group
   216  
   217  	// lengthMask is the number of groups in data minus one (note that
   218  	// length must be a power of two). This allows computing i%length
   219  	// quickly using bitwise AND.
   220  	lengthMask uint64
   221  
   222  	// entryMask is the total number of slots in the groups minus one.
   223  	entryMask uint64
   224  }
   225  
   226  // newGroups allocates a new array of length groups.
   227  //
   228  // Length must be a power of two.
   229  func newGroups(typ *abi.SwissMapType, length uint64) groupsReference {
   230  	return groupsReference{
   231  		// TODO: make the length type the same throughout.
   232  		data:       newarray(typ.Group, int(length)),
   233  		lengthMask: length - 1,
   234  		entryMask:  (length * abi.SwissMapGroupSlots) - 1,
   235  	}
   236  }
   237  
   238  // group returns the group at index i.
   239  func (g *groupsReference) group(typ *abi.SwissMapType, i uint64) groupReference {
   240  	// TODO(prattmic): Do something here about truncation on cast to
   241  	// uintptr on 32-bit systems?
   242  	offset := uintptr(i) * typ.Group.Size_
   243  
   244  	return groupReference{
   245  		data: unsafe.Pointer(uintptr(g.data) + offset),
   246  	}
   247  }
   248
View as plain text