]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2007-2013 | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | // | |
9 | // See http://www.boost.org/libs/intrusive for documentation. | |
10 | // | |
11 | ///////////////////////////////////////////////////////////////////////////// | |
12 | ||
13 | #ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP | |
14 | #define BOOST_INTRUSIVE_TEST_CONTAINER_HPP | |
15 | ||
16 | #include <boost/detail/lightweight_test.hpp> | |
17 | #include <boost/intrusive/detail/mpl.hpp> | |
18 | #include <boost/intrusive/detail/simple_disposers.hpp> | |
19 | #include <boost/intrusive/detail/iterator.hpp> | |
20 | #include <boost/move/utility_core.hpp> | |
b32b8144 | 21 | #include <boost/move/adl_move_swap.hpp> |
7c673cae FG |
22 | #include <boost/intrusive/detail/mpl.hpp> |
23 | #include <boost/static_assert.hpp> | |
24 | #include "iterator_test.hpp" | |
b32b8144 | 25 | #include <cstdlib> |
7c673cae FG |
26 | |
27 | namespace boost { | |
28 | namespace intrusive { | |
29 | namespace test { | |
30 | ||
31 | BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(is_unordered, hasher) | |
32 | ||
33 | template<class Container> | |
34 | struct test_container_typedefs | |
35 | { | |
36 | typedef typename Container::value_type value_type; | |
37 | typedef typename Container::iterator iterator; | |
38 | typedef typename Container::const_iterator const_iterator; | |
39 | typedef typename Container::reference reference; | |
40 | typedef typename Container::const_reference const_reference; | |
41 | typedef typename Container::pointer pointer; | |
42 | typedef typename Container::const_pointer const_pointer; | |
43 | typedef typename Container::difference_type difference_type; | |
44 | typedef typename Container::size_type size_type; | |
45 | typedef typename Container::value_traits value_traits; | |
46 | }; | |
47 | ||
48 | template< class Container > | |
49 | void test_container( Container & c ) | |
50 | { | |
51 | typedef typename Container::const_iterator const_iterator; | |
52 | typedef typename Container::iterator iterator; | |
53 | typedef typename Container::size_type size_type; | |
54 | ||
55 | {test_container_typedefs<Container> dummy; (void)dummy;} | |
56 | const size_type num_elem = c.size(); | |
57 | BOOST_TEST( c.empty() == (num_elem == 0) ); | |
58 | { | |
59 | iterator it(c.begin()), itend(c.end()); | |
60 | size_type i; | |
61 | for(i = 0; i < num_elem; ++i){ | |
62 | ++it; | |
63 | } | |
64 | BOOST_TEST( it == itend ); | |
65 | BOOST_TEST( c.size() == i ); | |
66 | } | |
67 | ||
68 | //Check iterator conversion | |
69 | BOOST_TEST(const_iterator(c.begin()) == c.cbegin() ); | |
70 | { | |
71 | const_iterator it(c.cbegin()), itend(c.cend()); | |
72 | size_type i; | |
73 | for(i = 0; i < num_elem; ++i){ | |
74 | ++it; | |
75 | } | |
76 | BOOST_TEST( it == itend ); | |
77 | BOOST_TEST( c.size() == i ); | |
78 | } | |
79 | static_cast<const Container&>(c).check(); | |
80 | //Very basic test for comparisons | |
81 | { | |
82 | BOOST_TEST(c == c); | |
83 | BOOST_TEST(!(c != c)); | |
84 | BOOST_TEST(!(c < c)); | |
85 | BOOST_TEST(c <= c); | |
86 | BOOST_TEST(!(c > c)); | |
87 | BOOST_TEST(c >= c); | |
88 | } | |
89 | } | |
90 | ||
91 | ||
92 | template< class Container, class Data > | |
93 | void test_sequence_container(Container & c, Data & d) | |
94 | { | |
95 | assert( d.size() > 2 ); | |
96 | { | |
97 | c.clear(); | |
98 | ||
99 | BOOST_TEST( c.size() == 0 ); | |
100 | BOOST_TEST( c.empty() ); | |
101 | ||
102 | ||
103 | { | |
104 | typename Data::iterator i = d.begin(); | |
105 | c.insert( c.begin(), *i ); | |
106 | BOOST_TEST( &*c.iterator_to(*c.begin()) == &*i ); | |
107 | BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &*i ); | |
108 | BOOST_TEST( &*Container::s_iterator_to(*c.begin()) == &*i ); | |
109 | BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &*i ); | |
110 | c.insert( c.end(), *(++i) ); | |
111 | } | |
112 | BOOST_TEST( c.size() == 2 ); | |
113 | BOOST_TEST( !c.empty() ); | |
114 | ||
115 | typename Container::iterator i; | |
116 | i = c.erase( c.begin() ); | |
117 | ||
118 | BOOST_TEST( c.size() == 1 ); | |
119 | BOOST_TEST( !c.empty() ); | |
120 | ||
121 | i = c.erase( c.begin() ); | |
122 | ||
123 | BOOST_TEST( c.size() == 0 ); | |
124 | BOOST_TEST( c.empty() ); | |
125 | ||
126 | c.insert( c.begin(), *d.begin() ); | |
127 | ||
128 | BOOST_TEST( c.size() == 1 ); | |
129 | BOOST_TEST( !c.empty() ); | |
130 | ||
131 | { | |
132 | typename Data::iterator di = d.begin(); | |
133 | ++++di; | |
134 | c.insert( c.begin(), *(di) ); | |
135 | } | |
136 | ||
137 | i = c.erase( c.begin(), c.end() ); | |
138 | BOOST_TEST( i == c.end() ); | |
139 | ||
140 | BOOST_TEST( c.empty() ); | |
141 | ||
142 | c.insert( c.begin(), *d.begin() ); | |
143 | ||
144 | BOOST_TEST( c.size() == 1 ); | |
145 | ||
146 | BOOST_TEST( c.begin() != c.end() ); | |
147 | ||
148 | i = c.erase_and_dispose( c.begin(), detail::null_disposer() ); | |
149 | BOOST_TEST( i == c.begin() ); | |
150 | ||
151 | c.assign(d.begin(), d.end()); | |
152 | ||
153 | BOOST_TEST( c.size() == d.size() ); | |
154 | ||
155 | c.clear(); | |
156 | ||
157 | BOOST_TEST( c.size() == 0 ); | |
158 | BOOST_TEST( c.empty() ); | |
159 | } | |
160 | { | |
161 | c.clear(); | |
162 | c.insert( c.begin(), d.begin(), d.end() ); | |
163 | Container move_c(::boost::move(c)); | |
164 | BOOST_TEST( move_c.size() == d.size() ); | |
165 | BOOST_TEST( c.empty()); | |
166 | ||
167 | c = ::boost::move(move_c); | |
168 | BOOST_TEST( c.size() == d.size() ); | |
169 | BOOST_TEST( move_c.empty()); | |
170 | } | |
171 | } | |
172 | ||
173 | template< class Container, class Data > | |
174 | void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::true_ unordered) | |
175 | { | |
176 | (void)unordered; | |
177 | typedef typename Container::size_type size_type; | |
178 | typedef typename Container::key_of_value key_of_value; | |
179 | typedef typename Container::iterator iterator; | |
180 | typedef typename Container::const_iterator const_iterator; | |
181 | ||
182 | assert( d.size() > 2 ); | |
183 | ||
184 | c.clear(); | |
185 | c.insert(d.begin(), d.end()); | |
186 | ||
187 | { | |
188 | Container const &cc = c; | |
189 | for( typename Data::const_iterator di = d.begin(), de = d.end(); | |
190 | di != de; ++di ) | |
191 | { | |
192 | BOOST_TEST( cc.find(key_of_value()(*di), c.hash_function(), c.key_eq()) != cc.end() ); | |
193 | std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.hash_function(), c.key_eq()); | |
194 | BOOST_TEST(rdi.first != rdi.second); | |
195 | BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.hash_function(), c.key_eq())); | |
196 | } | |
197 | ||
198 | for( iterator ci = c.begin(), ce = c.end(); ci != ce; ) | |
199 | { | |
200 | BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() ); | |
201 | std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.hash_function(), c.key_eq()); | |
202 | BOOST_TEST(rci.first != rci.second); | |
203 | size_type const sc = c.count(key_of_value()(*ci), c.hash_function(), c.key_eq()); | |
204 | BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc); | |
205 | BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.hash_function(), c.key_eq())); | |
206 | ci = rci.second; | |
207 | } | |
208 | BOOST_TEST(c.empty()); | |
209 | } | |
210 | ||
211 | c.clear(); | |
212 | c.insert(d.begin(), d.end()); | |
213 | ||
214 | typename Data::const_iterator db = d.begin(); | |
215 | typename Data::const_iterator da = db++; | |
216 | ||
217 | size_type old_size = c.size(); | |
218 | ||
219 | c.erase(key_of_value()(*da), c.hash_function(), c.key_eq()); | |
220 | BOOST_TEST( c.size() == old_size-1 ); | |
221 | //This should not eras anyone | |
222 | size_type second_erase = c.erase_and_dispose | |
223 | ( key_of_value()(*da), c.hash_function(), c.key_eq(), detail::null_disposer() ); | |
224 | BOOST_TEST( second_erase == 0 ); | |
225 | ||
226 | BOOST_TEST( c.count(key_of_value()(*da), c.hash_function(), c.key_eq()) == 0 ); | |
227 | BOOST_TEST( c.count(key_of_value()(*db), c.hash_function(), c.key_eq()) != 0 ); | |
228 | ||
229 | BOOST_TEST( c.find(key_of_value()(*da), c.hash_function(), c.key_eq()) == c.end() ); | |
230 | BOOST_TEST( c.find(key_of_value()(*db), c.hash_function(), c.key_eq()) != c.end() ); | |
231 | ||
232 | BOOST_TEST( c.equal_range(key_of_value()(*db), c.hash_function(), c.key_eq()).first != c.end() ); | |
233 | ||
234 | c.clear(); | |
235 | ||
236 | BOOST_TEST( c.equal_range(key_of_value()(*da), c.hash_function(), c.key_eq()).first == c.end() ); | |
237 | ||
238 | // | |
239 | //suggested_upper_bucket_count | |
240 | // | |
241 | //Maximum fallbacks to the highest possible value | |
242 | typename Container::size_type sz = Container::suggested_upper_bucket_count(size_type(-1)); | |
243 | BOOST_TEST( sz > size_type(-1)/2 ); | |
244 | //In the rest of cases the upper bound is returned | |
245 | sz = Container::suggested_upper_bucket_count(size_type(-1)/2); | |
246 | BOOST_TEST( sz >= size_type(-1)/2 ); | |
247 | sz = Container::suggested_upper_bucket_count(size_type(-1)/4); | |
248 | BOOST_TEST( sz >= size_type(-1)/4 ); | |
249 | sz = Container::suggested_upper_bucket_count(0); | |
250 | BOOST_TEST( sz > 0 ); | |
251 | // | |
252 | //suggested_lower_bucket_count | |
253 | // | |
254 | sz = Container::suggested_lower_bucket_count(size_type(-1)); | |
255 | BOOST_TEST( sz <= size_type(-1) ); | |
256 | //In the rest of cases the lower bound is returned | |
257 | sz = Container::suggested_lower_bucket_count(size_type(-1)/2); | |
258 | BOOST_TEST( sz <= size_type(-1)/2 ); | |
259 | sz = Container::suggested_lower_bucket_count(size_type(-1)/4); | |
260 | BOOST_TEST( sz <= size_type(-1)/4 ); | |
261 | //Minimum fallbacks to the lowest possible value | |
262 | sz = Container::suggested_upper_bucket_count(0); | |
263 | BOOST_TEST( sz > 0 ); | |
264 | } | |
265 | ||
266 | template< class Container, class Data > | |
267 | void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::false_ unordered) | |
268 | { | |
269 | (void)unordered; | |
270 | typedef typename Container::size_type size_type; | |
271 | typedef typename Container::key_of_value key_of_value; | |
272 | typedef typename Container::iterator iterator; | |
273 | typedef typename Container::const_iterator const_iterator; | |
274 | ||
275 | assert( d.size() > 2 ); | |
276 | ||
277 | c.clear(); | |
278 | typename Container::reference r = *d.begin(); | |
279 | c.insert(d.begin(), ++d.begin()); | |
280 | BOOST_TEST( &*Container::s_iterator_to(*c.begin()) == &r ); | |
281 | BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &r ); | |
282 | ||
283 | c.clear(); | |
284 | c.insert(d.begin(), d.end()); | |
285 | { | |
286 | Container const &cc = c; | |
287 | for( typename Data::const_iterator di = d.begin(), de = d.end(); | |
288 | di != de; ++di ) | |
289 | { | |
290 | BOOST_TEST( cc.find(key_of_value()(*di), c.key_comp()) != cc.end() ); | |
291 | std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.key_comp()); | |
292 | BOOST_TEST(rdi.first != rdi.second); | |
293 | BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.key_comp())); | |
294 | } | |
295 | ||
296 | for( iterator ci = c.begin(), ce = c.end(); ci != ce; ) | |
297 | { | |
298 | BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() ); | |
299 | std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.key_comp()); | |
300 | BOOST_TEST(rci.first != rci.second); | |
301 | size_type const sc = c.count(key_of_value()(*ci), c.key_comp()); | |
302 | BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc); | |
303 | BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.key_comp())); | |
304 | ci = rci.second; | |
305 | } | |
306 | BOOST_TEST(c.empty()); | |
307 | } | |
308 | ||
309 | c.clear(); | |
310 | c.insert(d.begin(), d.end()); | |
311 | ||
312 | typename Data::const_iterator db = d.begin(); | |
313 | typename Data::const_iterator da = db++; | |
314 | ||
315 | size_type old_size = c.size(); | |
316 | ||
317 | c.erase(key_of_value()(*da), c.key_comp()); | |
318 | BOOST_TEST( c.size() == old_size-1 ); | |
319 | //This should not erase any | |
320 | size_type second_erase = c.erase_and_dispose( key_of_value()(*da), c.key_comp(), detail::null_disposer() ); | |
321 | BOOST_TEST( second_erase == 0 ); | |
322 | ||
323 | BOOST_TEST( c.count(key_of_value()(*da), c.key_comp()) == 0 ); | |
324 | BOOST_TEST( c.count(key_of_value()(*db), c.key_comp()) != 0 ); | |
325 | BOOST_TEST( c.find(key_of_value()(*da), c.key_comp()) == c.end() ); | |
326 | BOOST_TEST( c.find(key_of_value()(*db), c.key_comp()) != c.end() ); | |
327 | BOOST_TEST( c.equal_range(key_of_value()(*db), c.key_comp()).first != c.end() ); | |
328 | c.clear(); | |
329 | BOOST_TEST( c.equal_range(key_of_value()(*da), c.key_comp()).first == c.end() ); | |
330 | } | |
331 | ||
332 | template< class Container, class Data > | |
333 | void test_common_unordered_and_associative_container(Container & c, Data & d) | |
334 | { | |
335 | typedef typename Container::size_type size_type; | |
336 | typedef typename Container::key_of_value key_of_value; | |
337 | typedef typename Container::iterator iterator; | |
338 | typedef typename Container::const_iterator const_iterator; | |
339 | ||
340 | { | |
341 | assert( d.size() > 2 ); | |
342 | ||
343 | c.clear(); | |
344 | typename Container::reference r = *d.begin(); | |
345 | c.insert(d.begin(), ++d.begin()); | |
346 | BOOST_TEST( &*c.iterator_to(*c.begin()) == &r ); | |
347 | BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &r ); | |
348 | ||
349 | c.clear(); | |
350 | c.insert(d.begin(), d.end()); | |
351 | ||
352 | Container const &cc = c; | |
353 | for( typename Data::const_iterator di = d.begin(), de = d.end(); | |
354 | di != de; ++di ) | |
355 | { | |
356 | BOOST_TEST( cc.find(key_of_value()(*di)) != cc.end() ); | |
357 | std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di)); | |
358 | BOOST_TEST(rdi.first != rdi.second); | |
359 | BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di))); | |
360 | } | |
361 | ||
362 | for( iterator ci = c.begin(), ce = c.end(); ci != ce; ) | |
363 | { | |
364 | BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() ); | |
365 | std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci)); | |
366 | BOOST_TEST(rci.first != rci.second); | |
367 | size_type const sc = c.count(key_of_value()(*ci)); | |
368 | BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc); | |
369 | BOOST_TEST(sc == c.erase(key_of_value()(*ci))); | |
370 | ci = rci.second; | |
371 | } | |
372 | BOOST_TEST(c.empty()); | |
373 | } | |
374 | { | |
375 | c.clear(); | |
376 | c.insert(d.begin(), d.end()); | |
377 | ||
378 | typename Data::const_iterator db = d.begin(); | |
379 | typename Data::const_iterator da = db++; | |
380 | ||
381 | size_type old_size = c.size(); | |
382 | ||
383 | c.erase(key_of_value()(*da)); | |
384 | BOOST_TEST( c.size() == old_size-1 ); | |
385 | //This should erase nothing | |
386 | size_type second_erase = c.erase_and_dispose( key_of_value()(*da), detail::null_disposer() ); | |
387 | BOOST_TEST( second_erase == 0 ); | |
388 | ||
389 | BOOST_TEST( c.count(key_of_value()(*da)) == 0 ); | |
390 | BOOST_TEST( c.count(key_of_value()(*db)) != 0 ); | |
391 | ||
392 | BOOST_TEST( c.find(key_of_value()(*da)) == c.end() ); | |
393 | BOOST_TEST( c.find(key_of_value()(*db)) != c.end() ); | |
394 | ||
395 | BOOST_TEST( c.equal_range(key_of_value()(*db)).first != c.end() ); | |
396 | BOOST_TEST( c.equal_range(key_of_value()(*da)).first == c.equal_range(key_of_value()(*da)).second ); | |
397 | } | |
398 | { | |
399 | c.clear(); | |
400 | c.insert( d.begin(), d.end() ); | |
401 | size_type orig_size = c.size(); | |
402 | Container move_c(::boost::move(c)); | |
403 | BOOST_TEST(orig_size == move_c.size()); | |
404 | BOOST_TEST( c.empty()); | |
405 | for( typename Data::const_iterator di = d.begin(), de = d.end(); | |
406 | di != de; ++di ) | |
407 | { BOOST_TEST( move_c.find(key_of_value()(*di)) != move_c.end() ); } | |
408 | ||
409 | c = ::boost::move(move_c); | |
410 | for( typename Data::const_iterator di = d.begin(), de = d.end(); | |
411 | di != de; ++di ) | |
412 | { BOOST_TEST( c.find(key_of_value()(*di)) != c.end() ); } | |
413 | BOOST_TEST( move_c.empty()); | |
414 | } | |
415 | typedef detail::bool_<is_unordered<Container>::value> enabler; | |
416 | test_common_unordered_and_associative_container(c, d, enabler()); | |
417 | } | |
418 | ||
419 | template< class Container, class Data > | |
420 | void test_associative_container_invariants(Container & c, Data & d) | |
421 | { | |
422 | typedef typename Container::const_iterator const_iterator; | |
423 | typedef typename Container::key_of_value key_of_value; | |
424 | for( typename Data::const_iterator di = d.begin(), de = d.end(); | |
425 | di != de; ++di) | |
426 | { | |
427 | const_iterator ci = c.find(key_of_value()(*di)); | |
428 | BOOST_TEST( ci != c.end() ); | |
429 | BOOST_TEST( ! c.value_comp()(*ci, *di) ); | |
430 | BOOST_TEST( ! c.key_comp()(key_of_value()(*ci), key_of_value()(*di)) ); | |
431 | const_iterator cil = c.lower_bound(key_of_value()(*di)); | |
432 | const_iterator ciu = c.upper_bound(key_of_value()(*di)); | |
433 | std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di)); | |
434 | BOOST_TEST( cil == er.first ); | |
435 | BOOST_TEST( ciu == er.second ); | |
436 | if(ciu != c.end()){ | |
437 | BOOST_TEST( c.value_comp()(*cil, *ciu) ); | |
438 | BOOST_TEST( c.key_comp()(key_of_value()(*cil), key_of_value()(*ciu)) ); | |
439 | } | |
440 | if(c.count(key_of_value()(*di)) > 1){ | |
441 | const_iterator ci_next = cil; ++ci_next; | |
442 | for( ; ci_next != ciu; ++cil, ++ci_next){ | |
443 | BOOST_TEST( !c.value_comp()(*ci_next, *cil) ); | |
444 | BOOST_TEST( !c.key_comp()(key_of_value()(*ci_next), key_of_value()(*cil)) ); | |
445 | } | |
446 | } | |
447 | } | |
448 | } | |
449 | ||
450 | template< class Container, class Data > | |
451 | void test_associative_container(Container & c, Data & d) | |
452 | { | |
453 | assert( d.size() > 2 ); | |
454 | ||
455 | c.clear(); | |
456 | c.insert(d.begin(),d.end()); | |
457 | ||
458 | test_associative_container_invariants(c, d); | |
459 | ||
460 | const Container & cr = c; | |
461 | ||
462 | test_associative_container_invariants(cr, d); | |
463 | } | |
464 | ||
465 | template< class Container, class Data > | |
466 | void test_unordered_associative_container_invariants(Container & c, Data & d) | |
467 | { | |
468 | typedef typename Container::size_type size_type; | |
469 | typedef typename Container::const_iterator const_iterator; | |
470 | typedef typename Container::key_of_value key_of_value; | |
471 | ||
472 | for( typename Data::const_iterator di = d.begin(), de = d.end() ; | |
473 | di != de ; ++di ){ | |
474 | const_iterator i = c.find(key_of_value()(*di)); | |
475 | size_type nb = c.bucket(key_of_value()(*i)); | |
476 | size_type bucket_elem = boost::intrusive::iterator_distance(c.begin(nb), c.end(nb)); | |
477 | BOOST_TEST( bucket_elem == c.bucket_size(nb) ); | |
478 | BOOST_TEST( &*c.local_iterator_to(*c.find(key_of_value()(*di))) == &*i ); | |
479 | BOOST_TEST( &*c.local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i ); | |
480 | BOOST_TEST( &*Container::s_local_iterator_to(*c.find(key_of_value()(*di))) == &*i ); | |
481 | BOOST_TEST( &*Container::s_local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i ); | |
482 | std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di)); | |
483 | size_type cnt = boost::intrusive::iterator_distance(er.first, er.second); | |
484 | BOOST_TEST( cnt == c.count(key_of_value()(*di))); | |
485 | if(cnt > 1){ | |
486 | const_iterator n = er.first; | |
487 | i = n++; | |
488 | const_iterator e = er.second; | |
489 | for(; n != e; ++i, ++n){ | |
490 | BOOST_TEST( c.key_eq()(key_of_value()(*i), key_of_value()(*n)) ); | |
491 | BOOST_TEST( (c.hash_function()(key_of_value()(*i))) == (c.hash_function()(key_of_value()(*n))) ); | |
492 | } | |
493 | } | |
494 | } | |
495 | ||
496 | size_type blen = c.bucket_count(); | |
497 | size_type total_objects = 0; | |
498 | for(size_type i = 0; i < blen; ++i){ | |
499 | total_objects += c.bucket_size(i); | |
500 | } | |
501 | BOOST_TEST( total_objects == c.size() ); | |
502 | } | |
503 | ||
504 | template< class Container, class Data > | |
505 | void test_unordered_associative_container(Container & c, Data & d) | |
506 | { | |
507 | c.clear(); | |
508 | c.insert( d.begin(), d.end() ); | |
509 | ||
510 | test_unordered_associative_container_invariants(c, d); | |
511 | ||
512 | const Container & cr = c; | |
513 | ||
514 | test_unordered_associative_container_invariants(cr, d); | |
515 | } | |
516 | ||
517 | template< class Container, class Data > | |
518 | void test_unique_container(Container & c, Data & d) | |
519 | { | |
520 | //typedef typename Container::value_type value_type; | |
521 | c.clear(); | |
522 | c.insert(d.begin(),d.end()); | |
523 | typename Container::size_type old_size = c.size(); | |
524 | //value_type v(*d.begin()); | |
525 | //c.insert(v); | |
526 | Data d2(1); | |
527 | (&d2.front())->value_ = (&d.front())->value_; | |
528 | c.insert(d2.front()); | |
529 | BOOST_TEST( c.size() == old_size ); | |
530 | c.clear(); | |
531 | } | |
532 | ||
533 | template< class Container, class Data > | |
534 | void test_non_unique_container(Container & c, Data & d) | |
535 | { | |
536 | //typedef typename Container::value_type value_type; | |
537 | c.clear(); | |
538 | c.insert(d.begin(),d.end()); | |
539 | typename Container::size_type old_size = c.size(); | |
540 | //value_type v(*d.begin()); | |
541 | //c.insert(v); | |
542 | Data d2(1); | |
543 | (&d2.front())->value_ = (&d.front())->value_; | |
544 | c.insert(d2.front()); | |
545 | BOOST_TEST( c.size() == (old_size+1) ); | |
546 | c.clear(); | |
547 | } | |
548 | ||
549 | template< class Container, class Data > | |
550 | void test_maybe_unique_container(Container & c, Data & d, detail::false_)//is_unique | |
551 | { test_unique_container(c, d); } | |
552 | ||
553 | template< class Container, class Data > | |
554 | void test_maybe_unique_container(Container & c, Data & d, detail::true_)//!is_unique | |
555 | { test_non_unique_container(c, d); } | |
556 | ||
b32b8144 FG |
557 | template< class RandomIt > |
558 | void random_shuffle( RandomIt first, RandomIt last ) | |
559 | { | |
560 | typedef typename boost::intrusive::iterator_traits<RandomIt>::difference_type difference_type; | |
561 | difference_type n = last - first; | |
562 | for (difference_type i = n-1; i > 0; --i) { | |
563 | difference_type j = std::rand() % (i+1); | |
564 | if(j != i) { | |
565 | boost::adl_move_swap(first[i], first[j]); | |
566 | } | |
567 | } | |
568 | } | |
569 | ||
7c673cae FG |
570 | }}} |
571 | ||
572 | #endif //#ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP |