summaryrefslogtreecommitdiff
path: root/boost/intrusive/linear_slist_algorithms.hpp
blob: db4092d2c92b9340a7d61b4df480e38420ce344e (plain)
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
// (C) Copyright Ion Gaztanaga  2006-2012
//
// 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_LINEAR_SLIST_ALGORITHMS_HPP
#define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP

#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/intrusive_fwd.hpp>
#include <boost/intrusive/detail/common_slist_algorithms.hpp>
#include <cstddef>
#include <utility>

namespace boost {
namespace intrusive {

//! linear_slist_algorithms provides basic algorithms to manipulate nodes
//! forming a linear singly linked list.
//!
//! linear_slist_algorithms is configured with a NodeTraits class, which encapsulates the
//! information about the node to be manipulated. NodeTraits must support the
//! following interface:
//!
//! <b>Typedefs</b>:
//!
//! <tt>node</tt>: The type of the node that forms the linear list
//!
//! <tt>node_ptr</tt>: A pointer to a node
//!
//! <tt>const_node_ptr</tt>: A pointer to a const node
//!
//! <b>Static functions</b>:
//!
//! <tt>static node_ptr get_next(const_node_ptr n);</tt>
//!
//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
template<class NodeTraits>
class linear_slist_algorithms
   /// @cond
   : public detail::common_slist_algorithms<NodeTraits>
   /// @endcond
{
   /// @cond
   typedef detail::common_slist_algorithms<NodeTraits> base_t;
   /// @endcond
   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;

   #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)

   //! <b>Effects</b>: Constructs an non-used list element, putting the next
   //!   pointer to null:
   //!  <tt>NodeTraits::get_next(this_node) == node_ptr()</tt>
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void init(const node_ptr & this_node);

   //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
   //!
   //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
   //!  or it's a not inserted node:
   //!  <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static bool unique(const_node_ptr this_node);

   //! <b>Effects</b>: Returns true is "this_node" has the same state as if
   //!  it was inited using "init(node_ptr)"
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static bool inited(const_node_ptr this_node);

   //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.
   //!
   //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void unlink_after(const node_ptr & prev_node);

   //! <b>Requires</b>: prev_node and last_node must be in a circular list
   //!  or be an empty circular list.
   //!
   //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list.
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node);

   //! <b>Requires</b>: prev_node must be a node of a linear list.
   //!
   //! <b>Effects</b>: Links this_node after prev_node in the linear list.
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void link_after(const node_ptr & prev_node, const node_ptr & this_node);

   //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range.
   //!   and p must be a node of a different linear list.
   //!
   //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts
   //!   them after p in p's linear list.
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void transfer_after(const node_ptr & p, const node_ptr & b, const node_ptr & e);

   #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)

   //! <b>Effects</b>: Constructs an empty list, making this_node the only
   //!   node of the circular list:
   //!  <tt>NodeTraits::get_next(this_node) == this_node</tt>.
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void init_header(const node_ptr & this_node)
   {  NodeTraits::set_next(this_node, node_ptr ());  }

   //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list.
   //!
   //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting.
   //!   the search from prev_init_node. The first node checked for equality
   //!   is NodeTraits::get_next(prev_init_node).
   //!
   //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
   //!
   //! <b>Throws</b>: Nothing.
   static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node)
   {  return base_t::get_previous_node(prev_init_node, this_node);   }

   //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list.
   //!
   //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list
   //!  is empty, returns 1.
   //!
   //! <b>Complexity</b>: Linear
   //!
   //! <b>Throws</b>: Nothing.
   static std::size_t count(const const_node_ptr & this_node)
   {
      std::size_t result = 0;
      const_node_ptr p = this_node;
      do{
         p = NodeTraits::get_next(p);
         ++result;
      } while (p);
      return result;
   }

   //! <b>Requires</b>: this_node and other_node must be nodes inserted
   //!  in linear lists or be empty linear lists.
   //!
   //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node
   //!   and vice-versa.
   //!
   //! <b>Complexity</b>: Constant
   //!
   //! <b>Throws</b>: Nothing.
   static void swap_trailing_nodes(const node_ptr & this_node, const node_ptr & other_node)
   {
      node_ptr this_nxt    = NodeTraits::get_next(this_node);
      node_ptr other_nxt   = NodeTraits::get_next(other_node);
      NodeTraits::set_next(this_node, other_nxt);
      NodeTraits::set_next(other_node, this_nxt);
   }

   //! <b>Effects</b>: Reverses the order of elements in the list.
   //!
   //! <b>Returns</b>: The new first node of the list.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: This function is linear to the contained elements.
   static node_ptr reverse(const node_ptr & p)
   {
      if(!p) return node_ptr();
      node_ptr i = NodeTraits::get_next(p);
      node_ptr first(p);
      while(i){
         node_ptr nxti(NodeTraits::get_next(i));
         base_t::unlink_after(p);
         NodeTraits::set_next(i, first);
         first = i;
         i = nxti;
      }
      return first;
   }

   //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list.
   //!
   //! <b>Returns</b>: A pair containing the new first and last node of the list or
   //!   if there has been any movement, a null pair if n leads to no movement.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
   static std::pair<node_ptr, node_ptr> move_first_n_backwards(const node_ptr & p, std::size_t n)
   {
      std::pair<node_ptr, node_ptr> ret;
      //Null shift, or count() == 0 or 1, nothing to do
      if(!n || !p || !NodeTraits::get_next(p)){
         return ret;
      }

      node_ptr first = p;
      bool end_found = false;
      node_ptr new_last = node_ptr();
      node_ptr old_last = node_ptr();

      //Now find the new last node according to the shift count.
      //If we find 0 before finding the new last node
      //unlink p, shortcut the search now that we know the size of the list
      //and continue.
      for(std::size_t i = 1; i <= n; ++i){
         new_last = first;
         first = NodeTraits::get_next(first);
         if(first == node_ptr()){
            //Shortcut the shift with the modulo of the size of the list
            n %= i;
            if(!n)   return ret;
            old_last = new_last;
            i = 0;
            //Unlink p and continue the new first node search
            first = p;
            //unlink_after(new_last);
            end_found = true;
         }
      }

      //If the p has not been found in the previous loop, find it
      //starting in the new first node and unlink it
      if(!end_found){
         old_last = base_t::get_previous_node(first, node_ptr());
      }

      //Now link p after the new last node
      NodeTraits::set_next(old_last, p);
      NodeTraits::set_next(new_last, node_ptr());
      ret.first   = first;
      ret.second  = new_last;
      return ret;
   }

   //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list.
   //!
   //! <b>Returns</b>: A pair containing the new first and last node of the list or
   //!   if there has been any movement, a null pair if n leads to no movement.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
   static std::pair<node_ptr, node_ptr> move_first_n_forward(const node_ptr & p, std::size_t n)
   {
      std::pair<node_ptr, node_ptr> ret;
      //Null shift, or count() == 0 or 1, nothing to do
      if(!n || !p || !NodeTraits::get_next(p))
         return ret;

      node_ptr first  = p;

      //Iterate until p is found to know where the current last node is.
      //If the shift count is less than the size of the list, we can also obtain
      //the position of the new last node after the shift.
      node_ptr old_last(first), next_to_it, new_last(p);
      std::size_t distance = 1;
      while(!!(next_to_it = node_traits::get_next(old_last))){
         if(distance++ > n)
            new_last = node_traits::get_next(new_last);
         old_last = next_to_it;
      }
      //If the shift was bigger or equal than the size, obtain the equivalent
      //forward shifts and find the new last node.
      if(distance <= n){
         //Now find the equivalent forward shifts.
         //Shortcut the shift with the modulo of the size of the list
         std::size_t new_before_last_pos = (distance - (n % distance))% distance;
         //If the shift is a multiple of the size there is nothing to do
         if(!new_before_last_pos)
            return ret;

         for( new_last = p
            ; --new_before_last_pos
            ; new_last = node_traits::get_next(new_last)){
            //empty
         }
      }

      //Get the first new node
      node_ptr new_first(node_traits::get_next(new_last));
      //Now put the old beginning after the old end
      NodeTraits::set_next(old_last, p);
      NodeTraits::set_next(new_last, node_ptr());
      ret.first   = new_first;
      ret.second  = new_last;
      return ret;
   }
};

} //namespace intrusive
} //namespace boost

#include <boost/intrusive/detail/config_end.hpp>

#endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP