14 #ifndef STXXL_LOSERTREE_HEADER
15 #define STXXL_LOSERTREE_HEADER
17 #include <stxxl/bits/noncopyable.h>
18 #include <stxxl/bits/common/utils.h>
21 __STXXL_BEGIN_NAMESPACE
23 template <
typename run_cursor_type,
24 typename run_cursor_cmp_type,
26 class loser_tree :
private noncopyable
31 run_cursor_type * current;
32 run_cursor_cmp_type cmp;
34 int_type init_winner(int_type root)
42 int_type left = init_winner(2 * root);
43 int_type right = init_winner(2 * root + 1);
44 if (cmp(current[left], current[right]))
58 typedef typename run_cursor_type::prefetcher_type prefetcher_type;
59 typedef typename run_cursor_type::value_type value_type;
64 run_cursor_cmp_type c) : cmp(c)
67 logK =
static_cast<int>(ceil(log(
double(nruns)) / log(2.)));
68 int_type kReg = k = (1 << logK);
70 STXXL_VERBOSE2(
"loser_tree: logK=" << logK <<
" nruns=" << nruns <<
" K=" << kReg);
72 #ifdef STXXL_SORT_SINGLE_PREFETCHER
73 current =
new run_cursor_type[kReg];
74 run_cursor_type::set_prefetcher(p);
76 current =
new run_cursor_type[kReg];
77 for (i = 0; i < kReg; ++i)
78 current[i].prefetcher() = p;
81 entry =
new int_type[(kReg << 1)];
83 for (i = 0; i < nruns; ++i)
85 current[i].buffer = p->pull_block();
90 for (i = nruns; i < kReg; ++i)
92 current[i].make_inf();
96 entry[0] = init_winner(1);
104 void swap(loser_tree & obj)
106 std::swap(logK, obj.logK);
108 std::swap(entry, obj.entry);
109 std::swap(current, obj.current);
110 std::swap(cmp, obj.cmp);
114 template <
unsigned LogK>
115 void multi_merge_unrolled(value_type * to)
117 run_cursor_type * currentE, * winnerE;
118 int_type * regEntry = entry;
119 value_type * done = to + buffer_size;
120 int_type winnerIndex = regEntry[0];
122 while (LIKELY(to < done))
124 winnerE = current + winnerIndex;
125 *(to++) = winnerE->current();
130 #define TreeStep(L) \
133 currentE = current + \
134 regEntry[(winnerIndex + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)]; \
135 if (cmp(*currentE, *winnerE)) \
137 std::swap(regEntry[(winnerIndex + (1 << LogK)) \
138 >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)], winnerIndex); \
139 winnerE = currentE; \
157 regEntry[0] = winnerIndex;
160 void multi_merge_unrolled_0(value_type * to)
162 const value_type * done = to + buffer_size;
165 *to = current->current();
171 void multi_merge_k(value_type * to)
173 run_cursor_type * currentE, * winnerE;
175 value_type * done = to + buffer_size;
176 int_type winnerIndex = entry[0];
178 while (LIKELY(to < done))
180 winnerE = current + winnerIndex;
181 *(to++) = winnerE->current();
185 for (int_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1)
187 currentE = current + entry[i];
189 if (cmp(*currentE, *winnerE))
191 std::swap(entry[i], winnerIndex);
197 entry[0] = winnerIndex;
201 void multi_merge(value_type * to)
206 multi_merge_unrolled_0(to);
209 multi_merge_unrolled<1>(to);
212 multi_merge_unrolled<2>(to);
215 multi_merge_unrolled<3>(to);
218 multi_merge_unrolled<4>(to);
221 multi_merge_unrolled<5>(to);
224 multi_merge_unrolled<6>(to);
227 multi_merge_unrolled<7>(to);
230 multi_merge_unrolled<8>(to);
233 multi_merge_unrolled<9>(to);
236 multi_merge_unrolled<10>(to);
245 __STXXL_END_NAMESPACE
249 template <
typename run_cursor_type,
250 typename run_cursor_cmp_type,
251 unsigned buffer_size>
252 void swap(stxxl::loser_tree<run_cursor_type, run_cursor_cmp_type, buffer_size> & a,
253 stxxl::loser_tree<run_cursor_type, run_cursor_cmp_type, buffer_size> & b)
259 #endif // !STXXL_LOSERTREE_HEADER