libstdc++
node_handle.h
Go to the documentation of this file.
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 
44 namespace 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>
66  {
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 
88  {
89  if (!empty())
90  _M_reset();
91  }
92 
94  : _M_ptr(__nh._M_ptr)
95  {
96  if (_M_ptr)
97  _M_move(std::move(__nh));
98  }
99 
101  operator=(_Node_handle_common&& __nh) noexcept
102  {
103  if (empty())
104  {
105  if (!__nh.empty())
106  _M_move(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 
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(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:
296 
297  _Node_handle(typename _AllocTraits::pointer __ptr,
298  const _NodeAlloc& __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
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:
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>
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
ISO C++ entities toplevel namespace is std.
Node handle type for maps.
Definition: node_handle.h:253
static constexpr void destroy(_Alloc &__a, _Tp *__p) noexcept(noexcept(_S_destroy(__a, __p, 0)))
Destroy an object of type _Tp.
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:177
Uniform interface to all allocator types.
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1718
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:400
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:126
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
Definition: ptr_traits.h:201
__detected_or_t< value_type *, __pointer, _Alloc > pointer
The allocator&#39;s pointer type.
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:395
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:51
Base class for node handle types of maps and sets.
Definition: node_handle.h:65