test/map.go

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