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