1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
/////////////////////////////////////////////////////////////////////////////
//
// (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
// http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
#ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
#define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
#ifndef BOOST_CONFIG_HPP
# include <boost/config.hpp>
#endif
#if defined(BOOST_HAS_PRAGMA_ONCE)
# 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 {
namespace intrusive {
namespace detail {
template<class NodeTraits>
class common_slist_algorithms
{
public:
typedef typename NodeTraits::node node;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
typedef NodeTraits node_traits;
static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node)
{
for( node_ptr p_next
; this_node != (p_next = NodeTraits::get_next(p))
; p = p_next){
//Logic error: possible use of linear lists with
//operations only permitted with circular lists
BOOST_INTRUSIVE_INVARIANT_ASSERT(p);
}
return p;
}
static void init(const node_ptr & this_node)
{ NodeTraits::set_next(this_node, node_ptr()); }
static bool unique(const const_node_ptr & this_node)
{
node_ptr next = NodeTraits::get_next(this_node);
return !next || next == this_node;
}
static bool inited(const const_node_ptr & this_node)
{ return !NodeTraits::get_next(this_node); }
static void unlink_after(const node_ptr & prev_node)
{
const_node_ptr this_node(NodeTraits::get_next(prev_node));
NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
}
static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
{ NodeTraits::set_next(prev_node, last_node); }
static void link_after(const node_ptr & prev_node, const node_ptr & this_node)
{
NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
NodeTraits::set_next(prev_node, this_node);
}
static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be)
{
node_ptr p(NodeTraits::get_next(bp));
NodeTraits::set_next(bp, b);
NodeTraits::set_next(be, p);
}
static void transfer_after(const node_ptr & bp, const node_ptr & bb, const node_ptr & be)
{
if (bp != bb && bp != be && bb != be) {
node_ptr next_b = NodeTraits::get_next(bb);
node_ptr next_e = NodeTraits::get_next(be);
node_ptr next_p = NodeTraits::get_next(bp);
NodeTraits::set_next(bb, next_e);
NodeTraits::set_next(be, next_p);
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);
BOOST_RETHROW;
}
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
#endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
|
