[gcc] GCC 4.5.0=>4.5.1

gcc/libstdc++-v3/include/parallel/losertree.h

Index: gcc/libstdc++-v3/include/parallel/losertree.h
diff --git a/gcc/libstdc++-v3/include/parallel/losertree.h b/gcc/libstdc++-v3/include/parallel/losertree.h
deleted file mode 100644
index 6dbd59288641cbf748dcef970f7590f64931b0f3..0000000000000000000000000000000000000000
--- a/gcc/libstdc++-v3/include/parallel/losertree.h
+++ /dev/null
@@ -1,1021 +0,0 @@
-// -*- C++ -*-
-
-// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library.  This library is free
-// software; you can redistribute it and/or modify it under the terms
-// of the GNU General Public License as published by the Free Software
-// Foundation; either version 3, or (at your option) any later
-// version.
-
-// This library is distributed in the hope that it will be useful, but
-// WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-// General Public License for more details.
-
-// Under Section 7 of GPL version 3, you are granted additional
-// permissions described in the GCC Runtime Library Exception, version
-// 3.1, as published by the Free Software Foundation.
-
-// You should have received a copy of the GNU General Public License and
-// a copy of the GCC Runtime Library Exception along with this program;
-// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
-// <http://www.gnu.org/licenses/>.
-
-/** @file parallel/losertree.h
-*  @brief Many generic loser tree variants.
-*  This file is a GNU parallel extension to the Standard C++ Library.
-*/
-
-// Written by Johannes Singler.
-
-#ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
-#define _GLIBCXX_PARALLEL_LOSERTREE_H 1
-
-#include <functional>
-
-#include <bits/stl_algobase.h>
-#include <parallel/features.h>
-#include <parallel/base.h>
-
-namespace __gnu_parallel
-{
-
-/**
- * @brief Guarded loser/tournament tree.
- *
- * The smallest element is at the top.
- *
- * Guarding is done explicitly through one flag sup per element,
- * inf is not needed due to a better initialization routine.  This
- * is a well-performing variant.
- *
- * @param T the element type
- * @param Comparator the comparator to use, defaults to std::less<T>
- */
-template<typename T, typename Comparator>
-class LoserTreeBase
-{
-protected:
-  /** @brief Internal representation of a LoserTree element. */
-  struct Loser
-  {
-    /** @brief flag, true iff this is a "maximum" sentinel. */
-    bool sup;
-    /** @brief index of the source sequence. */
-    int source;
-    /** @brief key of the element in the LoserTree. */
-    T key;
-  };
-
-  unsigned int ik, k, offset;
-
-  /** log_2{k} */
-  unsigned int _M_log_k;
-
-  /** @brief LoserTree elements. */
-  Loser* losers;
-
-  /** @brief Comparator to use. */
-  Comparator comp;
-
-  /**
-   * @brief State flag that determines whether the LoserTree is empty.
-   *
-   * Only used for building the LoserTree.
-   */
-  bool first_insert;
-
-public:
-  /**
-   * @brief The constructor.
-   *
-   * @param _k The number of sequences to merge.
-   * @param _comp The comparator to use.
-   */
-  LoserTreeBase(unsigned int _k, Comparator _comp)
-  : comp(_comp)
-  {
-    ik = _k;
-
-    // Compute log_2{k} for the Loser Tree
-    _M_log_k = __log2(ik - 1) + 1;
-
-    // Next greater power of 2.
-    k = 1 << _M_log_k;
-    offset = k;
-
-    // Avoid default-constructing losers[].key
-    losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
-    for (unsigned int i = ik - 1; i < k; ++i)
-      losers[i + k].sup = true;
-
-    first_insert = true;
-  }
-
-  /**
-   * @brief The destructor.
-   */
-  ~LoserTreeBase()
-  { ::operator delete(losers); }
-
-  /**
-   * @brief Initializes the sequence "source" with the element "key".
-   *
-   * @param key the element to insert
-   * @param source index of the source sequence
-   * @param sup flag that determines whether the value to insert is an
-   *   explicit supremum.
-   */
-  inline void
-  insert_start(const T& key, int source, bool sup)
-  {
-    unsigned int pos = k + source;
-
-    if(first_insert)
-      {
-        // Construct all keys, so we can easily deconstruct them.
-        for (unsigned int i = 0; i < (2 * k); ++i)
-          new(&(losers[i].key)) T(key);
-        first_insert = false;
-      }
-    else
-      new(&(losers[pos].key)) T(key);
-
-    losers[pos].sup = sup;
-    losers[pos].source = source;
-  }
-
-  /**
-   * @return the index of the sequence with the smallest element.
-   */
-  int get_min_source()
-  { return losers[0].source; }
-};
-
-/**
- * @brief Stable LoserTree variant.
- *
- * Provides the stable implementations of insert_start, init_winner,
- * init and delete_min_insert.
- *
- * Unstable variant is done using partial specialisation below.
- */
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTree : public LoserTreeBase<T, Comparator>
-{
-  typedef LoserTreeBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-  using Base::first_insert;
-
-public:
-  LoserTree(unsigned int _k, Comparator _comp)
-  : Base::LoserTreeBase(_k, _comp)
-  {}
-
-  unsigned int
-  init_winner(unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-        if (losers[right].sup
-            || (!losers[left].sup
-              && !comp(losers[right].key, losers[left].key)))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  void init()
-  { losers[0] = losers[init_winner(1)]; }
-
-  /**
-   * @brief Delete the smallest element and insert a new element from
-   *   the previously smallest element's sequence.
-   *
-   * This implementation is stable.
-   */
-  // Do not pass a const reference since key will be used as local variable.
-  void delete_min_insert(T key, bool sup)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted, ties are broken by source.
-        if ((sup && (!losers[pos].sup || losers[pos].source < source))
-              || (!sup && !losers[pos].sup
-                && ((comp(losers[pos].key, key))
-                  || (!comp(key, losers[pos].key)
-                    && losers[pos].source < source))))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].sup, sup);
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].key, key);
-          }
-      }
-
-    losers[0].sup = sup;
-    losers[0].source = source;
-    losers[0].key = key;
-  }
-};
-
-/**
- * @brief Unstable LoserTree variant.
- *
- * Stability (non-stable here) is selected with partial specialization.
- */
-template<typename T, typename Comparator>
-class LoserTree</* stable == */false, T, Comparator> :
-    public LoserTreeBase<T, Comparator>
-{
-  typedef LoserTreeBase<T, Comparator> Base;
-  using Base::_M_log_k;
-  using Base::k;
-  using Base::losers;
-  using Base::first_insert;
-
-public:
-  LoserTree(unsigned int _k, Comparator _comp)
-  : Base::LoserTreeBase(_k, _comp)
-  {}
-
-  /**
-   * Computes the winner of the competition at position "root".
-   *
-   * Called recursively (starting at 0) to build the initial tree.
-   *
-   * @param root index of the "game" to start.
-   */
-  unsigned int
-  init_winner (unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-        if (losers[right].sup ||
-            (!losers[left].sup
-              && !comp(losers[right].key, losers[left].key)))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  inline void
-  init()
-  { losers[0] = losers[init_winner(1)]; }
-
-  /**
-   * Delete the key smallest element and insert the element key instead.
-   *
-   * @param key the key to insert
-   * @param sup true iff key is an explicitly marked supremum
-   */
-  // Do not pass a const reference since key will be used as local variable.
-  inline void
-  delete_min_insert(T key, bool sup)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-    {
-        // The smaller one gets promoted.
-      if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
-      {
-            // The other one is smaller.
-        std::swap(losers[pos].sup, sup);
-        std::swap(losers[pos].source, source);
-        std::swap(losers[pos].key, key);
-      }
-    }
-
-    losers[0].sup = sup;
-    losers[0].source = source;
-    losers[0].key = key;
-  }
-};
-
-
-/**
- * @brief Base class of Loser Tree implementation using pointers.
- */
-template<typename T, typename Comparator>
-class LoserTreePointerBase
-{
-protected:
-  /** @brief Internal representation of LoserTree elements. */
-  struct Loser
-  {
-    bool sup;
-    int source;
-    const T* keyp;
-  };
-
-  unsigned int ik, k, offset;
-  Loser* losers;
-  Comparator comp;
-
-public:
-  LoserTreePointerBase(unsigned int _k, Comparator _comp = std::less<T>())
-    : comp(_comp)
-  {
-    ik = _k;
-
-    // Next greater power of 2.
-    k = 1 << (__log2(ik - 1) + 1);
-    offset = k;
-    losers = new Loser[k * 2];
-    for (unsigned int i = ik - 1; i < k; i++)
-      losers[i + k].sup = true;
-  }
-
-  ~LoserTreePointerBase()
-  { ::operator delete[](losers); }
-
-  int get_min_source()
-  { return losers[0].source; }
-
-  void insert_start(const T& key, int source, bool sup)
-  {
-    unsigned int pos = k + source;
-
-    losers[pos].sup = sup;
-    losers[pos].source = source;
-    losers[pos].keyp = &key;
-  }
-};
-
-/**
- * @brief Stable LoserTree implementation.
- *
- * The unstable variant is implemented using partial instantiation below.
- */
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTreePointer : public LoserTreePointerBase<T, Comparator>
-{
-  typedef LoserTreePointerBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-
-public:
-  LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
-    : Base::LoserTreePointerBase(_k, _comp)
-  {}
-
-  unsigned int
-  init_winner(unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-        if (losers[right].sup
-            || (!losers[left].sup && !comp(*losers[right].keyp,
-                                          *losers[left].keyp)))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  void init()
-  { losers[0] = losers[init_winner(1)]; }
-
-  void delete_min_insert(const T& key, bool sup)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    const T* keyp = &key;
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted, ties are broken by source.
-        if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
-              (!sup && !losers[pos].sup &&
-              ((comp(*losers[pos].keyp, *keyp)) ||
-                (!comp(*keyp, *losers[pos].keyp)
-                && losers[pos].source < source))))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].sup, sup);
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].keyp, keyp);
-          }
-      }
-
-    losers[0].sup = sup;
-    losers[0].source = source;
-    losers[0].keyp = keyp;
-  }
-};
-
-/**
- * @brief Unstable LoserTree implementation.
- *
- * The stable variant is above.
- */
-template<typename T, typename Comparator>
-class LoserTreePointer</* stable == */false, T, Comparator> :
-    public LoserTreePointerBase<T, Comparator>
-{
-  typedef LoserTreePointerBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-
-public:
-  LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
-    : Base::LoserTreePointerBase(_k, _comp)
-  {}
-
-  unsigned int
-  init_winner(unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-        if (losers[right].sup
-              || (!losers[left].sup
-                && !comp(*losers[right].keyp, *losers[left].keyp)))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  void init()
-  { losers[0] = losers[init_winner(1)]; }
-
-  void delete_min_insert(const T& key, bool sup)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    const T* keyp = &key;
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted.
-        if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].sup, sup);
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].keyp, keyp);
-          }
-      }
-
-    losers[0].sup = sup;
-    losers[0].source = source;
-    losers[0].keyp = keyp;
-  }
-};
-
-/** @brief Base class for unguarded LoserTree implementation.
- * 
- * The whole element is copied into the tree structure.
- *
- * No guarding is done, therefore not a single input sequence must
- * run empty.  Unused sequence heads are marked with a sentinel which
- * is &gt; all elements that are to be merged.
- *
- * This is a very fast variant.
- */
-template<typename T, typename Comparator>
-class LoserTreeUnguardedBase
-{
-protected:
-  struct Loser
-  {
-    int source;
-    T key;
-  };
-
-  unsigned int ik, k, offset;
-  Loser* losers;
-  Comparator comp;
-
-public:
-  inline
-  LoserTreeUnguardedBase(unsigned int _k, const T _sentinel,
-                         Comparator _comp = std::less<T>())
-    : comp(_comp)
-  {
-    ik = _k;
-
-    // Next greater power of 2.
-    k = 1 << (__log2(ik - 1) + 1);
-    offset = k;
-    // Avoid default-constructing losers[].key
-    losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
-
-    for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
-      {
-        losers[i].key = _sentinel;
-        losers[i].source = -1;
-      }
-  }
-
-  inline ~LoserTreeUnguardedBase()
-  { ::operator delete(losers); }
-
-  inline int
-  get_min_source()
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-    return losers[0].source;
-  }
-
-  inline void
-  insert_start(const T& key, int source, bool)
-  {
-    unsigned int pos = k + source;
-
-    new(&(losers[pos].key)) T(key);
-    losers[pos].source = source;
-  }
-};
-
-/**
- * @brief Stable implementation of unguarded LoserTree.
- *
- * Unstable variant is selected below with partial specialization.
- */
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTreeUnguarded : public LoserTreeUnguardedBase<T, Comparator>
-{
-  typedef LoserTreeUnguardedBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-
-public:
-  LoserTreeUnguarded(unsigned int _k, const T _sentinel,
-                     Comparator _comp = std::less<T>())
-    : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
-  {}
-
-  unsigned int
-  init_winner(unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-        if (!comp(losers[right].key, losers[left].key))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  inline void
-  init()
-  {
-    losers[0] = losers[init_winner(1)];
-
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top at the beginning (0 sequences!)
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-  }
-
-  // Do not pass a const reference since key will be used as local variable.
-  inline void
-  delete_min_insert(T key, bool)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted, ties are broken by source.
-        if (comp(losers[pos].key, key)
-              || (!comp(key, losers[pos].key) && losers[pos].source < source))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].key, key);
-          }
-      }
-
-    losers[0].source = source;
-    losers[0].key = key;
-  }
-};
-
-/**
- * @brief Non-Stable implementation of unguarded LoserTree.
- *
- * Stable implementation is above.
- */
-template<typename T, typename Comparator>
-class LoserTreeUnguarded</* stable == */false, T, Comparator> :
-    public LoserTreeUnguardedBase<T, Comparator>
-{
-  typedef LoserTreeUnguardedBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-
-public:
-  LoserTreeUnguarded(unsigned int _k, const T _sentinel,
-                     Comparator _comp = std::less<T>())
-    : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
-  {}
-
-  unsigned int
-  init_winner (unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-
-#if _GLIBCXX_ASSERTIONS
-        // If left one is sentinel then right one must be, too.
-        if (losers[left].source == -1)
-          _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
-#endif
-
-        if (!comp(losers[right].key, losers[left].key))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  inline void
-  init()
-  {
-    losers[0] = losers[init_winner(1)];
-
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top at the beginning (0 sequences!)
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-  }
-
-  // Do not pass a const reference since key will be used as local variable.
-  inline void
-  delete_min_insert(T key, bool)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted.
-        if (comp(losers[pos].key, key))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].key, key);
-          }
-      }
-
-    losers[0].source = source;
-    losers[0].key = key;
-  }
-};
-
-/** @brief Unguarded loser tree, keeping only pointers to the
-* elements in the tree structure.
-*
-*  No guarding is done, therefore not a single input sequence must
-*  run empty.  This is a very fast variant.
-*/
-template<typename T, typename Comparator>
-class LoserTreePointerUnguardedBase
-{
-protected:
-  struct Loser
-  {
-    int source;
-    const T* keyp;
-  };
-
-  unsigned int ik, k, offset;
-  Loser* losers;
-  Comparator comp;
-
-public:
-
-  inline
-  LoserTreePointerUnguardedBase(unsigned int _k, const T& _sentinel,
-      Comparator _comp = std::less<T>())
-    : comp(_comp)
-  {
-    ik = _k;
-
-    // Next greater power of 2.
-    k = 1 << (__log2(ik - 1) + 1);
-    offset = k;
-    // Avoid default-constructing losers[].key
-    losers = new Loser[2 * k];
-
-    for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
-      {
-        losers[i].keyp = &_sentinel;
-        losers[i].source = -1;
-      }
-  }
-
-  inline ~LoserTreePointerUnguardedBase()
-  { delete[] losers; }
-
-  inline int
-  get_min_source()
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-    return losers[0].source;
-  }
-
-  inline void
-  insert_start(const T& key, int source, bool)
-  {
-    unsigned int pos = k + source;
-
-    losers[pos].keyp = &key;
-    losers[pos].source = source;
-  }
-};
-
-/**
- * @brief Stable unguarded LoserTree variant storing pointers.
- *
- * Unstable variant is implemented below using partial specialization.
- */
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTreePointerUnguarded :
-    public LoserTreePointerUnguardedBase<T, Comparator>
-{
-  typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-
-public:
-  LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
-      Comparator _comp = std::less<T>())
-    : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
-  {}
-
-  unsigned int
-  init_winner(unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-        if (!comp(*losers[right].keyp, *losers[left].keyp))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  inline void
-  init()
-  {
-    losers[0] = losers[init_winner(1)];
-
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top at the beginning (0 sequences!)
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-  }
-
-  inline void
-  delete_min_insert(const T& key, bool sup)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    const T* keyp = &key;
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted, ties are broken by source.
-        if (comp(*losers[pos].keyp, *keyp)
-          || (!comp(*keyp, *losers[pos].keyp) && losers[pos].source < source))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].keyp, keyp);
-          }
-      }
-
-    losers[0].source = source;
-    losers[0].keyp = keyp;
-  }
-};
-
-/**
- * @brief Unstable unguarded LoserTree variant storing pointers.
- *
- * Stable variant is above.
- */
-template<typename T, typename Comparator>
-class LoserTreePointerUnguarded</* stable == */false, T, Comparator> :
-    public LoserTreePointerUnguardedBase<T, Comparator>
-{
-  typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
-  using Base::k;
-  using Base::losers;
-
-public:
-  LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
-      Comparator _comp = std::less<T>())
-    : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
-  {}
-
-  unsigned int
-  init_winner(unsigned int root)
-  {
-    if (root >= k)
-      {
-        return root;
-      }
-    else
-      {
-        unsigned int left = init_winner (2 * root);
-        unsigned int right = init_winner (2 * root + 1);
-
-#if _GLIBCXX_ASSERTIONS
-        // If left one is sentinel then right one must be, too.
-        if (losers[left].source == -1)
-          _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
-#endif
-
-        if (!comp(*losers[right].keyp, *losers[left].keyp))
-          {
-            // Left one is less or equal.
-            losers[root] = losers[right];
-            return left;
-          }
-        else
-          {
-            // Right one is less.
-            losers[root] = losers[left];
-            return right;
-          }
-      }
-  }
-
-  inline void
-  init()
-  {
-    losers[0] = losers[init_winner(1)];
-
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top at the beginning (0 sequences!)
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-  }
-
-  inline void
-  delete_min_insert(const T& key, bool sup)
-  {
-#if _GLIBCXX_ASSERTIONS
-    // no dummy sequence can ever be at the top!
-    _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
-#endif
-
-    const T* keyp = &key;
-    int source = losers[0].source;
-    for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
-      {
-        // The smaller one gets promoted.
-        if (comp(*(losers[pos].keyp), *keyp))
-          {
-            // The other one is smaller.
-            std::swap(losers[pos].source, source);
-            std::swap(losers[pos].keyp, keyp);
-          }
-      }
-
-    losers[0].source = source;
-    losers[0].keyp = keyp;
-  }
-};
-
-} // namespace __gnu_parallel
-
-#endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */