OSDN Git Service

cb24f7f6771d2cb9ecf78b503052198bf281fb77
[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_losers;
175       using _Base::_M_first_insert;
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     {
263       typedef _LoserTreeBase<_Tp, _Compare> _Base;
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>
355     class _LoserTreePointerBase
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
385       ~_LoserTreePointerBase()
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>
407     class _LoserTreePointer
408     : public _LoserTreePointerBase<_Tp, _Compare>
409     {
410       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
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     {
491       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
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>
570     class _LoserTreeUnguardedBase
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
609       ~_LoserTreeUnguardedBase()
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>
642     class _LoserTreeUnguarded
643     : public _LoserTreeUnguardedBase<_Tp, _Compare>
644     {
645       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
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     {
732       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
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>
822     class _LoserTreePointerUnguardedBase
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
856       ~_LoserTreePointerUnguardedBase()
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>
885     class _LoserTreePointerUnguarded
886     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
887     {
888       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
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     {
973       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
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 */