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 | |
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 | private: |
106 | std::string contents_; |
107 | }; |
108 | |
109 | class 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 | |
135 | typedef 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. |
139 | class 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 | |
176 | class 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 | |
210 | class 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 |
259 | class 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 | |
300 | class 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 | |
328 | class 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 | |
373 | enum TestType { TABLE_TEST, BLOCK_TEST, MEMTABLE_TEST, DB_TEST }; |
374 | |
375 | struct TestArgs { |
376 | TestType type; |
377 | bool reverse_compare; |
378 | int restart_interval; |
379 | }; |
380 | |
381 | static 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 | }; |
404 | static const int kNumTestArgs = sizeof(kTestArgList) / sizeof(kTestArgList[0]); |
405 | |
406 | class 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. |
612 | TEST_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. |
623 | TEST_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 |
642 | TEST_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 | |
651 | TEST_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 | |
660 | TEST_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 | |
671 | TEST_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 | |
680 | TEST_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 | |
700 | TEST_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 | |
724 | TEST(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 | |
748 | static 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 | |
758 | TEST(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 | |
787 | static bool SnappyCompressionSupported() { |
788 | std::string out; |
789 | Slice in = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" ; |
790 | return port::Snappy_Compress(in.data(), in.size(), &out); |
791 | } |
792 | |
793 | TEST(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 | |