Chris@101: /* Copyright 2003-2013 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <algorithm>
Chris@16: #include <boost/detail/allocator_utilities.hpp>
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@16: /* doubly-linked node for use by sequenced_index */
Chris@16: 
Chris@16: template<typename Allocator>
Chris@16: struct sequenced_index_node_impl
Chris@16: {
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:     Allocator,sequenced_index_node_impl
Chris@101:   >::type::pointer                      pointer;
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:     Allocator,sequenced_index_node_impl
Chris@101:   >::type::const_pointer                const_pointer;
Chris@16: 
Chris@16:   pointer& prior(){return prior_;}
Chris@16:   pointer  prior()const{return prior_;}
Chris@16:   pointer& next(){return next_;}
Chris@16:   pointer  next()const{return next_;}
Chris@16: 
Chris@16:   /* interoperability with bidir_node_iterator */
Chris@16: 
Chris@16:   static void increment(pointer& x){x=x->next();}
Chris@16:   static void decrement(pointer& x){x=x->prior();}
Chris@16: 
Chris@16:   /* algorithmic stuff */
Chris@16: 
Chris@16:   static void link(pointer x,pointer header)
Chris@16:   {
Chris@16:     x->prior()=header->prior();
Chris@16:     x->next()=header;
Chris@16:     x->prior()->next()=x->next()->prior()=x;
Chris@16:   };
Chris@16: 
Chris@16:   static void unlink(pointer x)
Chris@16:   {
Chris@16:     x->prior()->next()=x->next();
Chris@16:     x->next()->prior()=x->prior();
Chris@16:   }
Chris@16: 
Chris@16:   static void relink(pointer position,pointer x)
Chris@16:   {
Chris@16:     unlink(x);
Chris@16:     x->prior()=position->prior();
Chris@16:     x->next()=position;
Chris@16:     x->prior()->next()=x->next()->prior()=x;
Chris@16:   }
Chris@16: 
Chris@16:   static void relink(pointer position,pointer x,pointer y)
Chris@16:   {
Chris@16:     /* position is assumed not to be in [x,y) */
Chris@16: 
Chris@16:     if(x!=y){
Chris@16:       pointer z=y->prior();
Chris@16:       x->prior()->next()=y;
Chris@16:       y->prior()=x->prior();
Chris@16:       x->prior()=position->prior();
Chris@16:       z->next()=position;
Chris@16:       x->prior()->next()=x;
Chris@16:       z->next()->prior()=z;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   static void reverse(pointer header)
Chris@16:   {
Chris@16:     pointer x=header;
Chris@16:     do{
Chris@16:       pointer y=x->next();
Chris@16:       std::swap(x->prior(),x->next());
Chris@16:       x=y;
Chris@16:     }while(x!=header);
Chris@16:   }
Chris@16: 
Chris@16:   static void swap(pointer x,pointer y)
Chris@16:   {
Chris@16:     /* This swap function does not exchange the header nodes,
Chris@16:      * but rather their pointers. This is *not* used for implementing
Chris@16:      * sequenced_index::swap.
Chris@16:      */
Chris@16: 
Chris@16:     if(x->next()!=x){
Chris@16:       if(y->next()!=y){
Chris@16:         std::swap(x->next(),y->next());
Chris@16:         std::swap(x->prior(),y->prior());
Chris@16:         x->next()->prior()=x->prior()->next()=x;
Chris@16:         y->next()->prior()=y->prior()->next()=y;
Chris@16:       }
Chris@16:       else{
Chris@16:         y->next()=x->next();
Chris@16:         y->prior()=x->prior();
Chris@16:         x->next()=x->prior()=x;
Chris@16:         y->next()->prior()=y->prior()->next()=y;
Chris@16:       }
Chris@16:     }
Chris@16:     else if(y->next()!=y){
Chris@16:       x->next()=y->next();
Chris@16:       x->prior()=y->prior();
Chris@16:       y->next()=y->prior()=y;
Chris@16:       x->next()->prior()=x->prior()->next()=x;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   pointer prior_;
Chris@16:   pointer next_;
Chris@16: };
Chris@16: 
Chris@16: template<typename Super>
Chris@16: struct sequenced_index_node_trampoline:
Chris@101:   sequenced_index_node_impl<
Chris@101:     typename boost::detail::allocator::rebind_to<
Chris@101:       typename Super::allocator_type,
Chris@101:       char
Chris@101:     >::type
Chris@101:   >
Chris@16: {
Chris@101:   typedef sequenced_index_node_impl<
Chris@101:     typename boost::detail::allocator::rebind_to<
Chris@101:       typename Super::allocator_type,
Chris@101:       char
Chris@101:     >::type
Chris@101:   > impl_type;
Chris@16: };
Chris@16: 
Chris@16: template<typename Super>
Chris@16: struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
Chris@16: {
Chris@16: private:
Chris@16:   typedef sequenced_index_node_trampoline<Super> trampoline;
Chris@16: 
Chris@16: public:
Chris@16:   typedef typename trampoline::impl_type         impl_type;
Chris@16:   typedef typename trampoline::pointer           impl_pointer;
Chris@16:   typedef typename trampoline::const_pointer     const_impl_pointer;
Chris@16: 
Chris@16:   impl_pointer& prior(){return trampoline::prior();}
Chris@16:   impl_pointer  prior()const{return trampoline::prior();}
Chris@16:   impl_pointer& next(){return trampoline::next();}
Chris@16:   impl_pointer  next()const{return trampoline::next();}
Chris@16: 
Chris@16:   impl_pointer impl()
Chris@16:   {
Chris@16:     return static_cast<impl_pointer>(
Chris@16:       static_cast<impl_type*>(static_cast<trampoline*>(this)));
Chris@16:   }
Chris@16: 
Chris@16:   const_impl_pointer impl()const
Chris@16:   {
Chris@16:     return static_cast<const_impl_pointer>(
Chris@16:       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
Chris@16:   }
Chris@16: 
Chris@16:   static sequenced_index_node* from_impl(impl_pointer x)
Chris@16:   {
Chris@16:     return static_cast<sequenced_index_node*>(
Chris@16:       static_cast<trampoline*>(&*x));
Chris@16:   }
Chris@16: 
Chris@16:   static const sequenced_index_node* from_impl(const_impl_pointer x)
Chris@16:   {
Chris@16:     return static_cast<const sequenced_index_node*>(
Chris@16:       static_cast<const trampoline*>(&*x));
Chris@16:   }
Chris@16: 
Chris@16:   /* interoperability with bidir_node_iterator */
Chris@16: 
Chris@16:   static void increment(sequenced_index_node*& x)
Chris@16:   {
Chris@16:     impl_pointer xi=x->impl();
Chris@16:     trampoline::increment(xi);
Chris@16:     x=from_impl(xi);
Chris@16:   }
Chris@16: 
Chris@16:   static void decrement(sequenced_index_node*& x)
Chris@16:   {
Chris@16:     impl_pointer xi=x->impl();
Chris@16:     trampoline::decrement(xi);
Chris@16:     x=from_impl(xi);
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif