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 : 2900 : MergingIterator(const Comparator* comparator, Iterator** children, int n)
17 : 5800 : : comparator_(comparator),
18 [ + - + + ]: 11138 : children_(new IteratorWrapper[n]),
19 : 2900 : n_(n),
20 : 2900 : current_(nullptr),
21 [ + - ]: 2900 : direction_(kForward) {
22 [ + + ]: 11138 : for (int i = 0; i < n; i++) {
23 [ + - ]: 8238 : children_[i].Set(children[i]);
24 : : }
25 : 2900 : }
26 : :
27 [ + - + + ]: 14038 : ~MergingIterator() override { delete[] children_; }
28 : :
29 : 3892829 : bool Valid() const override { return (current_ != nullptr); }
30 : :
31 : 295 : void SeekToFirst() override {
32 [ + + ]: 1394 : for (int i = 0; i < n_; i++) {
33 : 1099 : children_[i].SeekToFirst();
34 : : }
35 : 295 : FindSmallest();
36 : 295 : direction_ = kForward;
37 : 295 : }
38 : :
39 : 0 : void SeekToLast() override {
40 [ # # ]: 0 : for (int i = 0; i < n_; i++) {
41 : 0 : children_[i].SeekToLast();
42 : : }
43 : 0 : FindLargest();
44 : 0 : direction_ = kReverse;
45 : 0 : }
46 : :
47 : 2605 : void Seek(const Slice& target) override {
48 [ + + ]: 9744 : for (int i = 0; i < n_; i++) {
49 : 7139 : children_[i].Seek(target);
50 : : }
51 : 2605 : FindSmallest();
52 : 2605 : direction_ = kForward;
53 : 2605 : }
54 : :
55 : 617363 : void Next() override {
56 [ - + ]: 617363 : 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 [ - + ]: 617363 : 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 : : }
72 : : }
73 : : }
74 : 0 : direction_ = kForward;
75 : : }
76 : :
77 : 617363 : current_->Next();
78 : 617363 : FindSmallest();
79 : 617363 : }
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 : : } else {
98 : : // Child has no entries >= key(). Position at last entry.
99 : 0 : child->SeekToLast();
100 : : }
101 : : }
102 : : }
103 : 0 : direction_ = kReverse;
104 : : }
105 : :
106 : 0 : current_->Prev();
107 : 0 : FindLargest();
108 : 0 : }
109 : :
110 : 1335606 : Slice key() const override {
111 [ - + ]: 1335606 : assert(Valid());
112 : 1335606 : return current_->key();
113 : : }
114 : :
115 : 959572 : Slice value() const override {
116 [ - + ]: 959572 : assert(Valid());
117 : 959572 : return current_->value();
118 : : }
119 : :
120 : 584 : Status status() const override {
121 : 584 : Status status;
122 [ + + ]: 2766 : for (int i = 0; i < n_; i++) {
123 [ + - - + ]: 2182 : status = children_[i].status();
124 [ + - ]: 2182 : if (!status.ok()) {
125 : : break;
126 : : }
127 : : }
128 : 584 : return status;
129 : 0 : }
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 : 620263 : void MergingIterator::FindSmallest() {
149 : 620263 : IteratorWrapper* smallest = nullptr;
150 [ + + ]: 2213977 : for (int i = 0; i < n_; i++) {
151 : 1593714 : IteratorWrapper* child = &children_[i];
152 [ + + ]: 1593714 : if (child->Valid()) {
153 [ + + ]: 1253254 : if (smallest == nullptr) {
154 : : smallest = child;
155 [ + + ]: 634949 : } else if (comparator_->Compare(child->key(), smallest->key()) < 0) {
156 : 286918 : smallest = child;
157 : : }
158 : : }
159 : : }
160 : 620263 : current_ = smallest;
161 : 620263 : }
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 : : largest = child;
170 [ # # ]: 0 : } else if (comparator_->Compare(child->key(), largest->key()) > 0) {
171 : 0 : largest = child;
172 : : }
173 : : }
174 : : }
175 : 0 : current_ = largest;
176 : 0 : }
177 : : } // namespace
178 : :
179 : 5326 : Iterator* NewMergingIterator(const Comparator* comparator, Iterator** children,
180 : : int n) {
181 [ - + ]: 5326 : assert(n >= 0);
182 [ - + ]: 5326 : if (n == 0) {
183 : 0 : return NewEmptyIterator();
184 [ + + ]: 5326 : } else if (n == 1) {
185 : 2426 : return children[0];
186 : : } else {
187 [ + - ]: 2900 : return new MergingIterator(comparator, children, n);
188 : : }
189 : : }
190 : :
191 : : } // namespace leveldb
|
