l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/parallel/losertree.h

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