multi_index/detail/seq_index_node.hpp

0001 /* Copyright 2003-2019 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/multi_index/detail/allocator_traits.hpp>
0019 #include <boost/multi_index/detail/raw_ptr.hpp>
0020
0021 namespace boost{
0022
0023 namespace multi_index{
0024
0025 namespace detail{
0026
0027 /* doubly-linked node for use by sequenced_index */
0028
0029 template<typename Allocator>
0030 struct sequenced_index_node_impl
0031 {
0032   typedef typename rebind_alloc_for<
0033     Allocator,sequenced_index_node_impl
0034   >::type                                        node_allocator;
0035   typedef allocator_traits<node_allocator>       alloc_traits;
0036   typedef typename alloc_traits::pointer         pointer;
0037   typedef typename alloc_traits::const_pointer   const_pointer;
0038   typedef typename alloc_traits::difference_type difference_type;
0039
0040   pointer& prior(){return prior_;}
0041   pointer  prior()const{return prior_;}
0042   pointer& next(){return next_;}
0043   pointer  next()const{return next_;}
0044
0045   /* interoperability with bidir_node_iterator */
0046
0047   static void increment(pointer& x){x=x->next();}
0048   static void decrement(pointer& x){x=x->prior();}
0049
0050   /* algorithmic stuff */
0051
0052   static void link(pointer x,pointer header)
0053   {
0054     x->prior()=header->prior();
0055     x->next()=header;
0056     x->prior()->next()=x->next()->prior()=x;
0057   }
0058
0059   static void unlink(pointer x)
0060   {
0061     x->prior()->next()=x->next();
0062     x->next()->prior()=x->prior();
0063   }
0064
0065   static void relink(pointer position,pointer x)
0066   {
0067     unlink(x);
0068     x->prior()=position->prior();
0069     x->next()=position;
0070     x->prior()->next()=x->next()->prior()=x;
0071   }
0072
0073   static void relink(pointer position,pointer x,pointer y)
0074   {
0075     /* position is assumed not to be in [x,y) */
0076
0077     if(x!=y){
0078       pointer z=y->prior();
0079       x->prior()->next()=y;
0080       y->prior()=x->prior();
0081       x->prior()=position->prior();
0082       z->next()=position;
0083       x->prior()->next()=x;
0084       z->next()->prior()=z;
0085     }
0086   }
0087
0088   static void reverse(pointer header)
0089   {
0090     pointer x=header;
0091     do{
0092       pointer y=x->next();
0093       std::swap(x->prior(),x->next());
0094       x=y;
0095     }while(x!=header);
0096   }
0097
0098   static void swap(pointer x,pointer y)
0099   {
0100     /* This swap function does not exchange the header nodes,
0101      * but rather their pointers. This is *not* used for implementing
0102      * sequenced_index::swap.
0103      */
0104
0105     if(x->next()!=x){
0106       if(y->next()!=y){
0107         std::swap(x->next(),y->next());
0108         std::swap(x->prior(),y->prior());
0109         x->next()->prior()=x->prior()->next()=x;
0110         y->next()->prior()=y->prior()->next()=y;
0111       }
0112       else{
0113         y->next()=x->next();
0114         y->prior()=x->prior();
0115         x->next()=x->prior()=x;
0116         y->next()->prior()=y->prior()->next()=y;
0117       }
0118     }
0119     else if(y->next()!=y){
0120       x->next()=y->next();
0121       x->prior()=y->prior();
0122       y->next()=y->prior()=y;
0123       x->next()->prior()=x->prior()->next()=x;
0124     }
0125   }
0126
0127 private:
0128   pointer prior_;
0129   pointer next_;
0130 };
0131
0132 template<typename Super>
0133 struct sequenced_index_node_trampoline:
0134   sequenced_index_node_impl<
0135     typename rebind_alloc_for<
0136       typename Super::allocator_type,
0137       char
0138     >::type
0139   >
0140 {
0141   typedef sequenced_index_node_impl<
0142     typename rebind_alloc_for<
0143       typename Super::allocator_type,
0144       char
0145     >::type
0146   > impl_type;
0147 };
0148
0149 template<typename Super>
0150 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
0151 {
0152 private:
0153   typedef sequenced_index_node_trampoline<Super> trampoline;
0154
0155 public:
0156   typedef typename trampoline::impl_type       impl_type;
0157   typedef typename trampoline::pointer         impl_pointer;
0158   typedef typename trampoline::const_pointer   const_impl_pointer;
0159   typedef typename trampoline::difference_type difference_type;
0160
0161   impl_pointer& prior(){return trampoline::prior();}
0162   impl_pointer  prior()const{return trampoline::prior();}
0163   impl_pointer& next(){return trampoline::next();}
0164   impl_pointer  next()const{return trampoline::next();}
0165
0166   impl_pointer impl()
0167   {
0168     return static_cast<impl_pointer>(
0169       static_cast<impl_type*>(static_cast<trampoline*>(this)));
0170   }
0171
0172   const_impl_pointer impl()const
0173   {
0174     return static_cast<const_impl_pointer>(
0175       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
0176   }
0177
0178   static sequenced_index_node* from_impl(impl_pointer x)
0179   {
0180     return
0181       static_cast<sequenced_index_node*>(
0182         static_cast<trampoline*>(
0183           raw_ptr<impl_type*>(x)));
0184   }
0185
0186   static const sequenced_index_node* from_impl(const_impl_pointer x)
0187   {
0188     return
0189       static_cast<const sequenced_index_node*>(
0190         static_cast<const trampoline*>(
0191           raw_ptr<const impl_type*>(x)));
0192   }
0193
0194   /* interoperability with bidir_node_iterator */
0195
0196   static void increment(sequenced_index_node*& x)
0197   {
0198     impl_pointer xi=x->impl();
0199     trampoline::increment(xi);
0200     x=from_impl(xi);
0201   }
0202
0203   static void decrement(sequenced_index_node*& x)
0204   {
0205     impl_pointer xi=x->impl();
0206     trampoline::decrement(xi);
0207     x=from_impl(xi);
0208   }
0209 };
0210
0211 } /* namespace multi_index::detail */
0212
0213 } /* namespace multi_index */
0214
0215 } /* namespace boost */
0216
0217 #endif