http://stxxl.sourceforge.net
<sanders@mpi-sb.mpg.de>
<dementiev@mpi-sb.mpg.de>
<beckmann@cs.uni-frankfurt.de>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_LOSERTREE_HEADER
#define STXXL_LOSERTREE_HEADER
#include <algorithm>
#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/common/utils.h>
#include <stxxl/bits/verbose.h>
__STXXL_BEGIN_NAMESPACE
template <typename run_cursor_type,
typename run_cursor_cmp_type>
class loser_tree : private noncopyable
{
int logK;
int_type k;
int_type * entry;
run_cursor_type * current;
run_cursor_cmp_type cmp;
int_type init_winner(int_type root)
{
if (root >= k)
{
return root - k;
}
else
{
int_type left = init_winner(2 * root);
int_type right = init_winner(2 * root + 1);
if (cmp(current[left], current[right]))
{
entry[root] = right;
return left;
}
else
{
entry[root] = left;
return right;
}
}
}
public:
typedef typename run_cursor_type::prefetcher_type prefetcher_type;
typedef typename run_cursor_type::value_type value_type;
loser_tree(
prefetcher_type * p,
int_type nruns,
run_cursor_cmp_type c) : cmp(c)
{
int_type i;
logK = log2_ceil(nruns);
int_type kReg = k = (1 << logK);
STXXL_VERBOSE2("loser_tree: logK=" << logK << " nruns=" << nruns << " K=" << kReg);
#ifdef STXXL_SORT_SINGLE_PREFETCHER
current = new run_cursor_type[kReg];
run_cursor_type::set_prefetcher(p);
#else
current = new run_cursor_type[kReg];
for (i = 0; i < kReg; ++i)
current[i].prefetcher() = p;
#endif
entry = new int_type[(kReg << 1)];
for (i = 0; i < nruns; ++i)
{
current[i].buffer = p->pull_block();
entry[kReg + i] = i;
}
for (i = nruns; i < kReg; ++i)
{
current[i].make_inf();
entry[kReg + i] = i;
}
entry[0] = init_winner(1);
}
~loser_tree()
{
delete[] current;
delete[] entry;
}
void swap(loser_tree & obj)
{
std::swap(logK, obj.logK);
std::swap(k, obj.k);
std::swap(entry, obj.entry);
std::swap(current, obj.current);
std::swap(cmp, obj.cmp);
}
private:
template <unsigned LogK>
void multi_merge_unrolled(value_type * out_first, value_type * out_last)
{
run_cursor_type * currentE, * winnerE;
int_type * regEntry = entry;
int_type winnerIndex = regEntry[0];
while (LIKELY(out_first != out_last))
{
winnerE = current + winnerIndex;
*(out_first) = winnerE->current();
++out_first;
++(*winnerE);
#define TreeStep(L) \
if (LogK >= L) \
{ \
currentE = current + \
regEntry[(winnerIndex + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)]; \
if (cmp(*currentE, *winnerE)) \
{ \
std::swap(regEntry[(winnerIndex + (1 << LogK)) \
>> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)], winnerIndex); \
winnerE = currentE; \
} \
}
TreeStep(10);
TreeStep(9);
TreeStep(8);
TreeStep(7);
TreeStep(6);
TreeStep(5);
TreeStep(4);
TreeStep(3);
TreeStep(2);
TreeStep(1);
#undef TreeStep
}
regEntry[0] = winnerIndex;
}
void multi_merge_unrolled_0(value_type * out_first, value_type * out_last)
{
while (LIKELY(out_first != out_last))
{
*out_first = current->current();
++out_first;
++(*current);
}
}
void multi_merge_k(value_type * out_first, value_type * out_last)
{
run_cursor_type * currentE, * winnerE;
int_type kReg = k;
int_type winnerIndex = entry[0];
while (LIKELY(out_first != out_last))
{
winnerE = current + winnerIndex;
*(out_first) = winnerE->current();
++out_first;
++(*winnerE);
for (int_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1)
{
currentE = current + entry[i];
if (cmp(*currentE, *winnerE))
{
std::swap(entry[i], winnerIndex);
winnerE = currentE;
}
}
}
entry[0] = winnerIndex;
}
public:
void multi_merge(value_type * out_first, value_type * out_last)
{
switch (logK)
{
case 0:
multi_merge_unrolled_0(out_first, out_last);
break;
case 1:
multi_merge_unrolled<1>(out_first, out_last);
break;
case 2:
multi_merge_unrolled<2>(out_first, out_last);
break;
case 3:
multi_merge_unrolled<3>(out_first, out_last);
break;
case 4:
multi_merge_unrolled<4>(out_first, out_last);
break;
case 5:
multi_merge_unrolled<5>(out_first, out_last);
break;
case 6:
multi_merge_unrolled<6>(out_first, out_last);
break;
case 7:
multi_merge_unrolled<7>(out_first, out_last);
break;
case 8:
multi_merge_unrolled<8>(out_first, out_last);
break;
case 9:
multi_merge_unrolled<9>(out_first, out_last);
break;
case 10:
multi_merge_unrolled<10>(out_first, out_last);
break;
default:
multi_merge_k(out_first, out_last);
break;
}
}
};
__STXXL_END_NAMESPACE
namespace std
{
template <typename run_cursor_type,
typename run_cursor_cmp_type>
void swap(stxxl::loser_tree<run_cursor_type, run_cursor_cmp_type> & a,
stxxl::loser_tree<run_cursor_type, run_cursor_cmp_type> & b)
{
a.swap(b);
}
}
#endif