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