1// Node handles for containers -*- C++ -*-
2
3// Copyright (C) 2016-2024 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
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}
29 */
30
31#ifndef _NODE_HANDLE
32#define _NODE_HANDLE 1
33
34#pragma GCC system_header
35
36#include <bits/version.h>
37
38#ifdef __glibcxx_node_extract // C++ >= 17 && HOSTED
39
40#include <new>
41#include <bits/alloc_traits.h>
42#include <bits/ptr_traits.h>
43
44namespace std _GLIBCXX_VISIBILITY(default)
45{
46_GLIBCXX_BEGIN_NAMESPACE_VERSION
47
48 /**
49 * @defgroup node_handles Node handles
50 * @ingroup associative_containers
51 * @since C++17
52 *
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.
59 *
60 * @{
61 */
62
63 /// Base class for node handle types of maps and sets.
64 template<typename _Val, typename _NodeAlloc>
65 class _Node_handle_common
66 {
67 using _AllocTraits = allocator_traits<_NodeAlloc>;
68
69 public:
70 using allocator_type = __alloc_rebind<_NodeAlloc, _Val>;
71
72 allocator_type
73 get_allocator() const noexcept
74 {
75 __glibcxx_assert(!this->empty());
76 return allocator_type(_M_alloc._M_alloc);
77 }
78
79 explicit operator bool() const noexcept { return _M_ptr != nullptr; }
80
81 [[nodiscard]] bool empty() const noexcept { return _M_ptr == nullptr; }
82
83 /// @cond undocumented
84 protected:
85 constexpr _Node_handle_common() noexcept : _M_ptr() { }
86
87 ~_Node_handle_common()
88 {
89 if (!empty())
90 _M_reset();
91 }
92
93 _Node_handle_common(_Node_handle_common&& __nh) noexcept
94 : _M_ptr(__nh._M_ptr)
95 {
96 if (_M_ptr)
97 _M_move(nh: std::move(__nh));
98 }
99
100 _Node_handle_common&
101 operator=(_Node_handle_common&& __nh) noexcept
102 {
103 if (empty())
104 {
105 if (!__nh.empty())
106 _M_move(nh: std::move(__nh));
107 }
108 else if (__nh.empty())
109 _M_reset();
110 else
111 {
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);
115
116 _M_alloc = __nh._M_alloc.release(); // assigns if POCMA
117 _M_ptr = __nh._M_ptr;
118 __nh._M_ptr = nullptr;
119 }
120 return *this;
121 }
122
123 _Node_handle_common(typename _AllocTraits::pointer __ptr,
124 const _NodeAlloc& __alloc)
125 : _M_ptr(__ptr), _M_alloc(__alloc)
126 {
127 __glibcxx_assert(__ptr != nullptr);
128 }
129
130 void
131 _M_swap(_Node_handle_common& __nh) noexcept
132 {
133 if (empty())
134 {
135 if (!__nh.empty())
136 _M_move(nh: std::move(__nh));
137 }
138 else if (__nh.empty())
139 __nh._M_move(std::move(*this));
140 else
141 {
142 using std::swap;
143 swap(_M_ptr, __nh._M_ptr);
144 _M_alloc.swap(__nh._M_alloc); // swaps if POCS
145 }
146 }
147
148 private:
149 // Moves the pointer and allocator from __nh to *this.
150 // Precondition: empty() && !__nh.empty()
151 // Postcondition: !empty() && __nh.empty()
152 void
153 _M_move(_Node_handle_common&& __nh) noexcept
154 {
155 ::new (std::__addressof(_M_alloc)) _NodeAlloc(__nh._M_alloc.release());
156 _M_ptr = __nh._M_ptr;
157 __nh._M_ptr = nullptr;
158 }
159
160 // Deallocates the node, destroys the allocator.
161 // Precondition: !empty()
162 // Postcondition: empty()
163 void
164 _M_reset() noexcept
165 {
166 _NodeAlloc __alloc = _M_alloc.release();
167 _AllocTraits::destroy(__alloc, _M_ptr->_M_valptr());
168 _AllocTraits::deallocate(__alloc, _M_ptr, 1);
169 _M_ptr = nullptr;
170 }
171
172 // Destroys the allocator. Does not deallocate or destroy the node.
173 // Precondition: !empty()
174 // Postcondition: empty()
175 void
176 release() noexcept
177 {
178 _M_alloc.release();
179 _M_ptr = nullptr;
180 }
181
182 protected:
183 typename _AllocTraits::pointer _M_ptr;
184
185 private:
186 // A simplified, non-copyable std::optional<_NodeAlloc>.
187 // Call release() before destruction iff the allocator member is active.
188 union _Optional_alloc
189 {
190 _Optional_alloc() { }
191 ~_Optional_alloc() { }
192
193 _Optional_alloc(_Optional_alloc&&) = delete;
194 _Optional_alloc& operator=(_Optional_alloc&&) = delete;
195
196 _Optional_alloc(const _NodeAlloc& __alloc) noexcept
197 : _M_alloc(__alloc)
198 { }
199
200 // Precondition: _M_alloc is the active member of the union.
201 void
202 operator=(_NodeAlloc&& __alloc) noexcept
203 {
204 using _ATr = _AllocTraits;
205 if constexpr (_ATr::propagate_on_container_move_assignment::value)
206 _M_alloc = std::move(__alloc);
207 else if constexpr (!_AllocTraits::is_always_equal::value)
208 __glibcxx_assert(_M_alloc == __alloc);
209 }
210
211 // Precondition: _M_alloc is the active member of both unions.
212 void
213 swap(_Optional_alloc& __other) noexcept
214 {
215 using std::swap;
216 if constexpr (_AllocTraits::propagate_on_container_swap::value)
217 swap(_M_alloc, __other._M_alloc);
218 else if constexpr (!_AllocTraits::is_always_equal::value)
219 __glibcxx_assert(_M_alloc == __other._M_alloc);
220 }
221
222 // Precondition: _M_alloc is the active member of the union.
223 _NodeAlloc& operator*() noexcept { return _M_alloc; }
224
225 // Precondition: _M_alloc is the active member of the union.
226 _NodeAlloc release() noexcept
227 {
228 _NodeAlloc __tmp = std::move(_M_alloc);
229 _M_alloc.~_NodeAlloc();
230 return __tmp;
231 }
232
233 [[__no_unique_address__]] _NodeAlloc _M_alloc;
234 };
235
236 [[__no_unique_address__]] _Optional_alloc _M_alloc;
237
238 template<typename _Key2, typename _Value2, typename _KeyOfValue,
239 typename _Compare, typename _ValueAlloc>
240 friend class _Rb_tree;
241
242 template<typename _Key2, typename _Value2, typename _ValueAlloc,
243 typename _ExtractKey, typename _Equal,
244 typename _Hash, typename _RangeHash, typename _Unused,
245 typename _RehashPolicy, typename _Traits>
246 friend class _Hashtable;
247
248 /// @endcond
249 };
250
251 /// Node handle type for maps.
252 template<typename _Key, typename _Value, typename _NodeAlloc>
253 class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc>
254 {
255 public:
256 constexpr _Node_handle() noexcept = default;
257 ~_Node_handle() = default;
258 _Node_handle(_Node_handle&&) noexcept = default;
259
260 _Node_handle&
261 operator=(_Node_handle&&) noexcept = default;
262
263 using key_type = _Key;
264 using mapped_type = typename _Value::second_type;
265
266 key_type&
267 key() const noexcept
268 {
269 __glibcxx_assert(!this->empty());
270 return *_M_pkey;
271 }
272
273 mapped_type&
274 mapped() const noexcept
275 {
276 __glibcxx_assert(!this->empty());
277 return *_M_pmapped;
278 }
279
280 void
281 swap(_Node_handle& __nh) noexcept
282 {
283 this->_M_swap(__nh);
284 using std::swap;
285 swap(_M_pkey, __nh._M_pkey);
286 swap(_M_pmapped, __nh._M_pmapped);
287 }
288
289 friend void
290 swap(_Node_handle& __x, _Node_handle& __y)
291 noexcept(noexcept(__x.swap(__y)))
292 { __x.swap(__y); }
293
294 private:
295 using _AllocTraits = allocator_traits<_NodeAlloc>;
296
297 _Node_handle(typename _AllocTraits::pointer __ptr,
298 const _NodeAlloc& __alloc)
299 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
300 {
301 if (__ptr)
302 {
303 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
304 _M_pkey = _S_pointer_to(__key);
305 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
306 }
307 else
308 {
309 _M_pkey = nullptr;
310 _M_pmapped = nullptr;
311 }
312 }
313
314 template<typename _Tp>
315 using __pointer
316 = __ptr_rebind<typename _AllocTraits::pointer,
317 remove_reference_t<_Tp>>;
318
319 __pointer<_Key> _M_pkey = nullptr;
320 __pointer<typename _Value::second_type> _M_pmapped = nullptr;
321
322 template<typename _Tp>
323 __pointer<_Tp>
324 _S_pointer_to(_Tp& __obj)
325 { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
326
327 const key_type&
328 _M_key() const noexcept { return key(); }
329
330 template<typename _Key2, typename _Value2, typename _KeyOfValue,
331 typename _Compare, typename _ValueAlloc>
332 friend class _Rb_tree;
333
334 template<typename _Key2, typename _Value2, typename _ValueAlloc,
335 typename _ExtractKey, typename _Equal,
336 typename _Hash, typename _RangeHash, typename _Unused,
337 typename _RehashPolicy, typename _Traits>
338 friend class _Hashtable;
339 };
340
341 /// Node handle type for sets.
342 template<typename _Value, typename _NodeAlloc>
343 class _Node_handle<_Value, _Value, _NodeAlloc>
344 : public _Node_handle_common<_Value, _NodeAlloc>
345 {
346 public:
347 constexpr _Node_handle() noexcept = default;
348 ~_Node_handle() = default;
349 _Node_handle(_Node_handle&&) noexcept = default;
350
351 _Node_handle&
352 operator=(_Node_handle&&) noexcept = default;
353
354 using value_type = _Value;
355
356 value_type&
357 value() const noexcept
358 {
359 __glibcxx_assert(!this->empty());
360 return *this->_M_ptr->_M_valptr();
361 }
362
363 void
364 swap(_Node_handle& __nh) noexcept
365 { this->_M_swap(__nh); }
366
367 friend void
368 swap(_Node_handle& __x, _Node_handle& __y)
369 noexcept(noexcept(__x.swap(__y)))
370 { __x.swap(__y); }
371
372 private:
373 using _AllocTraits = allocator_traits<_NodeAlloc>;
374
375 _Node_handle(typename _AllocTraits::pointer __ptr,
376 const _NodeAlloc& __alloc)
377 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
378
379 const value_type&
380 _M_key() const noexcept { return value(); }
381
382 template<typename _Key, typename _Val, typename _KeyOfValue,
383 typename _Compare, typename _Alloc>
384 friend class _Rb_tree;
385
386 template<typename _Key2, typename _Value2, typename _ValueAlloc,
387 typename _ExtractKey, typename _Equal,
388 typename _Hash, typename _RangeHash, typename _Unused,
389 typename _RehashPolicy, typename _Traits>
390 friend class _Hashtable;
391 };
392
393 /// Return type of insert(node_handle&&) on unique maps/sets.
394 template<typename _Iterator, typename _NodeHandle>
395 struct _Node_insert_return
396 {
397 _Iterator position = _Iterator();
398 bool inserted = false;
399 _NodeHandle node;
400 };
401
402 /// @}
403
404_GLIBCXX_END_NAMESPACE_VERSION
405} // namespace std
406
407#endif // __glibcxx_node_extract
408#endif
409