boost/intrusive/linear_slist_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Olaf Krzikalla 2004-2006.
   4 // (C) Copyright Ion Gaztanaga  2006-2008
   5 //
   6 // Distributed under the Boost Software License, Version 1.0.
   7 //    (See accompanying file LICENSE_1_0.txt or copy at
   8 //          http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10 // See http://www.boost.org/libs/intrusive for documentation.
  11 //
  12 /////////////////////////////////////////////////////////////////////////////
  13
  14 #ifndef BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
  15 #define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
  16
  17 #include <boost/intrusive/detail/config_begin.hpp>
  18 #include <boost/intrusive/intrusive_fwd.hpp>
  19 #include <boost/intrusive/detail/common_slist_algorithms.hpp>
  20 #include <cstddef>
  21 #include <utility>
  22
  23 namespace boost {
  24 namespace intrusive {
  25
  26 //! linear_slist_algorithms provides basic algorithms to manipulate nodes
  27 //! forming a linear singly linked list.
  28 //!
  29 //! linear_slist_algorithms is configured with a NodeTraits class, which encapsulates the
  30 //! information about the node to be manipulated. NodeTraits must support the
  31 //! following interface:
  32 //!
  33 //! <b>Typedefs</b>:
  34 //!
  35 //! <tt>node</tt>: The type of the node that forms the linear list
  36 //!
  37 //! <tt>node_ptr</tt>: A pointer to a node
  38 //!
  39 //! <tt>const_node_ptr</tt>: A pointer to a const node
  40 //!
  41 //! <b>Static functions</b>:
  42 //!
  43 //! <tt>static node_ptr get_next(const_node_ptr n);</tt>
  44 //!
  45 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
  46 template<class NodeTraits>
  47 class linear_slist_algorithms
  48    /// @cond
  49    : public detail::common_slist_algorithms<NodeTraits>
  50    /// @endcond
  51 {
  52    /// @cond
  53    typedef detail::common_slist_algorithms<NodeTraits> base_t;
  54    /// @endcond
  55    public:
  56    typedef typename NodeTraits::node            node;
  57    typedef typename NodeTraits::node_ptr        node_ptr;
  58    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
  59    typedef NodeTraits                           node_traits;
  60
  61    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  62
  63    //! <b>Effects</b>: Constructs an non-used list element, putting the next
  64    //!   pointer to null:
  65    //!  <tt>NodeTraits::get_next(this_node) == 0
  66    //!
  67    //! <b>Complexity</b>: Constant
  68    //!
  69    //! <b>Throws</b>: Nothing.
  70    static void init(node_ptr this_node);
  71
  72    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
  73    //!
  74    //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
  75    //!  or it's a not inserted node:
  76    //!  <tt>return !NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
  77    //!
  78    //! <b>Complexity</b>: Constant
  79    //!
  80    //! <b>Throws</b>: Nothing.
  81    static bool unique(const_node_ptr this_node);
  82
  83    //! <b>Effects</b>: Returns true is "this_node" has the same state as if
  84    //!  it was inited using "init(node_ptr)"
  85    //!
  86    //! <b>Complexity</b>: Constant
  87    //!
  88    //! <b>Throws</b>: Nothing.
  89    static bool inited(const_node_ptr this_node);
  90
  91    //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.
  92    //!
  93    //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.
  94    //!
  95    //! <b>Complexity</b>: Constant
  96    //!
  97    //! <b>Throws</b>: Nothing.
  98    static void unlink_after(node_ptr prev_node);
  99
 100    //! <b>Requires</b>: prev_node and last_node must be in a circular list
 101    //!  or be an empty circular list.
 102    //!
 103    //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list.
 104    //!
 105    //! <b>Complexity</b>: Constant
 106    //!
 107    //! <b>Throws</b>: Nothing.
 108    static void unlink_after(node_ptr prev_node, node_ptr last_node);
 109
 110    //! <b>Requires</b>: prev_node must be a node of a linear list.
 111    //!
 112    //! <b>Effects</b>: Links this_node after prev_node in the linear list.
 113    //!
 114    //! <b>Complexity</b>: Constant
 115    //!
 116    //! <b>Throws</b>: Nothing.
 117    static void link_after(node_ptr prev_node, node_ptr this_node);
 118
 119    //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range.
 120    //!   and p must be a node of a different linear list.
 121    //!
 122    //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts
 123    //!   them after p in p's linear list.
 124    //!
 125    //! <b>Complexity</b>: Constant
 126    //!
 127    //! <b>Throws</b>: Nothing.
 128    static void transfer_after(node_ptr p, node_ptr b, node_ptr e);
 129
 130    #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 131
 132    //! <b>Effects</b>: Constructs an empty list, making this_node the only
 133    //!   node of the circular list:
 134    //!  <tt>NodeTraits::get_next(this_node) == this_node</tt>.
 135    //!
 136    //! <b>Complexity</b>: Constant
 137    //!
 138    //! <b>Throws</b>: Nothing.
 139    static void init_header(node_ptr this_node)
 140    {  NodeTraits::set_next(this_node, node_ptr(0));  }
 141
 142    //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list.
 143    //!
 144    //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting.
 145    //!   the search from prev_init_node. The first node checked for equality
 146    //!   is NodeTraits::get_next(prev_init_node).
 147    //!
 148    //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
 149    //!
 150    //! <b>Throws</b>: Nothing.
 151    static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node)
 152    {  return base_t::get_previous_node(prev_init_node, this_node);   }
 153
 154    //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list.
 155    //!
 156    //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list
 157    //!  is empty, returns 1.
 158    //!
 159    //! <b>Complexity</b>: Constant
 160    //!
 161    //! <b>Throws</b>: Nothing.
 162    static std::size_t count(const_node_ptr this_node)
 163    {
 164       std::size_t result = 0;
 165       const_node_ptr p = this_node;
 166       do{
 167          p = NodeTraits::get_next(p);
 168          ++result;
 169       } while (p);
 170       return result;
 171    }
 172
 173    //! <b>Requires</b>: this_node and other_node must be nodes inserted
 174    //!  in linear lists or be empty linear lists.
 175    //!
 176    //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node
 177    //!   and vice-versa.
 178    //!
 179    //! <b>Complexity</b>: Constant
 180    //!
 181    //! <b>Throws</b>: Nothing.
 182    static void swap_trailing_nodes(node_ptr this_node, node_ptr other_node)
 183    {
 184       node_ptr this_nxt    = NodeTraits::get_next(this_node);
 185       node_ptr other_nxt   = NodeTraits::get_next(other_node);
 186       NodeTraits::set_next(this_node, other_nxt);
 187       NodeTraits::set_next(other_node, this_nxt);
 188    }
 189
 190    //! <b>Effects</b>: Reverses the order of elements in the list.
 191    //!
 192    //! <b>Returns</b>: The new first node of the list.
 193    //!
 194    //! <b>Throws</b>: Nothing.
 195    //!
 196    //! <b>Complexity</b>: This function is linear to the contained elements.
 197    static node_ptr reverse(node_ptr p)
 198    {
 199       if(!p) return node_ptr(0);
 200       node_ptr i = NodeTraits::get_next(p);
 201       node_ptr first(p);
 202       while(i){
 203          node_ptr nxti(NodeTraits::get_next(i));
 204          base_t::unlink_after(p);
 205          NodeTraits::set_next(i, first);
 206          first = i;
 207          i = nxti;
 208       }
 209       return first;
 210    }
 211
 212    //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list.
 213    //!
 214    //! <b>Returns</b>: A pair containing the new first and last node of the list or
 215    //!   if there has been any movement, a null pair if n leads to no movement.
 216    //!
 217    //! <b>Throws</b>: Nothing.
 218    //!
 219    //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
 220    static std::pair<node_ptr, node_ptr> move_first_n_backwards(node_ptr p, std::size_t n)
 221    {
 222       std::pair<node_ptr, node_ptr> ret(node_ptr(0), node_ptr(0));
 223       //Null shift, or count() == 0 or 1, nothing to do
 224       if(!n || !p || !NodeTraits::get_next(p)){
 225          return ret;
 226       }
 227
 228       node_ptr first = p;
 229       bool end_found = false;
 230       node_ptr new_last(0);
 231       node_ptr old_last(0);
 232
 233       //Now find the new last node according to the shift count.
 234       //If we find 0 before finding the new last node
 235       //unlink p, shortcut the search now that we know the size of the list
 236       //and continue.
 237       for(std::size_t i = 1; i <= n; ++i){
 238          new_last = first;
 239          first = NodeTraits::get_next(first);
 240          if(first == 0){
 241             //Shortcut the shift with the modulo of the size of the list
 242             n %= i;
 243             if(!n)   return ret;
 244             old_last = new_last;
 245             i = 0;
 246             //Unlink p and continue the new first node search
 247             first = p;
 248             //unlink_after(new_last);
 249             end_found = true;
 250          }
 251       }
 252
 253       //If the p has not been found in the previous loop, find it
 254       //starting in the new first node and unlink it
 255       if(!end_found){
 256          old_last = base_t::get_previous_node(first, node_ptr(0));
 257       }
 258
 259       //Now link p after the new last node
 260       NodeTraits::set_next(old_last, p);
 261       NodeTraits::set_next(new_last, node_ptr(0));
 262       ret.first   = first;
 263       ret.second  = new_last;
 264       return ret;
 265    }
 266
 267    //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list.
 268    //!
 269    //! <b>Returns</b>: A pair containing the new first and last node of the list or
 270    //!   if there has been any movement, a null pair if n leads to no movement.
 271    //!
 272    //! <b>Throws</b>: Nothing.
 273    //!
 274    //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
 275    static std::pair<node_ptr, node_ptr> move_first_n_forward(node_ptr p, std::size_t n)
 276    {
 277       std::pair<node_ptr, node_ptr> ret(node_ptr(0), node_ptr(0));
 278       //Null shift, or count() == 0 or 1, nothing to do
 279       if(!n || !p || !NodeTraits::get_next(p))
 280          return ret;
 281
 282       node_ptr first  = p;
 283
 284       //Iterate until p is found to know where the current last node is.
 285       //If the shift count is less than the size of the list, we can also obtain
 286       //the position of the new last node after the shift.
 287       node_ptr old_last(first), next_to_it, new_last(p);
 288       std::size_t distance = 1;
 289       while(!!(next_to_it = node_traits::get_next(old_last))){
 290          if(distance++ > n)
 291             new_last = node_traits::get_next(new_last);
 292          old_last = next_to_it;
 293       }
 294       //If the shift was bigger or equal than the size, obtain the equivalent
 295       //forward shifts and find the new last node.
 296       if(distance <= n){
 297          //Now find the equivalent forward shifts.
 298          //Shortcut the shift with the modulo of the size of the list
 299          std::size_t new_before_last_pos = (distance - (n % distance))% distance;
 300          //If the shift is a multiple of the size there is nothing to do
 301          if(!new_before_last_pos)
 302             return ret;
 303
 304          for( new_last = p
 305             ; --new_before_last_pos
 306             ; new_last = node_traits::get_next(new_last)){
 307             //empty
 308          }
 309       }
 310
 311       //Get the first new node
 312       node_ptr new_first(node_traits::get_next(new_last));
 313       //Now put the old beginning after the old end
 314       NodeTraits::set_next(old_last, p);
 315       NodeTraits::set_next(new_last, node_ptr(0));
 316       ret.first   = new_first;
 317       ret.second  = new_last;
 318       return ret;
 319    }
 320 };
 321
 322 } //namespace intrusive
 323 } //namespace boost
 324
 325 #include <boost/intrusive/detail/config_end.hpp>
 326
 327 #endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP