ceph/src/rocksdb/db/forward_iterator.h

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5 #pragma once
   6
   7 #ifndef ROCKSDB_LITE
   8
   9 #include <string>
  10 #include <vector>
  11 #include <queue>
  12
  13 #include "rocksdb/db.h"
  14 #include "rocksdb/iterator.h"
  15 #include "rocksdb/options.h"
  16 #include "db/dbformat.h"
  17 #include "table/internal_iterator.h"
  18 #include "util/arena.h"
  19
  20 namespace rocksdb {
  21
  22 class DBImpl;
  23 class Env;
  24 struct SuperVersion;
  25 class ColumnFamilyData;
  26 class LevelIterator;
  27 class VersionStorageInfo;
  28 struct FileMetaData;
  29
  30 class MinIterComparator {
  31  public:
  32   explicit MinIterComparator(const Comparator* comparator) :
  33     comparator_(comparator) {}
  34
  35   bool operator()(InternalIterator* a, InternalIterator* b) {
  36     return comparator_->Compare(a->key(), b->key()) > 0;
  37   }
  38  private:
  39   const Comparator* comparator_;
  40 };
  41
  42 typedef std::priority_queue<InternalIterator*, std::vector<InternalIterator*>,
  43                             MinIterComparator> MinIterHeap;
  44
  45 /**
  46  * ForwardIterator is a special type of iterator that only supports Seek()
  47  * and Next(). It is expected to perform better than TailingIterator by
  48  * removing the encapsulation and making all information accessible within
  49  * the iterator. At the current implementation, snapshot is taken at the
  50  * time Seek() is called. The Next() followed do not see new values after.
  51  */
  52 class ForwardIterator : public InternalIterator {
  53  public:
  54   ForwardIterator(DBImpl* db, const ReadOptions& read_options,
  55                   ColumnFamilyData* cfd, SuperVersion* current_sv = nullptr);
  56   virtual ~ForwardIterator();
  57
  58   void SeekForPrev(const Slice& target) override {
  59     status_ = Status::NotSupported("ForwardIterator::SeekForPrev()");
  60     valid_ = false;
  61   }
  62   void SeekToLast() override {
  63     status_ = Status::NotSupported("ForwardIterator::SeekToLast()");
  64     valid_ = false;
  65   }
  66   void Prev() override {
  67     status_ = Status::NotSupported("ForwardIterator::Prev");
  68     valid_ = false;
  69   }
  70
  71   virtual bool Valid() const override;
  72   void SeekToFirst() override;
  73   virtual void Seek(const Slice& target) override;
  74   virtual void Next() override;
  75   virtual Slice key() const override;
  76   virtual Slice value() const override;
  77   virtual Status status() const override;
  78   virtual Status GetProperty(std::string prop_name, std::string* prop) override;
  79   virtual void SetPinnedItersMgr(
  80       PinnedIteratorsManager* pinned_iters_mgr) override;
  81   virtual bool IsKeyPinned() const override;
  82   virtual bool IsValuePinned() const override;
  83
  84   bool TEST_CheckDeletedIters(int* deleted_iters, int* num_iters);
  85
  86  private:
  87   void Cleanup(bool release_sv);
  88   void SVCleanup();
  89   void RebuildIterators(bool refresh_sv);
  90   void RenewIterators();
  91   void BuildLevelIterators(const VersionStorageInfo* vstorage);
  92   void ResetIncompleteIterators();
  93   void SeekInternal(const Slice& internal_key, bool seek_to_first);
  94   void UpdateCurrent();
  95   bool NeedToSeekImmutable(const Slice& internal_key);
  96   void DeleteCurrentIter();
  97   uint32_t FindFileInRange(
  98     const std::vector<FileMetaData*>& files, const Slice& internal_key,
  99     uint32_t left, uint32_t right);
 100
 101   bool IsOverUpperBound(const Slice& internal_key) const;
 102
 103   // Set PinnedIteratorsManager for all children Iterators, this function should
 104   // be called whenever we update children Iterators or pinned_iters_mgr_.
 105   void UpdateChildrenPinnedItersMgr();
 106
 107   // A helper function that will release iter in the proper manner, or pass it
 108   // to pinned_iters_mgr_ to release it later if pinning is enabled.
 109   void DeleteIterator(InternalIterator* iter, bool is_arena = false);
 110
 111   DBImpl* const db_;
 112   const ReadOptions read_options_;
 113   ColumnFamilyData* const cfd_;
 114   const SliceTransform* const prefix_extractor_;
 115   const Comparator* user_comparator_;
 116   MinIterHeap immutable_min_heap_;
 117
 118   SuperVersion* sv_;
 119   InternalIterator* mutable_iter_;
 120   std::vector<InternalIterator*> imm_iters_;
 121   std::vector<InternalIterator*> l0_iters_;
 122   std::vector<LevelIterator*> level_iters_;
 123   InternalIterator* current_;
 124   bool valid_;
 125
 126   // Internal iterator status; set only by one of the unsupported methods.
 127   Status status_;
 128   // Status of immutable iterators, maintained here to avoid iterating over
 129   // all of them in status().
 130   Status immutable_status_;
 131   // Indicates that at least one of the immutable iterators pointed to a key
 132   // larger than iterate_upper_bound and was therefore destroyed. Seek() may
 133   // need to rebuild such iterators.
 134   bool has_iter_trimmed_for_upper_bound_;
 135   // Is current key larger than iterate_upper_bound? If so, makes Valid()
 136   // return false.
 137   bool current_over_upper_bound_;
 138
 139   // Left endpoint of the range of keys that immutable iterators currently
 140   // cover. When Seek() is called with a key that's within that range, immutable
 141   // iterators don't need to be moved; see NeedToSeekImmutable(). This key is
 142   // included in the range after a Seek(), but excluded when advancing the
 143   // iterator using Next().
 144   IterKey prev_key_;
 145   bool is_prev_set_;
 146   bool is_prev_inclusive_;
 147
 148   PinnedIteratorsManager* pinned_iters_mgr_;
 149   Arena arena_;
 150 };
 151
 152 }  // namespace rocksdb
 153 #endif  // ROCKSDB_LITE