ceph/src/boost/libs/multi_index/include/boost/multi_index/detail/rnd_index_node.hpp

   1 /* Copyright 2003-2015 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_RND_INDEX_NODE_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_RND_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/detail/allocator_utilities.hpp>
  19 #include <boost/integer/common_factor_rt.hpp>
  20 #include <boost/multi_index/detail/raw_ptr.hpp>
  21 #include <cstddef>
  22 #include <functional>
  23
  24 namespace boost{
  25
  26 namespace multi_index{
  27
  28 namespace detail{
  29
  30 template<typename Allocator>
  31 struct random_access_index_node_impl
  32 {
  33   typedef typename
  34   boost::detail::allocator::rebind_to<
  35     Allocator,random_access_index_node_impl
  36   >::type::pointer                          pointer;
  37   typedef typename
  38   boost::detail::allocator::rebind_to<
  39     Allocator,random_access_index_node_impl
  40   >::type::const_pointer                    const_pointer;
  41   typedef typename
  42   boost::detail::allocator::rebind_to<
  43     Allocator,pointer
  44   >::type::pointer                          ptr_pointer;
  45
  46   ptr_pointer& up(){return up_;}
  47   ptr_pointer  up()const{return up_;}
  48
  49   /* interoperability with rnd_node_iterator */
  50
  51   static void increment(pointer& x)
  52   {
  53     x=*(x->up()+1);
  54   }
  55
  56   static void decrement(pointer& x)
  57   {
  58     x=*(x->up()-1);
  59   }
  60
  61   static void advance(pointer& x,std::ptrdiff_t n)
  62   {
  63     x=*(x->up()+n);
  64   }
  65
  66   static std::ptrdiff_t distance(pointer x,pointer y)
  67   {
  68     return y->up()-x->up();
  69   }
  70
  71   /* algorithmic stuff */
  72
  73   static void relocate(ptr_pointer pos,ptr_pointer x)
  74   {
  75     pointer n=*x;
  76     if(x<pos){
  77       extract(x,pos);
  78       *(pos-1)=n;
  79       n->up()=pos-1;
  80     }
  81     else{
  82       while(x!=pos){
  83         *x=*(x-1);
  84         (*x)->up()=x;
  85         --x;
  86       }
  87       *pos=n;
  88       n->up()=pos;
  89     }
  90   };
  91
  92   static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)
  93   {
  94     ptr_pointer begin,middle,end;
  95     if(pos<first){
  96       begin=pos;
  97       middle=first;
  98       end=last;
  99     }
 100     else{
 101       begin=first;
 102       middle=last;
 103       end=pos;
 104     }
 105
 106     std::ptrdiff_t n=end-begin;
 107     std::ptrdiff_t m=middle-begin;
 108     std::ptrdiff_t n_m=n-m;
 109     std::ptrdiff_t p=integer::gcd(n,m);
 110
 111     for(std::ptrdiff_t i=0;i<p;++i){
 112       pointer tmp=begin[i];
 113       for(std::ptrdiff_t j=i,k;;){
 114         if(j<n_m)k=j+m;
 115         else     k=j-n_m;
 116         if(k==i){
 117           *(begin+j)=tmp;
 118           (*(begin+j))->up()=begin+j;
 119           break;
 120         }
 121         else{
 122           *(begin+j)=*(begin+k);
 123           (*(begin+j))->up()=begin+j;
 124         }
 125
 126         if(k<n_m)j=k+m;
 127         else     j=k-n_m;
 128         if(j==i){
 129           *(begin+k)=tmp;
 130           (*(begin+k))->up()=begin+k;
 131           break;
 132         }
 133         else{
 134           *(begin+k)=*(begin+j);
 135           (*(begin+k))->up()=begin+k;
 136         }
 137       }
 138     }
 139   };
 140
 141   static void extract(ptr_pointer x,ptr_pointer pend)
 142   {
 143     --pend;
 144     while(x!=pend){
 145       *x=*(x+1);
 146       (*x)->up()=x;
 147       ++x;
 148     }
 149   }
 150
 151   static void transfer(
 152     ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)
 153   {
 154     while(pbegin0!=pend0){
 155       *pbegin1=*pbegin0++;
 156       (*pbegin1)->up()=pbegin1;
 157       ++pbegin1;
 158     }
 159   }
 160
 161   static void reverse(ptr_pointer pbegin,ptr_pointer pend)
 162   {
 163     std::ptrdiff_t d=(pend-pbegin)/2;
 164     for(std::ptrdiff_t i=0;i<d;++i){
 165       std::swap(*pbegin,*--pend);
 166       (*pbegin)->up()=pbegin;
 167       (*pend)->up()=pend;
 168       ++pbegin;
 169     }
 170   }
 171
 172 private:
 173   ptr_pointer up_;
 174 };
 175
 176 template<typename Super>
 177 struct random_access_index_node_trampoline:
 178   random_access_index_node_impl<
 179     typename boost::detail::allocator::rebind_to<
 180       typename Super::allocator_type,
 181       char
 182     >::type
 183   >
 184 {
 185   typedef random_access_index_node_impl<
 186     typename boost::detail::allocator::rebind_to<
 187       typename Super::allocator_type,
 188       char
 189     >::type
 190   > impl_type;
 191 };
 192
 193 template<typename Super>
 194 struct random_access_index_node:
 195   Super,random_access_index_node_trampoline<Super>
 196 {
 197 private:
 198   typedef random_access_index_node_trampoline<Super> trampoline;
 199
 200 public:
 201   typedef typename trampoline::impl_type     impl_type;
 202   typedef typename trampoline::pointer       impl_pointer;
 203   typedef typename trampoline::const_pointer const_impl_pointer;
 204   typedef typename trampoline::ptr_pointer   impl_ptr_pointer;
 205
 206   impl_ptr_pointer& up(){return trampoline::up();}
 207   impl_ptr_pointer  up()const{return trampoline::up();}
 208
 209   impl_pointer impl()
 210   {
 211     return static_cast<impl_pointer>(
 212       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 213   }
 214
 215   const_impl_pointer impl()const
 216   {
 217     return static_cast<const_impl_pointer>(
 218       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 219   }
 220
 221   static random_access_index_node* from_impl(impl_pointer x)
 222   {
 223     return
 224       static_cast<random_access_index_node*>(
 225         static_cast<trampoline*>(
 226           raw_ptr<impl_type*>(x)));
 227   }
 228
 229   static const random_access_index_node* from_impl(const_impl_pointer x)
 230   {
 231     return
 232       static_cast<const random_access_index_node*>(
 233         static_cast<const trampoline*>(
 234           raw_ptr<const impl_type*>(x)));
 235   }
 236
 237   /* interoperability with rnd_node_iterator */
 238
 239   static void increment(random_access_index_node*& x)
 240   {
 241     impl_pointer xi=x->impl();
 242     trampoline::increment(xi);
 243     x=from_impl(xi);
 244   }
 245
 246   static void decrement(random_access_index_node*& x)
 247   {
 248     impl_pointer xi=x->impl();
 249     trampoline::decrement(xi);
 250     x=from_impl(xi);
 251   }
 252
 253   static void advance(random_access_index_node*& x,std::ptrdiff_t n)
 254   {
 255     impl_pointer xi=x->impl();
 256     trampoline::advance(xi,n);
 257     x=from_impl(xi);
 258   }
 259
 260   static std::ptrdiff_t distance(
 261     random_access_index_node* x,random_access_index_node* y)
 262   {
 263     return trampoline::distance(x->impl(),y->impl());
 264   }
 265 };
 266
 267 } /* namespace multi_index::detail */
 268
 269 } /* namespace multi_index */
 270
 271 } /* namespace boost */
 272
 273 #endif