First half of C++17's splicing maps and sets

This commit adds a node handle type, (located in __node_handle), and adds
extract() and insert() members to all map and set types, as well as their
implementations in __tree and __hash_table.

The second half of this feature is adding merge() members, which splice nodes
in bulk from one container into another. This will be committed in a follow-up.

Differential revision: https://reviews.llvm.org/D46845

llvm-svn: 338472

1 files changed, 164 insertions, 6 deletions

diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 30c32f16393..af9b9616df8 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -796,6 +796,16 @@ public:
     template <class> friend class __map_node_destructor;
 };
 
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>
+    : __tree_node_destructor<_Alloc>
+{
+    using __tree_node_destructor<_Alloc>::__tree_node_destructor;
+};
+#endif
 
 template <class _Tp, class _NodePtr, class _DiffType>
 class _LIBCPP_TEMPLATE_VIS __tree_iterator
@@ -1338,6 +1348,33 @@ public:
     iterator __node_insert_multi(__node_pointer __nd);
     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
+
+    _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer);
+
+#if _LIBCPP_STD_VER > 14
+    template <class _NodeHandle, class _InsertReturnType>
+    _LIBCPP_INLINE_VISIBILITY
+    _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(_NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
+
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract(key_type const&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract(const_iterator);
+#endif
+
     iterator erase(const_iterator __p);
     iterator erase(const_iterator __f, const_iterator __l);
     template <class _Key>
@@ -2347,17 +2384,138 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
-__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr)
 {
-    __node_pointer __np = __p.__get_np();
-    iterator __r(__p.__ptr_);
+    iterator __r(__ptr);
     ++__r;
-    if (__begin_node() == __p.__ptr_)
+    if (__begin_node() == __ptr)
         __begin_node() = __r.__ptr_;
     --size();
-    __node_allocator& __na = __node_alloc();
     __tree_remove(__end_node()->__left_,
-                  static_cast<__node_base_pointer>(__np));
+                  static_cast<__node_base_pointer>(__ptr));
+    return __r;
+}
+
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle, class _InsertReturnType>
+_LIBCPP_INLINE_VISIBILITY
+_InsertReturnType
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return _InsertReturnType{end(), false, _NodeHandle()};
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_equal(__parent,
+                                                __ptr->__value_);
+    if (__child != nullptr)
+        return _InsertReturnType{
+            iterator(static_cast<__node_pointer>(__child)),
+            false, _VSTD::move(__nh)};
+
+    __insert_node_at(__parent, __child,
+                     static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
+    __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy,
+                                                __ptr->__value_);
+    __node_pointer __r = static_cast<__node_pointer>(__child);
+    if (__child == nullptr)
+    {
+        __insert_node_at(__parent, __child,
+                         static_cast<__node_base_pointer>(__ptr));
+        __r = __ptr;
+        __nh.__release();
+    }
+    return iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key)
+{
+    iterator __it = find(__key);
+    if (__it == end())
+        return _NodeHandle();
+    return __node_handle_extract<_NodeHandle>(__it);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    __remove_node_pointer(__np);
+    return _NodeHandle(__np, __alloc());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_leaf_high(
+        __parent, _NodeTypes::__get_key(__ptr->__value_));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return iterator(__ptr);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_leaf(__hint, __parent,
+                                               _NodeTypes::__get_key(__ptr->__value_));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return iterator(__ptr);
+}
+
+#endif  // _LIBCPP_STD_VER > 14
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    iterator __r = __remove_node_pointer(__np);
+    __node_allocator& __na = __node_alloc();
     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
         const_cast<__node_value_type&>(*__p)));
     __node_traits::deallocate(__na, __np, 1);