]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2015-2015. | |
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 | #include <boost/intrusive/pointer_traits.hpp> | |
13 | #include <boost/intrusive/detail/iterator.hpp> | |
14 | #include "common_functors.hpp" | |
15 | #include <vector> | |
16 | #include <algorithm> //std::sort | |
17 | #include <set> | |
18 | #include <boost/detail/lightweight_test.hpp> | |
19 | ||
20 | #include "test_macros.hpp" | |
21 | #include "test_container.hpp" | |
22 | #include "unordered_test_common.hpp" | |
23 | ||
24 | namespace boost{ | |
25 | namespace intrusive{ | |
26 | namespace test{ | |
27 | ||
28 | static const std::size_t BucketSize = 8; | |
29 | ||
30 | template<class ContainerDefiner> | |
31 | struct test_unordered | |
32 | { | |
33 | typedef typename ContainerDefiner::value_cont_type value_cont_type; | |
34 | ||
35 | static void test_all(value_cont_type& values); | |
36 | private: | |
37 | static void test_sort(value_cont_type& values); | |
38 | static void test_insert(value_cont_type& values, detail::true_); | |
39 | static void test_insert(value_cont_type& values, detail::false_); | |
40 | static void test_swap(value_cont_type& values); | |
41 | static void test_rehash(value_cont_type& values, detail::true_); | |
42 | static void test_rehash(value_cont_type& values, detail::false_); | |
43 | static void test_find(value_cont_type& values); | |
44 | static void test_impl(); | |
45 | static void test_clone(value_cont_type& values); | |
46 | }; | |
47 | ||
48 | template<class ContainerDefiner> | |
49 | void test_unordered<ContainerDefiner>::test_all (value_cont_type& values) | |
50 | { | |
51 | typedef typename ContainerDefiner::template container | |
52 | <>::type unordered_type; | |
53 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 54 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
55 | { |
56 | typename unordered_type::bucket_type buckets [BucketSize]; | |
57 | unordered_type testset | |
b32b8144 | 58 | (bucket_traits(pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae FG |
59 | testset.insert(values.begin(), values.end()); |
60 | test::test_container(testset); | |
61 | testset.clear(); | |
62 | testset.insert(values.begin(), values.end()); | |
63 | test::test_common_unordered_and_associative_container(testset, values); | |
64 | testset.clear(); | |
65 | testset.insert(values.begin(), values.end()); | |
66 | test::test_unordered_associative_container(testset, values); | |
67 | testset.clear(); | |
68 | testset.insert(values.begin(), values.end()); | |
69 | typedef detail::bool_<boost::intrusive::test::is_multikey_true | |
70 | <unordered_type>::value> select_t; | |
71 | test::test_maybe_unique_container(testset, values, select_t()); | |
72 | } | |
73 | { | |
74 | value_cont_type vals(BucketSize); | |
75 | for (int i = 0; i < (int)BucketSize; ++i) | |
76 | (&vals[i])->value_ = i; | |
77 | typename unordered_type::bucket_type buckets [BucketSize]; | |
78 | unordered_type testset(bucket_traits( | |
b32b8144 | 79 | pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae FG |
80 | testset.insert(vals.begin(), vals.end()); |
81 | test::test_iterator_forward(testset); | |
82 | } | |
83 | test_sort(values); | |
84 | test_insert(values, detail::bool_<boost::intrusive::test::is_multikey_true<unordered_type>::value>()); | |
85 | test_swap(values); | |
86 | test_rehash(values, detail::bool_<unordered_type::incremental>()); | |
87 | test_find(values); | |
88 | test_impl(); | |
89 | test_clone(values); | |
90 | } | |
91 | ||
92 | //test case due to an error in tree implementation: | |
93 | template<class ContainerDefiner> | |
94 | void test_unordered<ContainerDefiner>::test_impl() | |
95 | { | |
96 | typedef typename ContainerDefiner::template container | |
97 | <>::type unordered_type; | |
98 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 99 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
100 | |
101 | value_cont_type values (5); | |
102 | for (int i = 0; i < 5; ++i) | |
103 | values[i].value_ = i; | |
104 | ||
105 | typename unordered_type::bucket_type buckets [BucketSize]; | |
106 | unordered_type testset(bucket_traits( | |
b32b8144 | 107 | pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae FG |
108 | |
109 | for (int i = 0; i < 5; ++i) | |
110 | testset.insert (values[i]); | |
111 | ||
112 | testset.erase (testset.iterator_to (values[0])); | |
113 | testset.erase (testset.iterator_to (values[1])); | |
114 | testset.insert (values[1]); | |
115 | ||
116 | testset.erase (testset.iterator_to (values[2])); | |
117 | testset.erase (testset.iterator_to (values[3])); | |
118 | } | |
119 | ||
120 | //test: constructor, iterator, clear, reverse_iterator, front, back, size: | |
121 | template<class ContainerDefiner> | |
122 | void test_unordered<ContainerDefiner>::test_sort(value_cont_type& values) | |
123 | { | |
124 | typedef typename ContainerDefiner::template container | |
125 | <>::type unordered_type; | |
126 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 127 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
128 | |
129 | typename unordered_type::bucket_type buckets [BucketSize]; | |
130 | unordered_type testset1 | |
131 | (values.begin(), values.end(), bucket_traits | |
b32b8144 | 132 | (pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae FG |
133 | |
134 | if(unordered_type::incremental){ | |
135 | { int init_values [] = { 4, 5, 1, 2, 2, 3 }; | |
136 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
137 | } | |
138 | else{ | |
139 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
140 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
141 | } | |
142 | testset1.clear(); | |
143 | BOOST_TEST (testset1.empty()); | |
144 | } | |
145 | ||
146 | //test: insert, const_iterator, const_reverse_iterator, erase, iterator_to: | |
147 | template<class ContainerDefiner> | |
148 | void test_unordered<ContainerDefiner>::test_insert(value_cont_type& values, detail::false_) //not multikey | |
149 | { | |
150 | ||
151 | typedef typename ContainerDefiner::template container | |
152 | <>::type unordered_set_type; | |
153 | typedef typename unordered_set_type::bucket_traits bucket_traits; | |
154 | typedef typename unordered_set_type::key_of_value key_of_value; | |
155 | ||
156 | typename unordered_set_type::bucket_type buckets [BucketSize]; | |
157 | unordered_set_type testset(bucket_traits( | |
158 | pointer_traits<typename unordered_set_type::bucket_ptr>:: | |
159 | pointer_to(buckets[0]), BucketSize)); | |
160 | testset.insert(&values[0] + 2, &values[0] + 5); | |
161 | ||
162 | typename unordered_set_type::insert_commit_data commit_data; | |
163 | BOOST_TEST ((!testset.insert_check(key_of_value()(values[2]), commit_data).second)); | |
164 | BOOST_TEST (( testset.insert_check(key_of_value()(values[0]), commit_data).second)); | |
165 | ||
166 | const unordered_set_type& const_testset = testset; | |
167 | if(unordered_set_type::incremental) | |
168 | { | |
169 | { int init_values [] = { 4, 5, 1 }; | |
170 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
171 | typename unordered_set_type::iterator i = testset.begin(); | |
172 | BOOST_TEST (i->value_ == 4); | |
173 | ||
174 | i = testset.insert(values[0]).first; | |
175 | BOOST_TEST (&*i == &values[0]); | |
176 | ||
177 | i = testset.iterator_to (values[2]); | |
178 | BOOST_TEST (&*i == &values[2]); | |
179 | ||
180 | testset.erase (i); | |
181 | ||
182 | { int init_values [] = { 5, 1, 3 }; | |
183 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
184 | } | |
185 | else{ | |
186 | { int init_values [] = { 1, 4, 5 }; | |
187 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
188 | typename unordered_set_type::iterator i = testset.begin(); | |
189 | BOOST_TEST (i->value_ == 1); | |
190 | ||
191 | i = testset.insert(values[0]).first; | |
192 | BOOST_TEST (&*i == &values[0]); | |
193 | ||
194 | i = testset.iterator_to (values[2]); | |
195 | BOOST_TEST (&*i == &values[2]); | |
196 | ||
197 | testset.erase (i); | |
198 | ||
199 | { int init_values [] = { 1, 3, 5 }; | |
200 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
201 | } | |
202 | } | |
203 | ||
204 | template<class ContainerDefiner> | |
205 | void test_unordered<ContainerDefiner>::test_insert(value_cont_type& values, detail::true_) //is multikey | |
206 | { | |
207 | typedef typename ContainerDefiner::template container | |
208 | <>::type unordered_type; | |
209 | ||
210 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 211 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
212 | typedef typename unordered_type::iterator iterator; |
213 | typedef typename unordered_type::key_type key_type; | |
214 | { | |
215 | typename unordered_type::bucket_type buckets [BucketSize]; | |
216 | unordered_type testset(bucket_traits( | |
b32b8144 | 217 | pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae FG |
218 | |
219 | testset.insert(&values[0] + 2, &values[0] + 5); | |
220 | ||
221 | const unordered_type& const_testset = testset; | |
222 | ||
223 | if(unordered_type::incremental){ | |
224 | { | |
225 | { int init_values [] = { 4, 5, 1 }; | |
226 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
227 | ||
228 | typename unordered_type::iterator i = testset.begin(); | |
229 | BOOST_TEST (i->value_ == 4); | |
230 | ||
231 | i = testset.insert (values[0]); | |
232 | BOOST_TEST (&*i == &values[0]); | |
233 | ||
234 | i = testset.iterator_to (values[2]); | |
235 | BOOST_TEST (&*i == &values[2]); | |
236 | testset.erase(i); | |
237 | ||
238 | { int init_values [] = { 5, 1, 3 }; | |
239 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
240 | testset.clear(); | |
241 | testset.insert(&values[0], &values[0] + values.size()); | |
242 | ||
243 | { int init_values [] = { 4, 5, 1, 2, 2, 3 }; | |
244 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
245 | ||
246 | BOOST_TEST (testset.erase(key_type(1)) == 1); | |
247 | BOOST_TEST (testset.erase(key_type(2)) == 2); | |
248 | BOOST_TEST (testset.erase(key_type(3)) == 1); | |
249 | BOOST_TEST (testset.erase(key_type(4)) == 1); | |
250 | BOOST_TEST (testset.erase(key_type(5)) == 1); | |
251 | BOOST_TEST (testset.empty() == true); | |
252 | ||
253 | //Now with a single bucket | |
254 | typename unordered_type::bucket_type single_bucket[1]; | |
255 | unordered_type testset2(bucket_traits( | |
b32b8144 | 256 | pointer_traits<bucket_ptr>::pointer_to(single_bucket[0]), 1)); |
7c673cae FG |
257 | testset2.insert(&values[0], &values[0] + values.size()); |
258 | BOOST_TEST (testset2.erase(key_type(5)) == 1); | |
259 | BOOST_TEST (testset2.erase(key_type(2)) == 2); | |
260 | BOOST_TEST (testset2.erase(key_type(1)) == 1); | |
261 | BOOST_TEST (testset2.erase(key_type(4)) == 1); | |
262 | BOOST_TEST (testset2.erase(key_type(3)) == 1); | |
263 | BOOST_TEST (testset2.empty() == true); | |
264 | } | |
265 | } | |
266 | else{ | |
267 | { | |
268 | { int init_values [] = { 1, 4, 5 }; | |
269 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
270 | ||
271 | typename unordered_type::iterator i = testset.begin(); | |
272 | BOOST_TEST (i->value_ == 1); | |
273 | ||
274 | i = testset.insert (values[0]); | |
275 | BOOST_TEST (&*i == &values[0]); | |
276 | ||
277 | i = testset.iterator_to (values[2]); | |
278 | BOOST_TEST (&*i == &values[2]); | |
279 | testset.erase(i); | |
280 | ||
281 | { int init_values [] = { 1, 3, 5 }; | |
282 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
283 | testset.clear(); | |
284 | testset.insert(&values[0], &values[0] + values.size()); | |
285 | ||
286 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
287 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset ); } | |
288 | ||
289 | BOOST_TEST (testset.erase(key_type(1)) == 1); | |
290 | BOOST_TEST (testset.erase(key_type(2)) == 2); | |
291 | BOOST_TEST (testset.erase(key_type(3)) == 1); | |
292 | BOOST_TEST (testset.erase(key_type(4)) == 1); | |
293 | BOOST_TEST (testset.erase(key_type(5)) == 1); | |
294 | BOOST_TEST (testset.empty() == true); | |
295 | ||
296 | //Now with a single bucket | |
297 | typename unordered_type::bucket_type single_bucket[1]; | |
298 | unordered_type testset2(bucket_traits( | |
b32b8144 | 299 | pointer_traits<bucket_ptr>::pointer_to(single_bucket[0]), 1)); |
7c673cae FG |
300 | testset2.insert(&values[0], &values[0] + values.size()); |
301 | BOOST_TEST (testset2.erase(key_type(5)) == 1); | |
302 | BOOST_TEST (testset2.erase(key_type(2)) == 2); | |
303 | BOOST_TEST (testset2.erase(key_type(1)) == 1); | |
304 | BOOST_TEST (testset2.erase(key_type(4)) == 1); | |
305 | BOOST_TEST (testset2.erase(key_type(3)) == 1); | |
306 | BOOST_TEST (testset2.empty() == true); | |
307 | } | |
308 | } | |
309 | { | |
310 | //Now erase just one per loop | |
311 | const int random_init[] = { 3, 2, 4, 1, 5, 2, 2 }; | |
312 | const unsigned int random_size = sizeof(random_init)/sizeof(random_init[0]); | |
313 | typename unordered_type::bucket_type single_bucket[1]; | |
314 | for(unsigned int i = 0, max = random_size; i != max; ++i){ | |
315 | value_cont_type data (random_size); | |
316 | for (unsigned int j = 0; j < random_size; ++j) | |
317 | data[j].value_ = random_init[j]; | |
318 | unordered_type testset_new(bucket_traits( | |
b32b8144 | 319 | pointer_traits<bucket_ptr>::pointer_to(single_bucket[0]), 1)); |
7c673cae FG |
320 | testset_new.insert(&data[0], &data[0]+max); |
321 | testset_new.erase(testset_new.iterator_to(data[i])); | |
322 | BOOST_TEST (testset_new.size() == (max -1)); | |
323 | } | |
324 | } | |
325 | } | |
326 | { | |
7c673cae | 327 | const unsigned int LoadFactor = 3; |
b32b8144 | 328 | const unsigned int NumIterations = BucketSize*LoadFactor; |
7c673cae FG |
329 | value_cont_type random_init(NumIterations);//Preserve memory |
330 | value_cont_type set_tester; | |
331 | set_tester.reserve(NumIterations); | |
332 | ||
333 | //Initialize values | |
334 | for (unsigned int i = 0; i < NumIterations; ++i){ | |
335 | random_init[i].value_ = i*2;//(i/LoadFactor)*LoadFactor; | |
336 | } | |
337 | ||
b32b8144 FG |
338 | typename unordered_type::bucket_type buckets [BucketSize]; |
339 | bucket_traits btraits(pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize); | |
340 | ||
7c673cae FG |
341 | for(unsigned int initial_pos = 0; initial_pos != (NumIterations+1); ++initial_pos){ |
342 | for(unsigned int final_pos = initial_pos; final_pos != (NumIterations+1); ++final_pos){ | |
343 | ||
344 | //Create intrusive container inserting values | |
345 | unordered_type testset | |
b32b8144 FG |
346 | ( random_init.data() |
347 | , random_init.data() + random_init.size() | |
348 | , btraits); | |
7c673cae FG |
349 | |
350 | BOOST_TEST (testset.size() == random_init.size()); | |
351 | ||
352 | //Obtain the iterator range to erase | |
353 | iterator it_beg_pos = testset.begin(); | |
354 | for(unsigned int it_beg_pos_num = 0; it_beg_pos_num != initial_pos; ++it_beg_pos_num){ | |
355 | ++it_beg_pos; | |
356 | } | |
357 | iterator it_end_pos(it_beg_pos); | |
358 | for(unsigned int it_end_pos_num = 0; it_end_pos_num != (final_pos - initial_pos); ++it_end_pos_num){ | |
359 | ++it_end_pos; | |
360 | } | |
361 | ||
362 | //Erase the same values in both the intrusive and original vector | |
363 | std::size_t erased_cnt = boost::intrusive::iterator_distance(it_beg_pos, it_end_pos); | |
364 | ||
365 | //Erase values from the intrusive container | |
366 | testset.erase(it_beg_pos, it_end_pos); | |
367 | ||
368 | BOOST_TEST (testset.size() == (random_init.size()-(final_pos - initial_pos))); | |
369 | ||
370 | //Now test... | |
371 | BOOST_TEST ((random_init.size() - erased_cnt) == testset.size()); | |
372 | ||
373 | //Create an ordered copy of the intrusive container | |
374 | set_tester.insert(set_tester.end(), testset.begin(), testset.end()); | |
375 | std::sort(set_tester.begin(), set_tester.end()); | |
376 | { | |
377 | typename value_cont_type::iterator it = set_tester.begin(), itend = set_tester.end(); | |
378 | typename value_cont_type::iterator random_init_it(random_init.begin()); | |
379 | for( ; it != itend; ++it){ | |
380 | while(!random_init_it->is_linked()) | |
381 | ++random_init_it; | |
382 | BOOST_TEST(*it == *random_init_it); | |
383 | ++random_init_it; | |
384 | } | |
385 | } | |
386 | set_tester.clear(); | |
387 | } | |
388 | } | |
389 | } | |
390 | } | |
391 | ||
392 | //test: insert (seq-version), swap, erase (seq-version), size: | |
393 | template<class ContainerDefiner> | |
394 | void test_unordered<ContainerDefiner>::test_swap(value_cont_type& values) | |
395 | { | |
396 | typedef typename ContainerDefiner::template container | |
397 | <>::type unordered_type; | |
398 | ||
399 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 400 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
401 | typename unordered_type::bucket_type buckets [BucketSize]; |
402 | ||
403 | typename unordered_type::bucket_type buckets2 [BucketSize]; | |
404 | unordered_type testset1(&values[0], &values[0] + 2, | |
b32b8144 | 405 | bucket_traits(pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae | 406 | unordered_type testset2(bucket_traits( |
b32b8144 | 407 | pointer_traits<bucket_ptr>::pointer_to(buckets2[0]), BucketSize)); |
7c673cae FG |
408 | |
409 | testset2.insert (&values[0] + 2, &values[0] + 6); | |
410 | testset1.swap (testset2); | |
411 | ||
412 | if(unordered_type::incremental){ | |
413 | { int init_values [] = { 4, 5, 1, 2 }; | |
414 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
415 | ||
416 | { int init_values [] = { 2, 3 }; | |
417 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset2 ); } | |
418 | testset1.erase (testset1.iterator_to(values[4]), testset1.end()); | |
419 | BOOST_TEST (testset1.size() == 1); | |
420 | // BOOST_TEST (&testset1.front() == &values[3]); | |
421 | BOOST_TEST (&*testset1.begin() == &values[2]); | |
422 | } | |
423 | else{ | |
424 | { int init_values [] = { 1, 2, 4, 5 }; | |
425 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
426 | ||
427 | { int init_values [] = { 2, 3 }; | |
428 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset2 ); } | |
429 | testset1.erase (testset1.iterator_to(values[5]), testset1.end()); | |
430 | BOOST_TEST (testset1.size() == 1); | |
431 | // BOOST_TEST (&testset1.front() == &values[3]); | |
432 | BOOST_TEST (&*testset1.begin() == &values[3]); | |
433 | } | |
434 | } | |
435 | ||
436 | ||
437 | ||
438 | //test: rehash: | |
439 | ||
440 | template<class ContainerDefiner> | |
441 | void test_unordered<ContainerDefiner>::test_rehash(value_cont_type& values, detail::true_) | |
442 | { | |
443 | typedef typename ContainerDefiner::template container | |
444 | <>::type unordered_type; | |
445 | ||
446 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 447 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
448 | //Build a uset |
449 | typename unordered_type::bucket_type buckets1 [BucketSize]; | |
450 | typename unordered_type::bucket_type buckets2 [BucketSize*2]; | |
451 | unordered_type testset1(&values[0], &values[0] + values.size(), | |
b32b8144 | 452 | bucket_traits(pointer_traits<bucket_ptr>:: |
7c673cae FG |
453 | pointer_to(buckets1[0]), BucketSize)); |
454 | //Test current state | |
455 | BOOST_TEST(testset1.split_count() == BucketSize/2); | |
456 | { int init_values [] = { 4, 5, 1, 2, 2, 3 }; | |
457 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
458 | //Incremental rehash step | |
459 | BOOST_TEST (testset1.incremental_rehash() == true); | |
460 | BOOST_TEST(testset1.split_count() == (BucketSize/2+1)); | |
461 | { int init_values [] = { 5, 1, 2, 2, 3, 4 }; | |
462 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
463 | //Rest of incremental rehashes should lead to the same sequence | |
464 | for(std::size_t split_bucket = testset1.split_count(); split_bucket != BucketSize; ++split_bucket){ | |
465 | BOOST_TEST (testset1.incremental_rehash() == true); | |
466 | BOOST_TEST(testset1.split_count() == (split_bucket+1)); | |
467 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
468 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
469 | } | |
470 | //This incremental rehash should fail because we've reached the end of the bucket array | |
471 | BOOST_TEST (testset1.incremental_rehash() == false); | |
472 | BOOST_TEST(testset1.split_count() == BucketSize); | |
473 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
474 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
475 | ||
476 | // | |
477 | //Try incremental hashing specifying a new bucket traits pointing to the same array | |
478 | // | |
479 | //This incremental rehash should fail because the new size is not twice the original | |
480 | BOOST_TEST(testset1.incremental_rehash(bucket_traits( | |
b32b8144 | 481 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
482 | pointer_to(buckets1[0]), BucketSize)) == false); |
483 | BOOST_TEST(testset1.split_count() == BucketSize); | |
484 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
485 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
486 | ||
487 | // | |
488 | //Try incremental hashing specifying a new bucket traits pointing to the same array | |
489 | // | |
490 | //This incremental rehash should fail because the new size is not twice the original | |
491 | BOOST_TEST(testset1.incremental_rehash(bucket_traits( | |
b32b8144 | 492 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
493 | pointer_to(buckets2[0]), BucketSize)) == false); |
494 | BOOST_TEST(testset1.split_count() == BucketSize); | |
495 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
496 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
497 | ||
498 | //This incremental rehash should success because the new size is twice the original | |
499 | //and split_count is the same as the old bucket count | |
500 | BOOST_TEST(testset1.incremental_rehash(bucket_traits( | |
b32b8144 | 501 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
502 | pointer_to(buckets2[0]), BucketSize*2)) == true); |
503 | BOOST_TEST(testset1.split_count() == BucketSize); | |
504 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
505 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
506 | ||
507 | //This incremental rehash should also success because the new size is half the original | |
508 | //and split_count is the same as the new bucket count | |
509 | BOOST_TEST(testset1.incremental_rehash(bucket_traits( | |
b32b8144 | 510 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
511 | pointer_to(buckets1[0]), BucketSize)) == true); |
512 | BOOST_TEST(testset1.split_count() == BucketSize); | |
513 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
514 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
515 | ||
516 | //Shrink rehash | |
517 | testset1.rehash(bucket_traits( | |
b32b8144 | 518 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
519 | pointer_to(buckets1[0]), 4)); |
520 | BOOST_TEST (testset1.incremental_rehash() == false); | |
521 | { int init_values [] = { 4, 5, 1, 2, 2, 3 }; | |
522 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
523 | ||
524 | //Shrink rehash again | |
525 | testset1.rehash(bucket_traits( | |
b32b8144 | 526 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
527 | pointer_to(buckets1[0]), 2)); |
528 | BOOST_TEST (testset1.incremental_rehash() == false); | |
529 | { int init_values [] = { 2, 2, 4, 3, 5, 1 }; | |
530 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
531 | ||
532 | //Growing rehash | |
533 | testset1.rehash(bucket_traits( | |
b32b8144 | 534 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
535 | pointer_to(buckets1[0]), BucketSize)); |
536 | ||
537 | //Full rehash (no effects) | |
538 | testset1.full_rehash(); | |
539 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
540 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
541 | ||
542 | //Incremental rehash shrinking | |
543 | //First incremental rehashes should lead to the same sequence | |
544 | for(std::size_t split_bucket = testset1.split_count(); split_bucket > 6; --split_bucket){ | |
545 | BOOST_TEST (testset1.incremental_rehash(false) == true); | |
546 | BOOST_TEST(testset1.split_count() == (split_bucket-1)); | |
547 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
548 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
549 | } | |
550 | ||
551 | //Incremental rehash step | |
552 | BOOST_TEST (testset1.incremental_rehash(false) == true); | |
553 | BOOST_TEST(testset1.split_count() == (BucketSize/2+1)); | |
554 | { int init_values [] = { 5, 1, 2, 2, 3, 4 }; | |
555 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
556 | ||
557 | //Incremental rehash step 2 | |
558 | BOOST_TEST (testset1.incremental_rehash(false) == true); | |
559 | BOOST_TEST(testset1.split_count() == (BucketSize/2)); | |
560 | { int init_values [] = { 4, 5, 1, 2, 2, 3 }; | |
561 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
562 | ||
563 | //This incremental rehash should fail because we've reached the half of the bucket array | |
564 | BOOST_TEST(testset1.incremental_rehash(false) == false); | |
565 | BOOST_TEST(testset1.split_count() == BucketSize/2); | |
566 | { int init_values [] = { 4, 5, 1, 2, 2, 3 }; | |
567 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
568 | } | |
569 | template<class ContainerDefiner> | |
570 | void test_unordered<ContainerDefiner>::test_rehash(value_cont_type& values, detail::false_) | |
571 | { | |
572 | typedef typename ContainerDefiner::template container | |
573 | <>::type unordered_type; | |
574 | ||
575 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 576 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
577 | |
578 | typename unordered_type::bucket_type buckets1 [BucketSize]; | |
579 | typename unordered_type::bucket_type buckets2 [2]; | |
580 | typename unordered_type::bucket_type buckets3 [BucketSize*2]; | |
581 | ||
582 | unordered_type testset1(&values[0], &values[0] + 6, bucket_traits( | |
b32b8144 | 583 | pointer_traits<bucket_ptr>:: |
7c673cae FG |
584 | pointer_to(buckets1[0]), BucketSize)); |
585 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
586 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
587 | ||
588 | testset1.rehash(bucket_traits( | |
b32b8144 | 589 | pointer_traits<bucket_ptr>::pointer_to(buckets2[0]), 2)); |
7c673cae FG |
590 | { int init_values [] = { 4, 2, 2, 5, 3, 1 }; |
591 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
592 | ||
593 | testset1.rehash(bucket_traits( | |
b32b8144 | 594 | pointer_traits<bucket_ptr>::pointer_to(buckets3[0]), BucketSize*2)); |
7c673cae FG |
595 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; |
596 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
597 | ||
598 | //Now rehash reducing the buckets | |
599 | testset1.rehash(bucket_traits( | |
b32b8144 | 600 | pointer_traits<bucket_ptr>::pointer_to(buckets3[0]), 2)); |
7c673cae FG |
601 | { int init_values [] = { 4, 2, 2, 5, 3, 1 }; |
602 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
603 | ||
604 | //Now rehash increasing the buckets | |
605 | testset1.rehash(bucket_traits( | |
b32b8144 | 606 | pointer_traits<bucket_ptr>::pointer_to(buckets3[0]), BucketSize*2)); |
7c673cae FG |
607 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; |
608 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
609 | ||
610 | //Full rehash (no effects) | |
611 | testset1.full_rehash(); | |
612 | { int init_values [] = { 1, 2, 2, 3, 4, 5 }; | |
613 | TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 ); } | |
614 | } | |
615 | ||
616 | //test: find, equal_range (lower_bound, upper_bound): | |
617 | template<class ContainerDefiner> | |
618 | void test_unordered<ContainerDefiner>::test_find(value_cont_type& values) | |
619 | { | |
620 | typedef typename ContainerDefiner::template container | |
621 | <>::type unordered_type; | |
622 | typedef typename unordered_type::value_type value_type; | |
623 | ||
624 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 | 625 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
7c673cae FG |
626 | typedef typename unordered_type::key_of_value key_of_value; |
627 | const bool is_multikey = boost::intrusive::test::is_multikey_true<unordered_type>::value; | |
628 | ||
629 | typename unordered_type::bucket_type buckets[BucketSize]; | |
630 | unordered_type testset(values.begin(), values.end(), bucket_traits( | |
b32b8144 | 631 | pointer_traits<bucket_ptr>::pointer_to(buckets[0]), BucketSize)); |
7c673cae FG |
632 | |
633 | typedef typename unordered_type::iterator iterator; | |
634 | ||
635 | value_type cmp_val; | |
636 | cmp_val.value_ = 2; | |
637 | BOOST_TEST (testset.count(key_of_value()(cmp_val)) == (is_multikey ? 2 : 1)); | |
638 | iterator i = testset.find (key_of_value()(cmp_val)); | |
639 | BOOST_TEST (i->value_ == 2); | |
640 | if(is_multikey) | |
641 | BOOST_TEST ((++i)->value_ == 2); | |
642 | else | |
643 | BOOST_TEST ((++i)->value_ != 2); | |
644 | std::pair<iterator,iterator> range = testset.equal_range (key_of_value()(cmp_val)); | |
645 | ||
646 | BOOST_TEST (range.first->value_ == 2); | |
647 | BOOST_TEST (range.second->value_ == 3); | |
648 | BOOST_TEST (boost::intrusive::iterator_distance (range.first, range.second) == (is_multikey ? 2 : 1)); | |
649 | cmp_val.value_ = 7; | |
650 | BOOST_TEST (testset.find (key_of_value()(cmp_val)) == testset.end()); | |
651 | BOOST_TEST (testset.count(key_of_value()(cmp_val)) == 0); | |
652 | } | |
653 | ||
654 | ||
655 | template<class ContainerDefiner> | |
656 | void test_unordered<ContainerDefiner>::test_clone(value_cont_type& values) | |
657 | { | |
658 | typedef typename ContainerDefiner::template container | |
659 | <>::type unordered_type; | |
660 | typedef typename unordered_type::value_type value_type; | |
661 | typedef std::multiset<value_type> std_multiset_t; | |
662 | ||
663 | typedef typename unordered_type::bucket_traits bucket_traits; | |
b32b8144 FG |
664 | typedef typename unordered_type::bucket_ptr bucket_ptr; |
665 | ||
7c673cae FG |
666 | { |
667 | //Test with equal bucket arrays | |
668 | typename unordered_type::bucket_type buckets1 [BucketSize]; | |
669 | typename unordered_type::bucket_type buckets2 [BucketSize]; | |
670 | unordered_type testset1 (values.begin(), values.end(), bucket_traits( | |
b32b8144 | 671 | pointer_traits<bucket_ptr>::pointer_to(buckets1[0]), BucketSize)); |
7c673cae | 672 | unordered_type testset2 (bucket_traits( |
b32b8144 | 673 | pointer_traits<bucket_ptr>::pointer_to(buckets2[0]), BucketSize)); |
7c673cae FG |
674 | |
675 | testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>()); | |
676 | BOOST_TEST(testset1 == testset2); | |
677 | //Ordering is not guarantee in the cloning so insert data in a set and test | |
678 | std_multiset_t src(testset1.begin(), testset1.end()); | |
679 | std_multiset_t dst(testset2.begin(), testset2.end()); | |
680 | BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin())); | |
681 | testset2.clear_and_dispose(test::delete_disposer<value_type>()); | |
682 | BOOST_TEST (testset2.empty()); | |
683 | ||
684 | testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>()); | |
685 | BOOST_TEST(testset1 == testset2); | |
686 | //Ordering is not guarantee in the cloning so insert data in a set and test | |
687 | std_multiset_t(testset1.begin(), testset1.end()).swap(src); | |
688 | std_multiset_t(testset2.begin(), testset2.end()).swap(dst); | |
689 | BOOST_TEST(src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin())); | |
690 | testset2.clear_and_dispose(test::delete_disposer<value_type>()); | |
691 | BOOST_TEST (testset2.empty()); | |
692 | } | |
693 | { | |
694 | //Test with bigger source bucket arrays | |
695 | typename unordered_type::bucket_type buckets1 [BucketSize*2]; | |
696 | typename unordered_type::bucket_type buckets2 [BucketSize]; | |
697 | unordered_type testset1 (values.begin(), values.end(), bucket_traits( | |
b32b8144 | 698 | pointer_traits<bucket_ptr>::pointer_to(buckets1[0]), BucketSize*2)); |
7c673cae | 699 | unordered_type testset2 (bucket_traits( |
b32b8144 | 700 | pointer_traits<bucket_ptr>::pointer_to(buckets2[0]), BucketSize)); |
7c673cae FG |
701 | |
702 | testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>()); | |
703 | BOOST_TEST(testset1 == testset2); | |
704 | //Ordering is not guarantee in the cloning so insert data in a set and test | |
705 | std_multiset_t src(testset1.begin(), testset1.end()); | |
706 | std_multiset_t dst(testset2.begin(), testset2.end()); | |
707 | BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin())); | |
708 | testset2.clear_and_dispose(test::delete_disposer<value_type>()); | |
709 | BOOST_TEST (testset2.empty()); | |
710 | ||
711 | testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>()); | |
712 | BOOST_TEST(testset1 == testset2); | |
713 | //Ordering is not guarantee in the cloning so insert data in a set and test | |
714 | std_multiset_t(testset1.begin(), testset1.end()).swap(src); | |
715 | std_multiset_t(testset2.begin(), testset2.end()).swap(dst); | |
716 | BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin())); | |
717 | testset2.clear_and_dispose(test::delete_disposer<value_type>()); | |
718 | BOOST_TEST (testset2.empty()); | |
719 | } | |
720 | { | |
721 | //Test with smaller source bucket arrays | |
722 | typename unordered_type::bucket_type buckets1 [BucketSize]; | |
723 | typename unordered_type::bucket_type buckets2 [BucketSize*2]; | |
724 | unordered_type testset1 (values.begin(), values.end(), bucket_traits( | |
b32b8144 | 725 | pointer_traits<bucket_ptr>::pointer_to(buckets1[0]), BucketSize)); |
7c673cae | 726 | unordered_type testset2 (bucket_traits( |
b32b8144 | 727 | pointer_traits<bucket_ptr>::pointer_to(buckets2[0]), BucketSize*2)); |
7c673cae FG |
728 | |
729 | testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>()); | |
730 | BOOST_TEST(testset1 == testset2); | |
731 | //Ordering is not guaranteed in the cloning so insert data in a set and test | |
732 | std_multiset_t src(testset1.begin(), testset1.end()); | |
733 | std_multiset_t dst(testset2.begin(), testset2.end()); | |
734 | BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin())); | |
735 | testset2.clear_and_dispose(test::delete_disposer<value_type>()); | |
736 | BOOST_TEST (testset2.empty()); | |
737 | ||
738 | testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>()); | |
739 | BOOST_TEST(testset1 == testset2); | |
740 | //Ordering is not guaranteed in the cloning so insert data in a set and test | |
741 | std_multiset_t(testset1.begin(), testset1.end()).swap(src); | |
742 | std_multiset_t(testset2.begin(), testset2.end()).swap(dst); | |
743 | BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin())); | |
744 | testset2.clear_and_dispose(test::delete_disposer<value_type>()); | |
745 | BOOST_TEST (testset2.empty()); | |
746 | } | |
747 | } | |
748 | ||
749 | } //namespace test{ | |
750 | } //namespace intrusive{ | |
751 | } //namespace boost{ |