1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2013.
5 //
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // See http://www.boost.org/libs/intrusive for documentation.
11 //
12 /////////////////////////////////////////////////////////////////////////////
13 #include <boost/container/vector.hpp> //vector
14 #include <algorithm> //sort, random_shuffle
15 #include <boost/intrusive/detail/config_begin.hpp>
16 #include "common_functors.hpp"
17 #include <boost/intrusive/options.hpp>
18 #include <boost/intrusive/detail/mpl.hpp>
19 #include <boost/detail/lightweight_test.hpp>
20 #include "test_macros.hpp"
21 #include "test_container.hpp"
22
23 namespace boost{
24 namespace intrusive{
25 namespace test{
26
27 BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(has_splay, splay)
28
29 BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(has_rebalance, rebalance)
30
31 BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(has_insert_before, insert_before)
32
33 BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(is_treap, priority_comp)
34
35 template<class ValueTraits, class ContainerDefiner>
36 struct test_generic_assoc
37 {
38 typedef typename ValueTraits::value_type value_type;
39 typedef typename ValueTraits::pointer pointer;
40 typedef typename ValueTraits::const_pointer const_pointer;
41 typedef typename ValueContainer< value_type >::type value_cont_type;
42 typedef typename pointer_traits<pointer>::reference reference;
43 typedef typename pointer_traits
44 <const_pointer>::reference const_reference;
45
46 static void test_all(value_cont_type&);
47 static void test_clone(value_cont_type&);
48 static void test_insert_erase_burst();
49 static void test_container_from_end(value_cont_type&, detail::true_type);
test_container_from_endboost::intrusive::test::test_generic_assoc50 static void test_container_from_end(value_cont_type&, detail::false_type) {}
51 static void test_splay_up(value_cont_type&, detail::true_type);
test_splay_upboost::intrusive::test::test_generic_assoc52 static void test_splay_up(value_cont_type&, detail::false_type) {}
53 static void test_splay_down(value_cont_type&, detail::true_type);
test_splay_downboost::intrusive::test::test_generic_assoc54 static void test_splay_down(value_cont_type&, detail::false_type) {}
55 static void test_rebalance(value_cont_type&, detail::true_type);
test_rebalanceboost::intrusive::test::test_generic_assoc56 static void test_rebalance(value_cont_type&, detail::false_type) {}
57 static void test_insert_before(value_cont_type&, detail::true_type);
test_insert_beforeboost::intrusive::test::test_generic_assoc58 static void test_insert_before(value_cont_type&, detail::false_type) {}
59 static void test_container_from_iterator(value_cont_type&, detail::true_type);
test_container_from_iteratorboost::intrusive::test::test_generic_assoc60 static void test_container_from_iterator(value_cont_type&, detail::false_type) {}
61 };
62
63 template<class ValueTraits, class ContainerDefiner>
64 void test_generic_assoc<ValueTraits, ContainerDefiner>::
test_container_from_iterator(value_cont_type & values,detail::true_type)65 test_container_from_iterator(value_cont_type& values, detail::true_type)
66 {
67 typedef typename ContainerDefiner::template container
68 <>::type assoc_type;
69 assoc_type testset(values.begin(), values.end());
70 typedef typename assoc_type::iterator it_type;
71 typedef typename assoc_type::const_iterator cit_type;
72 typedef typename assoc_type::size_type sz_type;
73 sz_type sz = testset.size();
74 for(it_type b(testset.begin()), e(testset.end()); b != e; ++b)
75 {
76 assoc_type &s = assoc_type::container_from_iterator(b);
77 const assoc_type &cs = assoc_type::container_from_iterator(cit_type(b));
78 BOOST_TEST(&s == &cs);
79 BOOST_TEST(&s == &testset);
80 s.erase(b);
81 BOOST_TEST(testset.size() == (sz-1));
82 s.insert(*b);
83 BOOST_TEST(testset.size() == sz);
84 }
85 }
86
87 template<class ValueTraits, class ContainerDefiner>
test_insert_erase_burst()88 void test_generic_assoc<ValueTraits, ContainerDefiner>::test_insert_erase_burst()
89 {
90 //value_cont_type values;
91 const std::size_t MaxValues = 200;
92 value_cont_type values(MaxValues);
93 for(std::size_t i = 0; i != MaxValues; ++i){
94 (&values[i])->value_ = i;
95 }
96
97 typedef typename ContainerDefiner::template container
98 <>::type assoc_type;
99 typedef typename assoc_type::iterator iterator;
100
101 { //Ordered insertion + erasure
102 assoc_type testset (values.begin(), values.begin() + values.size());
103 TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
104 testset.check();
105 iterator it(testset.begin()), itend(testset.end());
106 for(std::size_t i = 0; it != itend; ++i){
107 BOOST_TEST(&*it == &values[i]);
108 it = testset.erase(it);
109 testset.check();
110 }
111 BOOST_TEST(testset.empty());
112 }
113
114 { //Now random insertions + erasure
115 assoc_type testset;
116 typedef typename value_cont_type::iterator vec_iterator;
117 boost::container::vector<vec_iterator> it_vector;
118 //Random insertion
119 for(vec_iterator it(values.begin()), itend(values.end())
120 ; it != itend
121 ; ++it){
122 it_vector.push_back(it);
123 }
124 for(std::size_t i = 0; i != MaxValues; ++i){
125 testset.insert(*it_vector[i]);
126 testset.check();
127 }
128 TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
129 //Random erasure
130 std::random_shuffle(it_vector.begin(), it_vector.end());
131 for(std::size_t i = 0; i != MaxValues; ++i){
132 testset.erase(testset.iterator_to(*it_vector[i]));
133 testset.check();
134 }
135 BOOST_TEST(testset.empty());
136 }
137 }
138
139 template<class ValueTraits, class ContainerDefiner>
test_all(value_cont_type & values)140 void test_generic_assoc<ValueTraits, ContainerDefiner>::test_all(value_cont_type& values)
141 {
142 typedef typename ContainerDefiner::template container
143 <>::type assoc_type;
144 test_clone(values);
145 test_container_from_end(values, detail::bool_< assoc_type::has_container_from_iterator >());
146 test_splay_up(values, detail::bool_< has_splay< assoc_type >::value >());
147 test_splay_down(values, detail::bool_< has_splay< assoc_type >::value >());
148 test_rebalance(values, detail::bool_< has_rebalance< assoc_type >::value >());
149 test_insert_before(values, detail::bool_< has_insert_before< assoc_type >::value >());
150 test_insert_erase_burst();
151 test_container_from_iterator(values, detail::bool_< assoc_type::has_container_from_iterator >());
152 }
153
154 template<class ValueTraits, class ContainerDefiner>
155 void test_generic_assoc<ValueTraits, ContainerDefiner>
test_clone(value_cont_type & values)156 ::test_clone(value_cont_type& values)
157 {
158 {
159 typedef typename ContainerDefiner::template container
160 <>::type assoc_type;
161 assoc_type testset1 (values.begin(), values.begin() + values.size());
162 assoc_type testset2;
163
164 typedef typename assoc_type::size_type size_type;
165 size_type const testset1_oldsize = testset1.size();
166 testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
167 BOOST_TEST (testset1.size() == testset1_oldsize);
168 BOOST_TEST (testset2 == testset1);
169 testset2.clear_and_dispose(test::delete_disposer<value_type>());
170 BOOST_TEST (testset2.empty());
171
172 //Now test move clone
173 testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>());
174 BOOST_TEST (testset2 == testset1);
175 testset2.clear_and_dispose(test::delete_disposer<value_type>());
176 BOOST_TEST (testset2.empty());
177 }
178 }
179
180 template<class ValueTraits, class ContainerDefiner>
181 void test_generic_assoc<ValueTraits, ContainerDefiner>
test_container_from_end(value_cont_type & values,detail::true_type)182 ::test_container_from_end(value_cont_type& values, detail::true_type)
183 {
184 typedef typename ContainerDefiner::template container
185 <>::type assoc_type;
186 assoc_type testset (values.begin(), values.begin() + values.size());
187 BOOST_TEST (testset == assoc_type::container_from_end_iterator(testset.end()));
188 BOOST_TEST (testset == assoc_type::container_from_end_iterator(testset.cend()));
189 }
190
191 template<class ValueTraits, class ContainerDefiner>
test_splay_up(value_cont_type & values,detail::true_type)192 void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_up
193 (value_cont_type& values, detail::true_type)
194 {
195 typedef typename ContainerDefiner::template container
196 <>::type assoc_type;
197
198 typedef typename assoc_type::iterator iterator;
199 typedef value_cont_type orig_set_t;
200 std::size_t num_values;
201 orig_set_t original_testset;
202 {
203 assoc_type testset (values.begin(), values.end());
204 num_values = testset.size();
205 original_testset = value_cont_type(testset.begin(), testset.end());
206 }
207
208 for(std::size_t i = 0; i != num_values; ++i){
209 assoc_type testset (values.begin(), values.end());
210 {
211 iterator it = testset.begin();
212 for(std::size_t j = 0; j != i; ++j, ++it){}
213 testset.splay_up(it);
214 }
215 BOOST_TEST (testset.size() == num_values);
216 iterator it = testset.begin();
217 for( typename orig_set_t::const_iterator origit = original_testset.begin()
218 , origitend = original_testset.end()
219 ; origit != origitend
220 ; ++origit, ++it){
221 BOOST_TEST(*origit == *it);
222 }
223 }
224 }
225
226 template<class ValueTraits, class ContainerDefiner>
test_splay_down(value_cont_type & values,detail::true_type)227 void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_down
228 (value_cont_type& values, detail::true_type)
229 {
230 typedef typename ContainerDefiner::template container
231 <>::type assoc_type;
232
233 typedef typename assoc_type::iterator iterator;
234 typedef value_cont_type orig_set_t;
235 std::size_t num_values;
236 orig_set_t original_testset;
237 {
238 assoc_type testset (values.begin(), values.end());
239 num_values = testset.size();
240 original_testset = value_cont_type(testset.begin(), testset.end());
241 }
242
243 for(std::size_t i = 0; i != num_values; ++i){
244 assoc_type testset (values.begin(), values.end());
245 BOOST_TEST(testset.size() == num_values);
246 {
247 iterator it = testset.begin();
248 for(std::size_t j = 0; j != i; ++j, ++it){}
249 BOOST_TEST(*it == *testset.splay_down(*it));
250 }
251 BOOST_TEST (testset.size() == num_values);
252 iterator it = testset.begin();
253 for( typename orig_set_t::const_iterator origit = original_testset.begin()
254 , origitend = original_testset.end()
255 ; origit != origitend
256 ; ++origit, ++it){
257 BOOST_TEST(*origit == *it);
258 }
259 }
260 }
261
262 template<class ValueTraits, class ContainerDefiner>
test_rebalance(value_cont_type & values,detail::true_type)263 void test_generic_assoc<ValueTraits, ContainerDefiner>::test_rebalance
264 (value_cont_type& values, detail::true_type)
265 {
266 typedef typename ContainerDefiner::template container
267 <>::type assoc_type;
268 typedef value_cont_type orig_set_t;
269 orig_set_t original_testset;
270 {
271 assoc_type testset (values.begin(), values.end());
272 original_testset.assign(testset.begin(), testset.end());
273 }
274 {
275 assoc_type testset(values.begin(), values.end());
276 testset.rebalance();
277 TEST_INTRUSIVE_SEQUENCE_EXPECTED(original_testset, testset.begin());
278 }
279
280 {
281 std::size_t numdata;
282 {
283 assoc_type testset(values.begin(), values.end());
284 numdata = testset.size();
285 }
286
287 for(int i = 0; i != (int)numdata; ++i){
288 assoc_type testset(values.begin(), values.end());
289 typename assoc_type::iterator it = testset.begin();
290 for(int j = 0; j != i; ++j) ++it;
291 testset.rebalance_subtree(it);
292 TEST_INTRUSIVE_SEQUENCE_EXPECTED(original_testset, testset.begin());
293 }
294 }
295 }
296
297 template<class ValueTraits, class ContainerDefiner>
test_insert_before(value_cont_type & values,detail::true_type)298 void test_generic_assoc<ValueTraits, ContainerDefiner>::test_insert_before
299 (value_cont_type& values, detail::true_type)
300 {
301 typedef typename ContainerDefiner::template container
302 <>::type assoc_type;
303 {
304 assoc_type testset;
305 typedef typename value_cont_type::iterator vec_iterator;
306 for(vec_iterator it(values.begin()), itend(values.end())
307 ; it != itend
308 ; ++it){
309 testset.push_back(*it);
310 }
311 BOOST_TEST(testset.size() == values.size());
312 TEST_INTRUSIVE_SEQUENCE_EXPECTED(values, testset.begin());
313 }
314 {
315 assoc_type testset;
316 typedef typename value_cont_type::iterator vec_iterator;
317
318 for(vec_iterator it(--values.end()); true; --it){
319 testset.push_front(*it);
320 if(it == values.begin()){
321 break;
322 }
323 }
324 BOOST_TEST(testset.size() == values.size());
325 TEST_INTRUSIVE_SEQUENCE_EXPECTED(values, testset.begin());
326 }
327 {
328 assoc_type testset;
329 typedef typename value_cont_type::iterator vec_iterator;
330 typename assoc_type::iterator it_pos =
331 testset.insert_before(testset.end(), *values.rbegin());
332 testset.insert_before(testset.begin(), *values.begin());
333 for(vec_iterator it(++values.begin()), itend(--values.end())
334 ; it != itend
335 ; ++it){
336 testset.insert_before(it_pos, *it);
337 }
338 BOOST_TEST(testset.size() == values.size());
339 TEST_INTRUSIVE_SEQUENCE_EXPECTED(values, testset.begin());
340 }
341 }
342
343 }}} //namespace boost::intrusive::test
344
345 #include <boost/intrusive/detail/config_end.hpp>
346