Adding upstream version 14.2.21.upstream/14.2.21upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

18 files changed, 2099 insertions, 0 deletions

diff --git a/src/boost/libs/unordered/test/helpers/check_return_type.hpp b/src/boost/libs/unordered/test/helpers/check_return_type.hpp
new file mode 100644
index 00000000..1c70a8c7
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/check_return_type.hpp
@@ -0,0 +1,33 @@
+
+// Copyright 2005-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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_CHECK_RETURN_TYPE_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_CHECK_RETURN_TYPE_HEADER
+
+#include <boost/static_assert.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace test {
+  template <class T1> struct check_return_type
+  {
+    template <class T2> static void equals(T2)
+    {
+      BOOST_STATIC_ASSERT((boost::is_same<T1, T2>::value));
+    }
+
+    template <class T2> static void equals_ref(T2&)
+    {
+      BOOST_STATIC_ASSERT((boost::is_same<T1, T2>::value));
+    }
+
+    template <class T2> static void convertible(T2)
+    {
+      BOOST_STATIC_ASSERT((boost::is_convertible<T2, T1>::value));
+    }
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/count.hpp b/src/boost/libs/unordered/test/helpers/count.hpp
new file mode 100644
index 00000000..90372dca
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/count.hpp
@@ -0,0 +1,89 @@
+
+// Copyright 2008-2009 Daniel James.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or move at http://www.boost.org/LICENSE_1_0.txt)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_COUNT_HEAD)
+#define BOOST_UNORDERED_TEST_HELPERS_COUNT_HEAD
+
+#include <boost/core/lightweight_test.hpp>
+
+namespace test {
+  struct object_count
+  {
+    int instances;
+    int constructions;
+
+    object_count() : instances(0), constructions(0) {}
+    void reset() { *this = object_count(); }
+
+    void construct()
+    {
+      ++instances;
+      ++constructions;
+    }
+
+    void destruct()
+    {
+      if (instances == 0) {
+        BOOST_ERROR("Unbalanced constructions.");
+      } else {
+        --instances;
+      }
+    }
+
+    bool operator==(object_count const& x) const
+    {
+      return instances == x.instances && constructions == x.constructions;
+    }
+
+    bool operator!=(object_count const& x) const { return !(*this == x); }
+
+    friend std::ostream& operator<<(std::ostream& out, object_count const& c)
+    {
+      out << "[instances: " << c.instances
+          << ", constructions: " << c.constructions << "]";
+      return out;
+    }
+  };
+
+  // This won't be a problem as I'm only using a single compile unit
+  // in each test (this is actually require by the minimal test
+  // framework).
+  //
+  // boostinspect:nounnamed
+  namespace {
+    object_count global_object_count;
+  }
+
+  struct counted_object
+  {
+    counted_object() { global_object_count.construct(); }
+    counted_object(counted_object const&) { global_object_count.construct(); }
+    ~counted_object() { global_object_count.destruct(); }
+  };
+
+  struct check_instances
+  {
+    int instances_;
+    int constructions_;
+
+    check_instances()
+        : instances_(global_object_count.instances),
+          constructions_(global_object_count.constructions)
+    {
+    }
+    ~check_instances()
+    {
+      BOOST_TEST(global_object_count.instances == instances_);
+    }
+
+    int instances() const { return global_object_count.instances - instances_; }
+    int constructions() const
+    {
+      return global_object_count.constructions - constructions_;
+    }
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/equivalent.hpp b/src/boost/libs/unordered/test/helpers/equivalent.hpp
new file mode 100644
index 00000000..bd27d8df
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/equivalent.hpp
@@ -0,0 +1,96 @@
+
+// Copyright 2005-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)
+
+#if !defined(BOOST_UNORDERED_TESTS_EQUIVALENT_HEADER)
+#define BOOST_UNORDERED_TESTS_EQUIVALENT_HEADER
+
+#include "./fwd.hpp"
+#include "./list.hpp"
+#include "./metafunctions.hpp"
+#include <algorithm>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/unordered_map.hpp>
+#include <boost/unordered_set.hpp>
+
+namespace test {
+  template <class T1, class T2>
+  bool equivalent_impl(T1 const& x, T2 const& y, base_type)
+  {
+    return x == y;
+  }
+
+  template <class T>
+  bool equivalent_impl(
+    boost::hash<T> const&, boost::hash<T> const&, derived_type)
+  {
+    return true;
+  }
+
+  template <class T>
+  bool equivalent_impl(
+    std::equal_to<T> const&, std::equal_to<T> const&, derived_type)
+  {
+    return true;
+  }
+
+  template <class T1, class T2, class T3, class T4>
+  bool equivalent_impl(
+    std::pair<T1, T2> const& x1, std::pair<T3, T4> const& x2, derived_type)
+  {
+    return equivalent_impl(x1.first, x2.first, derived) &&
+           equivalent_impl(x1.second, x2.second, derived);
+  }
+
+  struct equivalent_type
+  {
+    equivalent_type() {}
+
+    template <class T1, class T2>
+    bool operator()(T1 const& x, T2 const& y) const
+    {
+      return equivalent_impl(x, y, derived);
+    }
+  };
+
+  const equivalent_type equivalent;
+
+  template <class Container> class unordered_equivalence_tester
+  {
+    typename Container::size_type size_;
+    typename Container::hasher hasher_;
+    typename Container::key_equal key_equal_;
+    float max_load_factor_;
+
+    typedef test::list<typename Container::value_type> value_list;
+    value_list values_;
+
+  public:
+    unordered_equivalence_tester(Container const& x)
+        : size_(x.size()), hasher_(x.hash_function()), key_equal_(x.key_eq()),
+          max_load_factor_(x.max_load_factor()), values_(x.begin(), x.end())
+    {
+      values_.sort();
+    }
+
+    bool operator()(Container const& x) const
+    {
+      if (!((size_ == x.size()) &&
+            (test::equivalent(hasher_, x.hash_function())) &&
+            (test::equivalent(key_equal_, x.key_eq())) &&
+            (max_load_factor_ == x.max_load_factor()) &&
+            (values_.size() == x.size())))
+        return false;
+
+      value_list copy(x.begin(), x.end());
+      copy.sort();
+      return values_ == copy;
+    }
+
+  private:
+    unordered_equivalence_tester();
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/exception_test.hpp b/src/boost/libs/unordered/test/helpers/exception_test.hpp
new file mode 100644
index 00000000..8984eee9
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/exception_test.hpp
@@ -0,0 +1,348 @@
+
+// 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)
+
+#if !defined(BOOST_UNORDERED_EXCEPTION_TEST_HEADER)
+#define BOOST_UNORDERED_EXCEPTION_TEST_HEADER
+
+#include "./count.hpp"
+#include "./test.hpp"
+
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/seq/elem.hpp>
+#include <boost/preprocessor/seq/for_each_product.hpp>
+
+#define UNORDERED_EXCEPTION_TEST_CASE(name, test_func, type)                   \
+  UNORDERED_AUTO_TEST (name) {                                                 \
+    test_func<type> fixture;                                                   \
+    ::test::lightweight::exception_safety(                                     \
+      fixture, BOOST_STRINGIZE(test_func<type>));                              \
+  }
+
+#define UNORDERED_EXCEPTION_TEST_CASE_REPEAT(name, test_func, n, type)         \
+  UNORDERED_AUTO_TEST (name) {                                                 \
+    for (unsigned i = 0; i < n; ++i) {                                         \
+      test_func<type> fixture;                                                 \
+      ::test::lightweight::exception_safety(                                   \
+        fixture, BOOST_STRINGIZE(test_func<type>));                            \
+    }                                                                          \
+  }
+
+#define UNORDERED_EPOINT_IMPL ::test::lightweight::epoint
+
+#define UNORDERED_EXCEPTION_TEST_POSTFIX RUN_TESTS()
+
+#define EXCEPTION_TESTS(test_seq, param_seq)                                   \
+  BOOST_PP_SEQ_FOR_EACH_PRODUCT(EXCEPTION_TESTS_OP, (test_seq)((1))(param_seq))
+
+#define EXCEPTION_TESTS_REPEAT(n, test_seq, param_seq)                         \
+  BOOST_PP_SEQ_FOR_EACH_PRODUCT(EXCEPTION_TESTS_OP, (test_seq)((n))(param_seq))
+
+#define EXCEPTION_TESTS_OP(r, product)                                         \
+  UNORDERED_EXCEPTION_TEST_CASE_REPEAT(                                        \
+    BOOST_PP_CAT(BOOST_PP_SEQ_ELEM(0, product),                                \
+      BOOST_PP_CAT(_, BOOST_PP_SEQ_ELEM(2, product))),                         \
+    BOOST_PP_SEQ_ELEM(0, product), BOOST_PP_SEQ_ELEM(1, product),              \
+    BOOST_PP_SEQ_ELEM(2, product))
+
+#define UNORDERED_SCOPE(scope_name)                                            \
+  for (::test::scope_guard unordered_test_guard(BOOST_STRINGIZE(scope_name));  \
+       !unordered_test_guard.dismissed(); unordered_test_guard.dismiss())
+
+#define UNORDERED_EPOINT(name)                                                 \
+  if (::test::exceptions_enabled) {                                            \
+    UNORDERED_EPOINT_IMPL(name);                                               \
+  }
+
+#define ENABLE_EXCEPTIONS                                                      \
+  ::test::exceptions_enable BOOST_PP_CAT(ENABLE_EXCEPTIONS_, __LINE__)(true)
+
+#define DISABLE_EXCEPTIONS                                                     \
+  ::test::exceptions_enable BOOST_PP_CAT(ENABLE_EXCEPTIONS_, __LINE__)(false)
+
+namespace test {
+  static char const* scope = "";
+  bool exceptions_enabled = false;
+
+  class scope_guard
+  {
+    scope_guard& operator=(scope_guard const&);
+    scope_guard(scope_guard const&);
+
+    char const* old_scope_;
+    char const* scope_;
+    bool dismissed_;
+
+  public:
+    scope_guard(char const* name)
+        : old_scope_(scope), scope_(name), dismissed_(false)
+    {
+      scope = scope_;
+    }
+
+    ~scope_guard()
+    {
+      if (dismissed_)
+        scope = old_scope_;
+    }
+
+    void dismiss() { dismissed_ = true; }
+
+    bool dismissed() const { return dismissed_; }
+  };
+
+  class exceptions_enable
+  {
+    exceptions_enable& operator=(exceptions_enable const&);
+    exceptions_enable(exceptions_enable const&);
+
+    bool old_value_;
+    bool released_;
+
+  public:
+    exceptions_enable(bool enable)
+        : old_value_(exceptions_enabled), released_(false)
+    {
+      exceptions_enabled = enable;
+    }
+
+    ~exceptions_enable()
+    {
+      if (!released_) {
+        exceptions_enabled = old_value_;
+        released_ = true;
+      }
+    }
+
+    void release()
+    {
+      if (!released_) {
+        exceptions_enabled = old_value_;
+        released_ = true;
+      }
+    }
+  };
+
+  struct exception_base
+  {
+    struct data_type
+    {
+    };
+    struct strong_type
+    {
+      template <class T> void store(T const&) {}
+      template <class T> void test(T const&) const {}
+    };
+    data_type init() const { return data_type(); }
+    void check BOOST_PREVENT_MACRO_SUBSTITUTION() const {}
+  };
+
+  template <class T, class P1, class P2, class T2>
+  inline void call_ignore_extra_parameters(
+    void (T::*fn)() const, T2 const& obj, P1&, P2&)
+  {
+    (obj.*fn)();
+  }
+
+  template <class T, class P1, class P2, class T2>
+  inline void call_ignore_extra_parameters(
+    void (T::*fn)(P1&) const, T2 const& obj, P1& p1, P2&)
+  {
+    (obj.*fn)(p1);
+  }
+
+  template <class T, class P1, class P2, class T2>
+  inline void call_ignore_extra_parameters(
+    void (T::*fn)(P1&, P2&) const, T2 const& obj, P1& p1, P2& p2)
+  {
+    (obj.*fn)(p1, p2);
+  }
+
+  template <class T> T const& constant(T const& x) { return x; }
+
+  template <class Test> class test_runner
+  {
+    Test const& test_;
+    bool exception_in_check_;
+
+    test_runner(test_runner const&);
+    test_runner& operator=(test_runner const&);
+
+  public:
+    test_runner(Test const& t) : test_(t), exception_in_check_(false) {}
+    void run()
+    {
+      DISABLE_EXCEPTIONS;
+      test::check_instances check;
+      test::scope = "";
+      typename Test::data_type x(test_.init());
+      typename Test::strong_type strong;
+      strong.store(x);
+      try {
+        ENABLE_EXCEPTIONS;
+        call_ignore_extra_parameters<Test, typename Test::data_type,
+          typename Test::strong_type>(&Test::run, test_, x, strong);
+      } catch (...) {
+        try {
+          DISABLE_EXCEPTIONS;
+          call_ignore_extra_parameters<Test, typename Test::data_type const,
+            typename Test::strong_type const>(
+            &Test::check, test_, constant(x), constant(strong));
+        } catch (...) {
+          exception_in_check_ = true;
+        }
+        throw;
+      }
+    }
+    void end()
+    {
+      if (exception_in_check_) {
+        BOOST_ERROR("Unexcpected exception in test_runner check call.");
+      }
+    }
+  };
+
+  // Quick exception testing based on lightweight test
+
+  namespace lightweight {
+    static int iteration;
+    static int count;
+
+    struct test_exception
+    {
+      char const* name;
+      test_exception(char const* n) : name(n) {}
+    };
+
+    struct test_failure
+    {
+    };
+
+    void epoint(char const* name)
+    {
+      ++count;
+      if (count == iteration) {
+        throw test_exception(name);
+      }
+    }
+
+    template <class Test>
+    void exception_safety(Test const& f, char const* /*name*/)
+    {
+      test_runner<Test> runner(f);
+
+      iteration = 0;
+      bool success = false;
+      unsigned int failure_count = 0;
+      char const* error_msg = 0;
+      do {
+        int error_count = boost::detail::test_errors();
+        ++iteration;
+        count = 0;
+
+        try {
+          runner.run();
+          success = true;
+        } catch (test_failure) {
+          error_msg = "test_failure caught.";
+          break;
+        } catch (test_exception e) {
+          if (error_count != boost::detail::test_errors()) {
+            BOOST_LIGHTWEIGHT_TEST_OSTREAM
+              << "Iteration: " << iteration
+              << " Error found for epoint: " << e.name << std::endl;
+          }
+        } catch (...) {
+          error_msg = "Unexpected exception.";
+          break;
+        }
+
+        if (error_count != boost::detail::test_errors()) {
+          ++failure_count;
+        }
+      } while (!success && failure_count < 5);
+
+      if (error_msg) {
+        BOOST_ERROR(error_msg);
+      }
+      runner.end();
+    }
+
+    //
+    // An alternative way to run exception tests.
+    // See merge_exception_tests.cpp for an example.
+
+    struct exception_looper
+    {
+      bool success;
+      unsigned int failure_count;
+      char const* error_msg;
+      int error_count;
+
+      exception_looper() : success(false), failure_count(0), error_msg(0) {}
+
+      void start() { iteration = 0; }
+
+      bool loop_condition() const
+      {
+        return !error_msg && !success && failure_count < 5;
+      }
+
+      void start_iteration()
+      {
+        error_count = boost::detail::test_errors();
+        ++iteration;
+        count = 0;
+      }
+
+      void successful_run() { success = true; }
+
+      void test_failure_caught(test_failure const&)
+      {
+        error_msg = "test_failure caught.";
+      }
+
+      void test_exception_caught(test_exception const& e)
+      {
+        if (error_count != boost::detail::test_errors()) {
+          BOOST_LIGHTWEIGHT_TEST_OSTREAM
+            << "Iteration: " << iteration
+            << " Error found for epoint: " << e.name << std::endl;
+        }
+      }
+
+      void unexpected_exception_caught()
+      {
+        error_msg = "Unexpected exception.";
+      }
+
+      void end()
+      {
+        if (error_msg) {
+          BOOST_ERROR(error_msg);
+        }
+      }
+    };
+
+#define EXCEPTION_LOOP(op)                                                     \
+  test::lightweight::exception_looper looper;                                  \
+  looper.start();                                                              \
+  while (looper.loop_condition()) {                                            \
+    looper.start_iteration();                                                  \
+    try {                                                                      \
+      op;                                                                      \
+      looper.successful_run();                                                 \
+    } catch (test::lightweight::test_failure e) {                              \
+      looper.test_failure_caught(e);                                           \
+    } catch (test::lightweight::test_exception e) {                            \
+      looper.test_exception_caught(e);                                         \
+    } catch (...) {                                                            \
+      looper.unexpected_exception_caught();                                    \
+    }                                                                          \
+  }                                                                            \
+  looper.end();
+  }
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/fwd.hpp b/src/boost/libs/unordered/test/helpers/fwd.hpp
new file mode 100644
index 00000000..a5657e01
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/fwd.hpp
@@ -0,0 +1,32 @@
+
+// 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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_FWD_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_FWD_HEADER
+
+#include <string>
+
+namespace test {
+  typedef enum {
+    default_generator,
+    generate_collisions,
+    limited_range
+  } random_generator;
+
+  int generate(int const*, random_generator);
+  char generate(char const*, random_generator);
+  signed char generate(signed char const*, random_generator);
+  std::string generate(std::string const*, random_generator);
+  float generate(float const*, random_generator);
+
+  struct base_type
+  {
+  } base;
+  struct derived_type : base_type
+  {
+  } derived;
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/generators.hpp b/src/boost/libs/unordered/test/helpers/generators.hpp
new file mode 100644
index 00000000..c9ed42bd
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/generators.hpp
@@ -0,0 +1,93 @@
+
+// Copyright 2005-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 uses std::rand to generate random values for tests.
+// Which is not good as different platforms will be running different tests.
+// It would be much better to use Boost.Random, but it doesn't
+// support all the compilers that I want to test on.
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_GENERATORS_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_GENERATORS_HEADER
+
+#include "./fwd.hpp"
+#include <boost/type_traits/add_const.hpp>
+#include <cstdlib>
+#include <stdexcept>
+#include <string>
+#include <utility>
+
+namespace test {
+  struct seed_t
+  {
+    seed_t(unsigned int x)
+    {
+      using namespace std;
+      srand(x);
+    }
+  };
+
+  std::size_t random_value(std::size_t max)
+  {
+    using namespace std;
+    return static_cast<std::size_t>(rand()) % max;
+  }
+
+  inline int generate(int const*, random_generator g)
+  {
+    using namespace std;
+    int value = rand();
+    if (g == limited_range) {
+      value = value % 100;
+    }
+    return value;
+  }
+
+  inline char generate(char const*, random_generator)
+  {
+    using namespace std;
+    return static_cast<char>((rand() >> 1) % (128 - 32) + 32);
+  }
+
+  inline signed char generate(signed char const*, random_generator)
+  {
+    using namespace std;
+    return static_cast<signed char>(rand());
+  }
+
+  inline std::string generate(std::string const*, random_generator g)
+  {
+    using namespace std;
+
+    char* char_ptr = 0;
+
+    std::string result;
+
+    if (g == limited_range) {
+      std::size_t length = test::random_value(2) + 2;
+
+      char const* strings[] = {"'vZh(3~ms", "%m", "_Y%U", "N'Y", "4,J_J"};
+      for (std::size_t i = 0; i < length; ++i) {
+        result += strings[random_value(sizeof(strings) / sizeof(strings[0]))];
+      }
+    } else {
+      std::size_t length = test::random_value(10) + 1;
+      for (std::size_t i = 0; i < length; ++i) {
+        result += generate(char_ptr, g);
+      }
+    }
+
+    return result;
+  }
+
+  float generate(float const*, random_generator g)
+  {
+    using namespace std;
+    int x = 0;
+    int value = generate(&x, g);
+    return (float)value / (float)RAND_MAX;
+  }
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/helpers.hpp b/src/boost/libs/unordered/test/helpers/helpers.hpp
new file mode 100644
index 00000000..146dea4d
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/helpers.hpp
@@ -0,0 +1,56 @@
+
+// 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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_HEADER
+
+#include <iterator>
+
+namespace test {
+  template <class Container> struct get_key_impl
+  {
+    typedef typename Container::key_type key_type;
+
+    static key_type const& get_key(key_type const& x) { return x; }
+
+    template <class T>
+    static key_type const& get_key(std::pair<key_type, T> const& x, char = 0)
+    {
+      return x.first;
+    }
+
+    template <class T>
+    static key_type const& get_key(
+      std::pair<key_type const, T> const& x, unsigned char = 0)
+    {
+      return x.first;
+    }
+  };
+
+  template <class Container, class T>
+  inline typename Container::key_type const& get_key(T const& x)
+  {
+    return get_key_impl<Container>::get_key(x);
+  }
+
+  // test::next
+  //
+  // Increments an iterator by 1 or a given value.
+  // Like boost::next, but simpler.
+  // Mainly because boost::next uses an MPL file
+  // which causes warnings.
+
+  template <typename Iterator> Iterator next(Iterator it) { return ++it; }
+
+  template <typename Iterator, typename IntType>
+  Iterator next(Iterator it, IntType x)
+  {
+    std::advance(it,
+      static_cast<typename std::iterator_traits<Iterator>::difference_type>(x));
+    return it;
+  }
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/input_iterator.hpp b/src/boost/libs/unordered/test/helpers/input_iterator.hpp
new file mode 100644
index 00000000..7a938a50
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/input_iterator.hpp
@@ -0,0 +1,165 @@
+
+// Copyright 2005-2010 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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_INPUT_ITERATOR_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_INPUT_ITERATOR_HEADER
+
+#include <boost/config.hpp>
+#include <iterator>
+
+namespace test {
+  template <class Iterator> struct proxy
+  {
+    typedef typename Iterator::value_type value_type;
+
+    explicit proxy(value_type const& v) : v_(v) {}
+    proxy(proxy const& x) : v_(x.v_) {}
+    operator value_type const&() const { return v_; }
+
+    value_type v_;
+
+  private:
+    proxy& operator=(proxy const&);
+  };
+
+  template <class Iterator> struct input_iterator_adaptor
+  {
+    typedef typename std::iterator_traits<Iterator>::value_type value_type;
+    typedef typename std::iterator_traits<Iterator>::pointer pointer;
+    typedef proxy<Iterator> reference;
+    typedef std::ptrdiff_t difference_type;
+    typedef std::input_iterator_tag iterator_category;
+
+    input_iterator_adaptor() : base_() {}
+    explicit input_iterator_adaptor(Iterator& it) : base_(&it) {}
+    proxy<Iterator> operator*() const { return proxy<Iterator>(**base_); }
+    value_type* operator->() const { return &**base_; }
+    input_iterator_adaptor& operator++()
+    {
+      ++*base_;
+      return *this;
+    }
+    // input_iterator_adaptor operator++(int) {
+    //}
+    bool operator==(input_iterator_adaptor const& x) const
+    {
+      return *base_ == *x.base_;
+    }
+    bool operator!=(input_iterator_adaptor const& x) const
+    {
+      return *base_ != *x.base_;
+    }
+
+  private:
+    Iterator* base_;
+  };
+
+  template <class Iterator>
+  input_iterator_adaptor<Iterator> input_iterator(Iterator& it)
+  {
+    return input_iterator_adaptor<Iterator>(it);
+  }
+
+  template <class Iterator> struct copy_iterator_adaptor
+  {
+    typedef typename std::iterator_traits<Iterator>::value_type value_type;
+    typedef
+      typename std::iterator_traits<Iterator>::difference_type difference_type;
+    typedef typename std::iterator_traits<Iterator>::iterator_category
+      iterator_category;
+    typedef typename std::iterator_traits<Iterator>::pointer pointer;
+    typedef proxy<Iterator> reference;
+
+    copy_iterator_adaptor() : base_() {}
+    explicit copy_iterator_adaptor(Iterator const& it) : base_(it) {}
+    value_type operator*() const { return *base_; }
+    value_type* operator->() const { return &*base_; }
+    value_type operator[](difference_type d) { return base_[d]; }
+    copy_iterator_adaptor& operator++()
+    {
+      ++base_;
+      return *this;
+    }
+    copy_iterator_adaptor operator++(int)
+    {
+      copy_iterator_adaptor tmp(*this);
+      ++base_;
+      return tmp;
+    }
+    copy_iterator_adaptor& operator--()
+    {
+      --base_;
+      return *this;
+    }
+    copy_iterator_adaptor operator--(int)
+    {
+      copy_iterator_adaptor tmp(*this);
+      --base_;
+      return tmp;
+    }
+    copy_iterator_adaptor operator+=(difference_type x)
+    {
+      base_ += x;
+      return *this;
+    }
+    copy_iterator_adaptor operator-=(difference_type x)
+    {
+      base_ -= x;
+      return *this;
+    }
+    copy_iterator_adaptor operator+(difference_type n)
+    {
+      return copy_iterator_adaptor(base_ + n);
+    }
+    copy_iterator_adaptor operator-(difference_type n)
+    {
+      return copy_iterator_adaptor(base_ - n);
+    }
+    friend copy_iterator_adaptor operator+(
+      difference_type n, copy_iterator_adaptor x)
+    {
+      return x + n;
+    }
+    difference_type operator-(copy_iterator_adaptor const& other)
+    {
+      return base_ - other.base_;
+    }
+    bool operator==(copy_iterator_adaptor const& x) const
+    {
+      return base_ == x.base_;
+    }
+    bool operator!=(copy_iterator_adaptor const& x) const
+    {
+      return base_ != x.base_;
+    }
+    bool operator<(copy_iterator_adaptor const& x) const
+    {
+      return base_ < x.base_;
+    }
+    bool operator>(copy_iterator_adaptor const& x) const
+    {
+      return base_ > x.base_;
+    }
+    bool operator<=(copy_iterator_adaptor const& x) const
+    {
+      return base_ <= x.base_;
+    }
+    bool operator>=(copy_iterator_adaptor const& x) const
+    {
+      return base_ >= x.base_;
+    }
+
+  private:
+    Iterator base_;
+  };
+
+  template <class Iterator>
+  copy_iterator_adaptor<Iterator> copy_iterator(Iterator const& it)
+  {
+    return copy_iterator_adaptor<Iterator>(it);
+  }
+}
+
+#endif
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 00000000..a555da60
--- /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
diff --git a/src/boost/libs/unordered/test/helpers/list.hpp b/src/boost/libs/unordered/test/helpers/list.hpp
new file mode 100644
index 00000000..d39c766e
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/list.hpp
@@ -0,0 +1,327 @@
+
+// Copyright 2008-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)
+
+// Gratuitous single linked list.
+//
+// Sadly some STL implementations aren't up to scratch and I need a simple
+// cross-platform container. So here it is.
+
+#if !defined(UNORDERED_TEST_LIST_HEADER)
+#define UNORDERED_TEST_LIST_HEADER
+
+#include <boost/limits.hpp>
+#include <functional>
+#include <iterator>
+
+namespace test {
+  template <typename It1, typename It2>
+  bool equal(It1 begin, It1 end, It2 compare)
+  {
+    for (; begin != end; ++begin, ++compare)
+      if (*begin != *compare)
+        return false;
+    return true;
+  }
+
+  template <typename It1, typename It2, typename Pred>
+  bool equal(It1 begin, It1 end, It2 compare, Pred predicate)
+  {
+    for (; begin != end; ++begin, ++compare)
+      if (!predicate(*begin, *compare))
+        return false;
+    return true;
+  }
+
+  template <typename T> class list;
+
+  namespace test_detail {
+    template <typename T> class list_node;
+    template <typename T> class list_data;
+    template <typename T> class list_iterator;
+    template <typename T> class list_const_iterator;
+
+    template <typename T> class list_node
+    {
+      list_node(list_node const&);
+      list_node& operator=(list_node const&);
+
+    public:
+      T value_;
+      list_node* next_;
+
+      list_node(T const& v) : value_(v), next_(0) {}
+      list_node(T const& v, list_node* n) : value_(v), next_(n) {}
+    };
+
+    template <typename T> class list_data
+    {
+    public:
+      typedef list_node<T> node;
+      typedef unsigned int size_type;
+
+      node* first_;
+      node** last_ptr_;
+      size_type size_;
+
+      list_data() : first_(0), last_ptr_(&first_), size_(0) {}
+
+      ~list_data()
+      {
+        while (first_) {
+          node* tmp = first_;
+          first_ = first_->next_;
+          delete tmp;
+        }
+      }
+
+    private:
+      list_data(list_data const&);
+      list_data& operator=(list_data const&);
+    };
+
+    template <typename T> class list_iterator
+    {
+      friend class list_const_iterator<T>;
+      friend class test::list<T>;
+      typedef list_node<T> node;
+      typedef list_const_iterator<T> const_iterator;
+
+      node* ptr_;
+
+    public:
+      typedef T value_type;
+      typedef T* pointer;
+      typedef T& reference;
+      typedef int difference_type;
+      typedef std::forward_iterator_tag iterator_category;
+
+      list_iterator() : ptr_(0) {}
+      explicit list_iterator(node* x) : ptr_(x) {}
+
+      T& operator*() const { return ptr_->value_; }
+      T* operator->() const { return &ptr_->value_; }
+      list_iterator& operator++()
+      {
+        ptr_ = ptr_->next_;
+        return *this;
+      }
+      list_iterator operator++(int)
+      {
+        list_iterator tmp = *this;
+        ptr_ = ptr_->next_;
+        return tmp;
+      }
+      bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
+      bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
+    };
+
+    template <typename T> class list_const_iterator
+    {
+      friend class list_iterator<T>;
+      friend class test::list<T>;
+      typedef list_node<T> node;
+      typedef list_iterator<T> iterator;
+      typedef list_const_iterator<T> const_iterator;
+
+      node* ptr_;
+
+    public:
+      typedef T value_type;
+      typedef T const* pointer;
+      typedef T const& reference;
+      typedef int difference_type;
+      typedef std::forward_iterator_tag iterator_category;
+
+      list_const_iterator() : ptr_(0) {}
+      list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
+
+      T const& operator*() const { return ptr_->value_; }
+      T const* operator->() const { return &ptr_->value_; }
+
+      list_const_iterator& operator++()
+      {
+        ptr_ = ptr_->next_;
+        return *this;
+      }
+
+      list_const_iterator operator++(int)
+      {
+        list_const_iterator tmp = *this;
+        ptr_ = ptr_->next_;
+        return tmp;
+      }
+
+      bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
+
+      bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
+    };
+  }
+
+  template <typename T> class list
+  {
+    typedef test::test_detail::list_data<T> data;
+    typedef test::test_detail::list_node<T> node;
+    data data_;
+
+  public:
+    typedef T value_type;
+    typedef value_type& reference;
+    typedef value_type const& const_reference;
+    typedef unsigned int size_type;
+
+    typedef test::test_detail::list_iterator<T> iterator;
+    typedef test::test_detail::list_const_iterator<T> const_iterator;
+
+    list() : data_() {}
+
+    list(list const& other) : data_() { insert(other.begin(), other.end()); }
+
+    template <class InputIterator>
+    list(InputIterator i, InputIterator j) : data_()
+    {
+      insert(i, j);
+    }
+
+    list& operator=(list const& other)
+    {
+      clear();
+      insert(other.begin(), other.end());
+      return *this;
+    }
+
+    iterator begin() { return iterator(data_.first_); }
+    iterator end() { return iterator(); }
+    const_iterator begin() const { return iterator(data_.first_); }
+    const_iterator end() const { return iterator(); }
+    const_iterator cbegin() const { return iterator(data_.first_); }
+    const_iterator cend() const { return iterator(); }
+
+    template <class InputIterator> void insert(InputIterator i, InputIterator j)
+    {
+      for (; i != j; ++i)
+        push_back(*i);
+    }
+
+    void push_front(value_type const& v)
+    {
+      data_.first_ = new node(v, data_.first_);
+      if (!data_.size_)
+        data_.last_ptr_ = &(*data_.last_ptr_)->next_;
+      ++data_.size_;
+    }
+
+    void push_back(value_type const& v)
+    {
+      *data_.last_ptr_ = new node(v);
+      data_.last_ptr_ = &(*data_.last_ptr_)->next_;
+      ++data_.size_;
+    }
+
+    void clear()
+    {
+      while (data_.first_) {
+        node* tmp = data_.first_;
+        data_.first_ = data_.first_->next_;
+        --data_.size_;
+        delete tmp;
+      }
+      data_.last_ptr_ = &data_.first_;
+    }
+
+    void erase(const_iterator i, const_iterator j)
+    {
+      node** ptr = &data_.first_;
+
+      while (*ptr != i.ptr_) {
+        ptr = &(*ptr)->next_;
+      }
+
+      while (*ptr != j.ptr_) {
+        node* to_delete = *ptr;
+        *ptr = (*ptr)->next_;
+        --data_.size_;
+        delete to_delete;
+      }
+
+      if (!*ptr)
+        data_.last_ptr_ = ptr;
+    }
+
+    bool empty() const { return !data_.size_; }
+
+    size_type size() const { return data_.size_; }
+
+    void sort() { sort(std::less<T>()); }
+
+    template <typename Less> void sort(Less less = Less())
+    {
+      if (!empty())
+        merge_sort(
+          &data_.first_, (std::numeric_limits<size_type>::max)(), less);
+    }
+
+    bool operator==(list const& y) const
+    {
+      return size() == y.size() && test::equal(begin(), end(), y.begin());
+    }
+
+    bool operator!=(list const& y) const { return !(*this == y); }
+
+  private:
+    template <typename Less>
+    node** merge_sort(node** l, size_type recurse_limit, Less less)
+    {
+      node** ptr = &(*l)->next_;
+      for (size_type count = 0; count < recurse_limit && *ptr; ++count) {
+        ptr = merge_adjacent_ranges(l, ptr, merge_sort(ptr, count, less), less);
+      }
+      return ptr;
+    }
+
+    template <typename Less>
+    node** merge_adjacent_ranges(
+      node** first, node** second, node** third, Less less)
+    {
+      for (;;) {
+        for (;;) {
+          if (first == second)
+            return third;
+          if (less((*second)->value_, (*first)->value_))
+            break;
+          first = &(*first)->next_;
+        }
+
+        swap_adjacent_ranges(first, second, third);
+        first = &(*first)->next_;
+
+        // Since the two ranges we just swapped, the order is now:
+        // first...third...second
+
+        for (;;) {
+          if (first == third)
+            return second;
+          if (!less((*first)->value_, (*third)->value_))
+            break;
+          first = &(*first)->next_;
+        }
+
+        swap_adjacent_ranges(first, third, second);
+        first = &(*first)->next_;
+      }
+    }
+
+    void swap_adjacent_ranges(node** first, node** second, node** third)
+    {
+      node* tmp = *first;
+      *first = *second;
+      *second = *third;
+      *third = tmp;
+      if (!*second)
+        data_.last_ptr_ = second;
+    }
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/memory.hpp b/src/boost/libs/unordered/test/helpers/memory.hpp
new file mode 100644
index 00000000..22946cc2
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/memory.hpp
@@ -0,0 +1,189 @@
+
+// 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)
+
+#if !defined(BOOST_UNORDERED_TEST_MEMORY_HEADER)
+#define BOOST_UNORDERED_TEST_MEMORY_HEADER
+
+#include "../helpers/test.hpp"
+#include <boost/assert.hpp>
+#include <boost/unordered/detail/implementation.hpp>
+#include <map>
+#include <memory>
+
+namespace test {
+  namespace detail {
+    struct memory_area
+    {
+      void const* start;
+      void const* end;
+
+      memory_area(void const* s, void const* e) : start(s), end(e)
+      {
+        BOOST_ASSERT(start != end);
+      }
+    };
+
+    struct memory_track
+    {
+      explicit memory_track(int tag = -1) : constructed_(0), tag_(tag) {}
+
+      int constructed_;
+      int tag_;
+    };
+
+    // This is a bit dodgy as it defines overlapping
+    // areas as 'equal', so this isn't a total ordering.
+    // But it is for non-overlapping memory regions - which
+    // is what'll be stored.
+    //
+    // All searches will be for areas entirely contained by
+    // a member of the set - so it should find the area that contains
+    // the region that is searched for.
+
+    struct memory_area_compare
+    {
+      bool operator()(memory_area const& x, memory_area const& y) const
+      {
+        return x.end <= y.start;
+      }
+    };
+
+    struct memory_tracker
+    {
+      typedef std::map<memory_area, memory_track, memory_area_compare,
+        std::allocator<std::pair<memory_area const, memory_track> > >
+        allocated_memory_type;
+
+      allocated_memory_type allocated_memory;
+      unsigned int count_allocators;
+      unsigned int count_allocations;
+      unsigned int count_constructions;
+      bool tracking_constructions;
+
+      memory_tracker()
+          : count_allocators(0), count_allocations(0), count_constructions(0),
+            tracking_constructions(true)
+      {
+      }
+
+      ~memory_tracker() { BOOST_TEST(count_allocators == 0); }
+
+      void allocator_ref()
+      {
+        if (count_allocators == 0) {
+          count_allocations = 0;
+          count_constructions = 0;
+          allocated_memory.clear();
+        }
+        ++count_allocators;
+      }
+
+      void allocator_unref()
+      {
+        BOOST_TEST(count_allocators > 0);
+        if (count_allocators > 0) {
+          --count_allocators;
+          if (count_allocators == 0) {
+            bool no_allocations_left = (count_allocations == 0);
+            bool no_constructions_left = (count_constructions == 0);
+            bool allocated_memory_empty = allocated_memory.empty();
+
+            // Clearing the data before the checks terminate the
+            // tests.
+            count_allocations = 0;
+            count_constructions = 0;
+            allocated_memory.clear();
+
+            BOOST_TEST(no_allocations_left);
+            BOOST_TEST(no_constructions_left);
+            BOOST_TEST(allocated_memory_empty);
+          }
+        }
+      }
+
+      void track_allocate(void* ptr, std::size_t n, std::size_t size, int tag)
+      {
+        if (n == 0) {
+          BOOST_ERROR("Allocating 0 length array.");
+        } else {
+          ++count_allocations;
+          allocated_memory.insert(std::pair<memory_area const, memory_track>(
+            memory_area(ptr, (char*)ptr + n * size), memory_track(tag)));
+        }
+      }
+
+      void track_deallocate(void* ptr, std::size_t n, std::size_t size, int tag,
+        bool check_tag_ = true)
+      {
+        allocated_memory_type::iterator pos =
+          allocated_memory.find(memory_area(ptr, (char*)ptr + n * size));
+        if (pos == allocated_memory.end()) {
+          BOOST_ERROR("Deallocating unknown pointer.");
+        } else {
+          BOOST_TEST(pos->first.start == ptr);
+          BOOST_TEST(pos->first.end == (char*)ptr + n * size);
+          if (check_tag_)
+            BOOST_TEST(pos->second.tag_ == tag);
+          allocated_memory.erase(pos);
+        }
+        BOOST_TEST(count_allocations > 0);
+        if (count_allocations > 0)
+          --count_allocations;
+      }
+
+      void track_construct(void* /*ptr*/, std::size_t /*size*/, int /*tag*/)
+      {
+        if (tracking_constructions) {
+          ++count_constructions;
+        }
+      }
+
+      void track_destroy(void* /*ptr*/, std::size_t /*size*/, int /*tag*/)
+      {
+        if (tracking_constructions) {
+          BOOST_TEST(count_constructions > 0);
+          if (count_constructions > 0)
+            --count_constructions;
+        }
+      }
+    };
+  }
+
+  namespace detail {
+    // This won't be a problem as I'm only using a single compile unit
+    // in each test (this is actually required by the minimal test
+    // framework).
+    //
+    // boostinspect:nounnamed
+    namespace {
+      test::detail::memory_tracker tracker;
+    }
+  }
+
+  namespace detail {
+    struct disable_construction_tracking
+    {
+      bool old_value;
+
+      disable_construction_tracking()
+          : old_value(detail::tracker.tracking_constructions)
+      {
+        test::detail::tracker.tracking_constructions = false;
+      }
+
+      ~disable_construction_tracking()
+      {
+        test::detail::tracker.tracking_constructions = old_value;
+      }
+
+    private:
+      disable_construction_tracking(disable_construction_tracking const&);
+      disable_construction_tracking& operator=(
+        disable_construction_tracking const&);
+    };
+  }
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/metafunctions.hpp b/src/boost/libs/unordered/test/helpers/metafunctions.hpp
new file mode 100644
index 00000000..f5f13851
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/metafunctions.hpp
@@ -0,0 +1,30 @@
+
+// Copyright 2005-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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_METAFUNCTIONS_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_METAFUNCTIONS_HEADER
+
+#include <boost/config.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace test {
+  template <class Container>
+  struct is_set : public boost::is_same<typename Container::key_type,
+                    typename Container::value_type>
+  {
+  };
+
+  template <class Container> struct has_unique_keys
+  {
+    static char flip(typename Container::iterator const&);
+    static long flip(std::pair<typename Container::iterator, bool> const&);
+    BOOST_STATIC_CONSTANT(bool,
+      value = sizeof(long) ==
+              sizeof(flip(
+                ((Container*)0)->insert(*(typename Container::value_type*)0))));
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/postfix.hpp b/src/boost/libs/unordered/test/helpers/postfix.hpp
new file mode 100644
index 00000000..ca14ae71
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/postfix.hpp
@@ -0,0 +1,10 @@
+
+// Copyright 2012 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)
+
+// Include this after the boost headers, but before other test headers.
+
+#if defined(__GNUC__)
+#pragma GCC diagnostic ignored "-Wfloat-equal"
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/prefix.hpp b/src/boost/libs/unordered/test/helpers/prefix.hpp
new file mode 100644
index 00000000..fe757025
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/prefix.hpp
@@ -0,0 +1,11 @@
+
+// Copyright 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)
+
+#if defined(_WIN32_WCE)
+// The standard windows mobile headers trigger this warning so I disable it
+// before doing anything else.
+#pragma warning(disable : 4201) // nonstandard extension used :
+                                // nameless struct/union
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/random_values.hpp b/src/boost/libs/unordered/test/helpers/random_values.hpp
new file mode 100644
index 00000000..d139d180
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/random_values.hpp
@@ -0,0 +1,109 @@
+
+// Copyright 2005-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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER
+
+#include "./generators.hpp"
+#include "./list.hpp"
+#include "./metafunctions.hpp"
+#include <algorithm>
+#include <boost/detail/select_type.hpp>
+
+namespace test {
+  template <class X> struct unordered_generator_set
+  {
+    typedef typename X::value_type value_type;
+
+    random_generator type_;
+
+    unordered_generator_set(random_generator type) : type_(type) {}
+
+    template <class T> void fill(T& x, std::size_t len)
+    {
+      value_type* value_ptr = 0;
+      len += x.size();
+
+      for (std::size_t i = 0; i < len; ++i) {
+        value_type value = generate(value_ptr, type_);
+
+        std::size_t count =
+          type_ == generate_collisions ? random_value(5) + 1 : 1;
+
+        for (std::size_t j = 0; j < count; ++j) {
+          x.push_back(value);
+        }
+      }
+    }
+  };
+
+  template <class X> struct unordered_generator_map
+  {
+    typedef typename X::key_type key_type;
+    typedef typename X::mapped_type mapped_type;
+
+    random_generator type_;
+
+    unordered_generator_map(random_generator type) : type_(type) {}
+
+    template <class T> void fill(T& x, std::size_t len)
+    {
+      key_type* key_ptr = 0;
+      mapped_type* mapped_ptr = 0;
+
+      for (std::size_t i = 0; i < len; ++i) {
+        key_type key = generate(key_ptr, type_);
+
+        std::size_t count =
+          type_ == generate_collisions ? random_value(5) + 1 : 1;
+
+        for (std::size_t j = 0; j < count; ++j) {
+          x.push_back(std::pair<key_type const, mapped_type>(
+            key, generate(mapped_ptr, type_)));
+        }
+      }
+    }
+  };
+
+  template <class X>
+  struct unordered_generator_base
+    : public boost::detail::if_true<test::is_set<X>::value>::
+        BOOST_NESTED_TEMPLATE then<test::unordered_generator_set<X>,
+          test::unordered_generator_map<X> >
+  {
+  };
+
+  template <class X>
+  struct unordered_generator : public unordered_generator_base<X>::type
+  {
+    typedef typename unordered_generator_base<X>::type base;
+
+    unordered_generator(random_generator const& type = default_generator)
+        : base(type)
+    {
+    }
+  };
+
+  template <class X>
+  struct random_values : public test::list<typename X::value_type>
+  {
+    random_values() {}
+
+    explicit random_values(std::size_t count,
+      test::random_generator const& generator = test::default_generator)
+    {
+      fill(count, generator);
+    }
+
+    void fill(std::size_t count,
+      test::random_generator const& generator = test::default_generator)
+    {
+      test::unordered_generator<X> gen(generator);
+      gen.fill(*this, count);
+    }
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/strong.hpp b/src/boost/libs/unordered/test/helpers/strong.hpp
new file mode 100644
index 00000000..3c936133
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/strong.hpp
@@ -0,0 +1,42 @@
+
+// Copyright 2005-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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_STRONG_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_STRONG_HEADER
+
+#include "./equivalent.hpp"
+#include "./exception_test.hpp"
+#include "./list.hpp"
+#include <boost/config.hpp>
+#include <iterator>
+
+namespace test {
+  template <class X> class strong
+  {
+    typedef test::list<typename X::value_type> values_type;
+    values_type values_;
+    unsigned int allocations_;
+
+  public:
+    void store(X const& x, unsigned int allocations = 0)
+    {
+      DISABLE_EXCEPTIONS;
+      values_.clear();
+      values_.insert(x.cbegin(), x.cend());
+      allocations_ = allocations;
+    }
+
+    void test(X const& x, unsigned int allocations = 0) const
+    {
+      if (!(x.size() == values_.size() && test::equal(x.cbegin(), x.cend(),
+                                            values_.begin(), test::equivalent)))
+        BOOST_ERROR("Strong exception safety failure.");
+      if (allocations != allocations_)
+        BOOST_ERROR("Strong exception failure: extra allocations.");
+    }
+  };
+}
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/test.hpp b/src/boost/libs/unordered/test/helpers/test.hpp
new file mode 100644
index 00000000..5534f811
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/test.hpp
@@ -0,0 +1,201 @@
+
+// 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)
+
+#if !defined(BOOST_UNORDERED_TEST_TEST_HEADER)
+#define BOOST_UNORDERED_TEST_TEST_HEADER
+
+#include <boost/core/lightweight_test.hpp>
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/stringize.hpp>
+
+#define UNORDERED_AUTO_TEST(x)                                                 \
+  struct BOOST_PP_CAT(x, _type) : public ::test::registered_test_base          \
+  {                                                                            \
+    BOOST_PP_CAT(x, _type)                                                     \
+    () : ::test::registered_test_base(BOOST_PP_STRINGIZE(x))                   \
+    {                                                                          \
+      ::test::get_state().add_test(this);                                      \
+    }                                                                          \
+    void run();                                                                \
+  };                                                                           \
+  BOOST_PP_CAT(x, _type) x;                                                    \
+  void BOOST_PP_CAT(x, _type)::run()
+
+#define RUN_TESTS()                                                            \
+  int main(int, char**)                                                        \
+  {                                                                            \
+    BOOST_UNORDERED_TEST_COMPILER_INFO()                                       \
+    ::test::get_state().run_tests();                                           \
+    return boost::report_errors();                                             \
+  }
+
+#define RUN_TESTS_QUIET()                                                      \
+  int main(int, char**)                                                        \
+  {                                                                            \
+    BOOST_UNORDERED_TEST_COMPILER_INFO()                                       \
+    ::test::get_state().run_tests(true);                                       \
+    return boost::report_errors();                                             \
+  }
+
+#define UNORDERED_SUB_TEST(x)                                                  \
+  for (int UNORDERED_SUB_TEST_VALUE = ::test::get_state().start_sub_test(x);   \
+       UNORDERED_SUB_TEST_VALUE;                                               \
+       UNORDERED_SUB_TEST_VALUE =                                              \
+         ::test::get_state().end_sub_test(x, UNORDERED_SUB_TEST_VALUE))
+
+namespace test {
+
+  struct registered_test_base
+  {
+    registered_test_base* next;
+    char const* name;
+    explicit registered_test_base(char const* n) : name(n) {}
+    virtual void run() = 0;
+    virtual ~registered_test_base() {}
+  };
+
+  struct state
+  {
+    bool is_quiet;
+    registered_test_base* first_test;
+    registered_test_base* last_test;
+
+    state() : is_quiet(false), first_test(0), last_test(0) {}
+
+    void add_test(registered_test_base* test)
+    {
+      if (last_test) {
+        last_test->next = test;
+      } else {
+        first_test = test;
+      }
+      last_test = test;
+    }
+
+    void run_tests(bool quiet = false)
+    {
+      is_quiet = quiet;
+
+      for (registered_test_base* i = first_test; i; i = i->next) {
+        int error_count = boost::detail::test_errors();
+        if (!quiet) {
+          BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Running " << i->name << "\n"
+                                         << std::flush;
+        }
+        i->run();
+        BOOST_LIGHTWEIGHT_TEST_OSTREAM << std::flush;
+        if (quiet && error_count != boost::detail::test_errors()) {
+          BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Error in: " << i->name << "\n"
+                                         << std::flush;
+        }
+      }
+    }
+
+    int start_sub_test(char const* name)
+    {
+      if (!is_quiet) {
+        BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Sub-test: " << name << "\n"
+                                       << std::flush;
+      }
+      // Add one because it's used as a loop condition.
+      return boost::detail::test_errors() + 1;
+    }
+
+    int end_sub_test(char const* name, int value)
+    {
+      if (is_quiet && value != boost::detail::test_errors() + 1) {
+        BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Error in sub-test: " << name << "\n"
+                                       << std::flush;
+      }
+      return 0;
+    }
+  };
+
+  // Get the currnet translation unit's test state.
+  static inline state& get_state()
+  {
+    static state instance;
+    return instance;
+  }
+}
+
+#if defined(__cplusplus)
+#define BOOST_UNORDERED_CPLUSPLUS __cplusplus
+#else
+#define BOOST_UNORDERED_CPLUSPLUS "(not defined)"
+#endif
+
+#define BOOST_UNORDERED_TEST_COMPILER_INFO()                                   \
+  {                                                                            \
+    BOOST_LIGHTWEIGHT_TEST_OSTREAM                                             \
+      << "Compiler: " << BOOST_COMPILER << "\n"                                \
+      << "Library: " << BOOST_STDLIB << "\n"                                   \
+      << "__cplusplus: " << BOOST_UNORDERED_CPLUSPLUS << "\n\n"                \
+      << "BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT: "                          \
+      << BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT << "\n"                      \
+      << "BOOST_UNORDERED_EMPLACE_LIMIT: " << BOOST_UNORDERED_EMPLACE_LIMIT    \
+      << "\n"                                                                  \
+      << "BOOST_UNORDERED_USE_ALLOCATOR_TRAITS: "                              \
+      << BOOST_UNORDERED_USE_ALLOCATOR_TRAITS << "\n"                          \
+      << "BOOST_UNORDERED_CXX11_CONSTRUCTION: "                                \
+      << BOOST_UNORDERED_CXX11_CONSTRUCTION << "\n\n"                          \
+      << std::flush;                                                           \
+  }
+
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/seq/fold_left.hpp>
+#include <boost/preprocessor/seq/for_each_product.hpp>
+#include <boost/preprocessor/seq/seq.hpp>
+#include <boost/preprocessor/seq/to_tuple.hpp>
+
+// Run test with every combination of the parameters (a sequence of sequences)
+#define UNORDERED_TEST(name, parameters)                                       \
+  BOOST_PP_SEQ_FOR_EACH_PRODUCT(UNORDERED_TEST_OP, ((name))((1))parameters)
+
+#define UNORDERED_TEST_REPEAT(name, n, parameters)                             \
+  BOOST_PP_SEQ_FOR_EACH_PRODUCT(UNORDERED_TEST_OP, ((name))((n))parameters)
+
+#define UNORDERED_TEST_OP(r, product)                                          \
+  UNORDERED_TEST_OP2(BOOST_PP_SEQ_ELEM(0, product),                            \
+    BOOST_PP_SEQ_ELEM(1, product),                                             \
+    BOOST_PP_SEQ_TAIL(BOOST_PP_SEQ_TAIL(product)))
+
+#define UNORDERED_TEST_OP2(name, n, params)                                    \
+  UNORDERED_AUTO_TEST (                                                        \
+    BOOST_PP_SEQ_FOLD_LEFT(UNORDERED_TEST_OP_JOIN, name, params)) {            \
+    for (int i = 0; i < n; ++i)                                                \
+      name BOOST_PP_SEQ_TO_TUPLE(params);                                      \
+  }
+
+#define UNORDERED_TEST_OP_JOIN(s, state, elem)                                 \
+  BOOST_PP_CAT(state, BOOST_PP_CAT(_, elem))
+
+#define UNORDERED_MULTI_TEST(name, impl, parameters)                           \
+  UNORDERED_MULTI_TEST_REPEAT(name, impl, 1, parameters)
+
+#define UNORDERED_MULTI_TEST_REPEAT(name, impl, n, parameters)                 \
+  UNORDERED_AUTO_TEST (name) {                                                 \
+    BOOST_PP_SEQ_FOR_EACH_PRODUCT(                                             \
+      UNORDERED_MULTI_TEST_OP, ((impl))((n))parameters)                        \
+  }
+
+#define UNORDERED_MULTI_TEST_OP(r, product)                                    \
+  UNORDERED_MULTI_TEST_OP2(BOOST_PP_SEQ_ELEM(0, product),                      \
+    BOOST_PP_SEQ_ELEM(1, product),                                             \
+    BOOST_PP_SEQ_TAIL(BOOST_PP_SEQ_TAIL(product)))
+
+// Need to wrap UNORDERED_SUB_TEST in a block to avoid an msvc bug.
+// https://support.microsoft.com/en-gb/help/315481/bug-too-many-unnested-loops-incorrectly-causes-a-c1061-compiler-error-in-visual-c
+#define UNORDERED_MULTI_TEST_OP2(name, n, params)                              \
+  {                                                                            \
+    UNORDERED_SUB_TEST(BOOST_PP_STRINGIZE(                                     \
+      BOOST_PP_SEQ_FOLD_LEFT(UNORDERED_TEST_OP_JOIN, name, params)))           \
+    {                                                                          \
+      for (int i = 0; i < n; ++i)                                              \
+        name BOOST_PP_SEQ_TO_TUPLE(params);                                    \
+    }                                                                          \
+  }
+
+#endif
diff --git a/src/boost/libs/unordered/test/helpers/tracker.hpp b/src/boost/libs/unordered/test/helpers/tracker.hpp
new file mode 100644
index 00000000..0f86ba6f
--- /dev/null
+++ b/src/boost/libs/unordered/test/helpers/tracker.hpp
@@ -0,0 +1,138 @@
+
+// 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_TRACKER_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_TRACKER_HEADER
+
+#include "../objects/fwd.hpp"
+#include "./equivalent.hpp"
+#include "./helpers.hpp"
+#include "./list.hpp"
+#include "./metafunctions.hpp"
+#include <algorithm>
+#include <iterator>
+#include <map>
+#include <set>
+
+namespace test {
+  template <typename X> struct equals_to_compare
+  {
+    typedef std::less<typename X::first_argument_type> type;
+  };
+
+  template <> struct equals_to_compare<test::equal_to>
+  {
+    typedef test::less type;
+  };
+
+  template <class X1, class X2> void compare_range(X1 const& x1, X2 const& x2)
+  {
+    typedef test::list<typename X1::value_type> value_list;
+    value_list values1(x1.begin(), x1.end());
+    value_list values2(x2.begin(), x2.end());
+    values1.sort();
+    values2.sort();
+    BOOST_TEST(values1.size() == values2.size() &&
+               test::equal(values1.begin(), values1.end(), values2.begin(),
+                 test::equivalent));
+  }
+
+  template <class X1, class X2, class T>
+  void compare_pairs(X1 const& x1, X2 const& x2, T*)
+  {
+    test::list<T> values1(x1.first, x1.second);
+    test::list<T> values2(x2.first, x2.second);
+    values1.sort();
+    values2.sort();
+    BOOST_TEST(values1.size() == values2.size() &&
+               test::equal(values1.begin(), values1.end(), values2.begin(),
+                 test::equivalent));
+  }
+
+  template <typename X, bool is_set = test::is_set<X>::value,
+    bool has_unique_keys = test::has_unique_keys<X>::value>
+  struct ordered_base;
+
+  template <typename X> struct ordered_base<X, true, true>
+  {
+    typedef std::set<typename X::value_type,
+      typename equals_to_compare<typename X::key_equal>::type>
+      type;
+  };
+
+  template <typename X> struct ordered_base<X, true, false>
+  {
+    typedef std::multiset<typename X::value_type,
+      typename equals_to_compare<typename X::key_equal>::type>
+      type;
+  };
+
+  template <typename X> struct ordered_base<X, false, true>
+  {
+    typedef std::map<typename X::key_type, typename X::mapped_type,
+      typename equals_to_compare<typename X::key_equal>::type>
+      type;
+  };
+
+  template <typename X> struct ordered_base<X, false, false>
+  {
+    typedef std::multimap<typename X::key_type, typename X::mapped_type,
+      typename equals_to_compare<typename X::key_equal>::type>
+      type;
+  };
+
+  template <class X> class ordered : public ordered_base<X>::type
+  {
+    typedef typename ordered_base<X>::type base;
+
+  public:
+    typedef typename base::key_compare key_compare;
+
+    ordered() : base() {}
+
+    explicit ordered(key_compare const& kc) : base(kc) {}
+
+    void compare(X const& x) { compare_range(x, *this); }
+
+    void compare_key(X const& x, typename X::value_type const& val)
+    {
+      compare_pairs(x.equal_range(get_key<X>(val)),
+        this->equal_range(get_key<X>(val)), (typename X::value_type*)0);
+    }
+
+    template <class It> void insert_range(It b, It e)
+    {
+      while (b != e) {
+        this->insert(*b);
+        ++b;
+      }
+    }
+  };
+
+  template <class Equals>
+  typename equals_to_compare<Equals>::type create_compare(Equals const&)
+  {
+    typename equals_to_compare<Equals>::type x;
+    return x;
+  }
+
+  template <class X> ordered<X> create_ordered(X const& container)
+  {
+    return ordered<X>(create_compare(container.key_eq()));
+  }
+
+  template <class X1, class X2>
+  void check_container(X1 const& container, X2 const& values)
+  {
+    ordered<X1> tracker = create_ordered(container);
+    tracker.insert_range(values.begin(), values.end());
+    tracker.compare(container);
+  }
+}
+
+#endif