diff options
Diffstat (limited to 'boost/intrusive/detail/common_slist_algorithms.hpp')
| -rw-r--r-- | boost/intrusive/detail/common_slist_algorithms.hpp | 109 |
1 files changed, 100 insertions, 9 deletions
diff --git a/boost/intrusive/detail/common_slist_algorithms.hpp b/boost/intrusive/detail/common_slist_algorithms.hpp index 942b35a3f4..4c7f1a11e0 100644 --- a/boost/intrusive/detail/common_slist_algorithms.hpp +++ b/boost/intrusive/detail/common_slist_algorithms.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (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 @@ -13,9 +13,14 @@ #ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP -#include <boost/intrusive/detail/config_begin.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/detail/algo_type.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <cstddef> namespace boost { @@ -31,9 +36,8 @@ class common_slist_algorithms typedef typename NodeTraits::const_node_ptr const_node_ptr; typedef NodeTraits node_traits; - static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node) + static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node) { - node_ptr p = prev_init_node; for( node_ptr p_next ; this_node != (p_next = NodeTraits::get_next(p)) ; p = p_next){ @@ -44,9 +48,6 @@ class common_slist_algorithms return p; } - static void init_header(const node_ptr & this_node) - { NodeTraits::set_next(this_node, this_node); } - static void init(const node_ptr & this_node) { NodeTraits::set_next(this_node, node_ptr()); } @@ -92,12 +93,102 @@ class common_slist_algorithms NodeTraits::set_next(bp, next_b); } } + + struct stable_partition_info + { + std::size_t num_1st_partition; + std::size_t num_2nd_partition; + node_ptr beg_2st_partition; + node_ptr new_last_node; + }; + + template<class Pred> + static void stable_partition(node_ptr before_beg, const node_ptr &end, Pred pred, stable_partition_info &info) + { + node_ptr bcur = before_beg; + node_ptr cur = node_traits::get_next(bcur); + node_ptr new_f = end; + + std::size_t num1 = 0, num2 = 0; + while(cur != end){ + if(pred(cur)){ + ++num1; + bcur = cur; + cur = node_traits::get_next(cur); + } + else{ + ++num2; + node_ptr last_to_remove = bcur; + new_f = cur; + bcur = cur; + cur = node_traits::get_next(cur); + BOOST_TRY{ + //Main loop + while(cur != end){ + if(pred(cur)){ //Might throw + ++num1; + //Process current node + node_traits::set_next(last_to_remove, cur); + last_to_remove = cur; + node_ptr nxt = node_traits::get_next(cur); + node_traits::set_next(bcur, nxt); + cur = nxt; + } + else{ + ++num2; + bcur = cur; + cur = node_traits::get_next(cur); + } + } + } + BOOST_CATCH(...){ + node_traits::set_next(last_to_remove, new_f); + throw; + } + BOOST_CATCH_END + node_traits::set_next(last_to_remove, new_f); + break; + } + } + info.num_1st_partition = num1; + info.num_2nd_partition = num2; + info.beg_2st_partition = new_f; + info.new_last_node = bcur; + } + + //! <b>Requires</b>: f and l must be in a circular list. + //! + //! <b>Effects</b>: Returns the number of nodes in the range [f, l). + //! + //! <b>Complexity</b>: Linear + //! + //! <b>Throws</b>: Nothing. + static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l) + { + const_node_ptr i(f); + std::size_t result = 0; + while(i != l){ + i = NodeTraits::get_next(i); + ++result; + } + return result; + } }; +/// @endcond + } //namespace detail + +/// @cond + +template<class NodeTraits> +struct get_algo<CommonSListAlgorithms, NodeTraits> +{ + typedef detail::common_slist_algorithms<NodeTraits> type; +}; + + } //namespace intrusive } //namespace boost -#include <boost/intrusive/detail/config_end.hpp> - #endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP |