1 files changed, 130 insertions, 0 deletions
diff --git a/src/boost/libs/unordered/test/helpers/invariants.hpp b/src/boost/libs/unordered/test/helpers/invariants.hpp
new file mode 100644
index 000000000..a555da60c
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/invariants.hpp
@@ -0,0 +1,130 @@
+
+// Copyright 2006-2009 Daniel James.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+// This header contains metafunctions/functions to get the equivalent
+// associative container for an unordered container, and compare the contents.
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER
+
+#include "./helpers.hpp"
+#include "./metafunctions.hpp"
+#include <cmath>
+#include <set>
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable : 4127) // conditional expression is constant
+#pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int',
+                                // possible loss of data
+#endif
+
+namespace test {
+  template <class X> void check_equivalent_keys(X const& x1)
+  {
+    typename X::key_equal eq = x1.key_eq();
+    typedef typename X::key_type key_type;
+    std::set<key_type, std::less<key_type> > found_;
+
+    typename X::const_iterator it = x1.begin(), end = x1.end();
+    typename X::size_type size = 0;
+    while (it != end) {
+      // First test that the current key has not occurred before, required
+      // to test either that keys are unique or that equivalent keys are
+      // adjacent. (6.3.1/6)
+      key_type key = get_key<X>(*it);
+      if (!found_.insert(key).second)
+        BOOST_ERROR("Elements with equivalent keys aren't adjacent.");
+
+      // Iterate over equivalent keys, counting them.
+      unsigned int count = 0;
+      do {
+        ++it;
+        ++count;
+        ++size;
+      } while (it != end && eq(get_key<X>(*it), key));
+
+      // If the container has unique keys, test that there's only one.
+      // Since the previous test makes sure that all equivalent keys are
+      // adjacent, this is all the equivalent keys - so the test is
+      // sufficient. (6.3.1/6 again).
+      if (test::has_unique_keys<X>::value && count != 1)
+        BOOST_ERROR("Non-unique key.");
+
+      if (x1.count(key) != count) {
+        BOOST_ERROR("Incorrect output of count.");
+        std::cerr << x1.count(key) << "," << count << "\n";
+      }
+
+      // Check that the keys are in the correct bucket and are
+      // adjacent in the bucket.
+      typename X::size_type bucket = x1.bucket(key);
+      typename X::const_local_iterator lit = x1.begin(bucket),
+                                       lend = x1.end(bucket);
+
+      unsigned int count_checked = 0;
+      for (; lit != lend && !eq(get_key<X>(*lit), key); ++lit) {
+        ++count_checked;
+      }
+
+      if (lit == lend) {
+        BOOST_ERROR("Unable to find element with a local_iterator");
+        std::cerr << "Checked: " << count_checked << " elements" << std::endl;
+      } else {
+        unsigned int count2 = 0;
+        for (; lit != lend && eq(get_key<X>(*lit), key); ++lit)
+          ++count2;
+        if (count != count2)
+          BOOST_ERROR("Element count doesn't match local_iterator.");
+        for (; lit != lend; ++lit) {
+          if (eq(get_key<X>(*lit), key)) {
+            BOOST_ERROR("Non-adjacent element with equivalent key "
+                        "in bucket.");
+            break;
+          }
+        }
+      }
+    };
+
+    // Check that size matches up.
+
+    if (x1.size() != size) {
+      BOOST_ERROR("x1.size() doesn't match actual size.");
+      std::cout << x1.size() << "/" << size << std::endl;
+    }
+
+    // Check the load factor.
+
+    float load_factor = size == 0 ? 0
+                                  : static_cast<float>(size) /
+                                      static_cast<float>(x1.bucket_count());
+    using namespace std;
+    if (fabs(x1.load_factor() - load_factor) > x1.load_factor() / 64)
+      BOOST_ERROR("x1.load_factor() doesn't match actual load_factor.");
+
+    // Check that size in the buckets matches up.
+
+    typename X::size_type bucket_size = 0;
+
+    for (typename X::size_type i = 0; i < x1.bucket_count(); ++i) {
+      for (typename X::const_local_iterator begin2 = x1.begin(i),
+                                            end2 = x1.end(i);
+           begin2 != end2; ++begin2) {
+        ++bucket_size;
+      }
+    }
+
+    if (x1.size() != bucket_size) {
+      BOOST_ERROR("x1.size() doesn't match bucket size.");
+      std::cout << x1.size() << "/" << bucket_size << std::endl;
+    }
+  }
+}
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
+#endif