ceph/src/rocksdb/db/forward_iterator.h

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