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 12 #include "./helpers.hpp" 13 #include "./metafunctions.hpp" 14 #include <cmath> 15 #include <set> 16 17 #if defined(BOOST_MSVC) 18 #pragma warning(push) 19 #pragma warning(disable : 4127) // conditional expression is constant 20 #pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int', 21 // possible loss of data 22 #endif 23 24 namespace test { check_equivalent_keys(X const & x1)25 template <class X> void check_equivalent_keys(X const& x1) 26 { 27 typename X::key_equal eq = x1.key_eq(); 28 typedef typename X::key_type key_type; 29 std::set<key_type, std::less<key_type> > found_; 30 31 typename X::const_iterator it = x1.begin(), end = x1.end(); 32 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 typename X::size_type bucket = x1.bucket(key); 64 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 " 84 "in bucket."); 85 break; 86 } 87 } 88 } 89 }; 90 91 // Check that size matches up. 92 93 if (x1.size() != size) { 94 BOOST_ERROR("x1.size() doesn't match actual size."); 95 std::cout << x1.size() << "/" << size << std::endl; 96 } 97 98 // Check the load factor. 99 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."); 106 107 // Check that size in the buckets matches up. 108 109 typename X::size_type bucket_size = 0; 110 111 for (typename X::size_type i = 0; i < x1.bucket_count(); ++i) { 112 for (typename X::const_local_iterator begin2 = x1.begin(i), 113 end2 = x1.end(i); 114 begin2 != end2; ++begin2) { 115 ++bucket_size; 116 } 117 } 118 119 if (x1.size() != bucket_size) { 120 BOOST_ERROR("x1.size() doesn't match bucket size."); 121 std::cout << x1.size() << "/" << bucket_size << std::endl; 122 } 123 } 124 } 125 126 #if defined(BOOST_MSVC) 127 #pragma warning(pop) 128 #endif 129 130 #endif 131