]> git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/db/db_iter_test.cc
projects / ceph.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
import quincy beta 17.1.0
[ceph.git] / ceph / src / rocksdb / db / db_iter_test.cc
1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5
6 #include <string>
7 #include <vector>
8 #include <algorithm>
9 #include <utility>
10
11 #include "db/db_iter.h"
12 #include "db/dbformat.h"
13 #include "rocksdb/comparator.h"
14 #include "rocksdb/options.h"
15 #include "rocksdb/perf_context.h"
16 #include "rocksdb/slice.h"
17 #include "rocksdb/statistics.h"
18 #include "table/iterator_wrapper.h"
19 #include "table/merging_iterator.h"
20 #include "test_util/sync_point.h"
21 #include "test_util/testharness.h"
22 #include "util/string_util.h"
23 #include "utilities/merge_operators.h"
24
25 namespace ROCKSDB_NAMESPACE {
26
27 static uint64_t TestGetTickerCount(const Options& options,
28 Tickers ticker_type) {
29 return options.statistics->getTickerCount(ticker_type);
30 }
31
32 class TestIterator : public InternalIterator {
33 public:
34 explicit TestIterator(const Comparator* comparator)
35 : initialized_(false),
36 valid_(false),
37 sequence_number_(0),
38 iter_(0),
39 cmp(comparator) {
40 data_.reserve(16);
41 }
42
43 void AddPut(std::string argkey, std::string argvalue) {
44 Add(argkey, kTypeValue, argvalue);
45 }
46
47 void AddDeletion(std::string argkey) {
48 Add(argkey, kTypeDeletion, std::string());
49 }
50
51 void AddSingleDeletion(std::string argkey) {
52 Add(argkey, kTypeSingleDeletion, std::string());
53 }
54
55 void AddMerge(std::string argkey, std::string argvalue) {
56 Add(argkey, kTypeMerge, argvalue);
57 }
58
59 void Add(std::string argkey, ValueType type, std::string argvalue) {
60 Add(argkey, type, argvalue, sequence_number_++);
61 }
62
63 void Add(std::string argkey, ValueType type, std::string argvalue,
64 size_t seq_num, bool update_iter = false) {
65 valid_ = true;
66 ParsedInternalKey internal_key(argkey, seq_num, type);
67 data_.push_back(
68 std::pair<std::string, std::string>(std::string(), argvalue));
69 AppendInternalKey(&data_.back().first, internal_key);
70 if (update_iter && valid_ && cmp.Compare(data_.back().first, key()) < 0) {
71 // insert a key smaller than current key
72 Finish();
73 // data_[iter_] is not anymore the current element of the iterator.
74 // Increment it to reposition it to the right position.
75 iter_++;
76 }
77 }
78
79 // should be called before operations with iterator
80 void Finish() {
81 initialized_ = true;
82 std::sort(data_.begin(), data_.end(),
83 [this](std::pair<std::string, std::string> a,
84 std::pair<std::string, std::string> b) {
85 return (cmp.Compare(a.first, b.first) < 0);
86 });
87 }
88
89 // Removes the key from the set of keys over which this iterator iterates.
90 // Not to be confused with AddDeletion().
91 // If the iterator is currently positioned on this key, the deletion will
92 // apply next time the iterator moves.
93 // Used for simulating ForwardIterator updating to a new version that doesn't
94 // have some of the keys (e.g. after compaction with a filter).
95 void Vanish(std::string _key) {
96 if (valid_ && data_[iter_].first == _key) {
97 delete_current_ = true;
98 return;
99 }
100 for (auto it = data_.begin(); it != data_.end(); ++it) {
101 ParsedInternalKey ikey;
102 Status pik_status =
103 ParseInternalKey(it->first, &ikey, true /* log_err_key */);
104 pik_status.PermitUncheckedError();
105 assert(pik_status.ok());
106 if (!pik_status.ok() || ikey.user_key != _key) {
107 continue;
108 }
109 if (valid_ && data_.begin() + iter_ > it) {
110 --iter_;
111 }
112 data_.erase(it);
113 return;
114 }
115 assert(false);
116 }
117
118 // Number of operations done on this iterator since construction.
119 size_t steps() const { return steps_; }
120
121 bool Valid() const override {
122 assert(initialized_);
123 return valid_;
124 }
125
126 void SeekToFirst() override {
127 assert(initialized_);
128 ++steps_;
129 DeleteCurrentIfNeeded();
130 valid_ = (data_.size() > 0);
131 iter_ = 0;
132 }
133
134 void SeekToLast() override {
135 assert(initialized_);
136 ++steps_;
137 DeleteCurrentIfNeeded();
138 valid_ = (data_.size() > 0);
139 iter_ = data_.size() - 1;
140 }
141
142 void Seek(const Slice& target) override {
143 assert(initialized_);
144 SeekToFirst();
145 ++steps_;
146 if (!valid_) {
147 return;
148 }
149 while (iter_ < data_.size() &&
150 (cmp.Compare(data_[iter_].first, target) < 0)) {
151 ++iter_;
152 }
153
154 if (iter_ == data_.size()) {
155 valid_ = false;
156 }
157 }
158
159 void SeekForPrev(const Slice& target) override {
160 assert(initialized_);
161 DeleteCurrentIfNeeded();
162 SeekForPrevImpl(target, &cmp);
163 }
164
165 void Next() override {
166 assert(initialized_);
167 assert(valid_);
168 assert(iter_ < data_.size());
169
170 ++steps_;
171 if (delete_current_) {
172 DeleteCurrentIfNeeded();
173 } else {
174 ++iter_;
175 }
176 valid_ = iter_ < data_.size();
177 }
178
179 void Prev() override {
180 assert(initialized_);
181 assert(valid_);
182 assert(iter_ < data_.size());
183
184 ++steps_;
185 DeleteCurrentIfNeeded();
186 if (iter_ == 0) {
187 valid_ = false;
188 } else {
189 --iter_;
190 }
191 }
192
193 Slice key() const override {
194 assert(initialized_);
195 return data_[iter_].first;
196 }
197
198 Slice value() const override {
199 assert(initialized_);
200 return data_[iter_].second;
201 }
202
203 Status status() const override {
204 assert(initialized_);
205 return Status::OK();
206 }
207
208 bool IsKeyPinned() const override { return true; }
209 bool IsValuePinned() const override { return true; }
210
211 private:
212 bool initialized_;
213 bool valid_;
214 size_t sequence_number_;
215 size_t iter_;
216 size_t steps_ = 0;
217
218 InternalKeyComparator cmp;
219 std::vector<std::pair<std::string, std::string>> data_;
220 bool delete_current_ = false;
221
222 void DeleteCurrentIfNeeded() {
223 if (!delete_current_) {
224 return;
225 }
226 data_.erase(data_.begin() + iter_);
227 delete_current_ = false;
228 }
229 };
230
231 class DBIteratorTest : public testing::Test {
232 public:
233 Env* env_;
234
235 DBIteratorTest() : env_(Env::Default()) {}
236 };
237
238 TEST_F(DBIteratorTest, DBIteratorPrevNext) {
239 Options options;
240 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
241 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
242 {
243 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
244 internal_iter->AddDeletion("a");
245 internal_iter->AddDeletion("a");
246 internal_iter->AddDeletion("a");
247 internal_iter->AddDeletion("a");
248 internal_iter->AddPut("a", "val_a");
249
250 internal_iter->AddPut("b", "val_b");
251 internal_iter->Finish();
252
253 ReadOptions ro;
254 std::unique_ptr<Iterator> db_iter(NewDBIterator(
255 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
256 internal_iter, 10, options.max_sequential_skip_in_iterations,
257 nullptr /*read_callback*/));
258
259 db_iter->SeekToLast();
260 ASSERT_TRUE(db_iter->Valid());
261 ASSERT_EQ(db_iter->key().ToString(), "b");
262 ASSERT_EQ(db_iter->value().ToString(), "val_b");
263
264 db_iter->Prev();
265 ASSERT_TRUE(db_iter->Valid());
266 ASSERT_EQ(db_iter->key().ToString(), "a");
267 ASSERT_EQ(db_iter->value().ToString(), "val_a");
268
269 db_iter->Next();
270 ASSERT_TRUE(db_iter->Valid());
271 ASSERT_EQ(db_iter->key().ToString(), "b");
272 ASSERT_EQ(db_iter->value().ToString(), "val_b");
273
274 db_iter->Next();
275 ASSERT_TRUE(!db_iter->Valid());
276 }
277 // Test to check the SeekToLast() with iterate_upper_bound not set
278 {
279 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
280 internal_iter->AddPut("a", "val_a");
281 internal_iter->AddPut("b", "val_b");
282 internal_iter->AddPut("b", "val_b");
283 internal_iter->AddPut("c", "val_c");
284 internal_iter->Finish();
285
286 ReadOptions ro;
287 std::unique_ptr<Iterator> db_iter(NewDBIterator(
288 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
289 internal_iter, 10, options.max_sequential_skip_in_iterations,
290 nullptr /*read_callback*/));
291
292 db_iter->SeekToLast();
293 ASSERT_TRUE(db_iter->Valid());
294 ASSERT_EQ(db_iter->key().ToString(), "c");
295 }
296
297 // Test to check the SeekToLast() with iterate_upper_bound set
298 {
299 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
300
301 internal_iter->AddPut("a", "val_a");
302 internal_iter->AddPut("b", "val_b");
303 internal_iter->AddPut("c", "val_c");
304 internal_iter->AddPut("d", "val_d");
305 internal_iter->AddPut("e", "val_e");
306 internal_iter->AddPut("f", "val_f");
307 internal_iter->Finish();
308
309 Slice prefix("d");
310
311 ReadOptions ro;
312 ro.iterate_upper_bound = &prefix;
313
314 std::unique_ptr<Iterator> db_iter(NewDBIterator(
315 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
316 internal_iter, 10, options.max_sequential_skip_in_iterations,
317 nullptr /*read_callback*/));
318
319 db_iter->SeekToLast();
320 ASSERT_TRUE(db_iter->Valid());
321 ASSERT_EQ(db_iter->key().ToString(), "c");
322
323 db_iter->Next();
324 ASSERT_TRUE(!db_iter->Valid());
325
326 db_iter->SeekToLast();
327 ASSERT_TRUE(db_iter->Valid());
328 ASSERT_EQ(db_iter->key().ToString(), "c");
329 }
330 // Test to check the SeekToLast() iterate_upper_bound set to a key that
331 // is not Put yet
332 {
333 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
334
335 internal_iter->AddPut("a", "val_a");
336 internal_iter->AddPut("a", "val_a");
337 internal_iter->AddPut("b", "val_b");
338 internal_iter->AddPut("c", "val_c");
339 internal_iter->AddPut("d", "val_d");
340 internal_iter->Finish();
341
342 Slice prefix("z");
343
344 ReadOptions ro;
345 ro.iterate_upper_bound = &prefix;
346
347 std::unique_ptr<Iterator> db_iter(NewDBIterator(
348 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
349 internal_iter, 10, options.max_sequential_skip_in_iterations,
350 nullptr /*read_callback*/));
351
352 db_iter->SeekToLast();
353 ASSERT_TRUE(db_iter->Valid());
354 ASSERT_EQ(db_iter->key().ToString(), "d");
355
356 db_iter->Next();
357 ASSERT_TRUE(!db_iter->Valid());
358
359 db_iter->SeekToLast();
360 ASSERT_TRUE(db_iter->Valid());
361 ASSERT_EQ(db_iter->key().ToString(), "d");
362
363 db_iter->Prev();
364 ASSERT_TRUE(db_iter->Valid());
365 ASSERT_EQ(db_iter->key().ToString(), "c");
366 }
367 // Test to check the SeekToLast() with iterate_upper_bound set to the
368 // first key
369 {
370 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
371 internal_iter->AddPut("a", "val_a");
372 internal_iter->AddPut("a", "val_a");
373 internal_iter->AddPut("a", "val_a");
374 internal_iter->AddPut("b", "val_b");
375 internal_iter->AddPut("b", "val_b");
376 internal_iter->Finish();
377
378 Slice prefix("a");
379
380 ReadOptions ro;
381 ro.iterate_upper_bound = &prefix;
382
383 std::unique_ptr<Iterator> db_iter(NewDBIterator(
384 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
385 internal_iter, 10, options.max_sequential_skip_in_iterations,
386 nullptr /*read_callback*/));
387
388 db_iter->SeekToLast();
389 ASSERT_TRUE(!db_iter->Valid());
390 }
391 // Test case to check SeekToLast with iterate_upper_bound set
392 // (same key put may times - SeekToLast should start with the
393 // maximum sequence id of the upper bound)
394
395 {
396 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
397 internal_iter->AddPut("a", "val_a");
398 internal_iter->AddPut("b", "val_b");
399 internal_iter->AddPut("c", "val_c");
400 internal_iter->AddPut("c", "val_c");
401 internal_iter->AddPut("c", "val_c");
402 internal_iter->AddPut("c", "val_c");
403 internal_iter->AddPut("c", "val_c");
404 internal_iter->AddPut("c", "val_c");
405 internal_iter->AddPut("c", "val_c");
406 internal_iter->Finish();
407
408 Slice prefix("c");
409
410 ReadOptions ro;
411 ro.iterate_upper_bound = &prefix;
412
413 std::unique_ptr<Iterator> db_iter(NewDBIterator(
414 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
415 internal_iter, 7, options.max_sequential_skip_in_iterations,
416 nullptr /*read_callback*/));
417
418 SetPerfLevel(kEnableCount);
419 ASSERT_TRUE(GetPerfLevel() == kEnableCount);
420
421 get_perf_context()->Reset();
422 db_iter->SeekToLast();
423
424 ASSERT_TRUE(db_iter->Valid());
425 ASSERT_EQ(static_cast<int>(get_perf_context()->internal_key_skipped_count), 1);
426 ASSERT_EQ(db_iter->key().ToString(), "b");
427
428 SetPerfLevel(kDisable);
429 }
430 // Test to check the SeekToLast() with the iterate_upper_bound set
431 // (Checking the value of the key which has sequence ids greater than
432 // and less that the iterator's sequence id)
433 {
434 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
435
436 internal_iter->AddPut("a", "val_a1");
437 internal_iter->AddPut("a", "val_a2");
438 internal_iter->AddPut("b", "val_b1");
439 internal_iter->AddPut("c", "val_c1");
440 internal_iter->AddPut("c", "val_c2");
441 internal_iter->AddPut("c", "val_c3");
442 internal_iter->AddPut("b", "val_b2");
443 internal_iter->AddPut("d", "val_d1");
444 internal_iter->Finish();
445
446 Slice prefix("c");
447
448 ReadOptions ro;
449 ro.iterate_upper_bound = &prefix;
450
451 std::unique_ptr<Iterator> db_iter(NewDBIterator(
452 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
453 internal_iter, 4, options.max_sequential_skip_in_iterations,
454 nullptr /*read_callback*/));
455
456 db_iter->SeekToLast();
457 ASSERT_TRUE(db_iter->Valid());
458 ASSERT_EQ(db_iter->key().ToString(), "b");
459 ASSERT_EQ(db_iter->value().ToString(), "val_b1");
460 }
461
462 // Test to check the SeekToLast() with the iterate_upper_bound set to the
463 // key that is deleted
464 {
465 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
466 internal_iter->AddPut("a", "val_a");
467 internal_iter->AddDeletion("a");
468 internal_iter->AddPut("b", "val_b");
469 internal_iter->AddPut("c", "val_c");
470 internal_iter->Finish();
471
472 Slice prefix("a");
473
474 ReadOptions ro;
475 ro.iterate_upper_bound = &prefix;
476
477 std::unique_ptr<Iterator> db_iter(NewDBIterator(
478 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
479 internal_iter, 10, options.max_sequential_skip_in_iterations,
480 nullptr /*read_callback*/));
481
482 db_iter->SeekToLast();
483 ASSERT_TRUE(!db_iter->Valid());
484 }
485 // Test to check the SeekToLast() with the iterate_upper_bound set
486 // (Deletion cases)
487 {
488 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
489 internal_iter->AddPut("a", "val_a");
490 internal_iter->AddPut("b", "val_b");
491 internal_iter->AddDeletion("b");
492 internal_iter->AddPut("c", "val_c");
493 internal_iter->Finish();
494
495 Slice prefix("c");
496
497 ReadOptions ro;
498 ro.iterate_upper_bound = &prefix;
499
500 std::unique_ptr<Iterator> db_iter(NewDBIterator(
501 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
502 internal_iter, 10, options.max_sequential_skip_in_iterations,
503 nullptr /*read_callback*/));
504
505 db_iter->SeekToLast();
506 ASSERT_TRUE(db_iter->Valid());
507 ASSERT_EQ(db_iter->key().ToString(), "a");
508
509 db_iter->Next();
510 ASSERT_TRUE(!db_iter->Valid());
511
512 db_iter->SeekToLast();
513 ASSERT_TRUE(db_iter->Valid());
514 ASSERT_EQ(db_iter->key().ToString(), "a");
515 }
516 // Test to check the SeekToLast() with iterate_upper_bound set
517 // (Deletion cases - Lot of internal keys after the upper_bound
518 // is deleted)
519 {
520 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
521 internal_iter->AddPut("a", "val_a");
522 internal_iter->AddPut("b", "val_b");
523 internal_iter->AddDeletion("c");
524 internal_iter->AddDeletion("d");
525 internal_iter->AddDeletion("e");
526 internal_iter->AddDeletion("f");
527 internal_iter->AddDeletion("g");
528 internal_iter->AddDeletion("h");
529 internal_iter->Finish();
530
531 Slice prefix("c");
532
533 ReadOptions ro;
534 ro.iterate_upper_bound = &prefix;
535
536 std::unique_ptr<Iterator> db_iter(NewDBIterator(
537 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
538 internal_iter, 7, options.max_sequential_skip_in_iterations,
539 nullptr /*read_callback*/));
540
541 SetPerfLevel(kEnableCount);
542 ASSERT_TRUE(GetPerfLevel() == kEnableCount);
543
544 get_perf_context()->Reset();
545 db_iter->SeekToLast();
546
547 ASSERT_TRUE(db_iter->Valid());
548 ASSERT_EQ(static_cast<int>(get_perf_context()->internal_delete_skipped_count), 0);
549 ASSERT_EQ(db_iter->key().ToString(), "b");
550
551 SetPerfLevel(kDisable);
552 }
553
554 {
555 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
556 internal_iter->AddDeletion("a");
557 internal_iter->AddDeletion("a");
558 internal_iter->AddDeletion("a");
559 internal_iter->AddDeletion("a");
560 internal_iter->AddPut("a", "val_a");
561
562 internal_iter->AddPut("b", "val_b");
563 internal_iter->Finish();
564
565 ReadOptions ro;
566 std::unique_ptr<Iterator> db_iter(NewDBIterator(
567 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
568 internal_iter, 10, options.max_sequential_skip_in_iterations,
569 nullptr /*read_callback*/));
570
571 db_iter->SeekToFirst();
572 ASSERT_TRUE(db_iter->Valid());
573 ASSERT_EQ(db_iter->key().ToString(), "a");
574 ASSERT_EQ(db_iter->value().ToString(), "val_a");
575
576 db_iter->Next();
577 ASSERT_TRUE(db_iter->Valid());
578 ASSERT_EQ(db_iter->key().ToString(), "b");
579 ASSERT_EQ(db_iter->value().ToString(), "val_b");
580
581 db_iter->Prev();
582 ASSERT_TRUE(db_iter->Valid());
583 ASSERT_EQ(db_iter->key().ToString(), "a");
584 ASSERT_EQ(db_iter->value().ToString(), "val_a");
585
586 db_iter->Prev();
587 ASSERT_TRUE(!db_iter->Valid());
588 }
589
590 {
591 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
592 internal_iter->AddPut("a", "val_a");
593 internal_iter->AddPut("b", "val_b");
594
595 internal_iter->AddPut("a", "val_a");
596 internal_iter->AddPut("b", "val_b");
597
598 internal_iter->AddPut("a", "val_a");
599 internal_iter->AddPut("b", "val_b");
600
601 internal_iter->AddPut("a", "val_a");
602 internal_iter->AddPut("b", "val_b");
603
604 internal_iter->AddPut("a", "val_a");
605 internal_iter->AddPut("b", "val_b");
606 internal_iter->Finish();
607
608 ReadOptions ro;
609 std::unique_ptr<Iterator> db_iter(NewDBIterator(
610 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
611 internal_iter, 2, options.max_sequential_skip_in_iterations,
612 nullptr /*read_callback*/));
613 db_iter->SeekToLast();
614 ASSERT_TRUE(db_iter->Valid());
615 ASSERT_EQ(db_iter->key().ToString(), "b");
616 ASSERT_EQ(db_iter->value().ToString(), "val_b");
617
618 db_iter->Next();
619 ASSERT_TRUE(!db_iter->Valid());
620
621 db_iter->SeekToLast();
622 ASSERT_TRUE(db_iter->Valid());
623 ASSERT_EQ(db_iter->key().ToString(), "b");
624 ASSERT_EQ(db_iter->value().ToString(), "val_b");
625 }
626
627 {
628 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
629 internal_iter->AddPut("a", "val_a");
630 internal_iter->AddPut("a", "val_a");
631 internal_iter->AddPut("a", "val_a");
632 internal_iter->AddPut("a", "val_a");
633 internal_iter->AddPut("a", "val_a");
634
635 internal_iter->AddPut("b", "val_b");
636
637 internal_iter->AddPut("c", "val_c");
638 internal_iter->Finish();
639
640 ReadOptions ro;
641 std::unique_ptr<Iterator> db_iter(NewDBIterator(
642 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
643 internal_iter, 10, options.max_sequential_skip_in_iterations,
644 nullptr /*read_callback*/));
645 db_iter->SeekToLast();
646 ASSERT_TRUE(db_iter->Valid());
647 ASSERT_EQ(db_iter->key().ToString(), "c");
648 ASSERT_EQ(db_iter->value().ToString(), "val_c");
649
650 db_iter->Prev();
651 ASSERT_TRUE(db_iter->Valid());
652 ASSERT_EQ(db_iter->key().ToString(), "b");
653 ASSERT_EQ(db_iter->value().ToString(), "val_b");
654
655 db_iter->Next();
656 ASSERT_TRUE(db_iter->Valid());
657 ASSERT_EQ(db_iter->key().ToString(), "c");
658 ASSERT_EQ(db_iter->value().ToString(), "val_c");
659 }
660 }
661
662 TEST_F(DBIteratorTest, DBIteratorEmpty) {
663 Options options;
664 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
665 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
666 ReadOptions ro;
667
668 {
669 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
670 internal_iter->Finish();
671
672 std::unique_ptr<Iterator> db_iter(NewDBIterator(
673 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
674 internal_iter, 0, options.max_sequential_skip_in_iterations,
675 nullptr /*read_callback*/));
676 db_iter->SeekToLast();
677 ASSERT_TRUE(!db_iter->Valid());
678 }
679
680 {
681 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
682 internal_iter->Finish();
683
684 std::unique_ptr<Iterator> db_iter(NewDBIterator(
685 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
686 internal_iter, 0, options.max_sequential_skip_in_iterations,
687 nullptr /*read_callback*/));
688 db_iter->SeekToFirst();
689 ASSERT_TRUE(!db_iter->Valid());
690 }
691 }
692
693 TEST_F(DBIteratorTest, DBIteratorUseSkipCountSkips) {
694 ReadOptions ro;
695 Options options;
696 options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
697 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
698
699 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
700 for (size_t i = 0; i < 200; ++i) {
701 internal_iter->AddPut("a", "a");
702 internal_iter->AddPut("b", "b");
703 internal_iter->AddPut("c", "c");
704 }
705 internal_iter->Finish();
706
707 std::unique_ptr<Iterator> db_iter(NewDBIterator(
708 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
709 BytewiseComparator(), internal_iter, 2,
710 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
711 db_iter->SeekToLast();
712 ASSERT_TRUE(db_iter->Valid());
713 ASSERT_EQ(db_iter->key().ToString(), "c");
714 ASSERT_EQ(db_iter->value().ToString(), "c");
715 ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 1u);
716
717 db_iter->Prev();
718 ASSERT_TRUE(db_iter->Valid());
719 ASSERT_EQ(db_iter->key().ToString(), "b");
720 ASSERT_EQ(db_iter->value().ToString(), "b");
721 ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 2u);
722
723 db_iter->Prev();
724 ASSERT_TRUE(db_iter->Valid());
725 ASSERT_EQ(db_iter->key().ToString(), "a");
726 ASSERT_EQ(db_iter->value().ToString(), "a");
727 ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 3u);
728
729 db_iter->Prev();
730 ASSERT_TRUE(!db_iter->Valid());
731 ASSERT_EQ(TestGetTickerCount(options, NUMBER_OF_RESEEKS_IN_ITERATION), 3u);
732 }
733
734 TEST_F(DBIteratorTest, DBIteratorUseSkip) {
735 ReadOptions ro;
736 Options options;
737 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
738 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
739 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
740
741 {
742 for (size_t i = 0; i < 200; ++i) {
743 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
744 internal_iter->AddMerge("b", "merge_1");
745 internal_iter->AddMerge("a", "merge_2");
746 for (size_t k = 0; k < 200; ++k) {
747 internal_iter->AddPut("c", ToString(k));
748 }
749 internal_iter->Finish();
750
751 options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
752 std::unique_ptr<Iterator> db_iter(NewDBIterator(
753 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
754 internal_iter, i + 2, options.max_sequential_skip_in_iterations,
755 nullptr /*read_callback*/));
756 db_iter->SeekToLast();
757 ASSERT_TRUE(db_iter->Valid());
758
759 ASSERT_EQ(db_iter->key().ToString(), "c");
760 ASSERT_EQ(db_iter->value().ToString(), ToString(i));
761 db_iter->Prev();
762 ASSERT_TRUE(db_iter->Valid());
763
764 ASSERT_EQ(db_iter->key().ToString(), "b");
765 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
766 db_iter->Prev();
767 ASSERT_TRUE(db_iter->Valid());
768
769 ASSERT_EQ(db_iter->key().ToString(), "a");
770 ASSERT_EQ(db_iter->value().ToString(), "merge_2");
771 db_iter->Prev();
772
773 ASSERT_TRUE(!db_iter->Valid());
774 }
775 }
776
777 {
778 for (size_t i = 0; i < 200; ++i) {
779 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
780 internal_iter->AddMerge("b", "merge_1");
781 internal_iter->AddMerge("a", "merge_2");
782 for (size_t k = 0; k < 200; ++k) {
783 internal_iter->AddDeletion("c");
784 }
785 internal_iter->AddPut("c", "200");
786 internal_iter->Finish();
787
788 std::unique_ptr<Iterator> db_iter(NewDBIterator(
789 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
790 internal_iter, i + 2, options.max_sequential_skip_in_iterations,
791 nullptr /*read_callback*/));
792 db_iter->SeekToLast();
793 ASSERT_TRUE(db_iter->Valid());
794
795 ASSERT_EQ(db_iter->key().ToString(), "b");
796 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
797 db_iter->Prev();
798 ASSERT_TRUE(db_iter->Valid());
799
800 ASSERT_EQ(db_iter->key().ToString(), "a");
801 ASSERT_EQ(db_iter->value().ToString(), "merge_2");
802 db_iter->Prev();
803
804 ASSERT_TRUE(!db_iter->Valid());
805 }
806
807 {
808 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
809 internal_iter->AddMerge("b", "merge_1");
810 internal_iter->AddMerge("a", "merge_2");
811 for (size_t i = 0; i < 200; ++i) {
812 internal_iter->AddDeletion("c");
813 }
814 internal_iter->AddPut("c", "200");
815 internal_iter->Finish();
816
817 std::unique_ptr<Iterator> db_iter(NewDBIterator(
818 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
819 internal_iter, 202, options.max_sequential_skip_in_iterations,
820 nullptr /*read_callback*/));
821 db_iter->SeekToLast();
822 ASSERT_TRUE(db_iter->Valid());
823
824 ASSERT_EQ(db_iter->key().ToString(), "c");
825 ASSERT_EQ(db_iter->value().ToString(), "200");
826 db_iter->Prev();
827 ASSERT_TRUE(db_iter->Valid());
828
829 ASSERT_EQ(db_iter->key().ToString(), "b");
830 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
831 db_iter->Prev();
832 ASSERT_TRUE(db_iter->Valid());
833
834 ASSERT_EQ(db_iter->key().ToString(), "a");
835 ASSERT_EQ(db_iter->value().ToString(), "merge_2");
836 db_iter->Prev();
837
838 ASSERT_TRUE(!db_iter->Valid());
839 }
840 }
841
842 {
843 for (size_t i = 0; i < 200; ++i) {
844 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
845 for (size_t k = 0; k < 200; ++k) {
846 internal_iter->AddDeletion("c");
847 }
848 internal_iter->AddPut("c", "200");
849 internal_iter->Finish();
850 std::unique_ptr<Iterator> db_iter(NewDBIterator(
851 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
852 internal_iter, i, options.max_sequential_skip_in_iterations,
853 nullptr /*read_callback*/));
854 db_iter->SeekToLast();
855 ASSERT_TRUE(!db_iter->Valid());
856
857 db_iter->SeekToFirst();
858 ASSERT_TRUE(!db_iter->Valid());
859 }
860
861 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
862 for (size_t i = 0; i < 200; ++i) {
863 internal_iter->AddDeletion("c");
864 }
865 internal_iter->AddPut("c", "200");
866 internal_iter->Finish();
867 std::unique_ptr<Iterator> db_iter(NewDBIterator(
868 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
869 internal_iter, 200, options.max_sequential_skip_in_iterations,
870 nullptr /*read_callback*/));
871 db_iter->SeekToLast();
872 ASSERT_TRUE(db_iter->Valid());
873 ASSERT_EQ(db_iter->key().ToString(), "c");
874 ASSERT_EQ(db_iter->value().ToString(), "200");
875
876 db_iter->Prev();
877 ASSERT_TRUE(!db_iter->Valid());
878
879 db_iter->SeekToFirst();
880 ASSERT_TRUE(db_iter->Valid());
881 ASSERT_EQ(db_iter->key().ToString(), "c");
882 ASSERT_EQ(db_iter->value().ToString(), "200");
883
884 db_iter->Next();
885 ASSERT_TRUE(!db_iter->Valid());
886 }
887
888 {
889 for (size_t i = 0; i < 200; ++i) {
890 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
891 internal_iter->AddMerge("b", "merge_1");
892 internal_iter->AddMerge("a", "merge_2");
893 for (size_t k = 0; k < 200; ++k) {
894 internal_iter->AddPut("d", ToString(k));
895 }
896
897 for (size_t k = 0; k < 200; ++k) {
898 internal_iter->AddPut("c", ToString(k));
899 }
900 internal_iter->Finish();
901
902 std::unique_ptr<Iterator> db_iter(NewDBIterator(
903 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
904 internal_iter, i + 2, options.max_sequential_skip_in_iterations,
905 nullptr /*read_callback*/));
906 db_iter->SeekToLast();
907 ASSERT_TRUE(db_iter->Valid());
908
909 ASSERT_EQ(db_iter->key().ToString(), "d");
910 ASSERT_EQ(db_iter->value().ToString(), ToString(i));
911 db_iter->Prev();
912 ASSERT_TRUE(db_iter->Valid());
913
914 ASSERT_EQ(db_iter->key().ToString(), "b");
915 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
916 db_iter->Prev();
917 ASSERT_TRUE(db_iter->Valid());
918
919 ASSERT_EQ(db_iter->key().ToString(), "a");
920 ASSERT_EQ(db_iter->value().ToString(), "merge_2");
921 db_iter->Prev();
922
923 ASSERT_TRUE(!db_iter->Valid());
924 }
925 }
926
927 {
928 for (size_t i = 0; i < 200; ++i) {
929 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
930 internal_iter->AddMerge("b", "b");
931 internal_iter->AddMerge("a", "a");
932 for (size_t k = 0; k < 200; ++k) {
933 internal_iter->AddMerge("c", ToString(k));
934 }
935 internal_iter->Finish();
936
937 std::unique_ptr<Iterator> db_iter(NewDBIterator(
938 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
939 internal_iter, i + 2, options.max_sequential_skip_in_iterations,
940 nullptr /*read_callback*/));
941 db_iter->SeekToLast();
942 ASSERT_TRUE(db_iter->Valid());
943
944 ASSERT_EQ(db_iter->key().ToString(), "c");
945 std::string merge_result = "0";
946 for (size_t j = 1; j <= i; ++j) {
947 merge_result += "," + ToString(j);
948 }
949 ASSERT_EQ(db_iter->value().ToString(), merge_result);
950
951 db_iter->Prev();
952 ASSERT_TRUE(db_iter->Valid());
953 ASSERT_EQ(db_iter->key().ToString(), "b");
954 ASSERT_EQ(db_iter->value().ToString(), "b");
955
956 db_iter->Prev();
957 ASSERT_TRUE(db_iter->Valid());
958 ASSERT_EQ(db_iter->key().ToString(), "a");
959 ASSERT_EQ(db_iter->value().ToString(), "a");
960
961 db_iter->Prev();
962 ASSERT_TRUE(!db_iter->Valid());
963 }
964 }
965 }
966
967 TEST_F(DBIteratorTest, DBIteratorSkipInternalKeys) {
968 Options options;
969 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
970 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
971 ReadOptions ro;
972
973 // Basic test case ... Make sure explicityly passing the default value works.
974 // Skipping internal keys is disabled by default, when the value is 0.
975 {
976 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
977 internal_iter->AddPut("a", "val_a");
978 internal_iter->AddDeletion("b");
979 internal_iter->AddDeletion("b");
980 internal_iter->AddPut("c", "val_c");
981 internal_iter->AddPut("c", "val_c");
982 internal_iter->AddDeletion("c");
983 internal_iter->AddPut("d", "val_d");
984 internal_iter->Finish();
985
986 ro.max_skippable_internal_keys = 0;
987 std::unique_ptr<Iterator> db_iter(NewDBIterator(
988 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
989 internal_iter, 10, options.max_sequential_skip_in_iterations,
990 nullptr /*read_callback*/));
991
992 db_iter->SeekToFirst();
993 ASSERT_TRUE(db_iter->Valid());
994 ASSERT_EQ(db_iter->key().ToString(), "a");
995 ASSERT_EQ(db_iter->value().ToString(), "val_a");
996
997 db_iter->Next();
998 ASSERT_TRUE(db_iter->Valid());
999 ASSERT_EQ(db_iter->key().ToString(), "d");
1000 ASSERT_EQ(db_iter->value().ToString(), "val_d");
1001
1002 db_iter->Next();
1003 ASSERT_TRUE(!db_iter->Valid());
1004 ASSERT_TRUE(db_iter->status().ok());
1005
1006 db_iter->SeekToLast();
1007 ASSERT_TRUE(db_iter->Valid());
1008 ASSERT_EQ(db_iter->key().ToString(), "d");
1009 ASSERT_EQ(db_iter->value().ToString(), "val_d");
1010
1011 db_iter->Prev();
1012 ASSERT_TRUE(db_iter->Valid());
1013 ASSERT_EQ(db_iter->key().ToString(), "a");
1014 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1015
1016 db_iter->Prev();
1017 ASSERT_TRUE(!db_iter->Valid());
1018 ASSERT_TRUE(db_iter->status().ok());
1019 }
1020
1021 // Test to make sure that the request will *not* fail as incomplete if
1022 // num_internal_keys_skipped is *equal* to max_skippable_internal_keys
1023 // threshold. (It will fail as incomplete only when the threshold is
1024 // exceeded.)
1025 {
1026 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1027 internal_iter->AddPut("a", "val_a");
1028 internal_iter->AddDeletion("b");
1029 internal_iter->AddDeletion("b");
1030 internal_iter->AddPut("c", "val_c");
1031 internal_iter->Finish();
1032
1033 ro.max_skippable_internal_keys = 2;
1034 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1035 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1036 internal_iter, 10, options.max_sequential_skip_in_iterations,
1037 nullptr /*read_callback*/));
1038
1039 db_iter->SeekToFirst();
1040 ASSERT_TRUE(db_iter->Valid());
1041 ASSERT_EQ(db_iter->key().ToString(), "a");
1042 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1043
1044 db_iter->Next();
1045 ASSERT_TRUE(db_iter->Valid());
1046 ASSERT_EQ(db_iter->key().ToString(), "c");
1047 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1048
1049 db_iter->Next();
1050 ASSERT_TRUE(!db_iter->Valid());
1051 ASSERT_TRUE(db_iter->status().ok());
1052
1053 db_iter->SeekToLast();
1054 ASSERT_TRUE(db_iter->Valid());
1055 ASSERT_EQ(db_iter->key().ToString(), "c");
1056 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1057
1058 db_iter->Prev();
1059 ASSERT_EQ(db_iter->key().ToString(), "a");
1060 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1061
1062 db_iter->Prev();
1063 ASSERT_TRUE(!db_iter->Valid());
1064 ASSERT_TRUE(db_iter->status().ok());
1065 }
1066
1067 // Fail the request as incomplete when num_internal_keys_skipped >
1068 // max_skippable_internal_keys
1069 {
1070 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1071 internal_iter->AddPut("a", "val_a");
1072 internal_iter->AddDeletion("b");
1073 internal_iter->AddDeletion("b");
1074 internal_iter->AddDeletion("b");
1075 internal_iter->AddPut("c", "val_c");
1076 internal_iter->Finish();
1077
1078 ro.max_skippable_internal_keys = 2;
1079 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1080 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1081 internal_iter, 10, options.max_sequential_skip_in_iterations,
1082 nullptr /*read_callback*/));
1083
1084 db_iter->SeekToFirst();
1085 ASSERT_TRUE(db_iter->Valid());
1086 ASSERT_EQ(db_iter->key().ToString(), "a");
1087 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1088
1089 db_iter->Next();
1090 ASSERT_TRUE(!db_iter->Valid());
1091 ASSERT_TRUE(db_iter->status().IsIncomplete());
1092
1093 db_iter->SeekToLast();
1094 ASSERT_TRUE(db_iter->Valid());
1095 ASSERT_EQ(db_iter->key().ToString(), "c");
1096 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1097
1098 db_iter->Prev();
1099 ASSERT_TRUE(!db_iter->Valid());
1100 ASSERT_TRUE(db_iter->status().IsIncomplete());
1101 }
1102
1103 // Test that the num_internal_keys_skipped counter resets after a successful
1104 // read.
1105 {
1106 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1107 internal_iter->AddPut("a", "val_a");
1108 internal_iter->AddDeletion("b");
1109 internal_iter->AddDeletion("b");
1110 internal_iter->AddPut("c", "val_c");
1111 internal_iter->AddDeletion("d");
1112 internal_iter->AddDeletion("d");
1113 internal_iter->AddDeletion("d");
1114 internal_iter->AddPut("e", "val_e");
1115 internal_iter->Finish();
1116
1117 ro.max_skippable_internal_keys = 2;
1118 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1119 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1120 internal_iter, 10, options.max_sequential_skip_in_iterations,
1121 nullptr /*read_callback*/));
1122
1123 db_iter->SeekToFirst();
1124 ASSERT_TRUE(db_iter->Valid());
1125 ASSERT_EQ(db_iter->key().ToString(), "a");
1126 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1127
1128 db_iter->Next();
1129 ASSERT_TRUE(db_iter->Valid());
1130 ASSERT_EQ(db_iter->key().ToString(), "c");
1131 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1132
1133 db_iter->Next(); // num_internal_keys_skipped counter resets here.
1134 ASSERT_TRUE(!db_iter->Valid());
1135 ASSERT_TRUE(db_iter->status().IsIncomplete());
1136 }
1137
1138 // Test that the num_internal_keys_skipped counter resets after a successful
1139 // read.
1140 // Reverse direction
1141 {
1142 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1143 internal_iter->AddPut("a", "val_a");
1144 internal_iter->AddDeletion("b");
1145 internal_iter->AddDeletion("b");
1146 internal_iter->AddDeletion("b");
1147 internal_iter->AddPut("c", "val_c");
1148 internal_iter->AddDeletion("d");
1149 internal_iter->AddDeletion("d");
1150 internal_iter->AddPut("e", "val_e");
1151 internal_iter->Finish();
1152
1153 ro.max_skippable_internal_keys = 2;
1154 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1155 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1156 internal_iter, 10, options.max_sequential_skip_in_iterations,
1157 nullptr /*read_callback*/));
1158
1159 db_iter->SeekToLast();
1160 ASSERT_TRUE(db_iter->Valid());
1161 ASSERT_EQ(db_iter->key().ToString(), "e");
1162 ASSERT_EQ(db_iter->value().ToString(), "val_e");
1163
1164 db_iter->Prev();
1165 ASSERT_TRUE(db_iter->Valid());
1166 ASSERT_EQ(db_iter->key().ToString(), "c");
1167 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1168
1169 db_iter->Prev(); // num_internal_keys_skipped counter resets here.
1170 ASSERT_TRUE(!db_iter->Valid());
1171 ASSERT_TRUE(db_iter->status().IsIncomplete());
1172 }
1173
1174 // Test that skipping separate keys is handled
1175 {
1176 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1177 internal_iter->AddPut("a", "val_a");
1178 internal_iter->AddDeletion("b");
1179 internal_iter->AddDeletion("c");
1180 internal_iter->AddDeletion("d");
1181 internal_iter->AddPut("e", "val_e");
1182 internal_iter->Finish();
1183
1184 ro.max_skippable_internal_keys = 2;
1185 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1186 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1187 internal_iter, 10, options.max_sequential_skip_in_iterations,
1188 nullptr /*read_callback*/));
1189
1190 db_iter->SeekToFirst();
1191 ASSERT_TRUE(db_iter->Valid());
1192 ASSERT_EQ(db_iter->key().ToString(), "a");
1193 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1194
1195 db_iter->Next();
1196 ASSERT_TRUE(!db_iter->Valid());
1197 ASSERT_TRUE(db_iter->status().IsIncomplete());
1198
1199 db_iter->SeekToLast();
1200 ASSERT_TRUE(db_iter->Valid());
1201 ASSERT_EQ(db_iter->key().ToString(), "e");
1202 ASSERT_EQ(db_iter->value().ToString(), "val_e");
1203
1204 db_iter->Prev();
1205 ASSERT_TRUE(!db_iter->Valid());
1206 ASSERT_TRUE(db_iter->status().IsIncomplete());
1207 }
1208
1209 // Test if alternating puts and deletes of the same key are handled correctly.
1210 {
1211 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1212 internal_iter->AddPut("a", "val_a");
1213 internal_iter->AddPut("b", "val_b");
1214 internal_iter->AddDeletion("b");
1215 internal_iter->AddPut("c", "val_c");
1216 internal_iter->AddDeletion("c");
1217 internal_iter->AddPut("d", "val_d");
1218 internal_iter->AddDeletion("d");
1219 internal_iter->AddPut("e", "val_e");
1220 internal_iter->Finish();
1221
1222 ro.max_skippable_internal_keys = 2;
1223 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1224 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1225 internal_iter, 10, options.max_sequential_skip_in_iterations,
1226 nullptr /*read_callback*/));
1227
1228 db_iter->SeekToFirst();
1229 ASSERT_TRUE(db_iter->Valid());
1230 ASSERT_EQ(db_iter->key().ToString(), "a");
1231 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1232
1233 db_iter->Next();
1234 ASSERT_TRUE(!db_iter->Valid());
1235 ASSERT_TRUE(db_iter->status().IsIncomplete());
1236
1237 db_iter->SeekToLast();
1238 ASSERT_TRUE(db_iter->Valid());
1239 ASSERT_EQ(db_iter->key().ToString(), "e");
1240 ASSERT_EQ(db_iter->value().ToString(), "val_e");
1241
1242 db_iter->Prev();
1243 ASSERT_TRUE(!db_iter->Valid());
1244 ASSERT_TRUE(db_iter->status().IsIncomplete());
1245 }
1246
1247 // Test for large number of skippable internal keys with *default*
1248 // max_sequential_skip_in_iterations.
1249 {
1250 for (size_t i = 1; i <= 200; ++i) {
1251 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1252 internal_iter->AddPut("a", "val_a");
1253 for (size_t j = 1; j <= i; ++j) {
1254 internal_iter->AddPut("b", "val_b");
1255 internal_iter->AddDeletion("b");
1256 }
1257 internal_iter->AddPut("c", "val_c");
1258 internal_iter->Finish();
1259
1260 ro.max_skippable_internal_keys = i;
1261 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1262 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1263 internal_iter, 2 * i + 1, options.max_sequential_skip_in_iterations,
1264 nullptr /*read_callback*/));
1265
1266 db_iter->SeekToFirst();
1267 ASSERT_TRUE(db_iter->Valid());
1268 ASSERT_EQ(db_iter->key().ToString(), "a");
1269 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1270
1271 db_iter->Next();
1272 if ((options.max_sequential_skip_in_iterations + 1) >=
1273 ro.max_skippable_internal_keys) {
1274 ASSERT_TRUE(!db_iter->Valid());
1275 ASSERT_TRUE(db_iter->status().IsIncomplete());
1276 } else {
1277 ASSERT_TRUE(db_iter->Valid());
1278 ASSERT_EQ(db_iter->key().ToString(), "c");
1279 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1280 }
1281
1282 db_iter->SeekToLast();
1283 ASSERT_TRUE(db_iter->Valid());
1284 ASSERT_EQ(db_iter->key().ToString(), "c");
1285 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1286
1287 db_iter->Prev();
1288 if ((options.max_sequential_skip_in_iterations + 1) >=
1289 ro.max_skippable_internal_keys) {
1290 ASSERT_TRUE(!db_iter->Valid());
1291 ASSERT_TRUE(db_iter->status().IsIncomplete());
1292 } else {
1293 ASSERT_TRUE(db_iter->Valid());
1294 ASSERT_EQ(db_iter->key().ToString(), "a");
1295 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1296 }
1297 }
1298 }
1299
1300 // Test for large number of skippable internal keys with a *non-default*
1301 // max_sequential_skip_in_iterations.
1302 {
1303 for (size_t i = 1; i <= 200; ++i) {
1304 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1305 internal_iter->AddPut("a", "val_a");
1306 for (size_t j = 1; j <= i; ++j) {
1307 internal_iter->AddPut("b", "val_b");
1308 internal_iter->AddDeletion("b");
1309 }
1310 internal_iter->AddPut("c", "val_c");
1311 internal_iter->Finish();
1312
1313 options.max_sequential_skip_in_iterations = 1000;
1314 ro.max_skippable_internal_keys = i;
1315 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1316 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1317 internal_iter, 2 * i + 1, options.max_sequential_skip_in_iterations,
1318 nullptr /*read_callback*/));
1319
1320 db_iter->SeekToFirst();
1321 ASSERT_TRUE(db_iter->Valid());
1322 ASSERT_EQ(db_iter->key().ToString(), "a");
1323 ASSERT_EQ(db_iter->value().ToString(), "val_a");
1324
1325 db_iter->Next();
1326 ASSERT_TRUE(!db_iter->Valid());
1327 ASSERT_TRUE(db_iter->status().IsIncomplete());
1328
1329 db_iter->SeekToLast();
1330 ASSERT_TRUE(db_iter->Valid());
1331 ASSERT_EQ(db_iter->key().ToString(), "c");
1332 ASSERT_EQ(db_iter->value().ToString(), "val_c");
1333
1334 db_iter->Prev();
1335 ASSERT_TRUE(!db_iter->Valid());
1336 ASSERT_TRUE(db_iter->status().IsIncomplete());
1337 }
1338 }
1339 }
1340
1341 TEST_F(DBIteratorTest, DBIterator1) {
1342 ReadOptions ro;
1343 Options options;
1344 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1345
1346 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1347 internal_iter->AddPut("a", "0");
1348 internal_iter->AddPut("b", "0");
1349 internal_iter->AddDeletion("b");
1350 internal_iter->AddMerge("a", "1");
1351 internal_iter->AddMerge("b", "2");
1352 internal_iter->Finish();
1353
1354 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1355 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
1356 BytewiseComparator(), internal_iter, 1,
1357 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
1358 db_iter->SeekToFirst();
1359 ASSERT_TRUE(db_iter->Valid());
1360 ASSERT_EQ(db_iter->key().ToString(), "a");
1361 ASSERT_EQ(db_iter->value().ToString(), "0");
1362 db_iter->Next();
1363 ASSERT_TRUE(db_iter->Valid());
1364 ASSERT_EQ(db_iter->key().ToString(), "b");
1365 db_iter->Next();
1366 ASSERT_FALSE(db_iter->Valid());
1367 }
1368
1369 TEST_F(DBIteratorTest, DBIterator2) {
1370 ReadOptions ro;
1371 Options options;
1372 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1373
1374 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1375 internal_iter->AddPut("a", "0");
1376 internal_iter->AddPut("b", "0");
1377 internal_iter->AddDeletion("b");
1378 internal_iter->AddMerge("a", "1");
1379 internal_iter->AddMerge("b", "2");
1380 internal_iter->Finish();
1381
1382 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1383 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
1384 BytewiseComparator(), internal_iter, 0,
1385 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
1386 db_iter->SeekToFirst();
1387 ASSERT_TRUE(db_iter->Valid());
1388 ASSERT_EQ(db_iter->key().ToString(), "a");
1389 ASSERT_EQ(db_iter->value().ToString(), "0");
1390 db_iter->Next();
1391 ASSERT_TRUE(!db_iter->Valid());
1392 }
1393
1394 TEST_F(DBIteratorTest, DBIterator3) {
1395 ReadOptions ro;
1396 Options options;
1397 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1398
1399 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1400 internal_iter->AddPut("a", "0");
1401 internal_iter->AddPut("b", "0");
1402 internal_iter->AddDeletion("b");
1403 internal_iter->AddMerge("a", "1");
1404 internal_iter->AddMerge("b", "2");
1405 internal_iter->Finish();
1406
1407 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1408 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
1409 BytewiseComparator(), internal_iter, 2,
1410 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
1411 db_iter->SeekToFirst();
1412 ASSERT_TRUE(db_iter->Valid());
1413 ASSERT_EQ(db_iter->key().ToString(), "a");
1414 ASSERT_EQ(db_iter->value().ToString(), "0");
1415 db_iter->Next();
1416 ASSERT_TRUE(!db_iter->Valid());
1417 }
1418
1419 TEST_F(DBIteratorTest, DBIterator4) {
1420 ReadOptions ro;
1421 Options options;
1422 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1423
1424 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1425 internal_iter->AddPut("a", "0");
1426 internal_iter->AddPut("b", "0");
1427 internal_iter->AddDeletion("b");
1428 internal_iter->AddMerge("a", "1");
1429 internal_iter->AddMerge("b", "2");
1430 internal_iter->Finish();
1431
1432 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1433 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
1434 BytewiseComparator(), internal_iter, 4,
1435 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
1436 db_iter->SeekToFirst();
1437 ASSERT_TRUE(db_iter->Valid());
1438 ASSERT_EQ(db_iter->key().ToString(), "a");
1439 ASSERT_EQ(db_iter->value().ToString(), "0,1");
1440 db_iter->Next();
1441 ASSERT_TRUE(db_iter->Valid());
1442 ASSERT_EQ(db_iter->key().ToString(), "b");
1443 ASSERT_EQ(db_iter->value().ToString(), "2");
1444 db_iter->Next();
1445 ASSERT_TRUE(!db_iter->Valid());
1446 }
1447
1448 TEST_F(DBIteratorTest, DBIterator5) {
1449 ReadOptions ro;
1450 Options options;
1451 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1452 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
1453 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
1454
1455 {
1456 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1457 internal_iter->AddMerge("a", "merge_1");
1458 internal_iter->AddMerge("a", "merge_2");
1459 internal_iter->AddMerge("a", "merge_3");
1460 internal_iter->AddPut("a", "put_1");
1461 internal_iter->AddMerge("a", "merge_4");
1462 internal_iter->AddMerge("a", "merge_5");
1463 internal_iter->AddMerge("a", "merge_6");
1464 internal_iter->Finish();
1465
1466 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1467 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1468 internal_iter, 0, options.max_sequential_skip_in_iterations,
1469 nullptr /*read_callback*/));
1470 db_iter->SeekToLast();
1471 ASSERT_TRUE(db_iter->Valid());
1472 ASSERT_EQ(db_iter->key().ToString(), "a");
1473 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
1474 db_iter->Prev();
1475 ASSERT_TRUE(!db_iter->Valid());
1476 }
1477
1478 {
1479 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1480 internal_iter->AddMerge("a", "merge_1");
1481 internal_iter->AddMerge("a", "merge_2");
1482 internal_iter->AddMerge("a", "merge_3");
1483 internal_iter->AddPut("a", "put_1");
1484 internal_iter->AddMerge("a", "merge_4");
1485 internal_iter->AddMerge("a", "merge_5");
1486 internal_iter->AddMerge("a", "merge_6");
1487 internal_iter->Finish();
1488
1489 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1490 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1491 internal_iter, 1, options.max_sequential_skip_in_iterations,
1492 nullptr /*read_callback*/));
1493 db_iter->SeekToLast();
1494 ASSERT_TRUE(db_iter->Valid());
1495 ASSERT_EQ(db_iter->key().ToString(), "a");
1496 ASSERT_EQ(db_iter->value().ToString(), "merge_1,merge_2");
1497 db_iter->Prev();
1498 ASSERT_TRUE(!db_iter->Valid());
1499 }
1500
1501 {
1502 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1503 internal_iter->AddMerge("a", "merge_1");
1504 internal_iter->AddMerge("a", "merge_2");
1505 internal_iter->AddMerge("a", "merge_3");
1506 internal_iter->AddPut("a", "put_1");
1507 internal_iter->AddMerge("a", "merge_4");
1508 internal_iter->AddMerge("a", "merge_5");
1509 internal_iter->AddMerge("a", "merge_6");
1510 internal_iter->Finish();
1511
1512 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1513 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1514 internal_iter, 2, options.max_sequential_skip_in_iterations,
1515 nullptr /*read_callback*/));
1516 db_iter->SeekToLast();
1517 ASSERT_TRUE(db_iter->Valid());
1518 ASSERT_EQ(db_iter->key().ToString(), "a");
1519 ASSERT_EQ(db_iter->value().ToString(), "merge_1,merge_2,merge_3");
1520 db_iter->Prev();
1521 ASSERT_TRUE(!db_iter->Valid());
1522 }
1523
1524 {
1525 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1526 internal_iter->AddMerge("a", "merge_1");
1527 internal_iter->AddMerge("a", "merge_2");
1528 internal_iter->AddMerge("a", "merge_3");
1529 internal_iter->AddPut("a", "put_1");
1530 internal_iter->AddMerge("a", "merge_4");
1531 internal_iter->AddMerge("a", "merge_5");
1532 internal_iter->AddMerge("a", "merge_6");
1533 internal_iter->Finish();
1534
1535 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1536 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1537 internal_iter, 3, options.max_sequential_skip_in_iterations,
1538 nullptr /*read_callback*/));
1539 db_iter->SeekToLast();
1540 ASSERT_TRUE(db_iter->Valid());
1541 ASSERT_EQ(db_iter->key().ToString(), "a");
1542 ASSERT_EQ(db_iter->value().ToString(), "put_1");
1543 db_iter->Prev();
1544 ASSERT_TRUE(!db_iter->Valid());
1545 }
1546
1547 {
1548 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1549 internal_iter->AddMerge("a", "merge_1");
1550 internal_iter->AddMerge("a", "merge_2");
1551 internal_iter->AddMerge("a", "merge_3");
1552 internal_iter->AddPut("a", "put_1");
1553 internal_iter->AddMerge("a", "merge_4");
1554 internal_iter->AddMerge("a", "merge_5");
1555 internal_iter->AddMerge("a", "merge_6");
1556 internal_iter->Finish();
1557
1558 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1559 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1560 internal_iter, 4, options.max_sequential_skip_in_iterations,
1561 nullptr /*read_callback*/));
1562 db_iter->SeekToLast();
1563 ASSERT_TRUE(db_iter->Valid());
1564 ASSERT_EQ(db_iter->key().ToString(), "a");
1565 ASSERT_EQ(db_iter->value().ToString(), "put_1,merge_4");
1566 db_iter->Prev();
1567 ASSERT_TRUE(!db_iter->Valid());
1568 }
1569
1570 {
1571 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1572 internal_iter->AddMerge("a", "merge_1");
1573 internal_iter->AddMerge("a", "merge_2");
1574 internal_iter->AddMerge("a", "merge_3");
1575 internal_iter->AddPut("a", "put_1");
1576 internal_iter->AddMerge("a", "merge_4");
1577 internal_iter->AddMerge("a", "merge_5");
1578 internal_iter->AddMerge("a", "merge_6");
1579 internal_iter->Finish();
1580
1581 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1582 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1583 internal_iter, 5, options.max_sequential_skip_in_iterations,
1584 nullptr /*read_callback*/));
1585 db_iter->SeekToLast();
1586 ASSERT_TRUE(db_iter->Valid());
1587 ASSERT_EQ(db_iter->key().ToString(), "a");
1588 ASSERT_EQ(db_iter->value().ToString(), "put_1,merge_4,merge_5");
1589 db_iter->Prev();
1590 ASSERT_TRUE(!db_iter->Valid());
1591 }
1592
1593 {
1594 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1595 internal_iter->AddMerge("a", "merge_1");
1596 internal_iter->AddMerge("a", "merge_2");
1597 internal_iter->AddMerge("a", "merge_3");
1598 internal_iter->AddPut("a", "put_1");
1599 internal_iter->AddMerge("a", "merge_4");
1600 internal_iter->AddMerge("a", "merge_5");
1601 internal_iter->AddMerge("a", "merge_6");
1602 internal_iter->Finish();
1603
1604 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1605 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1606 internal_iter, 6, options.max_sequential_skip_in_iterations,
1607 nullptr /*read_callback*/));
1608 db_iter->SeekToLast();
1609 ASSERT_TRUE(db_iter->Valid());
1610 ASSERT_EQ(db_iter->key().ToString(), "a");
1611 ASSERT_EQ(db_iter->value().ToString(), "put_1,merge_4,merge_5,merge_6");
1612 db_iter->Prev();
1613 ASSERT_TRUE(!db_iter->Valid());
1614 }
1615
1616 {
1617 // put, singledelete, merge
1618 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1619 internal_iter->AddPut("a", "val_a");
1620 internal_iter->AddSingleDeletion("a");
1621 internal_iter->AddMerge("a", "merge_1");
1622 internal_iter->AddMerge("a", "merge_2");
1623 internal_iter->AddPut("b", "val_b");
1624 internal_iter->Finish();
1625 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1626 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1627 internal_iter, 10, options.max_sequential_skip_in_iterations,
1628 nullptr /*read_callback*/));
1629 db_iter->Seek("b");
1630 ASSERT_TRUE(db_iter->Valid());
1631 ASSERT_EQ(db_iter->key().ToString(), "b");
1632 db_iter->Prev();
1633 ASSERT_TRUE(db_iter->Valid());
1634 ASSERT_EQ(db_iter->key().ToString(), "a");
1635 }
1636 }
1637
1638 TEST_F(DBIteratorTest, DBIterator6) {
1639 ReadOptions ro;
1640 Options options;
1641 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1642 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
1643 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
1644
1645 {
1646 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1647 internal_iter->AddMerge("a", "merge_1");
1648 internal_iter->AddMerge("a", "merge_2");
1649 internal_iter->AddMerge("a", "merge_3");
1650 internal_iter->AddDeletion("a");
1651 internal_iter->AddMerge("a", "merge_4");
1652 internal_iter->AddMerge("a", "merge_5");
1653 internal_iter->AddMerge("a", "merge_6");
1654 internal_iter->Finish();
1655
1656 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1657 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1658 internal_iter, 0, options.max_sequential_skip_in_iterations,
1659 nullptr /*read_callback*/));
1660 db_iter->SeekToLast();
1661 ASSERT_TRUE(db_iter->Valid());
1662 ASSERT_EQ(db_iter->key().ToString(), "a");
1663 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
1664 db_iter->Prev();
1665 ASSERT_TRUE(!db_iter->Valid());
1666 }
1667
1668 {
1669 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1670 internal_iter->AddMerge("a", "merge_1");
1671 internal_iter->AddMerge("a", "merge_2");
1672 internal_iter->AddMerge("a", "merge_3");
1673 internal_iter->AddDeletion("a");
1674 internal_iter->AddMerge("a", "merge_4");
1675 internal_iter->AddMerge("a", "merge_5");
1676 internal_iter->AddMerge("a", "merge_6");
1677 internal_iter->Finish();
1678
1679 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1680 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1681 internal_iter, 1, options.max_sequential_skip_in_iterations,
1682 nullptr /*read_callback*/));
1683 db_iter->SeekToLast();
1684 ASSERT_TRUE(db_iter->Valid());
1685 ASSERT_EQ(db_iter->key().ToString(), "a");
1686 ASSERT_EQ(db_iter->value().ToString(), "merge_1,merge_2");
1687 db_iter->Prev();
1688 ASSERT_TRUE(!db_iter->Valid());
1689 }
1690
1691 {
1692 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1693 internal_iter->AddMerge("a", "merge_1");
1694 internal_iter->AddMerge("a", "merge_2");
1695 internal_iter->AddMerge("a", "merge_3");
1696 internal_iter->AddDeletion("a");
1697 internal_iter->AddMerge("a", "merge_4");
1698 internal_iter->AddMerge("a", "merge_5");
1699 internal_iter->AddMerge("a", "merge_6");
1700 internal_iter->Finish();
1701
1702 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1703 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1704 internal_iter, 2, options.max_sequential_skip_in_iterations,
1705 nullptr /*read_callback*/));
1706 db_iter->SeekToLast();
1707 ASSERT_TRUE(db_iter->Valid());
1708 ASSERT_EQ(db_iter->key().ToString(), "a");
1709 ASSERT_EQ(db_iter->value().ToString(), "merge_1,merge_2,merge_3");
1710 db_iter->Prev();
1711 ASSERT_TRUE(!db_iter->Valid());
1712 }
1713
1714 {
1715 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1716 internal_iter->AddMerge("a", "merge_1");
1717 internal_iter->AddMerge("a", "merge_2");
1718 internal_iter->AddMerge("a", "merge_3");
1719 internal_iter->AddDeletion("a");
1720 internal_iter->AddMerge("a", "merge_4");
1721 internal_iter->AddMerge("a", "merge_5");
1722 internal_iter->AddMerge("a", "merge_6");
1723 internal_iter->Finish();
1724
1725 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1726 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1727 internal_iter, 3, options.max_sequential_skip_in_iterations,
1728 nullptr /*read_callback*/));
1729 db_iter->SeekToLast();
1730 ASSERT_TRUE(!db_iter->Valid());
1731 }
1732
1733 {
1734 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1735 internal_iter->AddMerge("a", "merge_1");
1736 internal_iter->AddMerge("a", "merge_2");
1737 internal_iter->AddMerge("a", "merge_3");
1738 internal_iter->AddDeletion("a");
1739 internal_iter->AddMerge("a", "merge_4");
1740 internal_iter->AddMerge("a", "merge_5");
1741 internal_iter->AddMerge("a", "merge_6");
1742 internal_iter->Finish();
1743
1744 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1745 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1746 internal_iter, 4, options.max_sequential_skip_in_iterations,
1747 nullptr /*read_callback*/));
1748 db_iter->SeekToLast();
1749 ASSERT_TRUE(db_iter->Valid());
1750 ASSERT_EQ(db_iter->key().ToString(), "a");
1751 ASSERT_EQ(db_iter->value().ToString(), "merge_4");
1752 db_iter->Prev();
1753 ASSERT_TRUE(!db_iter->Valid());
1754 }
1755
1756 {
1757 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1758 internal_iter->AddMerge("a", "merge_1");
1759 internal_iter->AddMerge("a", "merge_2");
1760 internal_iter->AddMerge("a", "merge_3");
1761 internal_iter->AddDeletion("a");
1762 internal_iter->AddMerge("a", "merge_4");
1763 internal_iter->AddMerge("a", "merge_5");
1764 internal_iter->AddMerge("a", "merge_6");
1765 internal_iter->Finish();
1766
1767 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1768 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1769 internal_iter, 5, options.max_sequential_skip_in_iterations,
1770 nullptr /*read_callback*/));
1771 db_iter->SeekToLast();
1772 ASSERT_TRUE(db_iter->Valid());
1773 ASSERT_EQ(db_iter->key().ToString(), "a");
1774 ASSERT_EQ(db_iter->value().ToString(), "merge_4,merge_5");
1775 db_iter->Prev();
1776 ASSERT_TRUE(!db_iter->Valid());
1777 }
1778
1779 {
1780 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1781 internal_iter->AddMerge("a", "merge_1");
1782 internal_iter->AddMerge("a", "merge_2");
1783 internal_iter->AddMerge("a", "merge_3");
1784 internal_iter->AddDeletion("a");
1785 internal_iter->AddMerge("a", "merge_4");
1786 internal_iter->AddMerge("a", "merge_5");
1787 internal_iter->AddMerge("a", "merge_6");
1788 internal_iter->Finish();
1789
1790 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1791 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1792 internal_iter, 6, options.max_sequential_skip_in_iterations,
1793 nullptr /*read_callback*/));
1794 db_iter->SeekToLast();
1795 ASSERT_TRUE(db_iter->Valid());
1796 ASSERT_EQ(db_iter->key().ToString(), "a");
1797 ASSERT_EQ(db_iter->value().ToString(), "merge_4,merge_5,merge_6");
1798 db_iter->Prev();
1799 ASSERT_TRUE(!db_iter->Valid());
1800 }
1801 }
1802
1803 TEST_F(DBIteratorTest, DBIterator7) {
1804 ReadOptions ro;
1805 Options options;
1806 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
1807 ImmutableCFOptions cf_options = ImmutableCFOptions(options);
1808 MutableCFOptions mutable_cf_options = MutableCFOptions(options);
1809
1810 {
1811 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1812 internal_iter->AddMerge("a", "merge_1");
1813 internal_iter->AddPut("b", "val");
1814 internal_iter->AddMerge("b", "merge_2");
1815
1816 internal_iter->AddDeletion("b");
1817 internal_iter->AddMerge("b", "merge_3");
1818
1819 internal_iter->AddMerge("c", "merge_4");
1820 internal_iter->AddMerge("c", "merge_5");
1821
1822 internal_iter->AddDeletion("b");
1823 internal_iter->AddMerge("b", "merge_6");
1824 internal_iter->AddMerge("b", "merge_7");
1825 internal_iter->AddMerge("b", "merge_8");
1826 internal_iter->AddMerge("b", "merge_9");
1827 internal_iter->AddMerge("b", "merge_10");
1828 internal_iter->AddMerge("b", "merge_11");
1829
1830 internal_iter->AddDeletion("c");
1831 internal_iter->Finish();
1832
1833 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1834 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1835 internal_iter, 0, options.max_sequential_skip_in_iterations,
1836 nullptr /*read_callback*/));
1837 db_iter->SeekToLast();
1838 ASSERT_TRUE(db_iter->Valid());
1839 ASSERT_EQ(db_iter->key().ToString(), "a");
1840 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
1841 db_iter->Prev();
1842 ASSERT_TRUE(!db_iter->Valid());
1843 }
1844
1845 {
1846 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1847 internal_iter->AddMerge("a", "merge_1");
1848 internal_iter->AddPut("b", "val");
1849 internal_iter->AddMerge("b", "merge_2");
1850
1851 internal_iter->AddDeletion("b");
1852 internal_iter->AddMerge("b", "merge_3");
1853
1854 internal_iter->AddMerge("c", "merge_4");
1855 internal_iter->AddMerge("c", "merge_5");
1856
1857 internal_iter->AddDeletion("b");
1858 internal_iter->AddMerge("b", "merge_6");
1859 internal_iter->AddMerge("b", "merge_7");
1860 internal_iter->AddMerge("b", "merge_8");
1861 internal_iter->AddMerge("b", "merge_9");
1862 internal_iter->AddMerge("b", "merge_10");
1863 internal_iter->AddMerge("b", "merge_11");
1864
1865 internal_iter->AddDeletion("c");
1866 internal_iter->Finish();
1867
1868 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1869 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1870 internal_iter, 2, options.max_sequential_skip_in_iterations,
1871 nullptr /*read_callback*/));
1872 db_iter->SeekToLast();
1873 ASSERT_TRUE(db_iter->Valid());
1874
1875 ASSERT_EQ(db_iter->key().ToString(), "b");
1876 ASSERT_EQ(db_iter->value().ToString(), "val,merge_2");
1877 db_iter->Prev();
1878 ASSERT_TRUE(db_iter->Valid());
1879
1880 ASSERT_EQ(db_iter->key().ToString(), "a");
1881 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
1882 db_iter->Prev();
1883 ASSERT_TRUE(!db_iter->Valid());
1884 }
1885
1886 {
1887 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1888 internal_iter->AddMerge("a", "merge_1");
1889 internal_iter->AddPut("b", "val");
1890 internal_iter->AddMerge("b", "merge_2");
1891
1892 internal_iter->AddDeletion("b");
1893 internal_iter->AddMerge("b", "merge_3");
1894
1895 internal_iter->AddMerge("c", "merge_4");
1896 internal_iter->AddMerge("c", "merge_5");
1897
1898 internal_iter->AddDeletion("b");
1899 internal_iter->AddMerge("b", "merge_6");
1900 internal_iter->AddMerge("b", "merge_7");
1901 internal_iter->AddMerge("b", "merge_8");
1902 internal_iter->AddMerge("b", "merge_9");
1903 internal_iter->AddMerge("b", "merge_10");
1904 internal_iter->AddMerge("b", "merge_11");
1905
1906 internal_iter->AddDeletion("c");
1907 internal_iter->Finish();
1908
1909 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1910 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1911 internal_iter, 4, options.max_sequential_skip_in_iterations,
1912 nullptr /*read_callback*/));
1913 db_iter->SeekToLast();
1914 ASSERT_TRUE(db_iter->Valid());
1915
1916 ASSERT_EQ(db_iter->key().ToString(), "b");
1917 ASSERT_EQ(db_iter->value().ToString(), "merge_3");
1918 db_iter->Prev();
1919 ASSERT_TRUE(db_iter->Valid());
1920
1921 ASSERT_EQ(db_iter->key().ToString(), "a");
1922 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
1923 db_iter->Prev();
1924 ASSERT_TRUE(!db_iter->Valid());
1925 }
1926
1927 {
1928 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1929 internal_iter->AddMerge("a", "merge_1");
1930 internal_iter->AddPut("b", "val");
1931 internal_iter->AddMerge("b", "merge_2");
1932
1933 internal_iter->AddDeletion("b");
1934 internal_iter->AddMerge("b", "merge_3");
1935
1936 internal_iter->AddMerge("c", "merge_4");
1937 internal_iter->AddMerge("c", "merge_5");
1938
1939 internal_iter->AddDeletion("b");
1940 internal_iter->AddMerge("b", "merge_6");
1941 internal_iter->AddMerge("b", "merge_7");
1942 internal_iter->AddMerge("b", "merge_8");
1943 internal_iter->AddMerge("b", "merge_9");
1944 internal_iter->AddMerge("b", "merge_10");
1945 internal_iter->AddMerge("b", "merge_11");
1946
1947 internal_iter->AddDeletion("c");
1948 internal_iter->Finish();
1949
1950 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1951 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1952 internal_iter, 5, options.max_sequential_skip_in_iterations,
1953 nullptr /*read_callback*/));
1954 db_iter->SeekToLast();
1955 ASSERT_TRUE(db_iter->Valid());
1956
1957 ASSERT_EQ(db_iter->key().ToString(), "c");
1958 ASSERT_EQ(db_iter->value().ToString(), "merge_4");
1959 db_iter->Prev();
1960
1961 ASSERT_TRUE(db_iter->Valid());
1962 ASSERT_EQ(db_iter->key().ToString(), "b");
1963 ASSERT_EQ(db_iter->value().ToString(), "merge_3");
1964 db_iter->Prev();
1965 ASSERT_TRUE(db_iter->Valid());
1966
1967 ASSERT_EQ(db_iter->key().ToString(), "a");
1968 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
1969 db_iter->Prev();
1970 ASSERT_TRUE(!db_iter->Valid());
1971 }
1972
1973 {
1974 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
1975 internal_iter->AddMerge("a", "merge_1");
1976 internal_iter->AddPut("b", "val");
1977 internal_iter->AddMerge("b", "merge_2");
1978
1979 internal_iter->AddDeletion("b");
1980 internal_iter->AddMerge("b", "merge_3");
1981
1982 internal_iter->AddMerge("c", "merge_4");
1983 internal_iter->AddMerge("c", "merge_5");
1984
1985 internal_iter->AddDeletion("b");
1986 internal_iter->AddMerge("b", "merge_6");
1987 internal_iter->AddMerge("b", "merge_7");
1988 internal_iter->AddMerge("b", "merge_8");
1989 internal_iter->AddMerge("b", "merge_9");
1990 internal_iter->AddMerge("b", "merge_10");
1991 internal_iter->AddMerge("b", "merge_11");
1992
1993 internal_iter->AddDeletion("c");
1994 internal_iter->Finish();
1995
1996 std::unique_ptr<Iterator> db_iter(NewDBIterator(
1997 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
1998 internal_iter, 6, options.max_sequential_skip_in_iterations,
1999 nullptr /*read_callback*/));
2000 db_iter->SeekToLast();
2001 ASSERT_TRUE(db_iter->Valid());
2002
2003 ASSERT_EQ(db_iter->key().ToString(), "c");
2004 ASSERT_EQ(db_iter->value().ToString(), "merge_4,merge_5");
2005 db_iter->Prev();
2006 ASSERT_TRUE(db_iter->Valid());
2007
2008 ASSERT_TRUE(db_iter->Valid());
2009 ASSERT_EQ(db_iter->key().ToString(), "b");
2010 ASSERT_EQ(db_iter->value().ToString(), "merge_3");
2011 db_iter->Prev();
2012 ASSERT_TRUE(db_iter->Valid());
2013
2014 ASSERT_EQ(db_iter->key().ToString(), "a");
2015 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
2016 db_iter->Prev();
2017 ASSERT_TRUE(!db_iter->Valid());
2018 }
2019
2020 {
2021 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2022 internal_iter->AddMerge("a", "merge_1");
2023 internal_iter->AddPut("b", "val");
2024 internal_iter->AddMerge("b", "merge_2");
2025
2026 internal_iter->AddDeletion("b");
2027 internal_iter->AddMerge("b", "merge_3");
2028
2029 internal_iter->AddMerge("c", "merge_4");
2030 internal_iter->AddMerge("c", "merge_5");
2031
2032 internal_iter->AddDeletion("b");
2033 internal_iter->AddMerge("b", "merge_6");
2034 internal_iter->AddMerge("b", "merge_7");
2035 internal_iter->AddMerge("b", "merge_8");
2036 internal_iter->AddMerge("b", "merge_9");
2037 internal_iter->AddMerge("b", "merge_10");
2038 internal_iter->AddMerge("b", "merge_11");
2039
2040 internal_iter->AddDeletion("c");
2041 internal_iter->Finish();
2042
2043 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2044 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
2045 internal_iter, 7, options.max_sequential_skip_in_iterations,
2046 nullptr /*read_callback*/));
2047 db_iter->SeekToLast();
2048 ASSERT_TRUE(db_iter->Valid());
2049
2050 ASSERT_EQ(db_iter->key().ToString(), "c");
2051 ASSERT_EQ(db_iter->value().ToString(), "merge_4,merge_5");
2052 db_iter->Prev();
2053 ASSERT_TRUE(db_iter->Valid());
2054
2055 ASSERT_EQ(db_iter->key().ToString(), "a");
2056 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
2057 db_iter->Prev();
2058 ASSERT_TRUE(!db_iter->Valid());
2059 }
2060
2061 {
2062 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2063 internal_iter->AddMerge("a", "merge_1");
2064 internal_iter->AddPut("b", "val");
2065 internal_iter->AddMerge("b", "merge_2");
2066
2067 internal_iter->AddDeletion("b");
2068 internal_iter->AddMerge("b", "merge_3");
2069
2070 internal_iter->AddMerge("c", "merge_4");
2071 internal_iter->AddMerge("c", "merge_5");
2072
2073 internal_iter->AddDeletion("b");
2074 internal_iter->AddMerge("b", "merge_6");
2075 internal_iter->AddMerge("b", "merge_7");
2076 internal_iter->AddMerge("b", "merge_8");
2077 internal_iter->AddMerge("b", "merge_9");
2078 internal_iter->AddMerge("b", "merge_10");
2079 internal_iter->AddMerge("b", "merge_11");
2080
2081 internal_iter->AddDeletion("c");
2082 internal_iter->Finish();
2083
2084 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2085 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
2086 internal_iter, 9, options.max_sequential_skip_in_iterations,
2087 nullptr /*read_callback*/));
2088 db_iter->SeekToLast();
2089 ASSERT_TRUE(db_iter->Valid());
2090
2091 ASSERT_EQ(db_iter->key().ToString(), "c");
2092 ASSERT_EQ(db_iter->value().ToString(), "merge_4,merge_5");
2093 db_iter->Prev();
2094 ASSERT_TRUE(db_iter->Valid());
2095
2096 ASSERT_TRUE(db_iter->Valid());
2097 ASSERT_EQ(db_iter->key().ToString(), "b");
2098 ASSERT_EQ(db_iter->value().ToString(), "merge_6,merge_7");
2099 db_iter->Prev();
2100 ASSERT_TRUE(db_iter->Valid());
2101
2102 ASSERT_EQ(db_iter->key().ToString(), "a");
2103 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
2104 db_iter->Prev();
2105 ASSERT_TRUE(!db_iter->Valid());
2106 }
2107
2108 {
2109 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2110 internal_iter->AddMerge("a", "merge_1");
2111 internal_iter->AddPut("b", "val");
2112 internal_iter->AddMerge("b", "merge_2");
2113
2114 internal_iter->AddDeletion("b");
2115 internal_iter->AddMerge("b", "merge_3");
2116
2117 internal_iter->AddMerge("c", "merge_4");
2118 internal_iter->AddMerge("c", "merge_5");
2119
2120 internal_iter->AddDeletion("b");
2121 internal_iter->AddMerge("b", "merge_6");
2122 internal_iter->AddMerge("b", "merge_7");
2123 internal_iter->AddMerge("b", "merge_8");
2124 internal_iter->AddMerge("b", "merge_9");
2125 internal_iter->AddMerge("b", "merge_10");
2126 internal_iter->AddMerge("b", "merge_11");
2127
2128 internal_iter->AddDeletion("c");
2129 internal_iter->Finish();
2130
2131 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2132 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
2133 internal_iter, 13, options.max_sequential_skip_in_iterations,
2134 nullptr /*read_callback*/));
2135 db_iter->SeekToLast();
2136 ASSERT_TRUE(db_iter->Valid());
2137
2138 ASSERT_EQ(db_iter->key().ToString(), "c");
2139 ASSERT_EQ(db_iter->value().ToString(), "merge_4,merge_5");
2140 db_iter->Prev();
2141 ASSERT_TRUE(db_iter->Valid());
2142
2143 ASSERT_TRUE(db_iter->Valid());
2144 ASSERT_EQ(db_iter->key().ToString(), "b");
2145 ASSERT_EQ(db_iter->value().ToString(),
2146 "merge_6,merge_7,merge_8,merge_9,merge_10,merge_11");
2147 db_iter->Prev();
2148 ASSERT_TRUE(db_iter->Valid());
2149
2150 ASSERT_EQ(db_iter->key().ToString(), "a");
2151 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
2152 db_iter->Prev();
2153 ASSERT_TRUE(!db_iter->Valid());
2154 }
2155
2156 {
2157 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2158 internal_iter->AddMerge("a", "merge_1");
2159 internal_iter->AddPut("b", "val");
2160 internal_iter->AddMerge("b", "merge_2");
2161
2162 internal_iter->AddDeletion("b");
2163 internal_iter->AddMerge("b", "merge_3");
2164
2165 internal_iter->AddMerge("c", "merge_4");
2166 internal_iter->AddMerge("c", "merge_5");
2167
2168 internal_iter->AddDeletion("b");
2169 internal_iter->AddMerge("b", "merge_6");
2170 internal_iter->AddMerge("b", "merge_7");
2171 internal_iter->AddMerge("b", "merge_8");
2172 internal_iter->AddMerge("b", "merge_9");
2173 internal_iter->AddMerge("b", "merge_10");
2174 internal_iter->AddMerge("b", "merge_11");
2175
2176 internal_iter->AddDeletion("c");
2177 internal_iter->Finish();
2178
2179 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2180 env_, ro, cf_options, mutable_cf_options, BytewiseComparator(),
2181 internal_iter, 14, options.max_sequential_skip_in_iterations,
2182 nullptr /*read_callback*/));
2183 db_iter->SeekToLast();
2184 ASSERT_TRUE(db_iter->Valid());
2185
2186 ASSERT_EQ(db_iter->key().ToString(), "b");
2187 ASSERT_EQ(db_iter->value().ToString(),
2188 "merge_6,merge_7,merge_8,merge_9,merge_10,merge_11");
2189 db_iter->Prev();
2190 ASSERT_TRUE(db_iter->Valid());
2191
2192 ASSERT_EQ(db_iter->key().ToString(), "a");
2193 ASSERT_EQ(db_iter->value().ToString(), "merge_1");
2194 db_iter->Prev();
2195 ASSERT_TRUE(!db_iter->Valid());
2196 }
2197 }
2198
2199 TEST_F(DBIteratorTest, DBIterator8) {
2200 ReadOptions ro;
2201 Options options;
2202 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
2203
2204 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2205 internal_iter->AddDeletion("a");
2206 internal_iter->AddPut("a", "0");
2207 internal_iter->AddPut("b", "0");
2208 internal_iter->Finish();
2209
2210 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2211 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2212 BytewiseComparator(), internal_iter, 10,
2213 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
2214 db_iter->SeekToLast();
2215 ASSERT_TRUE(db_iter->Valid());
2216 ASSERT_EQ(db_iter->key().ToString(), "b");
2217 ASSERT_EQ(db_iter->value().ToString(), "0");
2218
2219 db_iter->Prev();
2220 ASSERT_TRUE(db_iter->Valid());
2221 ASSERT_EQ(db_iter->key().ToString(), "a");
2222 ASSERT_EQ(db_iter->value().ToString(), "0");
2223 }
2224
2225 // TODO(3.13): fix the issue of Seek() then Prev() which might not necessary
2226 // return the biggest element smaller than the seek key.
2227 TEST_F(DBIteratorTest, DBIterator9) {
2228 ReadOptions ro;
2229 Options options;
2230 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
2231 {
2232 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2233 internal_iter->AddMerge("a", "merge_1");
2234 internal_iter->AddMerge("a", "merge_2");
2235 internal_iter->AddMerge("b", "merge_3");
2236 internal_iter->AddMerge("b", "merge_4");
2237 internal_iter->AddMerge("d", "merge_5");
2238 internal_iter->AddMerge("d", "merge_6");
2239 internal_iter->Finish();
2240
2241 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2242 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2243 BytewiseComparator(), internal_iter, 10,
2244 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
2245
2246 db_iter->SeekToLast();
2247 ASSERT_TRUE(db_iter->Valid());
2248 db_iter->Prev();
2249 ASSERT_TRUE(db_iter->Valid());
2250 ASSERT_EQ(db_iter->key().ToString(), "b");
2251 ASSERT_EQ(db_iter->value().ToString(), "merge_3,merge_4");
2252 db_iter->Next();
2253 ASSERT_TRUE(db_iter->Valid());
2254 ASSERT_EQ(db_iter->key().ToString(), "d");
2255 ASSERT_EQ(db_iter->value().ToString(), "merge_5,merge_6");
2256
2257 db_iter->Seek("b");
2258 ASSERT_TRUE(db_iter->Valid());
2259 ASSERT_EQ(db_iter->key().ToString(), "b");
2260 ASSERT_EQ(db_iter->value().ToString(), "merge_3,merge_4");
2261 db_iter->Prev();
2262 ASSERT_TRUE(db_iter->Valid());
2263 ASSERT_EQ(db_iter->key().ToString(), "a");
2264 ASSERT_EQ(db_iter->value().ToString(), "merge_1,merge_2");
2265
2266 db_iter->SeekForPrev("b");
2267 ASSERT_TRUE(db_iter->Valid());
2268 ASSERT_EQ(db_iter->key().ToString(), "b");
2269 ASSERT_EQ(db_iter->value().ToString(), "merge_3,merge_4");
2270 db_iter->Next();
2271 ASSERT_TRUE(db_iter->Valid());
2272 ASSERT_EQ(db_iter->key().ToString(), "d");
2273 ASSERT_EQ(db_iter->value().ToString(), "merge_5,merge_6");
2274
2275 db_iter->Seek("c");
2276 ASSERT_TRUE(db_iter->Valid());
2277 ASSERT_EQ(db_iter->key().ToString(), "d");
2278 ASSERT_EQ(db_iter->value().ToString(), "merge_5,merge_6");
2279 db_iter->Prev();
2280 ASSERT_TRUE(db_iter->Valid());
2281 ASSERT_EQ(db_iter->key().ToString(), "b");
2282 ASSERT_EQ(db_iter->value().ToString(), "merge_3,merge_4");
2283
2284 db_iter->SeekForPrev("c");
2285 ASSERT_TRUE(db_iter->Valid());
2286 ASSERT_EQ(db_iter->key().ToString(), "b");
2287 ASSERT_EQ(db_iter->value().ToString(), "merge_3,merge_4");
2288 db_iter->Next();
2289 ASSERT_TRUE(db_iter->Valid());
2290 ASSERT_EQ(db_iter->key().ToString(), "d");
2291 ASSERT_EQ(db_iter->value().ToString(), "merge_5,merge_6");
2292 }
2293 }
2294
2295 // TODO(3.13): fix the issue of Seek() then Prev() which might not necessary
2296 // return the biggest element smaller than the seek key.
2297 TEST_F(DBIteratorTest, DBIterator10) {
2298 ReadOptions ro;
2299 Options options;
2300
2301 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2302 internal_iter->AddPut("a", "1");
2303 internal_iter->AddPut("b", "2");
2304 internal_iter->AddPut("c", "3");
2305 internal_iter->AddPut("d", "4");
2306 internal_iter->Finish();
2307
2308 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2309 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2310 BytewiseComparator(), internal_iter, 10,
2311 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
2312
2313 db_iter->Seek("c");
2314 ASSERT_TRUE(db_iter->Valid());
2315 db_iter->Prev();
2316 ASSERT_TRUE(db_iter->Valid());
2317 ASSERT_EQ(db_iter->key().ToString(), "b");
2318 ASSERT_EQ(db_iter->value().ToString(), "2");
2319
2320 db_iter->Next();
2321 ASSERT_TRUE(db_iter->Valid());
2322 ASSERT_EQ(db_iter->key().ToString(), "c");
2323 ASSERT_EQ(db_iter->value().ToString(), "3");
2324
2325 db_iter->SeekForPrev("c");
2326 ASSERT_TRUE(db_iter->Valid());
2327 db_iter->Next();
2328 ASSERT_TRUE(db_iter->Valid());
2329 ASSERT_EQ(db_iter->key().ToString(), "d");
2330 ASSERT_EQ(db_iter->value().ToString(), "4");
2331
2332 db_iter->Prev();
2333 ASSERT_TRUE(db_iter->Valid());
2334 ASSERT_EQ(db_iter->key().ToString(), "c");
2335 ASSERT_EQ(db_iter->value().ToString(), "3");
2336 }
2337
2338 TEST_F(DBIteratorTest, SeekToLastOccurrenceSeq0) {
2339 ReadOptions ro;
2340 Options options;
2341 options.merge_operator = nullptr;
2342
2343 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2344 internal_iter->AddPut("a", "1");
2345 internal_iter->AddPut("b", "2");
2346 internal_iter->Finish();
2347
2348 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2349 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2350 BytewiseComparator(), internal_iter, 10, 0 /* force seek */,
2351 nullptr /*read_callback*/));
2352 db_iter->SeekToFirst();
2353 ASSERT_TRUE(db_iter->Valid());
2354 ASSERT_EQ(db_iter->key().ToString(), "a");
2355 ASSERT_EQ(db_iter->value().ToString(), "1");
2356 db_iter->Next();
2357 ASSERT_TRUE(db_iter->Valid());
2358 ASSERT_EQ(db_iter->key().ToString(), "b");
2359 ASSERT_EQ(db_iter->value().ToString(), "2");
2360 db_iter->Next();
2361 ASSERT_FALSE(db_iter->Valid());
2362 }
2363
2364 TEST_F(DBIteratorTest, DBIterator11) {
2365 ReadOptions ro;
2366 Options options;
2367 options.merge_operator = MergeOperators::CreateFromStringId("stringappend");
2368
2369 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2370 internal_iter->AddPut("a", "0");
2371 internal_iter->AddPut("b", "0");
2372 internal_iter->AddSingleDeletion("b");
2373 internal_iter->AddMerge("a", "1");
2374 internal_iter->AddMerge("b", "2");
2375 internal_iter->Finish();
2376
2377 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2378 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2379 BytewiseComparator(), internal_iter, 1,
2380 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
2381 db_iter->SeekToFirst();
2382 ASSERT_TRUE(db_iter->Valid());
2383 ASSERT_EQ(db_iter->key().ToString(), "a");
2384 ASSERT_EQ(db_iter->value().ToString(), "0");
2385 db_iter->Next();
2386 ASSERT_TRUE(db_iter->Valid());
2387 ASSERT_EQ(db_iter->key().ToString(), "b");
2388 db_iter->Next();
2389 ASSERT_FALSE(db_iter->Valid());
2390 }
2391
2392 TEST_F(DBIteratorTest, DBIterator12) {
2393 ReadOptions ro;
2394 Options options;
2395 options.merge_operator = nullptr;
2396
2397 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2398 internal_iter->AddPut("a", "1");
2399 internal_iter->AddPut("b", "2");
2400 internal_iter->AddPut("c", "3");
2401 internal_iter->AddSingleDeletion("b");
2402 internal_iter->Finish();
2403
2404 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2405 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2406 BytewiseComparator(), internal_iter, 10, 0, nullptr /*read_callback*/));
2407 db_iter->SeekToLast();
2408 ASSERT_TRUE(db_iter->Valid());
2409 ASSERT_EQ(db_iter->key().ToString(), "c");
2410 ASSERT_EQ(db_iter->value().ToString(), "3");
2411 db_iter->Prev();
2412 ASSERT_TRUE(db_iter->Valid());
2413 ASSERT_EQ(db_iter->key().ToString(), "a");
2414 ASSERT_EQ(db_iter->value().ToString(), "1");
2415 db_iter->Prev();
2416 ASSERT_FALSE(db_iter->Valid());
2417 }
2418
2419 TEST_F(DBIteratorTest, DBIterator13) {
2420 ReadOptions ro;
2421 Options options;
2422 options.merge_operator = nullptr;
2423
2424 std::string key;
2425 key.resize(9);
2426 key.assign(9, static_cast<char>(0));
2427 key[0] = 'b';
2428
2429 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2430 internal_iter->AddPut(key, "0");
2431 internal_iter->AddPut(key, "1");
2432 internal_iter->AddPut(key, "2");
2433 internal_iter->AddPut(key, "3");
2434 internal_iter->AddPut(key, "4");
2435 internal_iter->AddPut(key, "5");
2436 internal_iter->AddPut(key, "6");
2437 internal_iter->AddPut(key, "7");
2438 internal_iter->AddPut(key, "8");
2439 internal_iter->Finish();
2440
2441 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2442 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2443 BytewiseComparator(), internal_iter, 2, 3, nullptr /*read_callback*/));
2444 db_iter->Seek("b");
2445 ASSERT_TRUE(db_iter->Valid());
2446 ASSERT_EQ(db_iter->key().ToString(), key);
2447 ASSERT_EQ(db_iter->value().ToString(), "2");
2448 }
2449
2450 TEST_F(DBIteratorTest, DBIterator14) {
2451 ReadOptions ro;
2452 Options options;
2453 options.merge_operator = nullptr;
2454
2455 std::string key("b");
2456 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2457 internal_iter->AddPut("b", "0");
2458 internal_iter->AddPut("b", "1");
2459 internal_iter->AddPut("b", "2");
2460 internal_iter->AddPut("b", "3");
2461 internal_iter->AddPut("a", "4");
2462 internal_iter->AddPut("a", "5");
2463 internal_iter->AddPut("a", "6");
2464 internal_iter->AddPut("c", "7");
2465 internal_iter->AddPut("c", "8");
2466 internal_iter->AddPut("c", "9");
2467 internal_iter->Finish();
2468
2469 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2470 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2471 BytewiseComparator(), internal_iter, 4, 1, nullptr /*read_callback*/));
2472 db_iter->Seek("b");
2473 ASSERT_TRUE(db_iter->Valid());
2474 ASSERT_EQ(db_iter->key().ToString(), "b");
2475 ASSERT_EQ(db_iter->value().ToString(), "3");
2476 db_iter->SeekToFirst();
2477 ASSERT_EQ(db_iter->key().ToString(), "a");
2478 ASSERT_EQ(db_iter->value().ToString(), "4");
2479 }
2480
2481 TEST_F(DBIteratorTest, DBIteratorTestDifferentialSnapshots) {
2482 { // test that KVs earlier that iter_start_seqnum are filtered out
2483 ReadOptions ro;
2484 ro.iter_start_seqnum=5;
2485 Options options;
2486 options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
2487
2488 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2489 for (size_t i = 0; i < 10; ++i) {
2490 internal_iter->AddPut(std::to_string(i), std::to_string(i) + "a");
2491 internal_iter->AddPut(std::to_string(i), std::to_string(i) + "b");
2492 internal_iter->AddPut(std::to_string(i), std::to_string(i) + "c");
2493 }
2494 internal_iter->Finish();
2495
2496 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2497 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2498 BytewiseComparator(), internal_iter, 13,
2499 options.max_sequential_skip_in_iterations, nullptr));
2500 // Expecting InternalKeys in [5,8] range with correct type
2501 int seqnums[4] = {5,8,11,13};
2502 std::string user_keys[4] = {"1","2","3","4"};
2503 std::string values[4] = {"1c", "2c", "3c", "4b"};
2504 int i = 0;
2505 for (db_iter->SeekToFirst(); db_iter->Valid(); db_iter->Next()) {
2506 FullKey fkey;
2507 ParseFullKey(db_iter->key(), &fkey);
2508 ASSERT_EQ(user_keys[i], fkey.user_key.ToString());
2509 ASSERT_EQ(EntryType::kEntryPut, fkey.type);
2510 ASSERT_EQ(seqnums[i], fkey.sequence);
2511 ASSERT_EQ(values[i], db_iter->value().ToString());
2512 i++;
2513 }
2514 ASSERT_EQ(i, 4);
2515 }
2516
2517 { // Test that deletes are returned correctly as internal KVs
2518 ReadOptions ro;
2519 ro.iter_start_seqnum=5;
2520 Options options;
2521 options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
2522
2523 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
2524 for (size_t i = 0; i < 10; ++i) {
2525 internal_iter->AddPut(std::to_string(i), std::to_string(i) + "a");
2526 internal_iter->AddPut(std::to_string(i), std::to_string(i) + "b");
2527 internal_iter->AddDeletion(std::to_string(i));
2528 }
2529 internal_iter->Finish();
2530
2531 std::unique_ptr<Iterator> db_iter(NewDBIterator(
2532 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
2533 BytewiseComparator(), internal_iter, 13,
2534 options.max_sequential_skip_in_iterations, nullptr));
2535 // Expecting InternalKeys in [5,8] range with correct type
2536 int seqnums[4] = {5,8,11,13};
2537 EntryType key_types[4] = {EntryType::kEntryDelete,EntryType::kEntryDelete,
2538 EntryType::kEntryDelete,EntryType::kEntryPut};
2539 std::string user_keys[4] = {"1","2","3","4"};
2540 std::string values[4] = {"", "", "", "4b"};
2541 int i = 0;
2542 for (db_iter->SeekToFirst(); db_iter->Valid(); db_iter->Next()) {
2543 FullKey fkey;
2544 ParseFullKey(db_iter->key(), &fkey);
2545 ASSERT_EQ(user_keys[i], fkey.user_key.ToString());
2546 ASSERT_EQ(key_types[i], fkey.type);
2547 ASSERT_EQ(seqnums[i], fkey.sequence);
2548 ASSERT_EQ(values[i], db_iter->value().ToString());
2549 i++;
2550 }
2551 ASSERT_EQ(i, 4);
2552 }
2553 }
2554
2555 class DBIterWithMergeIterTest : public testing::Test {
2556 public:
2557 DBIterWithMergeIterTest()
2558 : env_(Env::Default()), icomp_(BytewiseComparator()) {
2559 options_.merge_operator = nullptr;
2560
2561 internal_iter1_ = new TestIterator(BytewiseComparator());
2562 internal_iter1_->Add("a", kTypeValue, "1", 3u);
2563 internal_iter1_->Add("f", kTypeValue, "2", 5u);
2564 internal_iter1_->Add("g", kTypeValue, "3", 7u);
2565 internal_iter1_->Finish();
2566
2567 internal_iter2_ = new TestIterator(BytewiseComparator());
2568 internal_iter2_->Add("a", kTypeValue, "4", 6u);
2569 internal_iter2_->Add("b", kTypeValue, "5", 1u);
2570 internal_iter2_->Add("c", kTypeValue, "6", 2u);
2571 internal_iter2_->Add("d", kTypeValue, "7", 3u);
2572 internal_iter2_->Finish();
2573
2574 std::vector<InternalIterator*> child_iters;
2575 child_iters.push_back(internal_iter1_);
2576 child_iters.push_back(internal_iter2_);
2577 InternalKeyComparator icomp(BytewiseComparator());
2578 InternalIterator* merge_iter =
2579 NewMergingIterator(&icomp_, &child_iters[0], 2u);
2580
2581 db_iter_.reset(NewDBIterator(
2582 env_, ro_, ImmutableCFOptions(options_), MutableCFOptions(options_),
2583 BytewiseComparator(), merge_iter,
2584 8 /* read data earlier than seqId 8 */,
2585 3 /* max iterators before reseek */, nullptr /*read_callback*/));
2586 }
2587
2588 Env* env_;
2589 ReadOptions ro_;
2590 Options options_;
2591 TestIterator* internal_iter1_;
2592 TestIterator* internal_iter2_;
2593 InternalKeyComparator icomp_;
2594 Iterator* merge_iter_;
2595 std::unique_ptr<Iterator> db_iter_;
2596 };
2597
2598 TEST_F(DBIterWithMergeIterTest, InnerMergeIterator1) {
2599 db_iter_->SeekToFirst();
2600 ASSERT_TRUE(db_iter_->Valid());
2601 ASSERT_EQ(db_iter_->key().ToString(), "a");
2602 ASSERT_EQ(db_iter_->value().ToString(), "4");
2603 db_iter_->Next();
2604 ASSERT_TRUE(db_iter_->Valid());
2605 ASSERT_EQ(db_iter_->key().ToString(), "b");
2606 ASSERT_EQ(db_iter_->value().ToString(), "5");
2607 db_iter_->Next();
2608 ASSERT_TRUE(db_iter_->Valid());
2609 ASSERT_EQ(db_iter_->key().ToString(), "c");
2610 ASSERT_EQ(db_iter_->value().ToString(), "6");
2611 db_iter_->Next();
2612 ASSERT_TRUE(db_iter_->Valid());
2613 ASSERT_EQ(db_iter_->key().ToString(), "d");
2614 ASSERT_EQ(db_iter_->value().ToString(), "7");
2615 db_iter_->Next();
2616 ASSERT_TRUE(db_iter_->Valid());
2617 ASSERT_EQ(db_iter_->key().ToString(), "f");
2618 ASSERT_EQ(db_iter_->value().ToString(), "2");
2619 db_iter_->Next();
2620 ASSERT_TRUE(db_iter_->Valid());
2621 ASSERT_EQ(db_iter_->key().ToString(), "g");
2622 ASSERT_EQ(db_iter_->value().ToString(), "3");
2623 db_iter_->Next();
2624 ASSERT_FALSE(db_iter_->Valid());
2625 }
2626
2627 TEST_F(DBIterWithMergeIterTest, InnerMergeIterator2) {
2628 // Test Prev() when one child iterator is at its end.
2629 db_iter_->SeekForPrev("g");
2630 ASSERT_TRUE(db_iter_->Valid());
2631 ASSERT_EQ(db_iter_->key().ToString(), "g");
2632 ASSERT_EQ(db_iter_->value().ToString(), "3");
2633 db_iter_->Prev();
2634 ASSERT_TRUE(db_iter_->Valid());
2635 ASSERT_EQ(db_iter_->key().ToString(), "f");
2636 ASSERT_EQ(db_iter_->value().ToString(), "2");
2637 db_iter_->Prev();
2638 ASSERT_TRUE(db_iter_->Valid());
2639 ASSERT_EQ(db_iter_->key().ToString(), "d");
2640 ASSERT_EQ(db_iter_->value().ToString(), "7");
2641 db_iter_->Prev();
2642 ASSERT_TRUE(db_iter_->Valid());
2643 ASSERT_EQ(db_iter_->key().ToString(), "c");
2644 ASSERT_EQ(db_iter_->value().ToString(), "6");
2645 db_iter_->Prev();
2646 ASSERT_TRUE(db_iter_->Valid());
2647 ASSERT_EQ(db_iter_->key().ToString(), "b");
2648 ASSERT_EQ(db_iter_->value().ToString(), "5");
2649 db_iter_->Prev();
2650 ASSERT_TRUE(db_iter_->Valid());
2651 ASSERT_EQ(db_iter_->key().ToString(), "a");
2652 ASSERT_EQ(db_iter_->value().ToString(), "4");
2653 }
2654
2655 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace1) {
2656 // Test Prev() when one child iterator is at its end but more rows
2657 // are added.
2658 db_iter_->Seek("f");
2659 ASSERT_TRUE(db_iter_->Valid());
2660 ASSERT_EQ(db_iter_->key().ToString(), "f");
2661 ASSERT_EQ(db_iter_->value().ToString(), "2");
2662
2663 // Test call back inserts a key in the end of the mem table after
2664 // MergeIterator::Prev() realized the mem table iterator is at its end
2665 // and before an SeekToLast() is called.
2666 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2667 "MergeIterator::Prev:BeforePrev",
2668 [&](void* /*arg*/) { internal_iter2_->Add("z", kTypeValue, "7", 12u); });
2669 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2670
2671 db_iter_->Prev();
2672 ASSERT_TRUE(db_iter_->Valid());
2673 ASSERT_EQ(db_iter_->key().ToString(), "d");
2674 ASSERT_EQ(db_iter_->value().ToString(), "7");
2675 db_iter_->Prev();
2676 ASSERT_TRUE(db_iter_->Valid());
2677 ASSERT_EQ(db_iter_->key().ToString(), "c");
2678 ASSERT_EQ(db_iter_->value().ToString(), "6");
2679 db_iter_->Prev();
2680 ASSERT_TRUE(db_iter_->Valid());
2681 ASSERT_EQ(db_iter_->key().ToString(), "b");
2682 ASSERT_EQ(db_iter_->value().ToString(), "5");
2683 db_iter_->Prev();
2684 ASSERT_TRUE(db_iter_->Valid());
2685 ASSERT_EQ(db_iter_->key().ToString(), "a");
2686 ASSERT_EQ(db_iter_->value().ToString(), "4");
2687
2688 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2689 }
2690
2691 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace2) {
2692 // Test Prev() when one child iterator is at its end but more rows
2693 // are added.
2694 db_iter_->Seek("f");
2695 ASSERT_TRUE(db_iter_->Valid());
2696 ASSERT_EQ(db_iter_->key().ToString(), "f");
2697 ASSERT_EQ(db_iter_->value().ToString(), "2");
2698
2699 // Test call back inserts entries for update a key in the end of the
2700 // mem table after MergeIterator::Prev() realized the mem tableiterator is at
2701 // its end and before an SeekToLast() is called.
2702 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2703 "MergeIterator::Prev:BeforePrev", [&](void* /*arg*/) {
2704 internal_iter2_->Add("z", kTypeValue, "7", 12u);
2705 internal_iter2_->Add("z", kTypeValue, "7", 11u);
2706 });
2707 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2708
2709 db_iter_->Prev();
2710 ASSERT_TRUE(db_iter_->Valid());
2711 ASSERT_EQ(db_iter_->key().ToString(), "d");
2712 ASSERT_EQ(db_iter_->value().ToString(), "7");
2713 db_iter_->Prev();
2714 ASSERT_TRUE(db_iter_->Valid());
2715 ASSERT_EQ(db_iter_->key().ToString(), "c");
2716 ASSERT_EQ(db_iter_->value().ToString(), "6");
2717 db_iter_->Prev();
2718 ASSERT_TRUE(db_iter_->Valid());
2719 ASSERT_EQ(db_iter_->key().ToString(), "b");
2720 ASSERT_EQ(db_iter_->value().ToString(), "5");
2721 db_iter_->Prev();
2722 ASSERT_TRUE(db_iter_->Valid());
2723 ASSERT_EQ(db_iter_->key().ToString(), "a");
2724 ASSERT_EQ(db_iter_->value().ToString(), "4");
2725
2726 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2727 }
2728
2729 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace3) {
2730 // Test Prev() when one child iterator is at its end but more rows
2731 // are added and max_skipped is triggered.
2732 db_iter_->Seek("f");
2733 ASSERT_TRUE(db_iter_->Valid());
2734 ASSERT_EQ(db_iter_->key().ToString(), "f");
2735 ASSERT_EQ(db_iter_->value().ToString(), "2");
2736
2737 // Test call back inserts entries for update a key in the end of the
2738 // mem table after MergeIterator::Prev() realized the mem table iterator is at
2739 // its end and before an SeekToLast() is called.
2740 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2741 "MergeIterator::Prev:BeforePrev", [&](void* /*arg*/) {
2742 internal_iter2_->Add("z", kTypeValue, "7", 16u, true);
2743 internal_iter2_->Add("z", kTypeValue, "7", 15u, true);
2744 internal_iter2_->Add("z", kTypeValue, "7", 14u, true);
2745 internal_iter2_->Add("z", kTypeValue, "7", 13u, true);
2746 internal_iter2_->Add("z", kTypeValue, "7", 12u, true);
2747 internal_iter2_->Add("z", kTypeValue, "7", 11u, true);
2748 });
2749 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2750
2751 db_iter_->Prev();
2752 ASSERT_TRUE(db_iter_->Valid());
2753 ASSERT_EQ(db_iter_->key().ToString(), "d");
2754 ASSERT_EQ(db_iter_->value().ToString(), "7");
2755 db_iter_->Prev();
2756 ASSERT_TRUE(db_iter_->Valid());
2757 ASSERT_EQ(db_iter_->key().ToString(), "c");
2758 ASSERT_EQ(db_iter_->value().ToString(), "6");
2759 db_iter_->Prev();
2760 ASSERT_TRUE(db_iter_->Valid());
2761 ASSERT_EQ(db_iter_->key().ToString(), "b");
2762 ASSERT_EQ(db_iter_->value().ToString(), "5");
2763 db_iter_->Prev();
2764 ASSERT_TRUE(db_iter_->Valid());
2765 ASSERT_EQ(db_iter_->key().ToString(), "a");
2766 ASSERT_EQ(db_iter_->value().ToString(), "4");
2767
2768 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2769 }
2770
2771 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace4) {
2772 // Test Prev() when one child iterator has more rows inserted
2773 // between Seek() and Prev() when changing directions.
2774 internal_iter2_->Add("z", kTypeValue, "9", 4u);
2775
2776 db_iter_->Seek("g");
2777 ASSERT_TRUE(db_iter_->Valid());
2778 ASSERT_EQ(db_iter_->key().ToString(), "g");
2779 ASSERT_EQ(db_iter_->value().ToString(), "3");
2780
2781 // Test call back inserts entries for update a key before "z" in
2782 // mem table after MergeIterator::Prev() calls mem table iterator's
2783 // Seek() and before calling Prev()
2784 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2785 "MergeIterator::Prev:BeforePrev", [&](void* arg) {
2786 IteratorWrapper* it = reinterpret_cast<IteratorWrapper*>(arg);
2787 if (it->key().starts_with("z")) {
2788 internal_iter2_->Add("x", kTypeValue, "7", 16u, true);
2789 internal_iter2_->Add("x", kTypeValue, "7", 15u, true);
2790 internal_iter2_->Add("x", kTypeValue, "7", 14u, true);
2791 internal_iter2_->Add("x", kTypeValue, "7", 13u, true);
2792 internal_iter2_->Add("x", kTypeValue, "7", 12u, true);
2793 internal_iter2_->Add("x", kTypeValue, "7", 11u, true);
2794 }
2795 });
2796 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2797
2798 db_iter_->Prev();
2799 ASSERT_TRUE(db_iter_->Valid());
2800 ASSERT_EQ(db_iter_->key().ToString(), "f");
2801 ASSERT_EQ(db_iter_->value().ToString(), "2");
2802 db_iter_->Prev();
2803 ASSERT_TRUE(db_iter_->Valid());
2804 ASSERT_EQ(db_iter_->key().ToString(), "d");
2805 ASSERT_EQ(db_iter_->value().ToString(), "7");
2806 db_iter_->Prev();
2807 ASSERT_TRUE(db_iter_->Valid());
2808 ASSERT_EQ(db_iter_->key().ToString(), "c");
2809 ASSERT_EQ(db_iter_->value().ToString(), "6");
2810 db_iter_->Prev();
2811 ASSERT_TRUE(db_iter_->Valid());
2812 ASSERT_EQ(db_iter_->key().ToString(), "b");
2813 ASSERT_EQ(db_iter_->value().ToString(), "5");
2814 db_iter_->Prev();
2815 ASSERT_TRUE(db_iter_->Valid());
2816 ASSERT_EQ(db_iter_->key().ToString(), "a");
2817 ASSERT_EQ(db_iter_->value().ToString(), "4");
2818
2819 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2820 }
2821
2822 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace5) {
2823 internal_iter2_->Add("z", kTypeValue, "9", 4u);
2824
2825 // Test Prev() when one child iterator has more rows inserted
2826 // between Seek() and Prev() when changing directions.
2827 db_iter_->Seek("g");
2828 ASSERT_TRUE(db_iter_->Valid());
2829 ASSERT_EQ(db_iter_->key().ToString(), "g");
2830 ASSERT_EQ(db_iter_->value().ToString(), "3");
2831
2832 // Test call back inserts entries for update a key before "z" in
2833 // mem table after MergeIterator::Prev() calls mem table iterator's
2834 // Seek() and before calling Prev()
2835 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2836 "MergeIterator::Prev:BeforePrev", [&](void* arg) {
2837 IteratorWrapper* it = reinterpret_cast<IteratorWrapper*>(arg);
2838 if (it->key().starts_with("z")) {
2839 internal_iter2_->Add("x", kTypeValue, "7", 16u, true);
2840 internal_iter2_->Add("x", kTypeValue, "7", 15u, true);
2841 }
2842 });
2843 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2844
2845 db_iter_->Prev();
2846 ASSERT_TRUE(db_iter_->Valid());
2847 ASSERT_EQ(db_iter_->key().ToString(), "f");
2848 ASSERT_EQ(db_iter_->value().ToString(), "2");
2849 db_iter_->Prev();
2850 ASSERT_TRUE(db_iter_->Valid());
2851 ASSERT_EQ(db_iter_->key().ToString(), "d");
2852 ASSERT_EQ(db_iter_->value().ToString(), "7");
2853 db_iter_->Prev();
2854 ASSERT_TRUE(db_iter_->Valid());
2855 ASSERT_EQ(db_iter_->key().ToString(), "c");
2856 ASSERT_EQ(db_iter_->value().ToString(), "6");
2857 db_iter_->Prev();
2858 ASSERT_TRUE(db_iter_->Valid());
2859 ASSERT_EQ(db_iter_->key().ToString(), "b");
2860 ASSERT_EQ(db_iter_->value().ToString(), "5");
2861 db_iter_->Prev();
2862 ASSERT_TRUE(db_iter_->Valid());
2863 ASSERT_EQ(db_iter_->key().ToString(), "a");
2864 ASSERT_EQ(db_iter_->value().ToString(), "4");
2865
2866 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2867 }
2868
2869 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace6) {
2870 internal_iter2_->Add("z", kTypeValue, "9", 4u);
2871
2872 // Test Prev() when one child iterator has more rows inserted
2873 // between Seek() and Prev() when changing directions.
2874 db_iter_->Seek("g");
2875 ASSERT_TRUE(db_iter_->Valid());
2876 ASSERT_EQ(db_iter_->key().ToString(), "g");
2877 ASSERT_EQ(db_iter_->value().ToString(), "3");
2878
2879 // Test call back inserts an entry for update a key before "z" in
2880 // mem table after MergeIterator::Prev() calls mem table iterator's
2881 // Seek() and before calling Prev()
2882 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2883 "MergeIterator::Prev:BeforePrev", [&](void* arg) {
2884 IteratorWrapper* it = reinterpret_cast<IteratorWrapper*>(arg);
2885 if (it->key().starts_with("z")) {
2886 internal_iter2_->Add("x", kTypeValue, "7", 16u, true);
2887 }
2888 });
2889 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2890
2891 db_iter_->Prev();
2892 ASSERT_TRUE(db_iter_->Valid());
2893 ASSERT_EQ(db_iter_->key().ToString(), "f");
2894 ASSERT_EQ(db_iter_->value().ToString(), "2");
2895 db_iter_->Prev();
2896 ASSERT_TRUE(db_iter_->Valid());
2897 ASSERT_EQ(db_iter_->key().ToString(), "d");
2898 ASSERT_EQ(db_iter_->value().ToString(), "7");
2899 db_iter_->Prev();
2900 ASSERT_TRUE(db_iter_->Valid());
2901 ASSERT_EQ(db_iter_->key().ToString(), "c");
2902 ASSERT_EQ(db_iter_->value().ToString(), "6");
2903 db_iter_->Prev();
2904 ASSERT_TRUE(db_iter_->Valid());
2905 ASSERT_EQ(db_iter_->key().ToString(), "b");
2906 ASSERT_EQ(db_iter_->value().ToString(), "5");
2907 db_iter_->Prev();
2908 ASSERT_TRUE(db_iter_->Valid());
2909 ASSERT_EQ(db_iter_->key().ToString(), "a");
2910 ASSERT_EQ(db_iter_->value().ToString(), "4");
2911
2912 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2913 }
2914
2915 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace7) {
2916 internal_iter1_->Add("u", kTypeValue, "10", 4u);
2917 internal_iter1_->Add("v", kTypeValue, "11", 4u);
2918 internal_iter1_->Add("w", kTypeValue, "12", 4u);
2919 internal_iter2_->Add("z", kTypeValue, "9", 4u);
2920
2921 // Test Prev() when one child iterator has more rows inserted
2922 // between Seek() and Prev() when changing directions.
2923 db_iter_->Seek("g");
2924 ASSERT_TRUE(db_iter_->Valid());
2925 ASSERT_EQ(db_iter_->key().ToString(), "g");
2926 ASSERT_EQ(db_iter_->value().ToString(), "3");
2927
2928 // Test call back inserts entries for update a key before "z" in
2929 // mem table after MergeIterator::Prev() calls mem table iterator's
2930 // Seek() and before calling Prev()
2931 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2932 "MergeIterator::Prev:BeforePrev", [&](void* arg) {
2933 IteratorWrapper* it = reinterpret_cast<IteratorWrapper*>(arg);
2934 if (it->key().starts_with("z")) {
2935 internal_iter2_->Add("x", kTypeValue, "7", 16u, true);
2936 internal_iter2_->Add("x", kTypeValue, "7", 15u, true);
2937 internal_iter2_->Add("x", kTypeValue, "7", 14u, true);
2938 internal_iter2_->Add("x", kTypeValue, "7", 13u, true);
2939 internal_iter2_->Add("x", kTypeValue, "7", 12u, true);
2940 internal_iter2_->Add("x", kTypeValue, "7", 11u, true);
2941 }
2942 });
2943 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2944
2945 db_iter_->Prev();
2946 ASSERT_TRUE(db_iter_->Valid());
2947 ASSERT_EQ(db_iter_->key().ToString(), "f");
2948 ASSERT_EQ(db_iter_->value().ToString(), "2");
2949 db_iter_->Prev();
2950 ASSERT_TRUE(db_iter_->Valid());
2951 ASSERT_EQ(db_iter_->key().ToString(), "d");
2952 ASSERT_EQ(db_iter_->value().ToString(), "7");
2953 db_iter_->Prev();
2954 ASSERT_TRUE(db_iter_->Valid());
2955 ASSERT_EQ(db_iter_->key().ToString(), "c");
2956 ASSERT_EQ(db_iter_->value().ToString(), "6");
2957 db_iter_->Prev();
2958 ASSERT_TRUE(db_iter_->Valid());
2959 ASSERT_EQ(db_iter_->key().ToString(), "b");
2960 ASSERT_EQ(db_iter_->value().ToString(), "5");
2961 db_iter_->Prev();
2962 ASSERT_TRUE(db_iter_->Valid());
2963 ASSERT_EQ(db_iter_->key().ToString(), "a");
2964 ASSERT_EQ(db_iter_->value().ToString(), "4");
2965
2966 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
2967 }
2968
2969 TEST_F(DBIterWithMergeIterTest, InnerMergeIteratorDataRace8) {
2970 // internal_iter1_: a, f, g
2971 // internal_iter2_: a, b, c, d, adding (z)
2972 internal_iter2_->Add("z", kTypeValue, "9", 4u);
2973
2974 // Test Prev() when one child iterator has more rows inserted
2975 // between Seek() and Prev() when changing directions.
2976 db_iter_->Seek("g");
2977 ASSERT_TRUE(db_iter_->Valid());
2978 ASSERT_EQ(db_iter_->key().ToString(), "g");
2979 ASSERT_EQ(db_iter_->value().ToString(), "3");
2980
2981 // Test call back inserts two keys before "z" in mem table after
2982 // MergeIterator::Prev() calls mem table iterator's Seek() and
2983 // before calling Prev()
2984 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
2985 "MergeIterator::Prev:BeforePrev", [&](void* arg) {
2986 IteratorWrapper* it = reinterpret_cast<IteratorWrapper*>(arg);
2987 if (it->key().starts_with("z")) {
2988 internal_iter2_->Add("x", kTypeValue, "7", 16u, true);
2989 internal_iter2_->Add("y", kTypeValue, "7", 17u, true);
2990 }
2991 });
2992 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
2993
2994 db_iter_->Prev();
2995 ASSERT_TRUE(db_iter_->Valid());
2996 ASSERT_EQ(db_iter_->key().ToString(), "f");
2997 ASSERT_EQ(db_iter_->value().ToString(), "2");
2998 db_iter_->Prev();
2999 ASSERT_TRUE(db_iter_->Valid());
3000 ASSERT_EQ(db_iter_->key().ToString(), "d");
3001 ASSERT_EQ(db_iter_->value().ToString(), "7");
3002
3003 ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
3004 }
3005
3006
3007 TEST_F(DBIteratorTest, SeekPrefixTombstones) {
3008 ReadOptions ro;
3009 Options options;
3010 options.prefix_extractor.reset(NewNoopTransform());
3011 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
3012 internal_iter->AddDeletion("b");
3013 internal_iter->AddDeletion("c");
3014 internal_iter->AddDeletion("d");
3015 internal_iter->AddDeletion("e");
3016 internal_iter->AddDeletion("f");
3017 internal_iter->AddDeletion("g");
3018 internal_iter->Finish();
3019
3020 ro.prefix_same_as_start = true;
3021 std::unique_ptr<Iterator> db_iter(NewDBIterator(
3022 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
3023 BytewiseComparator(), internal_iter, 10,
3024 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
3025
3026 int skipped_keys = 0;
3027
3028 get_perf_context()->Reset();
3029 db_iter->SeekForPrev("z");
3030 skipped_keys =
3031 static_cast<int>(get_perf_context()->internal_key_skipped_count);
3032 ASSERT_EQ(skipped_keys, 0);
3033
3034 get_perf_context()->Reset();
3035 db_iter->Seek("a");
3036 skipped_keys =
3037 static_cast<int>(get_perf_context()->internal_key_skipped_count);
3038 ASSERT_EQ(skipped_keys, 0);
3039 }
3040
3041 TEST_F(DBIteratorTest, SeekToFirstLowerBound) {
3042 const int kNumKeys = 3;
3043 for (int i = 0; i < kNumKeys + 2; ++i) {
3044 // + 2 for two special cases: lower bound before and lower bound after the
3045 // internal iterator's keys
3046 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
3047 for (int j = 1; j <= kNumKeys; ++j) {
3048 internal_iter->AddPut(std::to_string(j), "val");
3049 }
3050 internal_iter->Finish();
3051
3052 ReadOptions ro;
3053 auto lower_bound_str = std::to_string(i);
3054 Slice lower_bound(lower_bound_str);
3055 ro.iterate_lower_bound = &lower_bound;
3056 Options options;
3057 std::unique_ptr<Iterator> db_iter(NewDBIterator(
3058 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
3059 BytewiseComparator(), internal_iter, 10 /* sequence */,
3060 options.max_sequential_skip_in_iterations,
3061 nullptr /* read_callback */));
3062
3063 db_iter->SeekToFirst();
3064 if (i == kNumKeys + 1) {
3065 // lower bound was beyond the last key
3066 ASSERT_FALSE(db_iter->Valid());
3067 } else {
3068 ASSERT_TRUE(db_iter->Valid());
3069 int expected;
3070 if (i == 0) {
3071 // lower bound was before the first key
3072 expected = 1;
3073 } else {
3074 // lower bound was at the ith key
3075 expected = i;
3076 }
3077 ASSERT_EQ(std::to_string(expected), db_iter->key().ToString());
3078 }
3079 }
3080 }
3081
3082 TEST_F(DBIteratorTest, PrevLowerBound) {
3083 const int kNumKeys = 3;
3084 const int kLowerBound = 2;
3085 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
3086 for (int j = 1; j <= kNumKeys; ++j) {
3087 internal_iter->AddPut(std::to_string(j), "val");
3088 }
3089 internal_iter->Finish();
3090
3091 ReadOptions ro;
3092 auto lower_bound_str = std::to_string(kLowerBound);
3093 Slice lower_bound(lower_bound_str);
3094 ro.iterate_lower_bound = &lower_bound;
3095 Options options;
3096 std::unique_ptr<Iterator> db_iter(NewDBIterator(
3097 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
3098 BytewiseComparator(), internal_iter, 10 /* sequence */,
3099 options.max_sequential_skip_in_iterations, nullptr /* read_callback */));
3100
3101 db_iter->SeekToLast();
3102 for (int i = kNumKeys; i >= kLowerBound; --i) {
3103 ASSERT_TRUE(db_iter->Valid());
3104 ASSERT_EQ(std::to_string(i), db_iter->key().ToString());
3105 db_iter->Prev();
3106 }
3107 ASSERT_FALSE(db_iter->Valid());
3108 }
3109
3110 TEST_F(DBIteratorTest, SeekLessLowerBound) {
3111 const int kNumKeys = 3;
3112 const int kLowerBound = 2;
3113 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
3114 for (int j = 1; j <= kNumKeys; ++j) {
3115 internal_iter->AddPut(std::to_string(j), "val");
3116 }
3117 internal_iter->Finish();
3118
3119 ReadOptions ro;
3120 auto lower_bound_str = std::to_string(kLowerBound);
3121 Slice lower_bound(lower_bound_str);
3122 ro.iterate_lower_bound = &lower_bound;
3123 Options options;
3124 std::unique_ptr<Iterator> db_iter(NewDBIterator(
3125 env_, ro, ImmutableCFOptions(options), MutableCFOptions(options),
3126 BytewiseComparator(), internal_iter, 10 /* sequence */,
3127 options.max_sequential_skip_in_iterations, nullptr /* read_callback */));
3128
3129 auto before_lower_bound_str = std::to_string(kLowerBound - 1);
3130 Slice before_lower_bound(lower_bound_str);
3131
3132 db_iter->Seek(before_lower_bound);
3133 ASSERT_TRUE(db_iter->Valid());
3134 ASSERT_EQ(lower_bound_str, db_iter->key().ToString());
3135 }
3136
3137 TEST_F(DBIteratorTest, ReverseToForwardWithDisappearingKeys) {
3138 Options options;
3139 options.prefix_extractor.reset(NewCappedPrefixTransform(0));
3140
3141 TestIterator* internal_iter = new TestIterator(BytewiseComparator());
3142 internal_iter->AddPut("a", "A");
3143 internal_iter->AddPut("b", "B");
3144 for (int i = 0; i < 100; ++i) {
3145 internal_iter->AddPut("c" + ToString(i), "");
3146 }
3147 internal_iter->Finish();
3148
3149 std::unique_ptr<Iterator> db_iter(NewDBIterator(
3150 env_, ReadOptions(), ImmutableCFOptions(options),
3151 MutableCFOptions(options), BytewiseComparator(), internal_iter, 10,
3152 options.max_sequential_skip_in_iterations, nullptr /*read_callback*/));
3153
3154 db_iter->SeekForPrev("a");
3155 ASSERT_TRUE(db_iter->Valid());
3156 ASSERT_OK(db_iter->status());
3157 ASSERT_EQ("a", db_iter->key().ToString());
3158
3159 internal_iter->Vanish("a");
3160 db_iter->Next();
3161 ASSERT_TRUE(db_iter->Valid());
3162 ASSERT_OK(db_iter->status());
3163 ASSERT_EQ("b", db_iter->key().ToString());
3164
3165 // A (sort of) bug used to cause DBIter to pointlessly drag the internal
3166 // iterator all the way to the end. But this doesn't really matter at the time
3167 // of writing because the only iterator that can see disappearing keys is
3168 // ForwardIterator, which doesn't support SeekForPrev().
3169 EXPECT_LT(internal_iter->steps(), 20);
3170 }
3171
3172 } // namespace ROCKSDB_NAMESPACE
3173
3174 int main(int argc, char** argv) {
3175 ::testing::InitGoogleTest(&argc, argv);
3176 return RUN_ALL_TESTS();
3177 }
Ceph