Branch data Line data Source code
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 : 2841842 : bool Valid() const override { return data_iter_.Valid(); }
32 : 612628 : Slice key() const override {
33 [ - + ]: 612628 : assert(Valid());
34 : 612628 : return data_iter_.key();
35 : : }
36 : 995066 : Slice value() const override {
37 [ - + ]: 995066 : assert(Valid());
38 : 995066 : return data_iter_.value();
39 : : }
40 : 4576 : Status status() const override {
41 : : // It'd be nice if status() returned a const Status& instead of a Status
42 [ - + - + ]: 4576 : if (!index_iter_.status().ok()) {
43 : 0 : return index_iter_.status();
44 [ - + - - : 4576 : } else if (data_iter_.iter() != nullptr && !data_iter_.status().ok()) {
- + ]
45 : 0 : return data_iter_.status();
46 : : } else {
47 [ - + ]: 4576 : return status_;
48 : : }
49 : : }
50 : :
51 : : private:
52 : 12015 : void SaveError(const Status& s) {
53 [ + + + + ]: 12015 : if (status_.ok() && !s.ok()) status_ = s;
54 : 12015 : }
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 : 8517 : TwoLevelIterator::TwoLevelIterator(Iterator* index_iter,
72 : : BlockFunction block_function, void* arg,
73 : 8517 : const ReadOptions& options)
74 : 8517 : : block_function_(block_function),
75 : 8517 : arg_(arg),
76 : 8517 : options_(options),
77 [ + - ]: 8517 : index_iter_(index_iter),
78 [ + - + - : 8517 : data_iter_(nullptr) {}
- - ]
79 : :
80 [ + + ]: 17035 : TwoLevelIterator::~TwoLevelIterator() = default;
81 : :
82 : 5087 : void TwoLevelIterator::Seek(const Slice& target) {
83 : 5087 : index_iter_.Seek(target);
84 : 5087 : InitDataBlock();
85 [ + + ]: 5087 : if (data_iter_.iter() != nullptr) data_iter_.Seek(target);
86 : 5087 : SkipEmptyDataBlocksForward();
87 : 5087 : }
88 : :
89 : 1238 : void TwoLevelIterator::SeekToFirst() {
90 : 1238 : index_iter_.SeekToFirst();
91 : 1238 : InitDataBlock();
92 [ + - ]: 1238 : if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
93 : 1238 : SkipEmptyDataBlocksForward();
94 : 1238 : }
95 : :
96 : 0 : void TwoLevelIterator::SeekToLast() {
97 : 0 : index_iter_.SeekToLast();
98 : 0 : InitDataBlock();
99 [ # # ]: 0 : if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
100 : 0 : SkipEmptyDataBlocksBackward();
101 : 0 : }
102 : :
103 : 610749 : void TwoLevelIterator::Next() {
104 [ - + ]: 610749 : assert(Valid());
105 : 610749 : data_iter_.Next();
106 : 610749 : SkipEmptyDataBlocksForward();
107 : 610749 : }
108 : :
109 : 0 : void TwoLevelIterator::Prev() {
110 [ # # ]: 0 : assert(Valid());
111 : 0 : data_iter_.Prev();
112 : 0 : SkipEmptyDataBlocksBackward();
113 : 0 : }
114 : :
115 : 617074 : void TwoLevelIterator::SkipEmptyDataBlocksForward() {
116 [ + + + + ]: 1246163 : while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {
117 : : // Move to next block
118 [ + + ]: 16461 : if (!index_iter_.Valid()) {
119 : 4446 : SetDataIterator(nullptr);
120 : 4446 : return;
121 : : }
122 : 12015 : index_iter_.Next();
123 : 12015 : InitDataBlock();
124 [ + + ]: 12015 : if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
125 : : }
126 : : }
127 : :
128 : 0 : void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
129 [ # # # # ]: 0 : while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {
130 : : // Move to next block
131 [ # # ]: 0 : if (!index_iter_.Valid()) {
132 : 0 : SetDataIterator(nullptr);
133 : 0 : return;
134 : : }
135 : 0 : index_iter_.Prev();
136 : 0 : InitDataBlock();
137 [ # # ]: 0 : if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
138 : : }
139 : : }
140 : :
141 : 22786 : void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
142 [ + + + - ]: 34801 : if (data_iter_.iter() != nullptr) SaveError(data_iter_.status());
143 : 22786 : data_iter_.Set(data_iter);
144 : 22786 : }
145 : :
146 : 18340 : void TwoLevelIterator::InitDataBlock() {
147 [ + + ]: 18340 : if (!index_iter_.Valid()) {
148 : 4446 : SetDataIterator(nullptr);
149 : : } else {
150 : 13894 : Slice handle = index_iter_.value();
151 [ + + ]: 13894 : if (data_iter_.iter() != nullptr &&
152 [ - + + - ]: 9794 : 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 : 13894 : Iterator* iter = (*block_function_)(arg_, options_, handle);
157 : 13894 : data_block_handle_.assign(handle.data(), handle.size());
158 : 13894 : SetDataIterator(iter);
159 : : }
160 : : }
161 : 18340 : }
162 : :
163 : : } // namespace
164 : :
165 : 8517 : Iterator* NewTwoLevelIterator(Iterator* index_iter,
166 : : BlockFunction block_function, void* arg,
167 : : const ReadOptions& options) {
168 [ + - ]: 8517 : return new TwoLevelIterator(index_iter, block_function, arg, options);
169 : : }
170 : :
171 : : } // namespace leveldb
|
