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