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
_GLIBCXX_VISIBILITY(default)43 namespace 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 // Destroys the allocator. Does not deallocate or destroy the node.
172 // Precondition: !empty()
173 // Postcondition: empty()
174 void
175 release() noexcept
176 {
177 _M_alloc.release();
178 _M_ptr = nullptr;
179 }
180
181 protected:
182 typename _AllocTraits::pointer _M_ptr;
183
184 private:
185 // A simplified, non-copyable std::optional<_NodeAlloc>.
186 // Call release() before destruction iff the allocator member is active.
187 union _Optional_alloc
188 {
189 _Optional_alloc() { }
190 ~_Optional_alloc() { }
191
192 _Optional_alloc(_Optional_alloc&&) = delete;
193 _Optional_alloc& operator=(_Optional_alloc&&) = delete;
194
195 _Optional_alloc(const _NodeAlloc& __alloc) noexcept
196 : _M_alloc(__alloc)
197 { }
198
199 // Precondition: _M_alloc is the active member of the union.
200 void
201 operator=(_NodeAlloc&& __alloc) noexcept
202 {
203 using _ATr = _AllocTraits;
204 if constexpr (_ATr::propagate_on_container_move_assignment::value)
205 _M_alloc = std::move(__alloc);
206 else if constexpr (!_AllocTraits::is_always_equal::value)
207 __glibcxx_assert(_M_alloc == __alloc);
208 }
209
210 // Precondition: _M_alloc is the active member of both unions.
211 void
212 swap(_Optional_alloc& __other) noexcept
213 {
214 using std::swap;
215 if constexpr (_AllocTraits::propagate_on_container_swap::value)
216 swap(_M_alloc, __other._M_alloc);
217 else if constexpr (!_AllocTraits::is_always_equal::value)
218 __glibcxx_assert(_M_alloc == __other._M_alloc);
219 }
220
221 // Precondition: _M_alloc is the active member of the union.
222 _NodeAlloc& operator*() noexcept { return _M_alloc; }
223
224 // Precondition: _M_alloc is the active member of the union.
225 _NodeAlloc release() noexcept
226 {
227 _NodeAlloc __tmp = std::move(_M_alloc);
228 _M_alloc.~_NodeAlloc();
229 return __tmp;
230 }
231
232 [[__no_unique_address__]] _NodeAlloc _M_alloc;
233 };
234
235 [[__no_unique_address__]] _Optional_alloc _M_alloc;
236
237 template<typename _Key2, typename _Value2, typename _KeyOfValue,
238 typename _Compare, typename _ValueAlloc>
239 friend class _Rb_tree;
240
241 template<typename _Key2, typename _Value2, typename _ValueAlloc,
242 typename _ExtractKey, typename _Equal,
243 typename _Hash, typename _RangeHash, typename _Unused,
244 typename _RehashPolicy, typename _Traits>
245 friend class _Hashtable;
246
247 /// @endcond
248 };
249
250 /// Node handle type for maps.
251 template<typename _Key, typename _Value, typename _NodeAlloc>
252 class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc>
253 {
254 public:
255 constexpr _Node_handle() noexcept = default;
256 ~_Node_handle() = default;
257 _Node_handle(_Node_handle&&) noexcept = default;
258
259 _Node_handle&
260 operator=(_Node_handle&&) noexcept = default;
261
262 using key_type = _Key;
263 using mapped_type = typename _Value::second_type;
264
265 key_type&
266 key() const noexcept
267 {
268 __glibcxx_assert(!this->empty());
269 return *_M_pkey;
270 }
271
272 mapped_type&
273 mapped() const noexcept
274 {
275 __glibcxx_assert(!this->empty());
276 return *_M_pmapped;
277 }
278
279 void
280 swap(_Node_handle& __nh) noexcept
281 {
282 this->_M_swap(__nh);
283 using std::swap;
284 swap(_M_pkey, __nh._M_pkey);
285 swap(_M_pmapped, __nh._M_pmapped);
286 }
287
288 friend void
289 swap(_Node_handle& __x, _Node_handle& __y)
290 noexcept(noexcept(__x.swap(__y)))
291 { __x.swap(__y); }
292
293 private:
294 using _AllocTraits = allocator_traits<_NodeAlloc>;
295
296 _Node_handle(typename _AllocTraits::pointer __ptr,
297 const _NodeAlloc& __alloc)
298 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
299 {
300 if (__ptr)
301 {
302 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
303 _M_pkey = _S_pointer_to(__key);
304 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
305 }
306 else
307 {
308 _M_pkey = nullptr;
309 _M_pmapped = nullptr;
310 }
311 }
312
313 template<typename _Tp>
314 using __pointer
315 = __ptr_rebind<typename _AllocTraits::pointer,
316 remove_reference_t<_Tp>>;
317
318 __pointer<_Key> _M_pkey = nullptr;
319 __pointer<typename _Value::second_type> _M_pmapped = nullptr;
320
321 template<typename _Tp>
322 __pointer<_Tp>
323 _S_pointer_to(_Tp& __obj)
324 { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
325
326 const key_type&
327 _M_key() const noexcept { return key(); }
328
329 template<typename _Key2, typename _Value2, typename _KeyOfValue,
330 typename _Compare, typename _ValueAlloc>
331 friend class _Rb_tree;
332
333 template<typename _Key2, typename _Value2, typename _ValueAlloc,
334 typename _ExtractKey, typename _Equal,
335 typename _Hash, typename _RangeHash, typename _Unused,
336 typename _RehashPolicy, typename _Traits>
337 friend class _Hashtable;
338 };
339
340 /// Node handle type for sets.
341 template<typename _Value, typename _NodeAlloc>
342 class _Node_handle<_Value, _Value, _NodeAlloc>
343 : public _Node_handle_common<_Value, _NodeAlloc>
344 {
345 public:
346 constexpr _Node_handle() noexcept = default;
347 ~_Node_handle() = default;
348 _Node_handle(_Node_handle&&) noexcept = default;
349
350 _Node_handle&
351 operator=(_Node_handle&&) noexcept = default;
352
353 using value_type = _Value;
354
355 value_type&
356 value() const noexcept
357 {
358 __glibcxx_assert(!this->empty());
359 return *this->_M_ptr->_M_valptr();
360 }
361
362 void
363 swap(_Node_handle& __nh) noexcept
364 { this->_M_swap(__nh); }
365
366 friend void
367 swap(_Node_handle& __x, _Node_handle& __y)
368 noexcept(noexcept(__x.swap(__y)))
369 { __x.swap(__y); }
370
371 private:
372 using _AllocTraits = allocator_traits<_NodeAlloc>;
373
374 _Node_handle(typename _AllocTraits::pointer __ptr,
375 const _NodeAlloc& __alloc)
376 : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
377
378 const value_type&
379 _M_key() const noexcept { return value(); }
380
381 template<typename _Key, typename _Val, typename _KeyOfValue,
382 typename _Compare, typename _Alloc>
383 friend class _Rb_tree;
384
385 template<typename _Key2, typename _Value2, typename _ValueAlloc,
386 typename _ExtractKey, typename _Equal,
387 typename _Hash, typename _RangeHash, typename _Unused,
388 typename _RehashPolicy, typename _Traits>
389 friend class _Hashtable;
390 };
391
392 /// Return type of insert(node_handle&&) on unique maps/sets.
393 template<typename _Iterator, typename _NodeHandle>
394 struct _Node_insert_return
395 {
396 _Iterator position = _Iterator();
397 bool inserted = false;
398 _NodeHandle node;
399 };
400
401 /// @}
402
403 _GLIBCXX_END_NAMESPACE_VERSION
404 } // namespace std
405
406 #endif // C++17
407 #endif
408