table_test.cc raw
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(); }
838