Branch data Line data Source code
# 1 : : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
# 2 : : // Use of this source code is governed by a BSD-style license that can be
# 3 : : // found in the LICENSE file. See the AUTHORS file for names of contributors.
# 4 : :
# 5 : : #include "table/two_level_iterator.h"
# 6 : :
# 7 : : #include "leveldb/table.h"
# 8 : : #include "table/block.h"
# 9 : : #include "table/format.h"
# 10 : : #include "table/iterator_wrapper.h"
# 11 : :
# 12 : : namespace leveldb {
# 13 : :
# 14 : : namespace {
# 15 : :
# 16 : : typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&);
# 17 : :
# 18 : : class TwoLevelIterator : public Iterator {
# 19 : : public:
# 20 : : TwoLevelIterator(Iterator* index_iter, BlockFunction block_function,
# 21 : : void* arg, const ReadOptions& options);
# 22 : :
# 23 : : ~TwoLevelIterator() override;
# 24 : :
# 25 : : void Seek(const Slice& target) override;
# 26 : : void SeekToFirst() override;
# 27 : : void SeekToLast() override;
# 28 : : void Next() override;
# 29 : : void Prev() override;
# 30 : :
# 31 : 693150 : bool Valid() const override { return data_iter_.Valid(); }
# 32 : 149395 : Slice key() const override {
# 33 : 149395 : assert(Valid());
# 34 : 0 : return data_iter_.key();
# 35 : 149395 : }
# 36 : 242488 : Slice value() const override {
# 37 : 242488 : assert(Valid());
# 38 : 0 : return data_iter_.value();
# 39 : 242488 : }
# 40 : 1958 : Status status() const override {
# 41 : : // It'd be nice if status() returned a const Status& instead of a Status
# 42 [ - + ]: 1958 : if (!index_iter_.status().ok()) {
# 43 : 0 : return index_iter_.status();
# 44 [ - + ][ - + ]: 1958 : } else if (data_iter_.iter() != nullptr && !data_iter_.status().ok()) {
# [ # # ]
# 45 : 0 : return data_iter_.status();
# 46 : 1958 : } else {
# 47 : 1958 : return status_;
# 48 : 1958 : }
# 49 : 1958 : }
# 50 : :
# 51 : : private:
# 52 : 3793 : void SaveError(const Status& s) {
# 53 [ + - ][ - + ]: 3793 : if (status_.ok() && !s.ok()) status_ = s;
# 54 : 3793 : }
# 55 : : void SkipEmptyDataBlocksForward();
# 56 : : void SkipEmptyDataBlocksBackward();
# 57 : : void SetDataIterator(Iterator* data_iter);
# 58 : : void InitDataBlock();
# 59 : :
# 60 : : BlockFunction block_function_;
# 61 : : void* arg_;
# 62 : : const ReadOptions options_;
# 63 : : Status status_;
# 64 : : IteratorWrapper index_iter_;
# 65 : : IteratorWrapper data_iter_; // May be nullptr
# 66 : : // If data_iter_ is non-null, then "data_block_handle_" holds the
# 67 : : // "index_value" passed to block_function_ to create the data_iter_.
# 68 : : std::string data_block_handle_;
# 69 : : };
# 70 : :
# 71 : : TwoLevelIterator::TwoLevelIterator(Iterator* index_iter,
# 72 : : BlockFunction block_function, void* arg,
# 73 : : const ReadOptions& options)
# 74 : : : block_function_(block_function),
# 75 : : arg_(arg),
# 76 : : options_(options),
# 77 : : index_iter_(index_iter),
# 78 : 3458 : data_iter_(nullptr) {}
# 79 : :
# 80 : 3458 : TwoLevelIterator::~TwoLevelIterator() = default;
# 81 : :
# 82 : 1907 : void TwoLevelIterator::Seek(const Slice& target) {
# 83 : 1907 : index_iter_.Seek(target);
# 84 : 1907 : InitDataBlock();
# 85 [ + + ]: 1907 : if (data_iter_.iter() != nullptr) data_iter_.Seek(target);
# 86 : 1907 : SkipEmptyDataBlocksForward();
# 87 : 1907 : }
# 88 : :
# 89 : 458 : void TwoLevelIterator::SeekToFirst() {
# 90 : 458 : index_iter_.SeekToFirst();
# 91 : 458 : InitDataBlock();
# 92 [ + - ]: 458 : if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
# 93 : 458 : SkipEmptyDataBlocksForward();
# 94 : 458 : }
# 95 : :
# 96 : 0 : void TwoLevelIterator::SeekToLast() {
# 97 : 0 : index_iter_.SeekToLast();
# 98 : 0 : InitDataBlock();
# 99 [ # # ]: 0 : if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
# 100 : 0 : SkipEmptyDataBlocksBackward();
# 101 : 0 : }
# 102 : :
# 103 : 148396 : void TwoLevelIterator::Next() {
# 104 : 148396 : assert(Valid());
# 105 : 0 : data_iter_.Next();
# 106 : 148396 : SkipEmptyDataBlocksForward();
# 107 : 148396 : }
# 108 : :
# 109 : 0 : void TwoLevelIterator::Prev() {
# 110 : 0 : assert(Valid());
# 111 : 0 : data_iter_.Prev();
# 112 : 0 : SkipEmptyDataBlocksBackward();
# 113 : 0 : }
# 114 : :
# 115 : 150771 : void TwoLevelIterator::SkipEmptyDataBlocksForward() {
# 116 [ + + ][ + + ]: 154564 : while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {
# 117 : : // Move to next block
# 118 [ + + ]: 5178 : if (!index_iter_.Valid()) {
# 119 : 1385 : SetDataIterator(nullptr);
# 120 : 1385 : return;
# 121 : 1385 : }
# 122 : 3793 : index_iter_.Next();
# 123 : 3793 : InitDataBlock();
# 124 [ + + ]: 3793 : if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
# 125 : 3793 : }
# 126 : 150771 : }
# 127 : :
# 128 : 0 : void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
# 129 [ # # ][ # # ]: 0 : while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {
# 130 : : // Move to next block
# 131 [ # # ]: 0 : if (!index_iter_.Valid()) {
# 132 : 0 : SetDataIterator(nullptr);
# 133 : 0 : return;
# 134 : 0 : }
# 135 : 0 : index_iter_.Prev();
# 136 : 0 : InitDataBlock();
# 137 [ # # ]: 0 : if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
# 138 : 0 : }
# 139 : 0 : }
# 140 : :
# 141 : 7543 : void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
# 142 [ + + ]: 7543 : if (data_iter_.iter() != nullptr) SaveError(data_iter_.status());
# 143 : 7543 : data_iter_.Set(data_iter);
# 144 : 7543 : }
# 145 : :
# 146 : 6158 : void TwoLevelIterator::InitDataBlock() {
# 147 [ + + ]: 6158 : if (!index_iter_.Valid()) {
# 148 : 1385 : SetDataIterator(nullptr);
# 149 : 4773 : } else {
# 150 : 4773 : Slice handle = index_iter_.value();
# 151 [ + + ][ - + ]: 4773 : if (data_iter_.iter() != nullptr &&
# 152 [ - + ]: 4773 : handle.compare(data_block_handle_) == 0) {
# 153 : : // data_iter_ is already constructed with this iterator, so
# 154 : : // no need to change anything
# 155 : 4773 : } else {
# 156 : 4773 : Iterator* iter = (*block_function_)(arg_, options_, handle);
# 157 : 4773 : data_block_handle_.assign(handle.data(), handle.size());
# 158 : 4773 : SetDataIterator(iter);
# 159 : 4773 : }
# 160 : 4773 : }
# 161 : 6158 : }
# 162 : :
# 163 : : } // namespace
# 164 : :
# 165 : : Iterator* NewTwoLevelIterator(Iterator* index_iter,
# 166 : : BlockFunction block_function, void* arg,
# 167 : 3457 : const ReadOptions& options) {
# 168 : 3457 : return new TwoLevelIterator(index_iter, block_function, arg, options);
# 169 : 3457 : }
# 170 : :
# 171 : : } // namespace leveldb
|
