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 BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER
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
25namespace 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

source code of boost/libs/unordered/test/helpers/invariants.hpp