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")
34 if math
.Copysign(1.0, k
) > 0 {
39 m
= make(map[float64]bool, 0)
40 m
[math
.Copysign(0.0, -1.0)] = true
41 m
[+0.0] = true // should overwrite -0.0 entry
44 t
.Error("length wrong")
48 if math
.Copysign(1.0, k
) < 0 {
54 // nan is a good test because nan != nan, and nan has
55 // a randomized hash value.
56 func TestNan(t
*testing
.T
) {
57 m
:= make(map[float64]int, 0)
63 t
.Error("length wrong")
68 t
.Error("nan disappeared")
70 if (v
& (v
- 1)) != 0 {
71 t
.Error("value wrong")
76 t
.Error("values wrong")
80 // Maps aren't actually copied on assignment.
81 func TestAlias(t
*testing
.T
) {
82 m
:= make(map[int]int, 0)
87 t
.Error("alias didn't work")
91 func TestGrowWithNaN(t
*testing
.T
) {
92 m
:= make(map[float64]int, 4)
100 for k
, v
:= range m
{
102 // force a hashtable resize
103 for i
:= 0; i
< 100; i
++ {
114 t
.Error("NaN keys lost during grow")
117 t
.Error("NaN values lost during grow")
121 type FloatInt
struct {
126 func TestGrowWithNegativeZero(t
*testing
.T
) {
127 negzero
:= math
.Copysign(0.0, -1.0)
128 m
:= make(map[FloatInt
]int, 4)
129 m
[FloatInt
{0.0, 0}] = 1
130 m
[FloatInt
{0.0, 1}] = 2
131 m
[FloatInt
{0.0, 2}] = 4
132 m
[FloatInt
{0.0, 3}] = 8
137 // The first iteration should return the +0 key.
138 // The subsequent iterations should return the -0 key.
139 // I'm not really sure this is required by the spec,
140 // but it makes sense.
141 // TODO: are we allowed to get the first entry returned again???
142 for k
, v
:= range m
{
145 } // ignore entries added to grow table
147 if math
.Copysign(1.0, k
.x
) < 0 {
149 t
.Error("key/value not updated together 1")
155 t
.Error("key/value not updated together 2", k
, v
)
160 // force a hashtable resize
161 for i
:= 0; i
< 100; i
++ {
162 m
[FloatInt
{3.0, i
}] = 0
164 // then change all the entries
166 m
[FloatInt
{negzero
, 0}] = 1 |
16
167 m
[FloatInt
{negzero
, 1}] = 2 |
16
168 m
[FloatInt
{negzero
, 2}] = 4 |
16
169 m
[FloatInt
{negzero
, 3}] = 8 |
16
174 t
.Error("entry missing", s
)
177 t
.Error("wrong number of entries returned by iterator", cnt
)
180 t
.Error("update to negzero missed by iteration", negcnt
)
184 func TestIterGrowAndDelete(t
*testing
.T
) {
185 m
:= make(map[int]int, 4)
186 for i
:= 0; i
< 100; i
++ {
193 for i
:= 100; i
< 1000; i
++ {
196 // delete all odd keys
197 for i
:= 1; i
< 1000; i
+= 2 {
203 t
.Error("odd value returned")
209 // make sure old bucket arrays don't get GCd while
210 // an iterator is still using them.
211 func TestIterGrowWithGC(t
*testing
.T
) {
212 m
:= make(map[int]int, 4)
213 for i
:= 0; i
< 16; i
++ {
220 bitmask |
= 1 << uint(k
)
224 for i
:= 100; i
< 1000; i
++ {
232 if bitmask
!= 1<<16-1 {
233 t
.Error("missing key", bitmask
)
237 func testConcurrentReadsAfterGrowth(t
*testing
.T
, useReflect
bool) {
239 if runtime
.GOMAXPROCS(-1) == 1 {
240 if runtime
.GOARCH
== "s390" {
241 // Test uses too much address space on 31-bit S390.
242 defer runtime
.GOMAXPROCS(runtime
.GOMAXPROCS(8))
244 defer runtime
.GOMAXPROCS(runtime
.GOMAXPROCS(16))
251 numLoop
, numGrowStep
= 2, 500
253 for i
:= 0; i
< numLoop
; i
++ {
254 m
:= make(map[int]int, 0)
255 for gs
:= 0; gs
< numGrowStep
; gs
++ {
257 var wg sync
.WaitGroup
258 wg
.Add(numReader
* 2)
259 for nr
:= 0; nr
< numReader
; nr
++ {
267 for key
:= 0; key
< gs
; key
++ {
275 mv
:= reflect
.ValueOf(m
)
277 for _
, k
:= range keys
{
288 func TestConcurrentReadsAfterGrowth(t
*testing
.T
) {
289 testConcurrentReadsAfterGrowth(t
, false)
292 func TestConcurrentReadsAfterGrowthReflect(t
*testing
.T
) {
293 testConcurrentReadsAfterGrowth(t
, true)
296 func TestBigItems(t
*testing
.T
) {
298 for i
:= 0; i
< 256; i
++ {
301 m
:= make(map[[256]string][256]string, 4)
302 for i
:= 0; i
< 100; i
++ {
303 key
[37] = fmt
.Sprintf("string%02d", i
)
307 var values
[100]string
309 for k
, v
:= range m
{
314 sort
.Strings(keys
[:])
315 sort
.Strings(values
[:])
316 for i
:= 0; i
< 100; i
++ {
317 if keys
[i
] != fmt
.Sprintf("string%02d", i
) {
318 t
.Errorf("#%d: missing key: %v", i
, keys
[i
])
320 if values
[i
] != fmt
.Sprintf("string%02d", i
) {
321 t
.Errorf("#%d: missing value: %v", i
, values
[i
])
326 func TestMapHugeZero(t
*testing
.T
) {
331 t
.Errorf("map value not zero")
335 t
.Errorf("map value should be missing")
338 t
.Errorf("map value not zero")
345 func TestEmptyKeyAndValue(t
*testing
.T
) {
346 a
:= make(map[int]empty
, 4)
347 b
:= make(map[empty
]int, 4)
348 c
:= make(map[empty
]empty
, 4)
355 t
.Errorf("empty value insert problem")
358 t
.Errorf("empty key returned wrong value")
362 // Tests a map with a single bucket, with same-lengthed short keys
363 // ("quick keys") as well as long keys.
364 func TestSingleBucketMapStringKeys_DupLen(t
*testing
.T
) {
365 testMapLookups(t
, map[string]string{
369 "bar": "barval", // same key length as "foo"
371 strings
.Repeat("x", 128): "longval1",
372 strings
.Repeat("y", 128): "longval2",
376 // Tests a map with a single bucket, with all keys having different lengths.
377 func TestSingleBucketMapStringKeys_NoDupLen(t
*testing
.T
) {
378 testMapLookups(t
, map[string]string{
385 strings
.Repeat("x", 128): "longval",
389 func testMapLookups(t
*testing
.T
, m
map[string]string) {
390 for k
, v
:= range m
{
392 t
.Fatalf("m[%q] = %q; want %q", k
, m
[k
], v
)
397 // Tests whether the iterator returns the right elements when
398 // started in the middle of a grow, when the keys are NaNs.
399 func TestMapNanGrowIterator(t
*testing
.T
) {
400 m
:= make(map[float64]int)
403 // To fill nBuckets buckets takes LOAD * nBuckets keys.
404 nKeys
:= int(nBuckets
* *runtime
.HashLoad
)
406 // Get map to full point with nan keys.
407 for i
:= 0; i
< nKeys
; i
++ {
415 found
:= make(map[int]struct{})
416 for _
, v
:= range m
{
418 if _
, repeat
:= found
[v
]; repeat
{
419 t
.Fatalf("repeat of value %d", v
)
421 found
[v
] = struct{}{}
423 if len(found
) == nKeys
/2 {
424 // Halfway through iteration, finish grow.
425 for i
:= 0; i
< nBuckets
; i
++ {
430 if len(found
) != nKeys
{
431 t
.Fatalf("missing value")
435 func TestMapIterOrder(t
*testing
.T
) {
436 for _
, n
:= range [...]int{3, 7, 9, 15} {
437 for i
:= 0; i
< 1000; i
++ {
438 // Make m be {0: true, 1: true, ..., n-1: true}.
439 m
:= make(map[int]bool)
440 for i
:= 0; i
< n
; i
++ {
443 // Check that iterating over the map produces at least two different orderings.
444 ord
:= func() []int {
453 for try
:= 0; try
< 100; try
++ {
454 if !reflect
.DeepEqual(first
, ord()) {
460 t
.Errorf("Map with n=%d elements had consistent iteration order: %v", n
, first
)
468 func TestMapSparseIterOrder(t
*testing
.T
) {
469 // Run several rounds to increase the probability
470 // of failure. One is not enough.
472 for round
:= 0; round
< 10; round
++ {
473 m
:= make(map[int]bool)
474 // Add 1000 items, remove 980.
475 for i
:= 0; i
< 1000; i
++ {
478 for i
:= 20; i
< 1000; i
++ {
484 first
= append(first
, i
)
487 // 800 chances to get a different iteration order.
488 // See bug 8736 for why we need so many tries.
489 for n
:= 0; n
< 800; n
++ {
493 // iteration order changed.
499 t
.Fatalf("constant iteration order on round %d: %v", round
, first
)
503 func TestMapStringBytesLookup(t
*testing
.T
) {
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
)
519 t
.Skip("does not work on gccgo without better escape analysis")
522 n
:= testing
.AllocsPerRun(100, func() {
526 t
.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n
)
530 n
= testing
.AllocsPerRun(100, func() {
531 y
, ok
:= m
[string(buf
)]
538 t
.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n
)
542 func TestMapLargeKeyNoPointer(t
*testing
.T
) {
549 for i
:= 0; i
< I
; i
++ {
551 for j
:= 0; j
< N
; j
++ {
557 for i
:= 0; i
< I
; i
++ {
559 for j
:= 0; j
< N
; j
++ {
563 t
.Fatalf("corrupted map: want %+v, got %+v", i
, m
[v
])
568 func TestMapLargeValNoPointer(t
*testing
.T
) {
575 for i
:= 0; i
< I
; i
++ {
577 for j
:= 0; j
< N
; j
++ {
583 for i
:= 0; i
< I
; i
++ {
585 for j
:= 0; j
< N
; j
++ {
589 for j
:= 0; j
< N
; j
++ {
591 t
.Fatalf("corrupted map: want %+v, got %+v", v
, v1
)
597 func benchmarkMapPop(b
*testing
.B
, n
int) {
599 for i
:= 0; i
< b
.N
; i
++ {
600 for j
:= 0; j
< n
; j
++ {
603 for j
:= 0; j
< n
; j
++ {
604 // Use iterator to pop an element.
605 // We want this to be fast, see issue 8412.
614 func BenchmarkMapPop100(b
*testing
.B
) { benchmarkMapPop(b
, 100) }
615 func BenchmarkMapPop1000(b
*testing
.B
) { benchmarkMapPop(b
, 1000) }
616 func BenchmarkMapPop10000(b
*testing
.B
) { benchmarkMapPop(b
, 10000) }
618 func TestNonEscapingMap(t
*testing
.T
) {
619 t
.Skip("does not work on gccgo without better escape analysis")
620 n
:= testing
.AllocsPerRun(1000, func() {
621 m
:= make(map[int]int)
625 t
.Fatalf("want 0 allocs, got %v", n
)