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 #ifndef ROCKSDB_LITE
   8
   9 #include <string>
  10 #include <vector>
  11 #include <queue>
  12
  13 #include "db/dbformat.h"
  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 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                   bool allow_unprepared_value = false);
  57   virtual ~ForwardIterator();
  58
  59   void SeekForPrev(const Slice& /*target*/) override {
  60     status_ = Status::NotSupported("ForwardIterator::SeekForPrev()");
  61     valid_ = false;
  62   }
  63   void SeekToLast() override {
  64     status_ = Status::NotSupported("ForwardIterator::SeekToLast()");
  65     valid_ = false;
  66   }
  67   void Prev() override {
  68     status_ = Status::NotSupported("ForwardIterator::Prev");
  69     valid_ = false;
  70   }
  71
  72   virtual bool Valid() const override;
  73   void SeekToFirst() override;
  74   virtual void Seek(const Slice& target) override;
  75   virtual void Next() override;
  76   virtual Slice key() const override;
  77   virtual Slice value() const override;
  78   virtual Status status() const override;
  79   virtual bool PrepareValue() override;
  80   virtual Status GetProperty(std::string prop_name, std::string* prop) override;
  81   virtual void SetPinnedItersMgr(
  82       PinnedIteratorsManager* pinned_iters_mgr) override;
  83   virtual bool IsKeyPinned() const override;
  84   virtual bool IsValuePinned() const override;
  85
  86   bool TEST_CheckDeletedIters(int* deleted_iters, int* num_iters);
  87
  88  private:
  89   void Cleanup(bool release_sv);
  90   // Unreference and, if needed, clean up the current SuperVersion. This is
  91   // either done immediately or deferred until this iterator is unpinned by
  92   // PinnedIteratorsManager.
  93   void SVCleanup();
  94   static void SVCleanup(
  95     DBImpl* db, SuperVersion* sv, bool background_purge_on_iterator_cleanup);
  96   static void DeferredSVCleanup(void* arg);
  97
  98   void RebuildIterators(bool refresh_sv);
  99   void RenewIterators();
 100   void BuildLevelIterators(const VersionStorageInfo* vstorage);
 101   void ResetIncompleteIterators();
 102   void SeekInternal(const Slice& internal_key, bool seek_to_first);
 103   void UpdateCurrent();
 104   bool NeedToSeekImmutable(const Slice& internal_key);
 105   void DeleteCurrentIter();
 106   uint32_t FindFileInRange(
 107     const std::vector<FileMetaData*>& files, const Slice& internal_key,
 108     uint32_t left, uint32_t right);
 109
 110   bool IsOverUpperBound(const Slice& internal_key) const;
 111
 112   // Set PinnedIteratorsManager for all children Iterators, this function should
 113   // be called whenever we update children Iterators or pinned_iters_mgr_.
 114   void UpdateChildrenPinnedItersMgr();
 115
 116   // A helper function that will release iter in the proper manner, or pass it
 117   // to pinned_iters_mgr_ to release it later if pinning is enabled.
 118   void DeleteIterator(InternalIterator* iter, bool is_arena = false);
 119
 120   DBImpl* const db_;
 121   const ReadOptions read_options_;
 122   ColumnFamilyData* const cfd_;
 123   const SliceTransform* const prefix_extractor_;
 124   const Comparator* user_comparator_;
 125   const bool allow_unprepared_value_;
 126   MinIterHeap immutable_min_heap_;
 127
 128   SuperVersion* sv_;
 129   InternalIterator* mutable_iter_;
 130   std::vector<InternalIterator*> imm_iters_;
 131   std::vector<InternalIterator*> l0_iters_;
 132   std::vector<ForwardLevelIterator*> level_iters_;
 133   InternalIterator* current_;
 134   bool valid_;
 135
 136   // Internal iterator status; set only by one of the unsupported methods.
 137   Status status_;
 138   // Status of immutable iterators, maintained here to avoid iterating over
 139   // all of them in status().
 140   Status immutable_status_;
 141   // Indicates that at least one of the immutable iterators pointed to a key
 142   // larger than iterate_upper_bound and was therefore destroyed. Seek() may
 143   // need to rebuild such iterators.
 144   bool has_iter_trimmed_for_upper_bound_;
 145   // Is current key larger than iterate_upper_bound? If so, makes Valid()
 146   // return false.
 147   bool current_over_upper_bound_;
 148
 149   // Left endpoint of the range of keys that immutable iterators currently
 150   // cover. When Seek() is called with a key that's within that range, immutable
 151   // iterators don't need to be moved; see NeedToSeekImmutable(). This key is
 152   // included in the range after a Seek(), but excluded when advancing the
 153   // iterator using Next().
 154   IterKey prev_key_;
 155   bool is_prev_set_;
 156   bool is_prev_inclusive_;
 157
 158   PinnedIteratorsManager* pinned_iters_mgr_;
 159   Arena arena_;
 160 };
 161
 162 }  // namespace ROCKSDB_NAMESPACE
 163 #endif  // ROCKSDB_LITE