multi_index/detail/rnd_index_loader.hpp

0001 /* Copyright 2003-2022 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_LOADER_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_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/core/noncopyable.hpp>
0019 #include <boost/multi_index/detail/allocator_traits.hpp>
0020 #include <boost/multi_index/detail/auto_space.hpp>
0021 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
0022
0023 namespace boost{
0024
0025 namespace multi_index{
0026
0027 namespace detail{
0028
0029 /* This class implements a serialization rearranger for random access
0030  * indices. In order to achieve O(n) performance, the following strategy
0031  * is followed: the nodes of the index are handled as if in a bidirectional
0032  * list, where the next pointers are stored in the original
0033  * random_access_index_ptr_array and the prev pointers are stored in
0034  * an auxiliary array. Rearranging of nodes in such a bidirectional list
0035  * is constant time. Once all the arrangements are performed (on destruction
0036  * time) the list is traversed in reverse order and
0037  * pointers are swapped and set accordingly so that they recover its
0038  * original semantics ( *(node->up())==node ) while retaining the
0039  * new order.
0040  */
0041
0042 template<typename Allocator>
0043 class random_access_index_loader_base:private noncopyable
0044 {
0045 protected:
0046   typedef random_access_index_node_impl<
0047     typename rebind_alloc_for<
0048       Allocator,
0049       char
0050     >::type
0051   >                                                 node_impl_type;
0052   typedef typename node_impl_type::pointer          node_impl_pointer;
0053   typedef random_access_index_ptr_array<Allocator>  ptr_array;
0054
0055   random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_):
0056     al(al_),
0057     ptrs(ptrs_),
0058     header(*ptrs.end()),
0059     prev_spc(al,0),
0060     preprocessed(false)
0061   {}
0062
0063   ~random_access_index_loader_base()
0064   {
0065     if(preprocessed)
0066     {
0067       node_impl_pointer n=header;
0068       next(n)=n;
0069
0070       for(size_type i=ptrs.size();i--;){
0071         n=prev(n);
0072         size_type d=position(n);
0073         if(d!=i){
0074           node_impl_pointer m=prev(next_at(i));
0075           std::swap(m->up(),n->up());
0076           next_at(d)=next_at(i);
0077           std::swap(prev_at(d),prev_at(i));
0078         }
0079         next(n)=n;
0080       }
0081     }
0082   }
0083
0084   void rearrange(node_impl_pointer position_,node_impl_pointer x)
0085   {
0086     preprocess(); /* only incur this penalty if rearrange() is ever called */
0087     if(position_==node_impl_pointer(0))position_=header;
0088     next(prev(x))=next(x);
0089     prev(next(x))=prev(x);
0090     prev(x)=position_;
0091     next(x)=next(position_);
0092     next(prev(x))=prev(next(x))=x;
0093   }
0094
0095 private:
0096   typedef allocator_traits<Allocator>      alloc_traits;
0097   typedef typename alloc_traits::size_type size_type;
0098
0099   void preprocess()
0100   {
0101     if(!preprocessed){
0102       /* get space for the auxiliary prev array */
0103       auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1);
0104       prev_spc.swap(tmp);
0105
0106       /* prev_spc elements point to the prev nodes */
0107       std::rotate_copy(
0108         &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data());
0109
0110       /* ptrs elements point to the next nodes */
0111       std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1);
0112
0113       preprocessed=true;
0114     }
0115   }
0116
0117   size_type position(node_impl_pointer x)const
0118   {
0119     return (size_type)(x->up()-ptrs.begin());
0120   }
0121
0122   node_impl_pointer& next_at(size_type n)const
0123   {
0124     return *ptrs.at(n);
0125   }
0126
0127   node_impl_pointer& prev_at(size_type n)const
0128   {
0129     return *(prev_spc.data()+n);
0130   }
0131
0132   node_impl_pointer& next(node_impl_pointer x)const
0133   {
0134     return *(x->up());
0135   }
0136
0137   node_impl_pointer& prev(node_impl_pointer x)const
0138   {
0139     return prev_at(position(x));
0140   }
0141
0142   Allocator                               al;
0143   ptr_array&                              ptrs;
0144   node_impl_pointer                       header;
0145   auto_space<node_impl_pointer,Allocator> prev_spc;
0146   bool                                    preprocessed;
0147 };
0148
0149 template<typename Node,typename Allocator>
0150 class random_access_index_loader:
0151   private random_access_index_loader_base<Allocator>
0152 {
0153   typedef random_access_index_loader_base<Allocator> super;
0154   typedef typename super::node_impl_pointer          node_impl_pointer;
0155   typedef typename super::ptr_array                  ptr_array;
0156
0157 public:
0158   random_access_index_loader(const Allocator& al_,ptr_array& ptrs_):
0159     super(al_,ptrs_)
0160   {}
0161
0162   void rearrange(Node* position_,Node *x)
0163   {
0164     super::rearrange(
0165       position_?position_->impl():node_impl_pointer(0),x->impl());
0166   }
0167 };
0168
0169 } /* namespace multi_index::detail */
0170
0171 } /* namespace multi_index */
0172
0173 } /* namespace boost */
0174
0175 #endif