diff DEPENDENCIES/generic/include/boost/intrusive/sgtree.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

--- a/DEPENDENCIES/generic/include/boost/intrusive/sgtree.hpp	Fri Sep 04 12:01:02 2015 +0100
+++ b/DEPENDENCIES/generic/include/boost/intrusive/sgtree.hpp	Mon Sep 07 11:12:49 2015 +0100
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2007-2013
+// (C) Copyright Ion Gaztanaga 2007-2014
 //
 // Distributed under the Boost Software License, Version 1.0.
 //    (See accompanying file LICENSE_1_0.txt or copy at
@@ -19,27 +19,32 @@
 #define BOOST_INTRUSIVE_SGTREE_HPP
 
 #include <boost/intrusive/detail/config_begin.hpp>
-#include <algorithm>
-#include <cstddef>
-#include <functional>
-#include <iterator>
-#include <utility>
-#include <cmath>
-#include <cstddef>
+#include <boost/intrusive/intrusive_fwd.hpp>
 #include <boost/intrusive/detail/assert.hpp>
 #include <boost/static_assert.hpp>
-#include <boost/intrusive/intrusive_fwd.hpp>
 #include <boost/intrusive/bs_set_hook.hpp>
 #include <boost/intrusive/bstree.hpp>
 #include <boost/intrusive/detail/tree_node.hpp>
-#include <boost/intrusive/detail/ebo_functor_holder.hpp>
 #include <boost/intrusive/pointer_traits.hpp>
 #include <boost/intrusive/detail/mpl.hpp>
-#include <boost/intrusive/detail/utilities.hpp>
-#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/detail/math.hpp>
+#include <boost/intrusive/detail/get_value_traits.hpp>
 #include <boost/intrusive/sgtree_algorithms.hpp>
+#include <boost/intrusive/detail/key_nodeptr_comp.hpp>
 #include <boost/intrusive/link_mode.hpp>
-#include <boost/move/move.hpp>
+
+#include <boost/move/utility_core.hpp>
+#include <boost/move/adl_move_swap.hpp>
+
+#include <cstddef>
+#include <boost/intrusive/detail/minimal_less_equal_header.hpp>
+#include <boost/intrusive/detail/minimal_pair_header.hpp>   //std::pair
+#include <cmath>
+#include <cstddef>
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#  pragma once
+#endif
 
 namespace boost {
 namespace intrusive {
@@ -48,6 +53,12 @@
 
 namespace detail{
 
+/////////////////////////////////////////////////////////////
+//
+//       Halpha for fixed floating_point<false> option
+//
+/////////////////////////////////////////////////////////////
+
 //! Returns floor(log2(n)/log2(sqrt(2))) -> floor(2*log2(n))
 //! Undefined if N is 0.
 //!
@@ -55,7 +66,7 @@
 inline std::size_t calculate_h_sqrt2 (std::size_t n)
 {
    std::size_t f_log2 = detail::floor_log2(n);
-   return (2*f_log2) + (n >= detail::sqrt2_pow_2xplus1 (f_log2));
+   return (2*f_log2) + static_cast<std::size_t>(n >= detail::sqrt2_pow_2xplus1(f_log2));
 }
 
 struct h_alpha_sqrt2_t
@@ -76,6 +87,12 @@
    }
 };
 
+/////////////////////////////////////////////////////////////
+//
+//       Halpha for fixed floating_point<true> option
+//
+/////////////////////////////////////////////////////////////
+
 struct h_alpha_t
 {
    explicit h_alpha_t(float inv_minus_logalpha)
@@ -84,10 +101,12 @@
 
    std::size_t operator()(std::size_t n) const
    {
-      //Returns floor(log2(1/alpha(n))) ->
-      // floor(log2(n)/log(1/alpha)) ->
-      // floor(log2(n)/(-log2(alpha)))
-      //return static_cast<std::size_t>(std::log(float(n))*inv_minus_logalpha_);
+      ////////////////////////////////////////////////////////////
+      // This function must return "floor(log2(1/alpha(n)))" ->
+      //    floor(log2(n)/log(1/alpha)) ->
+      //    floor(log2(n)/-log2(alpha))
+      //    floor(log2(n)*(1/-log2(alpha)))
+      ////////////////////////////////////////////////////////////
       return static_cast<std::size_t>(detail::fast_log2(float(n))*inv_minus_logalpha_);
    }
 
@@ -118,8 +137,9 @@
    typedef boost::intrusive::detail::h_alpha_t           h_alpha_t;
    typedef boost::intrusive::detail::alpha_by_max_size_t multiply_by_alpha_t;
 
-   alpha_holder() : max_tree_size_(0)
-   {  set_alpha(0.7f);   }
+   alpha_holder()
+      : max_tree_size_()
+   {  set_alpha(0.70711f);   } // ~1/sqrt(2)
 
    float get_alpha() const
    {  return alpha_;  }
@@ -131,7 +151,7 @@
    }
 
    h_alpha_t get_h_alpha_t() const
-   {  return h_alpha_t(/*alpha_, */inv_minus_logalpha_);  }
+   {  return h_alpha_t(inv_minus_logalpha_);  }
 
    multiply_by_alpha_t get_multiply_by_alpha_t() const
    {  return multiply_by_alpha_t(alpha_);  }
@@ -151,6 +171,10 @@
    typedef boost::intrusive::detail::h_alpha_sqrt2_t           h_alpha_t;
    typedef boost::intrusive::detail::alpha_0_75_by_max_size_t  multiply_by_alpha_t;
 
+   alpha_holder()
+      : max_tree_size_()
+   {}
+
    float get_alpha() const
    {  return 0.70710677f;  }
 
@@ -172,11 +196,12 @@
 
 struct sgtree_defaults
 {
-   typedef detail::default_bstree_hook proto_value_traits;
+   typedef default_bstree_hook_applier proto_value_traits;
    static const bool constant_time_size = true;
    typedef std::size_t size_type;
    typedef void compare;
    static const bool floating_point = true;
+   typedef void header_holder_type;
 };
 
 /// @endcond
@@ -197,11 +222,11 @@
 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 template<class T, class ...Options>
 #else
-template<class ValueTraits, class VoidOrKeyComp, class SizeType, bool FloatingPoint>
+template<class ValueTraits, class VoidOrKeyComp, class SizeType, bool FloatingPoint, typename HeaderHolder>
 #endif
 class sgtree_impl
    /// @cond
-   :  public bstree_impl<ValueTraits, VoidOrKeyComp, SizeType, true, SgTreeAlgorithms>
+   :  public bstree_impl<ValueTraits, VoidOrKeyComp, SizeType, true, SgTreeAlgorithms, HeaderHolder>
    ,  public detail::alpha_holder<FloatingPoint, SizeType>
    /// @endcond
 {
@@ -209,9 +234,8 @@
    typedef ValueTraits                                               value_traits;
    /// @cond
    typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType
-                      , true, SgTreeAlgorithms>                      tree_type;
+                      , true, SgTreeAlgorithms, HeaderHolder>        tree_type;
    typedef tree_type                                                 implementation_defined;
-   typedef typename tree_type::real_value_traits                     real_value_traits;
 
    /// @endcond
 
@@ -248,11 +272,11 @@
    typedef typename alpha_traits::multiply_by_alpha_t       multiply_by_alpha_t;
 
    BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree_impl)
-   BOOST_STATIC_ASSERT(((int)real_value_traits::link_mode != (int)auto_unlink));
+   BOOST_STATIC_ASSERT(((int)value_traits::link_mode != (int)auto_unlink));
 
    enum { safemode_or_autounlink  =
-            (int)real_value_traits::link_mode == (int)auto_unlink   ||
-            (int)real_value_traits::link_mode == (int)safe_link     };
+            (int)value_traits::link_mode == (int)auto_unlink   ||
+            (int)value_traits::link_mode == (int)safe_link     };
 
    /// @endcond
 
@@ -281,14 +305,14 @@
 
    //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
    sgtree_impl(BOOST_RV_REF(sgtree_impl) x)
-      :  tree_type(::boost::move(static_cast<tree_type&>(x))), alpha_traits(x.get_alpha_traits())
-   {  std::swap(this->get_alpha_traits(), x.get_alpha_traits());   }
+      :  tree_type(BOOST_MOVE_BASE(tree_type, x)), alpha_traits(x.get_alpha_traits())
+   {  ::boost::adl_move_swap(this->get_alpha_traits(), x.get_alpha_traits());   }
 
    //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
    sgtree_impl& operator=(BOOST_RV_REF(sgtree_impl) x)
    {
       this->get_alpha_traits() = x.get_alpha_traits();
-      return static_cast<sgtree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x))));
+      return static_cast<sgtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));
    }
 
    /// @cond
@@ -380,9 +404,8 @@
    void swap(sgtree_impl& other)
    {
       //This can throw
-      using std::swap;
       this->tree_type::swap(static_cast<tree_type&>(other));
-      swap(this->get_alpha_traits(), other.get_alpha_traits());
+      ::boost::adl_move_swap(this->get_alpha_traits(), other.get_alpha_traits());
    }
 
    //! @copydoc ::boost::intrusive::bstree::clone_from
@@ -397,9 +420,9 @@
    //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
    iterator insert_equal(reference value)
    {
-      detail::key_nodeptr_comp<value_compare, real_value_traits>
-         key_node_comp(this->value_comp(), &this->get_real_value_traits());
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      detail::key_nodeptr_comp<value_compare, value_traits>
+         key_node_comp(this->value_comp(), &this->get_value_traits());
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
@@ -408,15 +431,15 @@
          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(p, this->real_value_traits_ptr());
+      return iterator(p, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
    iterator insert_equal(const_iterator hint, reference value)
    {
-      detail::key_nodeptr_comp<value_compare, real_value_traits>
-         key_node_comp(this->value_comp(), &this->get_real_value_traits());
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      detail::key_nodeptr_comp<value_compare, value_traits>
+         key_node_comp(this->value_comp(), &this->get_value_traits());
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
@@ -425,7 +448,7 @@
          , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(p, this->real_value_traits_ptr());
+      return iterator(p, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
@@ -462,12 +485,12 @@
    std::pair<iterator, bool> insert_unique_check
       (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
    {
-      detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
-         comp(key_value_comp, &this->get_real_value_traits());
+      detail::key_nodeptr_comp<KeyValueCompare, value_traits>
+         comp(key_value_comp, &this->get_value_traits());
       std::pair<node_ptr, bool> ret =
          (node_algorithms::insert_unique_check
             (this->tree_type::header_ptr(), key, comp, commit_data));
-      return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
+      return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyValueCompare,insert_commit_data&)
@@ -476,18 +499,18 @@
       (const_iterator hint, const KeyType &key
       ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
    {
-      detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
-         comp(key_value_comp, &this->get_real_value_traits());
+      detail::key_nodeptr_comp<KeyValueCompare, value_traits>
+         comp(key_value_comp, &this->get_value_traits());
       std::pair<node_ptr, bool> ret =
          (node_algorithms::insert_unique_check
             (this->tree_type::header_ptr(), hint.pointed_node(), key, comp, commit_data));
-      return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
+      return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
    iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
@@ -496,7 +519,7 @@
          , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(to_insert, this->real_value_traits_ptr());
+      return iterator(to_insert, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
@@ -517,7 +540,7 @@
    //! @copydoc ::boost::intrusive::bstree::insert_before
    iterator insert_before(const_iterator pos, reference value)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
@@ -526,13 +549,13 @@
          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(p, this->real_value_traits_ptr());
+      return iterator(p, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::push_back
    void push_back(reference value)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
@@ -546,7 +569,7 @@
    //! @copydoc ::boost::intrusive::bstree::push_front
    void push_front(reference value)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
@@ -605,7 +628,7 @@
    {
       node_ptr to_erase(i.pointed_node());
       iterator ret(this->erase(i));
-      disposer(this->get_real_value_traits().to_value_ptr(to_erase));
+      disposer(this->get_value_traits().to_value_ptr(to_erase));
       return ret;
    }
 
@@ -666,10 +689,10 @@
    //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyValueCompare)const
    template<class KeyType, class KeyValueCompare>
    size_type count(const KeyType& key, KeyValueCompare comp) const;
-   
+
    //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference)
    iterator lower_bound(const_reference value);
-   
+
    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare)
    template<class KeyType, class KeyValueCompare>
    iterator lower_bound(const KeyType& key, KeyValueCompare comp);
@@ -858,7 +881,8 @@
 template<class T, class ...Options>
 #else
 template<class T, class O1 = void, class O2 = void
-                , class O3 = void, class O4 = void>
+                , class O3 = void, class O4 = void
+                , class O5 = void>
 #endif
 struct make_sgtree
 {
@@ -866,7 +890,7 @@
    typedef typename pack_options
       < sgtree_defaults,
       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-      O1, O2, O3, O4
+      O1, O2, O3, O4, O5
       #else
       Options...
       #endif
@@ -880,6 +904,7 @@
          , typename packed_options::compare
          , typename packed_options::size_type
          , packed_options::floating_point
+         , typename packed_options::header_holder_type
          > implementation_defined;
    /// @endcond
    typedef implementation_defined type;
@@ -889,14 +914,14 @@
 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 
 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-template<class T, class O1, class O2, class O3, class O4>
+template<class T, class O1, class O2, class O3, class O4, class O5>
 #else
 template<class T, class ...Options>
 #endif
 class sgtree
    :  public make_sgtree<T,
       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-      O1, O2, O3, O4
+      O1, O2, O3, O4, O5
       #else
       Options...
       #endif
@@ -905,7 +930,7 @@
    typedef typename make_sgtree
       <T,
       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-      O1, O2, O3, O4
+      O1, O2, O3, O4, O5
       #else
       Options...
       #endif
@@ -915,14 +940,13 @@
    public:
    typedef typename Base::value_compare      value_compare;
    typedef typename Base::value_traits       value_traits;
-   typedef typename Base::real_value_traits  real_value_traits;
    typedef typename Base::iterator           iterator;
    typedef typename Base::const_iterator     const_iterator;
    typedef typename Base::reverse_iterator           reverse_iterator;
    typedef typename Base::const_reverse_iterator     const_reverse_iterator;
 
    //Assert if passed value traits are compatible with the type
-   BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value));
+   BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 
    explicit sgtree( const value_compare &cmp = value_compare()
                   , const value_traits &v_traits = value_traits())
@@ -937,11 +961,11 @@
    {}
 
    sgtree(BOOST_RV_REF(sgtree) x)
-      :  Base(::boost::move(static_cast<Base&>(x)))
+      :  Base(BOOST_MOVE_BASE(Base, x))
    {}
 
    sgtree& operator=(BOOST_RV_REF(sgtree) x)
-   {  return static_cast<sgtree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x))));  }
+   {  return static_cast<sgtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
 
    static sgtree &container_from_end_iterator(iterator end_iterator)
    {  return static_cast<sgtree &>(Base::container_from_end_iterator(end_iterator));   }