]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2004-2013. Distributed under the Boost | |
4 | // Software License, Version 1.0. (See accompanying file | |
5 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | // | |
7 | // See http://www.boost.org/libs/container for documentation. | |
8 | // | |
9 | ////////////////////////////////////////////////////////////////////////////// | |
10 | #include <boost/container/detail/config_begin.hpp> | |
11 | #include <set> | |
12 | #include <boost/container/set.hpp> | |
13 | #include <boost/container/adaptive_pool.hpp> | |
14 | ||
15 | #include "print_container.hpp" | |
16 | #include "movable_int.hpp" | |
17 | #include "dummy_test_allocator.hpp" | |
18 | #include "set_test.hpp" | |
19 | #include "propagate_allocator_test.hpp" | |
20 | #include "emplace_test.hpp" | |
21 | #include "../../intrusive/test/iterator_test.hpp" | |
22 | ||
23 | using namespace boost::container; | |
24 | ||
25 | namespace boost { | |
26 | namespace container { | |
27 | ||
28 | //Explicit instantiation to detect compilation errors | |
29 | ||
30 | //set | |
31 | template class set | |
32 | < test::movable_and_copyable_int | |
33 | , std::less<test::movable_and_copyable_int> | |
34 | , test::simple_allocator<test::movable_and_copyable_int> | |
35 | >; | |
36 | ||
37 | template class set | |
38 | < test::movable_and_copyable_int | |
39 | , std::less<test::movable_and_copyable_int> | |
b32b8144 | 40 | , new_allocator<test::movable_and_copyable_int> |
7c673cae FG |
41 | >; |
42 | ||
43 | //multiset | |
44 | template class multiset | |
45 | < test::movable_and_copyable_int | |
46 | , std::less<test::movable_and_copyable_int> | |
47 | , test::simple_allocator<test::movable_and_copyable_int> | |
48 | >; | |
49 | ||
50 | template class multiset | |
51 | < test::movable_and_copyable_int | |
52 | , std::less<test::movable_and_copyable_int> | |
53 | , adaptive_pool<test::movable_and_copyable_int> | |
54 | >; | |
55 | ||
7c673cae FG |
56 | }} //boost::container |
57 | ||
58 | //Test recursive structures | |
59 | class recursive_set | |
60 | { | |
61 | public: | |
62 | recursive_set & operator=(const recursive_set &x) | |
63 | { id_ = x.id_; set_ = x.set_; return *this; } | |
64 | ||
65 | int id_; | |
66 | set<recursive_set> set_; | |
67 | set<recursive_set>::iterator it_; | |
68 | set<recursive_set>::const_iterator cit_; | |
69 | set<recursive_set>::reverse_iterator rit_; | |
70 | set<recursive_set>::const_reverse_iterator crit_; | |
71 | ||
72 | friend bool operator< (const recursive_set &a, const recursive_set &b) | |
73 | { return a.id_ < b.id_; } | |
74 | }; | |
75 | ||
76 | //Test recursive structures | |
77 | class recursive_multiset | |
78 | { | |
79 | public: | |
80 | recursive_multiset & operator=(const recursive_multiset &x) | |
81 | { id_ = x.id_; multiset_ = x.multiset_; return *this; } | |
82 | ||
83 | int id_; | |
84 | multiset<recursive_multiset> multiset_; | |
85 | multiset<recursive_multiset>::iterator it_; | |
86 | multiset<recursive_multiset>::const_iterator cit_; | |
87 | multiset<recursive_multiset>::reverse_iterator rit_; | |
88 | multiset<recursive_multiset>::const_reverse_iterator crit_; | |
89 | ||
90 | friend bool operator< (const recursive_multiset &a, const recursive_multiset &b) | |
91 | { return a.id_ < b.id_; } | |
92 | }; | |
93 | ||
94 | template<class C> | |
95 | void test_move() | |
96 | { | |
97 | //Now test move semantics | |
98 | C original; | |
99 | original.emplace(); | |
100 | C move_ctor(boost::move(original)); | |
101 | C move_assign; | |
102 | move_assign.emplace(); | |
103 | move_assign = boost::move(move_ctor); | |
104 | move_assign.swap(original); | |
105 | } | |
106 | ||
107 | bool node_type_test() | |
108 | { | |
109 | using namespace boost::container; | |
110 | { | |
111 | typedef set<test::movable_int> set_type; | |
112 | set_type src; | |
113 | { | |
114 | test::movable_int mv_1(1), mv_2(2), mv_3(3); | |
115 | src.emplace(boost::move(mv_1)); | |
116 | src.emplace(boost::move(mv_2)); | |
117 | src.emplace(boost::move(mv_3)); | |
118 | } | |
119 | if(src.size() != 3) | |
120 | return false; | |
121 | ||
122 | set_type dst; | |
123 | { | |
124 | test::movable_int mv_3(3); | |
125 | dst.emplace(boost::move(mv_3)); | |
126 | } | |
127 | ||
128 | if(dst.size() != 1) | |
129 | return false; | |
130 | ||
131 | const test::movable_int mv_1(1); | |
132 | const test::movable_int mv_2(2); | |
133 | const test::movable_int mv_3(3); | |
134 | const test::movable_int mv_33(33); | |
135 | set_type::insert_return_type r; | |
136 | ||
137 | r = dst.insert(src.extract(mv_33)); // Key version, try to insert empty node | |
138 | if(! (r.position == dst.end() && r.inserted == false && r.node.empty()) ) | |
139 | return false; | |
140 | r = dst.insert(src.extract(src.find(mv_1))); // Iterator version, successful | |
141 | if(! (r.position == dst.find(mv_1) && r.inserted == true && r.node.empty()) ) | |
142 | return false; | |
143 | r = dst.insert(dst.begin(), src.extract(mv_2)); // Key type version, successful | |
144 | if(! (r.position == dst.find(mv_2) && r.inserted == true && r.node.empty()) ) | |
145 | return false; | |
146 | r = dst.insert(src.extract(mv_3)); // Key type version, unsuccessful | |
147 | ||
148 | if(!src.empty()) | |
149 | return false; | |
150 | if(dst.size() != 3) | |
151 | return false; | |
152 | if(! (r.position == dst.find(mv_3) && r.inserted == false && r.node.value() == mv_3) ) | |
153 | return false; | |
154 | } | |
155 | ||
156 | { | |
157 | typedef multiset<test::movable_int> multiset_type; | |
158 | multiset_type src; | |
159 | { | |
160 | test::movable_int mv_1(1), mv_2(2), mv_3(3), mv_3bis(3); | |
161 | src.emplace(boost::move(mv_1)); | |
162 | src.emplace(boost::move(mv_2)); | |
163 | src.emplace(boost::move(mv_3)); | |
164 | src.emplace_hint(src.begin(), boost::move(mv_3bis)); | |
165 | } | |
166 | if(src.size() != 4) | |
167 | return false; | |
168 | ||
169 | multiset_type dst; | |
170 | { | |
171 | test::movable_int mv_3(3); | |
172 | dst.emplace(boost::move(mv_3)); | |
173 | } | |
174 | ||
175 | if(dst.size() != 1) | |
176 | return false; | |
177 | ||
178 | const test::movable_int mv_1(1); | |
179 | const test::movable_int mv_2(2); | |
180 | const test::movable_int mv_3(3); | |
181 | const test::movable_int mv_4(4); | |
182 | multiset_type::iterator r; | |
183 | ||
184 | multiset_type::node_type nt(src.extract(mv_3)); | |
185 | r = dst.insert(dst.begin(), boost::move(nt)); | |
186 | if(! (*r == mv_3 && dst.find(mv_3) == r && nt.empty()) ) | |
187 | return false; | |
188 | ||
189 | nt = src.extract(src.find(mv_1)); | |
190 | r = dst.insert(boost::move(nt)); // Iterator version, successful | |
191 | if(! (*r == mv_1 && nt.empty()) ) | |
192 | return false; | |
193 | ||
194 | nt = src.extract(mv_2); | |
195 | r = dst.insert(boost::move(nt)); // Key type version, successful | |
196 | if(! (*r == mv_2 && nt.empty()) ) | |
197 | return false; | |
198 | ||
199 | r = dst.insert(src.extract(mv_3)); // Key type version, successful | |
200 | if(! (*r == mv_3 && r == --multiset_type::iterator(dst.upper_bound(mv_3)) && nt.empty()) ) | |
201 | return false; | |
202 | ||
203 | r = dst.insert(src.extract(mv_4)); // Key type version, unsuccessful | |
204 | if(! (r == dst.end()) ) | |
205 | return false; | |
206 | ||
207 | if(!src.empty()) | |
208 | return false; | |
209 | if(dst.size() != 5) | |
210 | return false; | |
211 | } | |
212 | return true; | |
213 | } | |
214 | ||
215 | struct boost_container_set; | |
216 | struct boost_container_multiset; | |
217 | ||
218 | namespace boost { | |
219 | namespace container { | |
220 | namespace test { | |
221 | ||
222 | template<> | |
223 | struct alloc_propagate_base<boost_container_set> | |
224 | { | |
225 | template <class T, class Allocator> | |
226 | struct apply | |
227 | { | |
228 | typedef boost::container::set<T, std::less<T>, Allocator> type; | |
229 | }; | |
230 | }; | |
231 | ||
232 | template<> | |
233 | struct alloc_propagate_base<boost_container_multiset> | |
234 | { | |
235 | template <class T, class Allocator> | |
236 | struct apply | |
237 | { | |
238 | typedef boost::container::multiset<T, std::less<T>, Allocator> type; | |
239 | }; | |
240 | }; | |
241 | ||
242 | }}} //boost::container::test | |
243 | ||
244 | template<class VoidAllocator, boost::container::tree_type_enum tree_type_value> | |
245 | struct GetAllocatorSet | |
246 | { | |
247 | template<class ValueType> | |
248 | struct apply | |
249 | { | |
250 | typedef set < ValueType | |
251 | , std::less<ValueType> | |
252 | , typename allocator_traits<VoidAllocator> | |
253 | ::template portable_rebind_alloc<ValueType>::type | |
254 | , typename boost::container::tree_assoc_options | |
255 | < boost::container::tree_type<tree_type_value> | |
256 | >::type | |
257 | > set_type; | |
258 | ||
259 | typedef multiset < ValueType | |
260 | , std::less<ValueType> | |
261 | , typename allocator_traits<VoidAllocator> | |
262 | ::template portable_rebind_alloc<ValueType>::type | |
263 | , typename boost::container::tree_assoc_options | |
264 | < boost::container::tree_type<tree_type_value> | |
265 | >::type | |
266 | > multiset_type; | |
267 | }; | |
268 | }; | |
269 | ||
270 | template<class VoidAllocator, boost::container::tree_type_enum tree_type_value> | |
271 | int test_set_variants() | |
272 | { | |
273 | typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<int>::set_type MySet; | |
274 | typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::movable_int>::set_type MyMoveSet; | |
7c673cae FG |
275 | typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::copyable_int>::set_type MyCopySet; |
276 | ||
277 | typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<int>::multiset_type MyMultiSet; | |
278 | typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::movable_int>::multiset_type MyMoveMultiSet; | |
7c673cae FG |
279 | typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::copyable_int>::multiset_type MyCopyMultiSet; |
280 | ||
281 | typedef std::set<int> MyStdSet; | |
282 | typedef std::multiset<int> MyStdMultiSet; | |
283 | ||
284 | if (0 != test::set_test< | |
285 | MySet | |
286 | ,MyStdSet | |
287 | ,MyMultiSet | |
288 | ,MyStdMultiSet>()){ | |
289 | std::cout << "Error in set_test<MyBoostSet>" << std::endl; | |
290 | return 1; | |
291 | } | |
292 | ||
293 | if (0 != test::set_test< | |
294 | MyMoveSet | |
295 | ,MyStdSet | |
296 | ,MyMoveMultiSet | |
297 | ,MyStdMultiSet>()){ | |
298 | std::cout << "Error in set_test<MyBoostSet>" << std::endl; | |
299 | return 1; | |
300 | } | |
301 | ||
7c673cae FG |
302 | if (0 != test::set_test< |
303 | MyCopySet | |
304 | ,MyStdSet | |
305 | ,MyCopyMultiSet | |
306 | ,MyStdMultiSet>()){ | |
307 | std::cout << "Error in set_test<MyBoostSet>" << std::endl; | |
308 | return 1; | |
309 | } | |
310 | ||
311 | return 0; | |
312 | } | |
313 | ||
314 | void test_merge_from_different_comparison() | |
315 | { | |
316 | set<int> set1; | |
317 | set<int, std::greater<int> > set2; | |
318 | set1.merge(set2); | |
319 | } | |
320 | ||
7c673cae FG |
321 | int main () |
322 | { | |
323 | //Recursive container instantiation | |
324 | { | |
325 | set<recursive_set> set_; | |
326 | multiset<recursive_multiset> multiset_; | |
327 | } | |
328 | //Allocator argument container | |
329 | { | |
330 | set<int> set_((set<int>::allocator_type())); | |
331 | multiset<int> multiset_((multiset<int>::allocator_type())); | |
332 | } | |
333 | //Now test move semantics | |
334 | { | |
335 | test_move<set<recursive_set> >(); | |
336 | test_move<multiset<recursive_multiset> >(); | |
337 | } | |
338 | //Test std::pair value type as tree has workarounds to make old std::pair | |
339 | //implementations movable that can break things | |
340 | { | |
b32b8144 FG |
341 | boost::container::set<std::pair<int,int> > s; |
342 | std::pair<int,int> p(0, 0); | |
343 | s.insert(p); | |
344 | s.emplace(p); | |
7c673cae FG |
345 | } |
346 | ||
b32b8144 FG |
347 | if (!boost::container::test::instantiate_constructors<set<int>, multiset<int> >()) |
348 | return 1; | |
349 | ||
7c673cae FG |
350 | test_merge_from_different_comparison(); |
351 | ||
352 | //////////////////////////////////// | |
353 | // Testing allocator implementations | |
354 | //////////////////////////////////// | |
355 | // std:allocator | |
356 | if(test_set_variants< std::allocator<void>, red_black_tree >()){ | |
357 | std::cerr << "test_set_variants< std::allocator<void> > failed" << std::endl; | |
358 | return 1; | |
359 | } | |
360 | // boost::container::adaptive_pool | |
361 | if(test_set_variants< adaptive_pool<void>, red_black_tree>()){ | |
362 | std::cerr << "test_set_variants< adaptive_pool<void> > failed" << std::endl; | |
363 | return 1; | |
364 | } | |
365 | ||
366 | //////////////////////////////////// | |
367 | // Tree implementations | |
368 | //////////////////////////////////// | |
369 | // AVL | |
370 | if(test_set_variants< std::allocator<void>, avl_tree >()){ | |
371 | std::cerr << "test_set_variants< std::allocator<void>, avl_tree > failed" << std::endl; | |
372 | return 1; | |
373 | } | |
374 | // SCAPEGOAT TREE | |
375 | if(test_set_variants< std::allocator<void>, scapegoat_tree >()){ | |
376 | std::cerr << "test_set_variants< std::allocator<void>, scapegoat_tree > failed" << std::endl; | |
377 | return 1; | |
378 | } | |
379 | // SPLAY TREE | |
380 | if(test_set_variants< std::allocator<void>, splay_tree >()){ | |
381 | std::cerr << "test_set_variants< std::allocator<void>, splay_tree > failed" << std::endl; | |
382 | return 1; | |
383 | } | |
384 | ||
385 | //////////////////////////////////// | |
386 | // Emplace testing | |
387 | //////////////////////////////////// | |
388 | const test::EmplaceOptions SetOptions = (test::EmplaceOptions)(test::EMPLACE_HINT | test::EMPLACE_ASSOC); | |
389 | if(!boost::container::test::test_emplace<set<test::EmplaceInt>, SetOptions>()) | |
390 | return 1; | |
391 | if(!boost::container::test::test_emplace<multiset<test::EmplaceInt>, SetOptions>()) | |
392 | return 1; | |
393 | ||
394 | //////////////////////////////////// | |
395 | // Allocator propagation testing | |
396 | //////////////////////////////////// | |
397 | if(!boost::container::test::test_propagate_allocator<boost_container_set>()) | |
398 | return 1; | |
399 | ||
400 | if(!boost::container::test::test_propagate_allocator<boost_container_multiset>()) | |
401 | return 1; | |
402 | ||
403 | if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<set<int> >()) | |
404 | return 1; | |
405 | ||
406 | if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<multiset<int> >()) | |
407 | return 1; | |
408 | ||
409 | //////////////////////////////////// | |
410 | // Test optimize_size option | |
411 | //////////////////////////////////// | |
412 | // | |
413 | // set | |
414 | // | |
415 | typedef set< int*, std::less<int*>, std::allocator<int*> | |
416 | , tree_assoc_options< optimize_size<false>, tree_type<red_black_tree> >::type > rbset_size_optimized_no; | |
7c673cae | 417 | |
7c673cae FG |
418 | typedef set< int*, std::less<int*>, std::allocator<int*> |
419 | , tree_assoc_options< optimize_size<true>, tree_type<avl_tree> >::type > avlset_size_optimized_yes; | |
7c673cae FG |
420 | // |
421 | // multiset | |
422 | // | |
7c673cae FG |
423 | typedef multiset< int*, std::less<int*>, std::allocator<int*> |
424 | , tree_assoc_options< optimize_size<true>, tree_type<red_black_tree> >::type > rbmset_size_optimized_yes; | |
7c673cae FG |
425 | |
426 | typedef multiset< int*, std::less<int*>, std::allocator<int*> | |
427 | , tree_assoc_options< optimize_size<false>, tree_type<avl_tree> >::type > avlmset_size_optimized_no; | |
b32b8144 FG |
428 | |
429 | BOOST_STATIC_ASSERT(sizeof(rbmset_size_optimized_yes) < sizeof(rbset_size_optimized_no)); | |
430 | BOOST_STATIC_ASSERT(sizeof(avlset_size_optimized_yes) < sizeof(avlmset_size_optimized_no)); | |
7c673cae FG |
431 | |
432 | //////////////////////////////////// | |
433 | // Iterator testing | |
434 | //////////////////////////////////// | |
435 | { | |
436 | typedef boost::container::set<int> cont_int; | |
437 | cont_int a; a.insert(0); a.insert(1); a.insert(2); | |
438 | boost::intrusive::test::test_iterator_bidirectional< cont_int >(a); | |
439 | if(boost::report_errors() != 0) { | |
440 | return 1; | |
441 | } | |
442 | } | |
443 | { | |
444 | typedef boost::container::multiset<int> cont_int; | |
445 | cont_int a; a.insert(0); a.insert(1); a.insert(2); | |
446 | boost::intrusive::test::test_iterator_bidirectional< cont_int >(a); | |
447 | if(boost::report_errors() != 0) { | |
448 | return 1; | |
449 | } | |
450 | } | |
451 | ||
452 | //////////////////////////////////// | |
453 | // Node extraction/insertion testing functions | |
454 | //////////////////////////////////// | |
455 | if(!node_type_test()) | |
456 | return 1; | |
457 | ||
458 | return 0; | |
459 | } | |
460 | ||
461 | #include <boost/container/detail/config_end.hpp> |