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/intrusive/list.hpp>
14 #include <boost/intrusive/pointer_traits.hpp>
15 #include "itestvalue.hpp"
16 #include "bptr_value.hpp"
17 #include "smart_ptr.hpp"
18 #include "common_functors.hpp"
19 #include <vector>
20 #include <boost/detail/lightweight_test.hpp>
21 #include "test_macros.hpp"
22 #include "test_container.hpp"
23 #include <typeinfo>
24
25 using namespace boost::intrusive;
26
27 template<class VoidPointer>
28 struct hooks
29 {
30 typedef list_base_hook<void_pointer<VoidPointer> > base_hook_type;
31 typedef list_base_hook< link_mode<auto_unlink>
32 , void_pointer<VoidPointer>, tag<void> > auto_base_hook_type;
33 typedef list_member_hook<void_pointer<VoidPointer>, tag<void> > member_hook_type;
34 typedef list_member_hook< link_mode<auto_unlink>
35 , void_pointer<VoidPointer> > auto_member_hook_type;
36 typedef nonhook_node_member< list_node_traits< VoidPointer >,
37 circular_list_algorithms > nonhook_node_member_type;
38 };
39
40
41 template < typename ListType, typename ValueContainer >
42 struct test_list
43 {
44 typedef ListType list_type;
45 typedef typename list_type::value_traits value_traits;
46 typedef typename value_traits::value_type value_type;
47 typedef typename list_type::node_algorithms node_algorithms;
48
49 static void test_all(ValueContainer&);
50 static void test_front_back(ValueContainer&);
51 static void test_sort(ValueContainer&);
52 static void test_merge(ValueContainer&);
53 static void test_remove_unique(ValueContainer&);
54 static void test_insert(ValueContainer&);
55 static void test_shift(ValueContainer&);
56 static void test_swap(ValueContainer&);
57 static void test_clone(ValueContainer&);
58 static void test_container_from_end(ValueContainer&, detail::true_type);
test_container_from_endtest_list59 static void test_container_from_end(ValueContainer&, detail::false_type) {}
60 };
61
62 template < typename ListType, typename ValueContainer >
test_all(ValueContainer & values)63 void test_list< ListType, ValueContainer >::test_all(ValueContainer& values)
64 {
65 {
66 list_type list(values.begin(), values.end());
67 test::test_container(list);
68 list.clear();
69 list.insert(list.end(), values.begin(), values.end());
70 test::test_sequence_container(list, values);
71 }
72 {
73 list_type list(values.begin(), values.end());
74 test::test_iterator_bidirectional(list);
75 }
76
77 test_front_back(values);
78 test_sort(values);
79 test_merge(values);
80 test_remove_unique(values);
81 test_insert(values);
82 test_shift(values);
83 test_swap(values);
84 test_clone(values);
85 test_container_from_end(values, detail::bool_< ListType::has_container_from_iterator >());
86 }
87
88 //test: push_front, pop_front, push_back, pop_back, front, back, size, empty:
89 template < class ListType, typename ValueContainer >
90 void test_list< ListType, ValueContainer >
test_front_back(ValueContainer & values)91 ::test_front_back(ValueContainer& values)
92 {
93 list_type testlist;
94 BOOST_TEST (testlist.empty());
95
96 testlist.push_back (values[0]);
97 BOOST_TEST (testlist.size() == 1);
98 BOOST_TEST (&testlist.front() == &values[0]);
99 BOOST_TEST (&testlist.back() == &values[0]);
100
101 testlist.push_front (values[1]);
102 BOOST_TEST (testlist.size() == 2);
103 BOOST_TEST (&testlist.front() == &values[1]);
104 BOOST_TEST (&testlist.back() == &values[0]);
105
106 testlist.pop_back();
107 BOOST_TEST (testlist.size() == 1);
108 const list_type &const_testlist = testlist;
109 BOOST_TEST (&const_testlist.front() == &values[1]);
110 BOOST_TEST (&const_testlist.back() == &values[1]);
111
112 testlist.pop_front();
113 BOOST_TEST (testlist.empty());
114 }
115
116 //test: constructor, iterator, reverse_iterator, sort, reverse:
117 template < class ListType, typename ValueContainer >
118 void test_list< ListType, ValueContainer >
test_sort(ValueContainer & values)119 ::test_sort(ValueContainer& values)
120 {
121 list_type testlist(values.begin(), values.end());
122
123 { int init_values [] = { 1, 2, 3, 4, 5 };
124 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.begin() ); }
125
126 testlist.sort (even_odd());
127 { int init_values [] = { 5, 3, 1, 4, 2 };
128 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.rbegin() ); }
129
130 testlist.reverse();
131 { int init_values [] = { 5, 3, 1, 4, 2 };
132 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.begin() ); }
133 }
134
135 //test: merge due to error in merge implementation:
136 template < class ListType, typename ValueContainer >
137 void test_list< ListType, ValueContainer >
test_remove_unique(ValueContainer & values)138 ::test_remove_unique (ValueContainer& values)
139 {
140 {
141 list_type list(values.begin(), values.end());
142 list.remove_if(is_even());
143 int init_values [] = { 1, 3, 5 };
144 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
145 }
146 {
147 list_type list(values.begin(), values.end());
148 list.remove_if(is_odd());
149 int init_values [] = { 2, 4 };
150 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
151 }
152 {
153 list_type list(values.begin(), values.end());
154 list.remove_and_dispose_if(is_even(), test::empty_disposer());
155 int init_values [] = { 1, 3, 5 };
156 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
157 }
158 {
159 list_type list(values.begin(), values.end());
160 list.remove_and_dispose_if(is_odd(), test::empty_disposer());
161 int init_values [] = { 2, 4 };
162 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
163 }
164 {
165 ValueContainer values2(values);
166 list_type list(values.begin(), values.end());
167 list.insert(list.end(), values2.begin(), values2.end());
168 list.sort();
169 int init_values [] = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };
170 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
171 list.unique();
172 int init_values2 [] = { 1, 2, 3, 4, 5 };
173 TEST_INTRUSIVE_SEQUENCE( init_values2, list.begin() );
174 }
175 }
176
177 //test: merge due to error in merge implementation:
178 template < class ListType, typename ValueContainer >
179 void test_list< ListType, ValueContainer >
test_merge(ValueContainer & values)180 ::test_merge (ValueContainer& values)
181 {
182 list_type testlist1, testlist2;
183 testlist1.push_front (values[0]);
184 testlist2.push_front (values[4]);
185 testlist2.push_front (values[3]);
186 testlist2.push_front (values[2]);
187 testlist1.merge (testlist2);
188
189 int init_values [] = { 1, 3, 4, 5 };
190 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() );
191 }
192
193 //test: assign, insert, const_iterator, const_reverse_iterator, erase, s_iterator_to:
194 template < class ListType, typename ValueContainer >
195 void test_list< ListType, ValueContainer >
test_insert(ValueContainer & values)196 ::test_insert(ValueContainer& values)
197 {
198 list_type testlist;
199 testlist.assign (values.begin() + 2, values.begin() + 5);
200
201 const list_type& const_testlist = testlist;
202 { int init_values [] = { 3, 4, 5 };
203 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
204
205 typename list_type::iterator i = ++testlist.begin();
206 BOOST_TEST (i->value_ == 4);
207
208 {
209 typename list_type::const_iterator ci = typename list_type::iterator();
210 (void)ci;
211 }
212
213 testlist.insert (i, values[0]);
214 { int init_values [] = { 5, 4, 1, 3 };
215 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.rbegin() ); }
216
217 i = testlist.iterator_to (values[4]);
218 BOOST_TEST (&*i == &values[4]);
219
220 i = list_type::s_iterator_to (values[4]);
221 BOOST_TEST (&*i == &values[4]);
222
223 typename list_type::const_iterator ic;
224 ic = testlist.iterator_to (static_cast< typename list_type::const_reference >(values[4]));
225 BOOST_TEST (&*ic == &values[4]);
226
227 ic = list_type::s_iterator_to (static_cast< typename list_type::const_reference >(values[4]));
228 BOOST_TEST (&*ic == &values[4]);
229
230 i = testlist.erase (i);
231 BOOST_TEST (i == testlist.end());
232
233 { int init_values [] = { 3, 1, 4 };
234 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
235 }
236
237 template < class ListType, typename ValueContainer >
238 void test_list< ListType, ValueContainer >
test_shift(ValueContainer & values)239 ::test_shift(ValueContainer& values)
240 {
241 list_type testlist;
242 const int num_values = (int)values.size();
243 std::vector<int> expected_values(num_values);
244
245 for(int s = 1; s <= num_values; ++s){
246 expected_values.resize(s);
247 //Shift forward all possible positions 3 times
248 for(int i = 0; i < s*3; ++i){
249 testlist.insert(testlist.begin(), values.begin(), values.begin() + s);
250 testlist.shift_forward(i);
251 for(int j = 0; j < s; ++j){
252 expected_values[(j + s - i%s) % s] = (j + 1);
253 }
254 TEST_INTRUSIVE_SEQUENCE_EXPECTED(expected_values, testlist.begin());
255 testlist.clear();
256 }
257
258 //Shift backwards all possible positions
259 for(int i = 0; i < s*3; ++i){
260 testlist.insert(testlist.begin(), values.begin(), values.begin() + s);
261 testlist.shift_backwards(i);
262 for(int j = 0; j < s; ++j){
263 expected_values[(j + i) % s] = (j + 1);
264 }
265 TEST_INTRUSIVE_SEQUENCE_EXPECTED(expected_values, testlist.begin());
266 testlist.clear();
267 }
268 }
269 }
270
271 //test: insert (seq-version), swap, splice, erase (seq-version):
272 template < class ListType, typename ValueContainer >
273 void test_list< ListType, ValueContainer >
test_swap(ValueContainer & values)274 ::test_swap(ValueContainer& values)
275 {
276 {
277 list_type testlist1 (values.begin(), values.begin() + 2);
278 list_type testlist2;
279 testlist2.insert (testlist2.end(), values.begin() + 2, values.begin() + 5);
280 testlist1.swap (testlist2);
281
282 { int init_values [] = { 3, 4, 5 };
283 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
284 { int init_values [] = { 1, 2 };
285 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
286
287 testlist2.splice (++testlist2.begin(), testlist1);
288 { int init_values [] = { 1, 3, 4, 5, 2 };
289 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
290
291 BOOST_TEST (testlist1.empty());
292
293 testlist1.splice (testlist1.end(), testlist2, ++(++testlist2.begin()));
294 { int init_values [] = { 4 };
295 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
296
297 { int init_values [] = { 1, 3, 5, 2 };
298 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
299
300 testlist1.splice (testlist1.end(), testlist2,
301 testlist2.begin(), ----testlist2.end());
302 { int init_values [] = { 4, 1, 3 };
303 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
304 { int init_values [] = { 5, 2 };
305 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
306
307 testlist1.erase (testlist1.iterator_to(values[0]), testlist1.end());
308 BOOST_TEST (testlist1.size() == 1);
309 BOOST_TEST (&testlist1.front() == &values[3]);
310 }
311 {
312 list_type testlist1 (values.begin(), values.begin() + 2);
313 list_type testlist2 (values.begin() + 3, values.begin() + 5);
314
315 swap_nodes< node_algorithms >(values[0], values[2]);
316 { int init_values [] = { 3, 2 };
317 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
318
319 swap_nodes< node_algorithms >(values[2], values[4]);
320 { int init_values [] = { 5, 2 };
321 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
322 { int init_values [] = { 4, 3 };
323 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
324 }
325 {
326 list_type testlist1 (values.begin(), values.begin() + 1);
327
328 { int init_values [] = { 1 };
329 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
330
331 swap_nodes< node_algorithms >(values[1], values[2]);
332
333 { int init_values [] = { 1 };
334 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
335
336 swap_nodes< node_algorithms >(values[0], values[2]);
337
338 { int init_values [] = { 3 };
339 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
340
341 swap_nodes< node_algorithms >(values[0], values[2]);
342
343 { int init_values [] = { 1 };
344 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
345 }
346 }
347
348 template < class ListType, typename ValueContainer >
349 void test_list< ListType, ValueContainer >
test_container_from_end(ValueContainer & values,detail::true_type)350 ::test_container_from_end(ValueContainer& values, detail::true_type)
351 {
352 list_type testlist1 (values.begin(), values.begin() + values.size());
353 BOOST_TEST (testlist1 == list_type::container_from_end_iterator(testlist1.end()));
354 BOOST_TEST (testlist1 == list_type::container_from_end_iterator(testlist1.cend()));
355 }
356
357 template < class ListType, typename ValueContainer >
358 void test_list< ListType, ValueContainer >
test_clone(ValueContainer & values)359 ::test_clone(ValueContainer& values)
360 {
361 list_type testlist1 (values.begin(), values.begin() + values.size());
362 list_type testlist2;
363
364 testlist2.clone_from(testlist1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
365 BOOST_TEST (testlist2 == testlist1);
366 testlist2.clear_and_dispose(test::delete_disposer<value_type>());
367 BOOST_TEST (testlist2.empty());
368 }
369
370 template < typename ValueTraits, bool ConstantTimeSize, bool Default_Holder, typename ValueContainer >
371 struct make_and_test_list
372 : test_list< list< typename ValueTraits::value_type,
373 value_traits< ValueTraits >,
374 size_type< std::size_t >,
375 constant_time_size< ConstantTimeSize >
376 >,
377 ValueContainer
378 >
379 {};
380
381 template < typename ValueTraits, bool ConstantTimeSize, typename ValueContainer >
382 struct make_and_test_list< ValueTraits, ConstantTimeSize, false, ValueContainer >
383 : test_list< list< typename ValueTraits::value_type,
384 value_traits< ValueTraits >,
385 size_type< std::size_t >,
386 constant_time_size< ConstantTimeSize >,
387 header_holder_type< heap_node_holder< typename ValueTraits::pointer > >
388 >,
389 ValueContainer
390 >
391 {};
392
393
394 template < class VoidPointer, bool ConstantTimeSize, bool Default_Holder >
395 class test_main_template
396 {
397 public:
operator ()()398 int operator()()
399 {
400 typedef testvalue< hooks<VoidPointer> > value_type;
401 std::vector<value_type> data (5);
402 for (int i = 0; i < 5; ++i)
403 data[i].value_ = i + 1;
404
405 make_and_test_list < typename detail::get_base_value_traits <
406 value_type,
407 typename hooks<VoidPointer>::base_hook_type
408 >::type,
409 ConstantTimeSize,
410 Default_Holder,
411 std::vector< value_type >
412 >::test_all(data);
413 make_and_test_list < typename detail::get_member_value_traits <
414 member_hook< value_type, typename hooks<VoidPointer>::member_hook_type, &value_type::node_>
415 >::type,
416 ConstantTimeSize,
417 Default_Holder,
418 std::vector< value_type >
419 >::test_all(data);
420 make_and_test_list< nonhook_node_member_value_traits <
421 value_type,
422 typename hooks<VoidPointer>::nonhook_node_member_type,
423 &value_type::nhn_member_,
424 safe_link
425 >,
426 ConstantTimeSize,
427 Default_Holder,
428 std::vector< value_type >
429 >::test_all(data);
430
431 return 0;
432 }
433 };
434
435 template < class VoidPointer, bool Default_Holder >
436 class test_main_template< VoidPointer, false, Default_Holder >
437 {
438 public:
operator ()()439 int operator()()
440 {
441 typedef testvalue< hooks<VoidPointer> > value_type;
442 std::vector<value_type> data (5);
443 for (int i = 0; i < 5; ++i)
444 data[i].value_ = i + 1;
445
446 make_and_test_list < typename detail::get_base_value_traits <
447 value_type,
448 typename hooks<VoidPointer>::auto_base_hook_type
449 >::type,
450 false,
451 Default_Holder,
452 std::vector< value_type >
453 >::test_all(data);
454 make_and_test_list < typename detail::get_member_value_traits <
455 member_hook< value_type, typename hooks<VoidPointer>::auto_member_hook_type, &value_type::auto_node_>
456 >::type,
457 false,
458 Default_Holder,
459 std::vector< value_type >
460 >::test_all(data);
461
462 return 0;
463 }
464 };
465
466 template < bool ConstantTimeSize >
467 struct test_main_template_bptr
468 {
operator ()test_main_template_bptr469 int operator()()
470 {
471 typedef BPtr_Value value_type;
472 typedef BPtr_Value_Traits< List_BPtr_Node_Traits > list_value_traits;
473 typedef typename list_value_traits::node_ptr node_ptr;
474 typedef bounded_allocator< value_type > allocator_type;
475
476 bounded_allocator_scope<allocator_type> bounded_scope; (void)bounded_scope;
477
478 allocator_type allocator;
479
480 {
481 bounded_reference_cont< value_type > ref_cont;
482 for (int i = 0; i < 5; ++i)
483 {
484 node_ptr tmp = allocator.allocate(1);
485 new (tmp.raw()) value_type(i + 1);
486 ref_cont.push_back(*tmp);
487 }
488
489 test_list < list < value_type,
490 value_traits< list_value_traits >,
491 size_type< std::size_t >,
492 constant_time_size< ConstantTimeSize >,
493 header_holder_type< bounded_pointer_holder< value_type > >
494 >,
495 bounded_reference_cont< value_type >
496 >::test_all(ref_cont);
497 }
498
499 return 0;
500 }
501 };
502
main()503 int main()
504 {
505 // test (plain/smart pointers) x (nonconst/const size) x (void node allocator)
506 test_main_template<void*, false, true>()();
507 test_main_template<boost::intrusive::smart_ptr<void>, false, true>()();
508 test_main_template<void*, true, true>()();
509 test_main_template<boost::intrusive::smart_ptr<void>, true, true>()();
510 // test (bounded pointers) x ((nonconst/const size) x (special node allocator)
511 test_main_template_bptr< true >()();
512 test_main_template_bptr< false >()();
513
514 return boost::report_errors();
515 }
516