boost_ext/boost/multi_index/detail/rnd_index_loader.hpp

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