test/map.go

   1 // run
   2
   3 // Copyright 2009 The Go Authors. All rights reserved.
   4 // Use of this source code is governed by a BSD-style
   5 // license that can be found in the LICENSE file.
   6
   7 // Test maps, almost exhaustively.
   8
   9 package main
  10
  11 import (
  12         "fmt"
  13         "math"
  14         "strconv"
  15         "time"
  16 )
  17
  18 const count = 100
  19
  20 func P(a []string) string {
  21         s := "{"
  22         for i := 0; i < len(a); i++ {
  23                 if i > 0 {
  24                         s += ","
  25                 }
  26                 s += `"` + a[i] + `"`
  27         }
  28         s += "}"
  29         return s
  30 }
  31
  32 func main() {
  33         testbasic()
  34         testfloat()
  35         testnan()
  36 }
  37
  38 func testbasic() {
  39         // Test a map literal.
  40         mlit := map[string]int{"0": 0, "1": 1, "2": 2, "3": 3, "4": 4}
  41         for i := 0; i < len(mlit); i++ {
  42                 s := string([]byte{byte(i) + '0'})
  43                 if mlit[s] != i {
  44                         fmt.Printf("mlit[%s] = %d\n", s, mlit[s])
  45                 }
  46         }
  47
  48         mib := make(map[int]bool)
  49         mii := make(map[int]int)
  50         mfi := make(map[float32]int)
  51         mif := make(map[int]float32)
  52         msi := make(map[string]int)
  53         mis := make(map[int]string)
  54         mss := make(map[string]string)
  55         mspa := make(map[string][]string)
  56         // BUG need an interface map both ways too
  57
  58         type T struct {
  59                 i int64 // can't use string here; struct values are only compared at the top level
  60                 f float32
  61         }
  62         mipT := make(map[int]*T)
  63         mpTi := make(map[*T]int)
  64         mit := make(map[int]T)
  65         //      mti := make(map[T] int)
  66
  67         type M map[int]int
  68         mipM := make(map[int]M)
  69
  70         var apT [2 * count]*T
  71
  72         for i := 0; i < count; i++ {
  73                 s := strconv.Itoa(i)
  74                 s10 := strconv.Itoa(i * 10)
  75                 f := float32(i)
  76                 t := T{int64(i), f}
  77                 apT[i] = new(T)
  78                 apT[i].i = int64(i)
  79                 apT[i].f = f
  80                 apT[2*i] = new(T) // need twice as many entries as we use, for the nonexistence check
  81                 apT[2*i].i = int64(i)
  82                 apT[2*i].f = f
  83                 m := M{i: i + 1}
  84                 mib[i] = (i != 0)
  85                 mii[i] = 10 * i
  86                 mfi[float32(i)] = 10 * i
  87                 mif[i] = 10.0 * f
  88                 mis[i] = s
  89                 msi[s] = i
  90                 mss[s] = s10
  91                 mss[s] = s10
  92                 as := make([]string, 2)
  93                 as[0] = s10
  94                 as[1] = s10
  95                 mspa[s] = as
  96                 mipT[i] = apT[i]
  97                 mpTi[apT[i]] = i
  98                 mipM[i] = m
  99                 mit[i] = t
 100                 //      mti[t] = i
 101         }
 102
 103         // test len
 104         if len(mib) != count {
 105                 fmt.Printf("len(mib) = %d\n", len(mib))
 106         }
 107         if len(mii) != count {
 108                 fmt.Printf("len(mii) = %d\n", len(mii))
 109         }
 110         if len(mfi) != count {
 111                 fmt.Printf("len(mfi) = %d\n", len(mfi))
 112         }
 113         if len(mif) != count {
 114                 fmt.Printf("len(mif) = %d\n", len(mif))
 115         }
 116         if len(msi) != count {
 117                 fmt.Printf("len(msi) = %d\n", len(msi))
 118         }
 119         if len(mis) != count {
 120                 fmt.Printf("len(mis) = %d\n", len(mis))
 121         }
 122         if len(mss) != count {
 123                 fmt.Printf("len(mss) = %d\n", len(mss))
 124         }
 125         if len(mspa) != count {
 126                 fmt.Printf("len(mspa) = %d\n", len(mspa))
 127         }
 128         if len(mipT) != count {
 129                 fmt.Printf("len(mipT) = %d\n", len(mipT))
 130         }
 131         if len(mpTi) != count {
 132                 fmt.Printf("len(mpTi) = %d\n", len(mpTi))
 133         }
 134         //      if len(mti) != count {
 135         //              fmt.Printf("len(mti) = %d\n", len(mti))
 136         //      }
 137         if len(mipM) != count {
 138                 fmt.Printf("len(mipM) = %d\n", len(mipM))
 139         }
 140         //      if len(mti) != count {
 141         //              fmt.Printf("len(mti) = %d\n", len(mti))
 142         //      }
 143         if len(mit) != count {
 144                 fmt.Printf("len(mit) = %d\n", len(mit))
 145         }
 146
 147         // test construction directly
 148         for i := 0; i < count; i++ {
 149                 s := strconv.Itoa(i)
 150                 s10 := strconv.Itoa(i * 10)
 151                 f := float32(i)
 152                 // BUG m := M(i, i+1)
 153                 if mib[i] != (i != 0) {
 154                         fmt.Printf("mib[%d] = %t\n", i, mib[i])
 155                 }
 156                 if mii[i] != 10*i {
 157                         fmt.Printf("mii[%d] = %d\n", i, mii[i])
 158                 }
 159                 if mfi[f] != 10*i {
 160                         fmt.Printf("mfi[%d] = %d\n", i, mfi[f])
 161                 }
 162                 if mif[i] != 10.0*f {
 163                         fmt.Printf("mif[%d] = %g\n", i, mif[i])
 164                 }
 165                 if mis[i] != s {
 166                         fmt.Printf("mis[%d] = %s\n", i, mis[i])
 167                 }
 168                 if msi[s] != i {
 169                         fmt.Printf("msi[%s] = %d\n", s, msi[s])
 170                 }
 171                 if mss[s] != s10 {
 172                         fmt.Printf("mss[%s] = %g\n", s, mss[s])
 173                 }
 174                 for j := 0; j < len(mspa[s]); j++ {
 175                         if mspa[s][j] != s10 {
 176                                 fmt.Printf("mspa[%s][%d] = %s\n", s, j, mspa[s][j])
 177                         }
 178                 }
 179                 if mipT[i].i != int64(i) || mipT[i].f != f {
 180                         fmt.Printf("mipT[%d] = %v\n", i, mipT[i])
 181                 }
 182                 if mpTi[apT[i]] != i {
 183                         fmt.Printf("mpTi[apT[%d]] = %d\n", i, mpTi[apT[i]])
 184                 }
 185                 //      if(mti[t] != i) {
 186                 //              fmt.Printf("mti[%s] = %s\n", s, mti[t])
 187                 //      }
 188                 if mipM[i][i] != i+1 {
 189                         fmt.Printf("mipM[%d][%d] = %d\n", i, i, mipM[i][i])
 190                 }
 191                 //      if(mti[t] != i) {
 192                 //              fmt.Printf("mti[%v] = %d\n", t, mti[t])
 193                 //      }
 194                 if mit[i].i != int64(i) || mit[i].f != f {
 195                         fmt.Printf("mit[%d] = {%d %g}\n", i, mit[i].i, mit[i].f)
 196                 }
 197         }
 198
 199         // test existence with tuple check
 200         // failed lookups yield a false value for the boolean.
 201         for i := 0; i < count; i++ {
 202                 s := strconv.Itoa(i)
 203                 f := float32(i)
 204                 {
 205                         _, b := mib[i]
 206                         if !b {
 207                                 fmt.Printf("tuple existence decl: mib[%d]\n", i)
 208                         }
 209                         _, b = mib[i]
 210                         if !b {
 211                                 fmt.Printf("tuple existence assign: mib[%d]\n", i)
 212                         }
 213                 }
 214                 {
 215                         _, b := mii[i]
 216                         if !b {
 217                                 fmt.Printf("tuple existence decl: mii[%d]\n", i)
 218                         }
 219                         _, b = mii[i]
 220                         if !b {
 221                                 fmt.Printf("tuple existence assign: mii[%d]\n", i)
 222                         }
 223                 }
 224                 {
 225                         _, b := mfi[f]
 226                         if !b {
 227                                 fmt.Printf("tuple existence decl: mfi[%d]\n", i)
 228                         }
 229                         _, b = mfi[f]
 230                         if !b {
 231                                 fmt.Printf("tuple existence assign: mfi[%d]\n", i)
 232                         }
 233                 }
 234                 {
 235                         _, b := mif[i]
 236                         if !b {
 237                                 fmt.Printf("tuple existence decl: mif[%d]\n", i)
 238                         }
 239                         _, b = mif[i]
 240                         if !b {
 241                                 fmt.Printf("tuple existence assign: mif[%d]\n", i)
 242                         }
 243                 }
 244                 {
 245                         _, b := mis[i]
 246                         if !b {
 247                                 fmt.Printf("tuple existence decl: mis[%d]\n", i)
 248                         }
 249                         _, b = mis[i]
 250                         if !b {
 251                                 fmt.Printf("tuple existence assign: mis[%d]\n", i)
 252                         }
 253                 }
 254                 {
 255                         _, b := msi[s]
 256                         if !b {
 257                                 fmt.Printf("tuple existence decl: msi[%d]\n", i)
 258                         }
 259                         _, b = msi[s]
 260                         if !b {
 261                                 fmt.Printf("tuple existence assign: msi[%d]\n", i)
 262                         }
 263                 }
 264                 {
 265                         _, b := mss[s]
 266                         if !b {
 267                                 fmt.Printf("tuple existence decl: mss[%d]\n", i)
 268                         }
 269                         _, b = mss[s]
 270                         if !b {
 271                                 fmt.Printf("tuple existence assign: mss[%d]\n", i)
 272                         }
 273                 }
 274                 {
 275                         _, b := mspa[s]
 276                         if !b {
 277                                 fmt.Printf("tuple existence decl: mspa[%d]\n", i)
 278                         }
 279                         _, b = mspa[s]
 280                         if !b {
 281                                 fmt.Printf("tuple existence assign: mspa[%d]\n", i)
 282                         }
 283                 }
 284                 {
 285                         _, b := mipT[i]
 286                         if !b {
 287                                 fmt.Printf("tuple existence decl: mipT[%d]\n", i)
 288                         }
 289                         _, b = mipT[i]
 290                         if !b {
 291                                 fmt.Printf("tuple existence assign: mipT[%d]\n", i)
 292                         }
 293                 }
 294                 {
 295                         _, b := mpTi[apT[i]]
 296                         if !b {
 297                                 fmt.Printf("tuple existence decl: mpTi[apT[%d]]\n", i)
 298                         }
 299                         _, b = mpTi[apT[i]]
 300                         if !b {
 301                                 fmt.Printf("tuple existence assign: mpTi[apT[%d]]\n", i)
 302                         }
 303                 }
 304                 {
 305                         _, b := mipM[i]
 306                         if !b {
 307                                 fmt.Printf("tuple existence decl: mipM[%d]\n", i)
 308                         }
 309                         _, b = mipM[i]
 310                         if !b {
 311                                 fmt.Printf("tuple existence assign: mipM[%d]\n", i)
 312                         }
 313                 }
 314                 {
 315                         _, b := mit[i]
 316                         if !b {
 317                                 fmt.Printf("tuple existence decl: mit[%d]\n", i)
 318                         }
 319                         _, b = mit[i]
 320                         if !b {
 321                                 fmt.Printf("tuple existence assign: mit[%d]\n", i)
 322                         }
 323                 }
 324                 //              {
 325                 //                      _, b := mti[t]
 326                 //                      if !b {
 327                 //                              fmt.Printf("tuple existence decl: mti[%d]\n", i)
 328                 //                      }
 329                 //                      _, b = mti[t]
 330                 //                      if !b {
 331                 //                              fmt.Printf("tuple existence assign: mti[%d]\n", i)
 332                 //                      }
 333                 //              }
 334         }
 335
 336         // test nonexistence with tuple check
 337         // failed lookups yield a false value for the boolean.
 338         for i := count; i < 2*count; i++ {
 339                 s := strconv.Itoa(i)
 340                 f := float32(i)
 341                 {
 342                         _, b := mib[i]
 343                         if b {
 344                                 fmt.Printf("tuple nonexistence decl: mib[%d]", i)
 345                         }
 346                         _, b = mib[i]
 347                         if b {
 348                                 fmt.Printf("tuple nonexistence assign: mib[%d]", i)
 349                         }
 350                 }
 351                 {
 352                         _, b := mii[i]
 353                         if b {
 354                                 fmt.Printf("tuple nonexistence decl: mii[%d]", i)
 355                         }
 356                         _, b = mii[i]
 357                         if b {
 358                                 fmt.Printf("tuple nonexistence assign: mii[%d]", i)
 359                         }
 360                 }
 361                 {
 362                         _, b := mfi[f]
 363                         if b {
 364                                 fmt.Printf("tuple nonexistence decl: mfi[%d]", i)
 365                         }
 366                         _, b = mfi[f]
 367                         if b {
 368                                 fmt.Printf("tuple nonexistence assign: mfi[%d]", i)
 369                         }
 370                 }
 371                 {
 372                         _, b := mif[i]
 373                         if b {
 374                                 fmt.Printf("tuple nonexistence decl: mif[%d]", i)
 375                         }
 376                         _, b = mif[i]
 377                         if b {
 378                                 fmt.Printf("tuple nonexistence assign: mif[%d]", i)
 379                         }
 380                 }
 381                 {
 382                         _, b := mis[i]
 383                         if b {
 384                                 fmt.Printf("tuple nonexistence decl: mis[%d]", i)
 385                         }
 386                         _, b = mis[i]
 387                         if b {
 388                                 fmt.Printf("tuple nonexistence assign: mis[%d]", i)
 389                         }
 390                 }
 391                 {
 392                         _, b := msi[s]
 393                         if b {
 394                                 fmt.Printf("tuple nonexistence decl: msi[%d]", i)
 395                         }
 396                         _, b = msi[s]
 397                         if b {
 398                                 fmt.Printf("tuple nonexistence assign: msi[%d]", i)
 399                         }
 400                 }
 401                 {
 402                         _, b := mss[s]
 403                         if b {
 404                                 fmt.Printf("tuple nonexistence decl: mss[%d]", i)
 405                         }
 406                         _, b = mss[s]
 407                         if b {
 408                                 fmt.Printf("tuple nonexistence assign: mss[%d]", i)
 409                         }
 410                 }
 411                 {
 412                         _, b := mspa[s]
 413                         if b {
 414                                 fmt.Printf("tuple nonexistence decl: mspa[%d]", i)
 415                         }
 416                         _, b = mspa[s]
 417                         if b {
 418                                 fmt.Printf("tuple nonexistence assign: mspa[%d]", i)
 419                         }
 420                 }
 421                 {
 422                         _, b := mipT[i]
 423                         if b {
 424                                 fmt.Printf("tuple nonexistence decl: mipT[%d]", i)
 425                         }
 426                         _, b = mipT[i]
 427                         if b {
 428                                 fmt.Printf("tuple nonexistence assign: mipT[%d]", i)
 429                         }
 430                 }
 431                 {
 432                         _, b := mpTi[apT[i]]
 433                         if b {
 434                                 fmt.Printf("tuple nonexistence decl: mpTi[apt[%d]]", i)
 435                         }
 436                         _, b = mpTi[apT[i]]
 437                         if b {
 438                                 fmt.Printf("tuple nonexistence assign: mpTi[apT[%d]]", i)
 439                         }
 440                 }
 441                 {
 442                         _, b := mipM[i]
 443                         if b {
 444                                 fmt.Printf("tuple nonexistence decl: mipM[%d]", i)
 445                         }
 446                         _, b = mipM[i]
 447                         if b {
 448                                 fmt.Printf("tuple nonexistence assign: mipM[%d]", i)
 449                         }
 450                 }
 451                 //              {
 452                 //                      _, b := mti[t]
 453                 //                      if b {
 454                 //                              fmt.Printf("tuple nonexistence decl: mti[%d]", i)
 455                 //                      }
 456                 //                      _, b = mti[t]
 457                 //                      if b {
 458                 //                              fmt.Printf("tuple nonexistence assign: mti[%d]", i)
 459                 //                      }
 460                 //              }
 461                 {
 462                         _, b := mit[i]
 463                         if b {
 464                                 fmt.Printf("tuple nonexistence decl: mit[%d]", i)
 465                         }
 466                         _, b = mit[i]
 467                         if b {
 468                                 fmt.Printf("tuple nonexistence assign: mit[%d]", i)
 469                         }
 470                 }
 471         }
 472
 473         // tests for structured map element updates
 474         for i := 0; i < count; i++ {
 475                 s := strconv.Itoa(i)
 476                 mspa[s][i%2] = "deleted"
 477                 if mspa[s][i%2] != "deleted" {
 478                         fmt.Printf("update mspa[%s][%d] = %s\n", s, i%2, mspa[s][i%2])
 479                 }
 480
 481                 mipT[i].i += 1
 482                 if mipT[i].i != int64(i)+1 {
 483                         fmt.Printf("update mipT[%d].i = %d\n", i, mipT[i].i)
 484                 }
 485                 mipT[i].f = float32(i + 1)
 486                 if mipT[i].f != float32(i+1) {
 487                         fmt.Printf("update mipT[%d].f = %g\n", i, mipT[i].f)
 488                 }
 489
 490                 mipM[i][i]++
 491                 if mipM[i][i] != (i+1)+1 {
 492                         fmt.Printf("update mipM[%d][%d] = %d\n", i, i, mipM[i][i])
 493                 }
 494         }
 495
 496         // test range on nil map
 497         var mnil map[string]int
 498         for _, _ = range mnil {
 499                 panic("range mnil")
 500         }
 501 }
 502
 503 func testfloat() {
 504         // Test floating point numbers in maps.
 505         // Two map keys refer to the same entry if the keys are ==.
 506         // The special cases, then, are that +0 == -0 and that NaN != NaN.
 507
 508         {
 509                 var (
 510                         pz   = float32(0)
 511                         nz   = math.Float32frombits(1 << 31)
 512                         nana = float32(math.NaN())
 513                         nanb = math.Float32frombits(math.Float32bits(nana) ^ 2)
 514                 )
 515
 516                 m := map[float32]string{
 517                         pz:   "+0",
 518                         nana: "NaN",
 519                         nanb: "NaN",
 520                 }
 521                 if m[pz] != "+0" {
 522                         fmt.Println("float32 map cannot read back m[+0]:", m[pz])
 523                 }
 524                 if m[nz] != "+0" {
 525                         fmt.Println("float32 map does not treat", pz, "and", nz, "as equal for read")
 526                         fmt.Println("float32 map does not treat -0 and +0 as equal for read")
 527                 }
 528                 m[nz] = "-0"
 529                 if m[pz] != "-0" {
 530                         fmt.Println("float32 map does not treat -0 and +0 as equal for write")
 531                 }
 532                 if _, ok := m[nana]; ok {
 533                         fmt.Println("float32 map allows NaN lookup (a)")
 534                 }
 535                 if _, ok := m[nanb]; ok {
 536                         fmt.Println("float32 map allows NaN lookup (b)")
 537                 }
 538                 if len(m) != 3 {
 539                         fmt.Println("float32 map should have 3 entries:", m)
 540                 }
 541                 m[nana] = "NaN"
 542                 m[nanb] = "NaN"
 543                 if len(m) != 5 {
 544                         fmt.Println("float32 map should have 5 entries:", m)
 545                 }
 546         }
 547
 548         {
 549                 var (
 550                         pz   = float64(0)
 551                         nz   = math.Float64frombits(1 << 63)
 552                         nana = float64(math.NaN())
 553                         nanb = math.Float64frombits(math.Float64bits(nana) ^ 2)
 554                 )
 555
 556                 m := map[float64]string{
 557                         pz:   "+0",
 558                         nana: "NaN",
 559                         nanb: "NaN",
 560                 }
 561                 if m[nz] != "+0" {
 562                         fmt.Println("float64 map does not treat -0 and +0 as equal for read")
 563                 }
 564                 m[nz] = "-0"
 565                 if m[pz] != "-0" {
 566                         fmt.Println("float64 map does not treat -0 and +0 as equal for write")
 567                 }
 568                 if _, ok := m[nana]; ok {
 569                         fmt.Println("float64 map allows NaN lookup (a)")
 570                 }
 571                 if _, ok := m[nanb]; ok {
 572                         fmt.Println("float64 map allows NaN lookup (b)")
 573                 }
 574                 if len(m) != 3 {
 575                         fmt.Println("float64 map should have 3 entries:", m)
 576                 }
 577                 m[nana] = "NaN"
 578                 m[nanb] = "NaN"
 579                 if len(m) != 5 {
 580                         fmt.Println("float64 map should have 5 entries:", m)
 581                 }
 582         }
 583
 584         {
 585                 var (
 586                         pz   = complex64(0)
 587                         nz   = complex(0, math.Float32frombits(1<<31))
 588                         nana = complex(5, float32(math.NaN()))
 589                         nanb = complex(5, math.Float32frombits(math.Float32bits(float32(math.NaN()))^2))
 590                 )
 591
 592                 m := map[complex64]string{
 593                         pz:   "+0",
 594                         nana: "NaN",
 595                         nanb: "NaN",
 596                 }
 597                 if m[nz] != "+0" {
 598                         fmt.Println("complex64 map does not treat -0 and +0 as equal for read")
 599                 }
 600                 m[nz] = "-0"
 601                 if m[pz] != "-0" {
 602                         fmt.Println("complex64 map does not treat -0 and +0 as equal for write")
 603                 }
 604                 if _, ok := m[nana]; ok {
 605                         fmt.Println("complex64 map allows NaN lookup (a)")
 606                 }
 607                 if _, ok := m[nanb]; ok {
 608                         fmt.Println("complex64 map allows NaN lookup (b)")
 609                 }
 610                 if len(m) != 3 {
 611                         fmt.Println("complex64 map should have 3 entries:", m)
 612                 }
 613                 m[nana] = "NaN"
 614                 m[nanb] = "NaN"
 615                 if len(m) != 5 {
 616                         fmt.Println("complex64 map should have 5 entries:", m)
 617                 }
 618         }
 619
 620         {
 621                 var (
 622                         pz   = complex128(0)
 623                         nz   = complex(0, math.Float64frombits(1<<63))
 624                         nana = complex(5, float64(math.NaN()))
 625                         nanb = complex(5, math.Float64frombits(math.Float64bits(float64(math.NaN()))^2))
 626                 )
 627
 628                 m := map[complex128]string{
 629                         pz:   "+0",
 630                         nana: "NaN",
 631                         nanb: "NaN",
 632                 }
 633                 if m[nz] != "+0" {
 634                         fmt.Println("complex128 map does not treat -0 and +0 as equal for read")
 635                 }
 636                 m[nz] = "-0"
 637                 if m[pz] != "-0" {
 638                         fmt.Println("complex128 map does not treat -0 and +0 as equal for write")
 639                 }
 640                 if _, ok := m[nana]; ok {
 641                         fmt.Println("complex128 map allows NaN lookup (a)")
 642                 }
 643                 if _, ok := m[nanb]; ok {
 644                         fmt.Println("complex128 map allows NaN lookup (b)")
 645                 }
 646                 if len(m) != 3 {
 647                         fmt.Println("complex128 map should have 3 entries:", m)
 648                 }
 649                 m[nana] = "NaN"
 650                 m[nanb] = "NaN"
 651                 if len(m) != 5 {
 652                         fmt.Println("complex128 map should have 5 entries:", m)
 653                 }
 654         }
 655 }
 656
 657 func testnan() {
 658         // Test that NaNs in maps don't go quadratic.
 659         t := func(n int) time.Duration {
 660                 t0 := time.Now()
 661                 m := map[float64]int{}
 662                 nan := math.NaN()
 663                 for i := 0; i < n; i++ {
 664                         m[nan] = 1
 665                 }
 666                 if len(m) != n {
 667                         panic("wrong size map after nan insertion")
 668                 }
 669                 return time.Since(t0)
 670         }
 671
 672         // Depending on the machine and OS, this test might be too fast
 673         // to measure with accurate enough granularity. On failure,
 674         // make it run longer, hoping that the timing granularity
 675         // is eventually sufficient.
 676
 677         n := 30000 // 0.02 seconds on a MacBook Air
 678         fails := 0
 679         for {
 680                 t1 := t(n)
 681                 t2 := t(2 * n)
 682                 // should be 2x (linear); allow up to 3x
 683                 if t2 < 3*t1 {
 684                         return
 685                 }
 686                 fails++
 687                 if fails == 4 {
 688                         fmt.Printf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2)
 689                         return
 690                 }
 691                 n *= 2
 692         }
 693 }