1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2013.
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)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
14 #include <boost/intrusive/slist.hpp>
15 #include <boost/intrusive/pointer_traits.hpp>
16 #include "itestvalue.hpp"
17 #include "bptr_value.hpp"
18 #include "smart_ptr.hpp"
19 #include "common_functors.hpp"
21 #include <boost/detail/lightweight_test.hpp>
22 #include "test_macros.hpp"
23 #include "test_container.hpp"
26 using namespace boost::intrusive
;
28 template<class VoidPointer
>
31 typedef slist_base_hook
<void_pointer
<VoidPointer
> > base_hook_type
;
32 typedef slist_base_hook
< link_mode
<auto_unlink
>
33 , void_pointer
<VoidPointer
>, tag
<void> > auto_base_hook_type
;
34 typedef slist_member_hook
<void_pointer
<VoidPointer
>, tag
<void> > member_hook_type
;
35 typedef slist_member_hook
< link_mode
<auto_unlink
>
36 , void_pointer
<VoidPointer
> > auto_member_hook_type
;
37 typedef nonhook_node_member
< slist_node_traits
< VoidPointer
>,
38 circular_slist_algorithms
39 > nonhook_node_member_type
;
42 template < typename ListType
, typename ValueContainer
>
45 typedef ListType list_type
;
46 typedef typename
list_type::value_traits value_traits
;
47 typedef typename
value_traits::value_type value_type
;
48 typedef typename
list_type::node_algorithms node_algorithms
;
50 static void test_all(ValueContainer
&);
51 static void test_front(ValueContainer
&);
52 static void test_back(ValueContainer
&, detail::true_type
);
53 static void test_back(ValueContainer
&, detail::false_type
) {}
54 static void test_sort(ValueContainer
&);
55 static void test_merge(ValueContainer
&);
56 static void test_remove_unique(ValueContainer
&);
57 static void test_insert(ValueContainer
&);
58 static void test_shift(ValueContainer
&);
59 static void test_swap(ValueContainer
&);
60 static void test_slow_insert(ValueContainer
&);
61 static void test_clone(ValueContainer
&);
62 static void test_container_from_end(ValueContainer
&, detail::true_type
);
63 static void test_container_from_end(ValueContainer
&, detail::false_type
) {}
66 template < typename ListType
, typename ValueContainer
>
67 void test_slist
< ListType
, ValueContainer
>
68 ::test_all (ValueContainer
& values
)
71 list_type
list(values
.begin(), values
.end());
72 test::test_container(list
);
74 list
.insert(list
.end(), values
.begin(), values
.end());
75 test::test_sequence_container(list
, values
);
78 list_type
list(values
.begin(), values
.end());
79 test::test_iterator_forward(list
);
82 test_back(values
, detail::bool_
< list_type::cache_last
>());
85 test_remove_unique(values
);
88 test_slow_insert (values
);
91 test_container_from_end(values
, detail::bool_
< !list_type::linear
&& list_type::has_container_from_iterator
>());
94 //test: push_front, pop_front, front, size, empty:
95 template < typename ListType
, typename ValueContainer
>
96 void test_slist
< ListType
, ValueContainer
>
97 ::test_front(ValueContainer
& values
)
100 BOOST_TEST (testlist
.empty());
102 testlist
.push_front (values
[0]);
103 BOOST_TEST (testlist
.size() == 1);
104 BOOST_TEST (&testlist
.front() == &values
[0]);
106 testlist
.push_front (values
[1]);
107 BOOST_TEST (testlist
.size() == 2);
108 BOOST_TEST (&testlist
.front() == &values
[1]);
110 testlist
.pop_front();
111 BOOST_TEST (testlist
.size() == 1);
112 BOOST_TEST (&testlist
.front() == &values
[0]);
114 testlist
.pop_front();
115 BOOST_TEST (testlist
.empty());
118 //test: push_front, pop_front, front, size, empty:
119 template < typename ListType
, typename ValueContainer
>
120 void test_slist
< ListType
, ValueContainer
>
121 ::test_back(ValueContainer
& values
, detail::true_type
)
124 BOOST_TEST (testlist
.empty());
126 testlist
.push_back (values
[0]);
127 BOOST_TEST (testlist
.size() == 1);
128 BOOST_TEST (&testlist
.front() == &values
[0]);
129 BOOST_TEST (&testlist
.back() == &values
[0]);
130 testlist
.push_back(values
[1]);
131 BOOST_TEST(*testlist
.previous(testlist
.end()) == values
[1]);
132 BOOST_TEST (&testlist
.front() == &values
[0]);
133 BOOST_TEST (&testlist
.back() == &values
[1]);
136 //test: merge due to error in merge implementation:
137 template < typename ListType
, typename ValueContainer
>
138 void test_slist
< ListType
, ValueContainer
>
139 ::test_merge (ValueContainer
& values
)
141 list_type testlist1
, testlist2
;
142 testlist1
.push_front (values
[0]);
143 testlist2
.push_front (values
[4]);
144 testlist2
.push_front (values
[3]);
145 testlist2
.push_front (values
[2]);
146 testlist1
.merge (testlist2
);
148 int init_values
[] = { 1, 3, 4, 5 };
149 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() );
152 //test: merge due to error in merge implementation:
153 template < typename ListType
, typename ValueContainer
>
154 void test_slist
< ListType
, ValueContainer
>
155 ::test_remove_unique (ValueContainer
& values
)
158 list_type
list(values
.begin(), values
.end());
159 list
.remove_if(is_even());
160 int init_values
[] = { 1, 3, 5 };
161 TEST_INTRUSIVE_SEQUENCE( init_values
, list
.begin() );
164 list_type
list(values
.begin(), values
.end());
165 list
.remove_if(is_odd());
166 int init_values
[] = { 2, 4 };
167 TEST_INTRUSIVE_SEQUENCE( init_values
, list
.begin() );
170 list_type
list(values
.begin(), values
.end());
171 list
.remove_and_dispose_if(is_even(), test::empty_disposer());
172 int init_values
[] = { 1, 3, 5 };
173 TEST_INTRUSIVE_SEQUENCE( init_values
, list
.begin() );
176 list_type
list(values
.begin(), values
.end());
177 list
.remove_and_dispose_if(is_odd(), test::empty_disposer());
178 int init_values
[] = { 2, 4 };
179 TEST_INTRUSIVE_SEQUENCE( init_values
, list
.begin() );
182 ValueContainer
values2(values
);
183 list_type
list(values
.begin(), values
.end());
184 list
.insert_after(list
.before_begin(), values2
.begin(), values2
.end());
186 int init_values
[] = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };
187 TEST_INTRUSIVE_SEQUENCE( init_values
, list
.begin() );
189 int init_values2
[] = { 1, 2, 3, 4, 5 };
190 TEST_INTRUSIVE_SEQUENCE( init_values2
, list
.begin() );
194 //test: constructor, iterator, sort, reverse:
195 template < typename ListType
, typename ValueContainer
>
196 void test_slist
< ListType
, ValueContainer
>
197 ::test_sort(ValueContainer
& values
)
199 list_type
testlist (values
.begin(), values
.end());
201 { int init_values
[] = { 1, 2, 3, 4, 5 };
202 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist
.begin() ); }
204 testlist
.sort (even_odd());
205 { int init_values
[] = { 2, 4, 1, 3, 5 };
206 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist
.begin() ); }
209 { int init_values
[] = { 5, 3, 1, 4, 2 };
210 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist
.begin() ); }
213 //test: assign, insert_after, const_iterator, erase_after, s_iterator_to, previous:
214 template < typename ListType
, typename ValueContainer
>
215 void test_slist
< ListType
, ValueContainer
>
216 ::test_insert(ValueContainer
& values
)
219 testlist
.assign (values
.begin() + 2, values
.begin() + 5);
221 const list_type
& const_testlist
= testlist
;
222 { int init_values
[] = { 3, 4, 5 };
223 TEST_INTRUSIVE_SEQUENCE( init_values
, const_testlist
.begin() ); }
225 typename
list_type::iterator i
= ++testlist
.begin();
226 BOOST_TEST (i
->value_
== 4);
228 testlist
.insert_after (i
, values
[0]);
229 { int init_values
[] = { 3, 4, 1, 5 };
230 TEST_INTRUSIVE_SEQUENCE( init_values
, const_testlist
.begin() ); }
232 i
= testlist
.iterator_to (values
[4]);
233 BOOST_TEST (&*i
== &values
[4]);
234 i
= list_type::s_iterator_to (values
[4]);
235 BOOST_TEST (&*i
== &values
[4]);
237 typename
list_type::const_iterator ic
;
238 ic
= testlist
.iterator_to (static_cast< typename
list_type::const_reference
>(values
[4]));
239 BOOST_TEST (&*ic
== &values
[4]);
240 ic
= list_type::s_iterator_to (static_cast< typename
list_type::const_reference
>(values
[4]));
241 BOOST_TEST (&*ic
== &values
[4]);
243 i
= testlist
.previous (i
);
244 BOOST_TEST (&*i
== &values
[0]);
246 testlist
.erase_after (i
);
247 BOOST_TEST (&*i
== &values
[0]);
248 { int init_values
[] = { 3, 4, 1 };
249 TEST_INTRUSIVE_SEQUENCE( init_values
, const_testlist
.begin() ); }
252 //test: insert, const_iterator, erase, siterator_to:
253 template < typename ListType
, typename ValueContainer
>
254 void test_slist
< ListType
, ValueContainer
>
255 ::test_slow_insert (ValueContainer
& values
)
258 testlist
.push_front (values
[4]);
259 testlist
.insert (testlist
.begin(), values
.begin() + 2, values
.begin() + 4);
261 const list_type
& const_testlist
= testlist
;
262 { int init_values
[] = { 3, 4, 5 };
263 TEST_INTRUSIVE_SEQUENCE( init_values
, const_testlist
.begin() ); }
265 typename
list_type::iterator i
= ++testlist
.begin();
266 BOOST_TEST (i
->value_
== 4);
268 testlist
.insert (i
, values
[0]);
269 { int init_values
[] = { 3, 1, 4, 5 };
270 TEST_INTRUSIVE_SEQUENCE( init_values
, const_testlist
.begin() ); }
272 i
= testlist
.iterator_to (values
[4]);
273 BOOST_TEST (&*i
== &values
[4]);
275 i
= list_type::s_iterator_to (values
[4]);
276 BOOST_TEST (&*i
== &values
[4]);
278 i
= testlist
.erase (i
);
279 BOOST_TEST (i
== testlist
.end());
281 { int init_values
[] = { 3, 1, 4 };
282 TEST_INTRUSIVE_SEQUENCE( init_values
, const_testlist
.begin() ); }
284 testlist
.erase (++testlist
.begin(), testlist
.end());
285 BOOST_TEST (testlist
.size() == 1);
286 BOOST_TEST (testlist
.begin()->value_
== 3);
289 template < typename ListType
, typename ValueContainer
>
290 void test_slist
< ListType
, ValueContainer
>
291 ::test_shift(ValueContainer
& values
)
294 const int num_values
= (int)values
.size();
295 std::vector
<int> expected_values(num_values
);
297 //Shift forward all possible positions 3 times
298 for(int s
= 1; s
<= num_values
; ++s
){
299 expected_values
.resize(s
);
300 for(int i
= 0; i
< s
*3; ++i
){
301 testlist
.insert_after(testlist
.before_begin(), values
.begin(), values
.begin() + s
);
302 testlist
.shift_forward(i
);
303 for(int j
= 0; j
< s
; ++j
){
304 expected_values
[(j
+ s
- i
%s
) % s
] = (j
+ 1);
307 TEST_INTRUSIVE_SEQUENCE_EXPECTED(expected_values
, testlist
.begin())
311 //Shift backwards all possible positions
312 for(int i
= 0; i
< s
*3; ++i
){
313 testlist
.insert_after(testlist
.before_begin(), values
.begin(), values
.begin() + s
);
314 testlist
.shift_backwards(i
);
315 for(int j
= 0; j
< s
; ++j
){
316 expected_values
[(j
+ i
) % s
] = (j
+ 1);
319 TEST_INTRUSIVE_SEQUENCE_EXPECTED(expected_values
, testlist
.begin())
325 //test: insert_after (seq-version), swap, splice_after:
326 template < typename ListType
, typename ValueContainer
>
327 void test_slist
< ListType
, ValueContainer
>
328 ::test_swap(ValueContainer
& values
)
331 list_type
testlist1 (values
.begin(), values
.begin() + 2);
333 testlist2
.insert_after (testlist2
.before_begin(), values
.begin() + 2, values
.begin() + 5);
334 testlist1
.swap(testlist2
);
335 { int init_values
[] = { 3, 4, 5 };
336 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
337 { int init_values
[] = { 1, 2 };
338 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist2
.begin() ); }
339 testlist2
.splice_after (testlist2
.begin(), testlist1
);
340 { int init_values
[] = { 1, 3, 4, 5, 2 };
341 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist2
.begin() ); }
342 BOOST_TEST (testlist1
.empty());
344 testlist1
.splice_after (testlist1
.before_begin(), testlist2
, ++testlist2
.begin());
345 { int init_values
[] = { 4 };
346 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
347 { int init_values
[] = { 1, 3, 5, 2 };
348 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist2
.begin() ); }
350 testlist1
.splice_after (testlist1
.begin(), testlist2
,
351 testlist2
.before_begin(), ++++testlist2
.begin());
352 { int init_values
[] = { 4, 1, 3, 5 };
353 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
354 { int init_values
[] = { 2 };
355 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist2
.begin() ); }
357 { //Now test swap when testlist2 is empty
358 list_type
testlist1 (values
.begin(), values
.begin() + 2);
360 testlist1
.swap(testlist2
);
361 BOOST_TEST (testlist1
.empty());
362 { int init_values
[] = { 1, 2 };
363 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist2
.begin() ); }
365 { //Now test swap when testlist1 is empty
366 list_type
testlist2 (values
.begin(), values
.begin() + 2);
368 testlist1
.swap(testlist2
);
369 BOOST_TEST (testlist2
.empty());
370 { int init_values
[] = { 1, 2 };
371 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
373 { //Now test when both are empty
374 list_type testlist1
, testlist2
;
375 testlist2
.swap(testlist1
);
376 BOOST_TEST (testlist1
.empty() && testlist2
.empty());
379 if(!list_type::linear
)
381 list_type
testlist1 (values
.begin(), values
.begin() + 2);
382 list_type
testlist2 (values
.begin() + 3, values
.begin() + 5);
384 swap_nodes
< node_algorithms
>(values
[0], values
[2]);
385 { int init_values
[] = { 3, 2 };
386 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
388 swap_nodes
< node_algorithms
>(values
[2], values
[4]);
389 { int init_values
[] = { 5, 2 };
390 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
391 { int init_values
[] = { 4, 3 };
392 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist2
.begin() ); }
394 if(!list_type::linear
)
396 list_type
testlist1 (values
.begin(), values
.begin()+1);
397 if(testlist1
.size() != 1){
400 { int init_values
[] = { 1 };
401 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
403 swap_nodes
< node_algorithms
>(values
[1], values
[2]);
405 BOOST_TEST(testlist1
.size() == 1);
406 BOOST_TEST(!(&values
[1])->is_linked());
407 BOOST_TEST(!(&values
[2])->is_linked());
408 { int init_values
[] = { 1 };
409 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
411 swap_nodes
< node_algorithms
>(values
[0], values
[2]);
412 BOOST_TEST(testlist1
.size() == 1);
413 BOOST_TEST((&values
[2])->is_linked());
414 BOOST_TEST(!(&values
[0])->is_linked());
415 { int init_values
[] = { 3 };
416 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
418 swap_nodes
< node_algorithms
>(values
[0], values
[2]);
419 BOOST_TEST(testlist1
.size() == 1);
420 BOOST_TEST(!(&values
[2])->is_linked());
421 BOOST_TEST((&values
[0])->is_linked());
422 { int init_values
[] = { 1 };
423 TEST_INTRUSIVE_SEQUENCE( init_values
, testlist1
.begin() ); }
427 template < typename ListType
, typename ValueContainer
>
428 void test_slist
< ListType
, ValueContainer
>
429 ::test_clone(ValueContainer
& values
)
431 list_type
testlist1 (values
.begin(), values
.begin() + values
.size());
434 testlist2
.clone_from(testlist1
, test::new_cloner
<value_type
>(), test::delete_disposer
<value_type
>());
435 BOOST_TEST (testlist2
== testlist1
);
436 testlist2
.clear_and_dispose(test::delete_disposer
<value_type
>());
437 BOOST_TEST (testlist2
.empty());
440 template < typename ListType
, typename ValueContainer
>
441 void test_slist
< ListType
, ValueContainer
>
442 ::test_container_from_end(ValueContainer
& values
, detail::true_type
)
444 list_type
testlist1 (values
.begin(), values
.begin() + values
.size());
445 BOOST_TEST (testlist1
== list_type::container_from_end_iterator(testlist1
.end()));
446 BOOST_TEST (testlist1
== list_type::container_from_end_iterator(testlist1
.cend()));
449 template < typename ValueTraits
, bool ConstantTimeSize
, bool Linear
, bool CacheLast
, bool Default_Holder
, typename ValueContainer
>
450 struct make_and_test_slist
451 : test_slist
< slist
< typename
ValueTraits::value_type
,
452 value_traits
< ValueTraits
>,
453 size_type
< std::size_t >,
454 constant_time_size
< ConstantTimeSize
>,
456 cache_last
<CacheLast
>
462 template < typename ValueTraits
, bool ConstantTimeSize
, bool Linear
, bool CacheLast
, typename ValueContainer
>
463 struct make_and_test_slist
< ValueTraits
, ConstantTimeSize
, Linear
, CacheLast
, false, ValueContainer
>
464 : test_slist
< slist
< typename
ValueTraits::value_type
,
465 value_traits
< ValueTraits
>,
466 size_type
< std::size_t >,
467 constant_time_size
< ConstantTimeSize
>,
469 cache_last
<CacheLast
>,
470 header_holder_type
< heap_node_holder
< typename
ValueTraits::pointer
> >
476 template<class VoidPointer
, bool constant_time_size
, bool Default_Holder
>
477 class test_main_template
482 typedef testvalue
< hooks
<VoidPointer
> > value_type
;
483 std::vector
< value_type
> data (5);
484 for (int i
= 0; i
< 5; ++i
)
485 data
[i
].value_
= i
+ 1;
487 make_and_test_slist
< typename
detail::get_base_value_traits
489 , typename hooks
<VoidPointer
>::base_hook_type
495 , std::vector
< value_type
>
497 make_and_test_slist
< nonhook_node_member_value_traits
< value_type
,
498 typename hooks
<VoidPointer
>::nonhook_node_member_type
,
499 &value_type::nhn_member_
,
506 , std::vector
< value_type
>
510 make_and_test_slist
< typename
detail::get_member_value_traits
511 < member_hook
< value_type
512 , typename hooks
<VoidPointer
>::member_hook_type
520 , std::vector
< value_type
>
523 //Now the same but caching the last node
524 make_and_test_slist
< typename
detail::get_base_value_traits
526 , typename hooks
<VoidPointer
>::base_hook_type
532 , std::vector
< value_type
>
536 make_and_test_slist
< typename
detail::get_base_value_traits
538 , typename hooks
<VoidPointer
>::base_hook_type
544 , std::vector
< value_type
>
550 template<class VoidPointer
, bool Default_Holder
>
551 class test_main_template
<VoidPointer
, false, Default_Holder
>
556 typedef testvalue
< hooks
<VoidPointer
> > value_type
;
557 std::vector
< value_type
> data (5);
558 for (int i
= 0; i
< 5; ++i
)
559 data
[i
].value_
= i
+ 1;
561 make_and_test_slist
< typename
detail::get_base_value_traits
563 , typename hooks
<VoidPointer
>::auto_base_hook_type
569 , std::vector
< value_type
>
572 make_and_test_slist
< nonhook_node_member_value_traits
< value_type
,
573 typename hooks
<VoidPointer
>::nonhook_node_member_type
,
574 &value_type::nhn_member_
,
581 , std::vector
< value_type
>
584 make_and_test_slist
< typename
detail::get_member_value_traits
585 < member_hook
< value_type
586 , typename hooks
<VoidPointer
>::member_hook_type
594 , std::vector
< value_type
>
597 make_and_test_slist
< typename
detail::get_base_value_traits
599 , typename hooks
<VoidPointer
>::base_hook_type
605 , std::vector
< value_type
>
612 template < bool ConstantTimeSize
>
613 struct test_main_template_bptr
617 typedef BPtr_Value value_type
;
618 typedef BPtr_Value_Traits
< List_BPtr_Node_Traits
> list_value_traits
;
619 typedef typename
list_value_traits::node_ptr node_ptr
;
620 typedef bounded_allocator
< value_type
> allocator_type
;
622 bounded_allocator_scope
<allocator_type
> bounded_scope
; (void)bounded_scope
;
623 allocator_type allocator
;
626 bounded_reference_cont
< value_type
> ref_cont
;
627 for (int i
= 0; i
< 5; ++i
)
629 node_ptr tmp
= allocator
.allocate(1);
630 new (tmp
.raw()) value_type(i
+ 1);
631 ref_cont
.push_back(*tmp
);
634 test_slist
< slist
< value_type
,
635 value_traits
< list_value_traits
>,
636 size_type
< std::size_t >,
637 constant_time_size
< ConstantTimeSize
>,
638 header_holder_type
< bounded_pointer_holder
< value_type
> >
640 bounded_reference_cont
< value_type
>
641 >::test_all(ref_cont
);
647 int main(int, char* [])
649 // test (plain/smart pointers) x (nonconst/const size) x (void node allocator)
650 test_main_template
<void*, false, true>()();
651 test_main_template
<boost::intrusive::smart_ptr
<void>, false, true>()();
652 test_main_template
<void*, true, true>()();
653 test_main_template
<boost::intrusive::smart_ptr
<void>, true, true>()();
654 // test (bounded pointers) x ((nonconst/const size) x (special node allocator)
655 test_main_template_bptr
< true >()();
656 test_main_template_bptr
< false >()();
659 return boost::report_errors();