libstdc++
node_handle.h
Go to the documentation of this file.
1 // Node handles for containers -*- C++ -*-
2 
3 // Copyright (C) 2016-2021 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 201606
38 
39 #include <new>
40 #include <bits/alloc_traits.h>
41 #include <bits/ptr_traits.h>
42 
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>
65  {
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 
87  {
88  if (!empty())
89  _M_reset();
90  }
91 
93  : _M_ptr(__nh._M_ptr)
94  {
95  if (_M_ptr)
96  _M_move(std::move(__nh));
97  }
98 
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 
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:
295 
296  _Node_handle(typename _AllocTraits::pointer __ptr,
297  const _NodeAlloc& __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
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:
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>
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
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:392
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1639
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
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:155
Uniform interface to all allocator types.
__detected_or_t< value_type *, __pointer, _Alloc > pointer
The allocator's pointer type.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr void destroy(_Alloc &__a, _Tp *__p) noexcept(noexcept(_S_destroy(__a, __p, 0)))
Destroy an object of type _Tp.
Base class for node handle types of maps and sets.
Definition: node_handle.h:65
Node handle type for maps.
Definition: node_handle.h:253
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:395
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:101