ceph/src/boost/libs/multi_index/include/boost/multi_index/detail/seq_index_node.hpp

   1 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
   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)
  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/raw_ptr.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
  33   boost::detail::allocator::rebind_to<
  34     Allocator,sequenced_index_node_impl
  35   >::type::pointer                      pointer;
  36   typedef typename
  37   boost::detail::allocator::rebind_to<
  38     Allocator,sequenced_index_node_impl
  39   >::type::const_pointer                const_pointer;
  40
  41   pointer& prior(){return prior_;}
  42   pointer  prior()const{return prior_;}
  43   pointer& next(){return next_;}
  44   pointer  next()const{return next_;}
  45
  46   /* interoperability with bidir_node_iterator */
  47
  48   static void increment(pointer& x){x=x->next();}
  49   static void decrement(pointer& x){x=x->prior();}
  50
  51   /* algorithmic stuff */
  52
  53   static void link(pointer x,pointer header)
  54   {
  55     x->prior()=header->prior();
  56     x->next()=header;
  57     x->prior()->next()=x->next()->prior()=x;
  58   };
  59
  60   static void unlink(pointer x)
  61   {
  62     x->prior()->next()=x->next();
  63     x->next()->prior()=x->prior();
  64   }
  65
  66   static void relink(pointer position,pointer x)
  67   {
  68     unlink(x);
  69     x->prior()=position->prior();
  70     x->next()=position;
  71     x->prior()->next()=x->next()->prior()=x;
  72   }
  73
  74   static void relink(pointer position,pointer x,pointer y)
  75   {
  76     /* position is assumed not to be in [x,y) */
  77
  78     if(x!=y){
  79       pointer z=y->prior();
  80       x->prior()->next()=y;
  81       y->prior()=x->prior();
  82       x->prior()=position->prior();
  83       z->next()=position;
  84       x->prior()->next()=x;
  85       z->next()->prior()=z;
  86     }
  87   }
  88
  89   static void reverse(pointer header)
  90   {
  91     pointer x=header;
  92     do{
  93       pointer y=x->next();
  94       std::swap(x->prior(),x->next());
  95       x=y;
  96     }while(x!=header);
  97   }
  98
  99   static void swap(pointer x,pointer y)
 100   {
 101     /* This swap function does not exchange the header nodes,
 102      * but rather their pointers. This is *not* used for implementing
 103      * sequenced_index::swap.
 104      */
 105
 106     if(x->next()!=x){
 107       if(y->next()!=y){
 108         std::swap(x->next(),y->next());
 109         std::swap(x->prior(),y->prior());
 110         x->next()->prior()=x->prior()->next()=x;
 111         y->next()->prior()=y->prior()->next()=y;
 112       }
 113       else{
 114         y->next()=x->next();
 115         y->prior()=x->prior();
 116         x->next()=x->prior()=x;
 117         y->next()->prior()=y->prior()->next()=y;
 118       }
 119     }
 120     else if(y->next()!=y){
 121       x->next()=y->next();
 122       x->prior()=y->prior();
 123       y->next()=y->prior()=y;
 124       x->next()->prior()=x->prior()->next()=x;
 125     }
 126   }
 127
 128 private:
 129   pointer prior_;
 130   pointer next_;
 131 };
 132
 133 template<typename Super>
 134 struct sequenced_index_node_trampoline:
 135   sequenced_index_node_impl<
 136     typename boost::detail::allocator::rebind_to<
 137       typename Super::allocator_type,
 138       char
 139     >::type
 140   >
 141 {
 142   typedef sequenced_index_node_impl<
 143     typename boost::detail::allocator::rebind_to<
 144       typename Super::allocator_type,
 145       char
 146     >::type
 147   > impl_type;
 148 };
 149
 150 template<typename Super>
 151 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
 152 {
 153 private:
 154   typedef sequenced_index_node_trampoline<Super> trampoline;
 155
 156 public:
 157   typedef typename trampoline::impl_type         impl_type;
 158   typedef typename trampoline::pointer           impl_pointer;
 159   typedef typename trampoline::const_pointer     const_impl_pointer;
 160
 161   impl_pointer& prior(){return trampoline::prior();}
 162   impl_pointer  prior()const{return trampoline::prior();}
 163   impl_pointer& next(){return trampoline::next();}
 164   impl_pointer  next()const{return trampoline::next();}
 165
 166   impl_pointer impl()
 167   {
 168     return static_cast<impl_pointer>(
 169       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 170   }
 171
 172   const_impl_pointer impl()const
 173   {
 174     return static_cast<const_impl_pointer>(
 175       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 176   }
 177
 178   static sequenced_index_node* from_impl(impl_pointer x)
 179   {
 180     return
 181       static_cast<sequenced_index_node*>(
 182         static_cast<trampoline*>(
 183           raw_ptr<impl_type*>(x)));
 184   }
 185
 186   static const sequenced_index_node* from_impl(const_impl_pointer x)
 187   {
 188     return
 189       static_cast<const sequenced_index_node*>(
 190         static_cast<const trampoline*>(
 191           raw_ptr<const impl_type*>(x)));
 192   }
 193
 194   /* interoperability with bidir_node_iterator */
 195
 196   static void increment(sequenced_index_node*& x)
 197   {
 198     impl_pointer xi=x->impl();
 199     trampoline::increment(xi);
 200     x=from_impl(xi);
 201   }
 202
 203   static void decrement(sequenced_index_node*& x)
 204   {
 205     impl_pointer xi=x->impl();
 206     trampoline::decrement(xi);
 207     x=from_impl(xi);
 208   }
 209 };
 210
 211 } /* namespace multi_index::detail */
 212
 213 } /* namespace multi_index */
 214
 215 } /* namespace boost */
 216
 217 #endif