Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
1 /* Copyright 2003-2006 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/multi_index/detail/auto_space.hpp>
19 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
20 #include <boost/noncopyable.hpp>
25 namespace multi_index{
29 /* This class implements a serialization rearranger for random access
30 * indices. In order to achieve O(n) performance, the following strategy
31 * is followed: the nodes of the index are handled as if in a bidirectional
32 * list, where the next pointers are stored in the original
33 * random_access_index_ptr_array and the prev pointers are stored in
34 * an auxiliary array. Rearranging of nodes in such a bidirectional list
35 * is constant time. Once all the arrangements are performed (on destruction
36 * time) the list is traversed in reverse order and
37 * pointers are swapped and set accordingly so that they recover its
38 * original semantics ( *(node->up())==node ) while retaining the
42 template<typename Allocator>
43 class random_access_index_loader_base:private noncopyable
46 typedef random_access_index_node_impl node_type;
47 typedef random_access_index_ptr_array<Allocator> ptr_array_type;
49 random_access_index_loader_base(const Allocator& al_,ptr_array_type& ptrs_):
57 ~random_access_index_loader_base()
64 for(std::size_t i=ptrs.size();i--;){
66 std::size_t d=position(n);
68 node_type* m=prev(next_at(i));
69 std::swap(m->up(),n->up());
70 next_at(d)=next_at(i);
71 std::swap(prev_at(d),prev_at(i));
78 void rearrange(node_type* position,node_type *x)
80 preprocess(); /* only incur this penalty if rearrange() is ever called */
81 if(!position)position=header;
82 next(prev(x))=next(x);
83 prev(next(x))=prev(x);
85 next(x)=next(position);
86 next(prev(x))=prev(next(x))=x;
93 /* get space for the auxiliary prev array */
94 auto_space<node_type*,Allocator> tmp(al,ptrs.size()+1);
97 /* prev_spc elements point to the prev nodes */
98 std::rotate_copy(ptrs.begin(),ptrs.end(),ptrs.end()+1,prev_spc.data());
100 /* ptrs elements point to the next nodes */
101 std::rotate(ptrs.begin(),ptrs.begin()+1,ptrs.end()+1);
107 std::size_t position(node_type* x)const
109 return (std::size_t)(x->up()-ptrs.begin());
112 node_type*& next_at(std::size_t n)const
117 node_type*& prev_at(std::size_t n)const
119 return prev_spc.data()[n];
122 node_type*& next(node_type* x)const
127 node_type*& prev(node_type* x)const
129 return prev_at(position(x));
133 ptr_array_type& ptrs;
135 auto_space<node_type*,Allocator> prev_spc;
139 template<typename Node,typename Allocator>
140 class random_access_index_loader:
141 private random_access_index_loader_base<Allocator>
143 typedef random_access_index_loader_base<Allocator> super;
144 typedef typename super::ptr_array_type ptr_array_type;
147 random_access_index_loader(const Allocator& al_,ptr_array_type& ptrs_):
151 void rearrange(Node* position,Node *x)
153 super::rearrange(position?position->impl():0,x->impl());
157 } /* namespace multi_index::detail */
159 } /* namespace multi_index */
161 } /* namespace boost */