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
Valid() const34 virtual bool Valid() const {
35 return data_iter_.Valid();
36 }
key() const37 virtual Slice key() const {
38 assert(Valid());
39 return data_iter_.key();
40 }
value() const41 virtual Slice value() const {
42 assert(Valid());
43 return data_iter_.value();
44 }
status() const45 virtual Status status() const {
46 // It'd be nice if status() returned a const Status& instead of a Status
47 if (!index_iter_.status().ok()) {
48 return index_iter_.status();
49 } else if (data_iter_.iter() != NULL && !data_iter_.status().ok()) {
50 return data_iter_.status();
51 } else {
52 return status_;
53 }
54 }
55
56 private:
SaveError(const Status & s)57 void SaveError(const Status& s) {
58 if (status_.ok() && !s.ok()) status_ = s;
59 }
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
TwoLevelIterator(Iterator * index_iter,BlockFunction block_function,void * arg,const ReadOptions & options)76 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 data_iter_(NULL) {
86 }
87
~TwoLevelIterator()88 TwoLevelIterator::~TwoLevelIterator() {
89 }
90
Seek(const Slice & target)91 void TwoLevelIterator::Seek(const Slice& target) {
92 index_iter_.Seek(target);
93 InitDataBlock();
94 if (data_iter_.iter() != NULL) data_iter_.Seek(target);
95 SkipEmptyDataBlocksForward();
96 }
97
SeekToFirst()98 void TwoLevelIterator::SeekToFirst() {
99 index_iter_.SeekToFirst();
100 InitDataBlock();
101 if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
102 SkipEmptyDataBlocksForward();
103 }
104
SeekToLast()105 void TwoLevelIterator::SeekToLast() {
106 index_iter_.SeekToLast();
107 InitDataBlock();
108 if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
109 SkipEmptyDataBlocksBackward();
110 }
111
Next()112 void TwoLevelIterator::Next() {
113 assert(Valid());
114 data_iter_.Next();
115 SkipEmptyDataBlocksForward();
116 }
117
Prev()118 void TwoLevelIterator::Prev() {
119 assert(Valid());
120 data_iter_.Prev();
121 SkipEmptyDataBlocksBackward();
122 }
123
124
SkipEmptyDataBlocksForward()125 void TwoLevelIterator::SkipEmptyDataBlocksForward() {
126 while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
127 // Move to next block
128 if (!index_iter_.Valid()) {
129 SetDataIterator(NULL);
130 return;
131 }
132 index_iter_.Next();
133 InitDataBlock();
134 if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
135 }
136 }
137
SkipEmptyDataBlocksBackward()138 void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
139 while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
140 // Move to next block
141 if (!index_iter_.Valid()) {
142 SetDataIterator(NULL);
143 return;
144 }
145 index_iter_.Prev();
146 InitDataBlock();
147 if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
148 }
149 }
150
SetDataIterator(Iterator * data_iter)151 void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
152 if (data_iter_.iter() != NULL) SaveError(data_iter_.status());
153 data_iter_.Set(data_iter);
154 }
155
InitDataBlock()156 void TwoLevelIterator::InitDataBlock() {
157 if (!index_iter_.Valid()) {
158 SetDataIterator(NULL);
159 } else {
160 Slice handle = index_iter_.value();
161 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 Iterator* iter = (*block_function_)(arg_, options_, handle);
166 data_block_handle_.assign(handle.data(), handle.size());
167 SetDataIterator(iter);
168 }
169 }
170 }
171
172 } // namespace
173
NewTwoLevelIterator(Iterator * index_iter,BlockFunction block_function,void * arg,const ReadOptions & options)174 Iterator* NewTwoLevelIterator(
175 Iterator* index_iter,
176 BlockFunction block_function,
177 void* arg,
178 const ReadOptions& options) {
179 return new TwoLevelIterator(index_iter, block_function, arg, options);
180 }
181
182 } // namespace leveldb
183