1 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | |
5 | #include "table/two_level_iterator.h" |
6 | |
7 | #include "leveldb/table.h" |
8 | #include "table/block.h" |
9 | #include "table/format.h" |
10 | #include "table/iterator_wrapper.h" |
11 | |
12 | namespace leveldb { |
13 | |
14 | namespace { |
15 | |
16 | typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&); |
17 | |
18 | class TwoLevelIterator : public Iterator { |
19 | public: |
20 | TwoLevelIterator(Iterator* index_iter, BlockFunction block_function, |
21 | void* arg, const ReadOptions& options); |
22 | |
23 | ~TwoLevelIterator() override; |
24 | |
25 | void Seek(const Slice& target) override; |
26 | void SeekToFirst() override; |
27 | void SeekToLast() override; |
28 | void Next() override; |
29 | void Prev() override; |
30 | |
31 | bool Valid() const override { return data_iter_.Valid(); } |
32 | Slice key() const override { |
33 | assert(Valid()); |
34 | return data_iter_.key(); |
35 | } |
36 | Slice value() const override { |
37 | assert(Valid()); |
38 | return data_iter_.value(); |
39 | } |
40 | Status status() const override { |
41 | // It'd be nice if status() returned a const Status& instead of a Status |
42 | if (!index_iter_.status().ok()) { |
43 | return index_iter_.status(); |
44 | } else if (data_iter_.iter() != nullptr && !data_iter_.status().ok()) { |
45 | return data_iter_.status(); |
46 | } else { |
47 | return status_; |
48 | } |
49 | } |
50 | |
51 | private: |
52 | void SaveError(const Status& s) { |
53 | if (status_.ok() && !s.ok()) status_ = s; |
54 | } |
55 | void SkipEmptyDataBlocksForward(); |
56 | void SkipEmptyDataBlocksBackward(); |
57 | void SetDataIterator(Iterator* data_iter); |
58 | void InitDataBlock(); |
59 | |
60 | BlockFunction block_function_; |
61 | void* arg_; |
62 | const ReadOptions options_; |
63 | Status status_; |
64 | IteratorWrapper index_iter_; |
65 | IteratorWrapper data_iter_; // May be nullptr |
66 | // If data_iter_ is non-null, then "data_block_handle_" holds the |
67 | // "index_value" passed to block_function_ to create the data_iter_. |
68 | std::string data_block_handle_; |
69 | }; |
70 | |
71 | TwoLevelIterator::TwoLevelIterator(Iterator* index_iter, |
72 | BlockFunction block_function, void* arg, |
73 | const ReadOptions& options) |
74 | : block_function_(block_function), |
75 | arg_(arg), |
76 | options_(options), |
77 | index_iter_(index_iter), |
78 | data_iter_(nullptr) {} |
79 | |
80 | TwoLevelIterator::~TwoLevelIterator() = default; |
81 | |
82 | void TwoLevelIterator::Seek(const Slice& target) { |
83 | index_iter_.Seek(target); |
84 | InitDataBlock(); |
85 | if (data_iter_.iter() != nullptr) data_iter_.Seek(target); |
86 | SkipEmptyDataBlocksForward(); |
87 | } |
88 | |
89 | void TwoLevelIterator::SeekToFirst() { |
90 | index_iter_.SeekToFirst(); |
91 | InitDataBlock(); |
92 | if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst(); |
93 | SkipEmptyDataBlocksForward(); |
94 | } |
95 | |
96 | void TwoLevelIterator::SeekToLast() { |
97 | index_iter_.SeekToLast(); |
98 | InitDataBlock(); |
99 | if (data_iter_.iter() != nullptr) data_iter_.SeekToLast(); |
100 | SkipEmptyDataBlocksBackward(); |
101 | } |
102 | |
103 | void TwoLevelIterator::Next() { |
104 | assert(Valid()); |
105 | data_iter_.Next(); |
106 | SkipEmptyDataBlocksForward(); |
107 | } |
108 | |
109 | void TwoLevelIterator::Prev() { |
110 | assert(Valid()); |
111 | data_iter_.Prev(); |
112 | SkipEmptyDataBlocksBackward(); |
113 | } |
114 | |
115 | void TwoLevelIterator::SkipEmptyDataBlocksForward() { |
116 | while (data_iter_.iter() == nullptr || !data_iter_.Valid()) { |
117 | // Move to next block |
118 | if (!index_iter_.Valid()) { |
119 | SetDataIterator(nullptr); |
120 | return; |
121 | } |
122 | index_iter_.Next(); |
123 | InitDataBlock(); |
124 | if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst(); |
125 | } |
126 | } |
127 | |
128 | void TwoLevelIterator::SkipEmptyDataBlocksBackward() { |
129 | while (data_iter_.iter() == nullptr || !data_iter_.Valid()) { |
130 | // Move to next block |
131 | if (!index_iter_.Valid()) { |
132 | SetDataIterator(nullptr); |
133 | return; |
134 | } |
135 | index_iter_.Prev(); |
136 | InitDataBlock(); |
137 | if (data_iter_.iter() != nullptr) data_iter_.SeekToLast(); |
138 | } |
139 | } |
140 | |
141 | void TwoLevelIterator::SetDataIterator(Iterator* data_iter) { |
142 | if (data_iter_.iter() != nullptr) SaveError(data_iter_.status()); |
143 | data_iter_.Set(data_iter); |
144 | } |
145 | |
146 | void TwoLevelIterator::InitDataBlock() { |
147 | if (!index_iter_.Valid()) { |
148 | SetDataIterator(nullptr); |
149 | } else { |
150 | Slice handle = index_iter_.value(); |
151 | if (data_iter_.iter() != nullptr && |
152 | handle.compare(data_block_handle_) == 0) { |
153 | // data_iter_ is already constructed with this iterator, so |
154 | // no need to change anything |
155 | } else { |
156 | Iterator* iter = (*block_function_)(arg_, options_, handle); |
157 | data_block_handle_.assign(handle.data(), handle.size()); |
158 | SetDataIterator(iter); |
159 | } |
160 | } |
161 | } |
162 | |
163 | } // namespace |
164 | |
165 | Iterator* NewTwoLevelIterator(Iterator* index_iter, |
166 | BlockFunction block_function, void* arg, |
167 | const ReadOptions& options) { |
168 | return new TwoLevelIterator(index_iter, block_function, arg, options); |
169 | } |
170 | |
171 | } // namespace leveldb |
172 | |