Chris@101: /* Copyright 2003-2013 Joaquin M Lopez Munoz. Chris@16: * Distributed under the Boost Software License, Version 1.0. Chris@16: * (See accompanying file LICENSE_1_0.txt or copy at Chris@16: * http://www.boost.org/LICENSE_1_0.txt) Chris@16: * Chris@16: * See http://www.boost.org/libs/multi_index for library home page. Chris@16: */ Chris@16: Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP Chris@16: #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP Chris@16: Chris@101: #if defined(_MSC_VER) Chris@16: #pragma once Chris@16: #endif Chris@16: Chris@16: #include /* keep it first to prevent nasty warns in MSVC */ Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: namespace boost{ Chris@16: Chris@16: namespace multi_index{ Chris@16: Chris@16: namespace detail{ Chris@16: Chris@16: /* This class implements a serialization rearranger for random access Chris@16: * indices. In order to achieve O(n) performance, the following strategy Chris@16: * is followed: the nodes of the index are handled as if in a bidirectional Chris@16: * list, where the next pointers are stored in the original Chris@16: * random_access_index_ptr_array and the prev pointers are stored in Chris@16: * an auxiliary array. Rearranging of nodes in such a bidirectional list Chris@16: * is constant time. Once all the arrangements are performed (on destruction Chris@16: * time) the list is traversed in reverse order and Chris@16: * pointers are swapped and set accordingly so that they recover its Chris@16: * original semantics ( *(node->up())==node ) while retaining the Chris@16: * new order. Chris@16: */ Chris@16: Chris@16: template Chris@16: class random_access_index_loader_base:private noncopyable Chris@16: { Chris@16: protected: Chris@101: typedef random_access_index_node_impl< Chris@101: typename boost::detail::allocator::rebind_to< Chris@101: Allocator, Chris@101: char Chris@101: >::type Chris@101: > node_impl_type; Chris@16: typedef typename node_impl_type::pointer node_impl_pointer; Chris@16: typedef random_access_index_ptr_array ptr_array; Chris@16: Chris@16: random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_): Chris@16: al(al_), Chris@16: ptrs(ptrs_), Chris@16: header(*ptrs.end()), Chris@16: prev_spc(al,0), Chris@16: preprocessed(false) Chris@16: {} Chris@16: Chris@16: ~random_access_index_loader_base() Chris@16: { Chris@16: if(preprocessed) Chris@16: { Chris@16: node_impl_pointer n=header; Chris@16: next(n)=n; Chris@16: Chris@16: for(std::size_t i=ptrs.size();i--;){ Chris@16: n=prev(n); Chris@16: std::size_t d=position(n); Chris@16: if(d!=i){ Chris@16: node_impl_pointer m=prev(next_at(i)); Chris@16: std::swap(m->up(),n->up()); Chris@16: next_at(d)=next_at(i); Chris@16: std::swap(prev_at(d),prev_at(i)); Chris@16: } Chris@16: next(n)=n; Chris@16: } Chris@16: } Chris@16: } Chris@16: Chris@101: void rearrange(node_impl_pointer position_,node_impl_pointer x) Chris@16: { Chris@16: preprocess(); /* only incur this penalty if rearrange() is ever called */ Chris@101: if(position_==node_impl_pointer(0))position_=header; Chris@16: next(prev(x))=next(x); Chris@16: prev(next(x))=prev(x); Chris@101: prev(x)=position_; Chris@101: next(x)=next(position_); Chris@16: next(prev(x))=prev(next(x))=x; Chris@16: } Chris@16: Chris@16: private: Chris@16: void preprocess() Chris@16: { Chris@16: if(!preprocessed){ Chris@16: /* get space for the auxiliary prev array */ Chris@16: auto_space tmp(al,ptrs.size()+1); Chris@16: prev_spc.swap(tmp); Chris@16: Chris@16: /* prev_spc elements point to the prev nodes */ Chris@16: std::rotate_copy( Chris@16: &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data()); Chris@16: Chris@16: /* ptrs elements point to the next nodes */ Chris@16: std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1); Chris@16: Chris@16: preprocessed=true; Chris@16: } Chris@16: } Chris@16: Chris@16: std::size_t position(node_impl_pointer x)const Chris@16: { Chris@16: return (std::size_t)(x->up()-ptrs.begin()); Chris@16: } Chris@16: Chris@16: node_impl_pointer& next_at(std::size_t n)const Chris@16: { Chris@16: return *ptrs.at(n); Chris@16: } Chris@16: Chris@16: node_impl_pointer& prev_at(std::size_t n)const Chris@16: { Chris@16: return *(prev_spc.data()+n); Chris@16: } Chris@16: Chris@16: node_impl_pointer& next(node_impl_pointer x)const Chris@16: { Chris@16: return *(x->up()); Chris@16: } Chris@16: Chris@16: node_impl_pointer& prev(node_impl_pointer x)const Chris@16: { Chris@16: return prev_at(position(x)); Chris@16: } Chris@16: Chris@16: Allocator al; Chris@16: ptr_array& ptrs; Chris@16: node_impl_pointer header; Chris@16: auto_space prev_spc; Chris@16: bool preprocessed; Chris@16: }; Chris@16: Chris@16: template Chris@16: class random_access_index_loader: Chris@16: private random_access_index_loader_base Chris@16: { Chris@16: typedef random_access_index_loader_base super; Chris@16: typedef typename super::node_impl_pointer node_impl_pointer; Chris@16: typedef typename super::ptr_array ptr_array; Chris@16: Chris@16: public: Chris@16: random_access_index_loader(const Allocator& al_,ptr_array& ptrs_): Chris@16: super(al_,ptrs_) Chris@16: {} Chris@16: Chris@101: void rearrange(Node* position_,Node *x) Chris@16: { Chris@101: super::rearrange( Chris@101: position_?position_->impl():node_impl_pointer(0),x->impl()); Chris@16: } Chris@16: }; Chris@16: Chris@16: } /* namespace multi_index::detail */ Chris@16: Chris@16: } /* namespace multi_index */ Chris@16: Chris@16: } /* namespace boost */ Chris@16: Chris@16: #endif