]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | // Copyright 2006-2009 Daniel James. | |
3 | // Distributed under the Boost Software License, Version 1.0. (See accompanying | |
4 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | // This header contains metafunctions/functions to get the equivalent | |
7 | // associative container for an unordered container, and compare the contents. | |
8 | ||
9 | #if !defined(BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER) | |
10 | #define BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER | |
11 | ||
7c673cae | 12 | #include "./helpers.hpp" |
b32b8144 FG |
13 | #include "./metafunctions.hpp" |
14 | #include <cmath> | |
15 | #include <set> | |
7c673cae FG |
16 | |
17 | #if defined(BOOST_MSVC) | |
18 | #pragma warning(push) | |
b32b8144 FG |
19 | #pragma warning(disable : 4127) // conditional expression is constant |
20 | #pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int', | |
7c673cae FG |
21 | // possible loss of data |
22 | #endif | |
23 | ||
b32b8144 FG |
24 | namespace test { |
25 | template <class X> void check_equivalent_keys(X const& x1) | |
26 | { | |
27 | BOOST_DEDUCED_TYPENAME X::key_equal eq = x1.key_eq(); | |
28 | typedef BOOST_DEDUCED_TYPENAME X::key_type key_type; | |
29 | std::set<key_type, std::less<key_type> > found_; | |
30 | ||
31 | BOOST_DEDUCED_TYPENAME X::const_iterator it = x1.begin(), end = x1.end(); | |
32 | BOOST_DEDUCED_TYPENAME X::size_type size = 0; | |
33 | while (it != end) { | |
34 | // First test that the current key has not occurred before, required | |
35 | // to test either that keys are unique or that equivalent keys are | |
36 | // adjacent. (6.3.1/6) | |
37 | key_type key = get_key<X>(*it); | |
38 | if (!found_.insert(key).second) | |
39 | BOOST_ERROR("Elements with equivalent keys aren't adjacent."); | |
40 | ||
41 | // Iterate over equivalent keys, counting them. | |
42 | unsigned int count = 0; | |
43 | do { | |
44 | ++it; | |
45 | ++count; | |
46 | ++size; | |
47 | } while (it != end && eq(get_key<X>(*it), key)); | |
48 | ||
49 | // If the container has unique keys, test that there's only one. | |
50 | // Since the previous test makes sure that all equivalent keys are | |
51 | // adjacent, this is all the equivalent keys - so the test is | |
52 | // sufficient. (6.3.1/6 again). | |
53 | if (test::has_unique_keys<X>::value && count != 1) | |
54 | BOOST_ERROR("Non-unique key."); | |
55 | ||
56 | if (x1.count(key) != count) { | |
57 | BOOST_ERROR("Incorrect output of count."); | |
58 | std::cerr << x1.count(key) << "," << count << "\n"; | |
59 | } | |
60 | ||
61 | // Check that the keys are in the correct bucket and are | |
62 | // adjacent in the bucket. | |
63 | BOOST_DEDUCED_TYPENAME X::size_type bucket = x1.bucket(key); | |
64 | BOOST_DEDUCED_TYPENAME X::const_local_iterator lit = x1.begin(bucket), | |
65 | lend = x1.end(bucket); | |
66 | ||
67 | unsigned int count_checked = 0; | |
68 | for (; lit != lend && !eq(get_key<X>(*lit), key); ++lit) { | |
69 | ++count_checked; | |
70 | } | |
71 | ||
72 | if (lit == lend) { | |
73 | BOOST_ERROR("Unable to find element with a local_iterator"); | |
74 | std::cerr << "Checked: " << count_checked << " elements" << std::endl; | |
75 | } else { | |
76 | unsigned int count2 = 0; | |
77 | for (; lit != lend && eq(get_key<X>(*lit), key); ++lit) | |
78 | ++count2; | |
79 | if (count != count2) | |
80 | BOOST_ERROR("Element count doesn't match local_iterator."); | |
81 | for (; lit != lend; ++lit) { | |
82 | if (eq(get_key<X>(*lit), key)) { | |
83 | BOOST_ERROR("Non-adjacent element with equivalent key " | |
7c673cae | 84 | "in bucket."); |
b32b8144 FG |
85 | break; |
86 | } | |
87 | } | |
88 | } | |
89 | }; | |
7c673cae | 90 | |
b32b8144 | 91 | // Check that size matches up. |
7c673cae | 92 | |
b32b8144 FG |
93 | if (x1.size() != size) { |
94 | BOOST_ERROR("x1.size() doesn't match actual size."); | |
95 | std::cout << x1.size() << "/" << size << std::endl; | |
96 | } | |
7c673cae | 97 | |
b32b8144 | 98 | // Check the load factor. |
7c673cae | 99 | |
b32b8144 FG |
100 | float load_factor = size == 0 ? 0 |
101 | : static_cast<float>(size) / | |
102 | static_cast<float>(x1.bucket_count()); | |
103 | using namespace std; | |
104 | if (fabs(x1.load_factor() - load_factor) > x1.load_factor() / 64) | |
105 | BOOST_ERROR("x1.load_factor() doesn't match actual load_factor."); | |
7c673cae | 106 | |
b32b8144 | 107 | // Check that size in the buckets matches up. |
7c673cae | 108 | |
b32b8144 | 109 | BOOST_DEDUCED_TYPENAME X::size_type bucket_size = 0; |
7c673cae | 110 | |
b32b8144 FG |
111 | for (BOOST_DEDUCED_TYPENAME X::size_type i = 0; i < x1.bucket_count(); |
112 | ++i) { | |
113 | for (BOOST_DEDUCED_TYPENAME X::const_local_iterator begin2 = x1.begin(i), | |
114 | end2 = x1.end(i); | |
115 | begin2 != end2; ++begin2) { | |
116 | ++bucket_size; | |
117 | } | |
118 | } | |
7c673cae | 119 | |
b32b8144 FG |
120 | if (x1.size() != bucket_size) { |
121 | BOOST_ERROR("x1.size() doesn't match bucket size."); | |
122 | std::cout << x1.size() << "/" << bucket_size << std::endl; | |
7c673cae | 123 | } |
b32b8144 | 124 | } |
7c673cae FG |
125 | } |
126 | ||
127 | #if defined(BOOST_MSVC) | |
128 | #pragma warning(pop) | |
129 | #endif | |
130 | ||
131 | #endif |