1 // Node handles for containers -*- C++ -*-
3 // Copyright (C) 2016-2024 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/node_handle.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly.
28 * @headername{map,set,unordered_map,unordered_set}
32 #define _NODE_HANDLE 1
34 #pragma GCC system_header
36 #include <bits/version.h>
38 #ifdef __glibcxx_node_extract // C++ >= 17 && HOSTED
41 #include <bits/alloc_traits.h>
42 #include <bits/ptr_traits.h>
44 namespace std
_GLIBCXX_VISIBILITY(default)
46 _GLIBCXX_BEGIN_NAMESPACE_VERSION
49 * @defgroup node_handles Node handles
50 * @ingroup associative_containers
53 * The associative containers (`map`, `set`, `multimap` and `multiset`)
54 * support extracting and re-inserting nodes from the container. Those
55 * operations use the container's `node_handle` type, which is an alias
56 * for a `_Node_handle<...>` type. You should always use the container's
57 * `node_handle` type (e.g. `std::set<int>::node_handle`) to refer to
58 * these types, not the non-standard internal `_Node_handle` names.
63 /// Base class for node handle types of maps and sets.
64 template<typename _Val
, typename _NodeAlloc
>
65 class _Node_handle_common
67 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
70 using allocator_type
= __alloc_rebind
<_NodeAlloc
, _Val
>;
73 get_allocator() const noexcept
75 __glibcxx_assert(!this->empty());
76 return allocator_type(_M_alloc
._M_alloc
);
79 explicit operator bool() const noexcept
{ return _M_ptr
!= nullptr; }
81 [[nodiscard
]] bool empty() const noexcept
{ return _M_ptr
== nullptr; }
83 /// @cond undocumented
85 constexpr _Node_handle_common() noexcept
: _M_ptr() { }
87 ~_Node_handle_common()
93 _Node_handle_common(_Node_handle_common
&& __nh
) noexcept
97 _M_move(std::move(__nh
));
101 operator=(_Node_handle_common
&& __nh
) noexcept
106 _M_move(std::move(__nh
));
108 else if (__nh
.empty())
112 // Free the current node before replacing the allocator.
113 _AllocTraits::destroy(*_M_alloc
, _M_ptr
->_M_valptr());
114 _AllocTraits::deallocate(*_M_alloc
, _M_ptr
, 1);
116 _M_alloc
= __nh
._M_alloc
.release(); // assigns if POCMA
117 _M_ptr
= __nh
._M_ptr
;
118 __nh
._M_ptr
= nullptr;
123 _Node_handle_common(typename
_AllocTraits::pointer __ptr
,
124 const _NodeAlloc
& __alloc
)
125 : _M_ptr(__ptr
), _M_alloc(__alloc
)
127 __glibcxx_assert(__ptr
!= nullptr);
131 _M_swap(_Node_handle_common
& __nh
) noexcept
136 _M_move(std::move(__nh
));
138 else if (__nh
.empty())
139 __nh
._M_move(std::move(*this));
143 swap(_M_ptr
, __nh
._M_ptr
);
144 _M_alloc
.swap(__nh
._M_alloc
); // swaps if POCS
149 // Moves the pointer and allocator from __nh to *this.
150 // Precondition: empty() && !__nh.empty()
151 // Postcondition: !empty() && __nh.empty()
153 _M_move(_Node_handle_common
&& __nh
) noexcept
155 ::new (std::__addressof(_M_alloc
)) _NodeAlloc(__nh
._M_alloc
.release());
156 _M_ptr
= __nh
._M_ptr
;
157 __nh
._M_ptr
= nullptr;
160 // Deallocates the node, destroys the allocator.
161 // Precondition: !empty()
162 // Postcondition: empty()
166 _NodeAlloc __alloc
= _M_alloc
.release();
167 _AllocTraits::destroy(__alloc
, _M_ptr
->_M_valptr());
168 _AllocTraits::deallocate(__alloc
, _M_ptr
, 1);
173 typename
_AllocTraits::pointer _M_ptr
;
176 // A simplified, non-copyable std::optional<_NodeAlloc>.
177 // Call release() before destruction iff the allocator member is active.
178 union _Optional_alloc
180 _Optional_alloc() { }
181 ~_Optional_alloc() { }
183 _Optional_alloc(_Optional_alloc
&&) = delete;
184 _Optional_alloc
& operator=(_Optional_alloc
&&) = delete;
186 _Optional_alloc(const _NodeAlloc
& __alloc
) noexcept
190 // Precondition: _M_alloc is the active member of the union.
192 operator=(_NodeAlloc
&& __alloc
) noexcept
194 using _ATr
= _AllocTraits
;
195 if constexpr (_ATr::propagate_on_container_move_assignment::value
)
196 _M_alloc
= std::move(__alloc
);
197 else if constexpr (!_AllocTraits::is_always_equal::value
)
198 __glibcxx_assert(_M_alloc
== __alloc
);
201 // Precondition: _M_alloc is the active member of both unions.
203 swap(_Optional_alloc
& __other
) noexcept
206 if constexpr (_AllocTraits::propagate_on_container_swap::value
)
207 swap(_M_alloc
, __other
._M_alloc
);
208 else if constexpr (!_AllocTraits::is_always_equal::value
)
209 __glibcxx_assert(_M_alloc
== __other
._M_alloc
);
212 // Precondition: _M_alloc is the active member of the union.
213 _NodeAlloc
& operator*() noexcept
{ return _M_alloc
; }
215 // Precondition: _M_alloc is the active member of the union.
216 _NodeAlloc
release() noexcept
218 _NodeAlloc __tmp
= std::move(_M_alloc
);
219 _M_alloc
.~_NodeAlloc();
225 [[__no_unique_address__
]] _Empty _M_empty
;
226 [[__no_unique_address__
]] _NodeAlloc _M_alloc
;
229 [[__no_unique_address__
]] _Optional_alloc _M_alloc
;
231 template<typename _Key2
, typename _Value2
, typename _KeyOfValue
,
232 typename _Compare
, typename _ValueAlloc
>
233 friend class _Rb_tree
;
238 /// Node handle type for maps.
239 template<typename _Key
, typename _Value
, typename _NodeAlloc
>
240 class _Node_handle
: public _Node_handle_common
<_Value
, _NodeAlloc
>
243 constexpr _Node_handle() noexcept
= default;
244 ~_Node_handle() = default;
245 _Node_handle(_Node_handle
&&) noexcept
= default;
248 operator=(_Node_handle
&&) noexcept
= default;
250 using key_type
= _Key
;
251 using mapped_type
= typename
_Value::second_type
;
256 __glibcxx_assert(!this->empty());
261 mapped() const noexcept
263 __glibcxx_assert(!this->empty());
268 swap(_Node_handle
& __nh
) noexcept
272 swap(_M_pkey
, __nh
._M_pkey
);
273 swap(_M_pmapped
, __nh
._M_pmapped
);
277 swap(_Node_handle
& __x
, _Node_handle
& __y
)
278 noexcept(noexcept(__x
.swap(__y
)))
282 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
284 _Node_handle(typename
_AllocTraits::pointer __ptr
,
285 const _NodeAlloc
& __alloc
)
286 : _Node_handle_common
<_Value
, _NodeAlloc
>(__ptr
, __alloc
)
290 auto& __key
= const_cast<_Key
&>(__ptr
->_M_valptr()->first
);
291 _M_pkey
= _S_pointer_to(__key
);
292 _M_pmapped
= _S_pointer_to(__ptr
->_M_valptr()->second
);
297 _M_pmapped
= nullptr;
301 template<typename _Tp
>
303 = __ptr_rebind
<typename
_AllocTraits::pointer
,
304 remove_reference_t
<_Tp
>>;
306 __pointer
<_Key
> _M_pkey
= nullptr;
307 __pointer
<typename
_Value::second_type
> _M_pmapped
= nullptr;
309 template<typename _Tp
>
311 _S_pointer_to(_Tp
& __obj
)
312 { return pointer_traits
<__pointer
<_Tp
>>::pointer_to(__obj
); }
315 _M_key() const noexcept
{ return key(); }
317 template<typename _Key2
, typename _Value2
, typename _KeyOfValue
,
318 typename _Compare
, typename _ValueAlloc
>
319 friend class _Rb_tree
;
321 template<typename _Key2
, typename _Value2
, typename _ValueAlloc
,
322 typename _ExtractKey
, typename _Equal
,
323 typename _Hash
, typename _RangeHash
, typename _Unused
,
324 typename _RehashPolicy
, typename _Traits
>
325 friend class _Hashtable
;
328 /// Node handle type for sets.
329 template<typename _Value
, typename _NodeAlloc
>
330 class _Node_handle
<_Value
, _Value
, _NodeAlloc
>
331 : public _Node_handle_common
<_Value
, _NodeAlloc
>
334 constexpr _Node_handle() noexcept
= default;
335 ~_Node_handle() = default;
336 _Node_handle(_Node_handle
&&) noexcept
= default;
339 operator=(_Node_handle
&&) noexcept
= default;
341 using value_type
= _Value
;
344 value() const noexcept
346 __glibcxx_assert(!this->empty());
347 return *this->_M_ptr
->_M_valptr();
351 swap(_Node_handle
& __nh
) noexcept
352 { this->_M_swap(__nh
); }
355 swap(_Node_handle
& __x
, _Node_handle
& __y
)
356 noexcept(noexcept(__x
.swap(__y
)))
360 using _AllocTraits
= allocator_traits
<_NodeAlloc
>;
362 _Node_handle(typename
_AllocTraits::pointer __ptr
,
363 const _NodeAlloc
& __alloc
)
364 : _Node_handle_common
<_Value
, _NodeAlloc
>(__ptr
, __alloc
) { }
367 _M_key() const noexcept
{ return value(); }
369 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
370 typename _Compare
, typename _Alloc
>
371 friend class _Rb_tree
;
373 template<typename _Key2
, typename _Value2
, typename _ValueAlloc
,
374 typename _ExtractKey
, typename _Equal
,
375 typename _Hash
, typename _RangeHash
, typename _Unused
,
376 typename _RehashPolicy
, typename _Traits
>
377 friend class _Hashtable
;
380 /// Return type of insert(node_handle&&) on unique maps/sets.
381 template<typename _Iterator
, typename _NodeHandle
>
382 struct _Node_insert_return
384 _Iterator position
= _Iterator();
385 bool inserted
= false;
391 _GLIBCXX_END_NAMESPACE_VERSION
394 #endif // __glibcxx_node_extract