← Back to branch summary

~ubuntu-branches/ubuntu/vivid/golang/vivid

« back to all changes in this revision

Viewing changes to src/pkg/runtime/map_test.go

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-20 14:06:23 UTC
  • mfrom: (14.1.23 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130820140623-b414jfxi3m0qkmrq
Tags: 2:1.1.2-2ubuntu1
https://launchpad.net/bugs/1211749
https://launchpad.net/bugs/1202027
* Merge from Debian unstable (LP: #1211749, #1202027). Remaining changes:
  - 016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.
  - d/control,control.cross: Update Breaks/Replaces for Ubuntu
    versions to ensure smooth upgrades, regenerate control file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/runtime/map_test.go
 
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.
 
4
 
 
5
package runtime_test
 
6
 
 
7
import (
 
8
        "fmt"
 
9
        "math"
 
10
        "reflect"
 
11
        "runtime"
 
12
        "sort"
 
13
        "strings"
 
14
        "sync"
 
15
        "testing"
 
16
)
 
17
 
 
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)
 
25
 
 
26
        m[+0.0] = true
 
27
        m[math.Copysign(0.0, -1.0)] = true // should overwrite +0 entry
 
28
 
 
29
        if len(m) != 1 {
 
30
                t.Error("length wrong")
 
31
        }
 
32
 
 
33
        for k := range m {
 
34
                if math.Copysign(1.0, k) > 0 {
 
35
                        t.Error("wrong sign")
 
36
                }
 
37
        }
 
38
 
 
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
 
42
 
 
43
        if len(m) != 1 {
 
44
                t.Error("length wrong")
 
45
        }
 
46
 
 
47
        for k := range m {
 
48
                if math.Copysign(1.0, k) < 0 {
 
49
                        t.Error("wrong sign")
 
50
                }
 
51
        }
 
52
}
 
53
 
 
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)
 
58
        nan := math.NaN()
 
59
        m[nan] = 1
 
60
        m[nan] = 2
 
61
        m[nan] = 4
 
62
        if len(m) != 3 {
 
63
                t.Error("length wrong")
 
64
        }
 
65
        s := 0
 
66
        for k, v := range m {
 
67
                if k == k {
 
68
                        t.Error("nan disappeared")
 
69
                }
 
70
                if (v & (v - 1)) != 0 {
 
71
                        t.Error("value wrong")
 
72
                }
 
73
                s |= v
 
74
        }
 
75
        if s != 7 {
 
76
                t.Error("values wrong")
 
77
        }
 
78
}
 
79
 
 
80
// Maps aren't actually copied on assignment.
 
81
func TestAlias(t *testing.T) {
 
82
        m := make(map[int]int, 0)
 
83
        m[0] = 5
 
84
        n := m
 
85
        n[0] = 6
 
86
        if m[0] != 6 {
 
87
                t.Error("alias didn't work")
 
88
        }
 
89
}
 
90
 
 
91
func TestGrowWithNaN(t *testing.T) {
 
92
        m := make(map[float64]int, 4)
 
93
        nan := math.NaN()
 
94
        m[nan] = 1
 
95
        m[nan] = 2
 
96
        m[nan] = 4
 
97
        cnt := 0
 
98
        s := 0
 
99
        growflag := true
 
100
        for k, v := range m {
 
101
                if growflag {
 
102
                        // force a hashtable resize
 
103
                        for i := 0; i < 100; i++ {
 
104
                                m[float64(i)] = i
 
105
                        }
 
106
                        growflag = false
 
107
                }
 
108
                if k != k {
 
109
                        cnt++
 
110
                        s |= v
 
111
                }
 
112
        }
 
113
        if cnt != 3 {
 
114
                t.Error("NaN keys lost during grow")
 
115
        }
 
116
        if s != 7 {
 
117
                t.Error("NaN values lost during grow")
 
118
        }
 
119
}
 
120
 
 
121
type FloatInt struct {
 
122
        x float64
 
123
        y int
 
124
}
 
125
 
 
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
 
133
        growflag := true
 
134
        s := 0
 
135
        cnt := 0
 
136
        negcnt := 0
 
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 {
 
143
                if v == 0 {
 
144
                        continue
 
145
                } // ignore entries added to grow table
 
146
                cnt++
 
147
                if math.Copysign(1.0, k.x) < 0 {
 
148
                        if v&16 == 0 {
 
149
                                t.Error("key/value not updated together 1")
 
150
                        }
 
151
                        negcnt++
 
152
                        s |= v & 15
 
153
                } else {
 
154
                        if v&16 == 16 {
 
155
                                t.Error("key/value not updated together 2", k, v)
 
156
                        }
 
157
                        s |= v
 
158
                }
 
159
                if growflag {
 
160
                        // force a hashtable resize
 
161
                        for i := 0; i < 100; i++ {
 
162
                                m[FloatInt{3.0, i}] = 0
 
163
                        }
 
164
                        // then change all the entries
 
165
                        // to negative zero
 
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
 
170
                        growflag = false
 
171
                }
 
172
        }
 
173
        if s != 15 {
 
174
                t.Error("entry missing", s)
 
175
        }
 
176
        if cnt != 4 {
 
177
                t.Error("wrong number of entries returned by iterator", cnt)
 
178
        }
 
179
        if negcnt != 3 {
 
180
                t.Error("update to negzero missed by iteration", negcnt)
 
181
        }
 
182
}
 
183
 
 
184
func TestIterGrowAndDelete(t *testing.T) {
 
185
        m := make(map[int]int, 4)
 
186
        for i := 0; i < 100; i++ {
 
187
                m[i] = i
 
188
        }
 
189
        growflag := true
 
190
        for k := range m {
 
191
                if growflag {
 
192
                        // grow the table
 
193
                        for i := 100; i < 1000; i++ {
 
194
                                m[i] = i
 
195
                        }
 
196
                        // delete all odd keys
 
197
                        for i := 1; i < 1000; i += 2 {
 
198
                                delete(m, i)
 
199
                        }
 
200
                        growflag = false
 
201
                } else {
 
202
                        if k&1 == 1 {
 
203
                                t.Error("odd value returned")
 
204
                        }
 
205
                }
 
206
        }
 
207
}
 
208
 
 
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++ {
 
214
                m[i] = i
 
215
        }
 
216
        growflag := true
 
217
        bitmask := 0
 
218
        for k := range m {
 
219
                if k < 16 {
 
220
                        bitmask |= 1 << uint(k)
 
221
                }
 
222
                if growflag {
 
223
                        // grow the table
 
224
                        for i := 100; i < 1000; i++ {
 
225
                                m[i] = i
 
226
                        }
 
227
                        // trigger a gc
 
228
                        runtime.GC()
 
229
                        growflag = false
 
230
                }
 
231
        }
 
232
        if bitmask != 1<<16-1 {
 
233
                t.Error("missing key", bitmask)
 
234
        }
 
235
}
 
236
 
 
237
func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
 
238
        if runtime.GOMAXPROCS(-1) == 1 {
 
239
                defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
 
240
        }
 
241
        numLoop := 10
 
242
        numGrowStep := 250
 
243
        numReader := 16
 
244
        if testing.Short() {
 
245
                numLoop, numGrowStep = 2, 500
 
246
        }
 
247
        for i := 0; i < numLoop; i++ {
 
248
                m := make(map[int]int, 0)
 
249
                for gs := 0; gs < numGrowStep; gs++ {
 
250
                        m[gs] = gs
 
251
                        var wg sync.WaitGroup
 
252
                        wg.Add(numReader * 2)
 
253
                        for nr := 0; nr < numReader; nr++ {
 
254
                                go func() {
 
255
                                        defer wg.Done()
 
256
                                        for _ = range m {
 
257
                                        }
 
258
                                }()
 
259
                                go func() {
 
260
                                        defer wg.Done()
 
261
                                        for key := 0; key < gs; key++ {
 
262
                                                _ = m[key]
 
263
                                        }
 
264
                                }()
 
265
                                if useReflect {
 
266
                                        wg.Add(1)
 
267
                                        go func() {
 
268
                                                defer wg.Done()
 
269
                                                mv := reflect.ValueOf(m)
 
270
                                                keys := mv.MapKeys()
 
271
                                                for _, k := range keys {
 
272
                                                        mv.MapIndex(k)
 
273
                                                }
 
274
                                        }()
 
275
                                }
 
276
                        }
 
277
                        wg.Wait()
 
278
                }
 
279
        }
 
280
}
 
281
 
 
282
func TestConcurrentReadsAfterGrowth(t *testing.T) {
 
283
        testConcurrentReadsAfterGrowth(t, false)
 
284
}
 
285
 
 
286
func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
 
287
        testConcurrentReadsAfterGrowth(t, true)
 
288
}
 
289
 
 
290
func TestBigItems(t *testing.T) {
 
291
        var key [256]string
 
292
        for i := 0; i < 256; i++ {
 
293
                key[i] = "foo"
 
294
        }
 
295
        m := make(map[[256]string][256]string, 4)
 
296
        for i := 0; i < 100; i++ {
 
297
                key[37] = fmt.Sprintf("string%02d", i)
 
298
                m[key] = key
 
299
        }
 
300
        var keys [100]string
 
301
        var values [100]string
 
302
        i := 0
 
303
        for k, v := range m {
 
304
                keys[i] = k[37]
 
305
                values[i] = v[37]
 
306
                i++
 
307
        }
 
308
        sort.Strings(keys[:])
 
309
        sort.Strings(values[:])
 
310
        for i := 0; i < 100; i++ {
 
311
                if keys[i] != fmt.Sprintf("string%02d", i) {
 
312
                        t.Errorf("#%d: missing key: %v", i, keys[i])
 
313
                }
 
314
                if values[i] != fmt.Sprintf("string%02d", i) {
 
315
                        t.Errorf("#%d: missing value: %v", i, values[i])
 
316
                }
 
317
        }
 
318
}
 
319
 
 
320
type empty struct {
 
321
}
 
322
 
 
323
func TestEmptyKeyAndValue(t *testing.T) {
 
324
        a := make(map[int]empty, 4)
 
325
        b := make(map[empty]int, 4)
 
326
        c := make(map[empty]empty, 4)
 
327
        a[0] = empty{}
 
328
        b[empty{}] = 0
 
329
        b[empty{}] = 1
 
330
        c[empty{}] = empty{}
 
331
 
 
332
        if len(a) != 1 {
 
333
                t.Errorf("empty value insert problem")
 
334
        }
 
335
        if b[empty{}] != 1 {
 
336
                t.Errorf("empty key returned wrong value")
 
337
        }
 
338
}
 
339
 
 
340
// Tests a map with a single bucket, with same-lengthed short keys
 
341
// ("quick keys") as well as long keys.
 
342
func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
 
343
        testMapLookups(t, map[string]string{
 
344
                "x":    "x1val",
 
345
                "xx":   "x2val",
 
346
                "foo":  "fooval",
 
347
                "bar":  "barval", // same key length as "foo"
 
348
                "xxxx": "x4val",
 
349
                strings.Repeat("x", 128): "longval1",
 
350
                strings.Repeat("y", 128): "longval2",
 
351
        })
 
352
}
 
353
 
 
354
// Tests a map with a single bucket, with all keys having different lengths.
 
355
func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
 
356
        testMapLookups(t, map[string]string{
 
357
                "x":                      "x1val",
 
358
                "xx":                     "x2val",
 
359
                "foo":                    "fooval",
 
360
                "xxxx":                   "x4val",
 
361
                "xxxxx":                  "x5val",
 
362
                "xxxxxx":                 "x6val",
 
363
                strings.Repeat("x", 128): "longval",
 
364
        })
 
365
}
 
366
 
 
367
func testMapLookups(t *testing.T, m map[string]string) {
 
368
        for k, v := range m {
 
369
                if m[k] != v {
 
370
                        t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
 
371
                }
 
372
        }
 
373
}