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: 260514

3 files changed, 57 insertions, 12 deletions

diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index.pass.cpp
index c072248f866..4757c926f68 100644
--- a/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index.pass.cpp
@@ -19,8 +19,11 @@
 #include <string>
 #include <cassert>
 
+#include "test_macros.h"
 #include "MoveOnly.h"
 #include "min_allocator.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
 
 int main()
 {
@@ -44,7 +47,7 @@ int main()
         assert(c.size() == 5);
         assert(c.at(11) == "eleven");
     }
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#if TEST_STD_VER >= 11
     {
         typedef std::unordered_map<MoveOnly, std::string> C;
         typedef std::pair<int, std::string> P;
@@ -65,8 +68,6 @@ int main()
         assert(c.size() == 5);
         assert(c.at(11) == "eleven");
     }
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#if __cplusplus >= 201103L
     {
         typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>,
                             min_allocator<std::pair<const int, std::string>>> C;
@@ -88,7 +89,7 @@ int main()
         assert(c.size() == 5);
         assert(c.at(11) == "eleven");
     }
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+
     {
         typedef std::unordered_map<MoveOnly, std::string, std::hash<MoveOnly>, std::equal_to<MoveOnly>,
                             min_allocator<std::pair<const MoveOnly, std::string>>> C;
@@ -110,6 +111,50 @@ int main()
         assert(c.size() == 5);
         assert(c.at(11) == "eleven");
     }
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    {
+        using Container = TCT::unordered_map<>;
+        using Key = Container::key_type;
+        using MappedType = Container::mapped_type;
+        using ValueTp = Container::value_type;
+        ConstructController* cc = getConstructController();
+        cc->reset();
+        {
+            Container c;
+            const Key k(1);
+            cc->expect<std::piecewise_construct_t const&, std::tuple<Key const&>&&, std::tuple<>&&>();
+            MappedType& mref = c[k];
+            assert(!cc->unchecked());
+            {
+                DisableAllocationGuard g;
+                MappedType& mref2 = c[k];
+                assert(&mref == &mref2);
+            }
+        }
+        {
+            Container c;
+            Key k(1);
+            cc->expect<std::piecewise_construct_t const&, std::tuple<Key const&>&&, std::tuple<>&&>();
+            MappedType& mref = c[k];
+            assert(!cc->unchecked());
+            {
+                DisableAllocationGuard g;
+                MappedType& mref2 = c[k];
+                assert(&mref == &mref2);
+            }
+        }
+        {
+            Container c;
+            Key k(1);
+            cc->expect<std::piecewise_construct_t const&, std::tuple<Key &&>&&, std::tuple<>&&>();
+            MappedType& mref = c[std::move(k)];
+            assert(!cc->unchecked());
+            {
+                Key k2(1);
+                DisableAllocationGuard g;
+                MappedType& mref2 = c[std::move(k2)];
+                assert(&mref == &mref2);
+            }
+        }
+    }
 #endif
 }
diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index_tuple.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index_tuple.pass.cpp
index c319b5c30b2..f2c694e86f7 100644
--- a/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index_tuple.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.elem/index_tuple.pass.cpp
@@ -7,6 +7,8 @@
 //
 //===----------------------------------------------------------------------===//
 
+// UNSUPPORTED: c++98, c++03
+
 // <unordered_map>
 
 // template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
@@ -18,9 +20,6 @@
 // http://llvm.org/bugs/show_bug.cgi?id=16542
 
 #include <unordered_map>
-
-#ifndef _LIBCPP_HAS_NO_VARIADICS
-
 #include <tuple>
 
 using namespace std;
@@ -30,12 +29,8 @@ struct my_hash
     size_t operator()(const tuple<int,int>&) const {return 0;}
 };
 
-#endif
-
 int main()
 {
-#ifndef _LIBCPP_HAS_NO_VARIADICS
     unordered_map<tuple<int,int>, size_t, my_hash> m;
     m[make_tuple(2,3)]=7;
-#endif
 }
diff --git a/libcxx/test/support/container_test_types.h b/libcxx/test/support/container_test_types.h
index 7f6544e9ced..54657eb170d 100644
--- a/libcxx/test/support/container_test_types.h
+++ b/libcxx/test/support/container_test_types.h
@@ -393,6 +393,11 @@ struct CopyInsertable {
     }
   }
 
+  CopyInsertable() : data(0), copied_once(false), constructed_under_allocator(true)
+  {
+    assert(getConstructController()->isInAllocatorConstruct());
+  }
+
   CopyInsertable(CopyInsertable const& other) : data(other.data),
                                                 copied_once(true),
                                                 constructed_under_allocator(true) {