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/merger.h" # 6 : : # 7 : : #include "leveldb/comparator.h" # 8 : : #include "leveldb/iterator.h" # 9 : : #include "table/iterator_wrapper.h" # 10 : : # 11 : : namespace leveldb { # 12 : : # 13 : : namespace { # 14 : : class MergingIterator : public Iterator { # 15 : : public: # 16 : : MergingIterator(const Comparator* comparator, Iterator** children, int n) # 17 : : : comparator_(comparator), # 18 : : children_(new IteratorWrapper[n]), # 19 : : n_(n), # 20 : : current_(nullptr), # 21 : 1106 : direction_(kForward) { # 22 [ + + ]: 4072 : for (int i = 0; i < n; i++) { # 23 : 2966 : children_[i].Set(children[i]); # 24 : 2966 : } # 25 : 1106 : } # 26 : : # 27 : 1106 : ~MergingIterator() override { delete[] children_; } # 28 : : # 29 : 672310 : bool Valid() const override { return (current_ != nullptr); } # 30 : : # 31 : 75 : void SeekToFirst() override { # 32 [ + + ]: 350 : for (int i = 0; i < n_; i++) { # 33 : 275 : children_[i].SeekToFirst(); # 34 : 275 : } # 35 : 75 : FindSmallest(); # 36 : 75 : direction_ = kForward; # 37 : 75 : } # 38 : : # 39 : 0 : void SeekToLast() override { # 40 [ # # ]: 0 : for (int i = 0; i < n_; i++) { # 41 : 0 : children_[i].SeekToLast(); # 42 : 0 : } # 43 : 0 : FindLargest(); # 44 : 0 : direction_ = kReverse; # 45 : 0 : } # 46 : : # 47 : 1031 : void Seek(const Slice& target) override { # 48 [ + + ]: 3722 : for (int i = 0; i < n_; i++) { # 49 : 2691 : children_[i].Seek(target); # 50 : 2691 : } # 51 : 1031 : FindSmallest(); # 52 : 1031 : direction_ = kForward; # 53 : 1031 : } # 54 : : # 55 : 95463 : void Next() override { # 56 : 95463 : assert(Valid()); # 57 : : # 58 : : // Ensure that all children are positioned after key(). # 59 : : // If we are moving in the forward direction, it is already # 60 : : // true for all of the non-current_ children since current_ is # 61 : : // the smallest child and key() == current_->key(). Otherwise, # 62 : : // we explicitly position the non-current_ children. # 63 [ - + ]: 95463 : if (direction_ != kForward) { # 64 [ # # ]: 0 : for (int i = 0; i < n_; i++) { # 65 : 0 : IteratorWrapper* child = &children_[i]; # 66 [ # # ]: 0 : if (child != current_) { # 67 : 0 : child->Seek(key()); # 68 [ # # ][ # # ]: 0 : if (child->Valid() && # 69 [ # # ]: 0 : comparator_->Compare(key(), child->key()) == 0) { # 70 : 0 : child->Next(); # 71 : 0 : } # 72 : 0 : } # 73 : 0 : } # 74 : 0 : direction_ = kForward; # 75 : 0 : } # 76 : : # 77 : 95463 : current_->Next(); # 78 : 95463 : FindSmallest(); # 79 : 95463 : } # 80 : : # 81 : 0 : void Prev() override { # 82 : 0 : assert(Valid()); # 83 : : # 84 : : // Ensure that all children are positioned before key(). # 85 : : // If we are moving in the reverse direction, it is already # 86 : : // true for all of the non-current_ children since current_ is # 87 : : // the largest child and key() == current_->key(). Otherwise, # 88 : : // we explicitly position the non-current_ children. # 89 [ # # ]: 0 : if (direction_ != kReverse) { # 90 [ # # ]: 0 : for (int i = 0; i < n_; i++) { # 91 : 0 : IteratorWrapper* child = &children_[i]; # 92 [ # # ]: 0 : if (child != current_) { # 93 : 0 : child->Seek(key()); # 94 [ # # ]: 0 : if (child->Valid()) { # 95 : : // Child is at first entry >= key(). Step back one to be < key() # 96 : 0 : child->Prev(); # 97 : 0 : } else { # 98 : : // Child has no entries >= key(). Position at last entry. # 99 : 0 : child->SeekToLast(); # 100 : 0 : } # 101 : 0 : } # 102 : 0 : } # 103 : 0 : direction_ = kReverse; # 104 : 0 : } # 105 : : # 106 : 0 : current_->Prev(); # 107 : 0 : FindLargest(); # 108 : 0 : } # 109 : : # 110 : 241329 : Slice key() const override { # 111 : 241329 : assert(Valid()); # 112 : 241329 : return current_->key(); # 113 : 241329 : } # 114 : : # 115 : 166174 : Slice value() const override { # 116 : 166174 : assert(Valid()); # 117 : 166174 : return current_->value(); # 118 : 166174 : } # 119 : : # 120 : 142 : Status status() const override { # 121 : 142 : Status status; # 122 [ + + ]: 676 : for (int i = 0; i < n_; i++) { # 123 : 534 : status = children_[i].status(); # 124 [ - + ]: 534 : if (!status.ok()) { # 125 : 0 : break; # 126 : 0 : } # 127 : 534 : } # 128 : 142 : return status; # 129 : 142 : } # 130 : : # 131 : : private: # 132 : : // Which direction is the iterator moving? # 133 : : enum Direction { kForward, kReverse }; # 134 : : # 135 : : void FindSmallest(); # 136 : : void FindLargest(); # 137 : : # 138 : : // We might want to use a heap in case there are lots of children. # 139 : : // For now we use a simple array since we expect a very small number # 140 : : // of children in leveldb. # 141 : : const Comparator* comparator_; # 142 : : IteratorWrapper* children_; # 143 : : int n_; # 144 : : IteratorWrapper* current_; # 145 : : Direction direction_; # 146 : : }; # 147 : : # 148 : 96573 : void MergingIterator::FindSmallest() { # 149 : 96573 : IteratorWrapper* smallest = nullptr; # 150 [ + + ]: 362766 : for (int i = 0; i < n_; i++) { # 151 : 266193 : IteratorWrapper* child = &children_[i]; # 152 [ + + ]: 266193 : if (child->Valid()) { # 153 [ + + ]: 198704 : if (smallest == nullptr) { # 154 : 96074 : smallest = child; # 155 [ + + ]: 102630 : } else if (comparator_->Compare(child->key(), smallest->key()) < 0) { # 156 : 24824 : smallest = child; # 157 : 24824 : } # 158 : 198704 : } # 159 : 266193 : } # 160 : 96573 : current_ = smallest; # 161 : 96573 : } # 162 : : # 163 : 0 : void MergingIterator::FindLargest() { # 164 : 0 : IteratorWrapper* largest = nullptr; # 165 [ # # ]: 0 : for (int i = n_ - 1; i >= 0; i--) { # 166 : 0 : IteratorWrapper* child = &children_[i]; # 167 [ # # ]: 0 : if (child->Valid()) { # 168 [ # # ]: 0 : if (largest == nullptr) { # 169 : 0 : largest = child; # 170 [ # # ]: 0 : } else if (comparator_->Compare(child->key(), largest->key()) > 0) { # 171 : 0 : largest = child; # 172 : 0 : } # 173 : 0 : } # 174 : 0 : } # 175 : 0 : current_ = largest; # 176 : 0 : } # 177 : : } // namespace # 178 : : # 179 : : Iterator* NewMergingIterator(const Comparator* comparator, Iterator** children, # 180 : 2973 : int n) { # 181 : 2973 : assert(n >= 0); # 182 [ - + ]: 2973 : if (n == 0) { # 183 : 0 : return NewEmptyIterator(); # 184 [ + + ]: 2973 : } else if (n == 1) { # 185 : 1867 : return children[0]; # 186 : 1867 : } else { # 187 : 1106 : return new MergingIterator(comparator, children, n); # 188 : 1106 : } # 189 : 2973 : } # 190 : : # 191 : : } // namespace leveldb