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