Stxxl  1.2.1
losertree.h
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 <sanders@mpi-sb.mpg.de>
7  * Copyright (C) 2002 Roman Dementiev <dementiev@mpi-sb.mpg.de>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_LOSERTREE_HEADER
15 #define STXXL_LOSERTREE_HEADER
16 
17 #include <stxxl/bits/noncopyable.h>
18 #include <stxxl/bits/common/utils.h>
19 
20 
21 __STXXL_BEGIN_NAMESPACE
22 
23 template <typename run_cursor_type,
24  typename run_cursor_cmp_type,
25  unsigned buffer_size>
26 class loser_tree : private noncopyable
27 {
28  int logK;
29  int_type k;
30  int_type * entry;
31  run_cursor_type * current;
32  run_cursor_cmp_type cmp;
33 
34  int_type init_winner(int_type root)
35  {
36  if (root >= k)
37  {
38  return root - k;
39  }
40  else
41  {
42  int_type left = init_winner(2 * root);
43  int_type right = init_winner(2 * root + 1);
44  if (cmp(current[left], current[right]))
45  {
46  entry[root] = right;
47  return left;
48  }
49  else
50  {
51  entry[root] = left;
52  return right;
53  }
54  }
55  }
56 
57 public:
58  typedef typename run_cursor_type::prefetcher_type prefetcher_type;
59  typedef typename run_cursor_type::value_type value_type;
60 
61  loser_tree(
62  prefetcher_type * p,
63  int_type nruns,
64  run_cursor_cmp_type c) : cmp(c)
65  {
66  int_type i;
67  logK = static_cast<int>(ceil(log(double(nruns)) / log(2.))); // replace with something smart
68  int_type kReg = k = (1 << logK);
69 
70  STXXL_VERBOSE2("loser_tree: logK=" << logK << " nruns=" << nruns << " K=" << kReg);
71 
72 #ifdef STXXL_SORT_SINGLE_PREFETCHER
73  current = new run_cursor_type[kReg];
74  run_cursor_type::set_prefetcher(p);
75 #else
76  current = new run_cursor_type[kReg];
77  for (i = 0; i < kReg; ++i)
78  current[i].prefetcher() = p;
79 
80 #endif
81  entry = new int_type[(kReg << 1)];
82  // init cursors
83  for (i = 0; i < nruns; ++i)
84  {
85  current[i].buffer = p->pull_block();
86  //current[i].pos = 0; // done in constructor
87  entry[kReg + i] = i;
88  }
89 
90  for (i = nruns; i < kReg; ++i)
91  {
92  current[i].make_inf();
93  entry[kReg + i] = i;
94  }
95 
96  entry[0] = init_winner(1);
97  }
98  ~loser_tree()
99  {
100  delete[] current;
101  delete[] entry;
102  }
103 
104  void swap(loser_tree & obj)
105  {
106  std::swap(logK, obj.logK);
107  std::swap(k, obj.k);
108  std::swap(entry, obj.entry);
109  std::swap(current, obj.current);
110  std::swap(cmp, obj.cmp);
111  }
112 
113 private:
114  template <unsigned LogK>
115  void multi_merge_unrolled(value_type * to)
116  {
117  run_cursor_type * currentE, * winnerE;
118  int_type * regEntry = entry;
119  value_type * done = to + buffer_size;
120  int_type winnerIndex = regEntry[0];
121 
122  while (LIKELY(to < done))
123  {
124  winnerE = current + winnerIndex;
125  *(to++) = winnerE->current();
126 
127  (*winnerE)++;
128 
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 * to)
161  {
162  const value_type * done = to + buffer_size;
163  while (to < done)
164  {
165  *to = current->current();
166  ++to;
167  (*current)++;
168  }
169  }
170 
171  void multi_merge_k(value_type * to)
172  {
173  run_cursor_type * currentE, * winnerE;
174  int_type kReg = k;
175  value_type * done = to + buffer_size;
176  int_type winnerIndex = entry[0];
177 
178  while (LIKELY(to < done))
179  {
180  winnerE = current + winnerIndex;
181  *(to++) = winnerE->current();
182 
183  (*winnerE)++;
184 
185  for (int_type i = (winnerIndex + kReg) >> 1; i > 0; i >>= 1)
186  {
187  currentE = current + entry[i];
188 
189  if (cmp(*currentE, *winnerE))
190  {
191  std::swap(entry[i], winnerIndex);
192  winnerE = currentE;
193  }
194  }
195  }
196 
197  entry[0] = winnerIndex;
198  }
199 
200 public:
201  void multi_merge(value_type * to)
202  {
203  switch (logK)
204  {
205  case 0:
206  multi_merge_unrolled_0(to);
207  break;
208  case 1:
209  multi_merge_unrolled<1>(to);
210  break;
211  case 2:
212  multi_merge_unrolled<2>(to);
213  break;
214  case 3:
215  multi_merge_unrolled<3>(to);
216  break;
217  case 4:
218  multi_merge_unrolled<4>(to);
219  break;
220  case 5:
221  multi_merge_unrolled<5>(to);
222  break;
223  case 6:
224  multi_merge_unrolled<6>(to);
225  break;
226  case 7:
227  multi_merge_unrolled<7>(to);
228  break;
229  case 8:
230  multi_merge_unrolled<8>(to);
231  break;
232  case 9:
233  multi_merge_unrolled<9>(to);
234  break;
235  case 10:
236  multi_merge_unrolled<10>(to);
237  break;
238  default:
239  multi_merge_k(to);
240  break;
241  }
242  }
243 };
244 
245 __STXXL_END_NAMESPACE
246 
247 namespace std
248 {
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)
254  {
255  a.swap(b);
256  }
257 }
258 
259 #endif // !STXXL_LOSERTREE_HEADER