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.
5 #include "table/two_level_iterator.h"
7 #include "leveldb/table.h"
8 #include "table/block.h"
9 #include "table/format.h"
10 #include "table/iterator_wrapper.h"
16 typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&);
18 class TwoLevelIterator: public Iterator {
22 BlockFunction block_function,
24 const ReadOptions& options);
26 virtual ~TwoLevelIterator();
28 virtual void Seek(const Slice& target);
29 virtual void SeekToFirst();
30 virtual void SeekToLast();
34 virtual bool Valid() const {
35 return data_iter_.Valid();
37 virtual Slice key() const {
39 return data_iter_.key();
41 virtual Slice value() const {
43 return data_iter_.value();
45 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();
57 void SaveError(const Status& s) {
58 if (status_.ok() && !s.ok()) status_ = s;
60 void SkipEmptyDataBlocksForward();
61 void SkipEmptyDataBlocksBackward();
62 void SetDataIterator(Iterator* data_iter);
65 BlockFunction block_function_;
67 const ReadOptions options_;
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_;
76 TwoLevelIterator::TwoLevelIterator(
78 BlockFunction block_function,
80 const ReadOptions& options)
81 : block_function_(block_function),
84 index_iter_(index_iter),
88 TwoLevelIterator::~TwoLevelIterator() {
91 void TwoLevelIterator::Seek(const Slice& target) {
92 index_iter_.Seek(target);
94 if (data_iter_.iter() != NULL) data_iter_.Seek(target);
95 SkipEmptyDataBlocksForward();
98 void TwoLevelIterator::SeekToFirst() {
99 index_iter_.SeekToFirst();
101 if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
102 SkipEmptyDataBlocksForward();
105 void TwoLevelIterator::SeekToLast() {
106 index_iter_.SeekToLast();
108 if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
109 SkipEmptyDataBlocksBackward();
112 void TwoLevelIterator::Next() {
115 SkipEmptyDataBlocksForward();
118 void TwoLevelIterator::Prev() {
121 SkipEmptyDataBlocksBackward();
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);
134 if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
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);
147 if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
151 void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
152 if (data_iter_.iter() != NULL) SaveError(data_iter_.status());
153 data_iter_.Set(data_iter);
156 void TwoLevelIterator::InitDataBlock() {
157 if (!index_iter_.Valid()) {
158 SetDataIterator(NULL);
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
165 Iterator* iter = (*block_function_)(arg_, options_, handle);
166 data_block_handle_.assign(handle.data(), handle.size());
167 SetDataIterator(iter);
174 Iterator* NewTwoLevelIterator(
175 Iterator* index_iter,
176 BlockFunction block_function,
178 const ReadOptions& options) {
179 return new TwoLevelIterator(index_iter, block_function, arg, options);
182 } // namespace leveldb