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