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
Cr-Mirrored-From: sso://chromium.googlesource.com/_direct/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: b0386a515b60c2f43eaaef986bd5b1cdc4448244
diff --git a/include/__tree b/include/__tree
index 30c32f1..af9b961 100644
--- a/include/__tree
+++ b/include/__tree
@@ -796,6 +796,16 @@
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 @@
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 @@
template <class _Tp, class _Compare, class _Allocator>
typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr)
+{
+ iterator __r(__ptr);
+ ++__r;
+ if (__begin_node() == __ptr)
+ __begin_node() = __r.__ptr_;
+ --size();
+ __tree_remove(__end_node()->__left_,
+ 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(__p.__ptr_);
- ++__r;
- if (__begin_node() == __p.__ptr_)
- __begin_node() = __r.__ptr_;
- --size();
+ iterator __r = __remove_node_pointer(__np);
__node_allocator& __na = __node_alloc();
- __tree_remove(__end_node()->__left_,
- static_cast<__node_base_pointer>(__np));
__node_traits::destroy(__na, _NodeTypes::__get_ptr(
const_cast<__node_value_type&>(*__p)));
__node_traits::deallocate(__na, __np, 1);