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