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   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   // Unreference and, if needed, clean up the current SuperVersion. This is
  89   // either done immediately or deferred until this iterator is unpinned by
  90   // PinnedIteratorsManager.
  91   void SVCleanup();
  92   static void SVCleanup(
  93     DBImpl* db, SuperVersion* sv, bool background_purge_on_iterator_cleanup);
  94   static void DeferredSVCleanup(void* arg);
  95
  96   void RebuildIterators(bool refresh_sv);
  97   void RenewIterators();
  98   void BuildLevelIterators(const VersionStorageInfo* vstorage);
  99   void ResetIncompleteIterators();
 100   void SeekInternal(const Slice& internal_key, bool seek_to_first);
 101   void UpdateCurrent();
 102   bool NeedToSeekImmutable(const Slice& internal_key);
 103   void DeleteCurrentIter();
 104   uint32_t FindFileInRange(
 105     const std::vector<FileMetaData*>& files, const Slice& internal_key,
 106     uint32_t left, uint32_t right);
 107
 108   bool IsOverUpperBound(const Slice& internal_key) const;
 109
 110   // Set PinnedIteratorsManager for all children Iterators, this function should
 111   // be called whenever we update children Iterators or pinned_iters_mgr_.
 112   void UpdateChildrenPinnedItersMgr();
 113
 114   // A helper function that will release iter in the proper manner, or pass it
 115   // to pinned_iters_mgr_ to release it later if pinning is enabled.
 116   void DeleteIterator(InternalIterator* iter, bool is_arena = false);
 117
 118   DBImpl* const db_;
 119   const ReadOptions read_options_;
 120   ColumnFamilyData* const cfd_;
 121   const SliceTransform* const prefix_extractor_;
 122   const Comparator* user_comparator_;
 123   MinIterHeap immutable_min_heap_;
 124
 125   SuperVersion* sv_;
 126   InternalIterator* mutable_iter_;
 127   std::vector<InternalIterator*> imm_iters_;
 128   std::vector<InternalIterator*> l0_iters_;
 129   std::vector<ForwardLevelIterator*> level_iters_;
 130   InternalIterator* current_;
 131   bool valid_;
 132
 133   // Internal iterator status; set only by one of the unsupported methods.
 134   Status status_;
 135   // Status of immutable iterators, maintained here to avoid iterating over
 136   // all of them in status().
 137   Status immutable_status_;
 138   // Indicates that at least one of the immutable iterators pointed to a key
 139   // larger than iterate_upper_bound and was therefore destroyed. Seek() may
 140   // need to rebuild such iterators.
 141   bool has_iter_trimmed_for_upper_bound_;
 142   // Is current key larger than iterate_upper_bound? If so, makes Valid()
 143   // return false.
 144   bool current_over_upper_bound_;
 145
 146   // Left endpoint of the range of keys that immutable iterators currently
 147   // cover. When Seek() is called with a key that's within that range, immutable
 148   // iterators don't need to be moved; see NeedToSeekImmutable(). This key is
 149   // included in the range after a Seek(), but excluded when advancing the
 150   // iterator using Next().
 151   IterKey prev_key_;
 152   bool is_prev_set_;
 153   bool is_prev_inclusive_;
 154
 155   PinnedIteratorsManager* pinned_iters_mgr_;
 156   Arena arena_;
 157 };
 158
 159 }  // namespace ROCKSDB_NAMESPACE
 160 #endif  // ROCKSDB_LITE