00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #ifndef STXXL_LOSERTREE_HEADER
00015 #define STXXL_LOSERTREE_HEADER
00016
00017 #include <stxxl/bits/noncopyable.h>
00018 #include <stxxl/bits/common/utils.h>
00019
00020
00021 __STXXL_BEGIN_NAMESPACE
00022
00023 template <typename run_cursor_type,
00024 typename run_cursor_cmp_type,
00025 unsigned buffer_size>
00026 class loser_tree : private noncopyable
00027 {
00028 int logK;
00029 int_type k;
00030 int_type * entry;
00031 run_cursor_type * current;
00032 run_cursor_cmp_type cmp;
00033
00034 int_type init_winner(int_type root)
00035 {
00036 if (root >= k)
00037 {
00038 return root - k;
00039 }
00040 else
00041 {
00042 int_type left = init_winner(2 * root);
00043 int_type right = init_winner(2 * root + 1);
00044 if (cmp(current[left], current[right]))
00045 {
00046 entry[root] = right;
00047 return left;
00048 }
00049 else
00050 {
00051 entry[root] = left;
00052 return right;
00053 }
00054 }
00055 }
00056
00057 public:
00058 typedef typename run_cursor_type::prefetcher_type prefetcher_type;
00059 typedef typename run_cursor_type::value_type value_type;
00060
00061 loser_tree(
00062 prefetcher_type * p,
00063 int_type nruns,
00064 run_cursor_cmp_type c) : cmp(c)
00065 {
00066 int_type i;
00067 logK = static_cast<int>(ceil(log(double(nruns)) / log(2.)));
00068 int_type kReg = k = (1 << logK);
00069
00070 STXXL_VERBOSE2("loser_tree: logK=" << logK << " nruns=" << nruns << " K=" << kReg);
00071
00072 #ifdef STXXL_SORT_SINGLE_PREFETCHER
00073 current = new run_cursor_type[kReg];
00074 run_cursor_type::set_prefetcher(p);
00075 #else
00076 current = new run_cursor_type[kReg];
00077 for (i = 0; i < kReg; ++i)
00078 current[i].prefetcher() = p;
00079
00080 #endif
00081 entry = new int_type[(kReg << 1)];
00082
00083 for (i = 0; i < nruns; ++i)
00084 {
00085 current[i].buffer = p->pull_block();
00086
00087 entry[kReg + i] = i;
00088 }
00089
00090 for (i = nruns; i < kReg; ++i)
00091 {
00092 current[i].make_inf();
00093 entry[kReg + i] = i;
00094 }
00095
00096 entry[0] = init_winner(1);
00097 }
00098 ~loser_tree()
00099 {
00100 delete[] current;
00101 delete[] entry;
00102 }
00103
00104 void swap(loser_tree & obj)
00105 {
00106 std::swap(logK, obj.logK);
00107 std::swap(k, obj.k);
00108 std::swap(entry, obj.entry);
00109 std::swap(current, obj.current);
00110 std::swap(cmp, obj.cmp);
00111 }
00112
00113 private:
00114 template <unsigned LogK>
00115 void multi_merge_unrolled(value_type * to)
00116 {
00117 run_cursor_type * currentE, * winnerE;
00118 int_type * regEntry = entry;
00119 value_type * done = to + buffer_size;
00120 int_type winnerIndex = regEntry[0];
00121
00122 while (LIKELY(to < done))
00123 {
00124 winnerE = current + winnerIndex;
00125 *(to++) = winnerE->current();
00126
00127 (*winnerE)++;
00128
00129
00130 #define TreeStep(L) \
00131 if (LogK >= L) \
00132 { \
00133 currentE = current + \
00134 regEntry[(winnerIndex + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)]; \
00135 if (cmp(*currentE, *winnerE)) \
00136 { \
00137 std::swap(regEntry[(winnerIndex + (1 << LogK)) \
00138 >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)], winnerIndex); \
00139 winnerE = currentE; \
00140 } \
00141 }
00142
00143 TreeStep(10);
00144 TreeStep(9);
00145 TreeStep(8);
00146 TreeStep(7);
00147 TreeStep(6);
00148 TreeStep(5);
00149 TreeStep(4);
00150 TreeStep(3);
00151 TreeStep(2);
00152 TreeStep(1);
00153
00154 #undef TreeStep
00155 }
00156
00157 regEntry[0] = winnerIndex;
00158 }
00159
00160 void multi_merge_unrolled_0(value_type * to)
00161 {
00162 const value_type * done = to + buffer_size;
00163 while (to < done)
00164 {
00165 *to = current->current();
00166 ++to;
00167 (*current)++;
00168 }
00169 }
00170
00171 void multi_merge_k(value_type * to)
00172 {
00173 run_cursor_type * currentE, * winnerE;
00174 int_type kReg = k;
00175 value_type * done = to + buffer_size;
00176 int_type winnerIndex = entry[0];
00177
00178 while (LIKELY(to < done))
00179 {
00180 winnerE = current + winnerIndex;
00181 *(to++) = winnerE->current();
00182
00183 (*winnerE)++;
00184
00185 for (int_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1)
00186 {
00187 currentE = current + entry[i];
00188
00189 if (cmp(*currentE, *winnerE))
00190 {
00191 std::swap(entry[i], winnerIndex);
00192 winnerE = currentE;
00193 }
00194 }
00195 }
00196
00197 entry[0] = winnerIndex;
00198 }
00199
00200 public:
00201 void multi_merge(value_type * to)
00202 {
00203 switch (logK)
00204 {
00205 case 0:
00206 multi_merge_unrolled_0(to);
00207 break;
00208 case 1:
00209 multi_merge_unrolled<1>(to);
00210 break;
00211 case 2:
00212 multi_merge_unrolled<2>(to);
00213 break;
00214 case 3:
00215 multi_merge_unrolled<3>(to);
00216 break;
00217 case 4:
00218 multi_merge_unrolled<4>(to);
00219 break;
00220 case 5:
00221 multi_merge_unrolled<5>(to);
00222 break;
00223 case 6:
00224 multi_merge_unrolled<6>(to);
00225 break;
00226 case 7:
00227 multi_merge_unrolled<7>(to);
00228 break;
00229 case 8:
00230 multi_merge_unrolled<8>(to);
00231 break;
00232 case 9:
00233 multi_merge_unrolled<9>(to);
00234 break;
00235 case 10:
00236 multi_merge_unrolled<10>(to);
00237 break;
00238 default:
00239 multi_merge_k(to);
00240 break;
00241 }
00242 }
00243 };
00244
00245 __STXXL_END_NAMESPACE
00246
00247 namespace std
00248 {
00249 template <typename run_cursor_type,
00250 typename run_cursor_cmp_type,
00251 unsigned buffer_size>
00252 void swap(stxxl::loser_tree<run_cursor_type, run_cursor_cmp_type, buffer_size> & a,
00253 stxxl::loser_tree<run_cursor_type, run_cursor_cmp_type, buffer_size> & b)
00254 {
00255 a.swap(b);
00256 }
00257 }
00258
00259 #endif // !STXXL_LOSERTREE_HEADER