STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
losertree.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/algo/losertree.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 1999 Peter Sanders <[email protected]>
7  * Copyright (C) 2002 Roman Dementiev <[email protected]>
8  * Copyright (C) 2009 Andreas Beckmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_ALGO_LOSERTREE_HEADER
16 #define STXXL_ALGO_LOSERTREE_HEADER
17 
18 #include <algorithm>
19 #include <stxxl/bits/noncopyable.h>
21 #include <stxxl/bits/verbose.h>
22 
24 
25 template <typename RunCursorType,
26  typename RunCursorCmpType>
27 class loser_tree : private noncopyable
28 {
29  int logK;
32  RunCursorType* current;
33  RunCursorCmpType cmp;
34 
36  {
37  if (root >= k)
38  {
39  return root - k;
40  }
41  else
42  {
43  int_type left = init_winner(2 * root);
44  int_type right = init_winner(2 * root + 1);
45  if (cmp(current[left], current[right]))
46  {
47  entry[root] = right;
48  return left;
49  }
50  else
51  {
52  entry[root] = left;
53  return right;
54  }
55  }
56  }
57 
58 public:
59  typedef typename RunCursorType::prefetcher_type prefetcher_type;
60  typedef typename RunCursorType::value_type value_type;
61 
63  prefetcher_type* p,
64  int_type nruns,
65  RunCursorCmpType c)
66  : cmp(c)
67  {
68  int_type i;
69  logK = ilog2_ceil(nruns);
70  int_type kReg = k = (int_type(1) << logK);
71 
72  STXXL_VERBOSE2("loser_tree: logK=" << logK << " nruns=" << nruns << " K=" << kReg);
73 
74 #ifdef STXXL_SORT_SINGLE_PREFETCHER
75  current = new RunCursorType[kReg];
76  RunCursorType::set_prefetcher(p);
77 #else
78  current = new RunCursorType[kReg];
79  for (i = 0; i < kReg; ++i)
80  current[i].prefetcher() = p;
81 #endif
82  entry = new int_type[(kReg << 1)];
83  // init cursors
84  for (i = 0; i < nruns; ++i)
85  {
86  current[i].buffer = p->pull_block();
87  //current[i].pos = 0; // done in constructor
88  entry[kReg + i] = i;
89  }
90 
91  for (i = nruns; i < kReg; ++i)
92  {
93  current[i].make_inf();
94  entry[kReg + i] = i;
95  }
96 
97  entry[0] = init_winner(1);
98  }
100  {
101  delete[] current;
102  delete[] entry;
103  }
104 
105  void swap(loser_tree& obj)
106  {
107  std::swap(logK, obj.logK);
108  std::swap(k, obj.k);
109  std::swap(entry, obj.entry);
110  std::swap(current, obj.current);
111  std::swap(cmp, obj.cmp);
112  }
113 
114 private:
115  template <int LogK>
116  void multi_merge_unrolled(value_type* out_first, value_type* out_last)
117  {
118  RunCursorType* currentE, * winnerE;
119  int_type* regEntry = entry;
120  int_type winnerIndex = regEntry[0];
121 
122  while (LIKELY(out_first != out_last))
123  {
124  winnerE = current + winnerIndex;
125  *(out_first) = winnerE->current();
126  ++out_first;
127 
128  ++(*winnerE);
129 
130 #define TreeStep(L) \
131  if (LogK >= L) \
132  { \
133  currentE = current + \
134  regEntry[(winnerIndex + (1 << LogK)) >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)]; \
135  if (cmp(*currentE, *winnerE)) \
136  { \
137  std::swap(regEntry[(winnerIndex + (1 << LogK)) \
138  >> (((int(LogK - L) + 1) >= 0) ? ((LogK - L) + 1) : 0)], winnerIndex); \
139  winnerE = currentE; \
140  } \
141  }
142 
143  TreeStep(10);
144  TreeStep(9);
145  TreeStep(8);
146  TreeStep(7);
147  TreeStep(6);
148  TreeStep(5);
149  TreeStep(4);
150  TreeStep(3);
151  TreeStep(2);
152  TreeStep(1);
153 
154 #undef TreeStep
155  }
156 
157  regEntry[0] = winnerIndex;
158  }
159 
160  void multi_merge_unrolled_0(value_type* out_first, value_type* out_last)
161  {
162  while (LIKELY(out_first != out_last))
163  {
164  *out_first = current->current();
165  ++out_first;
166  ++(*current);
167  }
168  }
169 
170  void multi_merge_k(value_type* out_first, value_type* out_last)
171  {
172  RunCursorType* currentE, * winnerE;
173  int_type kReg = k;
174  int_type winnerIndex = entry[0];
175 
176  while (LIKELY(out_first != out_last))
177  {
178  winnerE = current + winnerIndex;
179  *(out_first) = winnerE->current();
180  ++out_first;
181 
182  ++(*winnerE);
183 
184  for (int_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1)
185  {
186  currentE = current + entry[i];
187 
188  if (cmp(*currentE, *winnerE))
189  {
190  std::swap(entry[i], winnerIndex);
191  winnerE = currentE;
192  }
193  }
194  }
195 
196  entry[0] = winnerIndex;
197  }
198 
199 public:
200  void multi_merge(value_type* out_first, value_type* out_last)
201  {
202  switch (logK)
203  {
204  case 0:
205  multi_merge_unrolled_0(out_first, out_last);
206  break;
207  case 1:
208  multi_merge_unrolled<1>(out_first, out_last);
209  break;
210  case 2:
211  multi_merge_unrolled<2>(out_first, out_last);
212  break;
213  case 3:
214  multi_merge_unrolled<3>(out_first, out_last);
215  break;
216  case 4:
217  multi_merge_unrolled<4>(out_first, out_last);
218  break;
219  case 5:
220  multi_merge_unrolled<5>(out_first, out_last);
221  break;
222  case 6:
223  multi_merge_unrolled<6>(out_first, out_last);
224  break;
225  case 7:
226  multi_merge_unrolled<7>(out_first, out_last);
227  break;
228  case 8:
229  multi_merge_unrolled<8>(out_first, out_last);
230  break;
231  case 9:
232  multi_merge_unrolled<9>(out_first, out_last);
233  break;
234  case 10:
235  multi_merge_unrolled<10>(out_first, out_last);
236  break;
237  default:
238  multi_merge_k(out_first, out_last);
239  break;
240  }
241  }
242 };
243 
245 
246 namespace std {
247 
248 template <typename RunCursorType,
249  typename RunCursorCmpType>
252 {
253  a.swap(b);
254 }
255 
256 } // namespace std
257 
258 #endif // !STXXL_ALGO_LOSERTREE_HEADER
259 // vim: et:ts=4:sw=4
#define LIKELY(c)
Definition: utils.h:219
loser_tree(prefetcher_type *p, int_type nruns, RunCursorCmpType c)
Definition: losertree.h:62
RunCursorType * current
Definition: losertree.h:32
void multi_merge_unrolled(value_type *out_first, value_type *out_last)
Definition: losertree.h:116
RunCursorType::value_type value_type
Definition: losertree.h:60
#define STXXL_VERBOSE2(x)
Definition: verbose.h:107
RunCursorCmpType cmp
Definition: losertree.h:33
void multi_merge_k(value_type *out_first, value_type *out_last)
Definition: losertree.h:170
int_type * entry
Definition: losertree.h:31
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
void multi_merge_unrolled_0(value_type *out_first, value_type *out_last)
Definition: losertree.h:160
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
int_type init_winner(int_type root)
Definition: losertree.h:35
RunCursorType::prefetcher_type prefetcher_type
Definition: losertree.h:59
unsigned int ilog2_ceil(const IntegerType &i)
calculate the log2 ceiling of an integer type (by repeated bit shifts)
Definition: utils.h:188
#define TreeStep(L)
void swap(loser_tree &obj)
Definition: losertree.h:105
void multi_merge(value_type *out_first, value_type *out_last)
Definition: losertree.h:200
#define STXXL_END_NAMESPACE
Definition: namespace.h:17