1/* Boost.MultiIndex test for node handling operations.
2 *
3 * Copyright 2003-2021 Joaquin M Lopez Munoz.
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE_1_0.txt or copy at
6 * http://www.boost.org/LICENSE_1_0.txt)
7 *
8 * See http://www.boost.org/libs/multi_index for library home page.
9 */
10
11#include "test_node_handling.hpp"
12
13#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
14#include <boost/core/enable_if.hpp>
15#include <boost/detail/lightweight_test.hpp>
16#include <boost/move/utility_core.hpp>
17#include "pre_multi_index.hpp"
18#include <boost/multi_index_container.hpp>
19#include <boost/multi_index/hashed_index.hpp>
20#include <boost/multi_index/identity.hpp>
21#include <boost/multi_index/ordered_index.hpp>
22#include <boost/multi_index/random_access_index.hpp>
23#include <boost/multi_index/ranked_index.hpp>
24#include <boost/multi_index/sequenced_index.hpp>
25#include <boost/next_prior.hpp>
26#include <boost/type_traits/is_same.hpp>
27#include <boost/type_traits/remove_reference.hpp>
28#include <functional>
29#include <iterator>
30#include <utility>
31#include <vector>
32#include "count_allocator.hpp"
33
34using namespace boost::multi_index;
35
36void test_node_handle()
37{
38 typedef count_allocator<int> allocator;
39 typedef multi_index_container<
40 int,
41 indexed_by<
42 ordered_unique<identity<int> >
43 >,
44 allocator
45 > container;
46 typedef container::node_type node_type;
47
48 std::size_t element_count=0,allocator_count=0;
49 container c((allocator(element_count,allocator_count)));
50
51 element_count=0; /* ignore non element-related allocations */
52 allocator_count=0; /* ignore internal allocator(s) */
53
54 c.insert(x: 0);
55 c.insert(x: 1);
56 c.insert(x: 2);
57 const int* addr0=&*c.find(x: 0);
58 const int* addr1=&*c.find(x: 1);
59 BOOST_TEST(element_count==3);
60
61 node_type n1;
62 BOOST_TEST(n1.empty());
63 BOOST_TEST(!n1);
64 BOOST_TEST(allocator_count==0);
65
66 node_type n2=c.extract(x: 0);
67 BOOST_TEST(!n2.empty());
68 BOOST_TEST((bool)n2);
69 BOOST_TEST(n2.value()==0);
70 BOOST_TEST(&n2.value()==addr0);
71 BOOST_TEST(allocator_count==1);
72
73 node_type n3(boost::move(t&: n2));
74 BOOST_TEST(n2.empty());
75 BOOST_TEST(!n3.empty());
76 BOOST_TEST(&n3.value()==addr0);
77 BOOST_TEST(allocator_count==1);
78
79 node_type n4(boost::move(t&: n2));
80 BOOST_TEST(n4.empty());
81 BOOST_TEST(allocator_count==1);
82
83 n1=boost::move(t&: n3);
84 BOOST_TEST(!n1.empty());
85 BOOST_TEST(&n1.value()==addr0);
86 BOOST_TEST(n3.empty());
87 BOOST_TEST(allocator_count==1);
88
89 BOOST_TEST(n1.get_allocator()==c.get_allocator());
90
91 node_type n5=c.extract(x: 1);
92 BOOST_TEST(n5.value()==1);
93 BOOST_TEST(&n5.value()==addr1);
94 BOOST_TEST(allocator_count==2);
95
96 n1.swap(x&: n5);
97 BOOST_TEST(&n1.value()==addr1);
98 BOOST_TEST(&n5.value()==addr0);
99 BOOST_TEST(allocator_count==2);
100
101 using std::swap;
102
103 swap(x&: n2,y&: n3);
104 BOOST_TEST(n2.empty());
105 BOOST_TEST(n3.empty());
106 BOOST_TEST(allocator_count==2);
107
108 swap(x&: n1,y&: n2);
109 BOOST_TEST(!n2.empty());
110 BOOST_TEST(&n2.value()==addr1);
111 BOOST_TEST(allocator_count==2);
112
113 swap(x&: n1,y&: n2);
114 BOOST_TEST(&n1.value()==addr1);
115 BOOST_TEST(n2.empty());
116 BOOST_TEST(allocator_count==2);
117
118 n2=boost::move(t&: n3);
119 BOOST_TEST(n2.empty());
120 BOOST_TEST(n3.empty());
121 BOOST_TEST(allocator_count==2);
122
123 BOOST_TEST(element_count==3);
124 n1=boost::move(t&: n5);
125 BOOST_TEST(&n1.value()==addr0);
126 BOOST_TEST(n5.empty());
127 BOOST_TEST(element_count==2);
128 BOOST_TEST(allocator_count==1);
129
130 n1=boost::move(t&: n5);
131 BOOST_TEST(n1.empty());
132 BOOST_TEST(element_count==1);
133 BOOST_TEST(allocator_count==0);
134
135 c.extract(x: 2);
136 BOOST_TEST(element_count==0);
137}
138
139template<typename Index>
140struct is_key_based:boost::integral_constant<
141 bool,
142 /* rather fragile if new index types are included in the library */
143 (boost::tuples::length<typename boost::remove_reference<Index>::
144 type::ctor_args>::value > 0)
145>
146{};
147
148template<typename T>
149struct is_iterator
150{
151 typedef char yes;
152 struct no{char m[2];};
153
154 template<typename Q> static no test(...);
155 template<typename Q> static yes test(typename Q::iterator_category*);
156
157 BOOST_STATIC_CONSTANT(bool,value=(sizeof(test<T>(0))==sizeof(yes)));
158};
159
160template<typename T>
161struct enable_if_not_iterator:boost::enable_if_c<
162 !is_iterator<T>::value,
163 void*
164>{};
165
166template<typename Dst,typename Ret,typename NodeHandle,typename Value>
167void test_transfer_result(
168 Dst&,Ret res,const NodeHandle& n,const Value& x,
169 typename enable_if_not_iterator<Ret>::type=0)
170{
171 BOOST_TEST(*(res.position)==x);
172 if(res.inserted){
173 BOOST_TEST(res.node.empty());
174 }
175 else{
176 BOOST_TEST(res.node.value()==x);
177 }
178 BOOST_TEST(n.empty());
179}
180
181template<typename Dst,typename NodeHandle,typename Value>
182void test_transfer_result(
183 Dst&,typename Dst::iterator res,const NodeHandle& n,const Value& x)
184{
185 BOOST_TEST(*res==x);
186 if(n)BOOST_TEST(n.value()==x);
187}
188
189template<typename Dst,typename Ret>
190void test_transfer_result_empty(
191 Dst& dst,Ret res,
192 typename enable_if_not_iterator<Ret>::type=0)
193{
194 BOOST_TEST(res.position==dst.end());
195 BOOST_TEST(!res.inserted);
196 BOOST_TEST(res.node.empty());
197}
198
199template<typename Dst>
200void test_transfer_result_empty(Dst& dst,typename Dst::iterator res)
201{
202 BOOST_TEST(res==dst.end());
203}
204
205template<typename Dst,typename Ret,typename NodeHandle,typename Value>
206void test_transfer_result(
207 Dst& dst,typename Dst::iterator pos,Ret res,
208 const NodeHandle& n,const Value& x,
209 typename enable_if_not_iterator<Ret>::type=0)
210{
211 if(res.inserted&&pos!=dst.end()&&
212 (!is_key_based<Dst>::value||*pos==x)){
213 BOOST_TEST(boost::next(res.position)==pos);
214 }
215 test_transfer_result(dst,Ret(boost::move(res)),n,x);
216}
217
218template<typename Dst,typename NodeHandle,typename Value>
219void test_transfer_result(
220 Dst& dst,typename Dst::iterator pos,
221 typename Dst::iterator res,const NodeHandle& n,const Value& x)
222{
223 if(n.empty()&&pos!=dst.end()&&
224 (!is_key_based<Dst>::value||*pos==x)){
225 BOOST_TEST(boost::next(res)==pos);
226 }
227 test_transfer_result(dst,res,n,x);
228}
229
230template<typename Dst,typename Ret>
231void test_transfer_result_empty(
232 Dst& dst,typename Dst::iterator,Ret res,
233 typename enable_if_not_iterator<Ret>::type=0)
234{
235 test_transfer_result_empty(dst,Ret(boost::move(res)));
236}
237
238template<typename Dst>
239void test_transfer_result_empty(
240 Dst& dst,typename Dst::iterator,typename Dst::iterator res)
241{
242 test_transfer_result_empty(dst,res);
243}
244
245template<typename Src,typename Key>
246typename Src::node_type checked_extract(
247 Src& src,Key k,
248 typename enable_if_not_iterator<Key>::type=0)
249{
250 typename Src::node_type n=src.extract(k);
251 if(n)BOOST_TEST(src.key_extractor()(n.value())==k);
252 return boost::move(n);
253}
254
255template<typename Src>
256typename Src::node_type checked_extract(Src& src,typename Src::iterator pos)
257{
258 typename Src::value_type x=*pos;
259 typename Src::node_type n=src.extract(pos);
260 if(n)BOOST_TEST(n.value()==x);
261 return boost::move(n);
262}
263
264template<typename Src,typename Locator,typename Dst>
265void test_transfer(Src& src,Locator loc,Dst& dst)
266{
267 typename Dst::node_type n=checked_extract(src,loc);
268 if(n){
269 typename Dst::value_type x=n.value();
270 test_transfer_result(dst,dst.insert(boost::move(n)),n,x);
271 }
272 else{
273 test_transfer_result_empty(dst,dst.insert(boost::move(n)));
274 }
275}
276
277template<typename Src,typename Locator,typename Dst,typename Iterator>
278void test_transfer(Src& src,Locator loc,Dst& dst,Iterator pos)
279{
280 typename Dst::node_type n=checked_extract(src,loc);
281 if(n){
282 typename Dst::value_type x=n.value();
283 test_transfer_result(dst,pos,dst.insert(pos,boost::move(n)),n,x);
284 }
285 else{
286 test_transfer_result_empty(dst,pos,dst.insert(pos,boost::move(n)));
287 }
288}
289
290template<typename Src,typename Dst>
291void test_transfer(
292 Src& src,Dst& dst0,Dst& /* dst1 */,Dst& /* dst2 */,Dst& /* dst3 */,
293 boost::false_type /* Src key-based */,boost::false_type /* Dst key-based */)
294{
295 test_transfer(src,src.begin(),dst0,dst0.begin());
296 test_transfer(src,src.begin(),dst0,dst0.begin());
297 for(int i=0;i<6;++i)src.extract(src.begin());
298}
299
300template<typename Src,typename Dst>
301void test_transfer(
302 Src& src,Dst& dst0,Dst& dst1,Dst& /* dst2 */,Dst& /* dst3 */,
303 boost::false_type /* Src key-based */,boost::true_type /* Dst key-based */)
304{
305 test_transfer(src,src.begin(),dst0);
306 test_transfer(src,src.begin(),dst0);
307 test_transfer(src,src.begin(),dst1,dst1.find(*src.begin()));
308 test_transfer(src,src.begin(),dst1,dst1.find(*src.begin()));
309 for(int i=0;i<4;++i)src.extract(src.begin());
310}
311
312template<typename Src,typename Dst>
313void test_transfer(
314 Src& src,Dst& dst0,Dst& dst1,Dst& /* dst2 */,Dst& /* dst3 */,
315 boost::true_type /* Src key-based */,boost::false_type /* Dst key-based */)
316{
317 test_transfer(src, src.begin(),dst0,dst0.begin());
318 test_transfer(src, src.begin(),dst0,dst0.begin());
319 test_transfer(src,*src.begin(),dst1,dst1.begin());
320 test_transfer(src,*src.begin(),dst1,dst1.begin());
321 test_transfer(src, -1,dst1,dst1.begin());
322 for(int i=0;i<4;++i)src.extract(src.begin());
323}
324
325template<typename Src,typename Dst>
326void test_transfer(
327 Src& src,Dst& dst0,Dst& dst1,Dst& dst2,Dst& dst3,
328 boost::true_type /* Src key-based */,boost::true_type /* Dst key-based */)
329{
330 test_transfer(src, src.begin(),dst0);
331 test_transfer(src, src.begin(),dst0);
332 test_transfer(src,*src.begin(),dst1);
333 test_transfer(src,*src.begin(),dst1);
334 test_transfer(src, -1,dst1);
335 test_transfer(src, src.begin(),dst2,dst2.find(*src.begin()));
336 test_transfer(src, src.begin(),dst2,dst2.find(*src.begin()));
337 test_transfer(src,*src.begin(),dst3,dst3.find(*src.begin()));
338 test_transfer(src,*src.begin(),dst3,dst3.find(*src.begin()));
339 test_transfer(src, -1,dst3,dst3.begin());
340}
341
342template<typename Src,typename Dst>
343void test_transfer(Src& src,Dst& dst0,Dst& dst1,Dst& dst2,Dst& dst3)
344{
345 test_transfer(
346 src,dst0,dst1,dst2,dst3,is_key_based<Src>(),is_key_based<Dst>());
347}
348
349void test_transfer()
350{
351 typedef multi_index_container<
352 int,
353 indexed_by<
354 hashed_non_unique<identity<int> >,
355 ordered_non_unique<identity<int> >,
356 random_access<>,
357 sequenced<>,
358 ranked_non_unique<identity<int> >
359 >
360 > container1;
361 typedef multi_index_container<
362 int,
363 indexed_by<
364 hashed_non_unique<identity<int> >,
365 ordered_unique<identity<int>,std::greater<int> >,
366 random_access<>,
367 sequenced<>,
368 ranked_unique<identity<int>,std::greater<int> >
369 >
370 > container2;
371
372 container1 src;
373 container1::nth_index<0>::type& src0=src.get<0>();
374 container1::nth_index<1>::type& src1=src.get<1>();
375 container1::nth_index<2>::type& src2=src.get<2>();
376 container1::nth_index<3>::type& src3=src.get<3>();
377 container1::nth_index<4>::type& src4=src.get<4>();
378 container2 dst0,dst1,dst2,dst3;
379 container2::nth_index<0>::type& dst00=dst0.get<0>(),
380 & dst10=dst1.get<0>(),
381 & dst20=dst2.get<0>(),
382 & dst30=dst3.get<0>();
383 container2::nth_index<1>::type& dst01=dst0.get<1>(),
384 & dst11=dst1.get<1>(),
385 & dst21=dst2.get<1>(),
386 & dst31=dst3.get<1>();
387 container2::nth_index<2>::type& dst02=dst0.get<2>(),
388 & dst12=dst1.get<2>(),
389 & dst22=dst2.get<2>(),
390 & dst32=dst3.get<2>();
391 container2::nth_index<3>::type& dst03=dst0.get<3>(),
392 & dst13=dst1.get<3>(),
393 & dst23=dst2.get<3>(),
394 & dst33=dst3.get<3>();
395 container2::nth_index<4>::type& dst04=dst0.get<4>(),
396 & dst14=dst1.get<4>(),
397 & dst24=dst2.get<4>(),
398 & dst34=dst3.get<4>();
399 for(int i=0;i<6;++i){
400 for(int j=0;j<8;++j)src.insert(x: i);
401 }
402
403 test_transfer(src&: src0,dst0&: dst01,dst1&: dst11,dst2&: dst21,dst3&: dst31);
404 test_transfer(src&: src1,dst0&: dst02,dst1&: dst12,dst2&: dst22,dst3&: dst32);
405 test_transfer(src&: src2,dst0&: dst03,dst1&: dst13,dst2&: dst23,dst3&: dst33);
406 test_transfer(src&: src3,dst0&: dst04,dst1&: dst14,dst2&: dst24,dst3&: dst34);
407 test_transfer(src&: src4,dst0&: dst00,dst1&: dst10,dst2&: dst20,dst3&: dst30);
408 BOOST_TEST(src.size()==8);
409}
410
411template<typename T>
412struct enable_if_key_based:boost::enable_if_c<
413 is_key_based<T>::value,
414 void*
415>{};
416
417template<typename T>
418struct enable_if_not_key_based:boost::enable_if_c<
419 !is_key_based<T>::value,
420 void*
421>{};
422
423/* Boost.Move C++03 perfect forwarding emulation converts non-const lvalue
424 * refs to const lvalue refs. final_forward undoes that.
425 */
426
427#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
428
429template<typename T>
430T&& final_forward(typename boost::remove_reference<T>::type& x)
431{
432 return static_cast<T&&>(x);
433}
434
435#else
436
437template<typename T>
438T& final_forward(const T& x){return const_cast<T&>(x);}
439
440#endif
441
442template<typename Dst,typename Src>
443void merge(
444 Dst& dst,BOOST_FWD_REF(Src) src,
445 typename enable_if_key_based<Dst>::type=0)
446{
447 dst.merge(final_forward<Src>(src));
448}
449
450template<typename Dst,typename Src>
451void merge(
452 Dst& dst,BOOST_FWD_REF(Src) src,
453 typename enable_if_not_key_based<Dst>::type=0)
454{
455 dst.splice(dst.end(),final_forward<Src>(src));
456}
457
458template<typename Dst,typename Src>
459std::pair<typename Dst::iterator,bool> merge(
460 Dst& dst,BOOST_FWD_REF(Src) src,
461 typename boost::remove_reference<Src>::type::iterator i,
462 typename enable_if_key_based<Dst>::type=0)
463{
464 return dst.merge(final_forward<Src>(src),i);
465}
466
467template<typename Dst,typename Src>
468std::pair<typename Dst::iterator,bool> merge(
469 Dst& dst,BOOST_FWD_REF(Src) src,
470 typename boost::remove_reference<Src>::type::iterator i,
471 typename enable_if_not_key_based<Dst>::type=0)
472{
473 return dst.splice(dst.end(),final_forward<Src>(src),i);
474}
475
476template<typename Dst,typename Src>
477void merge(
478 Dst& dst,BOOST_FWD_REF(Src) src,
479 typename boost::remove_reference<Src>::type::iterator first,
480 typename boost::remove_reference<Src>::type::iterator last,
481 typename enable_if_key_based<Dst>::type=0)
482{
483 dst.merge(final_forward<Src>(src),first,last);
484}
485
486template<typename Dst,typename Src>
487void merge(
488 Dst& dst,BOOST_FWD_REF(Src) src,
489 typename boost::remove_reference<Src>::type::iterator first,
490 typename boost::remove_reference<Src>::type::iterator last,
491 typename enable_if_not_key_based<Dst>::type=0)
492{
493 dst.splice(dst.end(),final_forward<Src>(src),first,last);
494}
495
496template<typename Dst,typename Src>
497void test_merge_same(Dst& dst,BOOST_FWD_REF(Src) src)
498{
499 std::size_t n=dst.size();
500 merge(dst,boost::forward<Src>(src));
501 BOOST_TEST(dst.size()==n);
502 BOOST_TEST(src.size()==n);
503}
504
505template<typename Iterator,typename Value>
506bool find_address(Iterator first,Iterator last,const Value* x)
507{
508 while(first!=last)if(&*first++==x)return true;
509 return false;
510}
511
512template<typename Dst,typename Src>
513void test_merge_different(
514 Dst& dst,BOOST_FWD_REF(Src) src,bool transferred_iters)
515{
516 typedef typename boost::remove_reference<Src>::
517 type::iterator src_iterator;
518 typedef typename boost::remove_reference<Src>::
519 type::value_type src_value_type;
520
521 std::size_t n=dst.size(),m=src.size();
522 std::vector<
523 std::pair<src_iterator,const src_value_type*>
524 > v;
525 for(src_iterator first=src.begin(),last=src.end();first!=last;++first){
526 v.push_back(std::make_pair(first,&*first));
527 }
528
529 merge(dst,boost::forward<Src>(src));
530 BOOST_TEST(dst.size()>=n && m>=src.size() && dst.size()-n==m-src.size());
531 for(std::size_t i=0;i<v.size();++i){
532 BOOST_TEST(
533 find_address(src.begin(),src.end(),v[i].second)||
534 find_address(dst.begin(),dst.end(),v[i].second));
535 }
536 if(transferred_iters){
537 for(std::size_t i=0;i<v.size();++i){
538 BOOST_TEST(&*(v[i].first)==v[i].second);
539 }
540 }
541}
542
543template<typename Dst,typename Src>
544void test_merge_same(
545 Dst& dst,BOOST_FWD_REF(Src) src,
546 typename boost::remove_reference<Src>::type::iterator i,
547 bool key_based=is_key_based<Dst>::value)
548{
549 typedef typename Dst::iterator dst_iterator;
550
551 std::size_t n=dst.size();
552
553 std::pair<dst_iterator,bool> p=merge(dst,boost::forward<Src>(src),i);
554 BOOST_TEST(dst.size()==n);
555 BOOST_TEST(src.size()==n);
556 BOOST_TEST(&*(p.first)==&*i && p.second);
557 if(!key_based)BOOST_TEST(boost::next(p.first)==dst.end());
558}
559
560template<typename Dst,typename Src>
561void test_merge_different(
562 Dst& dst,BOOST_FWD_REF(Src) src,
563 typename boost::remove_reference<Src>::type::iterator i,
564 bool key_based=is_key_based<Dst>::value)
565{
566 typedef typename Dst::iterator dst_iterator;
567
568 std::size_t n=dst.size(),m=src.size();
569 const typename Dst::value_type* pi=&*i;
570
571 std::pair<dst_iterator,bool> p=merge(dst,boost::forward<Src>(src),i);
572 BOOST_TEST(dst.size()+src.size()==n+m);
573 BOOST_TEST(p.second?
574 &*(p.first)==pi:
575 &*(p.first)!=pi && *(p.first)==*i);
576 if(!key_based)BOOST_TEST(!p.second || boost::next(p.first)==dst.end());
577}
578
579template<typename Dst,typename Src>
580void test_merge_same(
581 Dst& dst,BOOST_FWD_REF(Src) src,
582 typename boost::remove_reference<Src>::type::iterator first,
583 typename boost::remove_reference<Src>::type::iterator last,
584 bool key_based=is_key_based<Dst>::value)
585{
586 typedef typename Dst::iterator dst_iterator;
587 typedef typename boost::remove_reference<Src>::
588 type::iterator src_iterator;
589 typedef typename boost::remove_reference<Src>::
590 type::value_type src_value_type;
591
592 std::size_t n=dst.size(),d=std::distance(first,last);
593 std::vector<const src_value_type*> v;
594 for(src_iterator it=first;it!=last;++it)v.push_back(&*it);
595
596 merge(dst,boost::forward<Src>(src),first,last);
597 BOOST_TEST(dst.size()==n);
598 BOOST_TEST(src.size()==n);
599 if(!key_based){
600 dst_iterator it=boost::next(dst.begin(),(std::ptrdiff_t)(dst.size()-d));
601 for(std::size_t i=0;i<d;++i){
602 BOOST_TEST(&*it++==v[i]);
603 }
604 }
605 else{
606 src_iterator it=first;
607 for(std::size_t i=0;i<d;++i){
608 BOOST_TEST(&*it++==v[i]);
609 }
610 }
611}
612
613template<typename Dst,typename Src>
614void test_merge_different(
615 Dst& dst,BOOST_FWD_REF(Src) src,
616 typename boost::remove_reference<Src>::type::iterator first,
617 typename boost::remove_reference<Src>::type::iterator last,
618 bool key_based=is_key_based<Dst>::value)
619{
620 typedef typename Dst::iterator dst_iterator;
621 typedef typename boost::remove_reference<Src>::
622 type::iterator src_iterator;
623 typedef typename boost::remove_reference<Src>::
624 type::value_type src_value_type;
625
626 std::size_t n=dst.size(),
627 m=src.size();
628 std::vector<const src_value_type*> v;
629 for(src_iterator it=first;it!=last;++it)v.push_back(&*it);
630
631 merge(dst,boost::forward<Src>(src),first,last);
632 BOOST_TEST(dst.size()>=n && m>=src.size() && dst.size()-n==m-src.size());
633 if(!key_based){
634 for(dst_iterator it=boost::next(dst.begin(),(std::ptrdiff_t)n);
635 it!=dst.end();++it){
636 BOOST_TEST(std::find(v.begin(),v.end(),&*it)!=v.end());
637 }
638 }
639 for(std::size_t i=0;i<v.size();++i){
640 BOOST_TEST(
641 find_address(src.begin(),src.end(),v[i])||
642 find_address(dst.begin(),dst.end(),v[i]));
643 }
644}
645
646template<int N,int M,typename Dst>
647void test_merge_same(Dst& dst)
648{
649 const Dst dst1=dst;
650 {
651 Dst dst2=dst1;
652 test_merge_same(
653 dst2.template get<N>(),dst2.template get<M>());
654 test_merge_same(
655 dst2.template get<N>(),boost::move(dst2.template get<M>()));
656 }
657 {
658 Dst dst2=dst1;
659 test_merge_same(
660 dst2.template get<N>(),dst2.template get<M>(),
661 boost::next(
662 dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2)));
663 test_merge_same(
664 dst2.template get<N>(),boost::move(dst2.template get<M>()),
665 boost::next(
666 dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2)));
667 }
668 {
669 Dst dst2=dst1;
670 test_merge_same(
671 dst2.template get<N>(),dst2.template get<M>(),
672 dst2.template get<M>().begin(),
673 boost::next(
674 dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2)));
675 test_merge_same(
676 dst2.template get<N>(),boost::move(dst2.template get<M>()),
677 dst2.template get<M>().begin(),
678 boost::next(
679 dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2)));
680 }
681}
682
683template<int N,int M,typename Dst,typename Src>
684void test_merge_different(Dst& dst,Src& src)
685{
686 const Dst dst1=dst;
687 const Src src1=src;
688 const bool transferred_iters=
689 boost::is_same<
690 typename boost::multi_index::nth_index<Dst,M>::type::iterator,
691 typename boost::multi_index::nth_index<Src,M>::type::iterator>::value;
692 {
693 Dst dst2=dst1;
694 Src src2=src1;
695 test_merge_different(
696 dst2.template get<N>(),src2.template get<M>(),transferred_iters);
697 }
698 {
699 Dst dst2=dst1;
700 Src src2=src1;
701 test_merge_different(
702 dst2.template get<N>(),boost::move(src2.template get<M>()),
703 transferred_iters);
704 }
705 {
706 Dst dst2=dst1;
707 Src src2=src1;
708 test_merge_different(
709 dst2.template get<N>(),src2.template get<M>(),
710 boost::next(
711 src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2)));
712 }
713 {
714 Dst dst2=dst1;
715 Src src2=src1;
716 test_merge_different(
717 dst2.template get<N>(),boost::move(src2.template get<M>()),
718 boost::next(
719 src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2)));
720 }
721 {
722 Dst dst2=dst1;
723 Src src2=src1;
724 test_merge_different(
725 dst2.template get<N>(),src2.template get<M>(),
726 src2.template get<M>().begin(),
727 boost::next(
728 src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2)));
729 }
730 {
731 Dst dst2=dst1;
732 Src src2=src1;
733 test_merge_different(
734 dst2.template get<N>(),boost::move(src2.template get<M>()),
735 src2.template get<M>().begin(),
736 boost::next(
737 src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2)));
738 }
739}
740
741template<int N,int M,typename Dst,typename Src>
742void test_merge(Dst& dst,Src& src)
743{
744 test_merge_different<N,M>(dst,src);
745}
746
747template<int N,int M,typename Dst>
748void test_merge(Dst& dst,Dst& src)
749{
750 if(&dst==&src)test_merge_same<N,M>(dst);
751 else test_merge_different<N,M>(dst,src);
752}
753
754struct another_int_hash
755{
756 std::size_t operator()(int x)const
757 {
758 return boost::hash<int>()(x)*2;
759 }
760};
761
762void test_merge()
763{
764 typedef multi_index_container<
765 int,
766 indexed_by<
767 ordered_non_unique<identity<int> >,
768 hashed_non_unique<identity<int> >,
769 random_access<>,
770 sequenced<>,
771 ranked_non_unique<identity<int> >
772 >
773 > container1;
774
775 typedef multi_index_container<
776 int,
777 indexed_by<
778 ordered_unique<
779 identity<int>,
780 std::greater<int>
781 >,
782 hashed_unique<
783 identity<int>,
784 another_int_hash
785 >,
786 random_access<>,
787 sequenced<>,
788 ranked_unique<
789 identity<int>,
790 std::greater<int>
791 >
792 >
793 > container2;
794
795 container1 c1;
796 container2 c2;
797 for(int i=0;i<10;++i){
798 c1.insert(x: i);
799 c2.insert(x: 2*i);
800 }
801
802 test_merge<0,1>(dst&: c1,src&: c1);
803 test_merge<1,2>(dst&: c1,src&: c1);
804 test_merge<2,3>(dst&: c1,src&: c1);
805 test_merge<3,4>(dst&: c1,src&: c1);
806 test_merge<4,0>(dst&: c1,src&: c1);
807 test_merge<0,3>(dst&: c2,src&: c2);
808 test_merge<1,4>(dst&: c2,src&: c2);
809 test_merge<4,2>(dst&: c2,src&: c2);
810
811 test_merge<0,1>(dst&: c1,src&: c2);
812 test_merge<1,2>(dst&: c1,src&: c2);
813 test_merge<2,3>(dst&: c1,src&: c2);
814 test_merge<3,4>(dst&: c1,src&: c2);
815 test_merge<4,0>(dst&: c1,src&: c2);
816 test_merge<0,3>(dst&: c2,src&: c1);
817 test_merge<1,4>(dst&: c2,src&: c1);
818 test_merge<4,2>(dst&: c2,src&: c1);
819}
820
821void test_node_handling()
822{
823 test_node_handle();
824 test_transfer();
825 test_merge();
826}
827

source code of boost/libs/multi_index/test/test_node_handling.cpp