1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. See the AUTHORS file for names of contributors. 4 5 #include "leveldb/table.h" 6 7 #include <map> 8 #include <string> 9 #include "db/dbformat.h" 10 #include "db/memtable.h" 11 #include "db/write_batch_internal.h" 12 #include "leveldb/db.h" 13 #include "leveldb/env.h" 14 #include "leveldb/iterator.h" 15 #include "leveldb/table_builder.h" 16 #include "table/block.h" 17 #include "table/block_builder.h" 18 #include "table/format.h" 19 #include "util/random.h" 20 #include "util/testharness.h" 21 #include "util/testutil.h" 22 23 namespace leveldb { 24 25 // Return reverse of "key". 26 // Used to test non-lexicographic comparators. 27 static std::string Reverse(const Slice& key) { 28 std::string str(key.ToString()); 29 std::string rev(""); 30 for (std::string::reverse_iterator rit = str.rbegin(); 31 rit != str.rend(); ++rit) { 32 rev.push_back(*rit); 33 } 34 return rev; 35 } 36 37 namespace { 38 class ReverseKeyComparator : public Comparator { 39 public: 40 virtual const char* Name() const { 41 return "leveldb.ReverseBytewiseComparator"; 42 } 43 44 virtual int Compare(const Slice& a, const Slice& b) const { 45 return BytewiseComparator()->Compare(Reverse(a), Reverse(b)); 46 } 47 48 virtual void FindShortestSeparator( 49 std::string* start, 50 const Slice& limit) const { 51 std::string s = Reverse(*start); 52 std::string l = Reverse(limit); 53 BytewiseComparator()->FindShortestSeparator(&s, l); 54 *start = Reverse(s); 55 } 56 57 virtual void FindShortSuccessor(std::string* key) const { 58 std::string s = Reverse(*key); 59 BytewiseComparator()->FindShortSuccessor(&s); 60 *key = Reverse(s); 61 } 62 }; 63 } // namespace 64 static ReverseKeyComparator reverse_key_comparator; 65 66 static void Increment(const Comparator* cmp, std::string* key) { 67 if (cmp == BytewiseComparator()) { 68 key->push_back('\0'); 69 } else { 70 assert(cmp == &reverse_key_comparator); 71 std::string rev = Reverse(*key); 72 rev.push_back('\0'); 73 *key = Reverse(rev); 74 } 75 } 76 77 // An STL comparator that uses a Comparator 78 namespace { 79 struct STLLessThan { 80 const Comparator* cmp; 81 82 STLLessThan() : cmp(BytewiseComparator()) { } 83 STLLessThan(const Comparator* c) : cmp(c) { } 84 bool operator()(const std::string& a, const std::string& b) const { 85 return cmp->Compare(Slice(a), Slice(b)) < 0; 86 } 87 }; 88 } // namespace 89 90 class StringSink: public WritableFile { 91 public: 92 ~StringSink() { } 93 94 const std::string& contents() const { return contents_; } 95 96 virtual Status Close() { return Status::OK(); } 97 virtual Status Flush() { return Status::OK(); } 98 virtual Status Sync() { return Status::OK(); } 99 100 virtual Status Append(const Slice& data) { 101 contents_.append(data.data(), data.size()); 102 return Status::OK(); 103 } 104 105 private: 106 std::string contents_; 107 }; 108 109 110 class StringSource: public RandomAccessFile { 111 public: 112 StringSource(const Slice& contents) 113 : contents_(contents.data(), contents.size()) { 114 } 115 116 virtual ~StringSource() { } 117 118 uint64_t Size() const { return contents_.size(); } 119 120 virtual Status Read(uint64_t offset, size_t n, Slice* result, 121 char* scratch) const { 122 if (offset > contents_.size()) { 123 return Status::InvalidArgument("invalid Read offset"); 124 } 125 if (offset + n > contents_.size()) { 126 n = contents_.size() - offset; 127 } 128 memcpy(scratch, &contents_[offset], n); 129 *result = Slice(scratch, n); 130 return Status::OK(); 131 } 132 133 private: 134 std::string contents_; 135 }; 136 137 typedef std::map<std::string, std::string, STLLessThan> KVMap; 138 139 // Helper class for tests to unify the interface between 140 // BlockBuilder/TableBuilder and Block/Table. 141 class Constructor { 142 public: 143 explicit Constructor(const Comparator* cmp) : data_(STLLessThan(cmp)) { } 144 virtual ~Constructor() { } 145 146 void Add(const std::string& key, const Slice& value) { 147 data_[key] = value.ToString(); 148 } 149 150 // Finish constructing the data structure with all the keys that have 151 // been added so far. Returns the keys in sorted order in "*keys" 152 // and stores the key/value pairs in "*kvmap" 153 void Finish(const Options& options, 154 std::vector<std::string>* keys, 155 KVMap* kvmap) { 156 *kvmap = data_; 157 keys->clear(); 158 for (KVMap::const_iterator it = data_.begin(); 159 it != data_.end(); 160 ++it) { 161 keys->push_back(it->first); 162 } 163 data_.clear(); 164 Status s = FinishImpl(options, *kvmap); 165 ASSERT_TRUE(s.ok()) << s.ToString(); 166 } 167 168 // Construct the data structure from the data in "data" 169 virtual Status FinishImpl(const Options& options, const KVMap& data) = 0; 170 171 virtual Iterator* NewIterator() const = 0; 172 173 virtual const KVMap& data() { return data_; } 174 175 virtual DB* db() const { return NULL; } // Overridden in DBConstructor 176 177 private: 178 KVMap data_; 179 }; 180 181 class BlockConstructor: public Constructor { 182 public: 183 explicit BlockConstructor(const Comparator* cmp) 184 : Constructor(cmp), 185 comparator_(cmp), 186 block_(NULL) { } 187 ~BlockConstructor() { 188 delete block_; 189 } 190 virtual Status FinishImpl(const Options& options, const KVMap& data) { 191 delete block_; 192 block_ = NULL; 193 BlockBuilder builder(&options); 194 195 for (KVMap::const_iterator it = data.begin(); 196 it != data.end(); 197 ++it) { 198 builder.Add(it->first, it->second); 199 } 200 // Open the block 201 data_ = builder.Finish().ToString(); 202 BlockContents contents; 203 contents.data = data_; 204 contents.cachable = false; 205 contents.heap_allocated = false; 206 block_ = new Block(contents); 207 return Status::OK(); 208 } 209 virtual Iterator* NewIterator() const { 210 return block_->NewIterator(comparator_); 211 } 212 213 private: 214 const Comparator* comparator_; 215 std::string data_; 216 Block* block_; 217 218 BlockConstructor(); 219 }; 220 221 class TableConstructor: public Constructor { 222 public: 223 TableConstructor(const Comparator* cmp) 224 : Constructor(cmp), 225 source_(NULL), table_(NULL) { 226 } 227 ~TableConstructor() { 228 Reset(); 229 } 230 virtual Status FinishImpl(const Options& options, const KVMap& data) { 231 Reset(); 232 StringSink sink; 233 TableBuilder builder(options, &sink); 234 235 for (KVMap::const_iterator it = data.begin(); 236 it != data.end(); 237 ++it) { 238 builder.Add(it->first, it->second); 239 ASSERT_TRUE(builder.status().ok()); 240 } 241 Status s = builder.Finish(); 242 ASSERT_TRUE(s.ok()) << s.ToString(); 243 244 ASSERT_EQ(sink.contents().size(), builder.FileSize()); 245 246 // Open the table 247 source_ = new StringSource(sink.contents()); 248 Options table_options; 249 table_options.comparator = options.comparator; 250 return Table::Open(table_options, source_, sink.contents().size(), &table_); 251 } 252 253 virtual Iterator* NewIterator() const { 254 return table_->NewIterator(ReadOptions()); 255 } 256 257 uint64_t ApproximateOffsetOf(const Slice& key) const { 258 return table_->ApproximateOffsetOf(key); 259 } 260 261 private: 262 void Reset() { 263 delete table_; 264 delete source_; 265 table_ = NULL; 266 source_ = NULL; 267 } 268 269 StringSource* source_; 270 Table* table_; 271 272 TableConstructor(); 273 }; 274 275 // A helper class that converts internal format keys into user keys 276 class KeyConvertingIterator: public Iterator { 277 public: 278 explicit KeyConvertingIterator(Iterator* iter) : iter_(iter) { } 279 virtual ~KeyConvertingIterator() { delete iter_; } 280 virtual bool Valid() const { return iter_->Valid(); } 281 virtual void Seek(const Slice& target) { 282 ParsedInternalKey ikey(target, kMaxSequenceNumber, kTypeValue); 283 std::string encoded; 284 AppendInternalKey(&encoded, ikey); 285 iter_->Seek(encoded); 286 } 287 virtual void SeekToFirst() { iter_->SeekToFirst(); } 288 virtual void SeekToLast() { iter_->SeekToLast(); } 289 virtual void Next() { iter_->Next(); } 290 virtual void Prev() { iter_->Prev(); } 291 292 virtual Slice key() const { 293 assert(Valid()); 294 ParsedInternalKey key; 295 if (!ParseInternalKey(iter_->key(), &key)) { 296 status_ = Status::Corruption("malformed internal key"); 297 return Slice("corrupted key"); 298 } 299 return key.user_key; 300 } 301 302 virtual Slice value() const { return iter_->value(); } 303 virtual Status status() const { 304 return status_.ok() ? iter_->status() : status_; 305 } 306 307 private: 308 mutable Status status_; 309 Iterator* iter_; 310 311 // No copying allowed 312 KeyConvertingIterator(const KeyConvertingIterator&); 313 void operator=(const KeyConvertingIterator&); 314 }; 315 316 class MemTableConstructor: public Constructor { 317 public: 318 explicit MemTableConstructor(const Comparator* cmp) 319 : Constructor(cmp), 320 internal_comparator_(cmp) { 321 memtable_ = new MemTable(internal_comparator_); 322 memtable_->Ref(); 323 } 324 ~MemTableConstructor() { 325 memtable_->Unref(); 326 } 327 virtual Status FinishImpl(const Options& options, const KVMap& data) { 328 memtable_->Unref(); 329 memtable_ = new MemTable(internal_comparator_); 330 memtable_->Ref(); 331 int seq = 1; 332 for (KVMap::const_iterator it = data.begin(); 333 it != data.end(); 334 ++it) { 335 memtable_->Add(seq, kTypeValue, it->first, it->second); 336 seq++; 337 } 338 return Status::OK(); 339 } 340 virtual Iterator* NewIterator() const { 341 return new KeyConvertingIterator(memtable_->NewIterator()); 342 } 343 344 private: 345 InternalKeyComparator internal_comparator_; 346 MemTable* memtable_; 347 }; 348 349 class DBConstructor: public Constructor { 350 public: 351 explicit DBConstructor(const Comparator* cmp) 352 : Constructor(cmp), 353 comparator_(cmp) { 354 db_ = NULL; 355 NewDB(); 356 } 357 ~DBConstructor() { 358 delete db_; 359 } 360 virtual Status FinishImpl(const Options& options, const KVMap& data) { 361 delete db_; 362 db_ = NULL; 363 NewDB(); 364 for (KVMap::const_iterator it = data.begin(); 365 it != data.end(); 366 ++it) { 367 WriteBatch batch; 368 batch.Put(it->first, it->second); 369 ASSERT_TRUE(db_->Write(WriteOptions(), &batch).ok()); 370 } 371 return Status::OK(); 372 } 373 virtual Iterator* NewIterator() const { 374 return db_->NewIterator(ReadOptions()); 375 } 376 377 virtual DB* db() const { return db_; } 378 379 private: 380 void NewDB() { 381 std::string name = test::TmpDir() + "/table_testdb"; 382 383 Options options; 384 options.comparator = comparator_; 385 Status status = DestroyDB(name, options); 386 ASSERT_TRUE(status.ok()) << status.ToString(); 387 388 options.create_if_missing = true; 389 options.error_if_exists = true; 390 options.write_buffer_size = 10000; // Something small to force merging 391 status = DB::Open(options, name, &db_); 392 ASSERT_TRUE(status.ok()) << status.ToString(); 393 } 394 395 const Comparator* comparator_; 396 DB* db_; 397 }; 398 399 enum TestType { 400 TABLE_TEST, 401 BLOCK_TEST, 402 MEMTABLE_TEST, 403 DB_TEST 404 }; 405 406 struct TestArgs { 407 TestType type; 408 bool reverse_compare; 409 int restart_interval; 410 }; 411 412 static const TestArgs kTestArgList[] = { 413 { TABLE_TEST, false, 16 }, 414 { TABLE_TEST, false, 1 }, 415 { TABLE_TEST, false, 1024 }, 416 { TABLE_TEST, true, 16 }, 417 { TABLE_TEST, true, 1 }, 418 { TABLE_TEST, true, 1024 }, 419 420 { BLOCK_TEST, false, 16 }, 421 { BLOCK_TEST, false, 1 }, 422 { BLOCK_TEST, false, 1024 }, 423 { BLOCK_TEST, true, 16 }, 424 { BLOCK_TEST, true, 1 }, 425 { BLOCK_TEST, true, 1024 }, 426 427 // Restart interval does not matter for memtables 428 { MEMTABLE_TEST, false, 16 }, 429 { MEMTABLE_TEST, true, 16 }, 430 431 // Do not bother with restart interval variations for DB 432 { DB_TEST, false, 16 }, 433 { DB_TEST, true, 16 }, 434 }; 435 static const int kNumTestArgs = sizeof(kTestArgList) / sizeof(kTestArgList[0]); 436 437 class Harness { 438 public: 439 Harness() : constructor_(NULL) { } 440 441 void Init(const TestArgs& args) { 442 delete constructor_; 443 constructor_ = NULL; 444 options_ = Options(); 445 446 options_.block_restart_interval = args.restart_interval; 447 // Use shorter block size for tests to exercise block boundary 448 // conditions more. 449 options_.block_size = 256; 450 if (args.reverse_compare) { 451 options_.comparator = &reverse_key_comparator; 452 } 453 switch (args.type) { 454 case TABLE_TEST: 455 constructor_ = new TableConstructor(options_.comparator); 456 break; 457 case BLOCK_TEST: 458 constructor_ = new BlockConstructor(options_.comparator); 459 break; 460 case MEMTABLE_TEST: 461 constructor_ = new MemTableConstructor(options_.comparator); 462 break; 463 case DB_TEST: 464 constructor_ = new DBConstructor(options_.comparator); 465 break; 466 } 467 } 468 469 ~Harness() { 470 delete constructor_; 471 } 472 473 void Add(const std::string& key, const std::string& value) { 474 constructor_->Add(key, value); 475 } 476 477 void Test(Random* rnd) { 478 std::vector<std::string> keys; 479 KVMap data; 480 constructor_->Finish(options_, &keys, &data); 481 482 TestForwardScan(keys, data); 483 TestBackwardScan(keys, data); 484 TestRandomAccess(rnd, keys, data); 485 } 486 487 void TestForwardScan(const std::vector<std::string>& keys, 488 const KVMap& data) { 489 Iterator* iter = constructor_->NewIterator(); 490 ASSERT_TRUE(!iter->Valid()); 491 iter->SeekToFirst(); 492 for (KVMap::const_iterator model_iter = data.begin(); 493 model_iter != data.end(); 494 ++model_iter) { 495 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 496 iter->Next(); 497 } 498 ASSERT_TRUE(!iter->Valid()); 499 delete iter; 500 } 501 502 void TestBackwardScan(const std::vector<std::string>& keys, 503 const KVMap& data) { 504 Iterator* iter = constructor_->NewIterator(); 505 ASSERT_TRUE(!iter->Valid()); 506 iter->SeekToLast(); 507 for (KVMap::const_reverse_iterator model_iter = data.rbegin(); 508 model_iter != data.rend(); 509 ++model_iter) { 510 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 511 iter->Prev(); 512 } 513 ASSERT_TRUE(!iter->Valid()); 514 delete iter; 515 } 516 517 void TestRandomAccess(Random* rnd, 518 const std::vector<std::string>& keys, 519 const KVMap& data) { 520 static const bool kVerbose = false; 521 Iterator* iter = constructor_->NewIterator(); 522 ASSERT_TRUE(!iter->Valid()); 523 KVMap::const_iterator model_iter = data.begin(); 524 if (kVerbose) fprintf(stderr, "---\n"); 525 for (int i = 0; i < 200; i++) { 526 const int toss = rnd->Uniform(5); 527 switch (toss) { 528 case 0: { 529 if (iter->Valid()) { 530 if (kVerbose) fprintf(stderr, "Next\n"); 531 iter->Next(); 532 ++model_iter; 533 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 534 } 535 break; 536 } 537 538 case 1: { 539 if (kVerbose) fprintf(stderr, "SeekToFirst\n"); 540 iter->SeekToFirst(); 541 model_iter = data.begin(); 542 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 543 break; 544 } 545 546 case 2: { 547 std::string key = PickRandomKey(rnd, keys); 548 model_iter = data.lower_bound(key); 549 if (kVerbose) fprintf(stderr, "Seek '%s'\n", 550 EscapeString(key).c_str()); 551 iter->Seek(Slice(key)); 552 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 553 break; 554 } 555 556 case 3: { 557 if (iter->Valid()) { 558 if (kVerbose) fprintf(stderr, "Prev\n"); 559 iter->Prev(); 560 if (model_iter == data.begin()) { 561 model_iter = data.end(); // Wrap around to invalid value 562 } else { 563 --model_iter; 564 } 565 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 566 } 567 break; 568 } 569 570 case 4: { 571 if (kVerbose) fprintf(stderr, "SeekToLast\n"); 572 iter->SeekToLast(); 573 if (keys.empty()) { 574 model_iter = data.end(); 575 } else { 576 std::string last = data.rbegin()->first; 577 model_iter = data.lower_bound(last); 578 } 579 ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 580 break; 581 } 582 } 583 } 584 delete iter; 585 } 586 587 std::string ToString(const KVMap& data, const KVMap::const_iterator& it) { 588 if (it == data.end()) { 589 return "END"; 590 } else { 591 return "'" + it->first + "->" + it->second + "'"; 592 } 593 } 594 595 std::string ToString(const KVMap& data, 596 const KVMap::const_reverse_iterator& it) { 597 if (it == data.rend()) { 598 return "END"; 599 } else { 600 return "'" + it->first + "->" + it->second + "'"; 601 } 602 } 603 604 std::string ToString(const Iterator* it) { 605 if (!it->Valid()) { 606 return "END"; 607 } else { 608 return "'" + it->key().ToString() + "->" + it->value().ToString() + "'"; 609 } 610 } 611 612 std::string PickRandomKey(Random* rnd, const std::vector<std::string>& keys) { 613 if (keys.empty()) { 614 return "foo"; 615 } else { 616 const int index = rnd->Uniform(keys.size()); 617 std::string result = keys[index]; 618 switch (rnd->Uniform(3)) { 619 case 0: 620 // Return an existing key 621 break; 622 case 1: { 623 // Attempt to return something smaller than an existing key 624 if (result.size() > 0 && result[result.size()-1] > '\0') { 625 result[result.size()-1]--; 626 } 627 break; 628 } 629 case 2: { 630 // Return something larger than an existing key 631 Increment(options_.comparator, &result); 632 break; 633 } 634 } 635 return result; 636 } 637 } 638 639 // Returns NULL if not running against a DB 640 DB* db() const { return constructor_->db(); } 641 642 private: 643 Options options_; 644 Constructor* constructor_; 645 }; 646 647 // Test empty table/block. 648 TEST(Harness, Empty) { 649 for (int i = 0; i < kNumTestArgs; i++) { 650 Init(kTestArgList[i]); 651 Random rnd(test::RandomSeed() + 1); 652 Test(&rnd); 653 } 654 } 655 656 // Special test for a block with no restart entries. The C++ leveldb 657 // code never generates such blocks, but the Java version of leveldb 658 // seems to. 659 TEST(Harness, ZeroRestartPointsInBlock) { 660 char data[sizeof(uint32_t)]; 661 memset(data, 0, sizeof(data)); 662 BlockContents contents; 663 contents.data = Slice(data, sizeof(data)); 664 contents.cachable = false; 665 contents.heap_allocated = false; 666 Block block(contents); 667 Iterator* iter = block.NewIterator(BytewiseComparator()); 668 iter->SeekToFirst(); 669 ASSERT_TRUE(!iter->Valid()); 670 iter->SeekToLast(); 671 ASSERT_TRUE(!iter->Valid()); 672 iter->Seek("foo"); 673 ASSERT_TRUE(!iter->Valid()); 674 delete iter; 675 } 676 677 // Test the empty key 678 TEST(Harness, SimpleEmptyKey) { 679 for (int i = 0; i < kNumTestArgs; i++) { 680 Init(kTestArgList[i]); 681 Random rnd(test::RandomSeed() + 1); 682 Add("", "v"); 683 Test(&rnd); 684 } 685 } 686 687 TEST(Harness, SimpleSingle) { 688 for (int i = 0; i < kNumTestArgs; i++) { 689 Init(kTestArgList[i]); 690 Random rnd(test::RandomSeed() + 2); 691 Add("abc", "v"); 692 Test(&rnd); 693 } 694 } 695 696 TEST(Harness, SimpleMulti) { 697 for (int i = 0; i < kNumTestArgs; i++) { 698 Init(kTestArgList[i]); 699 Random rnd(test::RandomSeed() + 3); 700 Add("abc", "v"); 701 Add("abcd", "v"); 702 Add("ac", "v2"); 703 Test(&rnd); 704 } 705 } 706 707 TEST(Harness, SimpleSpecialKey) { 708 for (int i = 0; i < kNumTestArgs; i++) { 709 Init(kTestArgList[i]); 710 Random rnd(test::RandomSeed() + 4); 711 Add("\xff\xff", "v3"); 712 Test(&rnd); 713 } 714 } 715 716 TEST(Harness, Randomized) { 717 for (int i = 0; i < kNumTestArgs; i++) { 718 Init(kTestArgList[i]); 719 Random rnd(test::RandomSeed() + 5); 720 for (int num_entries = 0; num_entries < 2000; 721 num_entries += (num_entries < 50 ? 1 : 200)) { 722 if ((num_entries % 10) == 0) { 723 fprintf(stderr, "case %d of %d: num_entries = %d\n", 724 (i + 1), int(kNumTestArgs), num_entries); 725 } 726 for (int e = 0; e < num_entries; e++) { 727 std::string v; 728 Add(test::RandomKey(&rnd, rnd.Skewed(4)), 729 test::RandomString(&rnd, rnd.Skewed(5), &v).ToString()); 730 } 731 Test(&rnd); 732 } 733 } 734 } 735 736 TEST(Harness, RandomizedLongDB) { 737 Random rnd(test::RandomSeed()); 738 TestArgs args = { DB_TEST, false, 16 }; 739 Init(args); 740 int num_entries = 100000; 741 for (int e = 0; e < num_entries; e++) { 742 std::string v; 743 Add(test::RandomKey(&rnd, rnd.Skewed(4)), 744 test::RandomString(&rnd, rnd.Skewed(5), &v).ToString()); 745 } 746 Test(&rnd); 747 748 // We must have created enough data to force merging 749 int files = 0; 750 for (int level = 0; level < config::kNumLevels; level++) { 751 std::string value; 752 char name[100]; 753 snprintf(name, sizeof(name), "leveldb.num-files-at-level%d", level); 754 ASSERT_TRUE(db()->GetProperty(name, &value)); 755 files += atoi(value.c_str()); 756 } 757 ASSERT_GT(files, 0); 758 } 759 760 class MemTableTest { }; 761 762 TEST(MemTableTest, Simple) { 763 InternalKeyComparator cmp(BytewiseComparator()); 764 MemTable* memtable = new MemTable(cmp); 765 memtable->Ref(); 766 WriteBatch batch; 767 WriteBatchInternal::SetSequence(&batch, 100); 768 batch.Put(std::string("k1"), std::string("v1")); 769 batch.Put(std::string("k2"), std::string("v2")); 770 batch.Put(std::string("k3"), std::string("v3")); 771 batch.Put(std::string("largekey"), std::string("vlarge")); 772 ASSERT_TRUE(WriteBatchInternal::InsertInto(&batch, memtable).ok()); 773 774 Iterator* iter = memtable->NewIterator(); 775 iter->SeekToFirst(); 776 while (iter->Valid()) { 777 fprintf(stderr, "key: '%s' -> '%s'\n", 778 iter->key().ToString().c_str(), 779 iter->value().ToString().c_str()); 780 iter->Next(); 781 } 782 783 delete iter; 784 memtable->Unref(); 785 } 786 787 static bool Between(uint64_t val, uint64_t low, uint64_t high) { 788 bool result = (val >= low) && (val <= high); 789 if (!result) { 790 fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n", 791 (unsigned long long)(val), 792 (unsigned long long)(low), 793 (unsigned long long)(high)); 794 } 795 return result; 796 } 797 798 class TableTest { }; 799 800 TEST(TableTest, ApproximateOffsetOfPlain) { 801 TableConstructor c(BytewiseComparator()); 802 c.Add("k01", "hello"); 803 c.Add("k02", "hello2"); 804 c.Add("k03", std::string(10000, 'x')); 805 c.Add("k04", std::string(200000, 'x')); 806 c.Add("k05", std::string(300000, 'x')); 807 c.Add("k06", "hello3"); 808 c.Add("k07", std::string(100000, 'x')); 809 std::vector<std::string> keys; 810 KVMap kvmap; 811 Options options; 812 options.block_size = 1024; 813 options.compression = kNoCompression; 814 c.Finish(options, &keys, &kvmap); 815 816 ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); 817 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); 818 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01a"), 0, 0)); 819 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); 820 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 0, 0)); 821 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 10000, 11000)); 822 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04a"), 210000, 211000)); 823 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k05"), 210000, 211000)); 824 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k06"), 510000, 511000)); 825 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k07"), 510000, 511000)); 826 ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 610000, 612000)); 827 828 } 829 830 static bool SnappyCompressionSupported() { 831 std::string out; 832 Slice in = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 833 return port::Snappy_Compress(in.data(), in.size(), &out); 834 } 835 836 TEST(TableTest, ApproximateOffsetOfCompressed) { 837 if (!SnappyCompressionSupported()) { 838 fprintf(stderr, "skipping compression tests\n"); 839 return; 840 } 841 842 Random rnd(301); 843 TableConstructor c(BytewiseComparator()); 844 std::string tmp; 845 c.Add("k01", "hello"); 846 c.Add("k02", test::CompressibleString(&rnd, 0.25, 10000, &tmp)); 847 c.Add("k03", "hello3"); 848 c.Add("k04", test::CompressibleString(&rnd, 0.25, 10000, &tmp)); 849 std::vector<std::string> keys; 850 KVMap kvmap; 851 Options options; 852 options.block_size = 1024; 853 options.compression = kSnappyCompression; 854 c.Finish(options, &keys, &kvmap); 855 856 ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); 857 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); 858 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); 859 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 2000, 3000)); 860 ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 2000, 3000)); 861 ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 4000, 6000)); 862 } 863 864 } // namespace leveldb 865 866 int main(int argc, char** argv) { 867 return leveldb::test::RunAllTests(); 868 } 869
