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;
30 template<class VoidPointer>
33 typedef slist_base_hook<void_pointer<VoidPointer> > base_hook_type;
34 typedef slist_base_hook< link_mode<auto_unlink>
35 , void_pointer<VoidPointer>, tag<my_tag> > auto_base_hook_type;
36 typedef slist_member_hook<void_pointer<VoidPointer>, tag<my_tag> > member_hook_type;
37 typedef slist_member_hook< link_mode<auto_unlink>
38 , void_pointer<VoidPointer> > auto_member_hook_type;
39 typedef nonhook_node_member< slist_node_traits< VoidPointer >,
40 circular_slist_algorithms
41 > nonhook_node_member_type;
44 template < typename List_Type, typename Value_Container >
47 typedef List_Type list_type;
48 typedef typename list_type::value_traits value_traits;
49 typedef typename value_traits::value_type value_type;
50 typedef typename list_type::node_algorithms node_algorithms;
52 static void test_all(Value_Container&);
53 static void test_front(Value_Container&);
54 static void test_back(Value_Container&, detail::true_type);
55 static void test_back(Value_Container&, detail::false_type) {}
56 static void test_sort(Value_Container&);
57 static void test_merge(Value_Container&);
58 static void test_remove_unique(Value_Container&);
59 static void test_insert(Value_Container&);
60 static void test_shift(Value_Container&);
61 static void test_swap(Value_Container&);
62 static void test_slow_insert(Value_Container&);
63 static void test_clone(Value_Container&);
64 static void test_container_from_end(Value_Container&, detail::true_type);
65 static void test_container_from_end(Value_Container&, detail::false_type) {}
68 template < typename List_Type, typename Value_Container >
69 void test_slist< List_Type, Value_Container >
70 ::test_all (Value_Container& values)
73 list_type list(values.begin(), values.end());
74 test::test_container(list);
76 list.insert(list.end(), values.begin(), values.end());
77 test::test_sequence_container(list, values);
80 test_back(values, detail::bool_< list_type::cache_last >());
83 test_remove_unique(values);
86 test_slow_insert (values);
89 test_container_from_end(values, detail::bool_< !list_type::linear && list_type::has_container_from_iterator >());
92 //test: push_front, pop_front, front, size, empty:
93 template < typename List_Type, typename Value_Container >
94 void test_slist< List_Type, Value_Container >
95 ::test_front(Value_Container& values)
98 BOOST_TEST (testlist.empty());
100 testlist.push_front (values[0]);
101 BOOST_TEST (testlist.size() == 1);
102 BOOST_TEST (&testlist.front() == &values[0]);
104 testlist.push_front (values[1]);
105 BOOST_TEST (testlist.size() == 2);
106 BOOST_TEST (&testlist.front() == &values[1]);
108 testlist.pop_front();
109 BOOST_TEST (testlist.size() == 1);
110 BOOST_TEST (&testlist.front() == &values[0]);
112 testlist.pop_front();
113 BOOST_TEST (testlist.empty());
116 //test: push_front, pop_front, front, size, empty:
117 template < typename List_Type, typename Value_Container >
118 void test_slist< List_Type, Value_Container >
119 ::test_back(Value_Container& values, detail::true_type)
122 BOOST_TEST (testlist.empty());
124 testlist.push_back (values[0]);
125 BOOST_TEST (testlist.size() == 1);
126 BOOST_TEST (&testlist.front() == &values[0]);
127 BOOST_TEST (&testlist.back() == &values[0]);
128 testlist.push_back(values[1]);
129 BOOST_TEST(*testlist.previous(testlist.end()) == values[1]);
130 BOOST_TEST (&testlist.front() == &values[0]);
131 BOOST_TEST (&testlist.back() == &values[1]);
134 //test: merge due to error in merge implementation:
135 template < typename List_Type, typename Value_Container >
136 void test_slist< List_Type, Value_Container >
137 ::test_merge (Value_Container& values)
139 list_type testlist1, testlist2;
140 testlist1.push_front (values[0]);
141 testlist2.push_front (values[4]);
142 testlist2.push_front (values[3]);
143 testlist2.push_front (values[2]);
144 testlist1.merge (testlist2);
146 int init_values [] = { 1, 3, 4, 5 };
147 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() );
150 //test: merge due to error in merge implementation:
151 template < typename List_Type, typename Value_Container >
152 void test_slist< List_Type, Value_Container >
153 ::test_remove_unique (Value_Container& values)
156 list_type list(values.begin(), values.end());
157 list.remove_if(is_even());
158 int init_values [] = { 1, 3, 5 };
159 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
162 list_type list(values.begin(), values.end());
163 list.remove_if(is_odd());
164 int init_values [] = { 2, 4 };
165 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
168 list_type list(values.begin(), values.end());
169 list.remove_and_dispose_if(is_even(), test::empty_disposer());
170 int init_values [] = { 1, 3, 5 };
171 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
174 list_type list(values.begin(), values.end());
175 list.remove_and_dispose_if(is_odd(), test::empty_disposer());
176 int init_values [] = { 2, 4 };
177 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
180 Value_Container values2(values);
181 list_type list(values.begin(), values.end());
182 list.insert_after(list.before_begin(), values2.begin(), values2.end());
184 int init_values [] = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };
185 TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
187 int init_values2 [] = { 1, 2, 3, 4, 5 };
188 TEST_INTRUSIVE_SEQUENCE( init_values2, list.begin() );
192 //test: constructor, iterator, sort, reverse:
193 template < typename List_Type, typename Value_Container >
194 void test_slist< List_Type, Value_Container >
195 ::test_sort(Value_Container& values)
197 list_type testlist (values.begin(), values.end());
199 { int init_values [] = { 1, 2, 3, 4, 5 };
200 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.begin() ); }
202 testlist.sort (even_odd());
203 { int init_values [] = { 2, 4, 1, 3, 5 };
204 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.begin() ); }
207 { int init_values [] = { 5, 3, 1, 4, 2 };
208 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.begin() ); }
211 //test: assign, insert_after, const_iterator, erase_after, s_iterator_to, previous:
212 template < typename List_Type, typename Value_Container >
213 void test_slist< List_Type, Value_Container >
214 ::test_insert(Value_Container& values)
217 testlist.assign (values.begin() + 2, values.begin() + 5);
219 const list_type& const_testlist = testlist;
220 { int init_values [] = { 3, 4, 5 };
221 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
223 typename list_type::iterator i = ++testlist.begin();
224 BOOST_TEST (i->value_ == 4);
226 testlist.insert_after (i, values[0]);
227 { int init_values [] = { 3, 4, 1, 5 };
228 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
230 i = testlist.iterator_to (values[4]);
231 BOOST_TEST (&*i == &values[4]);
232 i = list_type::s_iterator_to (values[4]);
233 BOOST_TEST (&*i == &values[4]);
235 typename list_type::const_iterator ic;
236 ic = testlist.iterator_to (static_cast< typename list_type::const_reference >(values[4]));
237 BOOST_TEST (&*ic == &values[4]);
238 ic = list_type::s_iterator_to (static_cast< typename list_type::const_reference >(values[4]));
239 BOOST_TEST (&*ic == &values[4]);
241 i = testlist.previous (i);
242 BOOST_TEST (&*i == &values[0]);
244 testlist.erase_after (i);
245 BOOST_TEST (&*i == &values[0]);
246 { int init_values [] = { 3, 4, 1 };
247 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
250 //test: insert, const_iterator, erase, siterator_to:
251 template < typename List_Type, typename Value_Container >
252 void test_slist< List_Type, Value_Container >
253 ::test_slow_insert (Value_Container& values)
256 testlist.push_front (values[4]);
257 testlist.insert (testlist.begin(), values.begin() + 2, values.begin() + 4);
259 const list_type& const_testlist = testlist;
260 { int init_values [] = { 3, 4, 5 };
261 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
263 typename list_type::iterator i = ++testlist.begin();
264 BOOST_TEST (i->value_ == 4);
266 testlist.insert (i, values[0]);
267 { int init_values [] = { 3, 1, 4, 5 };
268 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
270 i = testlist.iterator_to (values[4]);
271 BOOST_TEST (&*i == &values[4]);
273 i = list_type::s_iterator_to (values[4]);
274 BOOST_TEST (&*i == &values[4]);
276 i = testlist.erase (i);
277 BOOST_TEST (i == testlist.end());
279 { int init_values [] = { 3, 1, 4 };
280 TEST_INTRUSIVE_SEQUENCE( init_values, const_testlist.begin() ); }
282 testlist.erase (++testlist.begin(), testlist.end());
283 BOOST_TEST (testlist.size() == 1);
284 BOOST_TEST (testlist.begin()->value_ == 3);
287 template < typename List_Type, typename Value_Container >
288 void test_slist< List_Type, Value_Container >
289 ::test_shift(Value_Container& values)
292 const int num_values = (int)values.size();
293 std::vector<int> expected_values(num_values);
295 //Shift forward all possible positions 3 times
296 for(int s = 1; s <= num_values; ++s){
297 expected_values.resize(s);
298 for(int i = 0; i < s*3; ++i){
299 testlist.insert_after(testlist.before_begin(), values.begin(), values.begin() + s);
300 testlist.shift_forward(i);
301 for(int j = 0; j < s; ++j){
302 expected_values[(j + s - i%s) % s] = (j + 1);
305 TEST_INTRUSIVE_SEQUENCE_EXPECTED(expected_values, testlist.begin())
309 //Shift backwards all possible positions
310 for(int i = 0; i < s*3; ++i){
311 testlist.insert_after(testlist.before_begin(), values.begin(), values.begin() + s);
312 testlist.shift_backwards(i);
313 for(int j = 0; j < s; ++j){
314 expected_values[(j + i) % s] = (j + 1);
317 TEST_INTRUSIVE_SEQUENCE_EXPECTED(expected_values, testlist.begin())
323 //test: insert_after (seq-version), swap, splice_after:
324 template < typename List_Type, typename Value_Container >
325 void test_slist< List_Type, Value_Container >
326 ::test_swap(Value_Container& values)
329 list_type testlist1 (values.begin(), values.begin() + 2);
331 testlist2.insert_after (testlist2.before_begin(), values.begin() + 2, values.begin() + 5);
332 testlist1.swap(testlist2);
333 { int init_values [] = { 3, 4, 5 };
334 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
335 { int init_values [] = { 1, 2 };
336 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
337 testlist2.splice_after (testlist2.begin(), testlist1);
338 { int init_values [] = { 1, 3, 4, 5, 2 };
339 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
340 BOOST_TEST (testlist1.empty());
342 testlist1.splice_after (testlist1.before_begin(), testlist2, ++testlist2.begin());
343 { int init_values [] = { 4 };
344 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
345 { int init_values [] = { 1, 3, 5, 2 };
346 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
348 testlist1.splice_after (testlist1.begin(), testlist2,
349 testlist2.before_begin(), ++++testlist2.begin());
350 { int init_values [] = { 4, 1, 3, 5 };
351 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
352 { int init_values [] = { 2 };
353 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
355 { //Now test swap when testlist2 is empty
356 list_type testlist1 (values.begin(), values.begin() + 2);
358 testlist1.swap(testlist2);
359 BOOST_TEST (testlist1.empty());
360 { int init_values [] = { 1, 2 };
361 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
363 { //Now test swap when testlist1 is empty
364 list_type testlist2 (values.begin(), values.begin() + 2);
366 testlist1.swap(testlist2);
367 BOOST_TEST (testlist2.empty());
368 { int init_values [] = { 1, 2 };
369 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
371 { //Now test when both are empty
372 list_type testlist1, testlist2;
373 testlist2.swap(testlist1);
374 BOOST_TEST (testlist1.empty() && testlist2.empty());
377 if(!list_type::linear)
379 list_type testlist1 (values.begin(), values.begin() + 2);
380 list_type testlist2 (values.begin() + 3, values.begin() + 5);
382 swap_nodes< node_algorithms >(values[0], values[2]);
383 { int init_values [] = { 3, 2 };
384 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
386 swap_nodes< node_algorithms >(values[2], values[4]);
387 { int init_values [] = { 5, 2 };
388 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
389 { int init_values [] = { 4, 3 };
390 TEST_INTRUSIVE_SEQUENCE( init_values, testlist2.begin() ); }
392 if(!list_type::linear)
394 list_type testlist1 (values.begin(), values.begin()+1);
395 if(testlist1.size() != 1){
398 { int init_values [] = { 1 };
399 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
401 swap_nodes< node_algorithms >(values[1], values[2]);
403 BOOST_TEST(testlist1.size() == 1);
404 BOOST_TEST(!(&values[1])->is_linked());
405 BOOST_TEST(!(&values[2])->is_linked());
406 { int init_values [] = { 1 };
407 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
409 swap_nodes< node_algorithms >(values[0], values[2]);
410 BOOST_TEST(testlist1.size() == 1);
411 BOOST_TEST((&values[2])->is_linked());
412 BOOST_TEST(!(&values[0])->is_linked());
413 { int init_values [] = { 3 };
414 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
416 swap_nodes< node_algorithms >(values[0], values[2]);
417 BOOST_TEST(testlist1.size() == 1);
418 BOOST_TEST(!(&values[2])->is_linked());
419 BOOST_TEST((&values[0])->is_linked());
420 { int init_values [] = { 1 };
421 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() ); }
425 template < typename List_Type, typename Value_Container >
426 void test_slist< List_Type, Value_Container >
427 ::test_clone(Value_Container& values)
429 list_type testlist1 (values.begin(), values.begin() + values.size());
432 testlist2.clone_from(testlist1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
433 BOOST_TEST (testlist2 == testlist1);
434 testlist2.clear_and_dispose(test::delete_disposer<value_type>());
435 BOOST_TEST (testlist2.empty());
438 template < typename List_Type, typename Value_Container >
439 void test_slist< List_Type, Value_Container >
440 ::test_container_from_end(Value_Container& values, detail::true_type)
442 list_type testlist1 (values.begin(), values.begin() + values.size());
443 BOOST_TEST (testlist1 == list_type::container_from_end_iterator(testlist1.end()));
444 BOOST_TEST (testlist1 == list_type::container_from_end_iterator(testlist1.cend()));
447 template < typename Value_Traits, bool ConstantTimeSize, bool Linear, bool CacheLast, bool Default_Holder, typename Value_Container >
448 struct make_and_test_slist
449 : test_slist< slist< typename Value_Traits::value_type,
450 value_traits< Value_Traits >,
451 size_type< std::size_t >,
452 constant_time_size< ConstantTimeSize >,
454 cache_last<CacheLast>
460 template < typename Value_Traits, bool ConstantTimeSize, bool Linear, bool CacheLast, typename Value_Container >
461 struct make_and_test_slist< Value_Traits, ConstantTimeSize, Linear, CacheLast, false, Value_Container >
462 : test_slist< slist< typename Value_Traits::value_type,
463 value_traits< Value_Traits >,
464 size_type< std::size_t >,
465 constant_time_size< ConstantTimeSize >,
467 cache_last<CacheLast>,
468 header_holder_type< pointer_holder< typename Value_Traits::node_traits::node > >
474 template<class VoidPointer, bool constant_time_size, bool Default_Holder>
475 class test_main_template
480 typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
481 std::vector< value_type > data (5);
482 for (int i = 0; i < 5; ++i)
483 data[i].value_ = i + 1;
485 make_and_test_slist < typename detail::get_base_value_traits
487 , typename hooks<VoidPointer>::base_hook_type
493 , std::vector< value_type >
495 make_and_test_slist < typename detail::get_member_value_traits
496 < member_hook< value_type
497 , typename hooks<VoidPointer>::member_hook_type
505 , std::vector< value_type >
507 make_and_test_slist < nonhook_node_member_value_traits< value_type,
508 typename hooks<VoidPointer>::nonhook_node_member_type,
509 &value_type::nhn_member_,
516 , std::vector< value_type >
520 make_and_test_slist < typename detail::get_base_value_traits
522 , typename hooks<VoidPointer>::base_hook_type
528 , std::vector< value_type >
531 make_and_test_slist < typename detail::get_member_value_traits
532 < member_hook< value_type
533 , typename hooks<VoidPointer>::member_hook_type
541 , std::vector< value_type >
544 //Now the same but caching the last node
545 make_and_test_slist < typename detail::get_base_value_traits
547 , typename hooks<VoidPointer>::base_hook_type
553 , std::vector< value_type >
555 make_and_test_slist < typename detail::get_member_value_traits
556 < member_hook< value_type
557 , typename hooks<VoidPointer>::member_hook_type
565 , std::vector< value_type >
569 make_and_test_slist < typename detail::get_base_value_traits
571 , typename hooks<VoidPointer>::base_hook_type
577 , std::vector< value_type >
580 make_and_test_slist < typename detail::get_member_value_traits
581 < member_hook< value_type
582 , typename hooks<VoidPointer>::member_hook_type
590 , std::vector< value_type >
596 template<class VoidPointer, bool Default_Holder>
597 class test_main_template<VoidPointer, false, Default_Holder>
602 typedef testvalue<hooks<VoidPointer> , false> value_type;
603 std::vector< value_type > data (5);
604 for (int i = 0; i < 5; ++i)
605 data[i].value_ = i + 1;
607 make_and_test_slist < typename detail::get_base_value_traits
609 , typename hooks<VoidPointer>::base_hook_type
615 , std::vector< value_type >
618 make_and_test_slist < typename detail::get_member_value_traits
619 < member_hook< value_type
620 , typename hooks<VoidPointer>::member_hook_type
628 , std::vector< value_type >
631 make_and_test_slist < typename detail::get_base_value_traits
633 , typename hooks<VoidPointer>::auto_base_hook_type
639 , std::vector< value_type >
642 make_and_test_slist < typename detail::get_member_value_traits
643 < member_hook< value_type
644 , typename hooks<VoidPointer>::auto_member_hook_type
645 , &value_type::auto_node_
652 , std::vector< value_type >
655 make_and_test_slist < typename detail::get_base_value_traits
657 , typename hooks<VoidPointer>::base_hook_type
663 , std::vector< value_type >
666 make_and_test_slist < typename detail::get_member_value_traits
667 < member_hook< value_type
668 , typename hooks<VoidPointer>::member_hook_type
676 , std::vector< value_type >
680 make_and_test_slist < typename detail::get_base_value_traits
682 , typename hooks<VoidPointer>::base_hook_type
688 , std::vector< value_type >
691 make_and_test_slist < typename detail::get_member_value_traits
692 < member_hook< value_type
693 , typename hooks<VoidPointer>::member_hook_type
701 , std::vector< value_type >
704 make_and_test_slist < typename detail::get_base_value_traits
706 , typename hooks<VoidPointer>::base_hook_type
712 , std::vector< value_type >
715 make_and_test_slist < typename detail::get_member_value_traits
716 < member_hook< value_type
717 , typename hooks<VoidPointer>::member_hook_type
725 , std::vector< value_type >
731 template < bool ConstantTimeSize >
732 struct test_main_template_bptr
736 typedef BPtr_Value value_type;
737 typedef BPtr_Value_Traits< List_BPtr_Node_Traits > list_value_traits;
738 typedef typename list_value_traits::node_ptr node_ptr;
739 typedef bounded_allocator< value_type > allocator_type;
741 allocator_type::init();
742 allocator_type allocator;
745 bounded_reference_cont< value_type > ref_cont;
746 for (int i = 0; i < 5; ++i)
748 node_ptr tmp = allocator.allocate(1);
749 new (tmp.raw()) value_type(i + 1);
750 ref_cont.push_back(*tmp);
753 test_slist < slist < value_type,
754 value_traits< list_value_traits >,
755 size_type< std::size_t >,
756 constant_time_size< ConstantTimeSize >,
757 header_holder_type< bounded_pointer_holder< value_type > >
759 bounded_reference_cont< value_type >
760 >::test_all(ref_cont);
763 assert(allocator_type::is_clear());
764 allocator_type::destroy();
769 int main(int, char* [])
771 // test (plain/smart pointers) x (nonconst/const size) x (void node allocator)
772 test_main_template<void*, false, true>()();
773 test_main_template<boost::intrusive::smart_ptr<void>, false, true>()();
774 test_main_template<void*, true, true>()();
775 test_main_template<boost::intrusive::smart_ptr<void>, true, true>()();
776 // test (bounded pointers) x ((nonconst/const size) x (special node allocator)
777 test_main_template_bptr< true >()();
778 test_main_template_bptr< false >()();
781 return boost::report_errors();