two_level_iterator.cc raw

   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
 172