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 virtual bool Valid() const { 35 return data_iter_.Valid(); 36 } 37 virtual Slice key() const { 38 assert(Valid()); 39 return data_iter_.key(); 40 } 41 virtual Slice value() const { 42 assert(Valid()); 43 return data_iter_.value(); 44 } 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(); 51 } else { 52 return status_; 53 } 54 } 55 56 private: 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 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 88 TwoLevelIterator::~TwoLevelIterator() { 89 } 90 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 98 void TwoLevelIterator::SeekToFirst() { 99 index_iter_.SeekToFirst(); 100 InitDataBlock(); 101 if (data_iter_.iter() != NULL) data_iter_.SeekToFirst(); 102 SkipEmptyDataBlocksForward(); 103 } 104 105 void TwoLevelIterator::SeekToLast() { 106 index_iter_.SeekToLast(); 107 InitDataBlock(); 108 if (data_iter_.iter() != NULL) data_iter_.SeekToLast(); 109 SkipEmptyDataBlocksBackward(); 110 } 111 112 void TwoLevelIterator::Next() { 113 assert(Valid()); 114 data_iter_.Next(); 115 SkipEmptyDataBlocksForward(); 116 } 117 118 void TwoLevelIterator::Prev() { 119 assert(Valid()); 120 data_iter_.Prev(); 121 SkipEmptyDataBlocksBackward(); 122 } 123 124 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 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 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 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 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