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 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 #pragma once
10 #include "table/block_based/block_based_table_reader.h"
11 
12 #include "table/block_based/block_based_table_reader_impl.h"
13 #include "table/block_based/block_prefetcher.h"
14 #include "table/block_based/reader_common.h"
15 
16 namespace ROCKSDB_NAMESPACE {
17 // Iterator that iterates over partitioned index.
18 // Some upper and lower bound tricks played in block based table iterators
19 // could be played here, but it's too complicated to reason about index
20 // keys with upper or lower bound, so we skip it for simplicity.
21 class ParititionedIndexIterator : public InternalIteratorBase<IndexValue> {
22   // compaction_readahead_size: its value will only be used if for_compaction =
23   // true
24  public:
25   ParititionedIndexIterator(
26       const BlockBasedTable* table, const ReadOptions& read_options,
27       const InternalKeyComparator& icomp,
28       std::unique_ptr<InternalIteratorBase<IndexValue>>&& index_iter,
29       TableReaderCaller caller, size_t compaction_readahead_size = 0)
table_(table)30       : table_(table),
31         read_options_(read_options),
32 #ifndef NDEBUG
33         icomp_(icomp),
34 #endif
35         user_comparator_(icomp.user_comparator()),
36         index_iter_(std::move(index_iter)),
37         block_iter_points_to_real_block_(false),
38         lookup_context_(caller),
39         block_prefetcher_(compaction_readahead_size) {}
40 
~ParititionedIndexIterator()41   ~ParititionedIndexIterator() {}
42 
43   void Seek(const Slice& target) override;
SeekForPrev(const Slice &)44   void SeekForPrev(const Slice&) override {
45     // Shouldn't be called.
46     assert(false);
47   }
48   void SeekToFirst() override;
49   void SeekToLast() override;
50   void Next() final override;
NextAndGetResult(IterateResult *)51   bool NextAndGetResult(IterateResult*) override {
52     assert(false);
53     return false;
54   }
55   void Prev() override;
Valid()56   bool Valid() const override {
57     return block_iter_points_to_real_block_ && block_iter_.Valid();
58   }
key()59   Slice key() const override {
60     assert(Valid());
61     return block_iter_.key();
62   }
user_key()63   Slice user_key() const override {
64     assert(Valid());
65     return block_iter_.user_key();
66   }
value()67   IndexValue value() const override {
68     assert(Valid());
69     return block_iter_.value();
70   }
status()71   Status status() const override {
72     // Prefix index set status to NotFound when the prefix does not exist
73     if (!index_iter_->status().ok() && !index_iter_->status().IsNotFound()) {
74       return index_iter_->status();
75     } else if (block_iter_points_to_real_block_) {
76       return block_iter_.status();
77     } else {
78       return Status::OK();
79     }
80   }
81 
82   // Whether iterator invalidated for being out of bound.
IsOutOfBound()83   bool IsOutOfBound() override {
84     // Shoulldn't be called
85     assert(false);
86     return false;
87   }
88 
MayBeOutOfUpperBound()89   inline bool MayBeOutOfUpperBound() override {
90     // Shouldn't be called.
91     assert(false);
92     return true;
93   }
SetPinnedItersMgr(PinnedIteratorsManager *)94   void SetPinnedItersMgr(PinnedIteratorsManager*) override {
95     // Shouldn't be called.
96     assert(false);
97   }
IsKeyPinned()98   bool IsKeyPinned() const override {
99     // Shouldn't be called.
100     assert(false);
101     return false;
102   }
IsValuePinned()103   bool IsValuePinned() const override {
104     // Shouldn't be called.
105     assert(false);
106     return false;
107   }
108 
ResetPartitionedIndexIter()109   void ResetPartitionedIndexIter() {
110     if (block_iter_points_to_real_block_) {
111       block_iter_.Invalidate(Status::OK());
112       block_iter_points_to_real_block_ = false;
113     }
114   }
115 
SavePrevIndexValue()116   void SavePrevIndexValue() {
117     if (block_iter_points_to_real_block_) {
118       // Reseek. If they end up with the same data block, we shouldn't re-fetch
119       // the same data block.
120       prev_block_offset_ = index_iter_->value().handle.offset();
121     }
122   }
123 
124  private:
125   const BlockBasedTable* table_;
126   const ReadOptions read_options_;
127 #ifndef NDEBUG
128   const InternalKeyComparator& icomp_;
129 #endif
130   UserComparatorWrapper user_comparator_;
131   std::unique_ptr<InternalIteratorBase<IndexValue>> index_iter_;
132   IndexBlockIter block_iter_;
133 
134   // True if block_iter_ is initialized and points to the same block
135   // as index iterator.
136   bool block_iter_points_to_real_block_;
137   uint64_t prev_block_offset_ = std::numeric_limits<uint64_t>::max();
138   BlockCacheLookupContext lookup_context_;
139   BlockPrefetcher block_prefetcher_;
140 
141   // If `target` is null, seek to first.
142   void SeekImpl(const Slice* target);
143 
144   void InitPartitionedIndexBlock();
145   void FindKeyForward();
146   void FindBlockForward();
147   void FindKeyBackward();
148 };
149 }  // namespace ROCKSDB_NAMESPACE
150