Source file src/internal/sync/hashtriemap_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 sync_test
     6  
     7  import (
     8  	"fmt"
     9  	isync "internal/sync"
    10  	"math"
    11  	"runtime"
    12  	"strconv"
    13  	"sync"
    14  	"testing"
    15  )
    16  
    17  func TestHashTrieMap(t *testing.T) {
    18  	testHashTrieMap(t, func() *isync.HashTrieMap[string, int] {
    19  		var m isync.HashTrieMap[string, int]
    20  		return &m
    21  	})
    22  }
    23  
    24  func TestHashTrieMapBadHash(t *testing.T) {
    25  	testHashTrieMap(t, func() *isync.HashTrieMap[string, int] {
    26  		return isync.NewBadHashTrieMap[string, int]()
    27  	})
    28  }
    29  
    30  func TestHashTrieMapTruncHash(t *testing.T) {
    31  	testHashTrieMap(t, func() *isync.HashTrieMap[string, int] {
    32  		// Stub out the good hash function with a different terrible one
    33  		// (truncated hash). Everything should still work as expected.
    34  		// This is useful to test independently to catch issues with
    35  		// near collisions, where only the last few bits of the hash differ.
    36  		return isync.NewTruncHashTrieMap[string, int]()
    37  	})
    38  }
    39  
    40  func testHashTrieMap(t *testing.T, newMap func() *isync.HashTrieMap[string, int]) {
    41  	t.Run("LoadEmpty", func(t *testing.T) {
    42  		m := newMap()
    43  
    44  		for _, s := range testData {
    45  			expectMissing(t, s, 0)(m.Load(s))
    46  		}
    47  	})
    48  	t.Run("LoadOrStore", func(t *testing.T) {
    49  		m := newMap()
    50  
    51  		for i, s := range testData {
    52  			expectMissing(t, s, 0)(m.Load(s))
    53  			expectStored(t, s, i)(m.LoadOrStore(s, i))
    54  			expectPresent(t, s, i)(m.Load(s))
    55  			expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
    56  		}
    57  		for i, s := range testData {
    58  			expectPresent(t, s, i)(m.Load(s))
    59  			expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
    60  		}
    61  	})
    62  	t.Run("All", func(t *testing.T) {
    63  		m := newMap()
    64  
    65  		testAll(t, m, testDataMap(testData[:]), func(_ string, _ int) bool {
    66  			return true
    67  		})
    68  	})
    69  	t.Run("Clear", func(t *testing.T) {
    70  		t.Run("Simple", func(t *testing.T) {
    71  			m := newMap()
    72  
    73  			for i, s := range testData {
    74  				expectMissing(t, s, 0)(m.Load(s))
    75  				expectStored(t, s, i)(m.LoadOrStore(s, i))
    76  				expectPresent(t, s, i)(m.Load(s))
    77  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
    78  			}
    79  			m.Clear()
    80  			for _, s := range testData {
    81  				expectMissing(t, s, 0)(m.Load(s))
    82  			}
    83  		})
    84  		t.Run("Concurrent", func(t *testing.T) {
    85  			m := newMap()
    86  
    87  			// Load up the map.
    88  			for i, s := range testData {
    89  				expectMissing(t, s, 0)(m.Load(s))
    90  				expectStored(t, s, i)(m.LoadOrStore(s, i))
    91  			}
    92  			gmp := runtime.GOMAXPROCS(-1)
    93  			var wg sync.WaitGroup
    94  			for i := range gmp {
    95  				wg.Add(1)
    96  				go func(id int) {
    97  					defer wg.Done()
    98  
    99  					for _, s := range testData {
   100  						// Try a couple things to interfere with the clear.
   101  						expectNotDeleted(t, s, math.MaxInt)(m.CompareAndDelete(s, math.MaxInt))
   102  						m.CompareAndSwap(s, i, i+1) // May succeed or fail; we don't care.
   103  					}
   104  				}(i)
   105  			}
   106  
   107  			// Concurrently clear the map.
   108  			runtime.Gosched()
   109  			m.Clear()
   110  
   111  			// Wait for workers to finish.
   112  			wg.Wait()
   113  
   114  			// It should all be empty now.
   115  			for _, s := range testData {
   116  				expectMissing(t, s, 0)(m.Load(s))
   117  			}
   118  		})
   119  	})
   120  	t.Run("CompareAndDelete", func(t *testing.T) {
   121  		t.Run("All", func(t *testing.T) {
   122  			m := newMap()
   123  
   124  			for range 3 {
   125  				for i, s := range testData {
   126  					expectMissing(t, s, 0)(m.Load(s))
   127  					expectStored(t, s, i)(m.LoadOrStore(s, i))
   128  					expectPresent(t, s, i)(m.Load(s))
   129  					expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   130  				}
   131  				for i, s := range testData {
   132  					expectPresent(t, s, i)(m.Load(s))
   133  					expectNotDeleted(t, s, math.MaxInt)(m.CompareAndDelete(s, math.MaxInt))
   134  					expectDeleted(t, s, i)(m.CompareAndDelete(s, i))
   135  					expectNotDeleted(t, s, i)(m.CompareAndDelete(s, i))
   136  					expectMissing(t, s, 0)(m.Load(s))
   137  				}
   138  				for _, s := range testData {
   139  					expectMissing(t, s, 0)(m.Load(s))
   140  				}
   141  			}
   142  		})
   143  		t.Run("One", func(t *testing.T) {
   144  			m := newMap()
   145  
   146  			for i, s := range testData {
   147  				expectMissing(t, s, 0)(m.Load(s))
   148  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   149  				expectPresent(t, s, i)(m.Load(s))
   150  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   151  			}
   152  			expectNotDeleted(t, testData[15], math.MaxInt)(m.CompareAndDelete(testData[15], math.MaxInt))
   153  			expectDeleted(t, testData[15], 15)(m.CompareAndDelete(testData[15], 15))
   154  			expectNotDeleted(t, testData[15], 15)(m.CompareAndDelete(testData[15], 15))
   155  			for i, s := range testData {
   156  				if i == 15 {
   157  					expectMissing(t, s, 0)(m.Load(s))
   158  				} else {
   159  					expectPresent(t, s, i)(m.Load(s))
   160  				}
   161  			}
   162  		})
   163  		t.Run("Multiple", func(t *testing.T) {
   164  			m := newMap()
   165  
   166  			for i, s := range testData {
   167  				expectMissing(t, s, 0)(m.Load(s))
   168  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   169  				expectPresent(t, s, i)(m.Load(s))
   170  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   171  			}
   172  			for _, i := range []int{1, 105, 6, 85} {
   173  				expectNotDeleted(t, testData[i], math.MaxInt)(m.CompareAndDelete(testData[i], math.MaxInt))
   174  				expectDeleted(t, testData[i], i)(m.CompareAndDelete(testData[i], i))
   175  				expectNotDeleted(t, testData[i], i)(m.CompareAndDelete(testData[i], i))
   176  			}
   177  			for i, s := range testData {
   178  				if i == 1 || i == 105 || i == 6 || i == 85 {
   179  					expectMissing(t, s, 0)(m.Load(s))
   180  				} else {
   181  					expectPresent(t, s, i)(m.Load(s))
   182  				}
   183  			}
   184  		})
   185  		t.Run("Iterate", func(t *testing.T) {
   186  			m := newMap()
   187  
   188  			testAll(t, m, testDataMap(testData[:]), func(s string, i int) bool {
   189  				expectDeleted(t, s, i)(m.CompareAndDelete(s, i))
   190  				return true
   191  			})
   192  			for _, s := range testData {
   193  				expectMissing(t, s, 0)(m.Load(s))
   194  			}
   195  		})
   196  		t.Run("ConcurrentUnsharedKeys", func(t *testing.T) {
   197  			m := newMap()
   198  
   199  			gmp := runtime.GOMAXPROCS(-1)
   200  			var wg sync.WaitGroup
   201  			for i := range gmp {
   202  				wg.Add(1)
   203  				go func(id int) {
   204  					defer wg.Done()
   205  
   206  					makeKey := func(s string) string {
   207  						return s + "-" + strconv.Itoa(id)
   208  					}
   209  					for _, s := range testData {
   210  						key := makeKey(s)
   211  						expectMissing(t, key, 0)(m.Load(key))
   212  						expectStored(t, key, id)(m.LoadOrStore(key, id))
   213  						expectPresent(t, key, id)(m.Load(key))
   214  						expectLoaded(t, key, id)(m.LoadOrStore(key, 0))
   215  					}
   216  					for _, s := range testData {
   217  						key := makeKey(s)
   218  						expectPresent(t, key, id)(m.Load(key))
   219  						expectDeleted(t, key, id)(m.CompareAndDelete(key, id))
   220  						expectMissing(t, key, 0)(m.Load(key))
   221  					}
   222  					for _, s := range testData {
   223  						key := makeKey(s)
   224  						expectMissing(t, key, 0)(m.Load(key))
   225  					}
   226  				}(i)
   227  			}
   228  			wg.Wait()
   229  		})
   230  		t.Run("ConcurrentSharedKeys", func(t *testing.T) {
   231  			m := newMap()
   232  
   233  			// Load up the map.
   234  			for i, s := range testData {
   235  				expectMissing(t, s, 0)(m.Load(s))
   236  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   237  			}
   238  			gmp := runtime.GOMAXPROCS(-1)
   239  			var wg sync.WaitGroup
   240  			for i := range gmp {
   241  				wg.Add(1)
   242  				go func(id int) {
   243  					defer wg.Done()
   244  
   245  					for i, s := range testData {
   246  						expectNotDeleted(t, s, math.MaxInt)(m.CompareAndDelete(s, math.MaxInt))
   247  						m.CompareAndDelete(s, i)
   248  						expectMissing(t, s, 0)(m.Load(s))
   249  					}
   250  					for _, s := range testData {
   251  						expectMissing(t, s, 0)(m.Load(s))
   252  					}
   253  				}(i)
   254  			}
   255  			wg.Wait()
   256  		})
   257  	})
   258  	t.Run("CompareAndSwap", func(t *testing.T) {
   259  		t.Run("All", func(t *testing.T) {
   260  			m := newMap()
   261  
   262  			for i, s := range testData {
   263  				expectMissing(t, s, 0)(m.Load(s))
   264  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   265  				expectPresent(t, s, i)(m.Load(s))
   266  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   267  			}
   268  			for j := range 3 {
   269  				for i, s := range testData {
   270  					expectPresent(t, s, i+j)(m.Load(s))
   271  					expectNotSwapped(t, s, math.MaxInt, i+j+1)(m.CompareAndSwap(s, math.MaxInt, i+j+1))
   272  					expectSwapped(t, s, i, i+j+1)(m.CompareAndSwap(s, i+j, i+j+1))
   273  					expectNotSwapped(t, s, i+j, i+j+1)(m.CompareAndSwap(s, i+j, i+j+1))
   274  					expectPresent(t, s, i+j+1)(m.Load(s))
   275  				}
   276  			}
   277  			for i, s := range testData {
   278  				expectPresent(t, s, i+3)(m.Load(s))
   279  			}
   280  		})
   281  		t.Run("One", func(t *testing.T) {
   282  			m := newMap()
   283  
   284  			for i, s := range testData {
   285  				expectMissing(t, s, 0)(m.Load(s))
   286  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   287  				expectPresent(t, s, i)(m.Load(s))
   288  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   289  			}
   290  			expectNotSwapped(t, testData[15], math.MaxInt, 16)(m.CompareAndSwap(testData[15], math.MaxInt, 16))
   291  			expectSwapped(t, testData[15], 15, 16)(m.CompareAndSwap(testData[15], 15, 16))
   292  			expectNotSwapped(t, testData[15], 15, 16)(m.CompareAndSwap(testData[15], 15, 16))
   293  			for i, s := range testData {
   294  				if i == 15 {
   295  					expectPresent(t, s, 16)(m.Load(s))
   296  				} else {
   297  					expectPresent(t, s, i)(m.Load(s))
   298  				}
   299  			}
   300  		})
   301  		t.Run("Multiple", func(t *testing.T) {
   302  			m := newMap()
   303  
   304  			for i, s := range testData {
   305  				expectMissing(t, s, 0)(m.Load(s))
   306  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   307  				expectPresent(t, s, i)(m.Load(s))
   308  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   309  			}
   310  			for _, i := range []int{1, 105, 6, 85} {
   311  				expectNotSwapped(t, testData[i], math.MaxInt, i+1)(m.CompareAndSwap(testData[i], math.MaxInt, i+1))
   312  				expectSwapped(t, testData[i], i, i+1)(m.CompareAndSwap(testData[i], i, i+1))
   313  				expectNotSwapped(t, testData[i], i, i+1)(m.CompareAndSwap(testData[i], i, i+1))
   314  			}
   315  			for i, s := range testData {
   316  				if i == 1 || i == 105 || i == 6 || i == 85 {
   317  					expectPresent(t, s, i+1)(m.Load(s))
   318  				} else {
   319  					expectPresent(t, s, i)(m.Load(s))
   320  				}
   321  			}
   322  		})
   323  
   324  		t.Run("ConcurrentUnsharedKeys", func(t *testing.T) {
   325  			m := newMap()
   326  
   327  			gmp := runtime.GOMAXPROCS(-1)
   328  			var wg sync.WaitGroup
   329  			for i := range gmp {
   330  				wg.Add(1)
   331  				go func(id int) {
   332  					defer wg.Done()
   333  
   334  					makeKey := func(s string) string {
   335  						return s + "-" + strconv.Itoa(id)
   336  					}
   337  					for _, s := range testData {
   338  						key := makeKey(s)
   339  						expectMissing(t, key, 0)(m.Load(key))
   340  						expectStored(t, key, id)(m.LoadOrStore(key, id))
   341  						expectPresent(t, key, id)(m.Load(key))
   342  						expectLoaded(t, key, id)(m.LoadOrStore(key, 0))
   343  					}
   344  					for _, s := range testData {
   345  						key := makeKey(s)
   346  						expectPresent(t, key, id)(m.Load(key))
   347  						expectSwapped(t, key, id, id+1)(m.CompareAndSwap(key, id, id+1))
   348  						expectPresent(t, key, id+1)(m.Load(key))
   349  					}
   350  					for _, s := range testData {
   351  						key := makeKey(s)
   352  						expectPresent(t, key, id+1)(m.Load(key))
   353  					}
   354  				}(i)
   355  			}
   356  			wg.Wait()
   357  		})
   358  		t.Run("ConcurrentUnsharedKeysWithDelete", func(t *testing.T) {
   359  			m := newMap()
   360  
   361  			gmp := runtime.GOMAXPROCS(-1)
   362  			var wg sync.WaitGroup
   363  			for i := range gmp {
   364  				wg.Add(1)
   365  				go func(id int) {
   366  					defer wg.Done()
   367  
   368  					makeKey := func(s string) string {
   369  						return s + "-" + strconv.Itoa(id)
   370  					}
   371  					for _, s := range testData {
   372  						key := makeKey(s)
   373  						expectMissing(t, key, 0)(m.Load(key))
   374  						expectStored(t, key, id)(m.LoadOrStore(key, id))
   375  						expectPresent(t, key, id)(m.Load(key))
   376  						expectLoaded(t, key, id)(m.LoadOrStore(key, 0))
   377  					}
   378  					for _, s := range testData {
   379  						key := makeKey(s)
   380  						expectPresent(t, key, id)(m.Load(key))
   381  						expectSwapped(t, key, id, id+1)(m.CompareAndSwap(key, id, id+1))
   382  						expectPresent(t, key, id+1)(m.Load(key))
   383  						expectDeleted(t, key, id+1)(m.CompareAndDelete(key, id+1))
   384  						expectNotSwapped(t, key, id+1, id+2)(m.CompareAndSwap(key, id+1, id+2))
   385  						expectNotDeleted(t, key, id+1)(m.CompareAndDelete(key, id+1))
   386  						expectMissing(t, key, 0)(m.Load(key))
   387  					}
   388  					for _, s := range testData {
   389  						key := makeKey(s)
   390  						expectMissing(t, key, 0)(m.Load(key))
   391  					}
   392  				}(i)
   393  			}
   394  			wg.Wait()
   395  		})
   396  		t.Run("ConcurrentSharedKeys", func(t *testing.T) {
   397  			m := newMap()
   398  
   399  			// Load up the map.
   400  			for i, s := range testData {
   401  				expectMissing(t, s, 0)(m.Load(s))
   402  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   403  			}
   404  			gmp := runtime.GOMAXPROCS(-1)
   405  			var wg sync.WaitGroup
   406  			for i := range gmp {
   407  				wg.Add(1)
   408  				go func(id int) {
   409  					defer wg.Done()
   410  
   411  					for i, s := range testData {
   412  						expectNotSwapped(t, s, math.MaxInt, i+1)(m.CompareAndSwap(s, math.MaxInt, i+1))
   413  						m.CompareAndSwap(s, i, i+1)
   414  						expectPresent(t, s, i+1)(m.Load(s))
   415  					}
   416  					for i, s := range testData {
   417  						expectPresent(t, s, i+1)(m.Load(s))
   418  					}
   419  				}(i)
   420  			}
   421  			wg.Wait()
   422  		})
   423  	})
   424  	t.Run("Swap", func(t *testing.T) {
   425  		t.Run("All", func(t *testing.T) {
   426  			m := newMap()
   427  
   428  			for i, s := range testData {
   429  				expectMissing(t, s, 0)(m.Load(s))
   430  				expectNotLoadedFromSwap(t, s, i)(m.Swap(s, i))
   431  				expectPresent(t, s, i)(m.Load(s))
   432  				expectLoadedFromSwap(t, s, i, i)(m.Swap(s, i))
   433  			}
   434  			for j := range 3 {
   435  				for i, s := range testData {
   436  					expectPresent(t, s, i+j)(m.Load(s))
   437  					expectLoadedFromSwap(t, s, i+j, i+j+1)(m.Swap(s, i+j+1))
   438  					expectPresent(t, s, i+j+1)(m.Load(s))
   439  				}
   440  			}
   441  			for i, s := range testData {
   442  				expectLoadedFromSwap(t, s, i+3, i+3)(m.Swap(s, i+3))
   443  			}
   444  		})
   445  		t.Run("One", func(t *testing.T) {
   446  			m := newMap()
   447  
   448  			for i, s := range testData {
   449  				expectMissing(t, s, 0)(m.Load(s))
   450  				expectNotLoadedFromSwap(t, s, i)(m.Swap(s, i))
   451  				expectPresent(t, s, i)(m.Load(s))
   452  				expectLoadedFromSwap(t, s, i, i)(m.Swap(s, i))
   453  			}
   454  			expectLoadedFromSwap(t, testData[15], 15, 16)(m.Swap(testData[15], 16))
   455  			for i, s := range testData {
   456  				if i == 15 {
   457  					expectPresent(t, s, 16)(m.Load(s))
   458  				} else {
   459  					expectPresent(t, s, i)(m.Load(s))
   460  				}
   461  			}
   462  		})
   463  		t.Run("Multiple", func(t *testing.T) {
   464  			m := newMap()
   465  
   466  			for i, s := range testData {
   467  				expectMissing(t, s, 0)(m.Load(s))
   468  				expectNotLoadedFromSwap(t, s, i)(m.Swap(s, i))
   469  				expectPresent(t, s, i)(m.Load(s))
   470  				expectLoadedFromSwap(t, s, i, i)(m.Swap(s, i))
   471  			}
   472  			for _, i := range []int{1, 105, 6, 85} {
   473  				expectLoadedFromSwap(t, testData[i], i, i+1)(m.Swap(testData[i], i+1))
   474  			}
   475  			for i, s := range testData {
   476  				if i == 1 || i == 105 || i == 6 || i == 85 {
   477  					expectPresent(t, s, i+1)(m.Load(s))
   478  				} else {
   479  					expectPresent(t, s, i)(m.Load(s))
   480  				}
   481  			}
   482  		})
   483  		t.Run("ConcurrentUnsharedKeys", func(t *testing.T) {
   484  			m := newMap()
   485  
   486  			gmp := runtime.GOMAXPROCS(-1)
   487  			var wg sync.WaitGroup
   488  			for i := range gmp {
   489  				wg.Add(1)
   490  				go func(id int) {
   491  					defer wg.Done()
   492  
   493  					makeKey := func(s string) string {
   494  						return s + "-" + strconv.Itoa(id)
   495  					}
   496  					for _, s := range testData {
   497  						key := makeKey(s)
   498  						expectMissing(t, key, 0)(m.Load(key))
   499  						expectNotLoadedFromSwap(t, key, id)(m.Swap(key, id))
   500  						expectPresent(t, key, id)(m.Load(key))
   501  						expectLoadedFromSwap(t, key, id, id)(m.Swap(key, id))
   502  					}
   503  					for _, s := range testData {
   504  						key := makeKey(s)
   505  						expectPresent(t, key, id)(m.Load(key))
   506  						expectLoadedFromSwap(t, key, id, id+1)(m.Swap(key, id+1))
   507  						expectPresent(t, key, id+1)(m.Load(key))
   508  					}
   509  					for _, s := range testData {
   510  						key := makeKey(s)
   511  						expectPresent(t, key, id+1)(m.Load(key))
   512  					}
   513  				}(i)
   514  			}
   515  			wg.Wait()
   516  		})
   517  		t.Run("ConcurrentUnsharedKeysWithDelete", func(t *testing.T) {
   518  			m := newMap()
   519  
   520  			gmp := runtime.GOMAXPROCS(-1)
   521  			var wg sync.WaitGroup
   522  			for i := range gmp {
   523  				wg.Add(1)
   524  				go func(id int) {
   525  					defer wg.Done()
   526  
   527  					makeKey := func(s string) string {
   528  						return s + "-" + strconv.Itoa(id)
   529  					}
   530  					for _, s := range testData {
   531  						key := makeKey(s)
   532  						expectMissing(t, key, 0)(m.Load(key))
   533  						expectNotLoadedFromSwap(t, key, id)(m.Swap(key, id))
   534  						expectPresent(t, key, id)(m.Load(key))
   535  						expectLoadedFromSwap(t, key, id, id)(m.Swap(key, id))
   536  					}
   537  					for _, s := range testData {
   538  						key := makeKey(s)
   539  						expectPresent(t, key, id)(m.Load(key))
   540  						expectLoadedFromSwap(t, key, id, id+1)(m.Swap(key, id+1))
   541  						expectPresent(t, key, id+1)(m.Load(key))
   542  						expectDeleted(t, key, id+1)(m.CompareAndDelete(key, id+1))
   543  						expectNotLoadedFromSwap(t, key, id+2)(m.Swap(key, id+2))
   544  						expectPresent(t, key, id+2)(m.Load(key))
   545  					}
   546  					for _, s := range testData {
   547  						key := makeKey(s)
   548  						expectPresent(t, key, id+2)(m.Load(key))
   549  					}
   550  				}(i)
   551  			}
   552  			wg.Wait()
   553  		})
   554  		t.Run("ConcurrentSharedKeys", func(t *testing.T) {
   555  			m := newMap()
   556  
   557  			// Load up the map.
   558  			for i, s := range testData {
   559  				expectMissing(t, s, 0)(m.Load(s))
   560  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   561  			}
   562  			gmp := runtime.GOMAXPROCS(-1)
   563  			var wg sync.WaitGroup
   564  			for i := range gmp {
   565  				wg.Add(1)
   566  				go func(id int) {
   567  					defer wg.Done()
   568  
   569  					for i, s := range testData {
   570  						m.Swap(s, i+1)
   571  						expectPresent(t, s, i+1)(m.Load(s))
   572  					}
   573  					for i, s := range testData {
   574  						expectPresent(t, s, i+1)(m.Load(s))
   575  					}
   576  				}(i)
   577  			}
   578  			wg.Wait()
   579  		})
   580  	})
   581  	t.Run("LoadAndDelete", func(t *testing.T) {
   582  		t.Run("All", func(t *testing.T) {
   583  			m := newMap()
   584  
   585  			for range 3 {
   586  				for i, s := range testData {
   587  					expectMissing(t, s, 0)(m.Load(s))
   588  					expectStored(t, s, i)(m.LoadOrStore(s, i))
   589  					expectPresent(t, s, i)(m.Load(s))
   590  					expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   591  				}
   592  				for i, s := range testData {
   593  					expectPresent(t, s, i)(m.Load(s))
   594  					expectLoadedFromDelete(t, s, i)(m.LoadAndDelete(s))
   595  					expectMissing(t, s, 0)(m.Load(s))
   596  					expectNotLoadedFromDelete(t, s, 0)(m.LoadAndDelete(s))
   597  				}
   598  				for _, s := range testData {
   599  					expectMissing(t, s, 0)(m.Load(s))
   600  				}
   601  			}
   602  		})
   603  		t.Run("One", func(t *testing.T) {
   604  			m := newMap()
   605  
   606  			for i, s := range testData {
   607  				expectMissing(t, s, 0)(m.Load(s))
   608  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   609  				expectPresent(t, s, i)(m.Load(s))
   610  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   611  			}
   612  			expectPresent(t, testData[15], 15)(m.Load(testData[15]))
   613  			expectLoadedFromDelete(t, testData[15], 15)(m.LoadAndDelete(testData[15]))
   614  			expectMissing(t, testData[15], 0)(m.Load(testData[15]))
   615  			expectNotLoadedFromDelete(t, testData[15], 0)(m.LoadAndDelete(testData[15]))
   616  			for i, s := range testData {
   617  				if i == 15 {
   618  					expectMissing(t, s, 0)(m.Load(s))
   619  				} else {
   620  					expectPresent(t, s, i)(m.Load(s))
   621  				}
   622  			}
   623  		})
   624  		t.Run("Multiple", func(t *testing.T) {
   625  			m := newMap()
   626  
   627  			for i, s := range testData {
   628  				expectMissing(t, s, 0)(m.Load(s))
   629  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   630  				expectPresent(t, s, i)(m.Load(s))
   631  				expectLoaded(t, s, i)(m.LoadOrStore(s, 0))
   632  			}
   633  			for _, i := range []int{1, 105, 6, 85} {
   634  				expectPresent(t, testData[i], i)(m.Load(testData[i]))
   635  				expectLoadedFromDelete(t, testData[i], i)(m.LoadAndDelete(testData[i]))
   636  				expectMissing(t, testData[i], 0)(m.Load(testData[i]))
   637  				expectNotLoadedFromDelete(t, testData[i], 0)(m.LoadAndDelete(testData[i]))
   638  			}
   639  			for i, s := range testData {
   640  				if i == 1 || i == 105 || i == 6 || i == 85 {
   641  					expectMissing(t, s, 0)(m.Load(s))
   642  				} else {
   643  					expectPresent(t, s, i)(m.Load(s))
   644  				}
   645  			}
   646  		})
   647  		t.Run("Iterate", func(t *testing.T) {
   648  			m := newMap()
   649  
   650  			testAll(t, m, testDataMap(testData[:]), func(s string, i int) bool {
   651  				expectLoadedFromDelete(t, s, i)(m.LoadAndDelete(s))
   652  				return true
   653  			})
   654  			for _, s := range testData {
   655  				expectMissing(t, s, 0)(m.Load(s))
   656  			}
   657  		})
   658  		t.Run("ConcurrentUnsharedKeys", func(t *testing.T) {
   659  			m := newMap()
   660  
   661  			gmp := runtime.GOMAXPROCS(-1)
   662  			var wg sync.WaitGroup
   663  			for i := range gmp {
   664  				wg.Add(1)
   665  				go func(id int) {
   666  					defer wg.Done()
   667  
   668  					makeKey := func(s string) string {
   669  						return s + "-" + strconv.Itoa(id)
   670  					}
   671  					for _, s := range testData {
   672  						key := makeKey(s)
   673  						expectMissing(t, key, 0)(m.Load(key))
   674  						expectStored(t, key, id)(m.LoadOrStore(key, id))
   675  						expectPresent(t, key, id)(m.Load(key))
   676  						expectLoaded(t, key, id)(m.LoadOrStore(key, 0))
   677  					}
   678  					for _, s := range testData {
   679  						key := makeKey(s)
   680  						expectPresent(t, key, id)(m.Load(key))
   681  						expectLoadedFromDelete(t, key, id)(m.LoadAndDelete(key))
   682  						expectMissing(t, key, 0)(m.Load(key))
   683  					}
   684  					for _, s := range testData {
   685  						key := makeKey(s)
   686  						expectMissing(t, key, 0)(m.Load(key))
   687  					}
   688  				}(i)
   689  			}
   690  			wg.Wait()
   691  		})
   692  		t.Run("ConcurrentSharedKeys", func(t *testing.T) {
   693  			m := newMap()
   694  
   695  			// Load up the map.
   696  			for i, s := range testData {
   697  				expectMissing(t, s, 0)(m.Load(s))
   698  				expectStored(t, s, i)(m.LoadOrStore(s, i))
   699  			}
   700  			gmp := runtime.GOMAXPROCS(-1)
   701  			var wg sync.WaitGroup
   702  			for i := range gmp {
   703  				wg.Add(1)
   704  				go func(id int) {
   705  					defer wg.Done()
   706  
   707  					for _, s := range testData {
   708  						m.LoadAndDelete(s)
   709  						expectMissing(t, s, 0)(m.Load(s))
   710  					}
   711  					for _, s := range testData {
   712  						expectMissing(t, s, 0)(m.Load(s))
   713  					}
   714  				}(i)
   715  			}
   716  			wg.Wait()
   717  		})
   718  	})
   719  }
   720  
   721  func testAll[K, V comparable](t *testing.T, m *isync.HashTrieMap[K, V], testData map[K]V, yield func(K, V) bool) {
   722  	for k, v := range testData {
   723  		expectStored(t, k, v)(m.LoadOrStore(k, v))
   724  	}
   725  	visited := make(map[K]int)
   726  	m.All()(func(key K, got V) bool {
   727  		want, ok := testData[key]
   728  		if !ok {
   729  			t.Errorf("unexpected key %v in map", key)
   730  			return false
   731  		}
   732  		if got != want {
   733  			t.Errorf("expected key %v to have value %v, got %v", key, want, got)
   734  			return false
   735  		}
   736  		visited[key]++
   737  		return yield(key, got)
   738  	})
   739  	for key, n := range visited {
   740  		if n > 1 {
   741  			t.Errorf("visited key %v more than once", key)
   742  		}
   743  	}
   744  }
   745  
   746  func expectPresent[K, V comparable](t *testing.T, key K, want V) func(got V, ok bool) {
   747  	t.Helper()
   748  	return func(got V, ok bool) {
   749  		t.Helper()
   750  
   751  		if !ok {
   752  			t.Errorf("expected key %v to be present in map", key)
   753  		}
   754  		if ok && got != want {
   755  			t.Errorf("expected key %v to have value %v, got %v", key, want, got)
   756  		}
   757  	}
   758  }
   759  
   760  func expectMissing[K, V comparable](t *testing.T, key K, want V) func(got V, ok bool) {
   761  	t.Helper()
   762  	if want != *new(V) {
   763  		// This is awkward, but the want argument is necessary to smooth over type inference.
   764  		// Just make sure the want argument always looks the same.
   765  		panic("expectMissing must always have a zero value variable")
   766  	}
   767  	return func(got V, ok bool) {
   768  		t.Helper()
   769  
   770  		if ok {
   771  			t.Errorf("expected key %v to be missing from map, got value %v", key, got)
   772  		}
   773  		if !ok && got != want {
   774  			t.Errorf("expected missing key %v to be paired with the zero value; got %v", key, got)
   775  		}
   776  	}
   777  }
   778  
   779  func expectLoaded[K, V comparable](t *testing.T, key K, want V) func(got V, loaded bool) {
   780  	t.Helper()
   781  	return func(got V, loaded bool) {
   782  		t.Helper()
   783  
   784  		if !loaded {
   785  			t.Errorf("expected key %v to have been loaded, not stored", key)
   786  		}
   787  		if got != want {
   788  			t.Errorf("expected key %v to have value %v, got %v", key, want, got)
   789  		}
   790  	}
   791  }
   792  
   793  func expectStored[K, V comparable](t *testing.T, key K, want V) func(got V, loaded bool) {
   794  	t.Helper()
   795  	return func(got V, loaded bool) {
   796  		t.Helper()
   797  
   798  		if loaded {
   799  			t.Errorf("expected inserted key %v to have been stored, not loaded", key)
   800  		}
   801  		if got != want {
   802  			t.Errorf("expected inserted key %v to have value %v, got %v", key, want, got)
   803  		}
   804  	}
   805  }
   806  
   807  func expectDeleted[K, V comparable](t *testing.T, key K, old V) func(deleted bool) {
   808  	t.Helper()
   809  	return func(deleted bool) {
   810  		t.Helper()
   811  
   812  		if !deleted {
   813  			t.Errorf("expected key %v with value %v to be in map and deleted", key, old)
   814  		}
   815  	}
   816  }
   817  
   818  func expectNotDeleted[K, V comparable](t *testing.T, key K, old V) func(deleted bool) {
   819  	t.Helper()
   820  	return func(deleted bool) {
   821  		t.Helper()
   822  
   823  		if deleted {
   824  			t.Errorf("expected key %v with value %v to not be in map and thus not deleted", key, old)
   825  		}
   826  	}
   827  }
   828  
   829  func expectSwapped[K, V comparable](t *testing.T, key K, old, new V) func(swapped bool) {
   830  	t.Helper()
   831  	return func(swapped bool) {
   832  		t.Helper()
   833  
   834  		if !swapped {
   835  			t.Errorf("expected key %v with value %v to be in map and swapped for %v", key, old, new)
   836  		}
   837  	}
   838  }
   839  
   840  func expectNotSwapped[K, V comparable](t *testing.T, key K, old, new V) func(swapped bool) {
   841  	t.Helper()
   842  	return func(swapped bool) {
   843  		t.Helper()
   844  
   845  		if swapped {
   846  			t.Errorf("expected key %v with value %v to not be in map or not swapped for %v", key, old, new)
   847  		}
   848  	}
   849  }
   850  
   851  func expectLoadedFromSwap[K, V comparable](t *testing.T, key K, want, new V) func(got V, loaded bool) {
   852  	t.Helper()
   853  	return func(got V, loaded bool) {
   854  		t.Helper()
   855  
   856  		if !loaded {
   857  			t.Errorf("expected key %v to be in map and for %v to have been swapped for %v", key, want, new)
   858  		} else if want != got {
   859  			t.Errorf("key %v had its value %v swapped for %v, but expected it to have value %v", key, got, new, want)
   860  		}
   861  	}
   862  }
   863  
   864  func expectNotLoadedFromSwap[K, V comparable](t *testing.T, key K, new V) func(old V, loaded bool) {
   865  	t.Helper()
   866  	return func(old V, loaded bool) {
   867  		t.Helper()
   868  
   869  		if loaded {
   870  			t.Errorf("expected key %v to not be in map, but found value %v for it", key, old)
   871  		}
   872  	}
   873  }
   874  
   875  func expectLoadedFromDelete[K, V comparable](t *testing.T, key K, want V) func(got V, loaded bool) {
   876  	t.Helper()
   877  	return func(got V, loaded bool) {
   878  		t.Helper()
   879  
   880  		if !loaded {
   881  			t.Errorf("expected key %v to be in map to be deleted", key)
   882  		} else if want != got {
   883  			t.Errorf("key %v was deleted with value %v, but expected it to have value %v", key, got, want)
   884  		}
   885  	}
   886  }
   887  
   888  func expectNotLoadedFromDelete[K, V comparable](t *testing.T, key K, _ V) func(old V, loaded bool) {
   889  	t.Helper()
   890  	return func(old V, loaded bool) {
   891  		t.Helper()
   892  
   893  		if loaded {
   894  			t.Errorf("expected key %v to not be in map, but found value %v for it", key, old)
   895  		}
   896  	}
   897  }
   898  
   899  func testDataMap(data []string) map[string]int {
   900  	m := make(map[string]int)
   901  	for i, s := range data {
   902  		m[s] = i
   903  	}
   904  	return m
   905  }
   906  
   907  var (
   908  	testDataSmall [8]string
   909  	testData      [128]string
   910  	testDataLarge [128 << 10]string
   911  )
   912  
   913  func init() {
   914  	for i := range testDataSmall {
   915  		testDataSmall[i] = fmt.Sprintf("%b", i)
   916  	}
   917  	for i := range testData {
   918  		testData[i] = fmt.Sprintf("%b", i)
   919  	}
   920  	for i := range testDataLarge {
   921  		testDataLarge[i] = fmt.Sprintf("%b", i)
   922  	}
   923  }
   924  

View as plain text