/root/bitcoin/src/leveldb/table/merger.cc

Source
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "table/merger.h"

#include "leveldb/comparator.h"
#include "leveldb/iterator.h"
#include "table/iterator_wrapper.h"

namespace leveldb {

namespace {
class MergingIterator : public Iterator {
 public:
  MergingIterator(const Comparator* comparator, Iterator** children, int n)
      : comparator_(comparator),
        children_(new IteratorWrapper[n]),
        n_(n),
        current_(nullptr),
        direction_(kForward) {
    for (int i = 0; i < n; i++) {
      children_[i].Set(children[i]);
    }
  }

  ~MergingIterator() override { delete[] children_; }

  bool Valid() const override { return (current_ != nullptr); }

  void SeekToFirst() override {
    for (int i = 0; i < n_; i++) {
      children_[i].SeekToFirst();
    }
    FindSmallest();
    direction_ = kForward;
  }

  void SeekToLast() override {
    for (int i = 0; i < n_; i++) {
      children_[i].SeekToLast();
    }
    FindLargest();
    direction_ = kReverse;
  }

  void Seek(const Slice& target) override {
    for (int i = 0; i < n_; i++) {
      children_[i].Seek(target);
    }
    FindSmallest();
    direction_ = kForward;
  }

  void Next() override {
    assert(Valid());

    // Ensure that all children are positioned after key().
    // If we are moving in the forward direction, it is already
    // true for all of the non-current_ children since current_ is
    // the smallest child and key() == current_->key().  Otherwise,
    // we explicitly position the non-current_ children.
    if (direction_ != kForward) {
      for (int i = 0; i < n_; i++) {
        IteratorWrapper* child = &children_[i];
        if (child != current_) {
          child->Seek(key());
          if (child->Valid() &&
              comparator_->Compare(key(), child->key()) == 0) {
            child->Next();
          }
        }
      }
      direction_ = kForward;
    }

    current_->Next();
    FindSmallest();
  }

  void Prev() override {
    assert(Valid());

    // Ensure that all children are positioned before key().
    // If we are moving in the reverse direction, it is already
    // true for all of the non-current_ children since current_ is
    // the largest child and key() == current_->key().  Otherwise,
    // we explicitly position the non-current_ children.
    if (direction_ != kReverse) {
      for (int i = 0; i < n_; i++) {
        IteratorWrapper* child = &children_[i];
        if (child != current_) {
          child->Seek(key());
          if (child->Valid()) {
            // Child is at first entry >= key().  Step back one to be < key()
            child->Prev();
          } else {
            // Child has no entries >= key().  Position at last entry.
            child->SeekToLast();
          }
        }
      }
      direction_ = kReverse;
    }

    current_->Prev();
    FindLargest();
  }

  Slice key() const override {
    assert(Valid());
    return current_->key();
  }

  Slice value() const override {
    assert(Valid());
    return current_->value();
  }

  Status status() const override {
    Status status;
    for (int i = 0; i < n_; i++) {
      status = children_[i].status();
      if (!status.ok()) {
        break;
      }
    }
    return status;
  }

 private:
  // Which direction is the iterator moving?
  enum Direction { kForward, kReverse };

  void FindSmallest();
  void FindLargest();

  // We might want to use a heap in case there are lots of children.
  // For now we use a simple array since we expect a very small number
  // of children in leveldb.
  const Comparator* comparator_;
  IteratorWrapper* children_;
  int n_;
  IteratorWrapper* current_;
  Direction direction_;
};

void MergingIterator::FindSmallest() {
  IteratorWrapper* smallest = nullptr;
  for (int i = 0; i < n_; i++) {
    IteratorWrapper* child = &children_[i];
    if (child->Valid()) {
      if (smallest == nullptr) {
        smallest = child;
      } else if (comparator_->Compare(child->key(), smallest->key()) < 0) {
        smallest = child;
      }
    }
  }
  current_ = smallest;
}

void MergingIterator::FindLargest() {
  IteratorWrapper* largest = nullptr;
  for (int i = n_ - 1; i >= 0; i--) {
    IteratorWrapper* child = &children_[i];
    if (child->Valid()) {
      if (largest == nullptr) {
        largest = child;
      } else if (comparator_->Compare(child->key(), largest->key()) > 0) {
        largest = child;
      }
    }
  }
  current_ = largest;
}
}  // namespace

Iterator* NewMergingIterator(const Comparator* comparator, Iterator** children,
                             int n) {
  assert(n >= 0);
  if (n == 0) {
    return NewEmptyIterator();
  } else if (n == 1) {
    return children[0];
  } else {
    return new MergingIterator(comparator, children, n);
  }
}

}  // namespace leveldb

Line	Count	Source
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	254k	: comparator_(comparator),
18	254k	children_(new IteratorWrapper[n]),
19	254k	n_(n),
20	254k	current_(nullptr),
21	254k	direction_(kForward) {
22	997k	for (int i = 0; i < n; i++) { Branch (22:21): [True: 742k, False: 254k]
23	742k	children_[i].Set(children[i]);
24	742k	}
25	254k	}
26
27	254k	~MergingIterator() override { delete[] children_; }
28
29	89.1M	bool Valid() const override { return (current_ != nullptr); }
30
31	210k	void SeekToFirst() override {
32	834k	for (int i = 0; i < n_; i++) { Branch (32:21): [True: 624k, False: 210k]
33	624k	children_[i].SeekToFirst();
34	624k	}
35	210k	FindSmallest();
36	210k	direction_ = kForward;
37	210k	}
38
39	0	void SeekToLast() override {
40	0	for (int i = 0; i < n_; i++) { Branch (40:21): [True: 0, False: 0]
41	0	children_[i].SeekToLast();
42	0	}
43	0	FindLargest();
44	0	direction_ = kReverse;
45	0	}
46
47	75.2k	void Seek(const Slice& target) override {
48	296k	for (int i = 0; i < n_; i++) { Branch (48:21): [True: 220k, False: 75.2k]
49	220k	children_[i].Seek(target);
50	220k	}
51	75.2k	FindSmallest();
52	75.2k	direction_ = kForward;
53	75.2k	}
54
55	21.9M	void Next() override {
56	21.9M	assert(Valid()); Branch (56:5): [True: 21.9M, False: 18.4E]
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	21.9M	if (direction_ != kForward) { Branch (63:9): [True: 0, False: 21.9M]
64	0	for (int i = 0; i < n_; i++) { Branch (64:23): [True: 0, False: 0]
65	0	IteratorWrapper* child = &children_[i];
66	0	if (child != current_) { Branch (66:13): [True: 0, False: 0]
67	0	child->Seek(key());
68	0	if (child->Valid() && Branch (68:15): [True: 0, False: 0] Branch (68:15): [True: 0, False: 0]
69	0	comparator_->Compare(key(), child->key()) == 0) { Branch (69:15): [True: 0, False: 0]
70	0	child->Next();
71	0	}
72	0	}
73	0	}
74	0	direction_ = kForward;
75	0	}
76
77	21.9M	current_->Next();
78	21.9M	FindSmallest();
79	21.9M	}
80
81	0	void Prev() override {
82	0	assert(Valid()); Branch (82:5): [True: 0, False: 0]
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) { Branch (89:9): [True: 0, False: 0]
90	0	for (int i = 0; i < n_; i++) { Branch (90:23): [True: 0, False: 0]
91	0	IteratorWrapper* child = &children_[i];
92	0	if (child != current_) { Branch (92:13): [True: 0, False: 0]
93	0	child->Seek(key());
94	0	if (child->Valid()) { Branch (94:15): [True: 0, False: 0]
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	27.9M	Slice key() const override {
111	27.9M	assert(Valid()); Branch (111:5): [True: 27.9M, False: 18.4E]
112	27.9M	return current_->key();
113	27.9M	}
114
115	14.0M	Slice value() const override {
116	14.0M	assert(Valid()); Branch (116:5): [True: 14.0M, False: 18.4E]
117	14.0M	return current_->value();
118	14.0M	}
119
120	228k	Status status() const override {
121	228k	Status status;
122	750k	for (int i = 0; i < n_; i++) { Branch (122:21): [True: 522k, False: 228k]
123	522k	status = children_[i].status();
124	522k	if (!status.ok()) { Branch (124:11): [True: 0, False: 522k]
125	0	break;
126	0	}
127	522k	}
128	228k	return status;
129	228k	}
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	22.2M	void MergingIterator::FindSmallest() {
149	22.2M	IteratorWrapper* smallest = nullptr;
150	80.9M	for (int i = 0; i < n_; i++) { Branch (150:19): [True: 58.7M, False: 22.2M]
151	58.7M	IteratorWrapper* child = &children_[i];
152	58.7M	if (child->Valid()) { Branch (152:9): [True: 43.2M, False: 15.5M]
153	43.2M	if (smallest == nullptr) { Branch (153:11): [True: 22.0M, False: 21.2M]
154	22.0M	smallest = child;
155	22.0M	} else if (comparator_->Compare(child->key(), smallest->key()) < 0) { Branch (155:18): [True: 5.69M, False: 15.5M]
156	5.69M	smallest = child;
157	5.69M	}
158	43.2M	}
159	58.7M	}
160	22.2M	current_ = smallest;
161	22.2M	}
162
163	0	void MergingIterator::FindLargest() {
164	0	IteratorWrapper* largest = nullptr;
165	0	for (int i = n_ - 1; i >= 0; i--) { Branch (165:24): [True: 0, False: 0]
166	0	IteratorWrapper* child = &children_[i];
167	0	if (child->Valid()) { Branch (167:9): [True: 0, False: 0]
168	0	if (largest == nullptr) { Branch (168:11): [True: 0, False: 0]
169	0	largest = child;
170	0	} else if (comparator_->Compare(child->key(), largest->key()) > 0) { Branch (170:18): [True: 0, False: 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	395k	int n) {
181	395k	assert(n >= 0); Branch (181:3): [True: 395k, False: 0]
182	395k	if (n == 0) { Branch (182:7): [True: 0, False: 395k]
183	0	return NewEmptyIterator();
184	395k	} else if (n == 1) { Branch (184:14): [True: 140k, False: 254k]
185	140k	return children[0];
186	254k	} else {
187	254k	return new MergingIterator(comparator, children, n);
188	254k	}
189	395k	}
190
191		} // namespace leveldb

Coverage Report

Created: 2026-09-01 13:33