]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
99dee823 | 3 | // Copyright (C) 2007-2021 Free Software Foundation, Inc. |
c2ba9709 JS |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
c2ba9709 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
c2ba9709 JS |
24 | |
25 | /** @file parallel/losertree.h | |
e683ee2a JS |
26 | * @brief Many generic loser tree variants. |
27 | * This file is a GNU parallel extension to the Standard C++ Library. | |
28 | */ | |
c2ba9709 JS |
29 | |
30 | // Written by Johannes Singler. | |
31 | ||
32 | #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H | |
dfbed397 | 33 | #define _GLIBCXX_PARALLEL_LOSERTREE_H 1 |
c2ba9709 | 34 | |
c2ba9709 | 35 | #include <bits/stl_algobase.h> |
53567bbd | 36 | #include <bits/stl_function.h> |
c2ba9709 JS |
37 | #include <parallel/features.h> |
38 | #include <parallel/base.h> | |
39 | ||
40 | namespace __gnu_parallel | |
41 | { | |
77d16198 PC |
42 | /** |
43 | * @brief Guarded loser/tournament tree. | |
44 | * | |
45 | * The smallest element is at the top. | |
46 | * | |
47 | * Guarding is done explicitly through one flag _M_sup per element, | |
48 | * inf is not needed due to a better initialization routine. This | |
49 | * is a well-performing variant. | |
50 | * | |
51 | * @param _Tp the element type | |
52 | * @param _Compare the comparator to use, defaults to std::less<_Tp> | |
53 | */ | |
54 | template<typename _Tp, typename _Compare> | |
55 | class _LoserTreeBase | |
d87f43c3 | 56 | { |
77d16198 PC |
57 | protected: |
58 | /** @brief Internal representation of a _LoserTree element. */ | |
59 | struct _Loser | |
60 | { | |
61 | /** @brief flag, true iff this is a "maximum" __sentinel. */ | |
62 | bool _M_sup; | |
63 | /** @brief __index of the __source __sequence. */ | |
64 | int _M_source; | |
65 | /** @brief _M_key of the element in the _LoserTree. */ | |
66 | _Tp _M_key; | |
67 | }; | |
68 | ||
69 | unsigned int _M_ik, _M_k, _M_offset; | |
70 | ||
71 | /** log_2{_M_k} */ | |
72 | unsigned int _M_log_k; | |
73 | ||
74 | /** @brief _LoserTree __elements. */ | |
75 | _Loser* _M_losers; | |
76 | ||
77 | /** @brief _Compare to use. */ | |
78 | _Compare _M_comp; | |
79 | ||
80 | /** | |
81 | * @brief State flag that determines whether the _LoserTree is empty. | |
82 | * | |
83 | * Only used for building the _LoserTree. | |
84 | */ | |
85 | bool _M_first_insert; | |
86 | ||
87 | public: | |
88 | /** | |
89 | * @brief The constructor. | |
90 | * | |
91 | * @param __k The number of sequences to merge. | |
92 | * @param __comp The comparator to use. | |
93 | */ | |
94 | _LoserTreeBase(unsigned int __k, _Compare __comp) | |
95 | : _M_comp(__comp) | |
96 | { | |
97 | _M_ik = __k; | |
98 | ||
99 | // Compute log_2{_M_k} for the _Loser Tree | |
100 | _M_log_k = __rd_log2(_M_ik - 1) + 1; | |
101 | ||
102 | // Next greater power of 2. | |
103 | _M_k = 1 << _M_log_k; | |
104 | _M_offset = _M_k; | |
105 | ||
106 | // Avoid default-constructing _M_losers[]._M_key | |
107 | _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k | |
108 | * sizeof(_Loser))); | |
109 | for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i) | |
110 | _M_losers[__i + _M_k]._M_sup = true; | |
111 | ||
112 | _M_first_insert = true; | |
113 | } | |
114 | ||
115 | /** | |
116 | * @brief The destructor. | |
117 | */ | |
118 | ~_LoserTreeBase() | |
0ecca7a6 PC |
119 | { |
120 | for (unsigned int __i = 0; __i < (2 * _M_k); ++__i) | |
121 | _M_losers[__i].~_Loser(); | |
122 | ::operator delete(_M_losers); | |
123 | } | |
77d16198 PC |
124 | |
125 | /** | |
126 | * @brief Initializes the sequence "_M_source" with the element "__key". | |
127 | * | |
128 | * @param __key the element to insert | |
129 | * @param __source __index of the __source __sequence | |
130 | * @param __sup flag that determines whether the value to insert is an | |
131 | * explicit __supremum. | |
132 | */ | |
133 | void | |
134 | __insert_start(const _Tp& __key, int __source, bool __sup) | |
135 | { | |
136 | unsigned int __pos = _M_k + __source; | |
137 | ||
0ecca7a6 | 138 | if (_M_first_insert) |
77d16198 | 139 | { |
0ecca7a6 | 140 | // Construct all keys, so we can easily destruct them. |
77d16198 | 141 | for (unsigned int __i = 0; __i < (2 * _M_k); ++__i) |
0ecca7a6 | 142 | ::new(&(_M_losers[__i]._M_key)) _Tp(__key); |
77d16198 PC |
143 | _M_first_insert = false; |
144 | } | |
145 | else | |
0ecca7a6 | 146 | _M_losers[__pos]._M_key = __key; |
77d16198 PC |
147 | |
148 | _M_losers[__pos]._M_sup = __sup; | |
149 | _M_losers[__pos]._M_source = __source; | |
150 | } | |
151 | ||
152 | /** | |
153 | * @return the index of the sequence with the smallest element. | |
154 | */ | |
155 | int __get_min_source() | |
156 | { return _M_losers[0]._M_source; } | |
d87f43c3 PC |
157 | }; |
158 | ||
d87f43c3 | 159 | /** |
77d16198 | 160 | * @brief Stable _LoserTree variant. |
d87f43c3 | 161 | * |
77d16198 PC |
162 | * Provides the stable implementations of insert_start, __init_winner, |
163 | * __init and __delete_min_insert. | |
d87f43c3 | 164 | * |
77d16198 | 165 | * Unstable variant is done using partial specialisation below. |
d87f43c3 | 166 | */ |
77d16198 PC |
167 | template<bool __stable/* default == true */, typename _Tp, |
168 | typename _Compare> | |
169 | class _LoserTree | |
170 | : public _LoserTreeBase<_Tp, _Compare> | |
d87f43c3 | 171 | { |
77d16198 PC |
172 | typedef _LoserTreeBase<_Tp, _Compare> _Base; |
173 | using _Base::_M_k; | |
e330aa5b | 174 | using _Base::_M_comp; |
77d16198 PC |
175 | using _Base::_M_losers; |
176 | using _Base::_M_first_insert; | |
177 | ||
178 | public: | |
179 | _LoserTree(unsigned int __k, _Compare __comp) | |
180 | : _Base::_LoserTreeBase(__k, __comp) | |
181 | { } | |
182 | ||
183 | unsigned int | |
184 | __init_winner(unsigned int __root) | |
185 | { | |
186 | if (__root >= _M_k) | |
187 | return __root; | |
188 | else | |
189 | { | |
190 | unsigned int __left = __init_winner(2 * __root); | |
191 | unsigned int __right = __init_winner(2 * __root + 1); | |
192 | if (_M_losers[__right]._M_sup | |
193 | || (!_M_losers[__left]._M_sup | |
194 | && !_M_comp(_M_losers[__right]._M_key, | |
195 | _M_losers[__left]._M_key))) | |
196 | { | |
197 | // Left one is less or equal. | |
198 | _M_losers[__root] = _M_losers[__right]; | |
199 | return __left; | |
200 | } | |
201 | else | |
202 | { | |
203 | // Right one is less. | |
204 | _M_losers[__root] = _M_losers[__left]; | |
205 | return __right; | |
206 | } | |
207 | } | |
208 | } | |
209 | ||
210 | void __init() | |
211 | { _M_losers[0] = _M_losers[__init_winner(1)]; } | |
212 | ||
213 | /** | |
214 | * @brief Delete the smallest element and insert a new element from | |
215 | * the previously smallest element's sequence. | |
216 | * | |
217 | * This implementation is stable. | |
218 | */ | |
219 | // Do not pass a const reference since __key will be used as | |
220 | // local variable. | |
221 | void | |
222 | __delete_min_insert(_Tp __key, bool __sup) | |
223 | { | |
fc722a0e | 224 | using std::swap; |
e383deac | 225 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
226 | // no dummy sequence can ever be at the top! |
227 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
228 | #endif | |
f9985df5 | 229 | |
77d16198 PC |
230 | int __source = _M_losers[0]._M_source; |
231 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
232 | __pos /= 2) | |
233 | { | |
234 | // The smaller one gets promoted, ties are broken by _M_source. | |
235 | if ((__sup && (!_M_losers[__pos]._M_sup | |
236 | || _M_losers[__pos]._M_source < __source)) | |
237 | || (!__sup && !_M_losers[__pos]._M_sup | |
238 | && ((_M_comp(_M_losers[__pos]._M_key, __key)) | |
239 | || (!_M_comp(__key, _M_losers[__pos]._M_key) | |
240 | && _M_losers[__pos]._M_source < __source)))) | |
241 | { | |
242 | // The other one is smaller. | |
243 | std::swap(_M_losers[__pos]._M_sup, __sup); | |
244 | std::swap(_M_losers[__pos]._M_source, __source); | |
fc722a0e | 245 | swap(_M_losers[__pos]._M_key, __key); |
77d16198 PC |
246 | } |
247 | } | |
248 | ||
249 | _M_losers[0]._M_sup = __sup; | |
250 | _M_losers[0]._M_source = __source; | |
251 | _M_losers[0]._M_key = __key; | |
252 | } | |
253 | }; | |
d87f43c3 PC |
254 | |
255 | /** | |
77d16198 | 256 | * @brief Unstable _LoserTree variant. |
d87f43c3 | 257 | * |
77d16198 | 258 | * Stability (non-stable here) is selected with partial specialization. |
d87f43c3 | 259 | */ |
77d16198 PC |
260 | template<typename _Tp, typename _Compare> |
261 | class _LoserTree</* __stable == */false, _Tp, _Compare> | |
262 | : public _LoserTreeBase<_Tp, _Compare> | |
d87f43c3 | 263 | { |
77d16198 PC |
264 | typedef _LoserTreeBase<_Tp, _Compare> _Base; |
265 | using _Base::_M_log_k; | |
266 | using _Base::_M_k; | |
e330aa5b | 267 | using _Base::_M_comp; |
77d16198 PC |
268 | using _Base::_M_losers; |
269 | using _Base::_M_first_insert; | |
270 | ||
271 | public: | |
272 | _LoserTree(unsigned int __k, _Compare __comp) | |
273 | : _Base::_LoserTreeBase(__k, __comp) | |
274 | { } | |
275 | ||
276 | /** | |
277 | * Computes the winner of the competition at position "__root". | |
278 | * | |
279 | * Called recursively (starting at 0) to build the initial tree. | |
280 | * | |
281 | * @param __root __index of the "game" to start. | |
282 | */ | |
283 | unsigned int | |
284 | __init_winner(unsigned int __root) | |
285 | { | |
286 | if (__root >= _M_k) | |
287 | return __root; | |
288 | else | |
289 | { | |
290 | unsigned int __left = __init_winner(2 * __root); | |
291 | unsigned int __right = __init_winner(2 * __root + 1); | |
292 | if (_M_losers[__right]._M_sup | |
293 | || (!_M_losers[__left]._M_sup | |
294 | && !_M_comp(_M_losers[__right]._M_key, | |
295 | _M_losers[__left]._M_key))) | |
296 | { | |
297 | // Left one is less or equal. | |
298 | _M_losers[__root] = _M_losers[__right]; | |
299 | return __left; | |
300 | } | |
301 | else | |
302 | { | |
303 | // Right one is less. | |
304 | _M_losers[__root] = _M_losers[__left]; | |
305 | return __right; | |
306 | } | |
307 | } | |
308 | } | |
309 | ||
310 | void | |
311 | __init() | |
312 | { _M_losers[0] = _M_losers[__init_winner(1)]; } | |
313 | ||
314 | /** | |
315 | * Delete the _M_key smallest element and insert the element __key | |
316 | * instead. | |
317 | * | |
318 | * @param __key the _M_key to insert | |
319 | * @param __sup true iff __key is an explicitly marked supremum | |
320 | */ | |
321 | // Do not pass a const reference since __key will be used as local | |
322 | // variable. | |
323 | void | |
324 | __delete_min_insert(_Tp __key, bool __sup) | |
325 | { | |
fc722a0e | 326 | using std::swap; |
e383deac | 327 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
328 | // no dummy sequence can ever be at the top! |
329 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
330 | #endif | |
f9985df5 | 331 | |
77d16198 PC |
332 | int __source = _M_losers[0]._M_source; |
333 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
334 | __pos /= 2) | |
335 | { | |
336 | // The smaller one gets promoted. | |
337 | if (__sup || (!_M_losers[__pos]._M_sup | |
338 | && _M_comp(_M_losers[__pos]._M_key, __key))) | |
339 | { | |
340 | // The other one is smaller. | |
341 | std::swap(_M_losers[__pos]._M_sup, __sup); | |
342 | std::swap(_M_losers[__pos]._M_source, __source); | |
fc722a0e | 343 | swap(_M_losers[__pos]._M_key, __key); |
77d16198 PC |
344 | } |
345 | } | |
346 | ||
347 | _M_losers[0]._M_sup = __sup; | |
348 | _M_losers[0]._M_source = __source; | |
349 | _M_losers[0]._M_key = __key; | |
350 | } | |
351 | }; | |
f9985df5 JS |
352 | |
353 | /** | |
77d16198 | 354 | * @brief Base class of _Loser Tree implementation using pointers. |
f9985df5 | 355 | */ |
77d16198 PC |
356 | template<typename _Tp, typename _Compare> |
357 | class _LoserTreePointerBase | |
d87f43c3 | 358 | { |
77d16198 PC |
359 | protected: |
360 | /** @brief Internal representation of _LoserTree __elements. */ | |
361 | struct _Loser | |
362 | { | |
363 | bool _M_sup; | |
364 | int _M_source; | |
365 | const _Tp* _M_keyp; | |
366 | }; | |
367 | ||
368 | unsigned int _M_ik, _M_k, _M_offset; | |
369 | _Loser* _M_losers; | |
370 | _Compare _M_comp; | |
371 | ||
372 | public: | |
373 | _LoserTreePointerBase(unsigned int __k, | |
374 | _Compare __comp = std::less<_Tp>()) | |
375 | : _M_comp(__comp) | |
376 | { | |
377 | _M_ik = __k; | |
378 | ||
379 | // Next greater power of 2. | |
380 | _M_k = 1 << (__rd_log2(_M_ik - 1) + 1); | |
381 | _M_offset = _M_k; | |
382 | _M_losers = new _Loser[_M_k * 2]; | |
383 | for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++) | |
384 | _M_losers[__i + _M_k]._M_sup = true; | |
385 | } | |
386 | ||
387 | ~_LoserTreePointerBase() | |
0ecca7a6 | 388 | { delete[] _M_losers; } |
77d16198 PC |
389 | |
390 | int __get_min_source() | |
391 | { return _M_losers[0]._M_source; } | |
392 | ||
393 | void __insert_start(const _Tp& __key, int __source, bool __sup) | |
394 | { | |
395 | unsigned int __pos = _M_k + __source; | |
396 | ||
397 | _M_losers[__pos]._M_sup = __sup; | |
398 | _M_losers[__pos]._M_source = __source; | |
399 | _M_losers[__pos]._M_keyp = &__key; | |
400 | } | |
401 | }; | |
d87f43c3 | 402 | |
77d16198 PC |
403 | /** |
404 | * @brief Stable _LoserTree implementation. | |
405 | * | |
406 | * The unstable variant is implemented using partial instantiation below. | |
407 | */ | |
408 | template<bool __stable/* default == true */, typename _Tp, typename _Compare> | |
409 | class _LoserTreePointer | |
410 | : public _LoserTreePointerBase<_Tp, _Compare> | |
d87f43c3 | 411 | { |
77d16198 PC |
412 | typedef _LoserTreePointerBase<_Tp, _Compare> _Base; |
413 | using _Base::_M_k; | |
e330aa5b | 414 | using _Base::_M_comp; |
77d16198 PC |
415 | using _Base::_M_losers; |
416 | ||
417 | public: | |
418 | _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>()) | |
419 | : _Base::_LoserTreePointerBase(__k, __comp) | |
420 | { } | |
421 | ||
422 | unsigned int | |
423 | __init_winner(unsigned int __root) | |
424 | { | |
425 | if (__root >= _M_k) | |
426 | return __root; | |
427 | else | |
428 | { | |
429 | unsigned int __left = __init_winner(2 * __root); | |
430 | unsigned int __right = __init_winner(2 * __root + 1); | |
431 | if (_M_losers[__right]._M_sup | |
432 | || (!_M_losers[__left]._M_sup | |
433 | && !_M_comp(*_M_losers[__right]._M_keyp, | |
434 | *_M_losers[__left]._M_keyp))) | |
435 | { | |
436 | // Left one is less or equal. | |
437 | _M_losers[__root] = _M_losers[__right]; | |
438 | return __left; | |
439 | } | |
440 | else | |
441 | { | |
442 | // Right one is less. | |
443 | _M_losers[__root] = _M_losers[__left]; | |
444 | return __right; | |
445 | } | |
446 | } | |
447 | } | |
448 | ||
449 | void __init() | |
450 | { _M_losers[0] = _M_losers[__init_winner(1)]; } | |
451 | ||
452 | void __delete_min_insert(const _Tp& __key, bool __sup) | |
453 | { | |
e383deac | 454 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
455 | // no dummy sequence can ever be at the top! |
456 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
3234d6b0 JS |
457 | #endif |
458 | ||
77d16198 PC |
459 | const _Tp* __keyp = &__key; |
460 | int __source = _M_losers[0]._M_source; | |
461 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
462 | __pos /= 2) | |
463 | { | |
464 | // The smaller one gets promoted, ties are broken by __source. | |
465 | if ((__sup && (!_M_losers[__pos]._M_sup | |
466 | || _M_losers[__pos]._M_source < __source)) | |
467 | || (!__sup && !_M_losers[__pos]._M_sup && | |
468 | ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)) | |
469 | || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp) | |
470 | && _M_losers[__pos]._M_source < __source)))) | |
471 | { | |
472 | // The other one is smaller. | |
473 | std::swap(_M_losers[__pos]._M_sup, __sup); | |
474 | std::swap(_M_losers[__pos]._M_source, __source); | |
475 | std::swap(_M_losers[__pos]._M_keyp, __keyp); | |
476 | } | |
477 | } | |
478 | ||
479 | _M_losers[0]._M_sup = __sup; | |
480 | _M_losers[0]._M_source = __source; | |
481 | _M_losers[0]._M_keyp = __keyp; | |
482 | } | |
483 | }; | |
f9985df5 JS |
484 | |
485 | /** | |
77d16198 | 486 | * @brief Unstable _LoserTree implementation. |
f9985df5 | 487 | * |
77d16198 | 488 | * The stable variant is above. |
f9985df5 | 489 | */ |
77d16198 PC |
490 | template<typename _Tp, typename _Compare> |
491 | class _LoserTreePointer</* __stable == */false, _Tp, _Compare> | |
492 | : public _LoserTreePointerBase<_Tp, _Compare> | |
d87f43c3 | 493 | { |
77d16198 PC |
494 | typedef _LoserTreePointerBase<_Tp, _Compare> _Base; |
495 | using _Base::_M_k; | |
e330aa5b | 496 | using _Base::_M_comp; |
77d16198 PC |
497 | using _Base::_M_losers; |
498 | ||
499 | public: | |
500 | _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>()) | |
501 | : _Base::_LoserTreePointerBase(__k, __comp) | |
502 | { } | |
503 | ||
504 | unsigned int | |
505 | __init_winner(unsigned int __root) | |
506 | { | |
507 | if (__root >= _M_k) | |
508 | return __root; | |
509 | else | |
510 | { | |
511 | unsigned int __left = __init_winner(2 * __root); | |
512 | unsigned int __right = __init_winner(2 * __root + 1); | |
513 | if (_M_losers[__right]._M_sup | |
514 | || (!_M_losers[__left]._M_sup | |
515 | && !_M_comp(*_M_losers[__right]._M_keyp, | |
516 | *_M_losers[__left]._M_keyp))) | |
517 | { | |
518 | // Left one is less or equal. | |
519 | _M_losers[__root] = _M_losers[__right]; | |
520 | return __left; | |
521 | } | |
522 | else | |
523 | { | |
524 | // Right one is less. | |
525 | _M_losers[__root] = _M_losers[__left]; | |
526 | return __right; | |
527 | } | |
528 | } | |
529 | } | |
530 | ||
531 | void __init() | |
532 | { _M_losers[0] = _M_losers[__init_winner(1)]; } | |
533 | ||
534 | void __delete_min_insert(const _Tp& __key, bool __sup) | |
535 | { | |
e383deac | 536 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
537 | // no dummy sequence can ever be at the top! |
538 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
f9985df5 | 539 | #endif |
c2ba9709 | 540 | |
77d16198 PC |
541 | const _Tp* __keyp = &__key; |
542 | int __source = _M_losers[0]._M_source; | |
543 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
544 | __pos /= 2) | |
545 | { | |
546 | // The smaller one gets promoted. | |
547 | if (__sup || (!_M_losers[__pos]._M_sup | |
548 | && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp))) | |
549 | { | |
550 | // The other one is smaller. | |
551 | std::swap(_M_losers[__pos]._M_sup, __sup); | |
552 | std::swap(_M_losers[__pos]._M_source, __source); | |
553 | std::swap(_M_losers[__pos]._M_keyp, __keyp); | |
554 | } | |
555 | } | |
556 | ||
557 | _M_losers[0]._M_sup = __sup; | |
558 | _M_losers[0]._M_source = __source; | |
559 | _M_losers[0]._M_keyp = __keyp; | |
560 | } | |
d87f43c3 PC |
561 | }; |
562 | ||
77d16198 PC |
563 | /** @brief Base class for unguarded _LoserTree implementation. |
564 | * | |
565 | * The whole element is copied into the tree structure. | |
566 | * | |
567 | * No guarding is done, therefore not a single input sequence must | |
568 | * run empty. Unused __sequence heads are marked with a sentinel which | |
569 | * is > all elements that are to be merged. | |
570 | * | |
571 | * This is a very fast variant. | |
572 | */ | |
573 | template<typename _Tp, typename _Compare> | |
574 | class _LoserTreeUnguardedBase | |
d87f43c3 | 575 | { |
77d16198 PC |
576 | protected: |
577 | struct _Loser | |
578 | { | |
579 | int _M_source; | |
580 | _Tp _M_key; | |
581 | }; | |
582 | ||
583 | unsigned int _M_ik, _M_k, _M_offset; | |
584 | _Loser* _M_losers; | |
585 | _Compare _M_comp; | |
586 | ||
587 | public: | |
0ecca7a6 | 588 | _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel, |
77d16198 PC |
589 | _Compare __comp = std::less<_Tp>()) |
590 | : _M_comp(__comp) | |
591 | { | |
592 | _M_ik = __k; | |
593 | ||
594 | // Next greater power of 2. | |
595 | _M_k = 1 << (__rd_log2(_M_ik - 1) + 1); | |
596 | _M_offset = _M_k; | |
597 | // Avoid default-constructing _M_losers[]._M_key | |
598 | _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k | |
599 | * sizeof(_Loser))); | |
600 | ||
0ecca7a6 PC |
601 | for (unsigned int __i = 0; __i < _M_k; ++__i) |
602 | { | |
603 | ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel); | |
604 | _M_losers[__i]._M_source = -1; | |
605 | } | |
606 | for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i) | |
607 | { | |
608 | ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel); | |
77d16198 PC |
609 | _M_losers[__i]._M_source = -1; |
610 | } | |
611 | } | |
612 | ||
613 | ~_LoserTreeUnguardedBase() | |
0ecca7a6 PC |
614 | { |
615 | for (unsigned int __i = 0; __i < (2 * _M_k); ++__i) | |
616 | _M_losers[__i].~_Loser(); | |
617 | ::operator delete(_M_losers); | |
618 | } | |
77d16198 PC |
619 | |
620 | int | |
621 | __get_min_source() | |
622 | { | |
e383deac | 623 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
624 | // no dummy sequence can ever be at the top! |
625 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
626 | #endif | |
627 | return _M_losers[0]._M_source; | |
628 | } | |
c2ba9709 | 629 | |
77d16198 PC |
630 | void |
631 | __insert_start(const _Tp& __key, int __source, bool) | |
632 | { | |
633 | unsigned int __pos = _M_k + __source; | |
c2ba9709 | 634 | |
0ecca7a6 | 635 | ::new(&(_M_losers[__pos]._M_key)) _Tp(__key); |
77d16198 PC |
636 | _M_losers[__pos]._M_source = __source; |
637 | } | |
638 | }; | |
c2ba9709 | 639 | |
77d16198 PC |
640 | /** |
641 | * @brief Stable implementation of unguarded _LoserTree. | |
642 | * | |
643 | * Unstable variant is selected below with partial specialization. | |
644 | */ | |
645 | template<bool __stable/* default == true */, typename _Tp, typename _Compare> | |
646 | class _LoserTreeUnguarded | |
647 | : public _LoserTreeUnguardedBase<_Tp, _Compare> | |
d87f43c3 | 648 | { |
77d16198 PC |
649 | typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base; |
650 | using _Base::_M_k; | |
e330aa5b | 651 | using _Base::_M_comp; |
77d16198 | 652 | using _Base::_M_losers; |
c2ba9709 | 653 | |
d87f43c3 | 654 | public: |
0ecca7a6 | 655 | _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel, |
77d16198 PC |
656 | _Compare __comp = std::less<_Tp>()) |
657 | : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp) | |
658 | { } | |
659 | ||
660 | unsigned int | |
661 | __init_winner(unsigned int __root) | |
662 | { | |
663 | if (__root >= _M_k) | |
664 | return __root; | |
665 | else | |
666 | { | |
667 | unsigned int __left = __init_winner(2 * __root); | |
668 | unsigned int __right = __init_winner(2 * __root + 1); | |
669 | if (!_M_comp(_M_losers[__right]._M_key, | |
670 | _M_losers[__left]._M_key)) | |
671 | { | |
672 | // Left one is less or equal. | |
673 | _M_losers[__root] = _M_losers[__right]; | |
674 | return __left; | |
675 | } | |
676 | else | |
677 | { | |
678 | // Right one is less. | |
679 | _M_losers[__root] = _M_losers[__left]; | |
680 | return __right; | |
681 | } | |
682 | } | |
683 | } | |
684 | ||
685 | void | |
686 | __init() | |
687 | { | |
688 | _M_losers[0] = _M_losers[__init_winner(1)]; | |
c2ba9709 | 689 | |
e383deac | 690 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
691 | // no dummy sequence can ever be at the top at the beginning |
692 | // (0 sequences!) | |
693 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
3234d6b0 | 694 | #endif |
77d16198 | 695 | } |
3234d6b0 | 696 | |
77d16198 PC |
697 | // Do not pass a const reference since __key will be used as |
698 | // local variable. | |
699 | void | |
700 | __delete_min_insert(_Tp __key, bool) | |
701 | { | |
fc722a0e | 702 | using std::swap; |
e383deac | 703 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
704 | // no dummy sequence can ever be at the top! |
705 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
3234d6b0 JS |
706 | #endif |
707 | ||
77d16198 PC |
708 | int __source = _M_losers[0]._M_source; |
709 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
710 | __pos /= 2) | |
711 | { | |
712 | // The smaller one gets promoted, ties are broken by _M_source. | |
713 | if (_M_comp(_M_losers[__pos]._M_key, __key) | |
714 | || (!_M_comp(__key, _M_losers[__pos]._M_key) | |
715 | && _M_losers[__pos]._M_source < __source)) | |
716 | { | |
717 | // The other one is smaller. | |
718 | std::swap(_M_losers[__pos]._M_source, __source); | |
fc722a0e | 719 | swap(_M_losers[__pos]._M_key, __key); |
77d16198 PC |
720 | } |
721 | } | |
722 | ||
723 | _M_losers[0]._M_source = __source; | |
724 | _M_losers[0]._M_key = __key; | |
725 | } | |
d87f43c3 | 726 | }; |
c2ba9709 | 727 | |
77d16198 PC |
728 | /** |
729 | * @brief Non-Stable implementation of unguarded _LoserTree. | |
730 | * | |
731 | * Stable implementation is above. | |
732 | */ | |
733 | template<typename _Tp, typename _Compare> | |
734 | class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare> | |
735 | : public _LoserTreeUnguardedBase<_Tp, _Compare> | |
d87f43c3 | 736 | { |
77d16198 PC |
737 | typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base; |
738 | using _Base::_M_k; | |
e330aa5b | 739 | using _Base::_M_comp; |
77d16198 | 740 | using _Base::_M_losers; |
c2ba9709 | 741 | |
77d16198 | 742 | public: |
0ecca7a6 | 743 | _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel, |
77d16198 PC |
744 | _Compare __comp = std::less<_Tp>()) |
745 | : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp) | |
746 | { } | |
747 | ||
748 | unsigned int | |
749 | __init_winner(unsigned int __root) | |
750 | { | |
751 | if (__root >= _M_k) | |
752 | return __root; | |
753 | else | |
754 | { | |
755 | unsigned int __left = __init_winner(2 * __root); | |
756 | unsigned int __right = __init_winner(2 * __root + 1); | |
f9985df5 | 757 | |
e383deac | 758 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
759 | // If __left one is sentinel then __right one must be, too. |
760 | if (_M_losers[__left]._M_source == -1) | |
761 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1); | |
c2ba9709 JS |
762 | #endif |
763 | ||
77d16198 PC |
764 | if (!_M_comp(_M_losers[__right]._M_key, |
765 | _M_losers[__left]._M_key)) | |
766 | { | |
767 | // Left one is less or equal. | |
768 | _M_losers[__root] = _M_losers[__right]; | |
769 | return __left; | |
770 | } | |
771 | else | |
772 | { | |
773 | // Right one is less. | |
774 | _M_losers[__root] = _M_losers[__left]; | |
775 | return __right; | |
776 | } | |
777 | } | |
778 | } | |
779 | ||
780 | void | |
781 | __init() | |
782 | { | |
783 | _M_losers[0] = _M_losers[__init_winner(1)]; | |
c2ba9709 | 784 | |
e383deac | 785 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
786 | // no dummy sequence can ever be at the top at the beginning |
787 | // (0 sequences!) | |
788 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
c2ba9709 | 789 | #endif |
77d16198 | 790 | } |
c2ba9709 | 791 | |
77d16198 PC |
792 | // Do not pass a const reference since __key will be used as |
793 | // local variable. | |
794 | void | |
795 | __delete_min_insert(_Tp __key, bool) | |
796 | { | |
0ad84c3f | 797 | using std::swap; |
e383deac | 798 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
799 | // no dummy sequence can ever be at the top! |
800 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
3234d6b0 JS |
801 | #endif |
802 | ||
77d16198 PC |
803 | int __source = _M_losers[0]._M_source; |
804 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
805 | __pos /= 2) | |
806 | { | |
807 | // The smaller one gets promoted. | |
808 | if (_M_comp(_M_losers[__pos]._M_key, __key)) | |
809 | { | |
810 | // The other one is smaller. | |
811 | std::swap(_M_losers[__pos]._M_source, __source); | |
fc722a0e | 812 | swap(_M_losers[__pos]._M_key, __key); |
77d16198 PC |
813 | } |
814 | } | |
815 | ||
816 | _M_losers[0]._M_source = __source; | |
817 | _M_losers[0]._M_key = __key; | |
818 | } | |
d87f43c3 | 819 | }; |
c2ba9709 | 820 | |
77d16198 PC |
821 | /** @brief Unguarded loser tree, keeping only pointers to the |
822 | * elements in the tree structure. | |
823 | * | |
824 | * No guarding is done, therefore not a single input sequence must | |
825 | * run empty. This is a very fast variant. | |
826 | */ | |
827 | template<typename _Tp, typename _Compare> | |
828 | class _LoserTreePointerUnguardedBase | |
d87f43c3 | 829 | { |
77d16198 PC |
830 | protected: |
831 | struct _Loser | |
832 | { | |
833 | int _M_source; | |
834 | const _Tp* _M_keyp; | |
835 | }; | |
836 | ||
837 | unsigned int _M_ik, _M_k, _M_offset; | |
838 | _Loser* _M_losers; | |
839 | _Compare _M_comp; | |
840 | ||
841 | public: | |
842 | ||
843 | _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel, | |
844 | _Compare __comp = std::less<_Tp>()) | |
845 | : _M_comp(__comp) | |
846 | { | |
847 | _M_ik = __k; | |
848 | ||
849 | // Next greater power of 2. | |
850 | _M_k = 1 << (__rd_log2(_M_ik - 1) + 1); | |
851 | _M_offset = _M_k; | |
852 | // Avoid default-constructing _M_losers[]._M_key | |
853 | _M_losers = new _Loser[2 * _M_k]; | |
854 | ||
855 | for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i) | |
856 | { | |
857 | _M_losers[__i]._M_keyp = &__sentinel; | |
858 | _M_losers[__i]._M_source = -1; | |
859 | } | |
860 | } | |
861 | ||
862 | ~_LoserTreePointerUnguardedBase() | |
863 | { delete[] _M_losers; } | |
864 | ||
865 | int | |
866 | __get_min_source() | |
867 | { | |
e383deac | 868 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
869 | // no dummy sequence can ever be at the top! |
870 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
f9985df5 | 871 | #endif |
77d16198 PC |
872 | return _M_losers[0]._M_source; |
873 | } | |
c2ba9709 | 874 | |
77d16198 PC |
875 | void |
876 | __insert_start(const _Tp& __key, int __source, bool) | |
877 | { | |
878 | unsigned int __pos = _M_k + __source; | |
d87f43c3 | 879 | |
77d16198 PC |
880 | _M_losers[__pos]._M_keyp = &__key; |
881 | _M_losers[__pos]._M_source = __source; | |
882 | } | |
883 | }; | |
d87f43c3 | 884 | |
77d16198 PC |
885 | /** |
886 | * @brief Stable unguarded _LoserTree variant storing pointers. | |
887 | * | |
888 | * Unstable variant is implemented below using partial specialization. | |
889 | */ | |
890 | template<bool __stable/* default == true */, typename _Tp, typename _Compare> | |
891 | class _LoserTreePointerUnguarded | |
892 | : public _LoserTreePointerUnguardedBase<_Tp, _Compare> | |
d87f43c3 | 893 | { |
77d16198 PC |
894 | typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base; |
895 | using _Base::_M_k; | |
e330aa5b | 896 | using _Base::_M_comp; |
77d16198 PC |
897 | using _Base::_M_losers; |
898 | ||
899 | public: | |
900 | _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel, | |
901 | _Compare __comp = std::less<_Tp>()) | |
902 | : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp) | |
903 | { } | |
904 | ||
905 | unsigned int | |
906 | __init_winner(unsigned int __root) | |
907 | { | |
908 | if (__root >= _M_k) | |
909 | return __root; | |
910 | else | |
911 | { | |
912 | unsigned int __left = __init_winner(2 * __root); | |
913 | unsigned int __right = __init_winner(2 * __root + 1); | |
914 | if (!_M_comp(*_M_losers[__right]._M_keyp, | |
915 | *_M_losers[__left]._M_keyp)) | |
916 | { | |
917 | // Left one is less or equal. | |
918 | _M_losers[__root] = _M_losers[__right]; | |
919 | return __left; | |
920 | } | |
921 | else | |
922 | { | |
923 | // Right one is less. | |
924 | _M_losers[__root] = _M_losers[__left]; | |
925 | return __right; | |
926 | } | |
927 | } | |
928 | } | |
929 | ||
930 | void | |
931 | __init() | |
932 | { | |
933 | _M_losers[0] = _M_losers[__init_winner(1)]; | |
c2ba9709 | 934 | |
e383deac | 935 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
936 | // no dummy sequence can ever be at the top at the beginning |
937 | // (0 sequences!) | |
938 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
c2ba9709 | 939 | #endif |
77d16198 | 940 | } |
dfbed397 | 941 | |
77d16198 PC |
942 | void |
943 | __delete_min_insert(const _Tp& __key, bool __sup) | |
944 | { | |
e383deac | 945 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
946 | // no dummy sequence can ever be at the top! |
947 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
3234d6b0 JS |
948 | #endif |
949 | ||
77d16198 PC |
950 | const _Tp* __keyp = &__key; |
951 | int __source = _M_losers[0]._M_source; | |
952 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
953 | __pos /= 2) | |
954 | { | |
955 | // The smaller one gets promoted, ties are broken by _M_source. | |
956 | if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp) | |
957 | || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp) | |
958 | && _M_losers[__pos]._M_source < __source)) | |
959 | { | |
960 | // The other one is smaller. | |
961 | std::swap(_M_losers[__pos]._M_source, __source); | |
962 | std::swap(_M_losers[__pos]._M_keyp, __keyp); | |
963 | } | |
964 | } | |
965 | ||
966 | _M_losers[0]._M_source = __source; | |
967 | _M_losers[0]._M_keyp = __keyp; | |
968 | } | |
969 | }; | |
970 | ||
971 | /** | |
972 | * @brief Unstable unguarded _LoserTree variant storing pointers. | |
973 | * | |
974 | * Stable variant is above. | |
975 | */ | |
976 | template<typename _Tp, typename _Compare> | |
977 | class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare> | |
978 | : public _LoserTreePointerUnguardedBase<_Tp, _Compare> | |
d87f43c3 | 979 | { |
77d16198 PC |
980 | typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base; |
981 | using _Base::_M_k; | |
e330aa5b | 982 | using _Base::_M_comp; |
77d16198 PC |
983 | using _Base::_M_losers; |
984 | ||
985 | public: | |
986 | _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel, | |
987 | _Compare __comp = std::less<_Tp>()) | |
988 | : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp) | |
989 | { } | |
990 | ||
991 | unsigned int | |
992 | __init_winner(unsigned int __root) | |
993 | { | |
994 | if (__root >= _M_k) | |
995 | return __root; | |
996 | else | |
997 | { | |
998 | unsigned int __left = __init_winner(2 * __root); | |
999 | unsigned int __right = __init_winner(2 * __root + 1); | |
f9985df5 | 1000 | |
e383deac | 1001 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
1002 | // If __left one is sentinel then __right one must be, too. |
1003 | if (_M_losers[__left]._M_source == -1) | |
1004 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1); | |
dfbed397 | 1005 | #endif |
dfbed397 | 1006 | |
77d16198 PC |
1007 | if (!_M_comp(*_M_losers[__right]._M_keyp, |
1008 | *_M_losers[__left]._M_keyp)) | |
1009 | { | |
1010 | // Left one is less or equal. | |
1011 | _M_losers[__root] = _M_losers[__right]; | |
1012 | return __left; | |
1013 | } | |
1014 | else | |
1015 | { | |
1016 | // Right one is less. | |
1017 | _M_losers[__root] = _M_losers[__left]; | |
1018 | return __right; | |
1019 | } | |
1020 | } | |
1021 | } | |
1022 | ||
1023 | void | |
1024 | __init() | |
1025 | { | |
1026 | _M_losers[0] = _M_losers[__init_winner(1)]; | |
f9985df5 | 1027 | |
e383deac | 1028 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
1029 | // no dummy sequence can ever be at the top at the beginning |
1030 | // (0 sequences!) | |
1031 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
dfbed397 | 1032 | #endif |
77d16198 | 1033 | } |
dfbed397 | 1034 | |
77d16198 PC |
1035 | void |
1036 | __delete_min_insert(const _Tp& __key, bool __sup) | |
1037 | { | |
e383deac | 1038 | #if _GLIBCXX_PARALLEL_ASSERTIONS |
77d16198 PC |
1039 | // no dummy sequence can ever be at the top! |
1040 | _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1); | |
3234d6b0 JS |
1041 | #endif |
1042 | ||
77d16198 PC |
1043 | const _Tp* __keyp = &__key; |
1044 | int __source = _M_losers[0]._M_source; | |
1045 | for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0; | |
1046 | __pos /= 2) | |
1047 | { | |
1048 | // The smaller one gets promoted. | |
1049 | if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp)) | |
1050 | { | |
1051 | // The other one is smaller. | |
1052 | std::swap(_M_losers[__pos]._M_source, __source); | |
1053 | std::swap(_M_losers[__pos]._M_keyp, __keyp); | |
1054 | } | |
1055 | } | |
1056 | ||
1057 | _M_losers[0]._M_source = __source; | |
1058 | _M_losers[0]._M_keyp = __keyp; | |
1059 | } | |
1060 | }; | |
f9985df5 | 1061 | } // namespace __gnu_parallel |
c2ba9709 | 1062 | |
cbcd1e45 | 1063 | #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */ |