Source file src/internal/runtime/maps/map_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_test
     6  
     7  import (
     8  	"fmt"
     9  	"internal/abi"
    10  	"internal/runtime/maps"
    11  	"math"
    12  	"testing"
    13  	"unsafe"
    14  )
    15  
    16  func TestCtrlSize(t *testing.T) {
    17  	cs := unsafe.Sizeof(maps.CtrlGroup(0))
    18  	if cs != abi.MapGroupSlots {
    19  		t.Errorf("ctrlGroup size got %d want abi.MapGroupSlots %d", cs, abi.MapGroupSlots)
    20  	}
    21  }
    22  
    23  func TestMapPut(t *testing.T) {
    24  	m, typ := maps.NewTestMap[uint32, uint64](8)
    25  
    26  	key := uint32(0)
    27  	elem := uint64(256 + 0)
    28  
    29  	for i := 0; i < 31; i++ {
    30  		key += 1
    31  		elem += 1
    32  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
    33  
    34  		if maps.DebugLog {
    35  			fmt.Printf("After put %d: %v\n", key, m)
    36  		}
    37  	}
    38  
    39  	if m.Used() != 31 {
    40  		t.Errorf("Used() used got %d want 31", m.Used())
    41  	}
    42  
    43  	key = uint32(0)
    44  	elem = uint64(256 + 0)
    45  
    46  	for i := 0; i < 31; i++ {
    47  		key += 1
    48  		elem += 1
    49  		got, ok := m.Get(typ, unsafe.Pointer(&key))
    50  		if !ok {
    51  			t.Errorf("Get(%d) got ok false want true", key)
    52  		}
    53  		gotElem := *(*uint64)(got)
    54  		if gotElem != elem {
    55  			t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
    56  		}
    57  	}
    58  }
    59  
    60  func TestSmallMapGrow(t *testing.T) {
    61  	m, typ := maps.NewTestMap[uint32, uint64](8)
    62  
    63  	key := uint32(0)
    64  	elem := uint64(256 + 0)
    65  
    66  	for i := 0; i < 8; i++ {
    67  		key += 1
    68  		elem += 1
    69  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
    70  
    71  		if maps.DebugLog {
    72  			fmt.Printf("After put %d: %v\n", key, m)
    73  		}
    74  	}
    75  
    76  	if m.TableCount() != 0 {
    77  		t.Errorf("TableCount() got %d want 0", m.TableCount())
    78  	}
    79  
    80  	key = uint32(0)
    81  	elem = uint64(256 + 10)
    82  
    83  	for i := 0; i < 8; i++ {
    84  		key += 1
    85  		elem += 1
    86  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
    87  
    88  		if maps.DebugLog {
    89  			fmt.Printf("After put %d: %v\n", key, m)
    90  		}
    91  	}
    92  
    93  	if m.TableCount() != 0 {
    94  		t.Errorf("TableCount() got %d want 0", m.TableCount())
    95  	}
    96  
    97  	key += 1
    98  	elem += 1
    99  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   100  
   101  	if maps.DebugLog {
   102  		fmt.Printf("After put %d: %v\n", key, m)
   103  	}
   104  
   105  	if m.TableCount() != 1 {
   106  		t.Errorf("TableCount() got %d want 1", m.TableCount())
   107  	}
   108  }
   109  
   110  // Grow enough to cause a table split.
   111  func TestMapSplit(t *testing.T) {
   112  	m, typ := maps.NewTestMap[uint32, uint64](0)
   113  
   114  	key := uint32(0)
   115  	elem := uint64(256 + 0)
   116  
   117  	for i := 0; i < 2*maps.MaxTableCapacity; i++ {
   118  		key += 1
   119  		elem += 1
   120  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   121  
   122  		if maps.DebugLog {
   123  			fmt.Printf("After put %d: %v\n", key, m)
   124  		}
   125  	}
   126  
   127  	if m.Used() != 2*maps.MaxTableCapacity {
   128  		t.Errorf("Used() used got %d want 31", m.Used())
   129  	}
   130  
   131  	key = uint32(0)
   132  	elem = uint64(256 + 0)
   133  
   134  	for i := 0; i < 2*maps.MaxTableCapacity; i++ {
   135  		key += 1
   136  		elem += 1
   137  		got, ok := m.Get(typ, unsafe.Pointer(&key))
   138  		if !ok {
   139  			t.Errorf("Get(%d) got ok false want true", key)
   140  		}
   141  		gotElem := *(*uint64)(got)
   142  		if gotElem != elem {
   143  			t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
   144  		}
   145  	}
   146  }
   147  
   148  func TestMapDelete(t *testing.T) {
   149  	m, typ := maps.NewTestMap[uint32, uint64](32)
   150  
   151  	key := uint32(0)
   152  	elem := uint64(256 + 0)
   153  
   154  	for i := 0; i < 31; i++ {
   155  		key += 1
   156  		elem += 1
   157  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   158  
   159  		if maps.DebugLog {
   160  			fmt.Printf("After put %d: %v\n", key, m)
   161  		}
   162  	}
   163  
   164  	key = uint32(0)
   165  	elem = uint64(256 + 0)
   166  
   167  	for i := 0; i < 31; i++ {
   168  		key += 1
   169  		m.Delete(typ, unsafe.Pointer(&key))
   170  	}
   171  
   172  	if m.Used() != 0 {
   173  		t.Errorf("Used() used got %d want 0", m.Used())
   174  	}
   175  
   176  	key = uint32(0)
   177  	elem = uint64(256 + 0)
   178  
   179  	for i := 0; i < 31; i++ {
   180  		key += 1
   181  		elem += 1
   182  		_, ok := m.Get(typ, unsafe.Pointer(&key))
   183  		if ok {
   184  			t.Errorf("Get(%d) got ok true want false", key)
   185  		}
   186  	}
   187  }
   188  
   189  func TestTableClear(t *testing.T) {
   190  	m, typ := maps.NewTestMap[uint32, uint64](32)
   191  
   192  	key := uint32(0)
   193  	elem := uint64(256 + 0)
   194  
   195  	for i := 0; i < 31; i++ {
   196  		key += 1
   197  		elem += 1
   198  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   199  
   200  		if maps.DebugLog {
   201  			fmt.Printf("After put %d: %v\n", key, m)
   202  		}
   203  	}
   204  
   205  	m.Clear(typ)
   206  
   207  	if m.Used() != 0 {
   208  		t.Errorf("Clear() used got %d want 0", m.Used())
   209  	}
   210  
   211  	key = uint32(0)
   212  	elem = uint64(256 + 0)
   213  
   214  	for i := 0; i < 31; i++ {
   215  		key += 1
   216  		elem += 1
   217  		_, ok := m.Get(typ, unsafe.Pointer(&key))
   218  		if ok {
   219  			t.Errorf("Get(%d) got ok true want false", key)
   220  		}
   221  	}
   222  }
   223  
   224  // +0.0 and -0.0 compare equal, but we must still must update the key slot when
   225  // overwriting.
   226  func TestTableKeyUpdate(t *testing.T) {
   227  	m, typ := maps.NewTestMap[float64, uint64](8)
   228  
   229  	zero := float64(0.0)
   230  	negZero := math.Copysign(zero, -1.0)
   231  	elem := uint64(0)
   232  
   233  	m.Put(typ, unsafe.Pointer(&zero), unsafe.Pointer(&elem))
   234  	if maps.DebugLog {
   235  		fmt.Printf("After put %f: %v\n", zero, m)
   236  	}
   237  
   238  	elem = 1
   239  	m.Put(typ, unsafe.Pointer(&negZero), unsafe.Pointer(&elem))
   240  	if maps.DebugLog {
   241  		fmt.Printf("After put %f: %v\n", negZero, m)
   242  	}
   243  
   244  	if m.Used() != 1 {
   245  		t.Errorf("Used() used got %d want 1", m.Used())
   246  	}
   247  
   248  	it := new(maps.Iter)
   249  	it.Init(typ, m)
   250  	it.Next()
   251  	keyPtr, elemPtr := it.Key(), it.Elem()
   252  	if keyPtr == nil {
   253  		t.Fatal("it.Key() got nil want key")
   254  	}
   255  
   256  	key := *(*float64)(keyPtr)
   257  	elem = *(*uint64)(elemPtr)
   258  	if math.Copysign(1.0, key) > 0 {
   259  		t.Errorf("map key %f has positive sign", key)
   260  	}
   261  	if elem != 1 {
   262  		t.Errorf("map elem got %d want 1", elem)
   263  	}
   264  }
   265  
   266  // Put should reuse a deleted slot rather than consuming an empty slot.
   267  func TestTablePutDelete(t *testing.T) {
   268  	// Put will reuse the first deleted slot it encounters.
   269  	//
   270  	// This is awkward to test because Delete will only install ctrlDeleted
   271  	// if the group is full, otherwise it goes straight to empty.
   272  	//
   273  	// So first we must add to the table continuously until we happen to
   274  	// fill a group.
   275  
   276  	// Avoid small maps, they have no tables.
   277  	m, typ := maps.NewTestMap[uint32, uint32](16)
   278  
   279  	key := uint32(0)
   280  	elem := uint32(256 + 0)
   281  
   282  	for {
   283  		key += 1
   284  		elem += 1
   285  
   286  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   287  
   288  		// Normally a Put that fills a group would fill it with the
   289  		// inserted key, so why search the whole map for a potentially
   290  		// different key in a full group?
   291  		//
   292  		// Put may grow/split a table. Initial construction of the new
   293  		// table(s) could result in a full group consisting of
   294  		// arbitrary keys.
   295  		fullKeyPtr := m.KeyFromFullGroup(typ)
   296  		if fullKeyPtr != nil {
   297  			// Found a full group.
   298  			key = *(*uint32)(fullKeyPtr)
   299  			elem = 256 + key
   300  			break
   301  		}
   302  	}
   303  
   304  	// Key is in a full group. Deleting it will result in a ctrlDeleted
   305  	// slot.
   306  	m.Delete(typ, unsafe.Pointer(&key))
   307  
   308  	// Re-insert key. This should reuse the deleted slot rather than
   309  	// consuming space.
   310  	tabWant := m.TableFor(typ, unsafe.Pointer(&key))
   311  	growthLeftWant := tabWant.GrowthLeft()
   312  
   313  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   314  
   315  	tabGot := m.TableFor(typ, unsafe.Pointer(&key))
   316  	growthLeftGot := tabGot.GrowthLeft()
   317  
   318  	if tabGot != tabWant {
   319  		// There shouldn't be a grow, as replacing a deleted slot
   320  		// doesn't require more space.
   321  		t.Errorf("Put(%d) grew table got %v want %v map %v", key, tabGot, tabWant, m)
   322  	}
   323  
   324  	if growthLeftGot != growthLeftWant {
   325  		t.Errorf("GrowthLeft got %d want %d: map %v tab %v", growthLeftGot, growthLeftWant, m, tabGot)
   326  	}
   327  }
   328  
   329  func TestTableIteration(t *testing.T) {
   330  	m, typ := maps.NewTestMap[uint32, uint64](8)
   331  
   332  	key := uint32(0)
   333  	elem := uint64(256 + 0)
   334  
   335  	for i := 0; i < 31; i++ {
   336  		key += 1
   337  		elem += 1
   338  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   339  
   340  		if maps.DebugLog {
   341  			fmt.Printf("After put %d: %v\n", key, m)
   342  		}
   343  	}
   344  
   345  	got := make(map[uint32]uint64)
   346  
   347  	it := new(maps.Iter)
   348  	it.Init(typ, m)
   349  	for {
   350  		it.Next()
   351  		keyPtr, elemPtr := it.Key(), it.Elem()
   352  		if keyPtr == nil {
   353  			break
   354  		}
   355  
   356  		key := *(*uint32)(keyPtr)
   357  		elem := *(*uint64)(elemPtr)
   358  		got[key] = elem
   359  	}
   360  
   361  	if len(got) != 31 {
   362  		t.Errorf("Iteration got %d entries, want 31: %+v", len(got), got)
   363  	}
   364  
   365  	key = uint32(0)
   366  	elem = uint64(256 + 0)
   367  
   368  	for i := 0; i < 31; i++ {
   369  		key += 1
   370  		elem += 1
   371  		gotElem, ok := got[key]
   372  		if !ok {
   373  			t.Errorf("Iteration missing key %d", key)
   374  			continue
   375  		}
   376  		if gotElem != elem {
   377  			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
   378  		}
   379  	}
   380  }
   381  
   382  // Deleted keys shouldn't be visible in iteration.
   383  func TestTableIterationDelete(t *testing.T) {
   384  	m, typ := maps.NewTestMap[uint32, uint64](8)
   385  
   386  	key := uint32(0)
   387  	elem := uint64(256 + 0)
   388  
   389  	for i := 0; i < 31; i++ {
   390  		key += 1
   391  		elem += 1
   392  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   393  
   394  		if maps.DebugLog {
   395  			fmt.Printf("After put %d: %v\n", key, m)
   396  		}
   397  	}
   398  
   399  	got := make(map[uint32]uint64)
   400  	first := true
   401  	deletedKey := uint32(1)
   402  	it := new(maps.Iter)
   403  	it.Init(typ, m)
   404  	for {
   405  		it.Next()
   406  		keyPtr, elemPtr := it.Key(), it.Elem()
   407  		if keyPtr == nil {
   408  			break
   409  		}
   410  
   411  		key := *(*uint32)(keyPtr)
   412  		elem := *(*uint64)(elemPtr)
   413  		got[key] = elem
   414  
   415  		if first {
   416  			first = false
   417  
   418  			// If the key we intended to delete was the one we just
   419  			// saw, pick another to delete.
   420  			if key == deletedKey {
   421  				deletedKey++
   422  			}
   423  			m.Delete(typ, unsafe.Pointer(&deletedKey))
   424  		}
   425  	}
   426  
   427  	if len(got) != 30 {
   428  		t.Errorf("Iteration got %d entries, want 30: %+v", len(got), got)
   429  	}
   430  
   431  	key = uint32(0)
   432  	elem = uint64(256 + 0)
   433  
   434  	for i := 0; i < 31; i++ {
   435  		key += 1
   436  		elem += 1
   437  
   438  		wantOK := true
   439  		if key == deletedKey {
   440  			wantOK = false
   441  		}
   442  
   443  		gotElem, gotOK := got[key]
   444  		if gotOK != wantOK {
   445  			t.Errorf("Iteration key %d got ok %v want ok %v", key, gotOK, wantOK)
   446  			continue
   447  		}
   448  		if wantOK && gotElem != elem {
   449  			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
   450  		}
   451  	}
   452  }
   453  
   454  // Deleted keys shouldn't be visible in iteration even after a grow.
   455  func TestTableIterationGrowDelete(t *testing.T) {
   456  	m, typ := maps.NewTestMap[uint32, uint64](8)
   457  
   458  	key := uint32(0)
   459  	elem := uint64(256 + 0)
   460  
   461  	for i := 0; i < 31; i++ {
   462  		key += 1
   463  		elem += 1
   464  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   465  
   466  		if maps.DebugLog {
   467  			fmt.Printf("After put %d: %v\n", key, m)
   468  		}
   469  	}
   470  
   471  	got := make(map[uint32]uint64)
   472  	first := true
   473  	deletedKey := uint32(1)
   474  	it := new(maps.Iter)
   475  	it.Init(typ, m)
   476  	for {
   477  		it.Next()
   478  		keyPtr, elemPtr := it.Key(), it.Elem()
   479  		if keyPtr == nil {
   480  			break
   481  		}
   482  
   483  		key := *(*uint32)(keyPtr)
   484  		elem := *(*uint64)(elemPtr)
   485  		got[key] = elem
   486  
   487  		if first {
   488  			first = false
   489  
   490  			// If the key we intended to delete was the one we just
   491  			// saw, pick another to delete.
   492  			if key == deletedKey {
   493  				deletedKey++
   494  			}
   495  
   496  			// Double the number of elements to force a grow.
   497  			key := uint32(32)
   498  			elem := uint64(256 + 32)
   499  
   500  			for i := 0; i < 31; i++ {
   501  				key += 1
   502  				elem += 1
   503  				m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   504  
   505  				if maps.DebugLog {
   506  					fmt.Printf("After put %d: %v\n", key, m)
   507  				}
   508  			}
   509  
   510  			// Then delete from the grown map.
   511  			m.Delete(typ, unsafe.Pointer(&deletedKey))
   512  		}
   513  	}
   514  
   515  	// Don't check length: the number of new elements we'll see is
   516  	// unspecified.
   517  
   518  	// Check values only of the original pre-iteration entries.
   519  	key = uint32(0)
   520  	elem = uint64(256 + 0)
   521  
   522  	for i := 0; i < 31; i++ {
   523  		key += 1
   524  		elem += 1
   525  
   526  		wantOK := true
   527  		if key == deletedKey {
   528  			wantOK = false
   529  		}
   530  
   531  		gotElem, gotOK := got[key]
   532  		if gotOK != wantOK {
   533  			t.Errorf("Iteration key %d got ok %v want ok %v", key, gotOK, wantOK)
   534  			continue
   535  		}
   536  		if wantOK && gotElem != elem {
   537  			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
   538  		}
   539  	}
   540  }
   541  
   542  func testTableIterationGrowDuplicate(t *testing.T, grow int) {
   543  	m, typ := maps.NewTestMap[uint32, uint64](8)
   544  
   545  	key := uint32(0)
   546  	elem := uint64(256 + 0)
   547  
   548  	for i := 0; i < 31; i++ {
   549  		key += 1
   550  		elem += 1
   551  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   552  
   553  		if maps.DebugLog {
   554  			fmt.Printf("After put %d: %v\n", key, m)
   555  		}
   556  	}
   557  
   558  	got := make(map[uint32]uint64)
   559  	it := new(maps.Iter)
   560  	it.Init(typ, m)
   561  	for i := 0; ; i++ {
   562  		it.Next()
   563  		keyPtr, elemPtr := it.Key(), it.Elem()
   564  		if keyPtr == nil {
   565  			break
   566  		}
   567  
   568  		key := *(*uint32)(keyPtr)
   569  		elem := *(*uint64)(elemPtr)
   570  		if elem != 256+uint64(key) {
   571  			t.Errorf("iteration got key %d elem %d want elem %d", key, elem, 256+uint64(key))
   572  		}
   573  		if _, ok := got[key]; ok {
   574  			t.Errorf("iteration got key %d more than once", key)
   575  		}
   576  		got[key] = elem
   577  
   578  		// Grow halfway through iteration.
   579  		if i == 16 {
   580  			key := uint32(32)
   581  			elem := uint64(256 + 32)
   582  
   583  			for i := 0; i < grow; i++ {
   584  				key += 1
   585  				elem += 1
   586  				m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   587  
   588  				if maps.DebugLog {
   589  					fmt.Printf("After put %d: %v\n", key, m)
   590  				}
   591  			}
   592  		}
   593  	}
   594  
   595  	// Don't check length: the number of new elements we'll see is
   596  	// unspecified.
   597  }
   598  
   599  // Grow should not allow duplicate keys to appear.
   600  func TestTableIterationGrowDuplicate(t *testing.T) {
   601  	// Small grow, only enough to cause table grow.
   602  	t.Run("grow", func(t *testing.T) { testTableIterationGrowDuplicate(t, 32) })
   603  
   604  	// Large grow, to cause table split.
   605  	t.Run("split", func(t *testing.T) { testTableIterationGrowDuplicate(t, 2*maps.MaxTableCapacity) })
   606  }
   607  
   608  func TestAlignUpPow2(t *testing.T) {
   609  	tests := []struct {
   610  		in       uint64
   611  		want     uint64
   612  		overflow bool
   613  	}{
   614  		{
   615  			in:   0,
   616  			want: 0,
   617  		},
   618  		{
   619  			in:   3,
   620  			want: 4,
   621  		},
   622  		{
   623  			in:   4,
   624  			want: 4,
   625  		},
   626  		{
   627  			in:   1 << 63,
   628  			want: 1 << 63,
   629  		},
   630  		{
   631  			in:   (1 << 63) - 1,
   632  			want: 1 << 63,
   633  		},
   634  		{
   635  			in:       (1 << 63) + 1,
   636  			overflow: true,
   637  		},
   638  	}
   639  
   640  	for _, tc := range tests {
   641  		got, overflow := maps.AlignUpPow2(tc.in)
   642  		if got != tc.want {
   643  			t.Errorf("alignUpPow2(%d) got %d, want %d", tc.in, got, tc.want)
   644  		}
   645  		if overflow != tc.overflow {
   646  			t.Errorf("alignUpPow2(%d) got overflow %v, want %v", tc.in, overflow, tc.overflow)
   647  		}
   648  	}
   649  }
   650  
   651  // Verify that a map with zero-size slot is safe to use.
   652  func TestMapZeroSizeSlot(t *testing.T) {
   653  	m, typ := maps.NewTestMap[struct{}, struct{}](16)
   654  
   655  	key := struct{}{}
   656  	elem := struct{}{}
   657  
   658  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   659  
   660  	if maps.DebugLog {
   661  		fmt.Printf("After put %d: %v\n", key, m)
   662  	}
   663  
   664  	got, ok := m.Get(typ, unsafe.Pointer(&key))
   665  	if !ok {
   666  		t.Errorf("Get(%d) got ok false want true", key)
   667  	}
   668  	gotElem := *(*struct{})(got)
   669  	if gotElem != elem {
   670  		t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
   671  	}
   672  
   673  	tab := m.TableFor(typ, unsafe.Pointer(&key))
   674  	start := tab.GroupsStart()
   675  	length := tab.GroupsLength()
   676  	end := unsafe.Pointer(uintptr(start) + length*typ.GroupSize - 1) // inclusive to ensure we have a valid pointer
   677  	if uintptr(got) < uintptr(start) || uintptr(got) > uintptr(end) {
   678  		t.Errorf("elem address outside groups allocation; got %p want [%p, %p]", got, start, end)
   679  	}
   680  }
   681  
   682  func TestMapIndirect(t *testing.T) {
   683  	type big [abi.MapMaxKeyBytes + abi.MapMaxElemBytes]byte
   684  
   685  	m, typ := maps.NewTestMap[big, big](8)
   686  
   687  	key := big{}
   688  	elem := big{}
   689  	elem[0] = 128
   690  
   691  	for i := 0; i < 31; i++ {
   692  		key[0] += 1
   693  		elem[0] += 1
   694  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   695  
   696  		if maps.DebugLog {
   697  			fmt.Printf("After put %v: %v\n", key, m)
   698  		}
   699  	}
   700  
   701  	if m.Used() != 31 {
   702  		t.Errorf("Used() used got %d want 31", m.Used())
   703  	}
   704  
   705  	key = big{}
   706  	elem = big{}
   707  	elem[0] = 128
   708  
   709  	for i := 0; i < 31; i++ {
   710  		key[0] += 1
   711  		elem[0] += 1
   712  		got, ok := m.Get(typ, unsafe.Pointer(&key))
   713  		if !ok {
   714  			t.Errorf("Get(%v) got ok false want true", key)
   715  		}
   716  		gotElem := *(*big)(got)
   717  		if gotElem != elem {
   718  			t.Errorf("Get(%v) got elem %v want %v", key, gotElem, elem)
   719  		}
   720  	}
   721  }
   722  
   723  // Delete should clear element. See https://go.dev/issue/25936.
   724  func TestMapDeleteClear(t *testing.T) {
   725  	m, typ := maps.NewTestMap[int64, int64](8)
   726  
   727  	key := int64(0)
   728  	elem := int64(128)
   729  
   730  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   731  
   732  	if maps.DebugLog {
   733  		fmt.Printf("After put %d: %v\n", key, m)
   734  	}
   735  
   736  	got, ok := m.Get(typ, unsafe.Pointer(&key))
   737  	if !ok {
   738  		t.Errorf("Get(%d) got ok false want true", key)
   739  	}
   740  	gotElem := *(*int64)(got)
   741  	if gotElem != elem {
   742  		t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
   743  	}
   744  
   745  	m.Delete(typ, unsafe.Pointer(&key))
   746  
   747  	gotElem = *(*int64)(got)
   748  	if gotElem != 0 {
   749  		t.Errorf("Delete(%d) failed to clear element. got %d want 0", key, gotElem)
   750  	}
   751  }
   752  
   753  var alwaysFalse bool
   754  var escapeSink any
   755  
   756  func escape[T any](x T) T {
   757  	if alwaysFalse {
   758  		escapeSink = x
   759  	}
   760  	return x
   761  }
   762  
   763  const (
   764  	belowMax = abi.MapGroupSlots * 3 / 2                                          // 1.5 * group max = 2 groups @ 75%
   765  	atMax    = (2 * abi.MapGroupSlots * maps.MaxAvgGroupLoad) / abi.MapGroupSlots // 2 groups at 7/8 full.
   766  )
   767  
   768  func TestTableGroupCount(t *testing.T) {
   769  	// Test that maps of different sizes have the right number of
   770  	// tables/groups.
   771  
   772  	type mapCount struct {
   773  		tables int
   774  		groups uint64
   775  	}
   776  
   777  	type mapCase struct {
   778  		initialLit  mapCount
   779  		initialHint mapCount
   780  		after       mapCount
   781  	}
   782  
   783  	var testCases = []struct {
   784  		n      int     // n is the number of map elements
   785  		escape mapCase // expected values for escaping map
   786  	}{
   787  		{
   788  			n: -(1 << 30),
   789  			escape: mapCase{
   790  				initialLit:  mapCount{0, 0},
   791  				initialHint: mapCount{0, 0},
   792  				after:       mapCount{0, 0},
   793  			},
   794  		},
   795  		{
   796  			n: -1,
   797  			escape: mapCase{
   798  				initialLit:  mapCount{0, 0},
   799  				initialHint: mapCount{0, 0},
   800  				after:       mapCount{0, 0},
   801  			},
   802  		},
   803  		{
   804  			n: 0,
   805  			escape: mapCase{
   806  				initialLit:  mapCount{0, 0},
   807  				initialHint: mapCount{0, 0},
   808  				after:       mapCount{0, 0},
   809  			},
   810  		},
   811  		{
   812  			n: 1,
   813  			escape: mapCase{
   814  				initialLit:  mapCount{0, 0},
   815  				initialHint: mapCount{0, 0},
   816  				after:       mapCount{0, 1},
   817  			},
   818  		},
   819  		{
   820  			n: abi.MapGroupSlots,
   821  			escape: mapCase{
   822  				initialLit:  mapCount{0, 0},
   823  				initialHint: mapCount{0, 0},
   824  				after:       mapCount{0, 1},
   825  			},
   826  		},
   827  		{
   828  			n: abi.MapGroupSlots + 1,
   829  			escape: mapCase{
   830  				initialLit:  mapCount{0, 0},
   831  				initialHint: mapCount{1, 2},
   832  				after:       mapCount{1, 2},
   833  			},
   834  		},
   835  		{
   836  			n: belowMax, // 1.5 group max = 2 groups @ 75%
   837  			escape: mapCase{
   838  				initialLit:  mapCount{0, 0},
   839  				initialHint: mapCount{1, 2},
   840  				after:       mapCount{1, 2},
   841  			},
   842  		},
   843  		{
   844  			n: atMax, // 2 groups at max
   845  			escape: mapCase{
   846  				initialLit:  mapCount{0, 0},
   847  				initialHint: mapCount{1, 2},
   848  				after:       mapCount{1, 2},
   849  			},
   850  		},
   851  		{
   852  			n: atMax + 1, // 2 groups at max + 1 -> grow to 4 groups
   853  			escape: mapCase{
   854  				initialLit:  mapCount{0, 0},
   855  				initialHint: mapCount{1, 4},
   856  				after:       mapCount{1, 4},
   857  			},
   858  		},
   859  		{
   860  			n: 2 * belowMax, // 3 * group max = 4 groups @75%
   861  			escape: mapCase{
   862  				initialLit:  mapCount{0, 0},
   863  				initialHint: mapCount{1, 4},
   864  				after:       mapCount{1, 4},
   865  			},
   866  		},
   867  		{
   868  			n: 2*atMax + 1, // 4 groups at max + 1 -> grow to 8 groups
   869  			escape: mapCase{
   870  				initialLit:  mapCount{0, 0},
   871  				initialHint: mapCount{1, 8},
   872  				after:       mapCount{1, 8},
   873  			},
   874  		},
   875  	}
   876  
   877  	testMap := func(t *testing.T, m map[int]int, n int, initial, after mapCount) {
   878  		mm := *(**maps.Map)(unsafe.Pointer(&m))
   879  
   880  		gotTab := mm.TableCount()
   881  		if gotTab != initial.tables {
   882  			t.Errorf("initial TableCount got %d want %d", gotTab, initial.tables)
   883  		}
   884  
   885  		gotGroup := mm.GroupCount()
   886  		if gotGroup != initial.groups {
   887  			t.Errorf("initial GroupCount got %d want %d", gotGroup, initial.groups)
   888  		}
   889  
   890  		for i := 0; i < n; i++ {
   891  			m[i] = i
   892  		}
   893  
   894  		gotTab = mm.TableCount()
   895  		if gotTab != after.tables {
   896  			t.Errorf("after TableCount got %d want %d", gotTab, after.tables)
   897  		}
   898  
   899  		gotGroup = mm.GroupCount()
   900  		if gotGroup != after.groups {
   901  			t.Errorf("after GroupCount got %d want %d", gotGroup, after.groups)
   902  		}
   903  	}
   904  
   905  	t.Run("mapliteral", func(t *testing.T) {
   906  		for _, tc := range testCases {
   907  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   908  				t.Run("escape", func(t *testing.T) {
   909  					m := escape(map[int]int{})
   910  					testMap(t, m, tc.n, tc.escape.initialLit, tc.escape.after)
   911  				})
   912  			})
   913  		}
   914  	})
   915  	t.Run("nohint", func(t *testing.T) {
   916  		for _, tc := range testCases {
   917  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   918  				t.Run("escape", func(t *testing.T) {
   919  					m := escape(make(map[int]int))
   920  					testMap(t, m, tc.n, tc.escape.initialLit, tc.escape.after)
   921  				})
   922  			})
   923  		}
   924  	})
   925  	t.Run("makemap", func(t *testing.T) {
   926  		for _, tc := range testCases {
   927  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   928  				t.Run("escape", func(t *testing.T) {
   929  					m := escape(make(map[int]int, tc.n))
   930  					testMap(t, m, tc.n, tc.escape.initialHint, tc.escape.after)
   931  				})
   932  			})
   933  		}
   934  	})
   935  	t.Run("makemap64", func(t *testing.T) {
   936  		for _, tc := range testCases {
   937  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   938  				t.Run("escape", func(t *testing.T) {
   939  					m := escape(make(map[int]int, int64(tc.n)))
   940  					testMap(t, m, tc.n, tc.escape.initialHint, tc.escape.after)
   941  				})
   942  			})
   943  		}
   944  	})
   945  }
   946  
   947  func TestTombstoneGrow(t *testing.T) {
   948  	tableSizes := []int{16, 32, 64, 128, 256}
   949  	for _, tableSize := range tableSizes {
   950  		for _, load := range []string{"low", "mid", "high"} {
   951  			capacity := tableSize * 7 / 8
   952  			var initialElems int
   953  			switch load {
   954  			case "low":
   955  				initialElems = capacity / 8
   956  			case "mid":
   957  				initialElems = capacity / 2
   958  			case "high":
   959  				initialElems = capacity
   960  			}
   961  			t.Run(fmt.Sprintf("tableSize=%d/elems=%d/load=%0.3f", tableSize, initialElems, float64(initialElems)/float64(tableSize)), func(t *testing.T) {
   962  				allocs := testing.AllocsPerRun(1, func() {
   963  					// Fill the map with elements.
   964  					m := make(map[int]int, capacity)
   965  					for i := range initialElems {
   966  						m[i] = i
   967  					}
   968  
   969  					// This is the heart of our test.
   970  					// Loop over the map repeatedly, deleting a key then adding a not-yet-seen key
   971  					// while keeping the map at a ~constant number of elements (+/-1).
   972  					nextKey := initialElems
   973  					for range 100000 {
   974  						for k := range m {
   975  							delete(m, k)
   976  							break
   977  						}
   978  						m[nextKey] = nextKey
   979  						nextKey++
   980  						if len(m) != initialElems {
   981  							t.Fatal("len(m) should remain constant")
   982  						}
   983  					}
   984  				})
   985  
   986  				// The make has 4 allocs (map, directory, table, groups).
   987  				// Each growth has 2 allocs (table, groups).
   988  				// We allow two growths if we start full, 1 otherwise.
   989  				// Fail (somewhat arbitrarily) if there are more than that.
   990  				allowed := float64(4 + 1*2)
   991  				if initialElems == capacity {
   992  					allowed += 2
   993  				}
   994  				if allocs > allowed {
   995  					t.Fatalf("got %v allocations, allowed %v", allocs, allowed)
   996  				}
   997  			})
   998  		}
   999  	}
  1000  }
  1001  

View as plain text