1 // Copyright 2013 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.
18 // negative zero is a good test because:
19 // 1) 0 and -0 are equal, yet have distinct representations.
20 // 2) 0 is represented as all zeros, -0 isn't.
21 // I'm not sure the language spec actually requires this behavior,
22 // but it's what the current map implementation does.
23 func TestNegativeZero(t
*testing
.T
) {
24 m
:= make(map[float64]bool, 0)
27 m
[math
.Copysign(0.0, -1.0)] = true // should overwrite +0 entry
30 t
.Error("length wrong")
33 /* gccgo fails this test; this is not required by the spec.
35 if math.Copysign(1.0, k) > 0 {
41 m
= make(map[float64]bool, 0)
42 m
[math
.Copysign(0.0, -1.0)] = true
43 m
[+0.0] = true // should overwrite -0.0 entry
46 t
.Error("length wrong")
49 /* gccgo fails this test; this is not required by the spec.
51 if math.Copysign(1.0, k) < 0 {
58 // nan is a good test because nan != nan, and nan has
59 // a randomized hash value.
60 func TestNan(t
*testing
.T
) {
61 m
:= make(map[float64]int, 0)
67 t
.Error("length wrong")
72 t
.Error("nan disappeared")
74 if (v
& (v
- 1)) != 0 {
75 t
.Error("value wrong")
80 t
.Error("values wrong")
84 // Maps aren't actually copied on assignment.
85 func TestAlias(t
*testing
.T
) {
86 m
:= make(map[int]int, 0)
91 t
.Error("alias didn't work")
95 func TestGrowWithNaN(t
*testing
.T
) {
96 t
.Skip("fails with gccgo")
97 m
:= make(map[float64]int, 4)
105 for k
, v
:= range m
{
107 // force a hashtable resize
108 for i
:= 0; i
< 100; i
++ {
118 t
.Log("cnt:", cnt
, "s:", s
)
120 t
.Error("NaN keys lost during grow")
123 t
.Error("NaN values lost during grow")
127 type FloatInt
struct {
132 func TestGrowWithNegativeZero(t
*testing
.T
) {
133 t
.Skip("fails with gccgo")
134 negzero
:= math
.Copysign(0.0, -1.0)
135 m
:= make(map[FloatInt
]int, 4)
136 m
[FloatInt
{0.0, 0}] = 1
137 m
[FloatInt
{0.0, 1}] = 2
138 m
[FloatInt
{0.0, 2}] = 4
139 m
[FloatInt
{0.0, 3}] = 8
144 // The first iteration should return the +0 key.
145 // The subsequent iterations should return the -0 key.
146 // I'm not really sure this is required by the spec,
147 // but it makes sense.
148 // TODO: are we allowed to get the first entry returned again???
149 for k
, v
:= range m
{
152 } // ignore entries added to grow table
154 if math
.Copysign(1.0, k
.x
) < 0 {
156 t
.Error("key/value not updated together 1")
162 t
.Error("key/value not updated together 2", k
, v
)
167 // force a hashtable resize
168 for i
:= 0; i
< 100; i
++ {
169 m
[FloatInt
{3.0, i
}] = 0
171 // then change all the entries
173 m
[FloatInt
{negzero
, 0}] = 1 |
16
174 m
[FloatInt
{negzero
, 1}] = 2 |
16
175 m
[FloatInt
{negzero
, 2}] = 4 |
16
176 m
[FloatInt
{negzero
, 3}] = 8 |
16
181 t
.Error("entry missing", s
)
184 t
.Error("wrong number of entries returned by iterator", cnt
)
187 t
.Error("update to negzero missed by iteration", negcnt
)
191 func TestIterGrowAndDelete(t
*testing
.T
) {
192 m
:= make(map[int]int, 4)
193 for i
:= 0; i
< 100; i
++ {
200 for i
:= 100; i
< 1000; i
++ {
203 // delete all odd keys
204 for i
:= 1; i
< 1000; i
+= 2 {
210 t
.Error("odd value returned")
216 // make sure old bucket arrays don't get GCd while
217 // an iterator is still using them.
218 func TestIterGrowWithGC(t
*testing
.T
) {
219 m
:= make(map[int]int, 4)
220 for i
:= 0; i
< 16; i
++ {
227 bitmask |
= 1 << uint(k
)
231 for i
:= 100; i
< 1000; i
++ {
239 if bitmask
!= 1<<16-1 {
240 t
.Error("missing key", bitmask
)
244 func testConcurrentReadsAfterGrowth(t
*testing
.T
, useReflect
bool) {
245 if runtime
.GOMAXPROCS(-1) == 1 {
246 if runtime
.GOARCH
== "s390" {
247 // Test uses too much address space on 31-bit S390.
248 defer runtime
.GOMAXPROCS(runtime
.GOMAXPROCS(8))
250 defer runtime
.GOMAXPROCS(runtime
.GOMAXPROCS(16))
257 numLoop
, numGrowStep
= 2, 500
259 for i
:= 0; i
< numLoop
; i
++ {
260 m
:= make(map[int]int, 0)
261 for gs
:= 0; gs
< numGrowStep
; gs
++ {
263 var wg sync
.WaitGroup
264 wg
.Add(numReader
* 2)
265 for nr
:= 0; nr
< numReader
; nr
++ {
273 for key
:= 0; key
< gs
; key
++ {
281 mv
:= reflect
.ValueOf(m
)
283 for _
, k
:= range keys
{
294 func TestConcurrentReadsAfterGrowth(t
*testing
.T
) {
295 testConcurrentReadsAfterGrowth(t
, false)
298 func TestConcurrentReadsAfterGrowthReflect(t
*testing
.T
) {
299 testConcurrentReadsAfterGrowth(t
, true)
302 func TestBigItems(t
*testing
.T
) {
304 for i
:= 0; i
< 256; i
++ {
307 m
:= make(map[[256]string][256]string, 4)
308 for i
:= 0; i
< 100; i
++ {
309 key
[37] = fmt
.Sprintf("string%02d", i
)
313 var values
[100]string
315 for k
, v
:= range m
{
320 sort
.Strings(keys
[:])
321 sort
.Strings(values
[:])
322 for i
:= 0; i
< 100; i
++ {
323 if keys
[i
] != fmt
.Sprintf("string%02d", i
) {
324 t
.Errorf("#%d: missing key: %v", i
, keys
[i
])
326 if values
[i
] != fmt
.Sprintf("string%02d", i
) {
327 t
.Errorf("#%d: missing value: %v", i
, values
[i
])
335 func TestEmptyKeyAndValue(t
*testing
.T
) {
336 a
:= make(map[int]empty
, 4)
337 b
:= make(map[empty
]int, 4)
338 c
:= make(map[empty
]empty
, 4)
345 t
.Errorf("empty value insert problem")
348 t
.Errorf("empty key returned wrong value")
352 // Tests a map with a single bucket, with same-lengthed short keys
353 // ("quick keys") as well as long keys.
354 func TestSingleBucketMapStringKeys_DupLen(t
*testing
.T
) {
355 testMapLookups(t
, map[string]string{
359 "bar": "barval", // same key length as "foo"
361 strings
.Repeat("x", 128): "longval1",
362 strings
.Repeat("y", 128): "longval2",
366 // Tests a map with a single bucket, with all keys having different lengths.
367 func TestSingleBucketMapStringKeys_NoDupLen(t
*testing
.T
) {
368 testMapLookups(t
, map[string]string{
375 strings
.Repeat("x", 128): "longval",
379 func testMapLookups(t
*testing
.T
, m
map[string]string) {
380 for k
, v
:= range m
{
382 t
.Fatalf("m[%q] = %q; want %q", k
, m
[k
], v
)
387 // Tests whether the iterator returns the right elements when
388 // started in the middle of a grow, when the keys are NaNs.
389 func TestMapNanGrowIterator(t
*testing
.T
) {
390 m
:= make(map[float64]int)
393 // To fill nBuckets buckets takes LOAD * nBuckets keys.
394 nKeys
:= int(nBuckets
* /* *runtime.HashLoad */ 6.5)
396 // Get map to full point with nan keys.
397 for i
:= 0; i
< nKeys
; i
++ {
405 found
:= make(map[int]struct{})
406 for _
, v
:= range m
{
408 if _
, repeat
:= found
[v
]; repeat
{
409 t
.Fatalf("repeat of value %d", v
)
411 found
[v
] = struct{}{}
413 if len(found
) == nKeys
/2 {
414 // Halfway through iteration, finish grow.
415 for i
:= 0; i
< nBuckets
; i
++ {
420 if len(found
) != nKeys
{
421 t
.Fatalf("missing value")
425 func TestMapIterOrder(t
*testing
.T
) {
426 if runtime
.Compiler
== "gccgo" {
427 t
.Skip("skipping for gccgo")
430 for _
, n
:= range [...]int{3, 7, 9, 15} {
431 for i
:= 0; i
< 1000; i
++ {
432 // Make m be {0: true, 1: true, ..., n-1: true}.
433 m
:= make(map[int]bool)
434 for i
:= 0; i
< n
; i
++ {
437 // Check that iterating over the map produces at least two different orderings.
438 ord
:= func() []int {
447 for try
:= 0; try
< 100; try
++ {
448 if !reflect
.DeepEqual(first
, ord()) {
454 t
.Errorf("Map with n=%d elements had consistent iteration order: %v", n
, first
)
462 func TestMapSparseIterOrder(t
*testing
.T
) {
463 // Run several rounds to increase the probability
464 // of failure. One is not enough.
465 if runtime
.Compiler
== "gccgo" {
466 t
.Skip("skipping for gccgo")
469 for round
:= 0; round
< 10; round
++ {
470 m
:= make(map[int]bool)
471 // Add 1000 items, remove 980.
472 for i
:= 0; i
< 1000; i
++ {
475 for i
:= 20; i
< 1000; i
++ {
481 first
= append(first
, i
)
484 // 800 chances to get a different iteration order.
485 // See bug 8736 for why we need so many tries.
486 for n
:= 0; n
< 800; n
++ {
490 // iteration order changed.
496 t
.Fatalf("constant iteration order on round %d: %v", round
, first
)
500 func TestMapStringBytesLookup(t
*testing
.T
) {
501 if runtime
.Compiler
== "gccgo" {
502 t
.Skip("skipping for gccgo")
504 // Use large string keys to avoid small-allocation coalescing,
505 // which can cause AllocsPerRun to report lower counts than it should.
507 "1000000000000000000000000000000000000000000000000": 1,
508 "2000000000000000000000000000000000000000000000000": 2,
510 buf
:= []byte("1000000000000000000000000000000000000000000000000")
511 if x
:= m
[string(buf
)]; x
!= 1 {
512 t
.Errorf(`m[string([]byte("1"))] = %d, want 1`, x
)
515 if x
:= m
[string(buf
)]; x
!= 2 {
516 t
.Errorf(`m[string([]byte("2"))] = %d, want 2`, x
)
520 n
:= testing
.AllocsPerRun(100, func() {
524 t
.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n
)
528 n
= testing
.AllocsPerRun(100, func() {
529 y
, ok
:= m
[string(buf
)]
536 t
.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n
)
540 func TestMapLargeKeyNoPointer(t
*testing
.T
) {
547 for i
:= 0; i
< I
; i
++ {
549 for j
:= 0; j
< N
; j
++ {
555 for i
:= 0; i
< I
; i
++ {
557 for j
:= 0; j
< N
; j
++ {
561 t
.Fatalf("corrupted map: want %+v, got %+v", i
, m
[v
])
566 func TestMapLargeValNoPointer(t
*testing
.T
) {
573 for i
:= 0; i
< I
; i
++ {
575 for j
:= 0; j
< N
; j
++ {
581 for i
:= 0; i
< I
; i
++ {
583 for j
:= 0; j
< N
; j
++ {
587 for j
:= 0; j
< N
; j
++ {
589 t
.Fatalf("corrupted map: want %+v, got %+v", v
, v1
)
595 func benchmarkMapPop(b
*testing
.B
, n
int) {
597 for i
:= 0; i
< b
.N
; i
++ {
598 for j
:= 0; j
< n
; j
++ {
601 for j
:= 0; j
< n
; j
++ {
602 // Use iterator to pop an element.
603 // We want this to be fast, see issue 8412.
612 func BenchmarkMapPop100(b
*testing
.B
) { benchmarkMapPop(b
, 100) }
613 func BenchmarkMapPop1000(b
*testing
.B
) { benchmarkMapPop(b
, 1000) }
614 func BenchmarkMapPop10000(b
*testing
.B
) { benchmarkMapPop(b
, 10000) }
616 func TestNonEscapingMap(t
*testing
.T
) {
617 t
.Skip("does not work on gccgo without better escape analysis")
618 n
:= testing
.AllocsPerRun(1000, func() {
619 m
:= make(map[int]int)
623 t
.Fatalf("want 0 allocs, got %v", n
)