williamr@2
|
1 |
/* Copyright 2003-2006 Joaquín M López Muñoz.
|
williamr@2
|
2 |
* Distributed under the Boost Software License, Version 1.0.
|
williamr@2
|
3 |
* (See accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
4 |
* http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
5 |
*
|
williamr@2
|
6 |
* See http://www.boost.org/libs/multi_index for library home page.
|
williamr@2
|
7 |
*/
|
williamr@2
|
8 |
|
williamr@2
|
9 |
#ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP
|
williamr@2
|
10 |
#define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP
|
williamr@2
|
11 |
|
williamr@2
|
12 |
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
williamr@2
|
13 |
#pragma once
|
williamr@2
|
14 |
#endif
|
williamr@2
|
15 |
|
williamr@2
|
16 |
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
williamr@2
|
17 |
#include <algorithm>
|
williamr@2
|
18 |
#include <boost/multi_index/detail/auto_space.hpp>
|
williamr@2
|
19 |
#include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
|
williamr@2
|
20 |
#include <boost/noncopyable.hpp>
|
williamr@2
|
21 |
#include <cstddef>
|
williamr@2
|
22 |
|
williamr@2
|
23 |
namespace boost{
|
williamr@2
|
24 |
|
williamr@2
|
25 |
namespace multi_index{
|
williamr@2
|
26 |
|
williamr@2
|
27 |
namespace detail{
|
williamr@2
|
28 |
|
williamr@2
|
29 |
/* This class implements a serialization rearranger for random access
|
williamr@2
|
30 |
* indices. In order to achieve O(n) performance, the following strategy
|
williamr@2
|
31 |
* is followed: the nodes of the index are handled as if in a bidirectional
|
williamr@2
|
32 |
* list, where the next pointers are stored in the original
|
williamr@2
|
33 |
* random_access_index_ptr_array and the prev pointers are stored in
|
williamr@2
|
34 |
* an auxiliary array. Rearranging of nodes in such a bidirectional list
|
williamr@2
|
35 |
* is constant time. Once all the arrangements are performed (on destruction
|
williamr@2
|
36 |
* time) the list is traversed in reverse order and
|
williamr@2
|
37 |
* pointers are swapped and set accordingly so that they recover its
|
williamr@2
|
38 |
* original semantics ( *(node->up())==node ) while retaining the
|
williamr@2
|
39 |
* new order.
|
williamr@2
|
40 |
*/
|
williamr@2
|
41 |
|
williamr@2
|
42 |
template<typename Allocator>
|
williamr@2
|
43 |
class random_access_index_loader_base:private noncopyable
|
williamr@2
|
44 |
{
|
williamr@2
|
45 |
protected:
|
williamr@2
|
46 |
typedef random_access_index_node_impl node_type;
|
williamr@2
|
47 |
typedef random_access_index_ptr_array<Allocator> ptr_array_type;
|
williamr@2
|
48 |
|
williamr@2
|
49 |
random_access_index_loader_base(const Allocator& al_,ptr_array_type& ptrs_):
|
williamr@2
|
50 |
al(al_),
|
williamr@2
|
51 |
ptrs(ptrs_),
|
williamr@2
|
52 |
header(*ptrs.end()),
|
williamr@2
|
53 |
prev_spc(al,0),
|
williamr@2
|
54 |
preprocessed(false)
|
williamr@2
|
55 |
{}
|
williamr@2
|
56 |
|
williamr@2
|
57 |
~random_access_index_loader_base()
|
williamr@2
|
58 |
{
|
williamr@2
|
59 |
if(preprocessed)
|
williamr@2
|
60 |
{
|
williamr@2
|
61 |
node_type* n=header;
|
williamr@2
|
62 |
next(n)=n;
|
williamr@2
|
63 |
|
williamr@2
|
64 |
for(std::size_t i=ptrs.size();i--;){
|
williamr@2
|
65 |
n=prev(n);
|
williamr@2
|
66 |
std::size_t d=position(n);
|
williamr@2
|
67 |
if(d!=i){
|
williamr@2
|
68 |
node_type* m=prev(next_at(i));
|
williamr@2
|
69 |
std::swap(m->up(),n->up());
|
williamr@2
|
70 |
next_at(d)=next_at(i);
|
williamr@2
|
71 |
std::swap(prev_at(d),prev_at(i));
|
williamr@2
|
72 |
}
|
williamr@2
|
73 |
next(n)=n;
|
williamr@2
|
74 |
}
|
williamr@2
|
75 |
}
|
williamr@2
|
76 |
}
|
williamr@2
|
77 |
|
williamr@2
|
78 |
void rearrange(node_type* position,node_type *x)
|
williamr@2
|
79 |
{
|
williamr@2
|
80 |
preprocess(); /* only incur this penalty if rearrange() is ever called */
|
williamr@2
|
81 |
if(!position)position=header;
|
williamr@2
|
82 |
next(prev(x))=next(x);
|
williamr@2
|
83 |
prev(next(x))=prev(x);
|
williamr@2
|
84 |
prev(x)=position;
|
williamr@2
|
85 |
next(x)=next(position);
|
williamr@2
|
86 |
next(prev(x))=prev(next(x))=x;
|
williamr@2
|
87 |
}
|
williamr@2
|
88 |
|
williamr@2
|
89 |
private:
|
williamr@2
|
90 |
void preprocess()
|
williamr@2
|
91 |
{
|
williamr@2
|
92 |
if(!preprocessed){
|
williamr@2
|
93 |
/* get space for the auxiliary prev array */
|
williamr@2
|
94 |
auto_space<node_type*,Allocator> tmp(al,ptrs.size()+1);
|
williamr@2
|
95 |
prev_spc.swap(tmp);
|
williamr@2
|
96 |
|
williamr@2
|
97 |
/* prev_spc elements point to the prev nodes */
|
williamr@2
|
98 |
std::rotate_copy(ptrs.begin(),ptrs.end(),ptrs.end()+1,prev_spc.data());
|
williamr@2
|
99 |
|
williamr@2
|
100 |
/* ptrs elements point to the next nodes */
|
williamr@2
|
101 |
std::rotate(ptrs.begin(),ptrs.begin()+1,ptrs.end()+1);
|
williamr@2
|
102 |
|
williamr@2
|
103 |
preprocessed=true;
|
williamr@2
|
104 |
}
|
williamr@2
|
105 |
}
|
williamr@2
|
106 |
|
williamr@2
|
107 |
std::size_t position(node_type* x)const
|
williamr@2
|
108 |
{
|
williamr@2
|
109 |
return (std::size_t)(x->up()-ptrs.begin());
|
williamr@2
|
110 |
}
|
williamr@2
|
111 |
|
williamr@2
|
112 |
node_type*& next_at(std::size_t n)const
|
williamr@2
|
113 |
{
|
williamr@2
|
114 |
return *ptrs.at(n);
|
williamr@2
|
115 |
}
|
williamr@2
|
116 |
|
williamr@2
|
117 |
node_type*& prev_at(std::size_t n)const
|
williamr@2
|
118 |
{
|
williamr@2
|
119 |
return prev_spc.data()[n];
|
williamr@2
|
120 |
}
|
williamr@2
|
121 |
|
williamr@2
|
122 |
node_type*& next(node_type* x)const
|
williamr@2
|
123 |
{
|
williamr@2
|
124 |
return *(x->up());
|
williamr@2
|
125 |
}
|
williamr@2
|
126 |
|
williamr@2
|
127 |
node_type*& prev(node_type* x)const
|
williamr@2
|
128 |
{
|
williamr@2
|
129 |
return prev_at(position(x));
|
williamr@2
|
130 |
}
|
williamr@2
|
131 |
|
williamr@2
|
132 |
Allocator al;
|
williamr@2
|
133 |
ptr_array_type& ptrs;
|
williamr@2
|
134 |
node_type* header;
|
williamr@2
|
135 |
auto_space<node_type*,Allocator> prev_spc;
|
williamr@2
|
136 |
bool preprocessed;
|
williamr@2
|
137 |
};
|
williamr@2
|
138 |
|
williamr@2
|
139 |
template<typename Node,typename Allocator>
|
williamr@2
|
140 |
class random_access_index_loader:
|
williamr@2
|
141 |
private random_access_index_loader_base<Allocator>
|
williamr@2
|
142 |
{
|
williamr@2
|
143 |
typedef random_access_index_loader_base<Allocator> super;
|
williamr@2
|
144 |
typedef typename super::ptr_array_type ptr_array_type;
|
williamr@2
|
145 |
|
williamr@2
|
146 |
public:
|
williamr@2
|
147 |
random_access_index_loader(const Allocator& al_,ptr_array_type& ptrs_):
|
williamr@2
|
148 |
super(al_,ptrs_)
|
williamr@2
|
149 |
{}
|
williamr@2
|
150 |
|
williamr@2
|
151 |
void rearrange(Node* position,Node *x)
|
williamr@2
|
152 |
{
|
williamr@2
|
153 |
super::rearrange(position?position->impl():0,x->impl());
|
williamr@2
|
154 |
}
|
williamr@2
|
155 |
};
|
williamr@2
|
156 |
|
williamr@2
|
157 |
} /* namespace multi_index::detail */
|
williamr@2
|
158 |
|
williamr@2
|
159 |
} /* namespace multi_index */
|
williamr@2
|
160 |
|
williamr@2
|
161 |
} /* namespace boost */
|
williamr@2
|
162 |
|
williamr@2
|
163 |
#endif
|