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