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