32 #define _NODE_HANDLE 1
34 #pragma GCC system_header
36 #if __cplusplus > 201402L
37 # define __cpp_lib_node_extract 201606
43 namespace std _GLIBCXX_VISIBILITY(default)
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
48 template<
typename _Val,
typename _NodeAlloc>
49 class _Node_handle_common
51 using _AllocTraits = allocator_traits<_NodeAlloc>;
54 using allocator_type = __alloc_rebind<_NodeAlloc, _Val>;
57 get_allocator() const noexcept
59 __glibcxx_assert(!this->empty());
60 return allocator_type(*_M_alloc);
63 explicit operator bool() const noexcept {
return _M_ptr !=
nullptr; }
65 bool empty() const noexcept {
return _M_ptr ==
nullptr; }
68 constexpr _Node_handle_common() noexcept : _M_ptr(), _M_alloc() {}
70 ~_Node_handle_common() { _M_destroy(); }
72 _Node_handle_common(_Node_handle_common&& __nh) noexcept
73 : _M_ptr(__nh._M_ptr), _M_alloc(std::move(__nh._M_alloc))
75 __nh._M_ptr =
nullptr;
80 operator=(_Node_handle_common&& __nh) noexcept
84 if constexpr (is_move_assignable_v<_NodeAlloc>)
86 if (_AllocTraits::propagate_on_container_move_assignment::value
88 this->_M_alloc = std::move(__nh._M_alloc);
90 __glibcxx_assert(this->_M_alloc == __nh._M_alloc);
93 __glibcxx_assert(_M_alloc);
94 __nh._M_ptr =
nullptr;
99 _Node_handle_common(
typename _AllocTraits::pointer __ptr,
100 const _NodeAlloc& __alloc)
101 : _M_ptr(__ptr), _M_alloc(__alloc) { }
104 _M_swap(_Node_handle_common& __nh) noexcept
107 swap(_M_ptr, __nh._M_ptr);
108 if (_AllocTraits::propagate_on_container_swap
109 || !_M_alloc || !__nh._M_alloc)
110 _M_alloc.swap(__nh._M_alloc);
112 __glibcxx_assert(_M_alloc == __nh._M_alloc);
117 _M_destroy() noexcept
119 if (_M_ptr !=
nullptr)
121 allocator_type __alloc(*_M_alloc);
123 _M_ptr->_M_valptr());
124 _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1);
129 typename _AllocTraits::pointer _M_ptr;
131 optional<_NodeAlloc> _M_alloc;
133 template<
typename _Key2,
typename _Value2,
typename _KeyOfValue,
134 typename _Compare,
typename _ValueAlloc>
135 friend class _Rb_tree;
139 template<
typename _Key,
typename _Value,
typename _NodeAlloc>
140 class _Node_handle :
public _Node_handle_common<_Value, _NodeAlloc>
143 constexpr _Node_handle() noexcept = default;
144 ~_Node_handle() = default;
145 _Node_handle(_Node_handle&&) noexcept = default;
148 operator=(_Node_handle&&) noexcept = default;
150 using key_type = _Key;
151 using mapped_type = typename _Value::second_type;
156 __glibcxx_assert(!this->empty());
161 mapped() const noexcept
163 __glibcxx_assert(!this->empty());
168 swap(_Node_handle& __nh) noexcept
172 swap(_M_pkey, __nh._M_pkey);
173 swap(_M_pmapped, __nh._M_pmapped);
177 swap(_Node_handle& __x, _Node_handle& __y)
178 noexcept(noexcept(__x.swap(__y)))
182 using _AllocTraits = allocator_traits<_NodeAlloc>;
184 _Node_handle(
typename _AllocTraits::pointer __ptr,
185 const _NodeAlloc& __alloc)
186 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
190 auto& __key =
const_cast<_Key&
>(__ptr->_M_valptr()->first);
191 _M_pkey = _S_pointer_to(__key);
192 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
197 _M_pmapped =
nullptr;
201 template<
typename _Tp>
204 remove_reference_t<_Tp>>;
206 __pointer<_Key> _M_pkey =
nullptr;
207 __pointer<typename _Value::second_type> _M_pmapped =
nullptr;
209 template<
typename _Tp>
211 _S_pointer_to(_Tp& __obj)
212 {
return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
215 _M_key() const noexcept {
return key(); }
217 template<
typename _Key2,
typename _Value2,
typename _KeyOfValue,
218 typename _Compare,
typename _ValueAlloc>
219 friend class _Rb_tree;
221 template<
typename _Key2,
typename _Value2,
typename _ValueAlloc,
222 typename _ExtractKey,
typename _Equal,
223 typename _H1,
typename _H2,
typename _Hash,
224 typename _RehashPolicy,
typename _Traits>
225 friend class _Hashtable;
229 template<
typename _Value,
typename _NodeAlloc>
230 class _Node_handle<_Value, _Value, _NodeAlloc>
231 :
public _Node_handle_common<_Value, _NodeAlloc>
234 constexpr _Node_handle() noexcept = default;
235 ~_Node_handle() = default;
236 _Node_handle(_Node_handle&&) noexcept = default;
239 operator=(_Node_handle&&) noexcept = default;
241 using value_type = _Value;
244 value() const noexcept
246 __glibcxx_assert(!this->empty());
247 return *this->_M_ptr->_M_valptr();
251 swap(_Node_handle& __nh) noexcept
252 { this->_M_swap(__nh); }
255 swap(_Node_handle& __x, _Node_handle& __y)
256 noexcept(noexcept(__x.swap(__y)))
260 using _AllocTraits = allocator_traits<_NodeAlloc>;
262 _Node_handle(
typename _AllocTraits::pointer __ptr,
263 const _NodeAlloc& __alloc)
264 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
267 _M_key() const noexcept {
return value(); }
269 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
270 typename _Compare,
typename _Alloc>
271 friend class _Rb_tree;
273 template<
typename _Key2,
typename _Value2,
typename _ValueAlloc,
274 typename _ExtractKey,
typename _Equal,
275 typename _H1,
typename _H2,
typename _Hash,
276 typename _RehashPolicy,
typename _Traits>
277 friend class _Hashtable;
281 template<
typename _Iterator,
typename _NodeHandle>
282 struct _Node_insert_return
284 _Iterator position = _Iterator();
285 bool inserted =
false;
289 _GLIBCXX_END_NAMESPACE_VERSION
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
static void destroy(_Alloc &__a, _Tp *__p)
Destroy an object of type _Tp.
constexpr nullopt_t nullopt
Tag to disengage optional objects.