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