1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2014 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 13 #ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP 14 #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP 15 16 #ifndef BOOST_CONFIG_HPP 17 # include <boost/config.hpp> 18 #endif 19 20 #if defined(BOOST_HAS_PRAGMA_ONCE) 21 # pragma once 22 #endif 23 24 #include <boost/intrusive/intrusive_fwd.hpp> 25 #include <boost/intrusive/detail/assert.hpp> 26 #include <boost/intrusive/detail/algo_type.hpp> 27 #include <boost/core/no_exceptions_support.hpp> 28 #include <cstddef> 29 30 namespace boost { 31 namespace intrusive { 32 namespace detail { 33 34 template<class NodeTraits> 35 class common_slist_algorithms 36 { 37 public: 38 typedef typename NodeTraits::node node; 39 typedef typename NodeTraits::node_ptr node_ptr; 40 typedef typename NodeTraits::const_node_ptr const_node_ptr; 41 typedef NodeTraits node_traits; 42 get_previous_node(node_ptr p,const node_ptr & this_node)43 static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node) 44 { 45 for( node_ptr p_next 46 ; this_node != (p_next = NodeTraits::get_next(p)) 47 ; p = p_next){ 48 //Logic error: possible use of linear lists with 49 //operations only permitted with circular lists 50 BOOST_INTRUSIVE_INVARIANT_ASSERT(p); 51 } 52 return p; 53 } 54 init(node_ptr this_node)55 BOOST_INTRUSIVE_FORCEINLINE static void init(node_ptr this_node) 56 { NodeTraits::set_next(this_node, node_ptr()); } 57 unique(const const_node_ptr & this_node)58 BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & this_node) 59 { 60 node_ptr next = NodeTraits::get_next(this_node); 61 return !next || next == this_node; 62 } 63 inited(const const_node_ptr & this_node)64 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & this_node) 65 { return !NodeTraits::get_next(this_node); } 66 unlink_after(node_ptr prev_node)67 BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(node_ptr prev_node) 68 { 69 const_node_ptr this_node(NodeTraits::get_next(prev_node)); 70 NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node)); 71 } 72 unlink_after(node_ptr prev_node,node_ptr last_node)73 BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(node_ptr prev_node, node_ptr last_node) 74 { NodeTraits::set_next(prev_node, last_node); } 75 link_after(node_ptr prev_node,node_ptr this_node)76 BOOST_INTRUSIVE_FORCEINLINE static void link_after(node_ptr prev_node, node_ptr this_node) 77 { 78 NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node)); 79 NodeTraits::set_next(prev_node, this_node); 80 } 81 incorporate_after(node_ptr bp,node_ptr b,node_ptr be)82 BOOST_INTRUSIVE_FORCEINLINE static void incorporate_after(node_ptr bp, node_ptr b, node_ptr be) 83 { 84 node_ptr p(NodeTraits::get_next(bp)); 85 NodeTraits::set_next(bp, b); 86 NodeTraits::set_next(be, p); 87 } 88 transfer_after(node_ptr bp,node_ptr bb,node_ptr be)89 static void transfer_after(node_ptr bp, node_ptr bb, node_ptr be) 90 { 91 if (bp != bb && bp != be && bb != be) { 92 node_ptr next_b = NodeTraits::get_next(bb); 93 node_ptr next_e = NodeTraits::get_next(be); 94 node_ptr next_p = NodeTraits::get_next(bp); 95 NodeTraits::set_next(bb, next_e); 96 NodeTraits::set_next(be, next_p); 97 NodeTraits::set_next(bp, next_b); 98 } 99 } 100 101 struct stable_partition_info 102 { 103 std::size_t num_1st_partition; 104 std::size_t num_2nd_partition; 105 node_ptr beg_2st_partition; 106 node_ptr new_last_node; 107 }; 108 109 template<class Pred> stable_partition(node_ptr before_beg,node_ptr end,Pred pred,stable_partition_info & info)110 static void stable_partition(node_ptr before_beg, node_ptr end, Pred pred, stable_partition_info &info) 111 { 112 node_ptr bcur = before_beg; 113 node_ptr cur = node_traits::get_next(bcur); 114 node_ptr new_f = end; 115 116 std::size_t num1 = 0, num2 = 0; 117 while(cur != end){ 118 if(pred(cur)){ 119 ++num1; 120 bcur = cur; 121 cur = node_traits::get_next(cur); 122 } 123 else{ 124 ++num2; 125 node_ptr last_to_remove = bcur; 126 new_f = cur; 127 bcur = cur; 128 cur = node_traits::get_next(cur); 129 BOOST_TRY{ 130 //Main loop 131 while(cur != end){ 132 if(pred(cur)){ //Might throw 133 ++num1; 134 //Process current node 135 node_traits::set_next(last_to_remove, cur); 136 last_to_remove = cur; 137 node_ptr nxt = node_traits::get_next(cur); 138 node_traits::set_next(bcur, nxt); 139 cur = nxt; 140 } 141 else{ 142 ++num2; 143 bcur = cur; 144 cur = node_traits::get_next(cur); 145 } 146 } 147 } 148 BOOST_CATCH(...){ 149 node_traits::set_next(last_to_remove, new_f); 150 BOOST_RETHROW; 151 } 152 BOOST_CATCH_END 153 node_traits::set_next(last_to_remove, new_f); 154 break; 155 } 156 } 157 info.num_1st_partition = num1; 158 info.num_2nd_partition = num2; 159 info.beg_2st_partition = new_f; 160 info.new_last_node = bcur; 161 } 162 163 //! <b>Requires</b>: f and l must be in a circular list. 164 //! 165 //! <b>Effects</b>: Returns the number of nodes in the range [f, l). 166 //! 167 //! <b>Complexity</b>: Linear 168 //! 169 //! <b>Throws</b>: Nothing. distance(const const_node_ptr & f,const const_node_ptr & l)170 static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l) 171 { 172 const_node_ptr i(f); 173 std::size_t result = 0; 174 while(i != l){ 175 i = NodeTraits::get_next(i); 176 ++result; 177 } 178 return result; 179 } 180 }; 181 182 /// @endcond 183 184 } //namespace detail 185 186 /// @cond 187 188 template<class NodeTraits> 189 struct get_algo<CommonSListAlgorithms, NodeTraits> 190 { 191 typedef detail::common_slist_algorithms<NodeTraits> type; 192 }; 193 194 195 } //namespace intrusive 196 } //namespace boost 197 198 #endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP 199