1// Copyright (c) 2017 Couchbase, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package vellum 16 17import ( 18 "bytes" 19 "io/ioutil" 20 "os" 21 "reflect" 22 "testing" 23) 24 25func TestRoundTripSimple(t *testing.T) { 26 f, err := ioutil.TempFile("", "vellum") 27 if err != nil { 28 t.Fatal(err) 29 } 30 defer func() { 31 err = f.Close() 32 if err != nil { 33 t.Fatal(err) 34 } 35 }() 36 defer func() { 37 err = os.Remove(f.Name()) 38 if err != nil { 39 t.Fatal(err) 40 } 41 }() 42 43 b, err := New(f, nil) 44 if err != nil { 45 t.Fatalf("error creating builder: %v", err) 46 } 47 48 err = insertStringMap(b, smallSample) 49 if err != nil { 50 t.Fatalf("error building: %v", err) 51 } 52 53 err = b.Close() 54 if err != nil { 55 t.Fatalf("err closing: %v", err) 56 } 57 58 fst, err := Open(f.Name()) 59 if err != nil { 60 t.Fatalf("error loading set: %v", err) 61 } 62 defer func() { 63 err = fst.Close() 64 if err != nil { 65 t.Fatal(err) 66 } 67 }() 68 69 // first check all the expected values 70 got := map[string]uint64{} 71 itr, err := fst.Iterator(nil, nil) 72 for err == nil { 73 key, val := itr.Current() 74 got[string(key)] = val 75 err = itr.Next() 76 } 77 if err != ErrIteratorDone { 78 t.Errorf("iterator error: %v", err) 79 } 80 if !reflect.DeepEqual(smallSample, got) { 81 t.Errorf("expected %v, got: %v", smallSample, got) 82 } 83 84 // some additional tests for items that should not exist 85 if ok, _ := fst.Contains([]byte("mo")); ok { 86 t.Errorf("expected to not contain mo, but did") 87 } 88 89 if ok, _ := fst.Contains([]byte("monr")); ok { 90 t.Errorf("expected to not contain monr, but did") 91 } 92 93 if ok, _ := fst.Contains([]byte("thur")); ok { 94 t.Errorf("expected to not contain thur, but did") 95 } 96 97 if ok, _ := fst.Contains([]byte("thurp")); ok { 98 t.Errorf("expected to not contain thurp, but did") 99 } 100 101 if ok, _ := fst.Contains([]byte("tue")); ok { 102 t.Errorf("expected to not contain tue, but did") 103 } 104 105 if ok, _ := fst.Contains([]byte("tuesd")); ok { 106 t.Errorf("expected to not contain tuesd, but did") 107 } 108 109 // a few more misc non-existent values to increase coverage 110 if ok, _ := fst.Contains([]byte("x")); ok { 111 t.Errorf("expected to not contain x, but did") 112 } 113 114 // now try accessing it through the Automaton interface 115 exists := AutomatonContains(fst, []byte("mon")) 116 if !exists { 117 t.Errorf("expected key 'mon' to exist, doesn't") 118 } 119 120 exists = AutomatonContains(fst, []byte("mons")) 121 if exists { 122 t.Errorf("expected key 'mo' to not exist, does") 123 } 124 125 // now try accessing it through the Transducer interface 126 var val uint64 127 exists, val = TransducerGet(fst, []byte("mon")) 128 if !exists { 129 t.Errorf("expected key 'mon' to exist, doesn't") 130 } 131 if val != 2 { 132 t.Errorf("expected val 2, got %d", val) 133 } 134 135 // now try accessing it through the Transducer interface 136 // for key that doesn't exist 137 exists, _ = TransducerGet(fst, []byte("mons")) 138 if exists { 139 t.Errorf("expected key 'mo' to not exist, does") 140 } 141} 142 143func TestRoundTripThousand(t *testing.T) { 144 dataset := thousandTestWords 145 randomThousandVals := randomValues(dataset) 146 147 f, err := ioutil.TempFile("", "vellum") 148 if err != nil { 149 t.Fatal(err) 150 } 151 defer func() { 152 err = f.Close() 153 if err != nil { 154 t.Fatal(err) 155 } 156 }() 157 defer func() { 158 err = os.Remove(f.Name()) 159 if err != nil { 160 t.Fatal(err) 161 } 162 }() 163 164 b, err := New(f, nil) 165 if err != nil { 166 t.Fatalf("error creating builder: %v", err) 167 } 168 169 err = insertStrings(b, dataset, randomThousandVals) 170 if err != nil { 171 t.Fatalf("error inserting thousand words: %v", err) 172 } 173 err = b.Close() 174 if err != nil { 175 t.Fatalf("error closing builder: %v", err) 176 } 177 178 fst, err := Open(f.Name()) 179 if err != nil { 180 t.Fatalf("error loading set: %v", err) 181 } 182 defer func() { 183 err = fst.Close() 184 if err != nil { 185 t.Fatal(err) 186 } 187 }() 188 189 // first check all the expected values 190 got := map[string]uint64{} 191 itr, err := fst.Iterator(nil, nil) 192 for err == nil { 193 key, val := itr.Current() 194 got[string(key)] = val 195 err = itr.Next() 196 } 197 if err != ErrIteratorDone { 198 t.Errorf("iterator error: %v", err) 199 } 200 201 for i := 0; i < len(dataset); i++ { 202 foundVal, ok := got[dataset[i]] 203 if !ok { 204 t.Fatalf("expected to find key, but didn't: %s", dataset[i]) 205 } 206 207 if foundVal != randomThousandVals[i] { 208 t.Fatalf("expected value %d for key %s, but got %d", randomThousandVals[i], dataset[i], foundVal) 209 } 210 211 // now remove it 212 delete(got, dataset[i]) 213 } 214 215 if len(got) != 0 { 216 t.Fatalf("expected got map to be empty after checking, still has %v", got) 217 } 218} 219 220func TestRoundTripEmpty(t *testing.T) { 221 f, err := ioutil.TempFile("", "vellum") 222 if err != nil { 223 t.Fatal(err) 224 } 225 defer func() { 226 err = f.Close() 227 if err != nil { 228 t.Fatal(err) 229 } 230 }() 231 defer func() { 232 err = os.Remove(f.Name()) 233 if err != nil { 234 t.Fatal(err) 235 } 236 }() 237 238 b, err := New(f, nil) 239 if err != nil { 240 t.Fatalf("error creating builder: %v", err) 241 } 242 243 err = b.Close() 244 if err != nil { 245 t.Fatalf("error closing: %v", err) 246 } 247 248 fst, err := Open(f.Name()) 249 if err != nil { 250 t.Fatalf("error loading set: %v", err) 251 } 252 defer func() { 253 err = fst.Close() 254 if err != nil { 255 t.Fatal(err) 256 } 257 }() 258 259 if fst.Len() != 0 { 260 t.Fatalf("expected length 0, got %d", fst.Len()) 261 } 262 263 // first check all the expected values 264 got := map[string]uint64{} 265 itr, err := fst.Iterator(nil, nil) 266 for err == nil { 267 key, val := itr.Current() 268 got[string(key)] = val 269 err = itr.Next() 270 } 271 if err != ErrIteratorDone { 272 t.Errorf("iterator error: %v", err) 273 } 274 if len(got) > 0 { 275 t.Errorf("expected not to see anything, got %v", got) 276 } 277} 278 279func TestRoundTripEmptyString(t *testing.T) { 280 f, err := ioutil.TempFile("", "vellum") 281 if err != nil { 282 t.Fatal(err) 283 } 284 defer func() { 285 err = f.Close() 286 if err != nil { 287 t.Fatal(err) 288 } 289 }() 290 defer func() { 291 err = os.Remove(f.Name()) 292 if err != nil { 293 t.Fatal(err) 294 } 295 }() 296 297 b, err := New(f, nil) 298 if err != nil { 299 t.Fatalf("error creating builder: %v", err) 300 } 301 302 err = b.Insert([]byte(""), 1) 303 if err != nil { 304 t.Fatalf("error inserting empty string") 305 } 306 307 err = b.Close() 308 if err != nil { 309 t.Fatalf("error closing: %v", err) 310 } 311 312 fst, err := Open(f.Name()) 313 if err != nil { 314 t.Fatalf("error loading set: %v", err) 315 } 316 defer func() { 317 err = fst.Close() 318 if err != nil { 319 t.Fatal(err) 320 } 321 }() 322 323 if fst.Len() != 1 { 324 t.Fatalf("expected length 1, got %d", fst.Len()) 325 } 326 327 // first check all the expected values 328 want := map[string]uint64{ 329 "": 1, 330 } 331 got := map[string]uint64{} 332 itr, err := fst.Iterator(nil, nil) 333 for err == nil { 334 key, val := itr.Current() 335 got[string(key)] = val 336 err = itr.Next() 337 } 338 if err != ErrIteratorDone { 339 t.Errorf("iterator error: %v", err) 340 } 341 if !reflect.DeepEqual(want, got) { 342 t.Errorf("expected %v, got: %v", want, got) 343 } 344} 345 346func TestRoundTripEmptyStringAndOthers(t *testing.T) { 347 f, err := ioutil.TempFile("", "vellum") 348 if err != nil { 349 t.Fatal(err) 350 } 351 defer func() { 352 err = f.Close() 353 if err != nil { 354 t.Fatal(err) 355 } 356 }() 357 defer func() { 358 err = os.Remove(f.Name()) 359 if err != nil { 360 t.Fatal(err) 361 } 362 }() 363 364 b, err := New(f, nil) 365 if err != nil { 366 t.Fatalf("error creating builder: %v", err) 367 } 368 369 err = b.Insert([]byte(""), 0) 370 if err != nil { 371 t.Fatalf("error inserting empty string") 372 } 373 err = b.Insert([]byte("a"), 0) 374 if err != nil { 375 t.Fatalf("error inserting empty string") 376 } 377 378 err = b.Close() 379 if err != nil { 380 t.Fatalf("error closing: %v", err) 381 } 382 383 fst, err := Open(f.Name()) 384 if err != nil { 385 t.Fatalf("error loading set: %v", err) 386 } 387 defer func() { 388 err = fst.Close() 389 if err != nil { 390 t.Fatal(err) 391 } 392 }() 393 394 if fst.Len() != 2 { 395 t.Fatalf("expected length 2, got %d", fst.Len()) 396 } 397 398 // first check all the expected values 399 want := map[string]uint64{ 400 "": 0, 401 "a": 0, 402 } 403 got := map[string]uint64{} 404 itr, err := fst.Iterator(nil, nil) 405 for err == nil { 406 key, val := itr.Current() 407 got[string(key)] = val 408 err = itr.Next() 409 } 410 if err != ErrIteratorDone { 411 t.Errorf("iterator error: %v", err) 412 } 413 if !reflect.DeepEqual(want, got) { 414 t.Errorf("expected %v, got: %v", want, got) 415 } 416} 417 418func TestMerge(t *testing.T) { 419 420 // first create a file with the smallSample data 421 f, err := ioutil.TempFile("", "vellum1") 422 if err != nil { 423 t.Fatal(err) 424 } 425 defer func() { 426 err = f.Close() 427 if err != nil { 428 t.Fatal(err) 429 } 430 }() 431 defer func() { 432 err = os.Remove(f.Name()) 433 if err != nil { 434 t.Fatal(err) 435 } 436 }() 437 438 b, err := New(f, nil) 439 if err != nil { 440 t.Fatalf("error creating builder: %v", err) 441 } 442 443 err = insertStringMap(b, smallSample) 444 if err != nil { 445 t.Fatalf("error building: %v", err) 446 } 447 448 err = b.Close() 449 if err != nil { 450 t.Fatalf("err closing: %v", err) 451 } 452 453 smallSample2 := map[string]uint64{ 454 "bold": 25, 455 "last": 1, 456 "next": 500, 457 "tank": 0, 458 } 459 460 // next create a file with the smallSample2 data 461 f2, err := ioutil.TempFile("", "vellum1") 462 if err != nil { 463 t.Fatal(err) 464 } 465 defer func() { 466 err = f2.Close() 467 if err != nil { 468 t.Fatal(err) 469 } 470 }() 471 defer func() { 472 err = os.Remove(f2.Name()) 473 if err != nil { 474 t.Fatal(err) 475 } 476 }() 477 478 b, err = New(f2, nil) 479 if err != nil { 480 t.Fatalf("error creating builder: %v", err) 481 } 482 483 err = insertStringMap(b, smallSample2) 484 if err != nil { 485 t.Fatalf("error building: %v", err) 486 } 487 488 err = b.Close() 489 if err != nil { 490 t.Fatalf("err closing: %v", err) 491 } 492 493 // now open them both up 494 fst, err := Open(f.Name()) 495 if err != nil { 496 t.Fatalf("error loading set: %v", err) 497 } 498 defer func() { 499 err = fst.Close() 500 if err != nil { 501 t.Fatal(err) 502 } 503 }() 504 fst2, err := Open(f2.Name()) 505 if err != nil { 506 t.Fatalf("error loading set: %v", err) 507 } 508 defer func() { 509 err = fst2.Close() 510 if err != nil { 511 t.Fatal(err) 512 } 513 }() 514 515 // create full range iterators on both 516 itr, err := fst.Iterator(nil, nil) 517 if err != nil { 518 t.Fatalf("error opening iterator: %v", err) 519 } 520 itr2, err := fst2.Iterator(nil, nil) 521 if err != nil { 522 t.Fatalf("error opening iterator: %v", err) 523 } 524 525 f3, err := ioutil.TempFile("", "vellum1") 526 if err != nil { 527 t.Fatal(err) 528 } 529 defer func() { 530 err = f3.Close() 531 if err != nil { 532 t.Fatal(err) 533 } 534 }() 535 defer func() { 536 err = os.Remove(f3.Name()) 537 if err != nil { 538 t.Fatal(err) 539 } 540 }() 541 542 err = Merge(f3, nil, []Iterator{itr, itr2}, MergeSum) 543 if err != nil { 544 t.Fatalf("error merging iterators: %v", err) 545 } 546 547 // now check it 548 fstc, err := Open(f3.Name()) 549 if err != nil { 550 t.Fatalf("error loading set: %v", err) 551 } 552 defer func() { 553 err = fstc.Close() 554 if err != nil { 555 t.Fatal(err) 556 } 557 }() 558 559 if fstc.Len() != 8 { 560 t.Fatalf("expected length 8, got %d", fst.Len()) 561 } 562 563 // now check all the expected values 564 want := map[string]uint64{ 565 "mon": 2, 566 "tues": 3, 567 "thurs": 5, 568 "tye": 99, 569 "bold": 25, 570 "last": 1, 571 "next": 500, 572 "tank": 0, 573 } 574 got := map[string]uint64{} 575 itrc, err := fstc.Iterator(nil, nil) 576 for err == nil { 577 key, val := itrc.Current() 578 got[string(key)] = val 579 err = itrc.Next() 580 } 581 if err != ErrIteratorDone { 582 t.Errorf("iterator error: %v", err) 583 } 584 if !reflect.DeepEqual(want, got) { 585 t.Errorf("expected %v, got: %v", want, got) 586 } 587} 588 589func BenchmarkKey4000K(b *testing.B) { 590 benchmarkBigKey(b, 4000000) 591} 592 593func BenchmarkKey1000K(b *testing.B) { 594 benchmarkBigKey(b, 1000000) 595} 596 597func BenchmarkKey100K(b *testing.B) { 598 benchmarkBigKey(b, 100000) 599} 600 601func BenchmarkKey10K(b *testing.B) { 602 benchmarkBigKey(b, 10000) 603} 604 605func BenchmarkKey1K(b *testing.B) { 606 benchmarkBigKey(b, 1000) 607} 608 609func benchmarkBigKey(b *testing.B, n int) { 610 big := bytes.Repeat([]byte("a"), n) 611 612 b.ResetTimer() 613 614 for i := 0; i < b.N; i++ { 615 b, err := New(ioutil.Discard, nil) 616 if err != nil { 617 break 618 } 619 620 err = b.Insert(big, 0) 621 if err != nil { 622 break 623 } 624 625 err = b.Close() 626 if err != nil { 627 break 628 } 629 } 630} 631