OSDN Git Service

2011-05-27 Paolo Carlini <paolo.carlini@oracle.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / parallel / losertree.h
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>
55     class _LoserTreeBase
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. */
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()
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        */
155       int __get_min_source()
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>
169     class _LoserTree
170     : public _LoserTreeBase<_Tp, _Compare>
171     {
172       typedef _LoserTreeBase<_Tp, _Compare> _Base;
173       using _Base::_M_k;
174       using _Base::_M_comp;
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       {
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     {
264       typedef _LoserTreeBase<_Tp, _Compare> _Base;
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>
357     class _LoserTreePointerBase
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
387       ~_LoserTreePointerBase()
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>
409     class _LoserTreePointer
410     : public _LoserTreePointerBase<_Tp, _Compare>
411     {
412       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
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     {
494       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
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>
574     class _LoserTreeUnguardedBase
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
613       ~_LoserTreeUnguardedBase()
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>
646     class _LoserTreeUnguarded
647     : public _LoserTreeUnguardedBase<_Tp, _Compare>
648     {
649       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
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     {
737       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
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>
828     class _LoserTreePointerUnguardedBase
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
862       ~_LoserTreePointerUnguardedBase()
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>
891     class _LoserTreePointerUnguarded
892     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
893     {
894       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
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     {
980       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
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 */