multi_index/detail/rnd_index_node.hpp

0001 /* Copyright 2003-2021 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_RND_INDEX_NODE_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_RND_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/integer/common_factor_rt.hpp>
0019 #include <boost/multi_index/detail/allocator_traits.hpp>
0020 #include <boost/multi_index/detail/raw_ptr.hpp>
0021 #include <cstddef>
0022 #include <functional>
0023
0024 namespace boost{
0025
0026 namespace multi_index{
0027
0028 namespace detail{
0029
0030 template<typename Allocator>
0031 struct random_access_index_node_impl
0032 {
0033   typedef typename rebind_alloc_for<
0034     Allocator,random_access_index_node_impl
0035   >::type                                             node_allocator;
0036   typedef allocator_traits<node_allocator>            node_alloc_traits;
0037   typedef typename node_alloc_traits::pointer         pointer;
0038   typedef typename node_alloc_traits::const_pointer   const_pointer;
0039   typedef typename node_alloc_traits::difference_type difference_type;
0040   typedef typename rebind_alloc_for<
0041     Allocator,pointer
0042   >::type                                             ptr_allocator;
0043   typedef allocator_traits<ptr_allocator>             ptr_alloc_traits;
0044   typedef typename ptr_alloc_traits::pointer          ptr_pointer;
0045
0046   ptr_pointer& up(){return up_;}
0047   ptr_pointer  up()const{return up_;}
0048
0049   /* interoperability with rnd_node_iterator */
0050
0051   static void increment(pointer& x)
0052   {
0053     x=*(x->up()+1);
0054   }
0055
0056   static void decrement(pointer& x)
0057   {
0058     x=*(x->up()-1);
0059   }
0060
0061   static void advance(pointer& x,difference_type n)
0062   {
0063     x=*(x->up()+n);
0064   }
0065
0066   static difference_type distance(pointer x,pointer y)
0067   {
0068     return static_cast<difference_type>(y->up()-x->up());
0069   }
0070
0071   /* algorithmic stuff */
0072
0073   static void relocate(ptr_pointer pos,ptr_pointer x)
0074   {
0075     pointer n=*x;
0076     if(x<pos){
0077       extract(x,pos);
0078       *(pos-1)=n;
0079       n->up()=pos-1;
0080     }
0081     else{
0082       while(x!=pos){
0083         *x=*(x-1);
0084         (*x)->up()=x;
0085         --x;
0086       }
0087       *pos=n;
0088       n->up()=pos;
0089     }
0090   };
0091
0092   static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)
0093   {
0094     ptr_pointer begin,middle,end;
0095     if(pos<first){
0096       begin=pos;
0097       middle=first;
0098       end=last;
0099     }
0100     else{
0101       begin=first;
0102       middle=last;
0103       end=pos;
0104     }
0105
0106     std::ptrdiff_t n=end-begin;
0107     std::ptrdiff_t m=middle-begin;
0108     std::ptrdiff_t n_m=n-m;
0109     std::ptrdiff_t p=integer::gcd(n,m);
0110
0111     for(std::ptrdiff_t i=0;i<p;++i){
0112       pointer tmp=begin[i];
0113       for(std::ptrdiff_t j=i,k;;){
0114         if(j<n_m)k=j+m;
0115         else     k=j-n_m;
0116         if(k==i){
0117           *(begin+j)=tmp;
0118           (*(begin+j))->up()=begin+j;
0119           break;
0120         }
0121         else{
0122           *(begin+j)=*(begin+k);
0123           (*(begin+j))->up()=begin+j;
0124         }
0125
0126         if(k<n_m)j=k+m;
0127         else     j=k-n_m;
0128         if(j==i){
0129           *(begin+k)=tmp;
0130           (*(begin+k))->up()=begin+k;
0131           break;
0132         }
0133         else{
0134           *(begin+k)=*(begin+j);
0135           (*(begin+k))->up()=begin+k;
0136         }
0137       }
0138     }
0139   };
0140
0141   static void extract(ptr_pointer x,ptr_pointer pend)
0142   {
0143     --pend;
0144     while(x!=pend){
0145       *x=*(x+1);
0146       (*x)->up()=x;
0147       ++x;
0148     }
0149   }
0150
0151   static void transfer(
0152     ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)
0153   {
0154     while(pbegin0!=pend0){
0155       *pbegin1=*pbegin0++;
0156       (*pbegin1)->up()=pbegin1;
0157       ++pbegin1;
0158     }
0159   }
0160
0161   static void reverse(ptr_pointer pbegin,ptr_pointer pend)
0162   {
0163     std::ptrdiff_t d=(pend-pbegin)/2;
0164     for(std::ptrdiff_t i=0;i<d;++i){
0165       std::swap(*pbegin,*--pend);
0166       (*pbegin)->up()=pbegin;
0167       (*pend)->up()=pend;
0168       ++pbegin;
0169     }
0170   }
0171
0172   static ptr_pointer gather_nulls(
0173     ptr_pointer pbegin,ptr_pointer pend,ptr_pointer x)
0174   {
0175     for(ptr_pointer p=pbegin;p!=x;++p){
0176       if(*p){
0177         *pbegin=*p;
0178         (*pbegin)->up()=pbegin;
0179         ++pbegin;
0180       }
0181     }
0182     for(ptr_pointer p=pend;p!=x;){
0183       if(*--p){
0184         *--pend=*p;
0185         (*pend)->up()=pend;
0186       }
0187     }
0188     return pbegin;
0189   }
0190
0191 private:
0192   ptr_pointer up_;
0193 };
0194
0195 template<typename Super>
0196 struct random_access_index_node_trampoline:
0197   random_access_index_node_impl<
0198     typename rebind_alloc_for<
0199       typename Super::allocator_type,
0200       char
0201     >::type
0202   >
0203 {
0204   typedef random_access_index_node_impl<
0205     typename rebind_alloc_for<
0206       typename Super::allocator_type,
0207       char
0208     >::type
0209   > impl_type;
0210 };
0211
0212 template<typename Super>
0213 struct random_access_index_node:
0214   Super,random_access_index_node_trampoline<Super>
0215 {
0216 private:
0217   typedef random_access_index_node_trampoline<Super> trampoline;
0218
0219 public:
0220   typedef typename trampoline::impl_type         impl_type;
0221   typedef typename trampoline::pointer           impl_pointer;
0222   typedef typename trampoline::const_pointer     const_impl_pointer;
0223   typedef typename trampoline::difference_type   difference_type;
0224   typedef typename trampoline::ptr_pointer       impl_ptr_pointer;
0225
0226   impl_ptr_pointer& up(){return trampoline::up();}
0227   impl_ptr_pointer  up()const{return trampoline::up();}
0228
0229   impl_pointer impl()
0230   {
0231     return static_cast<impl_pointer>(
0232       static_cast<impl_type*>(static_cast<trampoline*>(this)));
0233   }
0234
0235   const_impl_pointer impl()const
0236   {
0237     return static_cast<const_impl_pointer>(
0238       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
0239   }
0240
0241   static random_access_index_node* from_impl(impl_pointer x)
0242   {
0243     return
0244       static_cast<random_access_index_node*>(
0245         static_cast<trampoline*>(
0246           raw_ptr<impl_type*>(x)));
0247   }
0248
0249   static const random_access_index_node* from_impl(const_impl_pointer x)
0250   {
0251     return
0252       static_cast<const random_access_index_node*>(
0253         static_cast<const trampoline*>(
0254           raw_ptr<const impl_type*>(x)));
0255   }
0256
0257   /* interoperability with rnd_node_iterator */
0258
0259   static void increment(random_access_index_node*& x)
0260   {
0261     impl_pointer xi=x->impl();
0262     trampoline::increment(xi);
0263     x=from_impl(xi);
0264   }
0265
0266   static void decrement(random_access_index_node*& x)
0267   {
0268     impl_pointer xi=x->impl();
0269     trampoline::decrement(xi);
0270     x=from_impl(xi);
0271   }
0272
0273   static void advance(random_access_index_node*& x,difference_type n)
0274   {
0275     impl_pointer xi=x->impl();
0276     trampoline::advance(xi,n);
0277     x=from_impl(xi);
0278   }
0279
0280   static difference_type distance(
0281     random_access_index_node* x,random_access_index_node* y)
0282   {
0283     return trampoline::distance(x->impl(),y->impl());
0284   }
0285 };
0286
0287 } /* namespace multi_index::detail */
0288
0289 } /* namespace multi_index */
0290
0291 } /* namespace boost */
0292
0293 #endif