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