1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2014
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
14 #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
16 #ifndef BOOST_CONFIG_HPP
17 # include <boost/config.hpp>
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
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>
34 template<class NodeTraits>
35 class common_slist_algorithms
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;
43 static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node)
46 ; this_node != (p_next = NodeTraits::get_next(p))
48 //Logic error: possible use of linear lists with
49 //operations only permitted with circular lists
50 BOOST_INTRUSIVE_INVARIANT_ASSERT(p);
55 BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & this_node)
56 { NodeTraits::set_next(this_node, node_ptr()); }
58 BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & this_node)
60 node_ptr next = NodeTraits::get_next(this_node);
61 return !next || next == this_node;
64 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & this_node)
65 { return !NodeTraits::get_next(this_node); }
67 BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const node_ptr & prev_node)
69 const_node_ptr this_node(NodeTraits::get_next(prev_node));
70 NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
73 BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
74 { NodeTraits::set_next(prev_node, last_node); }
76 BOOST_INTRUSIVE_FORCEINLINE static void link_after(const node_ptr & prev_node, const node_ptr & this_node)
78 NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
79 NodeTraits::set_next(prev_node, this_node);
82 BOOST_INTRUSIVE_FORCEINLINE static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be)
84 node_ptr p(NodeTraits::get_next(bp));
85 NodeTraits::set_next(bp, b);
86 NodeTraits::set_next(be, p);
89 static void transfer_after(const node_ptr & bp, const node_ptr & bb, const node_ptr & be)
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);
101 struct stable_partition_info
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;
110 static void stable_partition(node_ptr before_beg, const node_ptr &end, Pred pred, stable_partition_info &info)
112 node_ptr bcur = before_beg;
113 node_ptr cur = node_traits::get_next(bcur);
114 node_ptr new_f = end;
116 std::size_t num1 = 0, num2 = 0;
121 cur = node_traits::get_next(cur);
125 node_ptr last_to_remove = bcur;
128 cur = node_traits::get_next(cur);
132 if(pred(cur)){ //Might throw
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);
144 cur = node_traits::get_next(cur);
149 node_traits::set_next(last_to_remove, new_f);
153 node_traits::set_next(last_to_remove, new_f);
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;
163 //! <b>Requires</b>: f and l must be in a circular list.
165 //! <b>Effects</b>: Returns the number of nodes in the range [f, l).
167 //! <b>Complexity</b>: Linear
169 //! <b>Throws</b>: Nothing.
170 static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l)
173 std::size_t result = 0;
175 i = NodeTraits::get_next(i);
188 template<class NodeTraits>
189 struct get_algo<CommonSListAlgorithms, NodeTraits>
191 typedef detail::common_slist_algorithms<NodeTraits> type;
195 } //namespace intrusive
198 #endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP