1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10 #include "table/two_level_iterator.h"
11 #include "db/pinned_iterators_manager.h"
12 #include "memory/arena.h"
13 #include "rocksdb/options.h"
14 #include "rocksdb/table.h"
15 #include "table/block_based/block.h"
16 #include "table/format.h"
17
18 namespace ROCKSDB_NAMESPACE {
19
20 namespace {
21
22 class TwoLevelIndexIterator : public InternalIteratorBase<IndexValue> {
23 public:
24 explicit TwoLevelIndexIterator(
25 TwoLevelIteratorState* state,
26 InternalIteratorBase<IndexValue>* first_level_iter);
27
~TwoLevelIndexIterator()28 ~TwoLevelIndexIterator() override {
29 first_level_iter_.DeleteIter(false /* is_arena_mode */);
30 second_level_iter_.DeleteIter(false /* is_arena_mode */);
31 delete state_;
32 }
33
34 void Seek(const Slice& target) override;
35 void SeekForPrev(const Slice& target) override;
36 void SeekToFirst() override;
37 void SeekToLast() override;
38 void Next() override;
39 void Prev() override;
40
Valid() const41 bool Valid() const override { return second_level_iter_.Valid(); }
key() const42 Slice key() const override {
43 assert(Valid());
44 return second_level_iter_.key();
45 }
value() const46 IndexValue value() const override {
47 assert(Valid());
48 return second_level_iter_.value();
49 }
status() const50 Status status() const override {
51 if (!first_level_iter_.status().ok()) {
52 assert(second_level_iter_.iter() == nullptr);
53 return first_level_iter_.status();
54 } else if (second_level_iter_.iter() != nullptr &&
55 !second_level_iter_.status().ok()) {
56 return second_level_iter_.status();
57 } else {
58 return status_;
59 }
60 }
SetPinnedItersMgr(PinnedIteratorsManager *)61 void SetPinnedItersMgr(
62 PinnedIteratorsManager* /*pinned_iters_mgr*/) override {}
IsKeyPinned() const63 bool IsKeyPinned() const override { return false; }
IsValuePinned() const64 bool IsValuePinned() const override { return false; }
65
66 private:
SaveError(const Status & s)67 void SaveError(const Status& s) {
68 if (status_.ok() && !s.ok()) status_ = s;
69 }
70 void SkipEmptyDataBlocksForward();
71 void SkipEmptyDataBlocksBackward();
72 void SetSecondLevelIterator(InternalIteratorBase<IndexValue>* iter);
73 void InitDataBlock();
74
75 TwoLevelIteratorState* state_;
76 IteratorWrapperBase<IndexValue> first_level_iter_;
77 IteratorWrapperBase<IndexValue> second_level_iter_; // May be nullptr
78 Status status_;
79 // If second_level_iter is non-nullptr, then "data_block_handle_" holds the
80 // "index_value" passed to block_function_ to create the second_level_iter.
81 BlockHandle data_block_handle_;
82 };
83
TwoLevelIndexIterator(TwoLevelIteratorState * state,InternalIteratorBase<IndexValue> * first_level_iter)84 TwoLevelIndexIterator::TwoLevelIndexIterator(
85 TwoLevelIteratorState* state,
86 InternalIteratorBase<IndexValue>* first_level_iter)
87 : state_(state), first_level_iter_(first_level_iter) {}
88
Seek(const Slice & target)89 void TwoLevelIndexIterator::Seek(const Slice& target) {
90 first_level_iter_.Seek(target);
91
92 InitDataBlock();
93 if (second_level_iter_.iter() != nullptr) {
94 second_level_iter_.Seek(target);
95 }
96 SkipEmptyDataBlocksForward();
97 }
98
SeekForPrev(const Slice & target)99 void TwoLevelIndexIterator::SeekForPrev(const Slice& target) {
100 first_level_iter_.Seek(target);
101 InitDataBlock();
102 if (second_level_iter_.iter() != nullptr) {
103 second_level_iter_.SeekForPrev(target);
104 }
105 if (!Valid()) {
106 if (!first_level_iter_.Valid() && first_level_iter_.status().ok()) {
107 first_level_iter_.SeekToLast();
108 InitDataBlock();
109 if (second_level_iter_.iter() != nullptr) {
110 second_level_iter_.SeekForPrev(target);
111 }
112 }
113 SkipEmptyDataBlocksBackward();
114 }
115 }
116
SeekToFirst()117 void TwoLevelIndexIterator::SeekToFirst() {
118 first_level_iter_.SeekToFirst();
119 InitDataBlock();
120 if (second_level_iter_.iter() != nullptr) {
121 second_level_iter_.SeekToFirst();
122 }
123 SkipEmptyDataBlocksForward();
124 }
125
SeekToLast()126 void TwoLevelIndexIterator::SeekToLast() {
127 first_level_iter_.SeekToLast();
128 InitDataBlock();
129 if (second_level_iter_.iter() != nullptr) {
130 second_level_iter_.SeekToLast();
131 }
132 SkipEmptyDataBlocksBackward();
133 }
134
Next()135 void TwoLevelIndexIterator::Next() {
136 assert(Valid());
137 second_level_iter_.Next();
138 SkipEmptyDataBlocksForward();
139 }
140
Prev()141 void TwoLevelIndexIterator::Prev() {
142 assert(Valid());
143 second_level_iter_.Prev();
144 SkipEmptyDataBlocksBackward();
145 }
146
SkipEmptyDataBlocksForward()147 void TwoLevelIndexIterator::SkipEmptyDataBlocksForward() {
148 while (second_level_iter_.iter() == nullptr ||
149 (!second_level_iter_.Valid() && second_level_iter_.status().ok())) {
150 // Move to next block
151 if (!first_level_iter_.Valid()) {
152 SetSecondLevelIterator(nullptr);
153 return;
154 }
155 first_level_iter_.Next();
156 InitDataBlock();
157 if (second_level_iter_.iter() != nullptr) {
158 second_level_iter_.SeekToFirst();
159 }
160 }
161 }
162
SkipEmptyDataBlocksBackward()163 void TwoLevelIndexIterator::SkipEmptyDataBlocksBackward() {
164 while (second_level_iter_.iter() == nullptr ||
165 (!second_level_iter_.Valid() && second_level_iter_.status().ok())) {
166 // Move to next block
167 if (!first_level_iter_.Valid()) {
168 SetSecondLevelIterator(nullptr);
169 return;
170 }
171 first_level_iter_.Prev();
172 InitDataBlock();
173 if (second_level_iter_.iter() != nullptr) {
174 second_level_iter_.SeekToLast();
175 }
176 }
177 }
178
SetSecondLevelIterator(InternalIteratorBase<IndexValue> * iter)179 void TwoLevelIndexIterator::SetSecondLevelIterator(
180 InternalIteratorBase<IndexValue>* iter) {
181 InternalIteratorBase<IndexValue>* old_iter = second_level_iter_.Set(iter);
182 delete old_iter;
183 }
184
InitDataBlock()185 void TwoLevelIndexIterator::InitDataBlock() {
186 if (!first_level_iter_.Valid()) {
187 SetSecondLevelIterator(nullptr);
188 } else {
189 BlockHandle handle = first_level_iter_.value().handle;
190 if (second_level_iter_.iter() != nullptr &&
191 !second_level_iter_.status().IsIncomplete() &&
192 handle.offset() == data_block_handle_.offset()) {
193 // second_level_iter is already constructed with this iterator, so
194 // no need to change anything
195 } else {
196 InternalIteratorBase<IndexValue>* iter =
197 state_->NewSecondaryIterator(handle);
198 data_block_handle_ = handle;
199 SetSecondLevelIterator(iter);
200 }
201 }
202 }
203
204 } // namespace
205
NewTwoLevelIterator(TwoLevelIteratorState * state,InternalIteratorBase<IndexValue> * first_level_iter)206 InternalIteratorBase<IndexValue>* NewTwoLevelIterator(
207 TwoLevelIteratorState* state,
208 InternalIteratorBase<IndexValue>* first_level_iter) {
209 return new TwoLevelIndexIterator(state, first_level_iter);
210 }
211 } // namespace ROCKSDB_NAMESPACE
212