1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include "posting_priority_queue.hpp"
#include "posting_priority_queue_merger.h"
namespace search {
template <class Reader, class Writer>
void
PostingPriorityQueueMerger<Reader, Writer>::mergeHeap(Writer& writer, const IFlushToken& flush_token, uint32_t remaining_merge_chunk)
{
while (remaining_merge_chunk > 0u && !empty() && !flush_token.stop_requested()) {
Reader *low = lowest();
low->write(writer);
low->read();
adjust();
--remaining_merge_chunk;
}
}
template <class Reader, class Writer>
void
PostingPriorityQueueMerger<Reader, Writer>::mergeOne(Writer& writer, Reader& reader, const IFlushToken& flush_token, uint32_t remaining_merge_chunk)
{
while (remaining_merge_chunk > 0u && reader.isValid() && !flush_token.stop_requested()) {
reader.write(writer);
reader.read();
--remaining_merge_chunk;
}
}
template <class Reader, class Writer>
void
PostingPriorityQueueMerger<Reader, Writer>::mergeTwo(Writer& writer, Reader& reader1, Reader& reader2, const IFlushToken& flush_token, uint32_t& remaining_merge_chunk)
{
while (remaining_merge_chunk > 0u && !flush_token.stop_requested()) {
Reader &low = reader2 < reader1 ? reader2 : reader1;
low.write(writer);
low.read();
--remaining_merge_chunk;
if (!low.isValid()) {
break;
}
}
}
template <class Reader, class Writer>
void
PostingPriorityQueueMerger<Reader, Writer>::mergeSmall(Writer& writer, typename Vector::iterator ib, typename Vector::iterator ie, const IFlushToken& flush_token, uint32_t& remaining_merge_chunk)
{
while (remaining_merge_chunk > 0u && !flush_token.stop_requested()) {
typename Vector::iterator i = ib;
Reader *low = i->get();
for (++i; i != ie; ++i)
if (*i->get() < *low)
low = i->get();
low->write(writer);
low->read();
--remaining_merge_chunk;
if (!low->isValid()) {
break;
}
}
}
template <class Reader, class Writer>
void
PostingPriorityQueueMerger<Reader, Writer>::merge(Writer& writer, const IFlushToken& flush_token)
{
if (_vec.empty())
return;
assert(_heap_limit > 0u);
uint32_t remaining_merge_chunk = _merge_chunk;
if (_vec.size() >= _heap_limit) {
void (PostingPriorityQueueMerger::*mergeHeapFunc)(Writer& writer, const IFlushToken& flush_token, uint32_t remaining_merge_chunk) =
&PostingPriorityQueueMerger::mergeHeap;
(this->*mergeHeapFunc)(writer, flush_token, remaining_merge_chunk);
return;
}
while (remaining_merge_chunk > 0u && !flush_token.stop_requested()) {
if (_vec.size() == 1) {
void (*mergeOneFunc)(Writer& writer, Reader& reader, const IFlushToken& flush_token, uint32_t remaining_merge_chunk) =
&PostingPriorityQueueMerger::mergeOne;
(*mergeOneFunc)(writer, *_vec.front().get(), flush_token, remaining_merge_chunk);
if (!_vec.front().get()->isValid()) {
_vec.clear();
}
return;
}
if (_vec.size() == 2) {
void (*mergeTwoFunc)(Writer& writer, Reader& reader1, Reader& reader2, const IFlushToken& flush_token, uint32_t& remaining_merge_chunk) =
&PostingPriorityQueueMerger::mergeTwo;
(*mergeTwoFunc)(writer, *_vec[0].get(), *_vec[1].get(), flush_token, remaining_merge_chunk);
} else {
void (*mergeSmallFunc)(Writer& writer,
typename Vector::iterator ib,
typename Vector::iterator ie,
const IFlushToken& flush_token,
uint32_t& remaining_merge_chunk) =
&PostingPriorityQueueMerger::mergeSmall;
(*mergeSmallFunc)(writer, _vec.begin(), _vec.end(), flush_token, remaining_merge_chunk);
}
for (typename Vector::iterator i = _vec.begin(), ie = _vec.end();
i != ie; ++i) {
if (!i->get()->isValid()) {
_vec.erase(i);
break;
}
}
for (typename Vector::iterator i = _vec.begin(), ie = _vec.end();
i != ie; ++i) {
assert(i->get()->isValid());
}
assert(!_vec.empty());
}
}
}
|
