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

1 files changed, 21 insertions, 30 deletions

diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map
index 7e84f74d7e6..372868a0df5 100644
--- a/libcxx/include/unordered_map
+++ b/libcxx/include/unordered_map
@@ -369,6 +369,7 @@ template <class Key, class T, class Hash, class Pred, class Alloc>
 #include <__hash_table>
 #include <functional>
 #include <stdexcept>
+#include <tuple>
 
 #include <__debug>
 
@@ -1128,7 +1129,7 @@ public:
         {return __table_.__equal_range_unique(__k);}
 
     mapped_type& operator[](const key_type& __k);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
     mapped_type& operator[](key_type&& __k);
 #endif
 
@@ -1184,10 +1185,10 @@ public:
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 private:
-#ifndef _LIBCPP_CXX03_LANG
-    __node_holder __construct_node_with_key(key_type&& __k);
-#endif  // _LIBCPP_CXX03_LANG
+
+#ifdef _LIBCPP_CXX03_LANG
     __node_holder __construct_node_with_key(const key_type& __k);
+#endif
 };
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
@@ -1394,23 +1395,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
 
 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
-#ifndef _LIBCPP_CXX03_LANG
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
-{
-    __node_allocator& __na = __table_.__node_alloc();
-    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
-    __h.get_deleter().__first_constructed = true;
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
-    __h.get_deleter().__second_constructed = true;
-    return __h;
-}
-
-#endif
-
+#ifdef _LIBCPP_CXX03_LANG
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
@@ -1423,6 +1408,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const
     __h.get_deleter().__second_constructed = true;
     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 }
+#endif
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
@@ -1435,6 +1421,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
         __table_.__insert_unique(*__first);
 }
 
+#ifdef _LIBCPP_CXX03_LANG
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp&
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
@@ -1447,23 +1434,27 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
     __h.release();
     return __r.first->second;
 }
+#else
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
+_Tp&
+unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
+{
+    return __table_.__emplace_unique_key_args(__k,
+        std::piecewise_construct, std::forward_as_tuple(__k),
+                                  std::forward_as_tuple()).first->__cc.second;
+}
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp&
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
 {
-    iterator __i = find(__k);
-    if (__i != end())
-        return __i->second;
-    __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
-    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
-    __h.release();
-    return __r.first->second;
+    return __table_.__emplace_unique_key_args(__k,
+        std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
+                                  std::forward_as_tuple()).first->__cc.second;
 }
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // !_LIBCPP_CXX03_MODE
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp&