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
23namespace leveldb {
24
25// Return reverse of "key".
26// Used to test non-lexicographic comparators.
27static 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
37namespace {
38class 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
64static ReverseKeyComparator reverse_key_comparator;
65
66static 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
78namespace {
79struct 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
90class 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
110class 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
137typedef 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.
141class 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
181class 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
221class 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
276class 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
316class 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
349class 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
399enum TestType {
400  TABLE_TEST,
401  BLOCK_TEST,
402  MEMTABLE_TEST,
403  DB_TEST
404};
405
406struct TestArgs {
407  TestType type;
408  bool reverse_compare;
409  int restart_interval;
410};
411
412static 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};
435static const int kNumTestArgs = sizeof(kTestArgList) / sizeof(kTestArgList[0]);
436
437class 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.
648TEST(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.
659TEST(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
678TEST(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
687TEST(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
696TEST(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
707TEST(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
716TEST(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
736TEST(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
760class MemTableTest { };
761
762TEST(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
787static 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
798class TableTest { };
799
800TEST(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
830static bool SnappyCompressionSupported() {
831  std::string out;
832  Slice in = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
833  return port::Snappy_Compress(in.data(), in.size(), &out);
834}
835
836TEST(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
866int main(int argc, char** argv) {
867  return leveldb::test::RunAllTests();
868}
869