]> git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/db/db_iter_test.cc
projects / ceph.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
import 14.2.4 nautilus point release
[ceph.git] / ceph / src / rocksdb / db / db_iter_test.cc
1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5
6 #include <string>
7 #include <vector>
8 #include <algorithm>
9 #include <utility>
10
11 #include "db/db_iter.h"
12 #include "db/dbformat.h"
13 #include "rocksdb/comparator.h"
14 #include "rocksdb/options.h"
15 #include "rocksdb/perf_context.h"
16 #include "rocksdb/slice.h"
17 #include "rocksdb/statistics.h"
18 #include "table/iterator_wrapper.h"
19 #include "table/merging_iterator.h"
20 #include "util/string_util.h"
21 #include "util/sync_point.h"
22 #include "util/testharness.h"
23 #include "utilities/merge_operators.h"
24
25 namespace rocksdb {
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::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::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::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::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::SyncPoint::GetInstance()->SetCallBack(
2665 "MergeIterator::Prev:BeforePrev",
2666 [&](void* /*arg*/) { internal_iter2_->Add("z", kTypeValue, "7", 12u); });
2667 rocksdb::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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::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
3171
3172 int main(int argc, char** argv) {
3173 ::testing::InitGoogleTest(&argc, argv);
3174 return RUN_ALL_TESTS();
3175 }
Ceph