1 | // ----------------------------------------------------------- |
2 | // Copyright (c) 2001 Jeremy Siek |
3 | // Copyright (c) 2003-2006 Gennaro Prota |
4 | // Copyright (c) 2014 Ahmed Charles |
5 | // Copyright (c) 2014 Riccardo Marcangelo |
6 | // |
7 | // Copyright (c) 2014 Glen Joseph Fernandes |
8 | // glenfe at live dot com |
9 | // |
10 | // Distributed under the Boost Software License, Version 1.0. |
11 | // (See accompanying file LICENSE_1_0.txt or copy at |
12 | // http://www.boost.org/LICENSE_1_0.txt) |
13 | // |
14 | // ----------------------------------------------------------- |
15 | |
16 | #include "bitset_test.hpp" |
17 | #include "boost/dynamic_bitset/dynamic_bitset.hpp" |
18 | #include "boost/limits.hpp" |
19 | #include "boost/config.hpp" |
20 | |
21 | #include "boost/detail/workaround.hpp" |
22 | |
23 | #if !defined(BOOST_NO_CXX11_ALLOCATOR) |
24 | #include <cstdlib> |
25 | |
26 | template<class T> |
27 | class minimal_allocator { |
28 | public: |
29 | typedef T value_type; |
30 | |
31 | minimal_allocator() {} |
32 | |
33 | template <typename U> |
34 | minimal_allocator(const minimal_allocator<U>&) {} |
35 | |
36 | T* allocate(std::size_t n) { |
37 | void* p = std::malloc(size: sizeof(T) * n); |
38 | if (!p) { |
39 | throw std::bad_alloc(); |
40 | } |
41 | return static_cast<T*>(p); |
42 | } |
43 | |
44 | void deallocate(T* p, std::size_t) { |
45 | std::free(ptr: p); |
46 | } |
47 | }; |
48 | #endif |
49 | |
50 | #define BOOST_BITSET_TEST_COUNT(x) (sizeof(x)/sizeof(x[0])) |
51 | |
52 | |
53 | // Codewarrior 8.3 for Win fails without this. |
54 | // Thanks Howard Hinnant ;) |
55 | #if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x |
56 | # pragma parse_func_templ off |
57 | #endif |
58 | |
59 | |
60 | template <typename Tests, typename String> |
61 | void run_string_tests(const String& s |
62 | BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tests) |
63 | ) |
64 | { |
65 | |
66 | const std::size_t len = s.length(); |
67 | const std::size_t step = len/4 ? len/4 : 1; |
68 | |
69 | // bitset length determined by the string-related arguments |
70 | std::size_t i; |
71 | for (i = 0; i <= len/2 ; i += step) { |
72 | Tests::from_string(s, i, len/2); // len/2 - i bits |
73 | Tests::from_string(s, i, len); // len - i bits |
74 | Tests::from_string(s, i, 1 + len*2); // len - i bits |
75 | } |
76 | |
77 | // bitset length explicitly specified |
78 | for (i = 0; i <= len/2; i += step) { |
79 | for (std::size_t sz = 0; sz <= len*4; sz+= step*2) { |
80 | Tests::from_string(s, i, len/2, sz); |
81 | Tests::from_string(s, i, len, sz); |
82 | Tests::from_string(s, i, 1 + len*2, sz); |
83 | |
84 | } |
85 | } |
86 | |
87 | } |
88 | |
89 | // tests the do-the-right-thing constructor dispatch |
90 | template <typename Tests, typename T> |
91 | void run_numeric_ctor_tests( BOOST_EXPLICIT_TEMPLATE_TYPE(Tests) |
92 | BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(T) ) |
93 | { |
94 | |
95 | const int bits_per_block = Tests::bits_per_block; |
96 | const int width = std::numeric_limits<T>::digits; |
97 | const T ma = (std::numeric_limits<T>::max)(); |
98 | const T mi = (std::numeric_limits<T>::min)(); |
99 | |
100 | int sizes[] = { |
101 | 0, 7*width/10, width, 13*width/10, 3*width, |
102 | 7*bits_per_block/10, bits_per_block, 13*bits_per_block/10, 3*bits_per_block |
103 | }; |
104 | |
105 | const T numbers[] = { |
106 | T(-1), T(-3), T(-8), T(-15), T(mi/2), T(mi), |
107 | T(0), T(1), T(3), T(8), T(15), T(ma/2), T(ma) |
108 | }; |
109 | |
110 | for (std::size_t s = 0; s < BOOST_BITSET_TEST_COUNT(sizes); ++s) { |
111 | for (std::size_t n = 0; n < BOOST_BITSET_TEST_COUNT(numbers); ++n ) { |
112 | |
113 | // can match ctor from ulong or templated one |
114 | Tests::from_unsigned_long(sizes[s], numbers[n]); |
115 | |
116 | typedef std::size_t compare_type; |
117 | const compare_type sz = sizes[s]; |
118 | // this condition is to be sure that size is representable in T, so |
119 | // that for signed T's we avoid implementation-defined behavior [if ma |
120 | // is larger than what std::size_t can hold then this is ok for our |
121 | // purposes: our sizes are anyhow < max(size_t)], which in turn could |
122 | // make the first argument of from_unsigned_long() a small negative, |
123 | // later converted to a very large unsigned. Example: signed 8-bit |
124 | // char (CHAR_MAX=127), bits_per_block=64, sz = 192 > 127. |
125 | const bool fits = |
126 | sz <= static_cast<compare_type>(ma); |
127 | |
128 | if (fits) { |
129 | // can match templated ctor only (so we test dispatching) |
130 | Tests::from_unsigned_long(static_cast<T>(sizes[s]), numbers[n]); |
131 | } |
132 | |
133 | } |
134 | } |
135 | |
136 | } |
137 | |
138 | |
139 | template <typename Block> |
140 | void run_test_cases( BOOST_EXPLICIT_TEMPLATE_TYPE(Block) ) |
141 | { |
142 | typedef boost::dynamic_bitset<Block> bitset_type; |
143 | typedef bitset_test<bitset_type> Tests; |
144 | const int bits_per_block = bitset_type::bits_per_block; |
145 | |
146 | const std::string long_string = get_long_string(); |
147 | const Block all_1s = static_cast<Block>(-1); |
148 | |
149 | //===================================================================== |
150 | // Test construction from unsigned long |
151 | { |
152 | // NOTE: |
153 | // |
154 | // 1. keep this in sync with the numeric types supported |
155 | // for constructor dispatch (of course) |
156 | // 2. bool is tested separately; ugly and inelegant, but |
157 | // we don't have much time to think of a better solution |
158 | // which is likely to work on broken compilers |
159 | // |
160 | const int sizes[] = { |
161 | 0, 1, 3, |
162 | 7*bits_per_block/10, bits_per_block, 13*bits_per_block/10, 3*bits_per_block |
163 | }; |
164 | |
165 | const bool values[] = { false, true }; |
166 | |
167 | for (std::size_t s = 0; s < BOOST_BITSET_TEST_COUNT(sizes); ++s) { |
168 | for (std::size_t v = 0; v < BOOST_BITSET_TEST_COUNT(values); ++v) { |
169 | Tests::from_unsigned_long(sizes[s], values[v]); |
170 | Tests::from_unsigned_long(sizes[s] != 0, values[v]); |
171 | } |
172 | } |
173 | |
174 | run_numeric_ctor_tests<Tests, char>(); |
175 | |
176 | #if !defined(BOOST_NO_INTRINSIC_WCHAR_T) |
177 | run_numeric_ctor_tests<Tests, wchar_t>(); |
178 | #endif |
179 | |
180 | run_numeric_ctor_tests<Tests, signed char>(); |
181 | run_numeric_ctor_tests<Tests, short int>(); |
182 | run_numeric_ctor_tests<Tests, int>(); |
183 | run_numeric_ctor_tests<Tests, long int>(); |
184 | |
185 | run_numeric_ctor_tests<Tests, unsigned char>(); |
186 | run_numeric_ctor_tests<Tests, unsigned short>(); |
187 | run_numeric_ctor_tests<Tests, unsigned int>(); |
188 | run_numeric_ctor_tests<Tests, unsigned long>(); |
189 | |
190 | #if defined(BOOST_HAS_LONG_LONG) |
191 | run_numeric_ctor_tests<Tests, ::boost::long_long_type>(); |
192 | run_numeric_ctor_tests<Tests, ::boost::ulong_long_type>(); |
193 | #endif |
194 | |
195 | } |
196 | //===================================================================== |
197 | // Test construction from a string |
198 | { |
199 | |
200 | run_string_tests<Tests>(std::string("" )); // empty string |
201 | run_string_tests<Tests>(std::string("1" )); |
202 | |
203 | run_string_tests<Tests>(long_string); |
204 | |
205 | # if !defined BOOST_NO_STD_WSTRING |
206 | // I need to decide what to do for non "C" locales here. On |
207 | // one hand I should have better tests. On the other one |
208 | // I don't want tests for dynamic_bitset to cope with locales, |
209 | // ctype::widen, etc. (but that's what you deserve when you |
210 | // don't separate concerns at the library level) |
211 | // |
212 | run_string_tests<Tests>( |
213 | std::wstring(L"11111000000111111111010101010101010101010111111" )); |
214 | # endif |
215 | |
216 | // Note that these are _valid_ arguments |
217 | Tests::from_string(std::string("x11y" ), 1, 2); |
218 | Tests::from_string(std::string("x11" ), 1, 10); |
219 | Tests::from_string(std::string("x11" ), 1, 10, 10); |
220 | |
221 | } |
222 | //===================================================================== |
223 | // test from_block_range |
224 | { |
225 | std::vector<Block> blocks; |
226 | Tests::from_block_range(blocks); |
227 | } |
228 | { |
229 | std::vector<Block> blocks(3); |
230 | blocks[0] = static_cast<Block>(0); |
231 | blocks[1] = static_cast<Block>(1); |
232 | blocks[2] = all_1s; |
233 | Tests::from_block_range(blocks); |
234 | } |
235 | { |
236 | const unsigned int n = (std::numeric_limits<unsigned char>::max)(); |
237 | std::vector<Block> blocks(n); |
238 | for (typename std::vector<Block>::size_type i = 0; i < n; ++i) |
239 | blocks[i] = static_cast<Block>(i); |
240 | Tests::from_block_range(blocks); |
241 | } |
242 | //===================================================================== |
243 | // test to_block_range |
244 | { |
245 | bitset_type b; |
246 | Tests::to_block_range(b); |
247 | } |
248 | { |
249 | bitset_type b(1, 1ul); |
250 | Tests::to_block_range(b); |
251 | } |
252 | { |
253 | bitset_type b(long_string); |
254 | Tests::to_block_range(b); |
255 | } |
256 | |
257 | //===================================================================== |
258 | // Test copy constructor |
259 | { |
260 | boost::dynamic_bitset<Block> b; |
261 | Tests::copy_constructor(b); |
262 | } |
263 | { |
264 | boost::dynamic_bitset<Block> b(std::string("0" )); |
265 | Tests::copy_constructor(b); |
266 | } |
267 | { |
268 | boost::dynamic_bitset<Block> b(long_string); |
269 | Tests::copy_constructor(b); |
270 | } |
271 | //===================================================================== |
272 | // Test copy assignment operator |
273 | { |
274 | bitset_type a, b; |
275 | Tests::copy_assignment_operator(a, b); |
276 | } |
277 | { |
278 | bitset_type a(std::string("1" )), b(std::string("0" )); |
279 | Tests::copy_assignment_operator(a, b); |
280 | } |
281 | { |
282 | bitset_type a(long_string), b(long_string); |
283 | Tests::copy_assignment_operator(a, b); |
284 | } |
285 | { |
286 | bitset_type a; |
287 | bitset_type b(long_string); // b greater than a, a empty |
288 | Tests::copy_assignment_operator(a, b); |
289 | } |
290 | { |
291 | bitset_type a(std::string("0" )); |
292 | bitset_type b(long_string); // b greater than a |
293 | Tests::copy_assignment_operator(a, b); |
294 | } |
295 | |
296 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
297 | //===================================================================== |
298 | // Test move constructor |
299 | { |
300 | boost::dynamic_bitset<Block> b; |
301 | Tests::move_constructor(b); |
302 | } |
303 | { |
304 | boost::dynamic_bitset<Block> b(std::string("0" )); |
305 | Tests::move_constructor(b); |
306 | } |
307 | { |
308 | boost::dynamic_bitset<Block> b(long_string); |
309 | Tests::move_constructor(b); |
310 | } |
311 | //===================================================================== |
312 | // Test move assignment operator |
313 | { |
314 | bitset_type a, b; |
315 | Tests::move_assignment_operator(a, b); |
316 | } |
317 | { |
318 | bitset_type a(std::string("1" )), b(std::string("0" )); |
319 | Tests::move_assignment_operator(a, b); |
320 | } |
321 | { |
322 | bitset_type a(long_string), b(long_string); |
323 | Tests::move_assignment_operator(a, b); |
324 | } |
325 | { |
326 | bitset_type a; |
327 | bitset_type b(long_string); // b greater than a, a empty |
328 | Tests::move_assignment_operator(a, b); |
329 | } |
330 | { |
331 | bitset_type a(std::string("0" )); |
332 | bitset_type b(long_string); // b greater than a |
333 | Tests::move_assignment_operator(a, b); |
334 | } |
335 | #endif // BOOST_NO_CXX11_RVALUE_REFERENCES |
336 | //===================================================================== |
337 | // Test swap |
338 | { |
339 | bitset_type a; |
340 | bitset_type b(std::string("1" )); |
341 | Tests::swap(a, b); |
342 | Tests::swap(b, a); |
343 | Tests::swap(a, a); |
344 | } |
345 | { |
346 | bitset_type a; |
347 | bitset_type b(long_string); |
348 | Tests::swap(a, b); |
349 | Tests::swap(b, a); |
350 | } |
351 | { |
352 | bitset_type a(std::string("0" )); |
353 | bitset_type b(long_string); |
354 | Tests::swap(a, b); |
355 | Tests::swap(b, a); |
356 | Tests::swap(a, a); |
357 | Tests::swap(b, b); |
358 | } |
359 | //===================================================================== |
360 | // Test resize |
361 | { |
362 | boost::dynamic_bitset<Block> a; |
363 | Tests::resize(a); |
364 | } |
365 | { |
366 | boost::dynamic_bitset<Block> a(std::string("0" )); |
367 | Tests::resize(a); |
368 | } |
369 | { |
370 | boost::dynamic_bitset<Block> a(std::string("1" )); |
371 | Tests::resize(a); |
372 | } |
373 | { |
374 | boost::dynamic_bitset<Block> a(long_string); |
375 | Tests::resize(a); |
376 | } |
377 | //===================================================================== |
378 | // Test clear |
379 | { |
380 | boost::dynamic_bitset<Block> a; |
381 | Tests::clear(a); |
382 | } |
383 | { |
384 | boost::dynamic_bitset<Block> a(long_string); |
385 | Tests::clear(a); |
386 | } |
387 | //===================================================================== |
388 | // Test pop back |
389 | { |
390 | boost::dynamic_bitset<Block> a(std::string("01" )); |
391 | Tests::pop_back(a); |
392 | } |
393 | { |
394 | boost::dynamic_bitset<Block> a(std::string("10" )); |
395 | Tests::pop_back(a); |
396 | } |
397 | { |
398 | const int size_to_fill_all_blocks = 4 * bits_per_block; |
399 | boost::dynamic_bitset<Block> a(size_to_fill_all_blocks, 255ul); |
400 | Tests::pop_back(a); |
401 | } |
402 | { |
403 | boost::dynamic_bitset<Block> a(long_string); |
404 | Tests::pop_back(a); |
405 | } |
406 | //===================================================================== |
407 | // Test append bit |
408 | { |
409 | boost::dynamic_bitset<Block> a; |
410 | Tests::append_bit(a); |
411 | } |
412 | { |
413 | boost::dynamic_bitset<Block> a(std::string("0" )); |
414 | Tests::append_bit(a); |
415 | } |
416 | { |
417 | boost::dynamic_bitset<Block> a(std::string("1" )); |
418 | Tests::append_bit(a); |
419 | } |
420 | { |
421 | const int size_to_fill_all_blocks = 4 * bits_per_block; |
422 | boost::dynamic_bitset<Block> a(size_to_fill_all_blocks, 255ul); |
423 | Tests::append_bit(a); |
424 | } |
425 | { |
426 | boost::dynamic_bitset<Block> a(long_string); |
427 | Tests::append_bit(a); |
428 | } |
429 | //===================================================================== |
430 | // Test append block |
431 | { |
432 | boost::dynamic_bitset<Block> a; |
433 | Tests::append_block(a); |
434 | } |
435 | { |
436 | boost::dynamic_bitset<Block> a(std::string("0" )); |
437 | Tests::append_block(a); |
438 | } |
439 | { |
440 | boost::dynamic_bitset<Block> a(std::string("1" )); |
441 | Tests::append_block(a); |
442 | } |
443 | { |
444 | const int size_to_fill_all_blocks = 4 * bits_per_block; |
445 | boost::dynamic_bitset<Block> a(size_to_fill_all_blocks, 15ul); |
446 | Tests::append_block(a); |
447 | } |
448 | { |
449 | boost::dynamic_bitset<Block> a(long_string); |
450 | Tests::append_block(a); |
451 | } |
452 | //===================================================================== |
453 | // Test append block range |
454 | { |
455 | boost::dynamic_bitset<Block> a; |
456 | std::vector<Block> blocks; |
457 | Tests::append_block_range(a, blocks); |
458 | } |
459 | { |
460 | boost::dynamic_bitset<Block> a(std::string("0" )); |
461 | std::vector<Block> blocks(3); |
462 | blocks[0] = static_cast<Block>(0); |
463 | blocks[1] = static_cast<Block>(1); |
464 | blocks[2] = all_1s; |
465 | Tests::append_block_range(a, blocks); |
466 | } |
467 | { |
468 | boost::dynamic_bitset<Block> a(std::string("1" )); |
469 | const unsigned int n = (std::numeric_limits<unsigned char>::max)(); |
470 | std::vector<Block> blocks(n); |
471 | for (typename std::vector<Block>::size_type i = 0; i < n; ++i) |
472 | blocks[i] = static_cast<Block>(i); |
473 | Tests::append_block_range(a, blocks); |
474 | } |
475 | { |
476 | boost::dynamic_bitset<Block> a; |
477 | a.append(Block(1)); |
478 | a.append(Block(2)); |
479 | Block x[] = {3, 4, 5}; |
480 | std::size_t sz = sizeof(x) / sizeof(x[0]); |
481 | std::vector<Block> blocks(x, x + sz); |
482 | Tests::append_block_range(a, blocks); |
483 | } |
484 | { |
485 | boost::dynamic_bitset<Block> a(long_string); |
486 | std::vector<Block> blocks(3); |
487 | blocks[0] = static_cast<Block>(0); |
488 | blocks[1] = static_cast<Block>(1); |
489 | blocks[2] = all_1s; |
490 | Tests::append_block_range(a, blocks); |
491 | } |
492 | //===================================================================== |
493 | // Test bracket operator |
494 | { |
495 | boost::dynamic_bitset<Block> b1; |
496 | std::vector<bool> bitvec1; |
497 | Tests::operator_bracket(b1, bitvec1); |
498 | } |
499 | { |
500 | boost::dynamic_bitset<Block> b(std::string("1" )); |
501 | std::vector<bool> bit_vec(1, true); |
502 | Tests::operator_bracket(b, bit_vec); |
503 | } |
504 | { |
505 | boost::dynamic_bitset<Block> b(long_string); |
506 | std::size_t n = long_string.size(); |
507 | std::vector<bool> bit_vec(n); |
508 | for (std::size_t i = 0; i < n; ++i) |
509 | bit_vec[i] = long_string[n - 1 - i] == '0' ? 0 : 1; |
510 | Tests::operator_bracket(b, bit_vec); |
511 | } |
512 | #if !defined(BOOST_NO_CXX11_ALLOCATOR) |
513 | { |
514 | typedef boost::dynamic_bitset<Block, |
515 | minimal_allocator<Block> > Bitset; |
516 | Bitset b; |
517 | bitset_test<Bitset>::max_size(b); |
518 | } |
519 | #endif |
520 | } |
521 | |
522 | int |
523 | test_main(int, char*[]) |
524 | { |
525 | run_test_cases<unsigned char>(); |
526 | run_test_cases<unsigned short>(); |
527 | run_test_cases<unsigned int>(); |
528 | run_test_cases<unsigned long>(); |
529 | # ifdef BOOST_HAS_LONG_LONG |
530 | run_test_cases< ::boost::ulong_long_type>(); |
531 | # endif |
532 | |
533 | return 0; |
534 | } |
535 | |