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