Line data    Source code

       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       27037 :   pointer& prior(){return prior_;}
      41             :   pointer  prior()const{return prior_;}
      42       25893 :   pointer& next(){return next_;}
      43             :   pointer  next()const{return next_;}
      44             : 
      45             :   /* interoperability with bidir_node_iterator */
      46             : 
      47           0 :   static void increment(pointer& x){x=x->next();}
      48        1161 :   static void decrement(pointer& x){x=x->prior();}
      49             : 
      50             :   /* algorithmic stuff */
      51             : 
      52         387 :   static void link(pointer x,pointer header)
      53             :   {
      54         387 :     x->prior()=header->prior();
      55         387 :     x->next()=header;
      56         387 :     x->prior()->next()=x->next()->prior()=x;
      57         387 :   }
      58             : 
      59           0 :   static void unlink(pointer x)
      60             :   {
      61           0 :     x->prior()->next()=x->next();
      62           0 :     x->next()->prior()=x->prior();
      63           0 :   }
      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       24328 :   impl_pointer& prior(){return trampoline::prior();}
     162             :   impl_pointer  prior()const{return trampoline::prior();}
     163       24732 :   impl_pointer& next(){return trampoline::next();}
     164             :   impl_pointer  next()const{return trampoline::next();}
     165             : 
     166       26263 :   impl_pointer impl()
     167             :   {
     168       26263 :     return static_cast<impl_pointer>(
     169       26263 :       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        1565 :   static sequenced_index_node* from_impl(impl_pointer x)
     179             :   {
     180        1565 :     return
     181        1565 :       static_cast<sequenced_index_node*>(
     182             :         static_cast<trampoline*>(
     183        1565 :           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           0 :   static void increment(sequenced_index_node*& x)
     197             :   {
     198           0 :     impl_pointer xi=x->impl();
     199           0 :     trampoline::increment(xi);
     200           0 :     x=from_impl(xi);
     201           0 :   }
     202             : 
     203        1161 :   static void decrement(sequenced_index_node*& x)
     204             :   {
     205        1161 :     impl_pointer xi=x->impl();
     206        1161 :     trampoline::decrement(xi);
     207        1161 :     x=from_impl(xi);
     208        1161 :   }
     209             : };
     210             : 
     211             : } /* namespace multi_index::detail */
     212             : 
     213             : } /* namespace multi_index */
     214             : 
     215             : } /* namespace boost */
     216             : 
     217             : #endif