src/leveldb/table/table_test.cc

   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 }