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