]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* Copyright 2003-2013 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/detail/allocator_utilities.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 | #include <cstddef> | |
23 | ||
24 | namespace boost{ | |
25 | ||
26 | namespace multi_index{ | |
27 | ||
28 | namespace detail{ | |
29 | ||
30 | /* This class implements a serialization rearranger for random access | |
31 | * indices. In order to achieve O(n) performance, the following strategy | |
32 | * is followed: the nodes of the index are handled as if in a bidirectional | |
33 | * list, where the next pointers are stored in the original | |
34 | * random_access_index_ptr_array and the prev pointers are stored in | |
35 | * an auxiliary array. Rearranging of nodes in such a bidirectional list | |
36 | * is constant time. Once all the arrangements are performed (on destruction | |
37 | * time) the list is traversed in reverse order and | |
38 | * pointers are swapped and set accordingly so that they recover its | |
39 | * original semantics ( *(node->up())==node ) while retaining the | |
40 | * new order. | |
41 | */ | |
42 | ||
43 | template<typename Allocator> | |
44 | class random_access_index_loader_base:private noncopyable | |
45 | { | |
46 | protected: | |
47 | typedef random_access_index_node_impl< | |
48 | typename boost::detail::allocator::rebind_to< | |
49 | Allocator, | |
50 | char | |
51 | >::type | |
52 | > node_impl_type; | |
53 | typedef typename node_impl_type::pointer node_impl_pointer; | |
54 | typedef random_access_index_ptr_array<Allocator> ptr_array; | |
55 | ||
56 | random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_): | |
57 | al(al_), | |
58 | ptrs(ptrs_), | |
59 | header(*ptrs.end()), | |
60 | prev_spc(al,0), | |
61 | preprocessed(false) | |
62 | {} | |
63 | ||
64 | ~random_access_index_loader_base() | |
65 | { | |
66 | if(preprocessed) | |
67 | { | |
68 | node_impl_pointer n=header; | |
69 | next(n)=n; | |
70 | ||
71 | for(std::size_t i=ptrs.size();i--;){ | |
72 | n=prev(n); | |
73 | std::size_t d=position(n); | |
74 | if(d!=i){ | |
75 | node_impl_pointer m=prev(next_at(i)); | |
76 | std::swap(m->up(),n->up()); | |
77 | next_at(d)=next_at(i); | |
78 | std::swap(prev_at(d),prev_at(i)); | |
79 | } | |
80 | next(n)=n; | |
81 | } | |
82 | } | |
83 | } | |
84 | ||
85 | void rearrange(node_impl_pointer position_,node_impl_pointer x) | |
86 | { | |
87 | preprocess(); /* only incur this penalty if rearrange() is ever called */ | |
88 | if(position_==node_impl_pointer(0))position_=header; | |
89 | next(prev(x))=next(x); | |
90 | prev(next(x))=prev(x); | |
91 | prev(x)=position_; | |
92 | next(x)=next(position_); | |
93 | next(prev(x))=prev(next(x))=x; | |
94 | } | |
95 | ||
96 | private: | |
97 | void preprocess() | |
98 | { | |
99 | if(!preprocessed){ | |
100 | /* get space for the auxiliary prev array */ | |
101 | auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1); | |
102 | prev_spc.swap(tmp); | |
103 | ||
104 | /* prev_spc elements point to the prev nodes */ | |
105 | std::rotate_copy( | |
106 | &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data()); | |
107 | ||
108 | /* ptrs elements point to the next nodes */ | |
109 | std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1); | |
110 | ||
111 | preprocessed=true; | |
112 | } | |
113 | } | |
114 | ||
115 | std::size_t position(node_impl_pointer x)const | |
116 | { | |
117 | return (std::size_t)(x->up()-ptrs.begin()); | |
118 | } | |
119 | ||
120 | node_impl_pointer& next_at(std::size_t n)const | |
121 | { | |
122 | return *ptrs.at(n); | |
123 | } | |
124 | ||
125 | node_impl_pointer& prev_at(std::size_t n)const | |
126 | { | |
127 | return *(prev_spc.data()+n); | |
128 | } | |
129 | ||
130 | node_impl_pointer& next(node_impl_pointer x)const | |
131 | { | |
132 | return *(x->up()); | |
133 | } | |
134 | ||
135 | node_impl_pointer& prev(node_impl_pointer x)const | |
136 | { | |
137 | return prev_at(position(x)); | |
138 | } | |
139 | ||
140 | Allocator al; | |
141 | ptr_array& ptrs; | |
142 | node_impl_pointer header; | |
143 | auto_space<node_impl_pointer,Allocator> prev_spc; | |
144 | bool preprocessed; | |
145 | }; | |
146 | ||
147 | template<typename Node,typename Allocator> | |
148 | class random_access_index_loader: | |
149 | private random_access_index_loader_base<Allocator> | |
150 | { | |
151 | typedef random_access_index_loader_base<Allocator> super; | |
152 | typedef typename super::node_impl_pointer node_impl_pointer; | |
153 | typedef typename super::ptr_array ptr_array; | |
154 | ||
155 | public: | |
156 | random_access_index_loader(const Allocator& al_,ptr_array& ptrs_): | |
157 | super(al_,ptrs_) | |
158 | {} | |
159 | ||
160 | void rearrange(Node* position_,Node *x) | |
161 | { | |
162 | super::rearrange( | |
163 | position_?position_->impl():node_impl_pointer(0),x->impl()); | |
164 | } | |
165 | }; | |
166 | ||
167 | } /* namespace multi_index::detail */ | |
168 | ||
169 | } /* namespace multi_index */ | |
170 | ||
171 | } /* namespace boost */ | |
172 | ||
173 | #endif |