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