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