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

   1 /* Copyright 2003-2019 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/multi_index/detail/allocator_traits.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 rebind_alloc_for<
  33     Allocator,sequenced_index_node_impl
  34   >::type                                        node_allocator;
  35   typedef allocator_traits<node_allocator>       alloc_traits;
  36   typedef typename alloc_traits::pointer         pointer;
  37   typedef typename alloc_traits::const_pointer   const_pointer;
  38   typedef typename alloc_traits::difference_type difference_type;
  39
  40   pointer& prior(){return prior_;}
  41   pointer  prior()const{return prior_;}
  42   pointer& next(){return next_;}
  43   pointer  next()const{return next_;}
  44
  45   /* interoperability with bidir_node_iterator */
  46
  47   static void increment(pointer& x){x=x->next();}
  48   static void decrement(pointer& x){x=x->prior();}
  49
  50   /* algorithmic stuff */
  51
  52   static void link(pointer x,pointer header)
  53   {
  54     x->prior()=header->prior();
  55     x->next()=header;
  56     x->prior()->next()=x->next()->prior()=x;
  57   }
  58
  59   static void unlink(pointer x)
  60   {
  61     x->prior()->next()=x->next();
  62     x->next()->prior()=x->prior();
  63   }
  64
  65   static void relink(pointer position,pointer x)
  66   {
  67     unlink(x);
  68     x->prior()=position->prior();
  69     x->next()=position;
  70     x->prior()->next()=x->next()->prior()=x;
  71   }
  72
  73   static void relink(pointer position,pointer x,pointer y)
  74   {
  75     /* position is assumed not to be in [x,y) */
  76
  77     if(x!=y){
  78       pointer z=y->prior();
  79       x->prior()->next()=y;
  80       y->prior()=x->prior();
  81       x->prior()=position->prior();
  82       z->next()=position;
  83       x->prior()->next()=x;
  84       z->next()->prior()=z;
  85     }
  86   }
  87
  88   static void reverse(pointer header)
  89   {
  90     pointer x=header;
  91     do{
  92       pointer y=x->next();
  93       std::swap(x->prior(),x->next());
  94       x=y;
  95     }while(x!=header);
  96   }
  97
  98   static void swap(pointer x,pointer y)
  99   {
 100     /* This swap function does not exchange the header nodes,
 101      * but rather their pointers. This is *not* used for implementing
 102      * sequenced_index::swap.
 103      */
 104
 105     if(x->next()!=x){
 106       if(y->next()!=y){
 107         std::swap(x->next(),y->next());
 108         std::swap(x->prior(),y->prior());
 109         x->next()->prior()=x->prior()->next()=x;
 110         y->next()->prior()=y->prior()->next()=y;
 111       }
 112       else{
 113         y->next()=x->next();
 114         y->prior()=x->prior();
 115         x->next()=x->prior()=x;
 116         y->next()->prior()=y->prior()->next()=y;
 117       }
 118     }
 119     else if(y->next()!=y){
 120       x->next()=y->next();
 121       x->prior()=y->prior();
 122       y->next()=y->prior()=y;
 123       x->next()->prior()=x->prior()->next()=x;
 124     }
 125   }
 126
 127 private:
 128   pointer prior_;
 129   pointer next_;
 130 };
 131
 132 template<typename Super>
 133 struct sequenced_index_node_trampoline:
 134   sequenced_index_node_impl<
 135     typename rebind_alloc_for<
 136       typename Super::allocator_type,
 137       char
 138     >::type
 139   >
 140 {
 141   typedef sequenced_index_node_impl<
 142     typename rebind_alloc_for<
 143       typename Super::allocator_type,
 144       char
 145     >::type
 146   > impl_type;
 147 };
 148
 149 template<typename Super>
 150 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
 151 {
 152 private:
 153   typedef sequenced_index_node_trampoline<Super> trampoline;
 154
 155 public:
 156   typedef typename trampoline::impl_type       impl_type;
 157   typedef typename trampoline::pointer         impl_pointer;
 158   typedef typename trampoline::const_pointer   const_impl_pointer;
 159   typedef typename trampoline::difference_type difference_type;
 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