Fix LWG issue 2469 - Use piecewise construction in map::operator[].

map's allocator may only be used to construct objects of 'value_type',
or in this case 'pair<const Key, Value>'. In order to respect this requirement
in operator[], which requires default constructing the 'mapped_type', we have
to use pair's piecewise constructor with '(tuple<Kep>, tuple<>)'.

Unfortunately we still need to provide a fallback implementation for C++03
since we don't have <tuple>. Even worse this fallback is the last remaining
user of '__hash_map_node_destructor' and '__construct_node_with_key'.

This patch also switches try_emplace over to __tree.__emplace_unique_key_args.

llvm-svn: 264989

3 files changed, 108 insertions, 71 deletions

diff --git a/libcxx/include/map b/libcxx/include/map
index a459146021c..29d068a501c 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -1026,7 +1026,7 @@ public:
     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
 
     mapped_type& operator[](const key_type& __k);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
     mapped_type& operator[](key_type&& __k);
 #endif
 
@@ -1105,62 +1105,45 @@ public:
 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
 #if _LIBCPP_STD_VER > 14
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
         pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-            return _VSTD::make_pair(__p, false);
-        else
-            return _VSTD::make_pair(
-                      emplace_hint(__p, 
-                        _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 
-                        _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
-                      true);
+        return __tree_.__emplace_unique_key_args(__k,
+            _VSTD::piecewise_construct,
+            _VSTD::forward_as_tuple(__k),
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
     }
 
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
         pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-            return _VSTD::make_pair(__p, false);
-        else
-            return _VSTD::make_pair(
-                      emplace_hint(__p, 
-                        _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 
-                        _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
-                      true);
+        return __tree_.__emplace_unique_key_args(__k,
+            _VSTD::piecewise_construct,
+            _VSTD::forward_as_tuple(_VSTD::move(__k)),
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
     }
 
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-            return __p;
-        else
-            return emplace_hint(__p, 
-                      _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 
-                      _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+        return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
+            _VSTD::piecewise_construct,
+            _VSTD::forward_as_tuple(__k),
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
     }
 
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-            return __p;
-        else
-            return emplace_hint(__p, 
-                      _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 
-                      _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+        return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
+            _VSTD::piecewise_construct,
+            _VSTD::forward_as_tuple(_VSTD::move(__k)),
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
     }
 
     template <class _Vp>
@@ -1175,7 +1158,7 @@ public:
         }
         return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
     }
-        
+
     template <class _Vp>
         _LIBCPP_INLINE_VISIBILITY
         pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
@@ -1214,8 +1197,7 @@ public:
         }
         return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
      }
-#endif
-#endif
+
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
@@ -1321,11 +1303,9 @@ private:
     typedef __map_node_destructor<__node_allocator> _Dp;
     typedef unique_ptr<__node, _Dp> __node_holder;
 
-#ifndef _LIBCPP_CXX03_LANG
-    __node_holder __construct_node_with_key(key_type&& __k);
-#endif
-
+#ifdef _LIBCPP_CXX03_LANG
     __node_holder __construct_node_with_key(const key_type& __k);
+#endif
 
     __node_base_pointer const&
     __find_equal_key(__node_base_pointer& __parent, const key_type& __k) const;
@@ -1400,21 +1380,10 @@ map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
     }
 }
 
+#endif  // !_LIBCPP_CXX03_LANG
 
-template <class _Key, class _Tp, class _Compare, class _Allocator>
-typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
-map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
-{
-    __node_allocator& __na = __tree_.__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  // !_LIBCPP_CXX03_LANG
+#ifdef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
@@ -1445,25 +1414,29 @@ map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
     return __r->__value_.__cc.second;
 }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#else
+
+template <class _Key, class _Tp, class _Compare, class _Allocator>
+_Tp&
+map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
+{
+    return __tree_.__emplace_unique_key_args(__k,
+        _VSTD::piecewise_construct,
+        _VSTD::forward_as_tuple(__k),
+        _VSTD::forward_as_tuple()).first->__cc.second;
+}
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
 {
-    __node_base_pointer __parent;
-    __node_base_pointer& __child = __find_equal_key(__parent, __k);
-    __node_pointer __r = static_cast<__node_pointer>(__child);
-    if (__child == nullptr)
-    {
-        __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
-        __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-        __r = __h.release();
-    }
-    return __r->__value_.__cc.second;
+    return __tree_.__emplace_unique_key_args(__k,
+        _VSTD::piecewise_construct,
+        _VSTD::forward_as_tuple(_VSTD::move(__k)),
+        _VSTD::forward_as_tuple()).first->__cc.second;
 }
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // !_LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
diff --git a/libcxx/test/std/containers/associative/map/map.access/index_key.pass.cpp b/libcxx/test/std/containers/associative/map/map.access/index_key.pass.cpp
index ab1144c60af..3b1c21fd5da 100644
--- a/libcxx/test/std/containers/associative/map/map.access/index_key.pass.cpp
+++ b/libcxx/test/std/containers/associative/map/map.access/index_key.pass.cpp
@@ -16,8 +16,13 @@
 #include <map>
 #include <cassert>
 
+#include "test_macros.h"
+#include "count_new.hpp"
 #include "min_allocator.h"
 #include "private_constructor.hpp"
+#if TEST_STD_VER >= 11
+#include "container_test_types.h"
+#endif
 
 int main()
 {
@@ -46,7 +51,7 @@ int main()
     assert(m[6] == 6.5);
     assert(m.size() == 8);
     }
-#if __cplusplus >= 201103L
+#if TEST_STD_VER >= 11
     {
     typedef std::pair<const int, double> V;
     V ar[] =
@@ -73,8 +78,42 @@ int main()
     assert(m[6] == 6.5);
     assert(m.size() == 8);
     }
+    {
+        // Use "container_test_types.h" to check what arguments get passed
+        // to the allocator for operator[]
+        using Container = TCT::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);
+            }
+        }
+    }
 #endif
-#if _LIBCPP_STD_VER > 11
+#if TEST_STD_VER > 11
     {
     typedef std::pair<const int, double> V;
     V ar[] =
diff --git a/libcxx/test/std/containers/associative/map/map.access/index_rv_key.pass.cpp b/libcxx/test/std/containers/associative/map/map.access/index_rv_key.pass.cpp
index 6511dcc85f5..e5580bca395 100644
--- a/libcxx/test/std/containers/associative/map/map.access/index_rv_key.pass.cpp
+++ b/libcxx/test/std/containers/associative/map/map.access/index_rv_key.pass.cpp
@@ -7,6 +7,8 @@
 //
 //===----------------------------------------------------------------------===//
 
+// UNSUPPORTED: c++98, c++03
+
 // <map>
 
 // class map
@@ -17,12 +19,13 @@
 #include <cassert>
 
 #include "test_macros.h"
+#include "count_new.hpp"
 #include "MoveOnly.h"
 #include "min_allocator.h"
+#include "container_test_types.h"
 
 int main()
 {
-#if TEST_STD_VER >= 11
     {
     std::map<MoveOnly, double> m;
     assert(m.size() == 0);
@@ -52,5 +55,27 @@ int main()
     assert(m[6] == 6.5);
     assert(m.size() == 2);
     }
-#endif
+    {
+        // Use "container_test_types.h" to check what arguments get passed
+        // to the allocator for operator[]
+        using Container = TCT::map<>;
+        using Key = Container::key_type;
+        using MappedType = Container::mapped_type;
+        using ValueTp = Container::value_type;
+        ConstructController* cc = getConstructController();
+        cc->reset();
+        {
+            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);
+            }
+        }
+    }
 }