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