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 : 85 : MergingIterator(const Comparator* comparator, Iterator** children, int n)
17 : 170 : : comparator_(comparator),
18 [ + - + + ]: 362 : children_(new IteratorWrapper[n]),
19 : 85 : n_(n),
20 : 85 : current_(nullptr),
21 [ + - ]: 85 : direction_(kForward) {
22 [ + + ]: 362 : for (int i = 0; i < n; i++) {
23 [ + - ]: 277 : children_[i].Set(children[i]);
24 : : }
25 : 85 : }
26 : :
27 [ + - + + ]: 447 : ~MergingIterator() override { delete[] children_; }
28 : :
29 : 72368 : bool Valid() const override { return (current_ != nullptr); }
30 : :
31 : 14 : void SeekToFirst() override {
32 [ + + ]: 66 : for (int i = 0; i < n_; i++) {
33 : 52 : children_[i].SeekToFirst();
34 : : }
35 : 14 : FindSmallest();
36 : 14 : direction_ = kForward;
37 : 14 : }
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 : 71 : void Seek(const Slice& target) override {
48 [ + + ]: 296 : for (int i = 0; i < n_; i++) {
49 : 225 : children_[i].Seek(target);
50 : : }
51 : 71 : FindSmallest();
52 : 71 : direction_ = kForward;
53 : 71 : }
54 : :
55 : 10318 : void Next() override {
56 [ - + ]: 10318 : 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 [ - + ]: 10318 : 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 : 10318 : current_->Next();
78 : 10318 : FindSmallest();
79 : 10318 : }
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 : 25904 : Slice key() const override {
111 [ - + ]: 25904 : assert(Valid());
112 : 25904 : return current_->key();
113 : : }
114 : :
115 : 17897 : Slice value() const override {
116 [ - + ]: 17897 : assert(Valid());
117 : 17897 : return current_->value();
118 : : }
119 : :
120 : 22 : Status status() const override {
121 : 22 : Status status;
122 [ + + ]: 110 : for (int i = 0; i < n_; i++) {
123 [ + - - + ]: 88 : status = children_[i].status();
124 [ + - ]: 88 : if (!status.ok()) {
125 : : break;
126 : : }
127 : : }
128 : 22 : 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 : 10403 : void MergingIterator::FindSmallest() {
149 : 10403 : IteratorWrapper* smallest = nullptr;
150 [ + + ]: 43241 : for (int i = 0; i < n_; i++) {
151 : 32838 : IteratorWrapper* child = &children_[i];
152 [ + + ]: 32838 : if (child->Valid()) {
153 [ + + ]: 30317 : if (smallest == nullptr) {
154 : : smallest = child;
155 [ + + ]: 19987 : } else if (comparator_->Compare(child->key(), smallest->key()) < 0) {
156 : 7098 : smallest = child;
157 : : }
158 : : }
159 : : }
160 : 10403 : current_ = smallest;
161 : 10403 : }
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 : 1136 : Iterator* NewMergingIterator(const Comparator* comparator, Iterator** children,
180 : : int n) {
181 [ - + ]: 1136 : assert(n >= 0);
182 [ - + ]: 1136 : if (n == 0) {
183 : 0 : return NewEmptyIterator();
184 [ + + ]: 1136 : } else if (n == 1) {
185 : 1051 : return children[0];
186 : : } else {
187 [ + - ]: 85 : return new MergingIterator(comparator, children, n);
188 : : }
189 : : }
190 : :
191 : : } // namespace leveldb
|
