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_comp;
175  using _Base::_M_losers;
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  {
224  using std::swap;
225 #if _GLIBCXX_ASSERTIONS
226  // no dummy sequence can ever be at the top!
227  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
228 #endif
229 
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);
245  swap(_M_losers[__pos]._M_key, __key);
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  };
254 
255  /**
256  * @brief Unstable _LoserTree variant.
257  *
258  * Stability (non-stable here) is selected with partial specialization.
259  */
260  template<typename _Tp, typename _Compare>
261  class _LoserTree</* __stable == */false, _Tp, _Compare>
262  : public _LoserTreeBase<_Tp, _Compare>
263  {
265  using _Base::_M_log_k;
266  using _Base::_M_k;
267  using _Base::_M_comp;
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  {
326  using std::swap;
327 #if _GLIBCXX_ASSERTIONS
328  // no dummy sequence can ever be at the top!
329  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
330 #endif
331 
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);
343  swap(_M_losers[__pos]._M_key, __key);
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  };
352 
353  /**
354  * @brief Base class of _Loser Tree implementation using pointers.
355  */
356  template<typename _Tp, typename _Compare>
358  {
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 
388  { delete[] _M_losers; }
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  };
402 
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>
410  : public _LoserTreePointerBase<_Tp, _Compare>
411  {
413  using _Base::_M_k;
414  using _Base::_M_comp;
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  {
454 #if _GLIBCXX_ASSERTIONS
455  // no dummy sequence can ever be at the top!
456  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
457 #endif
458 
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  };
484 
485  /**
486  * @brief Unstable _LoserTree implementation.
487  *
488  * The stable variant is above.
489  */
490  template<typename _Tp, typename _Compare>
491  class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
492  : public _LoserTreePointerBase<_Tp, _Compare>
493  {
495  using _Base::_M_k;
496  using _Base::_M_comp;
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  {
536 #if _GLIBCXX_ASSERTIONS
537  // no dummy sequence can ever be at the top!
538  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
539 #endif
540 
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  }
561  };
562 
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 &gt; all elements that are to be merged.
570  *
571  * This is a very fast variant.
572  */
573  template<typename _Tp, typename _Compare>
575  {
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:
588  _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel,
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 
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);
609  _M_losers[__i]._M_source = -1;
610  }
611  }
612 
614  {
615  for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
616  _M_losers[__i].~_Loser();
617  ::operator delete(_M_losers);
618  }
619 
620  int
621  __get_min_source()
622  {
623 #if _GLIBCXX_ASSERTIONS
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  }
629 
630  void
631  __insert_start(const _Tp& __key, int __source, bool)
632  {
633  unsigned int __pos = _M_k + __source;
634 
635  ::new(&(_M_losers[__pos]._M_key)) _Tp(__key);
636  _M_losers[__pos]._M_source = __source;
637  }
638  };
639 
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>
647  : public _LoserTreeUnguardedBase<_Tp, _Compare>
648  {
650  using _Base::_M_k;
651  using _Base::_M_comp;
652  using _Base::_M_losers;
653 
654  public:
655  _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
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)];
689 
690 #if _GLIBCXX_ASSERTIONS
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);
694 #endif
695  }
696 
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  {
702  using std::swap;
703 #if _GLIBCXX_ASSERTIONS
704  // no dummy sequence can ever be at the top!
705  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
706 #endif
707 
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);
719  swap(_M_losers[__pos]._M_key, __key);
720  }
721  }
722 
723  _M_losers[0]._M_source = __source;
724  _M_losers[0]._M_key = __key;
725  }
726  };
727 
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>
736  {
738  using _Base::_M_k;
739  using _Base::_M_comp;
740  using _Base::_M_losers;
741 
742  public:
743  _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
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);
757 
758 #if _GLIBCXX_ASSERTIONS
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);
762 #endif
763 
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)];
784 
785 #if _GLIBCXX_ASSERTIONS
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);
789 #endif
790  }
791 
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  {
797  using std::swap;
798 #if _GLIBCXX_ASSERTIONS
799  // no dummy sequence can ever be at the top!
800  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
801 #endif
802 
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);
812  swap(_M_losers[__pos]._M_key, __key);
813  }
814  }
815 
816  _M_losers[0]._M_source = __source;
817  _M_losers[0]._M_key = __key;
818  }
819  };
820 
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>
829  {
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 
863  { delete[] _M_losers; }
864 
865  int
866  __get_min_source()
867  {
868 #if _GLIBCXX_ASSERTIONS
869  // no dummy sequence can ever be at the top!
870  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
871 #endif
872  return _M_losers[0]._M_source;
873  }
874 
875  void
876  __insert_start(const _Tp& __key, int __source, bool)
877  {
878  unsigned int __pos = _M_k + __source;
879 
880  _M_losers[__pos]._M_keyp = &__key;
881  _M_losers[__pos]._M_source = __source;
882  }
883  };
884 
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>
892  : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
893  {
895  using _Base::_M_k;
896  using _Base::_M_comp;
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)];
934 
935 #if _GLIBCXX_ASSERTIONS
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);
939 #endif
940  }
941 
942  void
943  __delete_min_insert(const _Tp& __key, bool __sup)
944  {
945 #if _GLIBCXX_ASSERTIONS
946  // no dummy sequence can ever be at the top!
947  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
948 #endif
949 
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>
979  {
981  using _Base::_M_k;
982  using _Base::_M_comp;
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);
1000 
1001 #if _GLIBCXX_ASSERTIONS
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);
1005 #endif
1006 
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)];
1027 
1028 #if _GLIBCXX_ASSERTIONS
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);
1032 #endif
1033  }
1034 
1035  void
1036  __delete_min_insert(const _Tp& __key, bool __sup)
1037  {
1038 #if _GLIBCXX_ASSERTIONS
1039  // no dummy sequence can ever be at the top!
1040  _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1041 #endif
1042 
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  };
1061 } // namespace __gnu_parallel
1062 
1063 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */