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(
21 : Iterator* index_iter,
22 : BlockFunction block_function,
23 : void* arg,
24 : const ReadOptions& options);
25 :
26 : virtual ~TwoLevelIterator();
27 :
28 : virtual void Seek(const Slice& target);
29 : virtual void SeekToFirst();
30 : virtual void SeekToLast();
31 : virtual void Next();
32 : virtual void Prev();
33 :
34 12871 : virtual bool Valid() const {
35 73302 : return data_iter_.Valid();
36 : }
37 12757 : virtual Slice key() const {
38 25514 : assert(Valid());
39 12757 : return data_iter_.key();
40 : }
41 34995 : virtual Slice value() const {
42 69990 : assert(Valid());
43 34995 : return data_iter_.value();
44 : }
45 158 : virtual Status status() const {
46 : // It'd be nice if status() returned a const Status& instead of a Status
47 474 : if (!index_iter_.status().ok()) {
48 0 : return index_iter_.status();
49 158 : } else if (data_iter_.iter() != NULL && !data_iter_.status().ok()) {
50 0 : return data_iter_.status();
51 : } else {
52 158 : return status_;
53 : }
54 : }
55 :
56 : private:
57 370 : void SaveError(const Status& s) {
58 1110 : if (status_.ok() && !s.ok()) status_ = s;
59 370 : }
60 : void SkipEmptyDataBlocksForward();
61 : void SkipEmptyDataBlocksBackward();
62 : void SetDataIterator(Iterator* data_iter);
63 : void InitDataBlock();
64 :
65 : BlockFunction block_function_;
66 : void* arg_;
67 : const ReadOptions options_;
68 : Status status_;
69 : IteratorWrapper index_iter_;
70 : IteratorWrapper data_iter_; // May be NULL
71 : // If data_iter_ is non-NULL, then "data_block_handle_" holds the
72 : // "index_value" passed to block_function_ to create the data_iter_.
73 : std::string data_block_handle_;
74 : };
75 :
76 218 : TwoLevelIterator::TwoLevelIterator(
77 : Iterator* index_iter,
78 : BlockFunction block_function,
79 : void* arg,
80 : const ReadOptions& options)
81 : : block_function_(block_function),
82 : arg_(arg),
83 : options_(options),
84 : index_iter_(index_iter),
85 872 : data_iter_(NULL) {
86 218 : }
87 :
88 1308 : TwoLevelIterator::~TwoLevelIterator() {
89 436 : }
90 :
91 76 : void TwoLevelIterator::Seek(const Slice& target) {
92 76 : index_iter_.Seek(target);
93 76 : InitDataBlock();
94 76 : if (data_iter_.iter() != NULL) data_iter_.Seek(target);
95 76 : SkipEmptyDataBlocksForward();
96 76 : }
97 :
98 20 : void TwoLevelIterator::SeekToFirst() {
99 20 : index_iter_.SeekToFirst();
100 20 : InitDataBlock();
101 20 : if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
102 20 : SkipEmptyDataBlocksForward();
103 20 : }
104 :
105 0 : void TwoLevelIterator::SeekToLast() {
106 0 : index_iter_.SeekToLast();
107 0 : InitDataBlock();
108 0 : if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
109 0 : SkipEmptyDataBlocksBackward();
110 0 : }
111 :
112 12679 : void TwoLevelIterator::Next() {
113 25358 : assert(Valid());
114 12679 : data_iter_.Next();
115 12679 : SkipEmptyDataBlocksForward();
116 12679 : }
117 :
118 0 : void TwoLevelIterator::Prev() {
119 0 : assert(Valid());
120 0 : data_iter_.Prev();
121 0 : SkipEmptyDataBlocksBackward();
122 0 : }
123 :
124 :
125 12775 : void TwoLevelIterator::SkipEmptyDataBlocksForward() {
126 25920 : while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
127 : // Move to next block
128 388 : if (!index_iter_.Valid()) {
129 18 : SetDataIterator(NULL);
130 12793 : return;
131 : }
132 370 : index_iter_.Next();
133 370 : InitDataBlock();
134 370 : if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
135 : }
136 : }
137 :
138 0 : void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
139 0 : while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
140 : // Move to next block
141 0 : if (!index_iter_.Valid()) {
142 0 : SetDataIterator(NULL);
143 0 : return;
144 : }
145 0 : index_iter_.Prev();
146 0 : InitDataBlock();
147 0 : if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
148 : }
149 : }
150 :
151 484 : void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
152 854 : if (data_iter_.iter() != NULL) SaveError(data_iter_.status());
153 484 : data_iter_.Set(data_iter);
154 484 : }
155 :
156 466 : void TwoLevelIterator::InitDataBlock() {
157 466 : if (!index_iter_.Valid()) {
158 18 : SetDataIterator(NULL);
159 : } else {
160 448 : Slice handle = index_iter_.value();
161 800 : if (data_iter_.iter() != NULL && handle.compare(data_block_handle_) == 0) {
162 : // data_iter_ is already constructed with this iterator, so
163 : // no need to change anything
164 : } else {
165 448 : Iterator* iter = (*block_function_)(arg_, options_, handle);
166 448 : data_block_handle_.assign(handle.data(), handle.size());
167 448 : SetDataIterator(iter);
168 : }
169 : }
170 466 : }
171 :
172 : } // namespace
173 :
174 218 : Iterator* NewTwoLevelIterator(
175 : Iterator* index_iter,
176 : BlockFunction block_function,
177 : void* arg,
178 : const ReadOptions& options) {
179 218 : return new TwoLevelIterator(index_iter, block_function, arg, options);
180 : }
181 :
182 : } // namespace leveldb
|
