1 /* Copyright 2003-2018 Joaquin M Lopez Munoz.
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)
5  *
6  * See http://www.boost.org/libs/multi_index for library home page.
7  */
8 
9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP
11 
12 #if defined(_MSC_VER)
13 #pragma once
14 #endif
15 
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
17 #include <algorithm>
18 #include <boost/multi_index/detail/allocator_traits.hpp>
19 #include <boost/multi_index/detail/auto_space.hpp>
20 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
21 #include <boost/noncopyable.hpp>
22 
23 namespace boost{
24 
25 namespace multi_index{
26 
27 namespace detail{
28 
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
39  * new order.
40  */
41 
42 template<typename Allocator>
43 class random_access_index_loader_base:private noncopyable
44 {
45 protected:
46   typedef random_access_index_node_impl<
47     typename rebind_alloc_for<
48       Allocator,
49       char
50     >::type
51   >                                                 node_impl_type;
52   typedef typename node_impl_type::pointer          node_impl_pointer;
53   typedef random_access_index_ptr_array<Allocator>  ptr_array;
54 
random_access_index_loader_base(const Allocator & al_,ptr_array & ptrs_)55   random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_):
56     al(al_),
57     ptrs(ptrs_),
58     header(*ptrs.end()),
59     prev_spc(al,0),
60     preprocessed(false)
61   {}
62 
~random_access_index_loader_base()63   ~random_access_index_loader_base()
64   {
65     if(preprocessed)
66     {
67       node_impl_pointer n=header;
68       next(n)=n;
69 
70       for(size_type i=ptrs.size();i--;){
71         n=prev(n);
72         size_type d=position(n);
73         if(d!=i){
74           node_impl_pointer m=prev(next_at(i));
75           std::swap(m->up(),n->up());
76           next_at(d)=next_at(i);
77           std::swap(prev_at(d),prev_at(i));
78         }
79         next(n)=n;
80       }
81     }
82   }
83 
rearrange(node_impl_pointer position_,node_impl_pointer x)84   void rearrange(node_impl_pointer position_,node_impl_pointer x)
85   {
86     preprocess(); /* only incur this penalty if rearrange() is ever called */
87     if(position_==node_impl_pointer(0))position_=header;
88     next(prev(x))=next(x);
89     prev(next(x))=prev(x);
90     prev(x)=position_;
91     next(x)=next(position_);
92     next(prev(x))=prev(next(x))=x;
93   }
94 
95 private:
96   typedef allocator_traits<Allocator>      alloc_traits;
97   typedef typename alloc_traits::size_type size_type;
98 
preprocess()99   void preprocess()
100   {
101     if(!preprocessed){
102       /* get space for the auxiliary prev array */
103       auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1);
104       prev_spc.swap(tmp);
105 
106       /* prev_spc elements point to the prev nodes */
107       std::rotate_copy(
108         &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data());
109 
110       /* ptrs elements point to the next nodes */
111       std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1);
112 
113       preprocessed=true;
114     }
115   }
116 
position(node_impl_pointer x) const117   size_type position(node_impl_pointer x)const
118   {
119     return (size_type)(x->up()-ptrs.begin());
120   }
121 
next_at(size_type n) const122   node_impl_pointer& next_at(size_type n)const
123   {
124     return *ptrs.at(n);
125   }
126 
prev_at(size_type n) const127   node_impl_pointer& prev_at(size_type n)const
128   {
129     return *(prev_spc.data()+n);
130   }
131 
next(node_impl_pointer x) const132   node_impl_pointer& next(node_impl_pointer x)const
133   {
134     return *(x->up());
135   }
136 
prev(node_impl_pointer x) const137   node_impl_pointer& prev(node_impl_pointer x)const
138   {
139     return prev_at(position(x));
140   }
141 
142   Allocator                               al;
143   ptr_array&                              ptrs;
144   node_impl_pointer                       header;
145   auto_space<node_impl_pointer,Allocator> prev_spc;
146   bool                                    preprocessed;
147 };
148 
149 template<typename Node,typename Allocator>
150 class random_access_index_loader:
151   private random_access_index_loader_base<Allocator>
152 {
153   typedef random_access_index_loader_base<Allocator> super;
154   typedef typename super::node_impl_pointer          node_impl_pointer;
155   typedef typename super::ptr_array                  ptr_array;
156 
157 public:
random_access_index_loader(const Allocator & al_,ptr_array & ptrs_)158   random_access_index_loader(const Allocator& al_,ptr_array& ptrs_):
159     super(al_,ptrs_)
160   {}
161 
rearrange(Node * position_,Node * x)162   void rearrange(Node* position_,Node *x)
163   {
164     super::rearrange(
165       position_?position_->impl():node_impl_pointer(0),x->impl());
166   }
167 };
168 
169 } /* namespace multi_index::detail */
170 
171 } /* namespace multi_index */
172 
173 } /* namespace boost */
174 
175 #endif
176