ceph/src/rocksdb/table/two_level_iterator.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include "table/two_level_iterator.h"
  11 #include "db/pinned_iterators_manager.h"
  12 #include "memory/arena.h"
  13 #include "rocksdb/options.h"
  14 #include "rocksdb/table.h"
  15 #include "table/block_based/block.h"
  16 #include "table/format.h"
  17
  18 namespace ROCKSDB_NAMESPACE {
  19
  20 namespace {
  21
  22 class TwoLevelIndexIterator : public InternalIteratorBase<IndexValue> {
  23  public:
  24   explicit TwoLevelIndexIterator(
  25       TwoLevelIteratorState* state,
  26       InternalIteratorBase<IndexValue>* first_level_iter);
  27
  28   ~TwoLevelIndexIterator() override {
  29     first_level_iter_.DeleteIter(false /* is_arena_mode */);
  30     second_level_iter_.DeleteIter(false /* is_arena_mode */);
  31     delete state_;
  32   }
  33
  34   void Seek(const Slice& target) override;
  35   void SeekForPrev(const Slice& target) override;
  36   void SeekToFirst() override;
  37   void SeekToLast() override;
  38   void Next() override;
  39   void Prev() override;
  40
  41   bool Valid() const override { return second_level_iter_.Valid(); }
  42   Slice key() const override {
  43     assert(Valid());
  44     return second_level_iter_.key();
  45   }
  46   Slice user_key() const override {
  47     assert(Valid());
  48     return second_level_iter_.user_key();
  49   }
  50   IndexValue value() const override {
  51     assert(Valid());
  52     return second_level_iter_.value();
  53   }
  54   Status status() const override {
  55     if (!first_level_iter_.status().ok()) {
  56       assert(second_level_iter_.iter() == nullptr);
  57       return first_level_iter_.status();
  58     } else if (second_level_iter_.iter() != nullptr &&
  59                !second_level_iter_.status().ok()) {
  60       return second_level_iter_.status();
  61     } else {
  62       return status_;
  63     }
  64   }
  65   void SetPinnedItersMgr(
  66       PinnedIteratorsManager* /*pinned_iters_mgr*/) override {}
  67   bool IsKeyPinned() const override { return false; }
  68   bool IsValuePinned() const override { return false; }
  69
  70  private:
  71   void SaveError(const Status& s) {
  72     if (status_.ok() && !s.ok()) status_ = s;
  73   }
  74   void SkipEmptyDataBlocksForward();
  75   void SkipEmptyDataBlocksBackward();
  76   void SetSecondLevelIterator(InternalIteratorBase<IndexValue>* iter);
  77   void InitDataBlock();
  78
  79   TwoLevelIteratorState* state_;
  80   IteratorWrapperBase<IndexValue> first_level_iter_;
  81   IteratorWrapperBase<IndexValue> second_level_iter_;  // May be nullptr
  82   Status status_;
  83   // If second_level_iter is non-nullptr, then "data_block_handle_" holds the
  84   // "index_value" passed to block_function_ to create the second_level_iter.
  85   BlockHandle data_block_handle_;
  86 };
  87
  88 TwoLevelIndexIterator::TwoLevelIndexIterator(
  89     TwoLevelIteratorState* state,
  90     InternalIteratorBase<IndexValue>* first_level_iter)
  91     : state_(state), first_level_iter_(first_level_iter) {}
  92
  93 void TwoLevelIndexIterator::Seek(const Slice& target) {
  94   first_level_iter_.Seek(target);
  95
  96   InitDataBlock();
  97   if (second_level_iter_.iter() != nullptr) {
  98     second_level_iter_.Seek(target);
  99   }
 100   SkipEmptyDataBlocksForward();
 101 }
 102
 103 void TwoLevelIndexIterator::SeekForPrev(const Slice& target) {
 104   first_level_iter_.Seek(target);
 105   InitDataBlock();
 106   if (second_level_iter_.iter() != nullptr) {
 107     second_level_iter_.SeekForPrev(target);
 108   }
 109   if (!Valid()) {
 110     if (!first_level_iter_.Valid() && first_level_iter_.status().ok()) {
 111       first_level_iter_.SeekToLast();
 112       InitDataBlock();
 113       if (second_level_iter_.iter() != nullptr) {
 114         second_level_iter_.SeekForPrev(target);
 115       }
 116     }
 117     SkipEmptyDataBlocksBackward();
 118   }
 119 }
 120
 121 void TwoLevelIndexIterator::SeekToFirst() {
 122   first_level_iter_.SeekToFirst();
 123   InitDataBlock();
 124   if (second_level_iter_.iter() != nullptr) {
 125     second_level_iter_.SeekToFirst();
 126   }
 127   SkipEmptyDataBlocksForward();
 128 }
 129
 130 void TwoLevelIndexIterator::SeekToLast() {
 131   first_level_iter_.SeekToLast();
 132   InitDataBlock();
 133   if (second_level_iter_.iter() != nullptr) {
 134     second_level_iter_.SeekToLast();
 135   }
 136   SkipEmptyDataBlocksBackward();
 137 }
 138
 139 void TwoLevelIndexIterator::Next() {
 140   assert(Valid());
 141   second_level_iter_.Next();
 142   SkipEmptyDataBlocksForward();
 143 }
 144
 145 void TwoLevelIndexIterator::Prev() {
 146   assert(Valid());
 147   second_level_iter_.Prev();
 148   SkipEmptyDataBlocksBackward();
 149 }
 150
 151 void TwoLevelIndexIterator::SkipEmptyDataBlocksForward() {
 152   while (second_level_iter_.iter() == nullptr ||
 153          (!second_level_iter_.Valid() && second_level_iter_.status().ok())) {
 154     // Move to next block
 155     if (!first_level_iter_.Valid()) {
 156       SetSecondLevelIterator(nullptr);
 157       return;
 158     }
 159     first_level_iter_.Next();
 160     InitDataBlock();
 161     if (second_level_iter_.iter() != nullptr) {
 162       second_level_iter_.SeekToFirst();
 163     }
 164   }
 165 }
 166
 167 void TwoLevelIndexIterator::SkipEmptyDataBlocksBackward() {
 168   while (second_level_iter_.iter() == nullptr ||
 169          (!second_level_iter_.Valid() && second_level_iter_.status().ok())) {
 170     // Move to next block
 171     if (!first_level_iter_.Valid()) {
 172       SetSecondLevelIterator(nullptr);
 173       return;
 174     }
 175     first_level_iter_.Prev();
 176     InitDataBlock();
 177     if (second_level_iter_.iter() != nullptr) {
 178       second_level_iter_.SeekToLast();
 179     }
 180   }
 181 }
 182
 183 void TwoLevelIndexIterator::SetSecondLevelIterator(
 184     InternalIteratorBase<IndexValue>* iter) {
 185   InternalIteratorBase<IndexValue>* old_iter = second_level_iter_.Set(iter);
 186   delete old_iter;
 187 }
 188
 189 void TwoLevelIndexIterator::InitDataBlock() {
 190   if (!first_level_iter_.Valid()) {
 191     SetSecondLevelIterator(nullptr);
 192   } else {
 193     BlockHandle handle = first_level_iter_.value().handle;
 194     if (second_level_iter_.iter() != nullptr &&
 195         !second_level_iter_.status().IsIncomplete() &&
 196         handle.offset() == data_block_handle_.offset()) {
 197       // second_level_iter is already constructed with this iterator, so
 198       // no need to change anything
 199     } else {
 200       InternalIteratorBase<IndexValue>* iter =
 201           state_->NewSecondaryIterator(handle);
 202       data_block_handle_ = handle;
 203       SetSecondLevelIterator(iter);
 204     }
 205   }
 206 }
 207
 208 }  // namespace
 209
 210 InternalIteratorBase<IndexValue>* NewTwoLevelIterator(
 211     TwoLevelIteratorState* state,
 212     InternalIteratorBase<IndexValue>* first_level_iter) {
 213   return new TwoLevelIndexIterator(state, first_level_iter);
 214 }
 215 }  // namespace ROCKSDB_NAMESPACE