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 7 #pragma once 8 9 #include <string> 10 #include "db/dbformat.h" 11 #include "rocksdb/comparator.h" 12 #include "rocksdb/iterator.h" 13 #include "rocksdb/status.h" 14 #include "table/format.h" 15 16 namespace ROCKSDB_NAMESPACE { 17 18 class PinnedIteratorsManager; 19 20 struct IterateResult { 21 Slice key; 22 bool may_be_out_of_upper_bound; 23 }; 24 25 template <class TValue> 26 class InternalIteratorBase : public Cleanable { 27 public: InternalIteratorBase()28 InternalIteratorBase() {} 29 30 // No copying allowed 31 InternalIteratorBase(const InternalIteratorBase&) = delete; 32 InternalIteratorBase& operator=(const InternalIteratorBase&) = delete; 33 ~InternalIteratorBase()34 virtual ~InternalIteratorBase() {} 35 36 // An iterator is either positioned at a key/value pair, or 37 // not valid. This method returns true iff the iterator is valid. 38 // Always returns false if !status().ok(). 39 virtual bool Valid() const = 0; 40 41 // Position at the first key in the source. The iterator is Valid() 42 // after this call iff the source is not empty. 43 virtual void SeekToFirst() = 0; 44 45 // Position at the last key in the source. The iterator is 46 // Valid() after this call iff the source is not empty. 47 virtual void SeekToLast() = 0; 48 49 // Position at the first key in the source that at or past target 50 // The iterator is Valid() after this call iff the source contains 51 // an entry that comes at or past target. 52 // All Seek*() methods clear any error status() that the iterator had prior to 53 // the call; after the seek, status() indicates only the error (if any) that 54 // happened during the seek, not any past errors. 55 virtual void Seek(const Slice& target) = 0; 56 57 // Position at the first key in the source that at or before target 58 // The iterator is Valid() after this call iff the source contains 59 // an entry that comes at or before target. 60 virtual void SeekForPrev(const Slice& target) = 0; 61 62 // Moves to the next entry in the source. After this call, Valid() is 63 // true iff the iterator was not positioned at the last entry in the source. 64 // REQUIRES: Valid() 65 virtual void Next() = 0; 66 67 // Moves to the next entry in the source, and return result. Iterator 68 // implementation should override this method to help methods inline better, 69 // or when MayBeOutOfUpperBound() is non-trivial. 70 // REQUIRES: Valid() NextAndGetResult(IterateResult * result)71 virtual bool NextAndGetResult(IterateResult* result) { 72 Next(); 73 bool is_valid = Valid(); 74 if (is_valid) { 75 result->key = key(); 76 // Default may_be_out_of_upper_bound to true to avoid unnecessary virtual 77 // call. If an implementation has non-trivial MayBeOutOfUpperBound(), 78 // it should also override NextAndGetResult(). 79 result->may_be_out_of_upper_bound = true; 80 assert(MayBeOutOfUpperBound()); 81 } 82 return is_valid; 83 } 84 85 // Moves to the previous entry in the source. After this call, Valid() is 86 // true iff the iterator was not positioned at the first entry in source. 87 // REQUIRES: Valid() 88 virtual void Prev() = 0; 89 90 // Return the key for the current entry. The underlying storage for 91 // the returned slice is valid only until the next modification of 92 // the iterator. 93 // REQUIRES: Valid() 94 virtual Slice key() const = 0; 95 96 // Return user key for the current entry. 97 // REQUIRES: Valid() user_key()98 virtual Slice user_key() const { return ExtractUserKey(key()); } 99 100 // Return the value for the current entry. The underlying storage for 101 // the returned slice is valid only until the next modification of 102 // the iterator. 103 // REQUIRES: Valid() 104 virtual TValue value() const = 0; 105 106 // If an error has occurred, return it. Else return an ok status. 107 // If non-blocking IO is requested and this operation cannot be 108 // satisfied without doing some IO, then this returns Status::Incomplete(). 109 virtual Status status() const = 0; 110 111 // True if the iterator is invalidated because it reached a key that is above 112 // the iterator upper bound. Used by LevelIterator to decide whether it should 113 // stop or move on to the next file. 114 // Important: if iterator reached the end of the file without encountering any 115 // keys above the upper bound, IsOutOfBound() must return false. IsOutOfBound()116 virtual bool IsOutOfBound() { return false; } 117 118 // Keys return from this iterator can be smaller than iterate_lower_bound. MayBeOutOfLowerBound()119 virtual bool MayBeOutOfLowerBound() { return true; } 120 121 // Keys return from this iterator can be larger or equal to 122 // iterate_upper_bound. MayBeOutOfUpperBound()123 virtual bool MayBeOutOfUpperBound() { return true; } 124 125 // Pass the PinnedIteratorsManager to the Iterator, most Iterators dont 126 // communicate with PinnedIteratorsManager so default implementation is no-op 127 // but for Iterators that need to communicate with PinnedIteratorsManager 128 // they will implement this function and use the passed pointer to communicate 129 // with PinnedIteratorsManager. SetPinnedItersMgr(PinnedIteratorsManager *)130 virtual void SetPinnedItersMgr(PinnedIteratorsManager* /*pinned_iters_mgr*/) { 131 } 132 133 // If true, this means that the Slice returned by key() is valid as long as 134 // PinnedIteratorsManager::ReleasePinnedData is not called and the 135 // Iterator is not deleted. 136 // 137 // IsKeyPinned() is guaranteed to always return true if 138 // - Iterator is created with ReadOptions::pin_data = true 139 // - DB tables were created with BlockBasedTableOptions::use_delta_encoding 140 // set to false. IsKeyPinned()141 virtual bool IsKeyPinned() const { return false; } 142 143 // If true, this means that the Slice returned by value() is valid as long as 144 // PinnedIteratorsManager::ReleasePinnedData is not called and the 145 // Iterator is not deleted. IsValuePinned()146 virtual bool IsValuePinned() const { return false; } 147 GetProperty(std::string,std::string *)148 virtual Status GetProperty(std::string /*prop_name*/, std::string* /*prop*/) { 149 return Status::NotSupported(""); 150 } 151 152 protected: SeekForPrevImpl(const Slice & target,const Comparator * cmp)153 void SeekForPrevImpl(const Slice& target, const Comparator* cmp) { 154 Seek(target); 155 if (!Valid()) { 156 SeekToLast(); 157 } 158 while (Valid() && cmp->Compare(target, key()) < 0) { 159 Prev(); 160 } 161 } 162 163 bool is_mutable_; 164 }; 165 166 using InternalIterator = InternalIteratorBase<Slice>; 167 168 // Return an empty iterator (yields nothing). 169 template <class TValue = Slice> 170 extern InternalIteratorBase<TValue>* NewEmptyInternalIterator(); 171 172 // Return an empty iterator with the specified status. 173 template <class TValue = Slice> 174 extern InternalIteratorBase<TValue>* NewErrorInternalIterator( 175 const Status& status); 176 177 // Return an empty iterator with the specified status, allocated arena. 178 template <class TValue = Slice> 179 extern InternalIteratorBase<TValue>* NewErrorInternalIterator( 180 const Status& status, Arena* arena); 181 182 } // namespace ROCKSDB_NAMESPACE 183