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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
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>
27 namespace multi_index{
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
44 template<typename Allocator>
45 class random_access_index_loader_base:private noncopyable
48 typedef typename prevent_eti<
50 random_access_index_node_impl<
51 typename boost::detail::allocator::rebind_to<
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;
60 random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_):
68 ~random_access_index_loader_base()
72 node_impl_pointer n=header;
75 for(std::size_t i=ptrs.size();i--;){
77 std::size_t d=position(n);
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));
89 void rearrange(node_impl_pointer position,node_impl_pointer x)
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);
96 next(x)=next(position);
97 next(prev(x))=prev(next(x))=x;
104 /* get space for the auxiliary prev array */
105 auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1);
108 /* prev_spc elements point to the prev nodes */
110 &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data());
112 /* ptrs elements point to the next nodes */
113 std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1);
119 std::size_t position(node_impl_pointer x)const
121 return (std::size_t)(x->up()-ptrs.begin());
124 node_impl_pointer& next_at(std::size_t n)const
129 node_impl_pointer& prev_at(std::size_t n)const
131 return *(prev_spc.data()+n);
134 node_impl_pointer& next(node_impl_pointer x)const
139 node_impl_pointer& prev(node_impl_pointer x)const
141 return prev_at(position(x));
146 node_impl_pointer header;
147 auto_space<node_impl_pointer,Allocator> prev_spc;
151 template<typename Node,typename Allocator>
152 class random_access_index_loader:
153 private random_access_index_loader_base<Allocator>
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;
160 random_access_index_loader(const Allocator& al_,ptr_array& ptrs_):
164 void rearrange(Node* position,Node *x)
166 super::rearrange(position?position->impl():node_impl_pointer(0),x->impl());
170 } /* namespace multi_index::detail */
172 } /* namespace multi_index */
174 } /* namespace boost */