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
Valid() const31 bool Valid() const override { return data_iter_.Valid(); }
key() const32 Slice key() const override {
33 assert(Valid());
34 return data_iter_.key();
35 }
value() const36 Slice value() const override {
37 assert(Valid());
38 return data_iter_.value();
39 }
status() const40 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:
SaveError(const Status & s)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
TwoLevelIterator(Iterator * index_iter,BlockFunction block_function,void * arg,const ReadOptions & options)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
Seek(const Slice & target)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
SeekToFirst()89 void TwoLevelIterator::SeekToFirst() {
90 index_iter_.SeekToFirst();
91 InitDataBlock();
92 if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
93 SkipEmptyDataBlocksForward();
94 }
95
SeekToLast()96 void TwoLevelIterator::SeekToLast() {
97 index_iter_.SeekToLast();
98 InitDataBlock();
99 if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
100 SkipEmptyDataBlocksBackward();
101 }
102
Next()103 void TwoLevelIterator::Next() {
104 assert(Valid());
105 data_iter_.Next();
106 SkipEmptyDataBlocksForward();
107 }
108
Prev()109 void TwoLevelIterator::Prev() {
110 assert(Valid());
111 data_iter_.Prev();
112 SkipEmptyDataBlocksBackward();
113 }
114
SkipEmptyDataBlocksForward()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
SkipEmptyDataBlocksBackward()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
SetDataIterator(Iterator * data_iter)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
InitDataBlock()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
NewTwoLevelIterator(Iterator * index_iter,BlockFunction block_function,void * arg,const ReadOptions & options)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