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