1 /* Boost.MultiIndex test for node handling operations.
2 *
3 * Copyright 2003-2020 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/integral_constant.hpp>
27 #include <functional>
28 #include "count_allocator.hpp"
29
30 using namespace boost::multi_index;
31
test_node_handle()32 void test_node_handle()
33 {
34 typedef count_allocator<int> allocator;
35 typedef multi_index_container<
36 int,
37 indexed_by<
38 ordered_unique<identity<int> >
39 >,
40 allocator
41 > container;
42 typedef container::node_type node_type;
43
44 std::size_t element_count=0,allocator_count=0;
45 container c((allocator(element_count,allocator_count)));
46
47 element_count=0; /* ignore non element-related allocations */
48 allocator_count=0; /* ignore internal allocator(s) */
49
50 c.insert(0);
51 c.insert(1);
52 c.insert(2);
53 const int* addr0=&*c.find(0);
54 const int* addr1=&*c.find(1);
55 BOOST_TEST(element_count==3);
56
57 node_type n1;
58 BOOST_TEST(n1.empty());
59 BOOST_TEST(!n1);
60 BOOST_TEST(allocator_count==0);
61
62 node_type n2=c.extract(0);
63 BOOST_TEST(!n2.empty());
64 BOOST_TEST((bool)n2);
65 BOOST_TEST(n2.value()==0);
66 BOOST_TEST(&n2.value()==addr0);
67 BOOST_TEST(allocator_count==1);
68
69 node_type n3(boost::move(n2));
70 BOOST_TEST(n2.empty());
71 BOOST_TEST(!n3.empty());
72 BOOST_TEST(&n3.value()==addr0);
73 BOOST_TEST(allocator_count==1);
74
75 node_type n4(boost::move(n2));
76 BOOST_TEST(n4.empty());
77 BOOST_TEST(allocator_count==1);
78
79 n1=boost::move(n3);
80 BOOST_TEST(!n1.empty());
81 BOOST_TEST(&n1.value()==addr0);
82 BOOST_TEST(n3.empty());
83 BOOST_TEST(allocator_count==1);
84
85 BOOST_TEST(n1.get_allocator()==c.get_allocator());
86
87 node_type n5=c.extract(1);
88 BOOST_TEST(n5.value()==1);
89 BOOST_TEST(&n5.value()==addr1);
90 BOOST_TEST(allocator_count==2);
91
92 n1.swap(n5);
93 BOOST_TEST(&n1.value()==addr1);
94 BOOST_TEST(&n5.value()==addr0);
95 BOOST_TEST(allocator_count==2);
96
97 using std::swap;
98
99 swap(n2,n3);
100 BOOST_TEST(n2.empty());
101 BOOST_TEST(n3.empty());
102 BOOST_TEST(allocator_count==2);
103
104 swap(n1,n2);
105 BOOST_TEST(!n2.empty());
106 BOOST_TEST(&n2.value()==addr1);
107 BOOST_TEST(allocator_count==2);
108
109 swap(n1,n2);
110 BOOST_TEST(&n1.value()==addr1);
111 BOOST_TEST(n2.empty());
112 BOOST_TEST(allocator_count==2);
113
114 n2=boost::move(n3);
115 BOOST_TEST(n2.empty());
116 BOOST_TEST(n3.empty());
117 BOOST_TEST(allocator_count==2);
118
119 BOOST_TEST(element_count==3);
120 n1=boost::move(n5);
121 BOOST_TEST(&n1.value()==addr0);
122 BOOST_TEST(n5.empty());
123 BOOST_TEST(element_count==2);
124 BOOST_TEST(allocator_count==1);
125
126 n1=boost::move(n5);
127 BOOST_TEST(n1.empty());
128 BOOST_TEST(element_count==1);
129 BOOST_TEST(allocator_count==0);
130
131 c.extract(2);
132 BOOST_TEST(element_count==0);
133 }
134
135 template<typename Index>
136 struct is_key_based:boost::integral_constant<
137 bool,
138 /* rather fragile if new index types are included in the library */
139 (boost::tuples::length<typename Index::ctor_args>::value > 0)
140 >
141 {};
142
143 template<typename T>
144 struct is_iterator
145 {
146 typedef char yes;
147 struct no{char m[2];};
148
149 template<typename Q> static no test(...);
150 template<typename Q> static yes test(typename Q::iterator_category*);
151
152 BOOST_STATIC_CONSTANT(bool,value=(sizeof(test<T>(0))==sizeof(yes)));
153 };
154
155 template<typename T>
156 struct enable_if_not_iterator:boost::enable_if_c<
157 !is_iterator<T>::value,
158 void*
159 >{};
160
161 template<typename Dst,typename Ret,typename NodeHandle,typename Value>
test_transfer_result(Dst &,Ret res,const NodeHandle & n,const Value & x,typename enable_if_not_iterator<Ret>::type=0)162 void test_transfer_result(
163 Dst&,Ret res,const NodeHandle& n,const Value& x,
164 typename enable_if_not_iterator<Ret>::type=0)
165 {
166 BOOST_TEST(*(res.position)==x);
167 if(res.inserted){
168 BOOST_TEST(res.node.empty());
169 }
170 else{
171 BOOST_TEST(res.node.value()==x);
172 }
173 BOOST_TEST(n.empty());
174 }
175
176 template<typename Dst,typename NodeHandle,typename Value>
test_transfer_result(Dst &,typename Dst::iterator res,const NodeHandle & n,const Value & x)177 void test_transfer_result(
178 Dst&,typename Dst::iterator res,const NodeHandle& n,const Value& x)
179 {
180 BOOST_TEST(*res==x);
181 if(n)BOOST_TEST(n.value()==x);
182 }
183
184 template<typename Dst,typename Ret>
test_transfer_result_empty(Dst & dst,Ret res,typename enable_if_not_iterator<Ret>::type=0)185 void test_transfer_result_empty(
186 Dst& dst,Ret res,
187 typename enable_if_not_iterator<Ret>::type=0)
188 {
189 BOOST_TEST(res.position==dst.end());
190 BOOST_TEST(!res.inserted);
191 BOOST_TEST(res.node.empty());
192 }
193
194 template<typename Dst>
test_transfer_result_empty(Dst & dst,typename Dst::iterator res)195 void test_transfer_result_empty(Dst& dst,typename Dst::iterator res)
196 {
197 BOOST_TEST(res==dst.end());
198 }
199
200 template<typename Dst,typename Ret,typename NodeHandle,typename Value>
test_transfer_result(Dst & dst,typename Dst::iterator pos,Ret res,const NodeHandle & n,const Value & x,typename enable_if_not_iterator<Ret>::type=0)201 void test_transfer_result(
202 Dst& dst,typename Dst::iterator pos,Ret res,
203 const NodeHandle& n,const Value& x,
204 typename enable_if_not_iterator<Ret>::type=0)
205 {
206 if(res.inserted&&pos!=dst.end()&&
207 (!is_key_based<Dst>::value||*pos==x)){
208 BOOST_TEST(boost::next(res.position)==pos);
209 }
210 test_transfer_result(dst,Ret(boost::move(res)),n,x);
211 }
212
213 template<typename Dst,typename NodeHandle,typename Value>
test_transfer_result(Dst & dst,typename Dst::iterator pos,typename Dst::iterator res,const NodeHandle & n,const Value & x)214 void test_transfer_result(
215 Dst& dst,typename Dst::iterator pos,
216 typename Dst::iterator res,const NodeHandle& n,const Value& x)
217 {
218 if(n.empty()&&pos!=dst.end()&&
219 (!is_key_based<Dst>::value||*pos==x)){
220 BOOST_TEST(boost::next(res)==pos);
221 }
222 test_transfer_result(dst,res,n,x);
223 }
224
225 template<typename Dst,typename Ret>
test_transfer_result_empty(Dst & dst,typename Dst::iterator,Ret res,typename enable_if_not_iterator<Ret>::type=0)226 void test_transfer_result_empty(
227 Dst& dst,typename Dst::iterator,Ret res,
228 typename enable_if_not_iterator<Ret>::type=0)
229 {
230 test_transfer_result_empty(dst,Ret(boost::move(res)));
231 }
232
233 template<typename Dst>
test_transfer_result_empty(Dst & dst,typename Dst::iterator,typename Dst::iterator res)234 void test_transfer_result_empty(
235 Dst& dst,typename Dst::iterator,typename Dst::iterator res)
236 {
237 test_transfer_result_empty(dst,res);
238 }
239
240 template<typename Src,typename Key>
checked_extract(Src & src,Key k,typename enable_if_not_iterator<Key>::type=0)241 typename Src::node_type checked_extract(
242 Src& src,Key k,
243 typename enable_if_not_iterator<Key>::type=0)
244 {
245 typename Src::node_type n=src.extract(k);
246 if(n)BOOST_TEST(src.key_extractor()(n.value())==k);
247 return boost::move(n);
248 }
249
250 template<typename Src>
checked_extract(Src & src,typename Src::iterator pos)251 typename Src::node_type checked_extract(Src& src,typename Src::iterator pos)
252 {
253 typename Src::value_type x=*pos;
254 typename Src::node_type n=src.extract(pos);
255 if(n)BOOST_TEST(n.value()==x);
256 return boost::move(n);
257 }
258
259 template<typename Src,typename Locator,typename Dst>
test_transfer(Src & src,Locator loc,Dst & dst)260 void test_transfer(Src& src,Locator loc,Dst& dst)
261 {
262 typename Dst::node_type n=checked_extract(src,loc);
263 if(n){
264 typename Dst::value_type x=n.value();
265 test_transfer_result(dst,dst.insert(boost::move(n)),n,x);
266 }
267 else{
268 test_transfer_result_empty(dst,dst.insert(boost::move(n)));
269 }
270 }
271
272 template<typename Src,typename Locator,typename Dst,typename Iterator>
test_transfer(Src & src,Locator loc,Dst & dst,Iterator pos)273 void test_transfer(Src& src,Locator loc,Dst& dst,Iterator pos)
274 {
275 typename Dst::node_type n=checked_extract(src,loc);
276 if(n){
277 typename Dst::value_type x=n.value();
278 test_transfer_result(dst,pos,dst.insert(pos,boost::move(n)),n,x);
279 }
280 else{
281 test_transfer_result_empty(dst,pos,dst.insert(pos,boost::move(n)));
282 }
283 }
284
285 template<typename Src,typename Dst>
test_transfer(Src & src,Dst & dst0,Dst &,Dst &,Dst &,boost::false_type,boost::false_type)286 void test_transfer(
287 Src& src,Dst& dst0,Dst& /* dst1 */,Dst& /* dst2 */,Dst& /* dst3 */,
288 boost::false_type /* Src key-based */,boost::false_type /* Dst key-based */)
289 {
290 test_transfer(src,src.begin(),dst0,dst0.begin());
291 test_transfer(src,src.begin(),dst0,dst0.begin());
292 for(int i=0;i<6;++i)src.extract(src.begin());
293 }
294
295 template<typename Src,typename Dst>
test_transfer(Src & src,Dst & dst0,Dst & dst1,Dst &,Dst &,boost::false_type,boost::true_type)296 void test_transfer(
297 Src& src,Dst& dst0,Dst& dst1,Dst& /* dst2 */,Dst& /* dst3 */,
298 boost::false_type /* Src key-based */,boost::true_type /* Dst key-based */)
299 {
300 test_transfer(src,src.begin(),dst0);
301 test_transfer(src,src.begin(),dst0);
302 test_transfer(src,src.begin(),dst1,dst1.find(*src.begin()));
303 test_transfer(src,src.begin(),dst1,dst1.find(*src.begin()));
304 for(int i=0;i<4;++i)src.extract(src.begin());
305 }
306
307 template<typename Src,typename Dst>
test_transfer(Src & src,Dst & dst0,Dst & dst1,Dst &,Dst &,boost::true_type,boost::false_type)308 void test_transfer(
309 Src& src,Dst& dst0,Dst& dst1,Dst& /* dst2 */,Dst& /* dst3 */,
310 boost::true_type /* Src key-based */,boost::false_type /* Dst key-based */)
311 {
312 test_transfer(src, src.begin(),dst0,dst0.begin());
313 test_transfer(src, src.begin(),dst0,dst0.begin());
314 test_transfer(src,*src.begin(),dst1,dst1.begin());
315 test_transfer(src,*src.begin(),dst1,dst1.begin());
316 test_transfer(src, -1,dst1,dst1.begin());
317 for(int i=0;i<4;++i)src.extract(src.begin());
318 }
319
320 template<typename Src,typename Dst>
test_transfer(Src & src,Dst & dst0,Dst & dst1,Dst & dst2,Dst & dst3,boost::true_type,boost::true_type)321 void test_transfer(
322 Src& src,Dst& dst0,Dst& dst1,Dst& dst2,Dst& dst3,
323 boost::true_type /* Src key-based */,boost::true_type /* Dst key-based */)
324 {
325 test_transfer(src, src.begin(),dst0);
326 test_transfer(src, src.begin(),dst0);
327 test_transfer(src,*src.begin(),dst1);
328 test_transfer(src,*src.begin(),dst1);
329 test_transfer(src, -1,dst1);
330 test_transfer(src, src.begin(),dst2,dst2.find(*src.begin()));
331 test_transfer(src, src.begin(),dst2,dst2.find(*src.begin()));
332 test_transfer(src,*src.begin(),dst3,dst3.find(*src.begin()));
333 test_transfer(src,*src.begin(),dst3,dst3.find(*src.begin()));
334 test_transfer(src, -1,dst3,dst3.begin());
335 }
336
337 template<typename Src,typename Dst>
test_transfer(Src & src,Dst & dst0,Dst & dst1,Dst & dst2,Dst & dst3)338 void test_transfer(Src& src,Dst& dst0,Dst& dst1,Dst& dst2,Dst& dst3)
339 {
340 test_transfer(
341 src,dst0,dst1,dst2,dst3,is_key_based<Src>(),is_key_based<Dst>());
342 }
343
test_transfer()344 void test_transfer()
345 {
346 typedef multi_index_container<
347 int,
348 indexed_by<
349 hashed_non_unique<identity<int> >,
350 ordered_non_unique<identity<int> >,
351 random_access<>,
352 sequenced<>,
353 ranked_non_unique<identity<int> >
354 >
355 > container1;
356 typedef multi_index_container<
357 int,
358 indexed_by<
359 hashed_non_unique<identity<int> >,
360 ordered_unique<identity<int>,std::greater<int> >,
361 random_access<>,
362 sequenced<>,
363 ranked_unique<identity<int>,std::greater<int> >
364 >
365 > container2;
366
367 container1 src;
368 container1::nth_index<0>::type& src0=src.get<0>();
369 container1::nth_index<1>::type& src1=src.get<1>();
370 container1::nth_index<2>::type& src2=src.get<2>();
371 container1::nth_index<3>::type& src3=src.get<3>();
372 container1::nth_index<4>::type& src4=src.get<4>();
373 container2 dst0,dst1,dst2,dst3;
374 container2::nth_index<0>::type& dst00=dst0.get<0>(),
375 & dst10=dst1.get<0>(),
376 & dst20=dst2.get<0>(),
377 & dst30=dst3.get<0>();
378 container2::nth_index<1>::type& dst01=dst0.get<1>(),
379 & dst11=dst1.get<1>(),
380 & dst21=dst2.get<1>(),
381 & dst31=dst3.get<1>();
382 container2::nth_index<2>::type& dst02=dst0.get<2>(),
383 & dst12=dst1.get<2>(),
384 & dst22=dst2.get<2>(),
385 & dst32=dst3.get<2>();
386 container2::nth_index<3>::type& dst03=dst0.get<3>(),
387 & dst13=dst1.get<3>(),
388 & dst23=dst2.get<3>(),
389 & dst33=dst3.get<3>();
390 container2::nth_index<4>::type& dst04=dst0.get<4>(),
391 & dst14=dst1.get<4>(),
392 & dst24=dst2.get<4>(),
393 & dst34=dst3.get<4>();
394 for(int i=0;i<6;++i){
395 for(int j=0;j<8;++j)src.insert(i);
396 }
397
398 test_transfer(src0,dst01,dst11,dst21,dst31);
399 test_transfer(src1,dst02,dst12,dst22,dst32);
400 test_transfer(src2,dst03,dst13,dst23,dst33);
401 test_transfer(src3,dst04,dst14,dst24,dst34);
402 test_transfer(src4,dst00,dst10,dst20,dst30);
403 BOOST_TEST(src.size()==8);
404 }
405
test_node_handling()406 void test_node_handling()
407 {
408 test_node_handle();
409 test_transfer();
410 }
411