Teach __hash_table how to handle unordered_map's __hash_value_type.

This patch is fairly large and contains a number of changes. The main change
is teaching '__hash_table' how to handle '__hash_value_type'. Unfortunately
this change is a rampant layering violation, but it's required to make
unordered_map conforming without re-writing all of __hash_table.
After this change 'unordered_map' can delegate to '__hash_table' in almost all cases.

The major changes found in this patch are:

  * Teach __hash_table to differentiate between the true container value type
    and the node value type by introducing the "__container_value_type" and
    "__node_value_type" typedefs. In the case of unordered_map '__container_value_type'
    is 'pair<const Key, Value>' and '__node_value_type' is '__hash_value_type'.
    
  * Switch almost all overloads in '__hash_table' previously taking 'value_type'
    (AKA '__node_value_type) to take  '__container_value_type' instead. Previously
    'pair<K, V>' would be implicitly converted to '__hash_value_type<K, V>' because
    of the function signature.
    
  * Add '__get_key', '__get_value', '__get_ptr', and '__move' static functions to
    '__key_value_types'. These functions allow '__hash_table' to unwrap
    '__node_value_type' objects into '__container_value_type' and its sub-parts.

  * Pass  '__hash_value_type::__value_'  to 'a.construct(p, ...)' instead of
    '__hash_value_type' itself. The C++14 standard requires that 'a.construct()'
    and 'a.destroy()' are only ever instantiated for the containers value type.

  * Remove '__hash_value_type's constructors and destructors. We should never
    construct an instance of this type.
    (TODO this is UB but we already do it in plenty of places).
  
  * Add a generic "try-emplace" function to '__hash_table' called
    '__emplace_unique_key_args(Key const&, Args...)'.

  
The following changes were done as cleanup:

  * Introduce the '_LIBCPP_CXX03_LANG' macro to be used in place of
    '_LIBCPP_HAS_NO_VARIADICS' or '_LIBCPP_HAS_NO_RVALUE_REFERENCE'.
    
  * Cleanup C++11 only overloads that assume an incomplete C++11 implementation.
    For example this patch removes the __construct_node overloads that do
    manual pack expansion.
    
  * Forward 'unordered_map::emplace' to '__hash_table' and remove dead code
    resulting from the change. This includes almost all
    'unordered_map::__construct_node' overloads.


The following changes are planed for future revisions:

  * Fix LWG issue #2469 by delegating 'unordered_map::operator[]' to use
    '__emplace_unique_key_args'.
    
  * Rewrite 'unordered_map::try_emplace' in terms of '__emplace_unique_key_args'.
  
  * Optimize '__emplace_unique' to call '__emplace_unique_key_args' when possible.
    This prevent unneeded allocations when inserting duplicate entries.


The additional follow up work needed after this patch:

  * Respect the lifetime rules for '__hash_value_type' by actually constructing it.
  * Make '__insert_multi' act similar to '__insert_unique' for objects of type
    'T&' and 'T const &&' with 'T = __container_value_type'.
  
  

llvm-svn: 260513

5 files changed, 1022 insertions, 0 deletions

diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp
new file mode 100644
index 00000000000..e889ce33480
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,143 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_map>
+
+// class unordered_map
+
+// insert(...);
+
+// UNSUPPORTED: c++98, c++03
+
+
+#include <unordered_map>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  typedef std::pair<typename C::iterator, bool> R;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::insert(const value_type&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42, 1);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&&>();
+    assert(c.insert(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42, 1);
+      assert(c.insert(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+    Container c;
+    std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
+    cc->expect<ValueTp const&>(2);
+    c.insert(il);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(il);
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+    Container c;
+    const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+    cc->expect<ValueTp&&>(3);
+    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+             std::move_iterator<ValueTp*>(std::end(ValueList)));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp ValueList2[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+      c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
+               std::move_iterator<ValueTp*>(std::end(ValueList2)));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+}
+
+
+int main()
+{
+  testContainerInsert<TCT::unordered_map<> >();
+}
diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_allocator_requirements.pass.cpp
new file mode 100644
index 00000000000..0926e8057ca
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,108 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// insert(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <unordered_map>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::insert(const value_type&)");
+    Container c;
+    const ValueTp v(42, 1);
+    cc->expect<const ValueTp&>();
+    c.insert(v);
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(value_type&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&>();
+    c.insert(v);
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(value_type&&)");
+    Container c;
+    ValueTp v(42, 1);
+    cc->expect<ValueTp&&>();
+    c.insert(std::move(v));
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+    Container c;
+    std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
+    cc->expect<ValueTp const&>(2);
+    c.insert(il);
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+    Container c;
+    const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+    cc->expect<ValueTp&&>(3);
+    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+             std::move_iterator<ValueTp*>(std::end(ValueList)));
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+    cc->expect<ValueTp&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+  }
+}
+
+
+int main()
+{
+  testContainerInsert<TCT::unordered_multimap<> >();
+}
diff --git a/libcxx/test/std/containers/unord/unord.multiset/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/insert_allocator_requirements.pass.cpp
new file mode 100644
index 00000000000..ae8ce055910
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multiset/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,107 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// insert(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <unordered_set>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::insert(const value_type&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    c.insert(v);
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(value_type&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    c.insert(v);
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(value_type&&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&&>();
+    c.insert(std::move(v));
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+    Container c;
+    std::initializer_list<ValueTp> il = { ValueTp(1), ValueTp(2) };
+    cc->expect<ValueTp const&>(2);
+    c.insert(il);
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+    Container c;
+    const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+    cc->expect<ValueTp&&>(3);
+    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+             std::move_iterator<ValueTp*>(std::end(ValueList)));
+    assert(!cc->unchecked());
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+    cc->expect<ValueTp&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+  }
+}
+
+int main()
+{
+  testContainerInsert<TCT::unordered_multiset<> >();
+}
diff --git a/libcxx/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp
new file mode 100644
index 00000000000..f5a30c237b9
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,142 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+
+// class unordered_set
+
+// insert(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <unordered_set>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+  std::cout << "In " << __FILE__ << ":" << line << ":\n    " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+  typedef typename Container::value_type ValueTp;
+  typedef Container C;
+  typedef std::pair<typename C::iterator, bool> R;
+  ConstructController* cc = getConstructController();
+  cc->reset();
+  {
+    PRINT("Testing C::insert(const value_type&)");
+    Container c;
+    const ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      const ValueTp v2(42);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<const ValueTp&>();
+    assert(c.insert(v).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      assert(c.insert(v2).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(value_type&&)");
+    Container c;
+    ValueTp v(42);
+    cc->expect<ValueTp&&>();
+    assert(c.insert(std::move(v)).second);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp v2(42);
+      assert(c.insert(std::move(v2)).second == false);
+    }
+  }
+  {
+    PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+    Container c;
+    std::initializer_list<ValueTp> il = { ValueTp(1), ValueTp(2) };
+    cc->expect<ValueTp const&>(2);
+    c.insert(il);
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(il);
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+    Container c;
+    const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+    cc->expect<ValueTp&&>(3);
+    c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+             std::move_iterator<ValueTp*>(std::end(ValueList)));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      ValueTp ValueList2[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+      c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
+               std::move_iterator<ValueTp*>(std::end(ValueList2)));
+    }
+  }
+  {
+    PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+    Container c;
+    ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+    cc->expect<ValueTp const&>(3);
+    c.insert(std::begin(ValueList), std::end(ValueList));
+    assert(!cc->unchecked());
+    {
+      DisableAllocationGuard g;
+      c.insert(std::begin(ValueList), std::end(ValueList));
+    }
+  }
+}
+
+
+int main()
+{
+  testContainerInsert<TCT::unordered_set<> >();
+}
diff --git a/libcxx/test/support/container_test_types.h b/libcxx/test/support/container_test_types.h
new file mode 100644
index 00000000000..7f6544e9ced
--- /dev/null
+++ b/libcxx/test/support/container_test_types.h
@@ -0,0 +1,522 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SUPPORT_CONTAINER_TEST_TYPES_H
+#define SUPPORT_CONTAINER_TEST_TYPES_H
+
+// container_test_types.h - A set of types used for testing STL containers.
+// The types container within this header are used to test the requirements in
+// [container.requirements.general]. The header is made up of 3 main components:
+//
+// * test-types: 'CopyInsertable', 'MoveInsertable' and 'EmplaceConstructible' -
+//    These test types are used to test the container requirements of the same
+//    name. These test types use the global 'AllocatorConstructController' to
+//    assert that they are only constructed by the containers allocator.
+//
+// * test-allocator: 'ContainerTestAllocator' - This test allocator is used to
+//    test the portions of [container.requirements.general] that pertain to the
+//    containers allocator. The three primary jobs of the test allocator are:
+//      1. Enforce that 'a.construct(...)' and 'a.destroy(...)' are only ever
+//         instantiated for 'Container::value_type'.
+//      2. Provide a mechanism of checking calls to 'a.construct(Args...)'.
+//         Including controlling when and with what types 'a.construct(...)'
+//         may be called with.
+//      3. Support the test types internals by controlling the global
+//        'AllocatorConstructController' object.
+//
+// * 'AllocatorConstructController' - This type defines an interface for testing
+//   the construction of types using an allocator. This type is used to communicate
+//   between the test author, the containers allocator, and the types
+//   being constructed by the container.
+//   The controllers primary functions are:
+//     1. Allow calls to 'a.construct(p, args...)' to be checked by a test.
+//        The test uses 'cc->expect<Args...>()' to specify that the allocator
+//        should expect one call to 'a.construct' with the specified argument
+//        types.
+//     2. Controlling the value of 'cc->isInAllocatorConstruct()' within the
+//        'construct' method. The test-types use this value to assert that
+//         they are being constructed by the allocator.
+//
+//   'AllocatorConstructController' enforces the Singleton pattern since the
+//    test-types, test-allocator and test need to share the same controller
+//    object. A pointer to the global controller is returned by
+//   'getConstructController()'.
+//
+//----------------------------------------------------------------------------
+/*
+ * Usage: The following example checks that 'unordered_map::emplace(Args&&...)'
+ *        with 'Args = [CopyInsertable<1> const&, CopyInsertible<2>&&]'
+ *        calls 'alloc.construct(value_type*, Args&&...)' with the same types.
+ *
+ * // Typedefs for container
+ * using Key = CopyInsertible<1>;
+ * using Value = CopyInsertible<2>;
+ * using ValueTp = std::pair<const Key, Value>;
+ * using Alloc = ContainerTestAllocator<ValueTp, ValueTp>;
+ * using Map = std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>, Alloc>;
+ *
+ * // Get the global controller, reset it, and construct an allocator with
+ * // the controller.
+ * ConstructController* cc = getConstructController();
+ * cc->reset();
+ *
+ * // Create a Map and a Key and Value to insert. Note that the test-allocator
+ * // does not need to be given 'cc'.
+ * Map m;
+ * const Key k(1);
+ * Value v(1);
+ *
+ * // Tell the controller to expect a construction from the specified types.
+ * cc->expect<Key const&, Value&&>();
+ *
+ * // Emplace the objects into the container. 'Alloc.construct(p, UArgs...)'
+ * // will assert 'cc->check<UArgs&&>()' is true which will consume
+ * // the call to 'cc->expect<...>()'.
+ * m.emplace(k, std::move(v));
+ *
+ * // Assert that the "expect" was consumed by a matching "check" call within
+ * // Alloc.
+ * assert(!cc->unexpected());
+ *
+ */
+
+#include <functional>
+#include <unordered_map>
+#include <unordered_set>
+#include <cassert>
+
+#include "test_macros.h"
+
+namespace detail {
+// TypeID - Represent a unique identifier for a type. TypeID allows equality
+// comparisons between different types.
+struct TypeID {
+  friend bool operator==(TypeID const& LHS, TypeID const& RHS)
+  {return LHS.m_id == RHS.m_id; }
+  friend bool operator!=(TypeID const& LHS, TypeID const& RHS)
+  {return LHS.m_id != RHS.m_id; }
+private:
+  explicit TEST_CONSTEXPR TypeID(const int* xid) : m_id(xid) {}
+  const int* const m_id;
+  template <class T> friend class TypeInfo;
+};
+
+// TypeInfo - Represent information for the specified type 'T', including a
+// unique TypeID.
+template <class T>
+class TypeInfo {
+public:
+  typedef T value_type;
+  typedef TypeID ID;
+  static  ID const& GetID() { static ID id(&dummy_addr); return id; }
+
+private:
+  static const int dummy_addr;
+};
+
+template <class L, class R>
+inline bool operator==(TypeInfo<L> const&, TypeInfo<R> const&)
+{ return std::is_same<L, R>::value; }
+
+template <class L, class R>
+inline bool operator!=(TypeInfo<L> const& lhs, TypeInfo<R> const& rhs)
+{ return !(lhs == rhs); }
+
+template <class T>
+const int TypeInfo<T>::dummy_addr = 42;
+
+// makeTypeID - Return the TypeID for the specified type 'T'.
+template <class T>
+inline TEST_CONSTEXPR TypeID const& makeTypeID() { return TypeInfo<T>::GetID(); }
+
+#if TEST_STD_VER >= 11
+template <class ...Args>
+struct ArgumentListID {};
+
+// makeArgumentID - Create and return a unique identifier for a given set
+// of arguments.
+template <class ...Args>
+inline TEST_CONSTEXPR TypeID const& makeArgumentID() {
+  return makeTypeID<ArgumentListID<Args...>>();
+}
+#else
+template <class A1 = void, class A2 = void, class A3 = void>
+struct ArgumentListID {};
+
+template <class A1>
+inline TypeID const& makeArgumentID() {
+  return makeTypeID<ArgumentListID<A1> >();
+}
+
+template <class A1, class A2>
+inline TypeID const& makeArgumentID() {
+  return makeTypeID<ArgumentListID<A1, A2> >();
+}
+
+template <class A1, class A2, class A3>
+inline TypeID const& makeArgumentID() {
+  return makeTypeID<ArgumentListID<A1, A2, A3> >();
+}
+#endif
+
+} // namespace detail
+
+//===----------------------------------------------------------------------===//
+//                        AllocatorConstructController
+//===----------------------------------------------------------------------===//
+
+struct AllocatorConstructController {
+  const detail::TypeID* m_expected_args;
+  bool m_allow_constructions;
+  bool m_allow_unchecked;
+  int m_expected_count;
+
+  // Check for and consume an expected construction added by 'expect'.
+  // Return true if the construction was expected and false otherwise.
+  // This should only be called by 'Allocator.construct'.
+  bool check(detail::TypeID const& tid) {
+    if (!m_expected_args)
+      assert(m_allow_unchecked);
+    bool res = *m_expected_args == tid;
+    if (m_expected_count == -1 || --m_expected_count == -1)
+      m_expected_args = nullptr;
+    return res;
+  }
+
+  // Return true iff there is an unchecked construction expression.
+  bool unchecked() {
+    return m_expected_args != nullptr;
+  }
+
+  // Expect a call to Allocator::construct with Args that match 'tid'.
+  void expect(detail::TypeID const& tid) {
+    assert(!unchecked());
+    m_expected_args = &tid;
+  }
+
+#if TEST_STD_VER >= 11
+  template <class ...Args>
+  void expect(int times = 1) {
+    assert(!unchecked());
+    assert(times > 0);
+    m_expected_count = times - 1;
+    m_expected_args = &detail::makeArgumentID<Args...>();
+  }
+  template <class ...Args>
+  bool check() {
+    return check(detail::makeArgumentID<Args...>());
+  }
+#else
+  template <class A1>
+  void expect(int times = 1) {
+    assert(!unchecked());
+    assert(times > 0);
+    m_expected_count = times - 1;
+    m_expected_args = &detail::makeArgumentID<A1>();
+  }
+  template <class A1>
+  bool check() {
+    return check(detail::makeArgumentID<A1>());
+  }
+#endif
+
+  // Return true iff the program is currently within a call to "Allocator::construct"
+  bool isInAllocatorConstruct() const {
+    return m_allow_constructions;
+  }
+
+  void inAllocatorConstruct(bool value = true) {
+    m_allow_constructions = value;
+  }
+
+  void allowUnchecked(bool value = true) {
+    m_allow_unchecked = value;
+  }
+
+  void reset() {
+    m_allow_constructions = false;
+    m_expected_args = nullptr;
+    m_allow_unchecked = false;
+    m_expected_count = -1;
+  }
+
+private:
+  friend AllocatorConstructController* getConstructController();
+  AllocatorConstructController()  { reset(); }
+  AllocatorConstructController(AllocatorConstructController const&);
+  AllocatorConstructController& operator=(AllocatorConstructController const&);
+};
+
+typedef AllocatorConstructController ConstructController;
+
+// getConstructController - Return the global allocator construction controller.
+inline ConstructController* getConstructController() {
+  static ConstructController c;
+  return &c;
+}
+
+//===----------------------------------------------------------------------===//
+//                       ContainerTestAllocator
+//===----------------------------------------------------------------------===//
+
+// ContainerTestAllocator - A STL allocator type that only allows 'construct'
+// and 'destroy' to be called for 'AllowConstructT' types. ContainerTestAllocator
+// uses the 'AllocatorConstructionController' interface.
+template <class T, class AllowConstructT>
+class ContainerTestAllocator
+{
+  struct InAllocatorConstructGuard {
+    ConstructController *m_cc;
+    bool m_old;
+    InAllocatorConstructGuard(ConstructController* cc) : m_cc(cc) {
+      if (m_cc) {
+        m_old = m_cc->isInAllocatorConstruct();
+        m_cc->inAllocatorConstruct(true);
+      }
+    }
+    ~InAllocatorConstructGuard() {
+      if (m_cc) m_cc->inAllocatorConstruct(m_old);
+    }
+  private:
+    InAllocatorConstructGuard(InAllocatorConstructGuard const&);
+    InAllocatorConstructGuard& operator=(InAllocatorConstructGuard const&);
+  };
+
+public:
+    typedef T value_type;
+
+    int construct_called;
+    int destroy_called;
+    ConstructController* controller;
+
+    ContainerTestAllocator() TEST_NOEXCEPT
+        : controller(getConstructController()) {}
+
+    explicit ContainerTestAllocator(ConstructController* c)
+       : controller(c)
+    {}
+
+    template <class U>
+    ContainerTestAllocator(ContainerTestAllocator<U, AllowConstructT> other) TEST_NOEXCEPT
+      : controller(other.controller)
+    {}
+
+    T* allocate(std::size_t n)
+    {
+        return static_cast<T*>(::operator new(n*sizeof(T)));
+    }
+
+    void deallocate(T* p, std::size_t)
+    {
+        return ::operator delete(static_cast<void*>(p));
+    }
+#if TEST_STD_VER >= 11
+    template <class Up, class ...Args>
+    void construct(Up* p, Args&&... args) {
+      static_assert((std::is_same<Up, AllowConstructT>::value),
+                    "Only allowed to construct Up");
+      assert(controller->check<Args&&...>());
+      {
+        InAllocatorConstructGuard g(controller);
+        ::new ((void*)p) Up(std::forward<Args>(args)...);
+      }
+    }
+#else
+    template <class Up, class A0>
+    void construct(Up* p, A0& a0) {
+      static_assert((std::is_same<Up, AllowConstructT>::value),
+                    "Only allowed to construct Up");
+      assert(controller->check<A0&>());
+      {
+        InAllocatorConstructGuard g(controller);
+        ::new ((void*)p) Up(a0);
+      }
+    }
+    template <class Up, class A0, class A1>
+    void construct(Up* p, A0& a0, A1& a1) {
+      static_assert((std::is_same<Up, AllowConstructT>::value),
+                    "Only allowed to construct Up");
+      assert((controller->check<A0&, A1&>()));
+      {
+        InAllocatorConstructGuard g(controller);
+        ::new ((void*)p) Up(a0, a1);
+      }
+    }
+#endif
+
+    template <class Up>
+    void destroy(Up* p) {
+      static_assert((std::is_same<Up, AllowConstructT>::value),
+                    "Only allowed to destroy Up");
+      {
+        InAllocatorConstructGuard g(controller);
+        p->~Up();
+      }
+    }
+
+    friend bool operator==(ContainerTestAllocator, ContainerTestAllocator) {return true;}
+    friend bool operator!=(ContainerTestAllocator x, ContainerTestAllocator y) {return !(x == y);}
+};
+
+#if TEST_STD_VER >= 11
+namespace test_detail {
+typedef ContainerTestAllocator<int, int> A1;
+typedef std::allocator_traits<A1> A1T;
+typedef ContainerTestAllocator<float, int> A2;
+typedef std::allocator_traits<A2> A2T;
+
+static_assert(std::is_same<A1T::rebind_traits<float>, A2T>::value, "");
+static_assert(std::is_same<A2T::rebind_traits<int>, A1T>::value, "");
+} // end namespace test_detail
+#endif
+
+//===----------------------------------------------------------------------===//
+//  'CopyInsertable', 'MoveInsertable' and 'EmplaceConstructible' test types
+//===----------------------------------------------------------------------===//
+
+template <int Dummy = 0>
+struct CopyInsertable {
+  int data;
+  mutable bool copied_once;
+  bool constructed_under_allocator;
+
+  explicit CopyInsertable(int val) : data(val), copied_once(false),
+                                     constructed_under_allocator(false) {
+    if (getConstructController()->isInAllocatorConstruct()) {
+      copied_once = true;
+      constructed_under_allocator = true;
+    }
+  }
+
+  CopyInsertable(CopyInsertable const& other) : data(other.data),
+                                                copied_once(true),
+                                                constructed_under_allocator(true) {
+    assert(getConstructController()->isInAllocatorConstruct());
+    assert(other.copied_once == false);
+    other.copied_once = true;
+  }
+
+  CopyInsertable(CopyInsertable& other) : data(other.data), copied_once(true),
+                                          constructed_under_allocator(true) {
+    assert(getConstructController()->isInAllocatorConstruct());
+    assert(other.copied_once == false);
+    other.copied_once = true;
+  }
+
+#if TEST_STD_VER >= 11
+  CopyInsertable(CopyInsertable&& other) : CopyInsertable(other) {}
+
+  // Forgive pair for not downcasting this to an lvalue it its constructors.
+  CopyInsertable(CopyInsertable const && other) : CopyInsertable(other) {}
+
+
+  template <class ...Args>
+  CopyInsertable(Args&&... args) {
+    assert(false);
+  }
+#else
+  template <class Arg>
+  CopyInsertable(Arg&) {
+    assert(false);
+  }
+#endif
+
+  ~CopyInsertable() {
+    assert(constructed_under_allocator == getConstructController()->isInAllocatorConstruct());
+  }
+
+  void reset(int value) {
+    data = value;
+    copied_once = false;
+    constructed_under_allocator = false;
+  }
+};
+
+template <int ID>
+bool operator==(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
+  return L.data == R.data;
+}
+
+
+template <int ID>
+bool operator!=(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
+  return L.data != R.data;
+}
+
+template <int ID>
+bool operator <(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
+  return L.data < R.data;
+}
+
+namespace std {
+template <int ID>
+struct hash< ::CopyInsertable<ID> > {
+  typedef ::CopyInsertable<ID> argument_type;
+  typedef size_t result_type;
+
+  size_t operator()(argument_type const& arg) const {
+    return arg.data;
+  }
+};
+} // namespace std
+
+// TCT - Test container type
+namespace TCT {
+
+template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2> >
+struct unordered_map_type {
+    typedef std::pair<const Key, Value> ValueTp;
+    typedef
+      std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>,
+                              ContainerTestAllocator<ValueTp, ValueTp> >
+      type;
+};
+
+template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>>
+struct unordered_multimap_type {
+    typedef std::pair<const Key, Value> ValueTp;
+    typedef
+      std::unordered_multimap<Key, Value, std::hash<Key>, std::equal_to<Key>,
+                                   ContainerTestAllocator<ValueTp, ValueTp> >
+      type;
+};
+
+template <class Value = CopyInsertable<1> >
+struct unordered_set_type {
+  typedef
+    std::unordered_set<Value, std::hash<Value>, std::equal_to<Value>,
+                               ContainerTestAllocator<Value, Value> >
+    type;
+};
+
+template <class Value = CopyInsertable<1> >
+struct unordered_multiset_type {
+  typedef
+    std::unordered_multiset<Value, std::hash<Value>, std::equal_to<Value>,
+                                    ContainerTestAllocator<Value, Value> >
+    type;
+};
+
+#if TEST_STD_VER >= 11
+template <class ...Args>
+using unordered_map = typename unordered_map_type<Args...>::type;
+
+template <class ...Args>
+using unordered_multimap = typename unordered_multimap_type<Args...>::type;
+
+template <class ...Args>
+using unordered_set = typename unordered_set_type<Args...>::type;
+
+template <class ...Args>
+using unordered_multiset = typename unordered_multiset_type<Args...>::type;
+#endif
+
+} // end namespace TCT
+
+
+#endif // SUPPORT_CONTAINER_TEST_TYPES_H