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

   1 /* Copyright 2003-2018 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 <memory>
  19 #include <boost/detail/allocator_utilities.hpp>
  20 #include <boost/multi_index/detail/raw_ptr.hpp>
  21
  22 namespace boost{
  23
  24 namespace multi_index{
  25
  26 namespace detail{
  27
  28 /* doubly-linked node for use by sequenced_index */
  29
  30 template<typename Allocator>
  31 struct sequenced_index_node_impl
  32 {
  33   typedef typename
  34   boost::detail::allocator::rebind_to<
  35     Allocator,sequenced_index_node_impl
  36   >::type                                          node_allocator;
  37 #ifdef BOOST_NO_CXX11_ALLOCATOR
  38   typedef typename node_allocator::pointer         pointer;
  39   typedef typename node_allocator::const_pointer   const_pointer;
  40 #else
  41   typedef std::allocator_traits<node_allocator>    allocator_traits;
  42   typedef typename allocator_traits::pointer       pointer;
  43   typedef typename allocator_traits::const_pointer const_pointer;
  44 #endif
  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   sequenced_index_node_impl<
 140     typename boost::detail::allocator::rebind_to<
 141       typename Super::allocator_type,
 142       char
 143     >::type
 144   >
 145 {
 146   typedef sequenced_index_node_impl<
 147     typename boost::detail::allocator::rebind_to<
 148       typename Super::allocator_type,
 149       char
 150     >::type
 151   > impl_type;
 152 };
 153
 154 template<typename Super>
 155 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
 156 {
 157 private:
 158   typedef sequenced_index_node_trampoline<Super> trampoline;
 159
 160 public:
 161   typedef typename trampoline::impl_type         impl_type;
 162   typedef typename trampoline::pointer           impl_pointer;
 163   typedef typename trampoline::const_pointer     const_impl_pointer;
 164
 165   impl_pointer& prior(){return trampoline::prior();}
 166   impl_pointer  prior()const{return trampoline::prior();}
 167   impl_pointer& next(){return trampoline::next();}
 168   impl_pointer  next()const{return trampoline::next();}
 169
 170   impl_pointer impl()
 171   {
 172     return static_cast<impl_pointer>(
 173       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 174   }
 175
 176   const_impl_pointer impl()const
 177   {
 178     return static_cast<const_impl_pointer>(
 179       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 180   }
 181
 182   static sequenced_index_node* from_impl(impl_pointer x)
 183   {
 184     return
 185       static_cast<sequenced_index_node*>(
 186         static_cast<trampoline*>(
 187           raw_ptr<impl_type*>(x)));
 188   }
 189
 190   static const sequenced_index_node* from_impl(const_impl_pointer x)
 191   {
 192     return
 193       static_cast<const sequenced_index_node*>(
 194         static_cast<const trampoline*>(
 195           raw_ptr<const impl_type*>(x)));
 196   }
 197
 198   /* interoperability with bidir_node_iterator */
 199
 200   static void increment(sequenced_index_node*& x)
 201   {
 202     impl_pointer xi=x->impl();
 203     trampoline::increment(xi);
 204     x=from_impl(xi);
 205   }
 206
 207   static void decrement(sequenced_index_node*& x)
 208   {
 209     impl_pointer xi=x->impl();
 210     trampoline::decrement(xi);
 211     x=from_impl(xi);
 212   }
 213 };
 214
 215 } /* namespace multi_index::detail */
 216
 217 } /* namespace multi_index */
 218
 219 } /* namespace boost */
 220
 221 #endif