Stxxl
1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/algo/losertree.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 1999 Peter Sanders <sanders@mpi-sb.mpg.de> 00007 * Copyright (C) 2002 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 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.))); // replace with something smart 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 // init cursors 00083 for (i = 0; i < nruns; ++i) 00084 { 00085 current[i].buffer = p->pull_block(); 00086 //current[i].pos = 0; // done in constructor 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