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  func newTestMapType[K comparable, V any]() *abi.MapType {
    26  	var m map[K]V
    27  	mTyp := abi.TypeOf(m)
    28  	mt := (*abi.MapType)(unsafe.Pointer(mTyp))
    29  	return mt
    30  }
    31  
    32  func NewTestMap[K comparable, V any](hint uintptr) (*Map, *abi.MapType) {
    33  	mt := newTestMapType[K, V]()
    34  	return NewMap(mt, hint, nil, maxAllocTest), mt
    35  }
    36  
    37  func (m *Map) TableCount() int {
    38  	if m.dirLen <= 0 {
    39  		return 0
    40  	}
    41  	return m.dirLen
    42  }
    43  
    44  // Total group count, summed across all tables.
    45  func (m *Map) GroupCount() uint64 {
    46  	if m.dirLen <= 0 {
    47  		if m.dirPtr == nil {
    48  			return 0
    49  		}
    50  		return 1
    51  	}
    52  
    53  	var n uint64
    54  	var lastTab *table
    55  	for i := range m.dirLen {
    56  		t := m.directoryAt(uintptr(i))
    57  		if t == lastTab {
    58  			continue
    59  		}
    60  		lastTab = t
    61  		n += t.groups.lengthMask + 1
    62  	}
    63  	return n
    64  }
    65  
    66  // Return a key from a group containing no empty slots.
    67  //
    68  // Returns nil if there are no full groups.
    69  // Returns nil if a group is full but contains entirely deleted slots.
    70  // Returns nil if the map is small.
    71  func (m *Map) KeyFromFullGroup(typ *abi.MapType) unsafe.Pointer {
    72  	if m.dirLen <= 0 {
    73  		return nil
    74  	}
    75  
    76  	var lastTab *table
    77  	for i := range m.dirLen {
    78  		t := m.directoryAt(uintptr(i))
    79  		if t == lastTab {
    80  			continue
    81  		}
    82  		lastTab = t
    83  
    84  		for i := uint64(0); i <= t.groups.lengthMask; i++ {
    85  			g := t.groups.group(typ, i)
    86  			match := g.ctrls().matchEmpty()
    87  			if match != 0 {
    88  				continue
    89  			}
    90  
    91  			// All full or deleted slots.
    92  			for j := uintptr(0); j < abi.MapGroupSlots; j++ {
    93  				if g.ctrls().get(j) == ctrlDeleted {
    94  					continue
    95  				}
    96  				slotKey := g.key(typ, j)
    97  				if typ.IndirectKey() {
    98  					slotKey = *((*unsafe.Pointer)(slotKey))
    99  				}
   100  				return slotKey
   101  			}
   102  		}
   103  	}
   104  
   105  	return nil
   106  }
   107  
   108  // Returns nil if the map is small.
   109  func (m *Map) TableFor(typ *abi.MapType, key unsafe.Pointer) *table {
   110  	if m.dirLen <= 0 {
   111  		return nil
   112  	}
   113  
   114  	hash := typ.Hasher(key, m.seed)
   115  	idx := m.directoryIndex(hash)
   116  	return m.directoryAt(idx)
   117  }
   118  
   119  func (t *table) GrowthLeft() uint64 {
   120  	return uint64(t.growthLeft)
   121  }
   122  
   123  // Returns the start address of the groups array.
   124  func (t *table) GroupsStart() unsafe.Pointer {
   125  	return t.groups.data
   126  }
   127  
   128  // Returns the length of the groups array.
   129  func (t *table) GroupsLength() uintptr {
   130  	return uintptr(t.groups.lengthMask + 1)
   131  }
   132
View as plain text