boost/multi_index/detail/seq_index_node.hpp

   1 /* Copyright 2003-2007 Joaquín M López Muñoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
  11
  12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/detail/allocator_utilities.hpp>
  19 #include <boost/multi_index/detail/prevent_eti.hpp>
  20
  21 namespace boost{
  22
  23 namespace multi_index{
  24
  25 namespace detail{
  26
  27 /* doubly-linked node for use by sequenced_index */
  28
  29 template<typename Allocator>
  30 struct sequenced_index_node_impl
  31 {
  32   typedef typename prevent_eti<
  33     Allocator,
  34     typename boost::detail::allocator::rebind_to<
  35       Allocator,sequenced_index_node_impl
  36     >::type
  37   >::type::pointer                                pointer;
  38   typedef typename prevent_eti<
  39     Allocator,
  40     typename boost::detail::allocator::rebind_to<
  41       Allocator,sequenced_index_node_impl
  42     >::type
  43   >::type::const_pointer                          const_pointer;
  44
  45   pointer& prior(){return prior_;}
  46   pointer  prior()const{return prior_;}
  47   pointer& next(){return next_;}
  48   pointer  next()const{return next_;}
  49
  50   /* interoperability with bidir_node_iterator */
  51
  52   static void increment(pointer& x){x=x->next();}
  53   static void decrement(pointer& x){x=x->prior();}
  54
  55   /* algorithmic stuff */
  56
  57   static void link(pointer x,pointer header)
  58   {
  59     x->prior()=header->prior();
  60     x->next()=header;
  61     x->prior()->next()=x->next()->prior()=x;
  62   };
  63
  64   static void unlink(pointer x)
  65   {
  66     x->prior()->next()=x->next();
  67     x->next()->prior()=x->prior();
  68   }
  69
  70   static void relink(pointer position,pointer x)
  71   {
  72     unlink(x);
  73     x->prior()=position->prior();
  74     x->next()=position;
  75     x->prior()->next()=x->next()->prior()=x;
  76   }
  77
  78   static void relink(pointer position,pointer x,pointer y)
  79   {
  80     /* position is assumed not to be in [x,y) */
  81
  82     if(x!=y){
  83       pointer z=y->prior();
  84       x->prior()->next()=y;
  85       y->prior()=x->prior();
  86       x->prior()=position->prior();
  87       z->next()=position;
  88       x->prior()->next()=x;
  89       z->next()->prior()=z;
  90     }
  91   }
  92
  93   static void reverse(pointer header)
  94   {
  95     pointer x=header;
  96     do{
  97       pointer y=x->next();
  98       std::swap(x->prior(),x->next());
  99       x=y;
 100     }while(x!=header);
 101   }
 102
 103   static void swap(pointer x,pointer y)
 104   {
 105     /* This swap function does not exchange the header nodes,
 106      * but rather their pointers. This is *not* used for implementing
 107      * sequenced_index::swap.
 108      */
 109
 110     if(x->next()!=x){
 111       if(y->next()!=y){
 112         std::swap(x->next(),y->next());
 113         std::swap(x->prior(),y->prior());
 114         x->next()->prior()=x->prior()->next()=x;
 115         y->next()->prior()=y->prior()->next()=y;
 116       }
 117       else{
 118         y->next()=x->next();
 119         y->prior()=x->prior();
 120         x->next()=x->prior()=x;
 121         y->next()->prior()=y->prior()->next()=y;
 122       }
 123     }
 124     else if(y->next()!=y){
 125       x->next()=y->next();
 126       x->prior()=y->prior();
 127       y->next()=y->prior()=y;
 128       x->next()->prior()=x->prior()->next()=x;
 129     }
 130   }
 131
 132 private:
 133   pointer prior_;
 134   pointer next_;
 135 };
 136
 137 template<typename Super>
 138 struct sequenced_index_node_trampoline:
 139   prevent_eti<
 140     Super,
 141     sequenced_index_node_impl<
 142       typename boost::detail::allocator::rebind_to<
 143         typename Super::allocator_type,
 144         void
 145       >::type
 146     >
 147   >::type
 148 {
 149   typedef typename prevent_eti<
 150     Super,
 151     sequenced_index_node_impl<
 152       typename boost::detail::allocator::rebind_to<
 153         typename Super::allocator_type,
 154         void
 155       >::type
 156     >
 157   >::type impl_type;
 158 };
 159
 160 template<typename Super>
 161 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
 162 {
 163 private:
 164   typedef sequenced_index_node_trampoline<Super> trampoline;
 165
 166 public:
 167   typedef typename trampoline::impl_type         impl_type;
 168   typedef typename trampoline::pointer           impl_pointer;
 169   typedef typename trampoline::const_pointer     const_impl_pointer;
 170
 171   impl_pointer& prior(){return trampoline::prior();}
 172   impl_pointer  prior()const{return trampoline::prior();}
 173   impl_pointer& next(){return trampoline::next();}
 174   impl_pointer  next()const{return trampoline::next();}
 175
 176   impl_pointer impl()
 177   {
 178     return static_cast<impl_pointer>(
 179       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 180   }
 181
 182   const_impl_pointer impl()const
 183   {
 184     return static_cast<const_impl_pointer>(
 185       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 186   }
 187
 188   static sequenced_index_node* from_impl(impl_pointer x)
 189   {
 190     return static_cast<sequenced_index_node*>(
 191       static_cast<trampoline*>(&*x));
 192   }
 193
 194   static const sequenced_index_node* from_impl(const_impl_pointer x)
 195   {
 196     return static_cast<const sequenced_index_node*>(
 197       static_cast<const trampoline*>(&*x));
 198   }
 199
 200   /* interoperability with bidir_node_iterator */
 201
 202   static void increment(sequenced_index_node*& x)
 203   {
 204     impl_pointer xi=x->impl();
 205     trampoline::increment(xi);
 206     x=from_impl(xi);
 207   }
 208
 209   static void decrement(sequenced_index_node*& x)
 210   {
 211     impl_pointer xi=x->impl();
 212     trampoline::decrement(xi);
 213     x=from_impl(xi);
 214   }
 215 };
 216
 217 } /* namespace multi_index::detail */
 218
 219 } /* namespace multi_index */
 220
 221 } /* namespace boost */
 222
 223 #endif