]>
Commit | Line | Data |
---|---|---|
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 FG |
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 "rocksdb/options.h" | |
13 | #include "rocksdb/table.h" | |
14 | #include "table/block.h" | |
15 | #include "table/format.h" | |
16 | #include "util/arena.h" | |
17 | ||
18 | namespace rocksdb { | |
19 | ||
20 | namespace { | |
21 | ||
11fdf7f2 | 22 | class TwoLevelIndexIterator : public InternalIteratorBase<BlockHandle> { |
7c673cae | 23 | public: |
11fdf7f2 TL |
24 | explicit TwoLevelIndexIterator( |
25 | TwoLevelIteratorState* state, | |
26 | InternalIteratorBase<BlockHandle>* first_level_iter); | |
7c673cae | 27 | |
494da23a | 28 | ~TwoLevelIndexIterator() override { |
11fdf7f2 TL |
29 | first_level_iter_.DeleteIter(false /* is_arena_mode */); |
30 | second_level_iter_.DeleteIter(false /* is_arena_mode */); | |
31 | delete state_; | |
7c673cae FG |
32 | } |
33 | ||
494da23a TL |
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; | |
7c673cae | 40 | |
494da23a TL |
41 | bool Valid() const override { return second_level_iter_.Valid(); } |
42 | Slice key() const override { | |
7c673cae FG |
43 | assert(Valid()); |
44 | return second_level_iter_.key(); | |
45 | } | |
494da23a | 46 | BlockHandle value() const override { |
7c673cae FG |
47 | assert(Valid()); |
48 | return second_level_iter_.value(); | |
49 | } | |
494da23a | 50 | Status status() const override { |
7c673cae | 51 | if (!first_level_iter_.status().ok()) { |
11fdf7f2 | 52 | assert(second_level_iter_.iter() == nullptr); |
7c673cae FG |
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 | } | |
494da23a | 61 | void SetPinnedItersMgr( |
11fdf7f2 | 62 | PinnedIteratorsManager* /*pinned_iters_mgr*/) override {} |
494da23a TL |
63 | bool IsKeyPinned() const override { return false; } |
64 | bool IsValuePinned() const override { return false; } | |
7c673cae FG |
65 | |
66 | private: | |
67 | void SaveError(const Status& s) { | |
68 | if (status_.ok() && !s.ok()) status_ = s; | |
69 | } | |
70 | void SkipEmptyDataBlocksForward(); | |
71 | void SkipEmptyDataBlocksBackward(); | |
11fdf7f2 | 72 | void SetSecondLevelIterator(InternalIteratorBase<BlockHandle>* iter); |
7c673cae FG |
73 | void InitDataBlock(); |
74 | ||
75 | TwoLevelIteratorState* state_; | |
11fdf7f2 TL |
76 | IteratorWrapperBase<BlockHandle> first_level_iter_; |
77 | IteratorWrapperBase<BlockHandle> second_level_iter_; // May be nullptr | |
7c673cae FG |
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. | |
11fdf7f2 | 81 | BlockHandle data_block_handle_; |
7c673cae FG |
82 | }; |
83 | ||
11fdf7f2 TL |
84 | TwoLevelIndexIterator::TwoLevelIndexIterator( |
85 | TwoLevelIteratorState* state, | |
86 | InternalIteratorBase<BlockHandle>* first_level_iter) | |
87 | : state_(state), first_level_iter_(first_level_iter) {} | |
7c673cae | 88 | |
11fdf7f2 | 89 | void TwoLevelIndexIterator::Seek(const Slice& target) { |
7c673cae FG |
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 | ||
11fdf7f2 | 99 | void TwoLevelIndexIterator::SeekForPrev(const Slice& target) { |
7c673cae FG |
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()) { | |
11fdf7f2 | 106 | if (!first_level_iter_.Valid() && first_level_iter_.status().ok()) { |
7c673cae FG |
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 | ||
11fdf7f2 | 117 | void TwoLevelIndexIterator::SeekToFirst() { |
7c673cae FG |
118 | first_level_iter_.SeekToFirst(); |
119 | InitDataBlock(); | |
120 | if (second_level_iter_.iter() != nullptr) { | |
121 | second_level_iter_.SeekToFirst(); | |
122 | } | |
123 | SkipEmptyDataBlocksForward(); | |
124 | } | |
125 | ||
11fdf7f2 | 126 | void TwoLevelIndexIterator::SeekToLast() { |
7c673cae FG |
127 | first_level_iter_.SeekToLast(); |
128 | InitDataBlock(); | |
129 | if (second_level_iter_.iter() != nullptr) { | |
130 | second_level_iter_.SeekToLast(); | |
131 | } | |
132 | SkipEmptyDataBlocksBackward(); | |
133 | } | |
134 | ||
11fdf7f2 | 135 | void TwoLevelIndexIterator::Next() { |
7c673cae FG |
136 | assert(Valid()); |
137 | second_level_iter_.Next(); | |
138 | SkipEmptyDataBlocksForward(); | |
139 | } | |
140 | ||
11fdf7f2 | 141 | void TwoLevelIndexIterator::Prev() { |
7c673cae FG |
142 | assert(Valid()); |
143 | second_level_iter_.Prev(); | |
144 | SkipEmptyDataBlocksBackward(); | |
145 | } | |
146 | ||
11fdf7f2 | 147 | void TwoLevelIndexIterator::SkipEmptyDataBlocksForward() { |
7c673cae | 148 | while (second_level_iter_.iter() == nullptr || |
11fdf7f2 | 149 | (!second_level_iter_.Valid() && second_level_iter_.status().ok())) { |
7c673cae FG |
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 | ||
11fdf7f2 | 163 | void TwoLevelIndexIterator::SkipEmptyDataBlocksBackward() { |
7c673cae | 164 | while (second_level_iter_.iter() == nullptr || |
11fdf7f2 | 165 | (!second_level_iter_.Valid() && second_level_iter_.status().ok())) { |
7c673cae FG |
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 | ||
11fdf7f2 TL |
179 | void TwoLevelIndexIterator::SetSecondLevelIterator( |
180 | InternalIteratorBase<BlockHandle>* iter) { | |
181 | InternalIteratorBase<BlockHandle>* old_iter = second_level_iter_.Set(iter); | |
182 | delete old_iter; | |
7c673cae FG |
183 | } |
184 | ||
11fdf7f2 | 185 | void TwoLevelIndexIterator::InitDataBlock() { |
7c673cae FG |
186 | if (!first_level_iter_.Valid()) { |
187 | SetSecondLevelIterator(nullptr); | |
188 | } else { | |
11fdf7f2 | 189 | BlockHandle handle = first_level_iter_.value(); |
7c673cae FG |
190 | if (second_level_iter_.iter() != nullptr && |
191 | !second_level_iter_.status().IsIncomplete() && | |
11fdf7f2 | 192 | handle.offset() == data_block_handle_.offset()) { |
7c673cae FG |
193 | // second_level_iter is already constructed with this iterator, so |
194 | // no need to change anything | |
195 | } else { | |
11fdf7f2 TL |
196 | InternalIteratorBase<BlockHandle>* iter = |
197 | state_->NewSecondaryIterator(handle); | |
198 | data_block_handle_ = handle; | |
7c673cae FG |
199 | SetSecondLevelIterator(iter); |
200 | } | |
201 | } | |
202 | } | |
203 | ||
204 | } // namespace | |
205 | ||
11fdf7f2 TL |
206 | InternalIteratorBase<BlockHandle>* NewTwoLevelIterator( |
207 | TwoLevelIteratorState* state, | |
208 | InternalIteratorBase<BlockHandle>* first_level_iter) { | |
209 | return new TwoLevelIndexIterator(state, first_level_iter); | |
7c673cae | 210 | } |
7c673cae | 211 | } // namespace rocksdb |