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