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

   1 /* Copyright 2003-2013 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_LOADER_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_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/multi_index/detail/auto_space.hpp>
  20 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
  21 #include <boost/noncopyable.hpp>
  22 #include <cstddef>
  23
  24 namespace boost{
  25
  26 namespace multi_index{
  27
  28 namespace detail{
  29
  30 /* This class implements a serialization rearranger for random access
  31  * indices. In order to achieve O(n) performance, the following strategy
  32  * is followed: the nodes of the index are handled as if in a bidirectional
  33  * list, where the next pointers are stored in the original
  34  * random_access_index_ptr_array and the prev pointers are stored in
  35  * an auxiliary array. Rearranging of nodes in such a bidirectional list
  36  * is constant time. Once all the arrangements are performed (on destruction
  37  * time) the list is traversed in reverse order and
  38  * pointers are swapped and set accordingly so that they recover its
  39  * original semantics ( *(node->up())==node ) while retaining the
  40  * new order.
  41  */
  42
  43 template<typename Allocator>
  44 class random_access_index_loader_base:private noncopyable
  45 {
  46 protected:
  47   typedef random_access_index_node_impl<
  48     typename boost::detail::allocator::rebind_to<
  49       Allocator,
  50       char
  51     >::type
  52   >                                                 node_impl_type;
  53   typedef typename node_impl_type::pointer          node_impl_pointer;
  54   typedef random_access_index_ptr_array<Allocator>  ptr_array;
  55
  56   random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_):
  57     al(al_),
  58     ptrs(ptrs_),
  59     header(*ptrs.end()),
  60     prev_spc(al,0),
  61     preprocessed(false)
  62   {}
  63
  64   ~random_access_index_loader_base()
  65   {
  66     if(preprocessed)
  67     {
  68       node_impl_pointer n=header;
  69       next(n)=n;
  70
  71       for(std::size_t i=ptrs.size();i--;){
  72         n=prev(n);
  73         std::size_t d=position(n);
  74         if(d!=i){
  75           node_impl_pointer m=prev(next_at(i));
  76           std::swap(m->up(),n->up());
  77           next_at(d)=next_at(i);
  78           std::swap(prev_at(d),prev_at(i));
  79         }
  80         next(n)=n;
  81       }
  82     }
  83   }
  84
  85   void rearrange(node_impl_pointer position_,node_impl_pointer x)
  86   {
  87     preprocess(); /* only incur this penalty if rearrange() is ever called */
  88     if(position_==node_impl_pointer(0))position_=header;
  89     next(prev(x))=next(x);
  90     prev(next(x))=prev(x);
  91     prev(x)=position_;
  92     next(x)=next(position_);
  93     next(prev(x))=prev(next(x))=x;
  94   }
  95
  96 private:
  97   void preprocess()
  98   {
  99     if(!preprocessed){
 100       /* get space for the auxiliary prev array */
 101       auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1);
 102       prev_spc.swap(tmp);
 103
 104       /* prev_spc elements point to the prev nodes */
 105       std::rotate_copy(
 106         &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data());
 107
 108       /* ptrs elements point to the next nodes */
 109       std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1);
 110
 111       preprocessed=true;
 112     }
 113   }
 114
 115   std::size_t position(node_impl_pointer x)const
 116   {
 117     return (std::size_t)(x->up()-ptrs.begin());
 118   }
 119
 120   node_impl_pointer& next_at(std::size_t n)const
 121   {
 122     return *ptrs.at(n);
 123   }
 124
 125   node_impl_pointer& prev_at(std::size_t n)const
 126   {
 127     return *(prev_spc.data()+n);
 128   }
 129
 130   node_impl_pointer& next(node_impl_pointer x)const
 131   {
 132     return *(x->up());
 133   }
 134
 135   node_impl_pointer& prev(node_impl_pointer x)const
 136   {
 137     return prev_at(position(x));
 138   }
 139
 140   Allocator                               al;
 141   ptr_array&                              ptrs;
 142   node_impl_pointer                       header;
 143   auto_space<node_impl_pointer,Allocator> prev_spc;
 144   bool                                    preprocessed;
 145 };
 146
 147 template<typename Node,typename Allocator>
 148 class random_access_index_loader:
 149   private random_access_index_loader_base<Allocator>
 150 {
 151   typedef random_access_index_loader_base<Allocator> super;
 152   typedef typename super::node_impl_pointer          node_impl_pointer;
 153   typedef typename super::ptr_array                  ptr_array;
 154
 155 public:
 156   random_access_index_loader(const Allocator& al_,ptr_array& ptrs_):
 157     super(al_,ptrs_)
 158   {}
 159
 160   void rearrange(Node* position_,Node *x)
 161   {
 162     super::rearrange(
 163       position_?position_->impl():node_impl_pointer(0),x->impl());
 164   }
 165 };
 166
 167 } /* namespace multi_index::detail */
 168
 169 } /* namespace multi_index */
 170
 171 } /* namespace boost */
 172
 173 #endif