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
30namespace boost {
31namespace intrusive {
32namespace detail {
33
34template<class NodeTraits>
35class 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
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
55 BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & this_node)
56 { NodeTraits::set_next(this_node, node_ptr()); }
57
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
64 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & this_node)
65 { return !NodeTraits::get_next(this_node); }
66
67 BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const 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
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); }
75
76 BOOST_INTRUSIVE_FORCEINLINE static void link_after(const node_ptr & prev_node, const 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
82 BOOST_INTRUSIVE_FORCEINLINE static void incorporate_after(const node_ptr & bp, const node_ptr & b, const 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
89 static void transfer_after(const node_ptr & bp, const node_ptr & bb, const 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>
110 static void stable_partition(node_ptr before_beg, const 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.
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
188template<class NodeTraits>
189struct 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